How to wiggle sort an array in linear time complexity?

Some characterizations of wiggle-sort
Skip this section if you would like to see the algorithms right away.$\def\A{\mathcal A}$ $\def\S{\mathcal S}$
Given an array $\A=(\A_0,\A_1, \cdots, \A_{n-1})$ of numbers, let us call the $\lceil n/2\rceil$-th smallest entry in $\A$ as well as each entry that is equal to that entry a median of $\A$. (This definition of median differs slightly from its usual definition when $n$ is even. For example, the median of $(3,4)$ is $3$ instead of $3.5$)
Call $A$ wiggle-sorted if $\A_0<\A_1>\A_2<\A_3>\A_4<\cdots$. Call $A$ wiggle-sortable if we can rearrange its entries so that it becomes wiggle-sorted. An array is always wiggle-sortable if all numbers in it are distinct. If all numbers are not distinct, the array may or may not be wiggle-sortable. For example, $[1,2,2]$ is not wiggle-sortable while $[1,1,2]$ is wiggle-sortable.
A permutation of $\{0,1,\cdots, n-1\}$, $\sigma$, is called a wiggling permutation if $\sigma(\A)=(\A_{\sigma(0)},\A_{\sigma(1)}, \cdots, \A_{\sigma(n-1)})$ is wiggle-sorted as long as $\A$ is sorted.
For all $n$, define a permutation $$w_n=\pmatrix { 0 &1 &2 &3 &4&5&\cdots\\m &n-1 &m-1 &n-2 &m-2 &n-3 &\cdots},$$
where $m=\lceil n/2\rceil-1$. For example,
$$w_5=\pmatrix { 0 &1 &2 &3 &4 \\2 &4 &1 &3 &0},$$
$$w_8=\pmatrix { 0 &1 &2 &3 &4&5&6&7\\3 &7 &2 &6 &1 &5 &0 &4}.$$
Characterization of wiggle-sortable arrays. The following propositions are equivalent.

$\A$ is wiggle-sortable of size $n$.
(Not too many medians) The number of medians of $A$ is no more than $\lceil n/2\rceil$.
If we have just sorted $A$ (in the usual sense), then $w_n(\A)$ is wiggle-sorted.

Uniqueness of wiggling permutation. For even size $n$, $w_n$ is the unique wiggle permutation. For odd size $n$, $w_n$ and $\overline{w_n}$ are the only two wiggling permutations, where $\overline{w_n}$ is the "reverse" of $w_n$, i.e., $\overline{w_n}(i)=n-1-w_n(i)$ for all $i$.

This uniqueness explains the fact that all solutions to the wiggle-sort problem arrange the given array the same way basically.

Here is the problem again: given an array of numbers, how can we wiggle-sort it?
A simple approach that runs in $O(n\log n)$ time
The easiest approach to implement, as illustrated in the question, is to sort the array, explicitly or implicitly, and rearrange the array.
Input: an array $\A$ of $n$ numbers with indices $0, 1, n-1$.
Output: None if $\A$ is not wiggle-sortable. Otherwise, return $\A$ that has been wiggle-sorted.
Procedure:

Sort $A$ into a temporary array. (Most sorting libraries run in $O(n\log n)$ time on average.)
Copy the largest number, the next largest number, and so on of the temporary array to $A$ at index $1, 3, 5,\cdots$ until the index is out of bound.
Copy the next largest number, the next largest number, and so on of the temporary array to $A$ at index $0, 2, 4,\cdots$ until all numbers are exhausted.
Check if the $\A$ is wiggle-sorted. Return accordingly.

# assume the given array, nums is wiggle-sortable
def wiggle_sort(nums):
    arr = sorted(nums)
    for i in range(1, len(nums), 2): nums[i] = arr.pop()
    for i in range(0, len(nums), 2): nums[i] = arr.pop()

To achieve better performance, we have to avoid sorting the array.

The outline of a faster algorithm
Procedure:

find the median of $\A$ by some $O(n)$ algorithm.
Count the number of all medians. If it is greater than $\lceil n/2\rceil$, return None.
Put all entries larger than the median in positions with odd indices,  $1, 3, 5,\cdots$ in that order.
Put all entries smaller than the median in positions with even indices from the largest-even-indice going downwards.
Fill the remaining entries of $A$ with the median. Return $\A$.

The problem is shifted to how to find the median and arrange the numbers
Find the median in linear time and constant space
To implement the algorithm in linear time and constant space we need to find the median in linear time and constant space.
There are various ways to achieve that deterministically, for example, linear-time in-place selection in less than 3n comparisons, 2005 and linear-time in-place selection with ⋅ element moves, 2006. Unfortunately, all these algorithms are somewhat complicated.
We can find the median in average linear time and constant space using a simple algorithm, quickselect. Here is the python code.
def k_smallest(nums, k, start, end):
    """
    Returns the k-th smallest number in nums[start:end+1].
    """
    if k <= 0 or end - start < k - 1:
        return None

    k = start + k - 1

    while True:
        if start >= end:
            return nums[start]

        # pivot = nums[random.randint(start, end)]
        pivot = nums[end]
        left, right, m = start, end, start
        while m <= right:
            if nums[m] < pivot:
                nums[left], nums[m] = nums[m], nums[left]
                left += 1
                m += 1
            elif nums[m] > pivot:
                nums[right], nums[m] = nums[m], nums[right]
                right -= 1
            else:
                m += 1
        if left <= k <= right:
            return pivot
        elif k < left:
            end = left - 1
        else:  # k > right
            start = right + 1

m = k_smallest(nums, (n + 1) // 2, 0, len(nums) - 1)  # m is the median

If we relax the space requirement slightly, we can find the median in linear-time and logarithmic-space using the median of medians algorithm.
Arrange the numbers in linear time and constant space
Once the median has been found, the problem is shifted to arrange the number as specified. Any reasonable implementation will run linear time. What is not obvious is how to do it in constant space as well.
We can imagine the entries of $\A$ is actually arranged in the memory consecutively as $A_1$, $A_3$, $A_5$, $\cdots$, $A_{n_1}$, $A_0$, $A_2$, $A_4$, $\cdots$, $A_{n_0}$, where $n_1$ and $n_0$ are the largest odd and even number not exceeding $n$.  Here is the explicit access pattern when $n=8$:
$\quad$ Accessing memory at index 0 actually accesses $A_1$.
$\quad$ Accessing memory at index 1 actually accesses $A_3$.
$\quad$ Accessing memory at index 2 actually accesses $A_5$.
$\quad$ Accessing memory at index 3 actually accesses $A_7$.
$\quad$ Accessing memory at index 4 actually accesses $A_0$.
$\quad$ Accessing memory at index 5 actually accesses $A_2$.
$\quad$ Accessing memory at index 6 actually accesses $A_4$.
$\quad$ Accessing memory at index 7 actually accesses $A_6$.
Or, in general, the memory at the index $p$ refers to $\A_{(1+2p)\pmod{n\,|\, 1}}$.
With this mapping between indices, the problem is transformed to the Dutch national flag problem or, what is the same, the tri-color problem on LeetCode. We can apply the tri-color algorithm almost verbatim, which runs in $O(n)$ time and $O(1)$ space (thanks to StefanPochmann for his post).
# Put numbers larger than pivot at smallest odd-indices.
# Put numbers smaller than pivot at largest even-indices.
def tri_color_clustering(nums, pivot):
    n = len(nums)

    def map_index(p):
        return (1 + 2 * p) % (n | 1)

    i, j, k = 0, 0, n - 1
    while j <= k:
        if nums[map_index(j)] > pivot:
            nums[map_index(j)], nums[map_index(i)] = nums[map_index(i)], nums[map_index(j)]
            i += 1
            j += 1
        elif nums[map_index(j)] < pivot:
            nums[map_index(j)], nums[map_index(k)] = nums[map_index(k)], nums[map_index(j)]
            k -= 1
        else:
            j += 1
    # print(nums)

A previous version of this answer shows a simple and fast algorithm to wiggle sort an array in $O(n)$ time and $O(1)$ space, assuming all numbers in the given array are distinct.


Arithmetic network to compute floor of binary logarithm

It can be done with a fairly simple log-depth circuit without resorting to such hacks that only really make sense in software.

The "position of most significant set bit" function pmsb can be defined recursively:

$\begin{split}pmsb(``0") &= Nil \\
pmsb(``1") &= Nil \\
pmsb(a:b) &= ``0":pmsb(b) \text{ if a=0}\\
&= ``1":pmsb(a) \text{ otherwise}
\end{split}$

Where : divides a power-of-two string down the middle or concatenates two strings, depending on its context.

This can already be implemented as a circuit, but it includes some annoying wide comparisons. They can be removed by returning a tuple with an extra bit that tracks the zero-ness of the whole string (it is applied to the halves so you get the result from the halves in the recursion):

$\begin{split}pmsb(``0") &= (Nil, T) \\
pmsb(``1") &= (Nil, F) \\
pmsb(a:b) &= \text{let } (pa, za) = pmsb(a) \\
&\phantom{=}\quad\quad (pb, zb) = pmsb(b) \\
&\phantom{=}\;\; \text{in if } za \text{ then } (``0":pb, zb)\\
&\phantom{=}\quad\quad\quad\quad\text{else } (``1":pa, F)
\end{split}$

This can then be evaluated bottom-up by a circuit of depth O(log n) and size O(n) where n is the length of the bit-string at the top level, which must be a power of two and not one. The zeroness bit circuit has the structure of an AND-reduction, but it is used at the intermediate nodes instead of only at the end. The main result is computed by a similar tree of MUXes that take those bits as control input.


I'm afraid that the answer to all your questions is false:

There are languages decided by constant size circuits which aren't decidable.
It is conjectured that $\mathsf{NC^1} \neq \mathsf{P}$.
It is conjectured that $\mathsf{NP} \neq \mathsf{coNP}$.


Returning two array indices in an array for a given value

Yeah, bisection'll maximize the information gained from each check.  If you do any sort of check other than bisection, then in the worst-case, the sought element'll be on the larger section of the selected divide.

The worst-case scenarios will occur whenever bisection has to happen $O\left(\log{n}\right)$ times to find the first/last indices of the selected value, x.  For example, if the array's all the same value, e.g. A=[0,...,0], then bisection'll have to occur until the algorithm whittles it down to the first 0 at $i=0$, then a separate bisective search would have to go just as many times to find the last 0 at $i=n_{\mathrm{length}}-1$.

Both searches'll be $O\left(\log{n}\right)$.  But since two sequential $O\left(\log{n}\right)$ processes are still just $O\left(\log{n}\right)$, the overall algorithm's $O\left(\log{n}\right)$.


Simulating a probability of 1 of 2^N with less than N random bits

Wow, great question!  Let me try to explain the resolution.  It'll take three distinct steps.

The first thing to note is that the entropy is focused more on the average number of bits needed per draw, not the maximum number of bits needed.

With your sampling procedure, the maximum number of random bits needed per draw is $N$ bits, but the average number of bits needed is 2 bits (the average of a geometric distribution with $p=1/2$) -- this is because there is a $1/2$ probability that you only need 1 bit (if the first bit turns out to be 1), a $1/4$ probability that you only need 2 bits (if the first two bits turn out to be 01), a $1/8$ probability that you only need 3 bits (if the first three bits turn out to be 001), and so on.

The second thing to note is that the entropy doesn't really capture the average number of bits needed for a single draw.  Instead, the entropy captures the amortized number of bits needed to sample $m$ i.i.d. draws from this distribution.  Suppose we need $f(m)$ bits to sample $m$ draws; then the entropy is the limit of $f(m)/m$ as $m \to \infty$.

The third thing to note is that, with this distribution, you can sample $m$ i.i.d. draws with fewer bits than needed to repeatedly sample one draw.  Suppose you naively decided to draw one sample (takes 2 random bits on average), then draw another sample (using 2 more random bits on average), and so on, until you've repeated this $m$ times.  That would require about $2m$ random bits on average.

But it turns out there's a way to sample from $m$ draws using fewer than $2m$ bits.  It's hard to believe, but it's true!

Let me give you the intuition.  Suppose you wrote down the result of sampling $m$ draws, where $m$ is really large. Then the result could be specified as a $m$-bit string.  This $m$-bit string will be mostly 0's, with a few 1's in it: in particular, on average it will have about $m/2^N$ 1's (could be more or less than that, but if $m$ is sufficiently large, usually the number will be close to that).  The length of the gaps between the 1's are random, but will typically be somewhere vaguely in the vicinity of $2^N$ (could easily be half that or twice that or even more, but of that order of magnitude).  Of course, instead of writing down the entire $m$-bit string, we could write it down more succinctly by writing down a list of the lengths of the gaps -- that carries all the same information, in a more compressed format.  How much more succinct?  Well, we'll usually need about $N$ bits to represent the length of each gap; and there will be about $m/2^N$ gaps; so we'll need in total about $mN/2^N$ bits (could be a bit more, could be a bit less, but if $m$ is sufficiently large, it'll usually be close to that).  That's a lot shorter than a $m$-bit string.

And if there's a way to write down the string this succinctly, perhaps it won't be too surprising if that means there's a way to generate the string with a number of random bits comparable to the length of the string.  In particular, you randomly generate the length of each gap; this is sampling from a geometric distribution with $p=1/2^N$, and that can be done with roughly $\sim N$ random bits on average (not $2^N$).  You'll need about $m/2^N$ i.i.d. draws from this geometric distribution, so you'll need in total roughly $\sim Nm/2^N$ random bits.  (It could be a small constant factor larger, but not too much larger.)  And, notice is that this is much smaller than $2m$ bits.

So, we can sample $m$ i.i.d. draws from your distribution, using just $f(m) \sim Nm/2^N$ random bits (roughly).  Recall that the entropy is $\lim_{m \to \infty} f(m)/m$.  So this means that you should expect the entropy to be (roughly) $N/2^N$.  That's off by a little bit, because the above calculation was sketchy and crude -- but hopefully it gives you some intuition for why the entropy is what it is, and why everything is consistent and reasonable.


Solving this problem benefits from geometrical intuition. Think that for each index $i$, the pair $(i, A[i])$ represents a point in 2D-space. Also we can think that assigning $A[j]=0$ is the same as removing the point $(j, A[j])$ from this space. Now a query with index i means removing all points that are left and below of point $(i, A[i])$.

Now the set of removed points can be represented with a set of points $(i_1, A[i_1]), (i_2, A[i_2]), \ldots, (i_k, A[i_k])$, for which $i_p < i_{p+1}$ and $A[i_p] < A[i_{p+1}]$ for all $1 \le p < k$. A point $(j, A[j])$ is removed if there is some $p$ for which $i_p < j$ and $A[i_p] > A[j]$. The picture https://en.wikipedia.org/wiki/Maxima_of_a_point_set#/media/File:Maxima_of_a_point_set.svg from Wikipedia might gives intuition for this (though it is left-right mirrored compared to our definition).
This set representation can be maintained with a balanced binary search tree. We can check in $O(\log n)$ time if a point $(j, A[j])$ is removed by finding the largest $i<j$ such that $(i, A[i])$ is in the set, and checking if $A[i] > A[j]$. For performing the query in your problem, first check if the given point $(i, A[i])$ already is removed. If it's not, insert it into the set in $O(\log n)$ and repeatedly check if the next element with $j>i$ has $A[j] < A[i]$, and remove it. This can be done in $O(k \log n)$, where $k$ is the number of removed elements, so the amortized complexity if $O(\log n)$.

In summary, your queries can be answered in $O(\log n)$ amortized complexity.


Defining computable functions on arbitrary sets

Effective model theory studies computable structures. The collection of all finite trees is a two-sorted computable structure in which one sort consists of vertices (which can be identified with the natural numbers) and the other sort consists of trees. It has the following relations:

$\operatorname{vertex}(x)$, which is true if $x$ is a vertex.
$\operatorname{tree}(x)$, which is true if $x$ is a tree.
$\operatorname{appears}(x,T)$, which is true if $x$ is a vertex that appears in the tree $T$.
$\operatorname{edge}(x,y,T)$, which is true if $x,y$ are two vertices in $T$ which are connected by an edge.

(We don't really need both $\operatorname{vertex}$ and $\operatorname{tree}$, but we do need to be able to express being in the domain of the structure, i.e., either a vertex or a tree.)

Formally speaking, to complete the definition of the structure we have to specify an encoding of the domain, either as strings or as natural numbers (this is an arbitrary choice which doesn't make much difference). Under any reasonable encoding, all the relations above will be computable, and so we have a computable structure.

A computable presentation of this structure is an isomorphism which maps this structure to another computable structure. This mapping has to be an isomorphism of structures, but it doesn't have to be computable. A computable structure $\mathcal{A}$ is computably categorical if whenevever $\mathcal{A}$ is isomorphic to a computable structure $\mathcal{B}$ (by a computable presentation), then there is a computable isomorphism between the two structures.

Using this vocabulary, what you might be asking is whether the computable structure of finite trees is computably categorical. (There is actually more freedom in your question, since you might want to use a different relational structure.) Some simple computable structures are computably categorical (for example, the rationals with the order relation, and the natural numbers with the successor function) and some aren't (for example, the natural numbers with the order relation), see Computable structures: presentations matter by Shore.


If $T(n+1)=T(n)+\lfloor \sqrt{n+1} \rfloor$ $\forall n\geq 1$, what is $T(m^2)$?

For a slightly different way to look at his problem, consider your original equation,
$$
T(n) = T(1)+\lfloor\sqrt2\rfloor+\lfloor\sqrt3\rfloor+\dotsb+\lfloor\sqrt n\rfloor
$$
Now the key here is to group the terms with the same values of $\lfloor\sqrt k\rfloor$:
$$\begin{align}
T(n) &= (T(1)+\lfloor\sqrt2\rfloor+\lfloor\sqrt3\rfloor)\\
 &+(\lfloor\sqrt4\rfloor+\lfloor\sqrt5\rfloor+\lfloor\sqrt6\rfloor+\lfloor\sqrt7\rfloor+\lfloor\sqrt8\rfloor)\\
 &+(\lfloor\sqrt9\rfloor+\lfloor\sqrt{10}\rfloor+\lfloor\sqrt{11}\rfloor+\lfloor\sqrt{12}\rfloor+\lfloor\sqrt{13}\rfloor+\lfloor\sqrt{14}\rfloor+\lfloor\sqrt{15}\rfloor)\\
 &+\dotsc
\end{align}$$
and observe that each summand will have $2k+1$ terms, since the difference $(k+1)^2-k^2 = 2k+1$:
$$
T(n) = (1\cdot3)+(2\cdot5)+(3\cdot 7)+(4\cdot 9)+\dotsb
$$
so we'll have, with $n=m^2$
$$\begin{align}
T(m^2) &= (1\cdot3)+(2\cdot5)+\dotsb+\left(\left\lfloor\sqrt{(m-1)^2}\right\rfloor+\dotsb+\left\lfloor\sqrt{m^2-1}\right\rfloor\right)+\left\lfloor\sqrt{m^2}\right\rfloor\\
 &=\sum_{k=1}^{m-1}k(2k+1)+m =\sum_{k=1}^{m-1}(2k^2+k)+m\\
 &=2\sum_{k=1}^{m-1}k^2+\sum_{k=1}^{m-1}k+m\\
 &=2\frac{(m-1)(m)(2(m-1)+1)}{6}+\frac{(m-1)(m)}{2}+m\\
 &=\frac{m}{6}(4m^2-3m+5)
\end{align}$$
as required.


As the definition of the 2NF is:

  A functional dependency on part of any candidate key is a violation of 2NF. In addition to the primary key, the relation may contain other candidate keys; it is necessary to establish that no non-prime attributes have part-key dependencies on any of these candidate keys.

This schema is not in 2NF.


Peterson Algorithm for process synchronisation

Firstly, since the program at the start the question starts with "flag[$i$] = true", it should be run by Process $i$. Here is the full program again formatted slightly better. Note that the I replace "Enter critical section" and "exit critical section" with comment "// inside the critical section", since there is no code that actually corresponds to them. Once the process breaks out of the "while (P)  do no-op" loop, it is in the critical section (CS). The process is exiting the critical section at the exact point of time when it is executing "flag[$i$] = false".

  repeat

  flag[$i$] = true;
  turn = $j$;
  while ($P$) do no-op;
  Perform some actions  // inside the critical section
  flag[$i$] = false;
  Perform other non-critical section actions.

  Until false;

The following is the full program run by Process $j$. You should be able to figure out the code represented by $Q$ once you have accepted my answer. :)

  repeat

  flag[$j$] = true;
  turn = $i$;
  while ($Q$) do no-op;
  Perform some actions   // inside the critical section
  flag[$j$] = false;
  Perform other non-critical section actions.

  Until false;

These two different programs together that are run by two different processes respectively at the same time competing for (some resources inside) the critical section (CS) is Peterson's algorithm.

Secondly, there is a fatal typo in the "important lines from the algorithm" with line numbers in the question. The second line

  2) turn = process ;

should be

  2) turn = other ;

Indeed, this line is the key to understand how Peterson's algorithm ensures mutual exclusion. Please note "the important lines from the algorithm" are executed sequentially at the same time by two processes, each considering itself as the "process" and the other process as "other" in those "important lines".  By executing this line, each process tries letting the other process to have a higher priority over itself to enter CS..

A minor typo in OP's question is "while (interested [other] == True" should be "while flag [other] == True".

Thirdly, OP asks which process is exactly currently executing. The answer is not just Process $i$. The answer is not just Process $j$. The answer is both processes. In fact, we can assume both process are executing at all times, each executing a different program. That is what we mean by concurrent processes or concurrent programming. Is it surprising? Please note, however, if the question is which process is exactly executing the program written at the start of OP's question, then, as I have said at first, the answer is Process $i$.

Fourthly, OP asks "which process are we blocking in while loop i.e stopping to enter CS?". Of course, the answer is the current process, that is, the process that is currently executing that line of code. It is the other process if you write the loop uniformly as "while (flag [other] == True && turn == process)", which can be either Process $i$ or $i$. It can only be Process $i$ if the loop is "while (flag[$j$] = true and turn = $j$)". It can only be Process $j$ if the while loop is "flag[$i$] = true and turn = $i$)".

Lastly, the "option b) flag[$j$] = true and turn = $j$" should be what $P$ stands for. Here "flag[$j$] = true" means process $j$, the other process, is interested in entering or staying in the critical section(CS) while "turn = $j$" say that the other process is either holding CS or, if other process is interested in entering CS, it has the priority over the current process to enter CS. Both conditions together imply the current process cannot enter CS. Once Process $j$ is not interested in CS by setting flag[$j$] to false, or once the value of variable "turn" is $i$, meaning Process $i$ has a higher priority over Process $j$ to enter CS, the "while (P)" loop is broken and Process $i$ is in CS. (I am avoiding to say "enter CS" here, just to emphasize the fact that there is no other code that enables or represents the act of entering CS. Process $i$ enters CS by breaking out of that while loop.)

All other options, (a), (c) and (d), are apparently wrong. For more detailed analysis, please check Peterson algorithm at Wikipedia.


Reduction to a vertex cover problem-like with weighted vertices and edges

This problem is a generalization of Dominating Set, and if you let weights of vertices and edges be 1, then you have exactly Dominating Set.

The problem definition of Dominating Set is:

  Given a graph $G = (V, E)$ and an integer $k$, is there a set $V' \subseteq V$ of size at most $k$ such that the distance of any vertex $v \in V \setminus V'$  to $V'$ is 1.

(This is assuming that the distance from $v' \in V'$ to $V'$ is defined as 0.)

It follows that WVE is NP-hard.  This is occasionally called proof by generalization.


Why not relax only edges in Q in Dijkstra's algorithm?

The condition

  min.priority + weight(min,v) < v.priority

can only be true if $v$ is in the queue. If a vertex $v$ has been removed from $Q$ the invariant of Dijkstra's algorithm guarantees we've already found the shortest path to $v$.

Edit: Proof Sketch
Suppose v isn't in Q. Then we must have already found the shortest path to v. Now if we later examine a vertex u connected to v, the condition min.priority + weight(min,v) < v.priority must be false, otherwise we would have found a shorter path to v which is a contradiction.


There is quite a bit of work on this important problem. Some of the most
insightful work is by Helmut Alt and collaborators. He wrote a survey in 2009:

  Helmut Alt. "The computational geometry of comparing shapes." Efficient Algorithms. Springer Berlin Heidelberg, 2009. 235-248.
  (Springer link.)

Image from Helmut Alt & Leonidas J. Guibas.
"Discrete geometric shapes: Matching, interpolation, and approximation." Handbook of computational geometry 1 (1999): 121-153.).


Let's see what we can do. Values are random and hence are incompressible, but keys can be sorted and then diffed. So, just sort the data, employ difference compression schema for keys and use binary search to find.

It will put your N keys+values into minimum amount of bits required to keep this amount of information.

May be, you can further improve compression ratio by dropping less compressible items.

EDIT: As mentioned here, you can compress keys to smaller values. So, f.e. you can use Bloom filter to check that probed key is included in the result set, and then use compressed 32-bit hash of the key to find it in table with 64K entries with pretty high fidelity. NOTE: at more thorough analysis I realized that Bloom filter will occupy at least the same space you will economy on reducing key values stored in the sorted table.

PS: You can use any rehashing scheme, including Cuckoo hashing, to cut off rehash chains at some point, but anyway sorted sequence should be better compressible than any hashtable containing unused cells.

Perfect hashing just helps you to make hashtable without holes. I don't know what signature you mean here.

Bloom filter by itself only checks value presence, then you still need to store entire key+value pair.


I have found the answer. External fragmentation happens over time when small spaces in memory are not effectively employed. This leads to hole everywhere in memory. Therefore it cannot be determined from the chart that there is external fragmentation.

On the other hand, internal fragmentation is the idea when there is over-allocation of memory space to a process. In the above chart, internal fragmentation depends on the page/frame size. Since it is possible for a page to only have one byte of data then larger page sizes have more internal fragmentation. Design 3 has the most spread which is the answer.


Forward Error Correction for streaming data

tl;dr: This solution is quite good for random noise, but fails for bursty noise, or if you wish to get extremely low failure probability.

Random Noise

Assume the average noise (across the entire stream) is 10%, that is, each symbol is flipped with probability 0.1.
The naive approach you suggest can be summarized as taking small chunks of data ("small" with respect to the size of the stream), and encoding each chunk individually via some ECC.
For instance, a single chunk may be of length $\log N$, while the stream is of length $N$. Then, if you use ECC on that chunk (and expand it into length $C\log N$, for some large constant$~C$), there is a probability of $\approx 2^{-C\log N}$ that it will be decoded incorrectly. Taking a union bound over the entire stream, there is only a polynomially small probability that some chunk of data will fail.

If polynomially-small failure probability is good for you - you are golden. Otherwise, you will have to take ECC with larger redundancy, and this may be impractical. There's also an issue of delay, but that is secondary here.

Bursty noise

A different problem arises when the noise is not random, but adversarial, or even simpler, just bursty. Here again we can assume that 10% of the transmissions are noise, however they can come as a single burst of noise, corrupting  $N'/10$ consecutive transmissions. Clearly, the above naive solution will fail, since there are many codewords that will be completely noisy. Note that even if you increase the redundancy of each encoding, this will not help. The only solution is to increase the chunk size (that is, to send at most 10 encoded chunks), but this is terrible in terms of delay.

One solution to the bursty noise is send the information in a random order. If the transmission is long enough and the information is spread across this transmission quite evenly, then even a burst of noise "behaves" like a random noise with high probability (i.e., it will corrupt the codewords in balanced manner, and will have low probability to completely corrupt a single codeword). This might not be enough.

Using stronger codes (that have an "online" property) can help resisting more noise, improve the delay and reduce the failure property to be exponentially small. See Franklin et al., "Optimal Coding for Streaming Authentication and Interactive Communication" (IEEE Trans. Info. Theory. 61:133-145, 2015). There is also a similar encoding scheme that works for sliding windows rather than unbounded streams, see "Efficient Error-Correcting Codes for Sliding Windows".


What happens with register usage in deeply nested functions calls (in theory)?

Ignore recursion for the moment, and pretend that a recursive call is just like any other call.

Then the solution is easy: all local variables are spilled to the stack across calls, including the recursive call. So yes, if there is deep recursion going on, most of the local variables will reside on the stack most of the time.

Every platform (operating system + CPU family) defines a protocol called the application binary interface, or ABI for short. This specifies how parameters are passed to a function, how values are returned, how the stack is to be managed, and so on. If you want to see what a real-world ABI looks like, see the SysV ABI for Intel x86-64/AMD64. Almost all operating systems follow this ABI on that family of CPUs, with Windows being the most notable exception.

The ABI will specify that some registers are not preserved across function calls (i.e. they are caller-save) and some are preserved (i.e. they are callee-save). A callee-save register must be preserved by a function if it wants to use that register, and a caller-save register must be explicitly spilled across a call if the caller needs the value.

It's also possible to optimise recursion, as long as the function ultimately presents itself to the rest of the system as if it obeys the ABI. This is where things get interesting.

Tail call optimisation is the most common scenario. If the last thing that a function does in some code path is to call another function, it's sometimes possible to transform the last call into a jump. And if it's a recursive call, then it can be transformed into a loop.

So this:

foo(args)
{
    if (the base case applies) {
        return something();
    }
    before_the_recursive_call();
    foo(recursive_args);
}

can be transformed into this:

foo(args)
{
    while (the base case doesn't apply) {
        before_the_recursive_call();
        args = recursive_args;
    }
    return something();
}

But in that case, no local variables have to be saved across that final call. So nothing, in theory at least, needs to be spilled to the stack there.

As an aside, in C++, the semantics of RAII and exception handling often makes tail call optimisation impossible, so you won't often see this in compilers for the C family of languages.

There is a related optimisation called "middle recursion optimisation", which is used for the more familiar recursive scenario, where there is a single recursive call in the middle of a function:

foo(args)
{
    if (the base case applies) {
        return something();
    }
    before_the_recursive_call();
    foo(recursive_args);
    return after_the_recursive_call();
}

This can be transformed into something like this:

foo(args)
{
    while (the base case does not apply) {
        before_the_recursive_call();
        push_anything_to_the_stack_that_the_last_part_needs();
        args = recursive_args;
    }

    return_value = something();  // base case

    while (pop_the_stack()) {
        return_value = after_the_recursive_call();
    }
    return return_value;
}

Again, this is rare in C-like languages. You would more typically find it in functional or logic languages which don't have loop constructs, and only have recursion. In a language like that, it's often worth going to a lot of trouble to optimise recursion into loops.


Proving that a word is *not* generated by a context-free grammar

Let's assume you want to show that some word $w$ of length $n$ is not in the language generated by some grammar context-free $G$.

You can solve the problem algorithmically. There are two approaches:

Enumerate all strings in $L(G)$ of length at most $n$. In order to do that,

transform the grammar in Chomsky normal form and
enumerate all derivations with at most $n$ rule applications.

This works since every rule application adds one terminal symbol in CNF (there are no $\varepsilon$-rules). If your original grammar has this property (as does the one in your question), you can skip the transformation in CNF.

This is tractable for small $n$ and/or grammars with few words per length. As soon as $L(G)$ grows fast with $n$, it breaks down.
Parse $w$, for instance with the CYK algorithm. This runs in time $\Theta(n^3)$ and feasible for most grammars and inputs of reasonable size.

Clearly, the latter is the better option in an algorithmic mindset, but the former might be prudent if you have to make a quick decision given a short word in an exam-like situation.


Fundamental motivation behind the use of bits and binary representation

Well, the fact is that binary values are much easier to handle technically that ternary values. And there are reasons for it. So if there was some technical breakthrough where suddenly ternary values become easy to handle, there would be a good reason to believe that binary values would have a similar breakthrough very soon.

So yours is a purely hypothetical question. And you are making assumptions about how people would react in a purely hypothetical situation.

In lots of situations, for many algorithms, binary or ternary doesn't matter. At a high level, we just talk about integers. But for many basic operations, ternary is at a disadvantage. Design a format for signed integers. Preferably one where the same representation is used for positive signed integers and for unsigned integers. You have a problem unless you use one trit and use it as a sign bit. Which means you now have a representation where not every trit value is valid.

Floating-point arithmetic: I don't remember if it was Knuth and Kahan who showed that "round to nearest even" has some very nice properties, and then showed that you have these nice properties whenever the floating-point base is 8k + 2 (including binary and decimal, what a luck) but not for base 3.

Design the logic for a full-adder. Two inputs from 0 to 2 and one input 0 or 1 (the carry from the previous operation). Quite complicated. Much much more complicated than binary. Going one level down, is there anything like NAND and NOR for trits that can serve as the basis of all logical operations? Try creating a fast multiplier. For binary, the basis for this is an operation which produces x*0 or x*1. Now you need something that produces x*0, x*1 or x*2. Wait, that can't be stored in a single trit. Trouble. Plus you can't use the ordinary full adder to finish off the fast multiplier.


Probability with an unusual pseudo-random generator

The key here is the part of the problem that says "each value, $v$ occurs with a probability that is inversely proportional to $v$". You can do this by assigning $$
P(1)=c, P(2)=\frac{c}{2}, P(3)=\frac{c}{3}, P(4)=\frac{c}{4}
$$
Then, since these values are the only ones possible, we'll have
$$
c\cdot 1+\frac{c}{2}+\frac{c}{3}+\frac{c}{4} = 1
$$
so
$$
1 =c(1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}) = c\cdot\frac{25}{12}
$$
and so $c=12/25$, giving us $P(1)=12/25, P(2)=6/25, P(3)=4/25, P(4)=3/25$. It's easy to see that these satisfy the requirements of the problem.


How can a one-counter machine accept $a^n b^n c^n$?

Be careful where the hyphens are! One counter-machine can recognize $a^n b^n c^n$, but a one-counter machine cannot.

From the answer you linked to:

  Languages recognized by one[-]counter automata form a proper subset of the context free languages.

(There's a proof for this, but it's long and boring, so I'm going to leave it out; you can find it online if you're interested.)

Since $a^n b^n c^n$ is not context-free, it cannot be recognized by a one-counter automaton.

It can, however, be recognized by a two-counter machine (a machine with two counters). The basic structure goes something like this:

When you see an $a$, increment $X$, increment $Y$
When you see a $b$, decrement $X$
When you see a $c$, decrement $Y$
Accept iff the letters are in the right order (a trivial state machine), AND $X = 0$, AND $Y = 0$

This is "one counter-machine" (in the sense that it's a single machine using counters). But you need at least two counters to do it.


Theory of Complexity - Relation between a class and its complement

The first part is easy since there is a $C$-complete problem that belongs to $coC$ and since all problems in $C$ are reduced to that complete problem, $C \subseteq coC$

As for the second part let $L_C$ be a $C$-complete problem that belongs to $coC$. Then by definition of $coC$, $\overline{L}_C \in C$. So, $\overline{L}_C$ are in $C$ (decidable in $C$). Also since $L_C$ is $C$-complete, for any language $L \in C$ there is a reduction $f$ such as $x \in L \Leftrightarrow f(x) \in L_C$.

Now, if a problem $L \in coC$ then $\overline{L} \in C$ and $x \in \overline{L} \Leftrightarrow f(x) \in L_C$ meaning that $x \in L \Leftrightarrow f(x) \in \overline{L}_C$. So $L$ is reduced to $\overline{L}_C$ which is in $C$. Thus $coC \subseteq C$.


If you have unlimited physical access to the CPU, then you can send your own instructions into it, including instructions to read from arbitrary memory addresses. Looking at the voltages on the data bus then shows you exactly what's in that word of memory.

Remember, any data the computer is able to use, has to be accessible by at least one CPU. That's just how it works. So access to the CPU gives you theoretical access to everything else.

(Note: this is an answer to the question in the body, not the question in the title.)


Apparently, we're given a collection of equations of the form

$$|x_i - x_j| = c_{i,j},$$

where the $c_{i,j}$ are given and $x_1,\dots,x_n$ are the unknowns to solve for.  We want to look for a valid solution that satisfies all of the equations, and where the values of $x_1,\dots,x_n$ are a permutation of $1,2,\dots,n$.

The kind of algorithm to use will probably depend upon how many equations we're given and the structure of the corresponding graph.  However, here is a simple case to start with, to give you some intuition:

Suppose that we are given a complete set of $n(n-1)/2$ equations: i.e., for all $i,j$, we are given $c_{i,j}$.  Then there is a polynomial-time algorithm to recover the $x_i$'s.  Basically, we'll leave $x_1$ as a variable, and we'll try to express every other $x_i$ in terms of $x_1$.  Define $\delta_i$ so that $x_i = x_1 + \delta_i$.  Here's how the algorithm works:

Guess $\delta_2$.  Note that it is either $c_{1,2}$ or $-c_{1,2}$, so there are only two possibilities.
Guess $\delta_3$.  Again, there are only two possibilities: $c_{1,3}$ or $-c_{1,3}$.
Check that $|\delta_2-\delta_3| = c_{2,3}$; if this doesn't hold, discard your current guess.  (This will eliminate $1/2$ of the wrong guesses.)
Guess $\delta_4$; there are only two possibilities.
Check that $|\delta_2-\delta_4| = c_{2,4}$ and $|\delta_3-\delta_4|=c_{3,4}$; if either doesn't hold, discard the current guess.  (This will eliminate at least $1/2$ of the wrong guesses.)
Continue in this way, alternately guessing $\delta_i$ and then checking the equations $|\delta_j-\delta_i|=c_{j,i}$ hold for all $j=2,3,\dots,i-1$.

What's the running time?  The expected running time to list all possible combinations for $\delta_2,\dots,\delta_n$ is $O(n)$.  In particular, at each step, we double the number of combinations we need to consider (since there are two possibilities for the guess), but then we halve the number of combinations we need to consider (since $1/2$ of the wrong guesses can be discarded by virtue of the fact that they violate at least one of the known equations).  Thus the expected number of guesses that remain at the $i$th step is a constant independent of $i$, which implies the running time bound above.

Finally, once you have a combination $\delta_2,\dots,\delta_n$, you can test whether it leads to a viable solution by checking all possible values of $x_1$, inferring the implied values of $x_2,\dots,x_n$ (using the known values for $\delta_2,\dots,\delta_n$), and then checking whether they are a permutation of $1,2,\dots,n$.  Each combination takes $O(n^2)$ time to check, so the overall running time of the algorithm is $O(n^2)$.  This can probably be reduced further, but it's enough to make it already a polynomial-time algorithm.

Now what if we're not given all of the equations?  Then we can apply a similar strategy, but the running time will depend upon the number of equations we're given and the structure of the graph they correspond to.  There's also some degree of freedom in the order that you guess $\delta_i$ values; it's not clear what the optimal strategy is, but probably it will involve looking for small highly-connected regions of the graph and starting with them first.  The best approach might depend upon the specific distribution on problem instances that arises in your practical setting.


This site may also offer you a resource for locating content similar to your paper. Most academic institutions and public libraries have free access to these sorts of research tools to look for published work in selected areas of research. Good Luck.

Click Here


What's the difference between $a^*+b^*$ and $(a+b)^*$?

$a^*+b^*$ generates words that either consist of any amount of $a$s or any amount of $b$s, like: $a$, $aaaaa$, $bbbb$
$(a+b)^*$ generates secquences of either $a$ or $b$, for example: $abab$, $aabb$, $bbaa$,...

So, the main difference is, that in 1 you either get strings only containing as or only containing bs. Regex 2 produces a language where you have no order of characters and can put both in.

So, both don't produce the same language, but 1 is a subset of 2.


General method behind converting recursive inorder, preorder and postorder traversals of a binary tree to a non-recursive one?

Can they be reformuated and/or created from the recursive implementations in some unified way, so that I can write them out by just looking at the recursive implementations?

Yes, they can be reformulated in a unified way.

We take the <pre/in/post>_order recursive calls together with the visit procedure call, reverse them and push the corresponding nodes on the stack s, marking each node with its purpose: TRAVERSE or VISIT. I think the examples below explain the idea better.

Preorder traversal

So, iterativePreorder can be reformulated as

iterativePreorder(node)
  s ← empty stack
  s.push(<node, TRAVERSE>)

  while (not s.isEmpty())
    <node, mark> ← s.pop()
    if node = null
      continue
    if mark = TRAVERSE
      s.push(<node.right, TRAVERSE>)
      s.push(<node.left, TRAVERSE>)
      s.push(<node, VISIT>)
    else
      visit(node)

It's easy to see the above pseudocode can be transformed into the iterativePreorder procedure provided in the question by

eliminating two consecutive push/ pop operations on the same node;
not pushing null-nodes on the stack.

In-order traversal

Skipping the boilerplate code, we get:

iterativeInorder(node)
...
    if mark = TRAVERSE
      s.push(<node.right, TRAVERSE>)
      s.push(<node, VISIT>)
      s.push(<node.left, TRAVERSE>)
...

Postorder traversal

iterativePostorder(node)
...
    if mark = TRAVERSE
      s.push(<node, VISIT>)
      s.push(<node.right, TRAVERSE>)
      s.push(<node.left, TRAVERSE>)
...

The iterativeInorder and iterativePostorder procedures cited in the question don't look like the above code because they make use of the traversal patterns arising in those cases. Like the fact that under in-order traversal we go straight to the leftmost leaf of the input tree, visit it, go one level up and do the same thing for the right subtree of the current node, etc.


How to prove that finding math proofs is $\text{NP}$-hard?

Define $\mathrm{Bool}$ to be the set of all subsets of $\{\varnothing\}$ (or some arbitrary set with 1 element). Then represent a propositional variable $x$ by some subset $x\in\mathrm{Bool}$, i.e. $x\subseteq\{\varnothing\}$.

Now there is an extremely straightforward translation $\rho$ of propositional formulae into such subsets:

$\rho(x)$ if $x$ is a variable is just some set (also called $x$) $\in\mathrm{Bool}$.
$\rho(\neg\phi)$  into the complement of $\rho(\phi)$ in $\mathrm{Bool}$.
$\rho(\psi\vee\phi)=\rho(\psi)\cup\rho(\phi)$
$\rho(\phi\wedge\psi)=\rho(\psi)\cap\rho(\phi)$

And you don't need any other connectives to get a polynomial sized translation of a propositional formula.

Then a formula $\phi$ is satisfiable iff
$$ ZF\vdash\exists x_1\ldots x_n\in\mathrm{Bool},\ \rho(\phi) \neq \varnothing$$

I'll let you work out the details. One important thing, though, is to show that a proof will be proportional in length to $n$, where $n$ is the number of variables.


How making non LL, non LR grammar a valid LL grammar, also makes it a valid LR grammar? Is there any connection between LL and LR conflicts?

When we use left factoring (or any other approaches) to eliminate conflicts from LL parsing table, it becomes valid LL grammar, and hence also a valid LR grammar.

To say that the grammar "becomes a valid LR grammar" implies that it was not a valid LR grammar before. But I will argue that if a mechanical procedure is used to transform a non-LL grammar $G$ into the LL grammar $G'$, then it is likely that both $G$ and $G'$ are LR grammars. In other words, the elimination of the LL conflict did not have any effect on LR conflicts, because there weren't any.

I'm not going to attempt to prove this assertion for all possible mechanical procedures. Indeed, it might not be correct for all heuristics. But it's pretty clear that the assertion is correct for the procedure used to left factor a grammar, because failure to left factor does not introduce any LR conflicts.

Both types of LR conflicts require that at least one production be reduceable. If left-factoring involves a factor which is not an entire right-hand side, then it does not apply to any SLR state including a reduceable production, and thus substituting a new non-terminal for the non-common part of the right-hand sides has no effect on any hypothetical LR conflict. Of course, it is possible that the factor is the entire right-hand-side of one production $A\to\beta$, and there is another production $A\to\beta\gamma$. So left-factoring will use a newly-created non-terminal $A'$ to produce:

$$\begin{align}A&\to \beta A'\\
A'&\to\gamma\mid\epsilon\\
\end{align}$$

The new grammar no longer has a prediction conflict on $A$, but there is no guarantee that the result is LL. For it to be LL, the parser needs to determined which alternative for $A'$ to use, which requires that $FOLLOW(\gamma)$ and $FOLLOW(A')$ be disjoint. But if that is true, there is no LR conflict; the shift and reduce actions are clearly differentiated by the lookahead.

So, if left-factoring results in an LL grammar, the grammar was originally LR. Left-factoring has not "made the grammar LR".

Left-recursion elimination is a bit more complex. To start to come to terms with that, consider a very simple left-recursive grammar $G_{sub}$:

$$\begin{align}S &\to E\\
E &\to T\\
E &\to E - E\\
T&\to 0|1|2|3|4|5|6|7|8|9
\end{align}$$

That grammar is ambiguous because $5 - 2 - 1$ has two parses: (for clarity, I put the subnode evaluation [brackets] beside each operator, to indicate that the two different parses lead to different program semantics):

     - [4]                        - [2]
   /   \                        /   \
  /     - [1]                  - [3] \
 /    /   \                  /   \    \
5    2     1                5     2    1

Since $G_{sub}$ is ambiguous, it cannot be LR, and indeed when we try to construct the parsing automaton we find a shift-reduce conflict on lookahead $-$ in the state $\{[E\to E\bullet-E], [E\to E-E\bullet]\}$. The ambiguity also implies that the grammar cannot be LL, but in this case we can immediately see that it is not LL because no LL grammar has a left-recursive production.

We might chose to eliminate ambiguity by adding a precedence specification and using the precedence algorithm implemented in Yacc (and other parser generators). The precedence algorithm does not perform a transformation on the grammar. Rather, it transforms the parse automaton generated by the LR algorithm by removing all but one action from each conflict. (Hence, it is only applicable to LR parsing.) The resulting automaton could be transformed back into a deterministic CFG, but this is rarely done because the parse automaton is sufficient to implement a parser. (The procedure to convert a DPDA to a DCFG is outlined in Sipser, Introduction to the Theory of Computation, in Theorem 2.57; you can take that as an exercise.)

$G_{sub}$ has only a single operator, $-$, so there are only two possible precedence declarations: either we declare the operator to be left-associative or we declare it to be right-associative. Normally, we would choose left-associativity, since that is how we were taught in school to understand expressions like $5 - 2 - 1$. That produces the parse tree on the right above, the one which evaluates to 2.

But right associative operators are also plausible. For example, in many programming languages, assignment is right associative, because $a = b = 7$ must be evaluated by first setting $b$ to 7 (subexpression on the right) and only then setting $a$ to the result of the first assignment.

As I said, actually constructing the parse automaton, removing the conflicts, and then turning it back into a grammar is a bit tedious, although it is probably a good exercise; for the purposes of this answer, I didn't do it. But I can provide CFGs which will produce the same parses, and probably differ from the full procedure only in minor details.

Here is the usual left-associative grammar:
$$\begin{align}S &\to E\\
E &\to T\\
E &\to E - T\\
T&\to 0|1|2|3|4|5|6|7|8|9
\end{align}$$

And here is the right-associative grammar:
$$\begin{align}S &\to E\\
E &\to T\\
E &\to T - E\\
T&\to 0|1|2|3|4|5|6|7|8|9
\end{align}$$

The only difference from the original ambiguous grammar is the second production for $E$. In the ambiguous grammar it is $E\to E - E$. The left associative grammar turns that into a left-recursive production $E\to E - T$, and the right associative grammar tuns it into a right-recursive production $E\to T - E$.

Both of the above associative grammars are LR, and neither is LL. The right-associative grammar can easily be transformed into an LL grammar by left factoring:

$$\begin{align}S&\to E\\
E&\to T E'\\
E'&\to - E\\
E'&\to\epsilon\\
T&\to 0|1|2|3|4|5|6|7|8|9
\end{align}$$

Again, this is an example of turning an non-LL grammar which was LR into an LL grammar (which is still LR).

To turn the left associative grammar into an LL grammar, we could try eliminating left recursion:

$$\begin{align}S&\to E\\
E&\to T E'\\
E'&\to - T E'\\
E'&\to\epsilon\\
T&\to 0|1|2|3|4|5|6|7|8|9
\end{align}$$

In this case, the resulting grammar is indeed LL. (And once again, both the original and the transformed grammar are LR.)

But here is something interesting. Left-factoring the right-associative grammar and eliminating left-recursion from the left-associative grammar produced virtually the same result. The only difference is that the first one has the production $E'\to - E$; in the second one, this production has had the $E$ pre-expanded, so it reads $E'\to - T E'$. Evidently, these two grammars parse the every input in the same way, despite the fact that we started with two grammars which produced different parses.

That's because the left-recursion-elimination algorithm does not preserve the parse tree. Or, to put it another way, you can turn a left-associative grammar into an LL grammar, but you sacrifice left-associativity.

Interesting though that is, it's really a side issue, since the point here was to try to find a relationship between LL and LR conflicts. And so far, we have found nothing even vaguely similar to a relationship. To close the circle, lets go back to the ambiguous grammar $G_{sub}$, which was neither LL nor LR, and try to turn it into an LL grammar by eliminating left-recursion. We get

$$\begin{align}S&\to E\\
E &\to T E' \\
E'&\to - E E' \\
E'&\to\epsilon \\
\\
T&\to 0|1|2|3|4|5|6|7|8|9
\end{align}$$

That successfully removed the left-recursion, but the resulting grammar is still not LL. We did not remove the ambiguity, and the resulting grammar is neither LL nor LR.

In summary:

An ambiguous grammar is neither LL nor LR. There will be conflicts produced by both algorithms, but it may be that they manifest in different ways.
If you can transform a non-LL grammar to an LL grammar using standard heuristics, then it probably had not LR conflicts to begin with.
LL and LR conflicts are completely different phenomena.


Why is NP not trivially equal to Co-NP? (a.k.a. what does Co-NP mean exactly?)

The Definitions

This comes from the one-sidedness of the definition $NP$, that (we think) is inherent to the class.

One definition of $NP$ is the set of languages $L$ such that there is some for every $x \in L$, there exists a certificate $c$ polynomial-sized relative to $x$, and an algorithm to check if $c$ is a valid certificate that runs in polynomial time.

This definition says absolutely nothing about strings $y \not \in L$. If a word is in our language, there's some certificate. But there might not be certificates for each string not in the language.

So, if we have a magic guessing machine (aka non-determinism, the $N$ of $NP$), we can magically guess a certificate for any $x$ that is in $L$, but to show that $y$ is not in $L$, we have to iterate through all potential certificates and show that none of them are valid.

Example

This is probably made more clear with an example. Let's suppose we have some problem where we have two sets $A$ and $B$, and we want to test if $A \subseteq B$. Let's assume all members of $A$ and $B$ are polynomially sized, and there's a polynomial check to test if any given member is in $A$ or $B$, but there's potentially exponentially many elements in both $A$ and $B$.

This problem is in $co-NP$. Why? Because there's an easy certificate for the "no" case. If $A \not \subseteq B$, then we can just say "Look, I know it's not a subset, since I found this element in $A$ that's not in $B$".

But, to show that there is a subset, we have to go through all elements and show that none of them are in $A$ but not in $B$. So this problem is easy to certify in the no case, but hard in the yes-case.

Implications

Why does this matter? In practice, it tells us the direction that is easy to guess, the direction where heuristics or local search help us the most, and the direction that has the potential to be fast.

For example, consider the travelling salesman problem. Say we want a path shorter than $k$. We can use a bunch of heuristics to try to find the shortest path through all cities. If it finds one of length less than $k$, then we know the solution to the decision problem: a tour of length $k$ or less exists. If it doesn't find one, we have no extra information. There could have been some path that our heuristics missed.

$NP$ problems are ones where the "yes" instances give us this certainty, a "for-sure yes" answer. We search, and if we find one solution/certificate, we know the answer is yes. But to say no, we need to look at all certificates.

$Co-NP$ is where we are searching for a certificate that says "for-sure no", where a yes is only found by looking at all potential certificates and seeing none work.


Local (stochastic) search is all about clever navigation of the search space.  DPLL's advantage is pruning the search space of large swaths of assignments that provably cannot satisfy the formula.  DPLL does this by incrementally building partial assignments (some variables assigned values, some left unassigned), applying the unit propagation and pure literal rules and then checking if the resulting formula is trivially unsatisfiable.  If the simplified formula implied by the partial assignment contains an empty clause, DPLL need not try assigning values to the remaining unassigned variables since the empty clause represents a clause that can never be satisfied under the partial assignment.  The time saved is exponential to the number of unassigned variables, and those skipped assignments are where DPLL improves on brute force sequential search.


How to measure the degree of randomness in Disk I/Os?

I am not aware of any formal discrete metrics of spatial and/or temporal locality of reference. Maybe someone else can enlighten us on that.

Often I see metrics used that are relevant to the particular platform you're studying. So the metric is either 'L1 cache misses', 'branch mispredicts', 'hard drive head movement', etc. You can google how to measure those.

You can make ad-hoc models by saving the location of your read/writes and applying penalties if those locations (or 4K blocks around those locations) haven't seen I/O recently.


How to write recurrence relation for the following scenario?

Hints:

Can you make a guess?  If you can make a guess, can you prove it?

What do you know about the height of a balanced search tree?

If the entire tree has $n$ nodes, what can you say about the number of nodes in the left subtree?  What is the smallest it could be?  The largest it could be?  What about the right subtree?

Can you derive a recurrence relation?

Imagine you treat the cost of computing $g(x)$ to be measured in dollars, and you charge \$1 to each node in the right/left subtree (whichever is smaller) to account for the cost of computing $g(x)$.  For any given node, what can you say about how many dollars it is charged?

If you know about amortized analysis, you might review that material.

It's not clear to me what $k$ represents in your proposed approach or where you got that recurrence relation.  Why don't you try harder to work out what recurrence relation might be suitable and what its solution is?


Which of these simple data structures is most efficient when implementing a Dequeue?

We need to clearly separate interface interfaces (abstract data types) from implementation. You talk about implementing a deque, an ADT, in terms of a stack or queue, but those are themselves ADTs. We need to be talking about concrete implementations.

So here's the answer (drumroll please): use a doubly-linked list. All the operations you mentioned are now $O(1)$.


What complexity does this 'how many ways to climb' algorithm have?

The solution is the recursive formula:

$S[k] = \sum_{i=1}^mS[k-i]$

For $m=2$ this is the Fibonacci sequence, and the way to program it is with dynamic programming. The complexity of the dynamic programming is $O(m \cdot n)$.

Consider the last step before reaching step $k$, the number of ways to reach $k$ when the last step is $i$, is equal to the number of steps to reach $S[k-i]$


Summed-area table for circular range queries

The best way is to approximate circle with hexagon or octagon as desciribed in expired patent US 6507676 B1. Further improvement is to add rectangles to octagon to get more circular shape or like harold proposed cover the whole circle with rectangles. Unfortunately this defies the core efficiency of summed area table.
The naive way would be to use e.g. Bresenham circle algorithm and sum consecutive rectangles, which by the way is still big speed up, proportional to circle size. The best way is to inscribe square and add rectangles to get finer results. This is illustrated here.

Picture taken from http://yehar.com/

There is no possibility of creating SAT especially for circle even leaving jagged border, simple proof is from impossibility of tesselating space by circles.


What are all the differences between the Gibbs phenomenon artefects and JPEG artefacts?

There are three kinds of JPEG artifacts.  The first and (arguably) most important one is described in Yuval's answer: To a first order the problem is that under high compression all the high frequency information is discarded, and the lowest frequency information remaining is the average color of each 8x8 square.  When you take the inverse but leave out the high frequency information, the result is a square of a single color.  A decoder can't perform any low-pass filtering to remove the blocky effect because that would cause significant error in the case that you used a high-quality setting to encode.

The second artifact is exactly the Gibbs phenomenon.  Fine detail in the image will get "halos" if highly compressed.  For example, here is a 64x64 image with a single dot at pixel 35,35:

Here's the same image saved by GIMP as a Jpeg with low quality (25%):

There is a halo around the pixel in the 8x8 block the pixel is in.  (To make it easier to see, here is an image of that block scaled up by a factor of 8:

This effect is called ringing.  (In audio processing it really produces a ringing noise.)  This occurs because high levels of compression are chopping out the highest frequencies, which leaves ripples at the highest remaining frequency.  (I.e., it's the Gibbs phenomenon.)

The third artifact is the inverse of the Gibbs phenomenon.  The Gibbs phenom is because the multiplication of the brick-wall filter in the frequency domain is equivalent to convolution with the sinc function in the time domain.  The inverse problem is using a box-car filter for downsampling in the time domain leads to a sinc function in the frequency domain, and thus a large amount of high-frequency noise gets aliased into the resulting downsampled image.  This is essentially what JPEG is doing when it breaks the image into 8x8 blocks.  The lowest-frequency component of each 8x8 block is the average (box-car) of the pixel values in that 8x8 block, so actually contains significant high-frequency aliasing.  For example, consider the following image.  (It is 64x64 with a horizontal stripe each third pixel.  So has significant amount of high frequency information.

Now if I encode with jpeg at very low quality I get this:

The high frequency information from the original image is not being completely filtered by the box-car averaging, and thus gets aliased into a lower-frequency error in the image.


Prove/Disprove: $L_1, L_2 \in RE-R \implies L_1 \cup L_2 \notin R$

Hint: Let $L$ be any language in $\mathsf{RE} - \mathsf{R}$, and consider
$$ L_1 = 0\Sigma^* \cup 1L, \quad L_2 = 1\Sigma^* \cup 0L. $$


What other implementation styles are there besides compilation, interpretation and transpilation?

Fundamentally, there are only the two: compilation and interpretation.
tl;dr: An interpreter runs the program, a compiler translates the program to another language.
An interpreter for language X is a program (or a machine, or just some kind of mechanism in general) that executes any program p written in language X such that it performs the effects and evaluates the results as prescribed by the specification of X. CPUs are usually interpreters for their respective instructions sets, although modern high-performance workstation and server CPUs are actually more complex than that; they may actually have an underlying proprietary private instruction set and either translate (compile) or interpret the externally visible public instruction set.
A compiler from X to Y is a program (or a machine, or just some kind of mechanism in general) that translates any program p from some language X into a semantically equivalent program p′ in some language Y in such a way that the semantics of the program are preserved, i.e. that interpreting p′ with an interpreter for Y will yield the same results and have the same effects as interpreting p with an interpreter for X. (Note that X and Y may be the same language.)
In some cases, we have more specialized names for certain kinds of compilers, depending on what X and Y are, and what the compiler does:

if X is perceived to be assembly language and Y is perceived to be machine language, then we call it an assembler,
if X is perceived to be machine language and Y is perceived to be assembly language, then we call it a disassembler,
if X is perceived to be lower-level than Y, then we call it a decompiler,
if X and Y are the same language, and the resulting program is in some way faster or lighter, then we call it an optimizer,
if X and Y are the same languages, and the resulting program is smaller, then we call it a minifier,
if X and Y are the same languages, and the resulting program is less readable, then we call it an obfuscator,
if X and Y are perceived to be at roughly the same level of abstraction, then we call it a transpiler, and
if X and Y are perceived to be at roughly the same level of abstraction and the resulting program preserves formatting, comments, and programmer intent such that it is possible to maintain the resulting the program in the same fashion as the original program, then we call it a re-engineering tool.

Also, note that older sources may use the terms "translation" and "translator" instead of "compilation" and "compiler". For example, C talks about "translation units".
You may also stumble across the term "language processor". This can mean either a compiler, an interpreter, or both compilers and interpreters depending on the definition.
The terms Ahead-of-Time (AOT) and Just-in-Time (JIT) refer to when compilation takes place: the "time" referred to in those terms is "runtime", i.e. a JIT compiler compiles the program as it is running, an AOT compiler compiles the program before it is running. Note that this requires that a JIT compiler from language X to language Y must somehow work together with an interpreter for language Y, otherwise there wouldn't be any way to run the program. (So, for example, a JIT compiler which compiles JavaScript to x86 machine code doesn't make sense without an x86 CPU; it compiles the program while it is running, but without the x86 CPU the program wouldn't be running.)
So, we have:

AOT compiler: compiles before running
JIT compiler: compiles while running
interpreter: runs

JIT Compilers
Within the family of JIT compilers, there are still many differences as to when exactly they compile, how often, and at what granularity.
Some JIT compilers for example only compils code once (when it is loaded) and compiles a whole module at a time. Other compilers may gather information while the program is running and recompile code several times as new information becomes available that allows them to better optimize it. Some JIT compilers are even capable of de-optimizing code. Now, you might ask yourself why one would ever want to do that? De-optimizing allows you to perform very aggressive optimizations that might actually be unsafe: if it turns out you were too aggressive you can just back out again, whereas, with a JIT compiler that cannot de-optimize, the program would crash or return a wrong result; in other words, you simply can't allow yourself to perform the aggressive optimizations in the first place.
JIT compilers may either compile some static unit of code in one go (one module, one class, one function, one method, …; these are typically called method-at-a-time JIT, for example) or they may trace the dynamic execution of code to find dynamic traces (typically loops) that they will then compile (these are called tracing JITs).
Combining Interpreters and Compilers
Interpreters and compilers may be combined into a single language execution engine. There are two typical scenarios where this is done.
Combining an AOT compiler from X to Y with an interpreter for Y. Here, typically X is some higher-level language optimized for readability by humans, whereas Y is a compact language (often some kind of bytecode) optimized for interpretability by machines. For example, the CPython Python execution engine has an AOT compiler that compiles Python sourcecode to CPython bytecode and an interpreter that interprets CPython bytecode. Likewise, the YARV Ruby execution engine has an AOT compiler that compiles Ruby sourcecode to YARV bytecode and an interpreter that interprets YARV bytecode. Why would you want to do that? Ruby and Python are both very high-level and somewhat complex languages, so we first compile them into a language that is easier to parse and easier to interpret, and then interpret that language.
The other way to combine an interpreter and a compiler is a mixed-mode execution engine. Here, we "mix" two "modes" of implementing the same language together, i.e. an interpreter for X and a JIT compiler from X to Y. (So, the difference here is that in the above case, we had multiple "stages" with the compiler compiling the program and then feeding the result into the interpreter, here we have the two working side-by-side on the same language.) Code that has been compiled by a compiler tends to run faster than code that is executed by an interpreter, but actually compiling the code first takes time (and particularly, if you want to heavily optimize the code to run really fast, it takes a lot of time). So, to bridge this time where the JIT compiler is busy compiling the code, the interpreter can already start running the code, and once the JIT is finished compiling, we can switch execution over to the compiled code. This means that we get both the best possible performance of the compiled code, but we don't have to wait for the compilation to finish, and our application starts running straight away (although not as fast as could be).
This is actually just the simplest possible application of a mixed-mode execution engine. More interesting possibilities are, for example, to not start compiling right away, but let the interpreter run for a bit, and collect statistics, profiling information, type information, information about the likelihood of which specific conditional branches are taken, which methods are called most often etc. and then feed this dynamic information to the compiler so that it can generate more optimized code. This is also a way to implement the de-optimization I talked about above: if it turns out that you were too aggressive in optimizing, you can throw away (a part of) the code and revert back to interpreting. The HotSpot JVM does this, for example. It contains both an interpreter for JVM bytecode as well as a compiler for JVM bytecode. (In fact, it actually contains two compilers!)
It is also possible and in fact common to combine those two approaches: two phases with the first being an AOT compiler that compiles X to Y and the second phase being a mixed-mode engine that both interprets Y and compiles Y to Z. The Rubinius Ruby execution engine works this way, for example: it has an AOT compiler that compiles Ruby sourcecode to Rubinius bytecode and a mixed-mode engine that first interprets Rubinius bytecode and once it has gathered some information compiles the most often called methods into native machine code.
Note that the role that the interpreter plays in the case of a mixed-mode execution engine, namely providing fast startup, and also potentially collecting information and providing fallback capability may alternatively also be played by a second JIT compiler.
This is how the second generation of Google's V8 ECMAScript engine worked, for example. This generation of V8 never interprets, it always compiles. The first compiler is a very fast, very slim compiler that starts up very quick. The code it produces isn't very fast, though. This compiler also injects profiling code into the code it generates. The other compiler is slower and uses more memory, but produces much faster code, and it can use the profiling information collected by running the code compiled by the first compiler.


Is it decidable if a given TM accepts infinitely many words in a fixed number of moves?

I'm going to assume that you mean

$\qquad L = \{ \langle M \rangle \mid |L_{\leq 10}(M)| = \infty \}$

with $L_{\leq m}(M)$ the set of words that $M$ accepts after at most $m$ steps. In particular, it does not say a thing about all the other inputs.

  How is it possible to derive infinite amount of words in finite moves?

The Turing machine that does nothing but accept clearly accepts an infinite language. While it's true that machines that qualify for $L$ have to work with finite prefixes, but they can accept arbitrarily many inputs based on these prefixes!

  How can we determine if a word is or isn't in the language at all?

I don't know what "we" is here; but clearly, we can just run $M$ on the input. If it accepts after at most ten steps, fine; otherwise, it's not relevant for the criterion of $L$.

  Why is this language decidable?

Who says so?

Hint: How many symbols of the input can any TM examine in ten steps? Let's call this number $k$. What does it tell you if it accepts or rejects an input of length at most $k$? What does it tell you if it accepts or rejects an input of length greater than $k$?

  I understand that it is because it halts on every input.

How so? If you had an algorithm that decides $L$, then yes, it would halt on every input. But we can not assume that -- that's the claim we have to prove!

The inputs for this algorithm are all Turing machines, in particular also such that don't halt.

  but what are we looking for after 10 moves to decide if it will reject or accept?

You have one bit of information: did the machine accept or not? You can have some more, if that helps: did the machine visit a state twice? Did it move, and how?


Pumping Lemma for irregular language, how to choose and divide the string

w = abn-1abn.

We have to consider all the division xyz = w with |y| >= 1 and |xy| <= n. So

x = apbr

y = aqbs

z = btabn

where:

p + q = 1
r > 0 implies p = 1
q + s > 0
r + s + t = n - 1

Let's now consider w' = xy0z=apbr+tabn. If x is the empty string, then w' is missing the initial 'a' (and maybe some b), so w' is not in L. Else if x is not empty, we know that y contains at least one occurrence of 'b', so w' can't be in the form abnabn+1 and w' is not in L.


In an M/M/1 Queue, what does exponential distribution of service time mean?

In an exponential distribution, the probability is DECREASING exponentially -- hence little risk that service time will grow. On the contrary, the mean service time is fixed, at the inverse of the rate.
This distribution is actually very rare in practice, but is chosen because it is Markovian:
the probability to terminate servicing a client does not depend on the past, and in particular on how much time you already spent servicing that client. That yields very nice mathematical properties.


Unfortunately, that textbook says nothing about how to deduce that particular recurrence relation, although it has plenty of examples on how to obtain a recurrence relation. In fact, I cannot understand $C_1=1+1+C_0 =2$, which says that we need two comparisons to sort 1 item using quicksort.

If OP's intention is emphasizing how he (meaning them, Donald Knuth and Oren Patashnik) get the recurrence relation, then I can only honestly say I have no credible idea beyond a few educated guesses.

If OP's intention is just to know how to deduce the recurrence relation, then the wikipedia item on quicksort is a nice answer, which I have copied below with minor modification to fit current question.

   Assume that there are no duplicates. When the input is a random permutation, the rank of the pivot is uniform random from 0 to $n − 1$. Then the resulting parts of the partition have sizes i and $n − i − 1$, and $i$ is uniform random from 0 to $n − 1$. So, averaging over all possible splits and noting that the number of comparisons for the partition is $n − 1$, the average number of comparisons over all permutations of the input sequence can be estimated accurately by solving the following recurrence relation.

$$
C(n)=n-1+{\frac 1n}\sum_{i=0}^{n-1}(C(i)+C(n-i-1))=n-1+{\frac 2n}\sum _{i=0}^{n-1}C(i) $$

Please note that in the wikipedia item, $C(1)=1-1+0=0$, which say that we need no comparison to sort 1 item, which looks much more reasonable to me


Turing Machine which will double every 'b' in all inputted string

When you encounter $b$ change state to shifting tape right: move to next cell read content and put blank character.
Keep replacing characters until you encounter blank character (end of your tape content).
Put your last character at the end and move head left until you find blank character. Pur $b$ there.
Keep moving right until you find $b$ and repeat.

In your example:
$\color{green}cbcbcb\_$
Move right
$c\color{green}bcbcb\_$
Change state to copy and put blank:
$cb\color{green}\_bcb\_$ switch state to put $c$ and memorize next element
$cb\_\color{green}ccb\_$ switch state to put $b$ and memorize next element
$cb\_c\color{green}bb\_$ switch state to put $c$ and memorize next element
$cb\_cb\color{green}c\_$ switch state to put $b$ and memorize next element
$cb\_cbc\color{green}b\_$ blank encountered, move back to blank
$cb\_cb\color{green}cb\_$
$cb\_c\color{green}bcb\_$
$cb\_\color{green}cbcb\_$
$cb\color{green}\_cbcb\_$ blank encountered put $b$
$cbb\color{green}cbcb\_$ now repeat move right and switch to copy mode when another $b$ is found. When you reach end of the tape then all $b$'s are doubled.


Christofides algorithm: why must an MST have even number of odd-degree vertices?

Every edge in a graph is incident with exactly two vertices. The degree of a vertex is the number of edges incident with it. From this you get the standard fact that the sum of all the vertex degrees in a graph equals twice the number of edges; in particular, it is even. A minimum spanning tree is a graph in its own right. If it had an odd number of odd-degree vertices, the sum of degrees would be odd, which is impossible.


What is the asymptotic runtime of the best known TSP solving algorithm?

The worst case running time of Concorde or any other known method is exponential in the size of the input. However, sometimes heuristics or other pruning techniques are effective and you are able to solve some, even large, instances pretty quickly. You should define exactly what you mean by TSP as there are many variants, and many algorithms with different worst case run times.

See the accepted answer in this question on CSTheory to see a list of algorithms.


Minimum number of steps to sort 3x3 matrix in a given way

Since you are looking for minimal number of moves without any tricks, there is old good pattern for small exact problems.

0) treat your starting matrix as root.
1) enumerate possible moves, and perform them (copy matrix, save steps etc.).
2) keep performing step one for every resulting matrix until you find them ordered. This is minimal number of moves.
1+) optimization possible is to ignore the same matrices that you already have, block sliding ply in direction it came from.


Rigorous proof that parametric polymorphism implies naturality using parametricity?

The missing part is the "identity extension lemma", which is mentioned in Reynolds' original paper but not in Wadler's.
For $F : \text{Type} \to \text{Type}$, this says that if the relational interpretation of $F$ is instantiated with a type $A$ and the identity relation
on $A$, we get the identity relation on $F\,A$.
For System F, identity extension can be proven for types-in-contexts, but note that there is no $F : \text{Type} \to \text{Type}$ in System F. To gracefully handle identity extension for type operators in general, it's better to switch to reflexive graph models, where identity extension is given mutually with the rest of the model.
Let's use the reflexive graph model of some type theory. This means that for every closed $F : \text{Type} \to \text{Type}$, we get a semantic $F^S : \text{Set} \to \text{Set}$, together with $F^R : (A, B : \text{Set}) \to \text{Rel}\,A\,B \to \text{Rel}\,(F\,A)\,(F\,B)$ where $\text{Rel}\,A\,B$ denotes a set of proof-irrelevant relations. We also get identity extension: $F^R\,A\,A\,(\text{Id}\,A) = \text{Id}\,(F\,A)$, where $\text{Id}\,A$ is the identity relation. In the following, let's omit all $^S$-es and don't talk about syntactic things, only about semantic things, so that we may write $F : \text{Set} \to \text{Set}$.
Assume $F, G : \text{Set} \to \text{Set}$ are functors, and $\eta : (A : \text{Set}) \to F\,A \to G\,A$. Let's write $\text{map}$ for functorial mapping.
We assume that everything is parametric. This means that we get $F^R$, $G^R$, $\eta^R$ and ${\text{map}_F}^R$ and ${\text{map}_G}^R$. Assume $f : A \to B$ and $x : F\,A$.
To show:
$$ \text{map}_G\,f\,(\eta_A\,x) = \eta_B\,(\text{map}_F\,f\,x) $$
By identity extension for $G$, this is equivalent to
$$ G^R\,B\,B\,(\text{Id}\,B)\,(\text{map}_G\,f\,(\eta_A\,x))\,(\eta_B\,(\text{map}_F\,f\,x)) $$
Category law:
$$ G^R\,B\,B\,(\text{Id}\,B)\,(\text{map}_G\,f\,(\eta_A\,x))\,(\text{map}_G\,id\,(\eta_B\,(\text{map}_F\,f\,x))) $$
To show the above, we use ${\text{map}_G}^R$, i.e. that $\text{map}_G$ preserves all relations. We have to pick two relations, one in $\text{Rel}\,A\,B$ and one in $\text{Rel}\,B\,B$ and show that $f : A \to B$ and $id : B \to B$ are pointwise related. We pick the graph of $f$ and $\text{Id}\,B$, and the functions are clearly pointwise related. It remains to show:
$$ G^R\,A\,B\,(\text{Graph}\,f)\,(\eta_A\,x)\,(\eta_B\,(\text{map}_F\,f\,x)) $$
We know that $\eta$ preserves all relations, so it's enough to show:
$$ F^R\,A\,B\,(\text{Graph}\,f)\,x\,(\text{map}_F\,f\,x) $$
Category law:
$$ F^R\,A\,B\,(\text{Graph}\,f)\,(\text{map}_F\,id\,x)\,(\text{map}_F\,f\,x)$$
We instantiate ${\text{map}_F}^R$ with $\text{Id}\,A$ and $\text{Graph}\,f$ and it remains to show:
$$ F^R\,A\,A\,(\text{Id}\,A)\,x\,x $$
By identity extension for $F$, this is equivalent to:
$$ x = x $$

The same thing in Agda:
-- Agda 2.6.1, stdlib 1.5

open import Relation.Binary.PropositionalEquality
  renaming (sym to infix 6 _⁻¹; cong to ap; trans to infixr 5 _◾_; subst to tr)
open import Function

coe : ∀{i}{A B : Set i} → A ≡ B → A → B
coe refl a = a

Rel : Set → Set → Set₁
Rel A B = A → B → Set

Id : (A : Set) → Rel A A
Id A x y = x ≡ y

Graph : {A B : Set} → (A → B) → Rel A B
Graph f a b = f a ≡ b

happly : ∀{i j}{A : Set i}{B : Set j}{f g : A → B} → f ≡ g → ∀ x → f x ≡ g x
happly refl x = refl

record Functor : Set₁ where
  field
    !      : Set → Set
    map    : {A B : Set} → (A → B) → ! A → ! B
    map-id : ∀ {A} → map {A} id ≡ id
    map-∘  : ∀ {A B C}(f : B → C)(g : A → B) → map (f ∘ g) ≡ map f ∘ map g

record Functorᴿ (F : Functor) : Set₁ where
  private module F = Functor F
  field
    !     : ∀{A₀ A₁} → Rel A₀ A₁ → Rel (F.! A₀) (F.! A₁)
    map   : ∀ {A₀ A₁}(Aᴿ : Rel A₀ A₁){B₀ B₁}(Bᴿ : Rel B₀ B₁)
            (f₀ : A₀ → B₀)(f₁ : A₁ → B₁)(fᴿ : ∀ {a₀ a₁} → Aᴿ a₀ a₁ → Bᴿ (f₀ a₀) (f₁ a₁))
            {fa₀ fa₁} → ! Aᴿ fa₀ fa₁ → ! Bᴿ (F.map f₀ fa₀) (F.map f₁ fa₁)

    idext : ∀ {A} → ! (Id A) ≡ Id (F.! A)

  reflexive : ∀ {A x} → ! (Id A) x x
  reflexive {A} {x} = tr (λ f →  f x x) (idext ⁻¹) refl

module _
  (F G : Functor) (Fᴿ : Functorᴿ F) (Gᴿ : Functorᴿ G) where

  module F  = Functor F   ; module G  = Functor G
  module Fᴿ = Functorᴿ Fᴿ ; module Gᴿ = Functorᴿ Gᴿ

  module _ (η  : ∀ {A} → F.! A → G.! A)
           (ηᴿ : ∀ {A₀ A₁}(Aᴿ : Rel A₀ A₁){fa₀ fa₁}
                 → Fᴿ.! Aᴿ fa₀ fa₁ → Gᴿ.! Aᴿ (η fa₀) (η fa₁)) where

    η-is-natural : ∀ {A B}(f : A → B) x → G.map f (η x) ≡ η (F.map f x)
    η-is-natural {A} {B} f x =
      let lem1 : Fᴿ.! (Graph f) (F.map id x) (F.map f x)
          lem1 = Fᴿ.map (Id A) (Graph f) id f (ap f) {x} {x} Fᴿ.reflexive

          lem2 : Fᴿ.! (Graph f) x (F.map f x)
          lem2 = tr (λ y → Fᴿ.! (Graph f) y (F.map f x)) (happly F.map-id x) lem1

          lem3 : Gᴿ.! (Graph f) (η x) (η (F.map f x))
          lem3 = ηᴿ (Graph f) lem2

          lem4 : Gᴿ.! (Id B) (G.map f (η x)) (G.map id (η (F.map f x)))
          lem4 = Gᴿ.map (Graph f) (Id B) f id id lem3

          lem5 : Gᴿ.! (Id B) (G.map f (η x)) (η (F.map f x))
          lem5 = tr (λ y → Gᴿ.! (Id B) (G.map f (η x)) y) (happly G.map-id _) lem4

      in coe (happly (happly Gᴿ.idext (G.map f (η x))) (η (F.map f x))) lem5


interference graph: assigning variable to itself

You are right. The lifetime of a could be split into two spans. That said, how would you notate that in the interference graph? That is, how would you notate that one variable only interfered with one span of another variable's lifetime?

This is one of the motivations for Static Single Assignment (SSA) form. By having each assignment write to a "new" variable, you're never in the situation where a variable's lifetime is in potentially disjoint spans. You also have a name for each span of a (source-level) variable's lifetime, so the interference graph can be finer grained.

It is, however, safe to treat the lifetimes as starting at the first assignments and ending at the last uses. So while it may not be optimal to give each variable one single span of lifetime, it will never cause incorrect behavior.


Yes, exactly as you said. This is used to decrease the number of multiplications, so it is more efficient than computing it the normal way.

Example:

  You have the polynomial $ax^3 + bx^2 + cx + d$.
  Computing directly you have six multiplications: (a * x * x * x, b * x * x, c * x). With Horner $((ax + b)x + c)x + d$ you have three multiplications: (a * x, first parenthesis * x, second parenthesis * x)

It is important to remember that in floating point calculations results from these two methods (direct and Horner) will differ.


Is there a specific problem that is in both NP and co-NP but not in P?

An answer to your question would be a problem $p$ which is in $\mathop{NP}\cap\mathop{coNP}$, and thus in $\mathop{NP}$, but not in $P$. Existence of such a problem would easily imply $P\neq\mathop{NP}$, which is a seriously open problem to this date. That is to say, no one can answer your question yet.


Is there any nongeneral CFG parsing algorithm that recognises EPAL?

Consider the following sketch of a parsing strategy at your own risk.

Instead of reading the input only from one end, we read from both sides and look for matching rules. We can do this in recursive descent style; in a call to $A()$, find prefix $w$ and suffix $v$ to the input such that there is a rule $A \to wBv$, descend to $B()$ on the remaining word. If there is no matching rule, reject the word.

This algorithm parses all linear, unambiguous grammars. It takes linear time if all rule pairs $A \to wBv$ and $A \to w'B'v'$ have $w \not\equiv_p w'$ or $v \not\equiv_s v'$¹. This includes EPAL. Otherwise we need to look ahead so we might take $\Theta(n^2)$ time.

The idea does not work for non-linear grammars at all. Linear but ambiguous grammars can in general not be parsed without backtracking (for negative inputs at least).

$w \not\equiv_p v$ means here that $w \not\sqsubseteq v$ and $v \not\sqsubseteq w$, i.e. neither word is a prefix of the other. $\not\equiv_s$ is similar for suffixes.


Find the median of a list of sorted arrays

You can do it in $O(l + k \text{ log } l)$ time and $O(l)$ extra space as follows:

Build a binary heap with one entry for each of the arrays.  The key for entry $i$ is the smallest element in array $A_i$.  This takes $O(l)$ time.
Select the smallest entry from the heap and remove it (taking $O(\text{log } l$) time).  Add that entry back to the heap using the next smallest entry in the relevant array as its key (again $O(\text{log } l)$ time).
Do the previous step $k$ times.  The last element you remove from the heap is your answer.

If you replace the binary heap with a Fibonacci heap, I think this gets you down to amortized $O(l + k)$ time, but in practice it'll be slower than the binary heap unless $l$ is HUGE.

I suspect that the Fibonacci heap bound is optimal, because intuitively you're going to have to inspect at least $k$ elements to find the $k$th smallest one, and you're going to have to inspect at least one element from each of the $l$ arrays since you don't know how they're sorted, which immediately gives a lower bound of $\Omega(\text{max}(k, l)) = \Omega(k + l)$.


Comparison of $(\log^* n)!$ and $(n\log n)^b$

For sufficiently large values of $n$, and $b>0$:
$$
( \log^*n )! < ( \log \log n )! < (\log \log n)^{\log \log n} = 2^{(\log\log n) \log \log \log n} \in o(2^{b \log n}) \subset o( (n \log n)^b ).
$$


Is regularity of the language accepted by a given Turing machine a semi-decidable property?

You have a good idea for proving that $L$ is not semi-decidable but it's not going to work since neither $L$ nor $\overline{L}$ are semi-decidable. Intuitively, how can saying after finite time "this language is not regular" be easier than "this language is regular" -- you can only inspect finitely many inputs, and all finite languages are regular (thus we can not separate REG from other classes on finite samples).

So we are left with our basic device: reduction from a non-semi-decidable language. The canonical one is the complement of the halting problem, i.e.

$\qquad\displaystyle \overline{K} = \{ \langle M \rangle \mid M(\langle M \rangle) \text{ loops}\}$.

Now we have to define a function for every $M$ whose accepted language is (non-)regular depending on whether $M$ halts on itself in order to establish the contradiction.

So, for any fixed TM $M$, define the following function¹:

$\qquad\displaystyle
    f_M(w) = \begin{cases}
                1, & w = a^n b^n \land M(\langle M \rangle) \text{ terminates after at most $n$ steps} \\
                0, &\text{else}
             \end{cases}
$

The function $f_M$ is clearly computable for any $M$; just check the form of the input and simulate $M$ for $n = \frac{|w|}{2}$ steps if necessary.
Note furthermore that given $\langle M \rangle$, we can compute $\langle f_M \rangle$; such compilation is possible because we have (or can assume) a Gödel numbering.

Now we have what we always want when reducing, the equivalence of doom:

$\qquad\displaystyle \langle M \rangle \in \overline{K} \iff \mathcal{L}(f_M) = \emptyset \iff \mathcal{L}(f_M) \in \mathrm{REG}$,

since $\mathcal{L}(f_M) = \{a^n b^n \mid n \geq N \} \not\in \mathrm{REG}$ if $M(\langle M \rangle)$ halts after $N$ steps, i.e. $\langle M \rangle \in K$.

Thus, if we had a semi-decider for your $L$, we could semi-decide $\overline{K}$ which contradicts what we know.

For ease of notation I use strings as inputs; of course, we'd work on naturals using some computable bijection.


Is it possible to implement a dictionary with efficient access according to insertion order?

To summarize, this is what you require:

a dictionary that
offers find, add and delete in $O(\log n)$ time and also
GetByIndex, KeyByIndex and IndexByKey in $O(\log n)$ time, where the index is determined by insertion order.

The first part is easy: use any balanced search tree. Say we use AVL trees.

For the second, we can use a second tree but use an increasing counter as key. With a small change to the data structure, we can find the $i$th element in $O(\log n)$ time (rank selection). Thus, we don't have to change any indices; the tree structure maintains the order for us.

We can further link the two AVL trees back and forth.

Assuming we have an implementation AVL which provides efficient select and rank (zero-based) and has a field for crosslinks, this would be rough pseudocode:

class IndexedDictionary {
  dataTree  = new AVL()
  indexTree = new AVL()
  nextId = 0

  add(key, data) {
    dataNode  = dataTree.add(key, data)
    indexNode = indexTree.add(nextId, data)
    dataNode.crosslink = indexNode
    indexNode.crosslink = dataNode
    nextId += 1
  }

  delete(key) {
    i = index(key)
    dataTree.delete(key)
    indexTree.delete(indexTree.select(i).key)
  }

  find(key) {
    return dataTree.find(key).value
  }

  get(index) {
    return indexTree.select(index).value
  }

  key(index) {
    return indexTree.select(index).crosslink.key
  }

  index(key) {
    return indexTree.rank(dataNode.find(key).crosslink.key)
  }
}

Of course, delete(index) can be implemented similarly to delete(key). Delete can be implemented faster if you add an operation delete-ith to AVL, and have AVL-delete return the removed node.


Efficient Algorithm to determine highly composited numbers

As in many cases, read the problem carefully first. The problem asks for all numbers that have more divisors than any small numbers. Nobody asks you to determine the number of divisors of lots of numbers.

First write down the formula how to calculate the number of divisors of n, given its factorisation into prime numbers. Then figure out rules that say what kinds of prime factors a highly composite number might have. Quite obviously a highly composite number must be a product $2^a·3^b·5^c·7^d...$ where a ≥ b ≥ c ≥ d and so on. That's because if for example a < b, then $2^b·3^a$ would be smaller than $2^a·3^b$ but have the same number of prime factors.

That's just the start of it, but this should already help you to find highly composite numbers up to n a lot, lot faster than O (n).


How to evaluate all derivatives of a polynomial at a point with FFT?

Hint: Taking the derivative has a certain, simple diagonal effect on the Fourier transform, that hopefully was covered in class. Hence if you compute the Fourier transform of the original function, you "know" the Fourier transform of all its derivatives as well. Given the Fourier transform, there is a formula for the value of the actual function. In your case, in order to compute the value of all derivatives of the function at a point, you multiply some matrix by the vector of Fourier coefficients. This matrix looks suspiciously similar to the DFT matrix, so hopefully you can compute the matrix-vector product in time $O(n\log n)$.


Soon to be computer science major with some questions

Firstly, is CS going to be Math heavy?
It's not a very easy question to answer as it depends on quite a few factors. How good are you in Mathematics and how strong are you with the basic concepts? If you were comfortable with the Math you have done so far, then you won't have any problem. If not, then there is nothing that some hard work cannot solve. Plus CS is definitely not he most heavy of all the majors in engineering or sciences. I believe Mechanical, Aeronautical, etc to involve a lot more advanced Math in them.

Secondly, what will you be learning?

You will be learning Algorithms, various programming languages and there pros and cons, maybe artificial intelligence, operating systems, networking, database theory, some electronics I believe, and maybe sensor networks,etc.

Thirdly, should you quit stressing?

Definitely Yes. If you have decided to become a Computer Science major then I am guessing that you have interest in the field. If that is true you should be able to grasp the concepts just fine.

My Advice, pick an area like Artificial Intelligence or Networking or Operating System etc, which ever field you like best, early, and try and master that field. That will help you tons in the future.

I have a PhD in CS and seen quite a few young guys go through the same phase as you. It's very natural to feel nervous about the unknown, specially when it's about your career and the rest of your life. Just try and make smart decisions whenever you have to. Plus, there will be lots of people around to help you when you are unsure.

So, Good Luck and have Fun.


Subgraph isomorphism on star multi-graphs with labelled edges

After you fix the star centers, your problem is simply bipartite matching.


Providing a regular expression or DFA for a language and proceeding to demonstrate that it is correct for the language in question generally constitutes a pretty convincing argument for the regularity of the language. To prove a language is non-regular, you have a few options: the pumping lemma for regular languages is a classic standby, but the Myhill-Nerode theorem is pretty nifty, too (especially since you can use it to prove regularity as well as non-regularity).

Your first job should be to define what constitute valid strings in the languages $HTML$ and $CSS$. Note that most browsers will take anything you call $HTML$ and display something without error; in that sense, anything is valid $HTML$, and the language $\Sigma^*$ is trivially regular. However, I think it's safe to assume that you have something a bit more strict in mind: $HTML$ consists only of those strings that conform to some standard, which probably calls for matched tags. In this case, you should be able to prove that $HTML$ isn't regular, since you can consider the following kinds of strings (whitespace is added only for clarity and could be removed in the real string):

                  ...

This language,  $($

 $)^n($

 $)^n$`</body></html>`, should be enough to get to a proof of non-regularity, provided you accept the above as valid $HTML$, and would say that a missing `</table>` tag would make the resulting string invalid $HTML$, even though browsers would try to render it anyway.

For $CSS$, first figure out what strings you think are valid, then try to come up with a regular expression or DFA for the set of all $CSS$ strings, or figure out how to define a subset of $CSS$ that requires non-local checks and unbounded memory (counting, matching, nesting, etc.) If you can define such a subset (like we did for $HTML$ above), then you're good to go.