How to find rows of matrix that are zero everywhere except for 1 entry? I am interested in finding the rows of a matrix where all entries are equal to zeros except for one.

Example: Given the following matrix:

\begin{bmatrix}0  &0 &3 & 8\\ 0 & 4 & 0 & 0 \\ 0 &1 & 0  & 1\end{bmatrix}

Only the second line has this property.

Of course, the brute force way is to go over the entries and check them one by one. But I am wondering if there is another most efficient way I don't know about.

There is no algorithm with worst-case running time better than $O(n^2)$.  There is a simple adversary argument to prove this.

Consider any algorithm that is purported to be correct, and that always inspects fewer than $n^2$ entries of the matrix. Thus, there must always be some entry that is uninspected.  Consider a matrix that has 1's in the entire first column.  Every time the algorithm inspects any other entry, it will find a 0.  After inspecting at most $n^2-1$ entries, the algorithm terminates and outputs some list of rows.  Pick any entry that was uninspected.  Now we have a freedom about whether to fill it in with a 0 or a 1; and we can always make a choice that will make the algorithm's output wrong (if the algorithm included that row in its output, make it a 1; otherwise make it a 0).  So, for any correct algorithm, it must inspect all matrix entries for at least some inputs, so its running time must be at least $\Omega(n^2)$.

There are various optimizations you can use in practice, like using bitwise operations (depending on how the matrix is stored), and if you see more than a single 1 in any row, don't look at any other entries in that row -- but these won't affect the asymptotic worst-case running time.


If problem is coNL-complete, is it NL-complete We know from Immerman-Szelepcsényi theorem that $coNL=NL$. But, what about:
If problem is $coNL\text{-}complete$, is it $NL\text{-}complete$? And why?

If the language $A$ is $NL$-complete then

$A \in NL$
Each problem in $NL$ is logspace reducible to $A$

Since $coNL = NL$ each problem in $coNL$ is logspace reducible to $A$ as well. Thus $A$ is $coNL$-complete.


How to prove that knapsack has no competitive algorithm In online knapsack problem, items arrive one by one. Each time an item $i$ arrives, its weight $w_i$ is revealed. We would like to maximize, in an online fashion, the number of items placed in a bin of capacity $W$.
The proposition that I am trying to prove is that no deterministic competitive algorithm exists for this problem.
I did something like this: assume that an online algorithm decided to place an item $j$. Then the adversary can choose a sequence of items in a way that the online algorithm places only a single item. In other words, it chooses the sequence where $w_j=W$ and all other items have $w_i$ small enough to make the competitive ratio grows without bound.
This proof seems wrong because I did not fix the sequence of input beforehand, right? (My input sequence changes when the online algorithm changes.) I should fix the input, then prove that no online algorithm is competitive. How to do this?

Let's check the definition of a competitive algorithm, in your specific case. For simplicity, we assume that $W = 1$.
We can describe an algorithm for Knapsack as a sequence of functions $A_n\colon \mathbb{R}_+^n \to \{0,1\}^n$, describing which items are taken given their weights, which satisfies the following two properties:

The result fits inside the knapsack: for all $w \in \mathbb{R}_+^n$, if $x = A_n(w)$ then $\sum_{i=1}^n x_i w_i \leq 1$.
The algorithm is online: for all $w \in \mathbb{R}_+^n$ and $m \leq n$, if $x = A_n(w)$ and $y = A_m(w_1,\ldots,w_m)$ then $x_i = y_i$ for $i = 1,\ldots,m$.

The algorithm is furthermore $c$-competitive if:

For all $w \in \mathbb{R}_+^n$ and $o \in \{0,1\}^n$ such that $\sum_{i=1}^n o_i w_i \leq 1$, if $x = A_n(w)$ then $\sum_{i=1}^n x_i \geq c \sum_{i=1}^n o_i$.

(Your definition might put $c$ on the other side of the inequality.)

Suppose now that $A$ is a $c$-competitive algorithm, where $c > 0$, and let $N = \lceil 1/c \rceil + 1$, so that $cN > 1$.
Consider $w_1 = 1$ and $o_1 = 1$, which satisfies $o_1 w_1 = 1$. By Property 3, $x_1 = A_1(w_1)$ satisfies $x_1 \geq co_1 = c > 0$, and so necessarily $x_1 = 1$.
Now consider $w = 1,1/N,\ldots,1/N$, where there are $N$ many $1/N$'s, and $o = 0,1\ldots,1$, where there are $N$ many $1$'s. These vectors satisfy $\sum_{i=1}^{N+1} o_i w_i = 1$. Let $x = A_{N+1}(w)$. By Property 2, $x_1 = A_1(w_1) = 1$. By Property 1, $x_2 = \cdots = x_{N+1} = 0$. By Property 3,
$$1 = \sum_{i=1}^{N+1} x_i \geq c\sum_{i=1}^{N+1} o_i = cN, $$
which contradicts the choice of $N$. This contradiction shows that no $c$-competitive algorithm exists.

Here is how this proof would usually be presented. Consider any competitive algorithm. We start by presenting it an item of weight $1$. If the algorithm doesn't take the item, then we immediately end the stream, and so the algorithm is revealed to be $0$-competitive (comparing to the solution which does take the item). Otherwise, we present it $N$ more elements of weight $1/N$. The algorithm's knapsack is already full, so it cannot take them. Since instead it could have taken only the $N$ low-weight elements, this shows that the algorithm isn't even $1/N$ competitive. Since $1/N$ can be arbitrary small, we reach a contradiction.
Notice how this argument is much less formal and much more "intuitive", if not particularly shorter (though this is only an artifact of this particular argument being so simple). We usually present it in the latter form, keeping in mind that we could translate it in principle to the more formal form of the former proof. This is no different than the difference between written proof and completely formal proof in the sense of formal logic.


Accounting method - dynamic array I want to compute the amortize time of a type of dynamic array (inserting such that if i have no place to insert i am multipling the array by (1+a) (a is between 0 to 1).
I need to compute the time with the accounting method.
The answer is that i need for each insertion a 2 + $1/a$ coins.
I can see why the answer is right, problem is that i don't understand how i was supposed to get to the answer myself so what i am asking for is the way to the solution and the way to approach the question.

The accounting method relies on two arguments. The first is that in any sequence of $n$ operations, you never run out of coins. That is, however you choose to distribute the coins and pay for the operations, no sequence of operation will lead your scheme to a negative balance. The question remains of what this has to do with running time. Now the second argument comes into play, you want the running time to be bounded by the number of chips spent (without this claim, we have nothing relating the amortized running time with our chips distribution scheme). We can conclude that if you have devised a scheme satisfying those two properties, in which $C$ is the maximal amount of chips drawn in a single operation (where the maximum is taken over different types of operations), then the amortized running time is bounded by $C$.
This sheds some light on how to choose the number of chips per operation. I want to draw, for some element $x$, a number of coins that will suffice for all future operations involving $x$ (think of the insertion of $x$ as an element being born, and you attempt to compute how much money you will need from childbirth all the way to college). The tricky thing is that $x$ can be involved in an unbounded number of operations. Each extension of the array requires moving $x$, so I don't know how to determine the number of coins that will suffice to put $x$ through its entire existence. We can overcome this by having each element pay for his part in the first extension after its insertion.
Suppose that you just extended your array from size $k$ to size $\lceil(1+\alpha)k\rceil$. You would need to add an additional $\lceil(1+\alpha)k\rceil - k$ elements before the next extension, which will require $\lceil(1+\alpha)k\rceil$ operations. Let us try to construct our distribution scheme in such a way that only those new elements would pay for the next extension. Let $C$ be the number of coins requested for each insertion which allows this. It suffices that $C\cdot \left(\lceil(1+\alpha)k\rceil - k\right)\ge \lceil(1+\alpha)k\rceil$, or equivalently $C\ge\frac{\lceil(1+\alpha)k\rceil}{\lceil(1+\alpha)k\rceil - k}$. Since $\frac{\lceil(1+\alpha)k\rceil}{\lceil(1+\alpha)k\rceil - k}\le 1+\frac{k}{\lceil(1+\alpha)k\rceil - k}\le 1+\frac{k}{(1+\alpha)k-k}=1+\frac{1}{\alpha}$, it suffices to ask for $1+\frac{1}{\alpha}$ coins. Recalling that you also need a coin for the insertion itself yields the desired result of $2+\alpha^{-1}$.


Upper bounding randomized k-SAT solver Problem:

Consider a k-SAT solver that assigns values independently uniformly at random to all the variables. Given the formula has $m$ clauses provide an upper bound for the probability of a random assignment to be unsatisfiable.

The issue is that I have no clue from where to start. Both Markov, Chernoff, Chebyshev and McDiarmid's inequalities seem to be not applicable in this situation as the probability of a particular clause to be unsatisfiable depends on the probability of other clauses with overlapping variables to be unsatisfiable.

For every clause the probability of it to be unsatisfiable is
$${1 \over {2^k}}$$

There are $m$ clauses in total, so if there are all independent, the answer would be
$$P(\mathit{assignment~is~unsatisfiable}) = (2^{-k})^m$$

If somebody would help me a bit with at least some kind of hint I would be extremely grateful.

Hint: Use a union bound.

Note that for $m \geq 2^k$ you cannot provide any non-trivial bound, since there are formulas with $2^k$ clauses of width $k$ that are unsatisfiable. The same example shows that the bounded hinted above is tight (for all $m \leq 2^k$).


Prove function in little-oh of a big-theta function I'm having trouble with this homework question.

Prove if $f(n)$ is $o( g(n) )$ and $g(n)$ is $\Theta( h(n) )$, then $f(n)$ is $o(h(n))$.

I know I need to use the precise definition of a limit, but I'm not sure how to apply it to this proof. Any help would be appreciated.

$f(n)$ is $o( g(n) )$

This above equation implies the following:

$f(n) < c \cdot g(n) \  -(1)$

for some $c \in R$ and $\forall n \geq n_{0}$

$g(n)$ is $\Theta( h(n) )$

The above equation implies following:

$ c_{1} \cdot h(n) \leq g(n) \leq c_{2} \cdot h(n) -(2)$

for some $c1, c2 \in R$ and $\forall n \geq n_{0}'$

Now let's assume $c$ > 0

Multiplying equation $(2)$ by $c$ gives:

$ c \cdot c_{1} \cdot h(n) \leq c \cdot g(n) \leq c \cdot c_{2} \cdot h(n)$

Considering right side of the above inequality:

$c \cdot g(n) \leq c \cdot c_{2} \cdot h(n)  -(3)$

Let $n_{0}''$ be $max(n_{0}, n_{0}')$

We can say $\forall n \geq n_{0}''$, equation $(1)$, $(2)$ and $(3)$ will hold true. Now by using $(1)$ and $(3)$, we can infer:

$ c \cdot c_{2} \cdot h(n) > f(n) -(4)$

Let $c' = c \cdot c_{2}$

Therefore we can write equation $(4)$ as:

$ f(n) < c' \cdot h(n)$

$\forall n \geq n_{0}''$ and since $R$ is closed under multiplication, therefore $c \in R$

which implies $f(n)$ is $o(h(n))$.

Note: For $c < 0$, you can consider left side of the inequality, which after multiplying by $c$ will actually come to right side (since $c < 0$).


Efficient algorithm to compare arrays problem I was submitted an interesting problem, but I wasn't able to find a solution.

Define a function p(x, y) that takes int x and y, with y > x and returns an int.

p(x, y) = x & (x+1) & (x+2) & ... & (y-1) & y

There are then two arrays X of length N and Y of length M representing x and y, in binary with M >= N > 0. X and Y are consistently indexed, so that X[0] and Y[0] represent the least significant digit of x and y.

The final goal is to write an efficient algorithm that computer p(x, y). The ideal solution would be to have a time complexity of O(M) and a space complexity of O(M).
We can assume that the bitwise AND operator is already implemented with a complexity of O(M) in both time and space. There's also no need to work on the binary representation of the numbers. Pseudocode is fine.

You can write $x$ and $y$ in binary as
\begin{align}
x&=x_{M-1} \ldots x_0 \\
y&=y_{M-1} \ldots y_0
\end{align}
(This is exactly the contents of your arrays.)
Since $x \neq y$, there must be a first bit (from the left) at which they differ. Say that this bit is $x_i \neq y_i$. Since $y > x$, we know that $y_i = 1$ and $x_i = 0$. Thus
\begin{align}
x &= x_{M-1} \ldots x_{i+1} 0 x_{i-1} \ldots x_0 \\
y &= x_{M-1} \ldots x_{i+1} 1 y_{i-1} \ldots y_0
\end{align}
The following two integers are in the range $x,\ldots,y$:
\begin{align}
&x_{M-1} \ldots x_{i+1} 0 1 \ldots 1 \\
&x_{M-1} \ldots x_{i+1} 1 0 \ldots 0
\end{align}
This shows that if you take the AND of all integers from $x$ to $y$, you get
$$
x_{M-1} \ldots x_{i+1} 0 0 \ldots 0
$$


In lieu of neural networks and deep learning, what are some approaches to computer vision? So much software related to computer vision relies on AI and neural networks, I wonder some of the approaches which don't use those methods. How could some of the mainstays of computer vision (eg. recognition and identification) be achieved without "artificial" means?

I'm reading Vision by David Marr and it talks about the human visual system model and how it could be emulated algorithmically for computer vision. I know of salience mapping and edge detection algorithms which there's significant consensus that the brain processes visual information in a manner not too dissimilar to, but what other methods are there?

Consider something such as facial recognition: I have a headshot of hundreds of individuals, how could a system recognize if a new face was novel or previously recognized without neural networks or deep learning? My interest is in white-box approaches to computer vision rather than these black-box approaches.

I think you could use some type of probabilistic model to solve this issue. I might be completely wrong, though, as I do not know a lot about probabilistic models.

Some time ago, I made use of Markov chains to generate levels for a game called Mega Man, and I remember that the results were promising, so I looked up "Markov Chains and face recognition" and found the following paper:

http://www.anefian.com/research/nefian98_face.pdf

It deals with the specific problem of face recognition.

Markov Chains also work with Optical Character Recognition, and though I know that comparing a letter to a face is a bit of a stretch, the following paper might give you some insight.

http://www.aclweb.org/anthology/N03-1018

I hope that helps!


Function that enumerates a recursively enumerable language I have an exercise where one is supposed to give a function that will enumerate the following language:

$L_1 = \{ a^pb^p \hspace{1mm} |\hspace{1mm} p \in  \mathbb{N} \hspace{1mm} \wedge \text{ (P is a prime number )} \}$.

The solution is the following function: $f:  \mathbb{N} \rightarrow \Sigma^*$ with $f(i) = a^{p_{i+1}}b^{p_{i+1}}$,
where $p_{i+1}$ is the $(i+1)^{th}$ prime number, ordered by the prime's order.

Could anyone explain to why does this solution work? And especially why does the function include $p_{i+1}$ instead of $p_{i}$ ?

Thank you!

This function maps nonnegative integers to the set of integers of the form $a^pb^p$. Enumerating is trivial, just start $i$ from 0, compute $p_{i+1}$-th prime, compute $a^{p_{i+1}}b^{p_{i+1}}$ and output that number.

As for the index $i+1$, I guess that is because $0 \in N$ and it is assumed that primes are ordered starting from the index 1 not from 0, in other words we start from $p_1$ not from $p_0$, e.g., $f(0) = a^{p_1}b^{p_1}$.


Solving simultaneous multiple chinese remainder theorem on the quantum computer - possible? Is it possible to solving simultaneous multiple chinese remainder theorem on the quantum computer?

We have $k$ variables. Each variable can take two values.

The question is: can we calculate all possible circuits equations chinese remainder theorem (which may be $2^k$) and reduce to the smallest result on a quantum computer?

I know the question can be very difficult but I wanted to ask.

I hope I have described the problem quite clearly (but maybe there are ambiguities).

For example we have table:

2 3 7 31

A B C D => [RESULT]

0 1 3 4 => 934
0 1 3 27 => 430
0 1 4 4 => 4
0 1 4 27 => 802
0 2 3 4 => 500
0 2 3 27 => 1298
0 2 4 4 => 872
0 2 4 27 => 368

Third line:

0 1 3 4 => 934

means the system of equations:

$x \equiv 0 \pmod 2$

$x \equiv 1 \pmod 3$

$x \equiv 3 \pmod 7$

$x \equiv 4 \pmod {31}$

and solution for this line in CRT (chinese remainder theorem) is 934.

The final result that the algorithm should return (minimum) is 4. This result is in line:

0 1 4 4 => 4

This is just an example - I wanted to show to know what I mean.

Someone may have some idea?

Sorry for the (maybe) difficult question.

If you prepare a superposition containing the various input problems, a quantum computer will allow you to compute a superposition containing the various outputs.

That being said, I'm not sure why you would want to do this. You only get to sample one of the outputs, and you don't get to pick which one. You'll get one of them at random. Presumably you would instead do some quantum computation on the output superposition, perhaps use a QFT to sample from their frequency space... but just remember that this means you must erase the input! Otherwise you won't be able to interfere the various output cases.


Why is the complexity of this nested for loop not $O(n^2)$? I have the following pseudo-code:

mystery(n):
if n <= 50 :
    for i = 1 ... n :
        for j = 1 ... n :
            print i*j
else :
    mystery(n-1)

For the following nested for loop:

for i = 1 ... n :
        for j = 1 ... n :

For every i in n, j iterates through n as many as i times. So, why is it that the complexity is not $O(n^2)$?

Because $n$ is bounded by $50$, which is simply a constant. Observe that when $n$ is larger than $50$, you simply have a recursive call. It's only when $n \leq 50$ that you go into the first portion of the if statement and execute the for-loops. Therefore, both nested loops take $\Theta(1)$ time. Hence the total time complexity of the mystery function is linear.

Note that $O(n^2)$ is technically correct, though not tight since $O(1) \subset O(n^2)$. The exact running time is $\Theta(1)$ as pointed above.


Why use comparisons instead of runtime for comparing two algorithms? I notice that in a few CS research papers, to compare the efficiency of two algorithms, the total number of key comparison in the algorithms is used rather than the real computing times themselves. Why can't we compare which one is better by running both programs and counting the total time needed to run the algorithms?

This is actually a deep issue that has some methodic and some pragmatic answers. I assume you want to know something about the algorithm(s) at hand. If you want to know which algorithm works better on a given machine on given inputs, go ahead and measure runtimes. If you want to compare the quality of a compiler for a given algorithm, go ahead and measure runtimes. For learning something about the algorithm, don't do it.

Let me first give some reasons why using runtimes is not a good idea.

Generality
Runtimes measured using one language and one compiler on one machine have little meaning if you change any component. Even slightly different implementations of the same algorithm may perform differently because you trigger some compiler opimisation in on case but not in the other.
Prediction
So you have a couple of runtimes for some inputs. What does that tell about the runtime of some other input? In general, nothing.
Significance
Usually, you won't benchmark all inputs (of some size), so that immediately restricts your ability to compare algorithms: maybe your test set triggered the worst case in one and the best case in the other algorithm? Or maybe your inputs were too small to exhibit the runtime behaviour.
Metering
Measuring runtimes well is not trivial. Is there a JIT? Has there been contention, i.e. are you counting time the algorithm did not even run? Can you reproduce exactly the same machine state for another run (of the other algorithm), in particular concurrent processes and caches? How is memory latency dealt with?

I hope these convinced you that runtimes are a horrible measure to compare algorithms, and that some general, abstract method for investigating algorithm runtime is needed.

On to the second part of the question. Why do we use comparisons or similar elementary operations?

Analytic tractability
Assuming you want to do formal analysis, you have to be able to do it. Counting individual statements is very technical, sometimes even hard; some people do it nevertheless (e.g. Knuth). Counting only some statements -- those that dominate the runtime -- is easier. For the same reason, we often "only" investigate (upper bounds on) worst-case runtime.
Dominance
The selected operation dominates the runtime. That does not mean that it contributes the most runtime -- comparisons clearly do not, e.g. in Quicksort when sorting word-sized integers. But they are executed the most often, so by counting them you count how often the most executed parts of the algorithm are run. Consequently, your asymptotic runtime is proportional to the number of dominant elementary operations. This is why we are comfortable using Landau notation and the word "runtime" even though we only count comparisons.

Note that it can be useful to count more than one operation. For example, some Quicksort variants take more comparisons but less swaps than others (on average).

For what it's worth, after you have done all the theory you might want to revisit runtimes in order to verify that the predictions your theory makes are sound. If they are not, your theory is not useful (in practice) and has to be extended. Memory hierarchy is one of the first things you realise is important but missing in basic analyses.


Correctness of Dijkstra's algorithm This question is about the correctness proof of Dijkstra's algorithm in the third edition of Introduction to Algorithms by Cormen et al. (pages 660–661).

The proof makes a case that considering path $p$ is the shortest path that connects a vertex in set $S$ (set of vertices where the distance of nodes to node $s$, the starting node, is minimal) to  a vertex in set $u$ in $V-S$. It then considers the first vertex as $y$ in set $V-S$ along the path $p$. It argues that $y.d \leq u.d$ which is intuitive as $y$ precedes $u$ in set $V-S$. The second argument that since both $u$ and $y$ were in $V-S$ when $u$ was chosen thus $u.d \leq y.d$. I have following two doubts about the second argument:

Why were $y$ and $u$ both in $V-S$ when $u$ was chosen? We know by our construction that when both $u$ and $y$ are in $V-S$, then $y$ will be chosen before $u$.
The node $u$ is chosen such that when it's added to set $S$ it is not at the minimum distance from node $s$. How is this used in this proof?

In answer to both of your questions:
  Firstly, note that during the maintenance phase of the loop invariant proof, we are in the process of inserting u into S, and the way that y is defined is that it is a node in V\S while this is happening, therefore u and y exist in V\S at the same time when u is inserted. This answers your first question.
  Secondly, note that in the proof, we assume that u.d ≠ δ(s,u). It therefore follows that there would be a pair of nodes x and y (such that π(y)=x such that x ∈ S and y ∈ V\S) such that y ≠ u and therefore y must come before u, because otherwise from the Convergence Property it would automatically follow that u.d = δ(s,u) which would be a contradiction to our assumption. Therefore from here it must follow that y comes before u. But note that from the first point I made above, y must come after u. And this is exactly the whole point of the proof, both of these things cannot happen simultaneously unless y.d = δ(s,y) = δ(s,u) = u.d.
Note that we used the assumption that u is not the minimal distance from s when added to S by showing that we reach a contradiction if we assume this.


What's a bank memory? I've search on Google but still don't understand. I've read about it into arm book, but they don't define it.

Could you explain me what is it, where is it used, what's the point to have it and, if you can, its used into arm chips.

Thanks.

Memory banks were an abstraction paired with a hardware implementation to extend the amount of memory normally available to a particular architecture.

For example, the PDP-8 had a "page" size of 128 12-bit words, and most instructions could only address memory on the same page as itself.  Other instructions could access the full memory complement of 2^12 (4K!) 12-bit words.  To go beyond 4K, special techniques could address memory outside the normal 4K. When implemented, the original 4K became (memory) bank 0 and other
memory banks numbers 1, 2 etc might exist.

The details varied, as computers worked their way up to today's standard
of 64 bit address space.


Grouping n points into groups of size m with objective to have least traveling distance in each group Assumptions:

There are "n" jobs which are distributed over the city.
Company has "k" available workers.
Each worker can do "x" jobs per day.
"x" is dependent to the worker skills and the distance he travels each day so it's not a constant.
Workers have no initial traveling distance.
"s" is a set that shows each workers can do how many jobs based on the distance he travels
"d" is the number of days that takes for company to do all the jobs.

Objective: Minimize the "d"

I know this problem is probably NP-hard so I don't need the exact answer. I think it's kinda a variation of Traveling salesman problem combining with scheduling and assignment problems.

My algorithm for this problem is to "some how" efficiently ( of course not the most efficient way ) grouping the jobs based on their traveling distance in the groups in to groups of "m" which is the mean of set "s". Then after each day rerun the algorithm to get better results.

My question is what is the best way to do that grouping? Anyway if you know a better algorithm I would be more than happy to know them.

It's at least as hard as the "Traveling Salesman" problem, that is NP complete: TSP asks whether a salesman can visit n towns while travelling a distance ≤ K. Take the special case of one worker, who can do n jobs in a day if and only he travels a distance ≤ K, then the question "can the single available worker do all jobs in one day" is equivalent to TSP. But that is an extreme case.

Even an approximation is difficult. I assume each worker goes from company office to location 1 to location 2 ... to location n to company office. I'd try to group far away locations into clusters so that a worker can do a complete cluster and not be left with a single job in a cluster; doing half a cluster one day and the other half the next day would be fine, or picking jobs up on the way. Problem changes if each worker starts at home and ends up at home, then you'd want each one to do jobs near his home.

In reality, you will have new jobs coming in every day, so you need a solution for one day, and then recalculate the next day. Plus take into account that customers waiting a long time will get angry.


Does the 3SAT problems have to have consistent operators? What are the rules pertaining to 3SAT as to the actual boolean equation?

The main thing I do not understand is in a given boolean expression within a single clause can you have both AND + OR operators i.e. (x1 & x2 | x3) or do they have to remain consistent i.e. (x1 & x2 & x3) or (x1 | x2 | x3)?

That being said when connecting clauses together do the boolean operators have to be consistent?

i.e. (x1 & x2 & x3) & (x1 & x2 & x3) & (x1 & x2 & x3)

or

i.e. (x1 & x2 & x3) | (x1 & x2 & x3) | (x1 & x2 & x3)

or can they be mixed up like

i.e. (x1 & x2 & x3) | (x1 & x2 & x3) & (x1 & x2 & x3)

or

i.e. (x1 & x2 & x3) & (x1 & x2 & x3) | (x1 & x2 & x3)

Can a 3SAT problem just be a huge jumble of different logic operators or do they have to remain consistent throughout the equation? Ever example I have seen has consistent operators and I cant seem to find the answer to the question anywhere.

3SAT is a problem of deciding satisfiability of boolean formula in 3CNF form: this means that

Each clause has either exactly 3 different literals in each clause or at most 3 literals in each clause, according to different definitions.
Only $\lor$ operators can be used inside clauses (not counting varible negations).
Only $\land$ operators can be used outside clauses.

[General] SAT problem does not have a limit on number of literals in a clause and Circuit SAT allows any boolean formula.


Find maximal subset with interesting weight function You are given $n$ rows of positive integers of length $k$. We define a weight function for every subset of given $n$ rows as follows - for every $i = 1, 2, \dots, k$ take the maximum value of $i$-th column, then add up all the maximums.
For example, for $n = 4$, $k = 2$ and rows $(1, 4), (2, 3), (3, 2), (4, 1)$ the weight of subset $(1, 4), (2, 3), (3, 2)$ is $\max\{1, 2, 3\} + \max\{4, 3, 2\} = 3 + 4 = 7$.
The question is, having $m \leq n$, find the subset of size $m$ (from given $n$ rows) with maximal weight.
The problem looks trivial when $m \geq k$, but how can one solve it for $m < k$? Looks like dynamic programming on subsets could work for small $k$, isn't it? Are there other ways to do it?

Definitely NP-hard, since it can be used to encode a maximisation form of Vertex Cover in which we ask for the maximum number of edges that can be covered by any subset of $k$ vertices: The input matrix here is just the incidence matrix of the graph, with vertices in the rows and edges in the columns.


Fast Poisson quantile computation I am seeking a fast algorithm to compute the following function, a quantile of the Poisson distribution:
$$f(n, \lambda) = e^{-\lambda} \sum_{k=0}^{n} \frac{\lambda^k}{k!} $$

I can think of an algorithm in $O(n)$, but considering the structure of the series, there is probably a $O(1)$ solution (or at least a good $O(1)$ approximation). Any take?

Given a precision $ε>0$ you want to compute $f(n,λ)$. When $n≤m$, let $g$ be the error function, that is the difference, between the sum of the $m-1$ first terms and the actual value $f(n,λ)$.

$$g(n,λ,m)=e^{-λ}\sum_{k=m}^n\frac{λ^k}{k!}$$

You want to find a $m$ big enough to have $g(n,λ,m)≤ε$. Then you just have to remark that the following terms are not very big so you can go a little bit further:

$$g(n,λ,m)<e^{-λ}\sum_{k=m}^∞\frac{λ^k}{k!}=h_λ(m)$$

Since the well-known corresponding series converges, $\lim h_λ = 0$. So for all $ε$ and $λ$ you can find a $m_{ε,λ}$ such that $m_{ε,λ}$ steps are enough to compute $f(n,λ)$ with precision $ε$.

Given $ε$ and $λ$ your problem is in $O(1)$.


Substitution lemma for types TAPL (page 549) proposes the following lemma in order to prove soundness of System F type system:

Substitution lemma for types:

$E, X, \Delta \vdash t: T \implies E, [X \mapsto S] \Delta \vdash [X \mapsto S]t: [X \mapsto S]T$

Proof of the T-TApp case:

$ E,X,\Delta \vdash t[A]: [Y \mapsto A]T $

and by rule T-TApp we have:

$ E,X,\Delta \vdash t: \lambda Y . T $

so by induction hypothesis:

$E, [X \mapsto S] \Delta \vdash [X \mapsto S]t: \lambda Y. [X \mapsto S]T$

so applying the T-TApp rule we have:

$E, [X \mapsto S] \Delta \vdash [X \mapsto S]t[A]: [Y \mapsto A][X \mapsto S]T$

however I should need $[Y \mapsto A][X \mapsto S]T = [X \mapsto S][Y \mapsto A]T$

I think I can assume that $A,S$ cannot contain $Y$.

However, what if $A$ contains $X$? Then these types do not coincide.

Assume $T$ contains $Y$. Then the lhs type leaves $X$'s in the result while the rhs type does not leave any.

Other sources

You can find an sketched proof in the proof of lemma 17, page 86 of the following lecture notes. But this case appears to be immediate.

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

There several ways to model variable names and renaming.

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

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

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


Term for binary search tree using hashes? I was looking for a way to easily store and access a symbol table using the least memory and code as possible and I went with a BST. Symbols, however, tend to be defined in order as in foo0, foo1, foo2... so tree balance is an issue.

I considered balancing and auto-balancing algorithms, but then I realized that the hash for a key given a good hash function should have a 50% average chance for left/right. And I already had a hash function so that meant no additional code. So I would get a balanced tree for free(edit: at no point did I want to imply a perfectly balanced tree, this is emergent behavior).

I wanted to check if my theory was correct. When I search for BSTs, hashes, and hash trees, however, no relevant information turns up.

What is the term for a binary search tree that balances itself by using a hash?

edit:
I am going to accept the answer because if something doesn't have a name it just doesn't, but I tested this because some comments and asides imply that it is worse than it actually is.

I tested a sorted list of 468685 words containing both English words and "elite" password cracking words.

balanced-tree:    worst(19)     average(18.84)
edlin-tree:       worst(47)     average(22.72)
edlin-tree(SHA2): worst(46)     average(23.25)
regular BST:      worst(468685) average(234342.50)

So it's not going to replace your language library algorithms but, as stated in the accepted answer, it is obviously logarithmic.

As for the hash function(Which for reference is add+xorshift as in:

do{h+=*s;h^=h<<left1;h^=h>>right;h^=h<<left2;}while(*s);

), I have also tested how bad it is by comparing collisions to the expected value.

8 bits:
   expected :  468428.99
   axs      :  468429
   SHA2-256 :  468429

16 bits:
   expected :  403200.35
   axs      :  403189
   SHA2-256 :  403198

24 bits:
   expected :    6485.99
   axs      :    6451
   SHA2-256 :    6433

31 bits:
   expected :      51.14
   axs      :      59
   SHA2-256 :      47

32 bits:
   expected :      25.57
   axs      :      30
   SHA2-256 :      20

33 bits:
   expected :      12.79
   axs      :      14
   SHA2-256 :      11

35 bits:
   expected :       3.19
   axs      :       7
   SHA2-256 :       2

36 bits:
   expected :       1.59
   axs      :       1
   SHA2-256 :       2

37 bits:
   expected :       0.80
   axs      :       0
   SHA2-256 :       0

So, while it appears to lag for some bitnesses, it generally follows the expected values, both for tree depth and collisions.
What would a hash which is not good for your input mean? That your input generates a sequence when passed to it? That would be ridiculously unlikely statistically speaking. Worst case is O(n) but you are not going to see it.

The algorithm is not good compared to AVL or red-black, even though insertion will probably be faster generally, however it beats a linked list or betting on input for a BST any day.

To answer the explicitly asked question: There probably is no specific name for this data structure since noone has bothered to use or study it.

Regarding the underlying question: Even using a "good" hash function, you can not expect as well a degree of balanced as you think:

Looking at the node with key $foo$, we see that all keys (in the subtree below $foo$) with a hash smaller than $h(foo)$ will be in the left subtree, while all those with a larger hash will be in the right subtree. So the balancedness of the tree will depend on how far $h(foo)$ is away from the center. This has an expected value of $\frac 12 N$, where $N$ is the number of hash values that belong in the subtree below $foo$. So we can expect an average weight balance of $1:3$ in each node. While this is still enough to give logarithmic expected height, it is already notably worse than the $1:1.6$ balance an AVL tree has in the worst case. Factoring in the additional risk of the hash function being not "good" for the data of a specific run, the idea quickly becomes unattractive.

Additionally, in many practical scenarios you have the option of using a library implementation of AVL trees, while you have to implement the "hash tree" yourself. So your "for free" argument will typically be the other way round.


What does it mean that numbers are "totally ordered", in the Paxos Made Simple paper? I was studying Paxos from the paper by Lamport called "Paxos Made Simple".

Recall that Paxos is a distributed system algorithm with the goal that the processes participating in its protocol will reach consensus on one of the valid values.

On page 3, it says

  Since all numbers are totally ordered, condition P2 guarantees the crucial safety property that only a single value is chosen.

where P2 is the following

  If a proposal with value v is chosen, then every higher-numbered proposal that is chosen has value v.

What does it mean for numbers to be totally ordered? How is this property essential for condition P2 to guarantee safety?

Totally ordered means that there exists an order relation such that given any two elements, one is greater than the other. In other words, there are no incomparable elements. For example, the real numbers are totally ordered: either $x \le y$ or $y \le x$. Counter-example: set inclusion $\subseteq$ is an order relation, but $\{0\}$ and $\{1\}$ are incomparable.

Intuitively, a total order is one where you can lay all the elements on a line, where moving along the line always increases the value. (This is not mathematically true because some orders are too “dense” to fit.)

Suppose that two proposals numbered $n_1$ and $n_2$ are chosen, with values $v_1$ and $v_2$ respectively. The desired safety property is that the values are in fact the same: $v_1 = v_2$. By condition P2, if $n_1 \le n_2$, then proposal $n_2$ is higher-numbered than proposal $n_1$, so its value $v_2$ is equal to $v_1$. Similarly, if $n_2 \le n_1$ then $v_1 = v_2$. The fact that the integers are totally ordered implies that at least one of the propositions $n_1 \le n_2$ and $n_2 \le n_1$ is true, and therefore either way $v_1 = v_2$.

What condition P2 means in some idealized way is that if a choice is made, all subsequent choices will be for the same value. However, “subsequent” doesn't quite work out, because the numbering of the proposals doesn't necessarily correspond with the order in which they are made in real time: different nodes in the network can make proposals before they are aware of each other, so numbers can't be assigned to proposals in chronological order. Solving this problem is a large part of working out a consensus algorithm.


A procedure for Topological sort, proof for its correctness Definition: A preserved invariant of a state machine is a predicate, $P$, on
states, such that whenever $P(q)$ is true of a state, $q$, and $q  \rightarrow r$ for some state, $r$,
then $P(r)$ holds.

Definition: A line graph is a graph whose edges are all on one path.

Definition: Formally, a state machine is nothing more than a binary relation on a set, except
that the elements of the set are called “states,” the relation is called the transition
relation, and an arrow in the graph of the transition relation is called a transition.
A transition from state $q$ to state $r$ will be written $q \rightarrow r$.

DAG: Directed Acylic Graph

  The following procedure can be applied to any directed graph, $G$:

  Delete an edge that is in a cycle.
  Delete edge $<u \rightarrow v>$ if there is a path from vertex $u$ to vertex $v$ that does not
  include $<u \rightarrow v>$.
  Add edge $<u \rightarrow v>$ if there is no path in either direction between vertex $u$ and
  vertex $v$.

  Repeat these operations until none of them are applicable.

This procedure can be modeled as a state machine. The start state is $G$, and the
states are all possible digraphs with the same vertices as $G$.

(b) Prove that if the procedure terminates with a digraph, $H$, then $H$ is a line
graph with the same vertices as $G$.

Hint: Show that if $H$ is not a line graph, then some operation must be applicable.

(c) Prove that being a DAG is a preserved invariant of the procedure.

(d) Prove that if $G$ is a DAG and the procedure terminates, then the walk relation
of the final line graph is a topological sort of $G$.

Hint: Verify that the predicate
$P(u,v)$:: there is a directed path from $u$ to $v$
is a preserved invariant of the procedure, for any two vertices $u, \ v$ of a DAG.

(e) Prove that if $G$ is finite, then the procedure terminates.

Hint: Let $s$ be the number of cycles, $e$ be the number of edges, and $p$ be the number
of pairs of vertices with a directed path (in either direction) between them. Note
that $p \leq n^2$ where $n$ is the number of vertices of $G$. Find coefficients $a,b,c$ such
that as+bp+e+c is nonnegative integer valued and decreases at each transition.

  My Problems:

  I got stuck with problems $d$ and $e$ but solutions to other problems are welcome too.

  At problem  $d$, I could not understand the hint and why it is given, how it helps.

In my way for proving $d$, I am trying to show that given procedure always preserves the order of vertices, which are associated with edges, on the start graph $G$. So a line graph is automatically a topological sort since the "precedence order" of the vertices are preserved.

  But procedure number $3$ is problematic, how to show it preserves precedence ?

b. As operation $1$ cannot be performed, $H$ must be a DAG. Consider a topological sort of $H$. As $3$ cannot be performed, if $u$ precedes $v$ in the topological sort, there is a path from $u$ to $v$. Start at the initial vertex in the sort and keep moving forward until we find a vertex which has more than one outgoing edges (if each vertex has only one outgoing, then it is a line graph). Let $u$ have edges to $v$ and $w$ and let $v$ precede $w$. Then there is path from $v$ to $w$, which gives a path from $u$ to $w$ that doesn't include $u \rightarrow w$, a contradiction as operation $2$ can be performed here.

c. As deleting edges will not alter DAG property, we only need to check $3$. A cycle is formed only when we add an edge $u \rightarrow v$, when there was a path from $v$ to $u$ already. As $3$ doesn't add such edges, DAG is maintained.

d. Let $H$ be obtained from $G$ by a single operation. We show that any topological sort of $H$ is also valid for $G$ (note that the converse need not be true). For this we need to show that if there was a path from $u$ to $v$ in $G$, then there is path from $u$ to $v$ in $H$ too. Some path can be broken only when we are removing edges. So clearly operation $3$ will not cause any problem here. Also, in $2$, we are only removing those edges $u \rightarrow v$ where there is already a path from $u$ to $v$. So for any path from $w$ to $z$, containing that edge, we can just replace that edge by the path from $u$ to $v$, maintaining a path from $w$ to $z$ in $H$. And $G$ is DAG, so $1$ never happens.

e. First observe how each of $s$, $e$ and $p$ change with each operation. With operation $1$, $s$ reduces by at least $1$, $e$ reduces by $1$ and $p$ can decrease by close to $n^2$ (almost all paths might be broken). With $2$, $s$ might reduce by $1$ (not necessary though), $e$ reduces by $1$ and $p$ is unchanged. With $3$, $s$ doesn't change, $e$ increases by $1$ and $p$ increases by at least $1$. Notice that as we are going towards line graph, we are trying to reduce number of edges ($e$), remove cycles ($s$) while increasing $p$. So in $as+bp+de+c$, we expect $a$ and $d$ to be positive and $b$ to be negative. The worst case changes in $s,e,p$ for each operation are

$$
\begin{array}{cccc}
 & s & e & p \\
1. & -1 & -1 & -n^2 \\
2. & 0 & -1 & 0 \\
3. & 0 & 1 & 1
\end{array}
$$

As $s$ never increases, we can make $a$ as large as we want. As we can scale $a,b,d$ by a constant, lets keep $d=1$. With these observations we can get one possible set of values for $a,b,d$ as $2n^2$, $-2$ and $1$ respectively. And pick $c$ as negative of the value at line graph.


NP-completeness and NP problems Suppose that someone found a polynomial algorithm for a NP-complete decision problem. Would this mean that we can modify the algorithm a bit and use it for solving the problems that are in NP, but not in NP-complete? Or would this just shows the availability of a polynomial algorithm for each NP problem indirectly?

edit:
I know that when NP-complete problems have polynomial algorithms, all NP problems must have polynomial algorithms. The question I am asking is that whether we can use the discovered algorithm for NP-complete to all NP problems just by modifying the algorithm. Or would we just know that NP problems must have a polynomial algorithm indirectly?

Recall a few definitions. A language $L \subseteq \{0,1\}^*$ is polynomial-time reducible to a language $L' \subseteq \{0,1\}^*$, often denoted as $L \leq_p L'$, if there is a polynomial-time computable function $f : \{0,1\}^* \to \{0,1\}^*$ such that for every $x \in \{0,1\}^*$, $x \in L$ iff $f(x) \in L'$. Now, $L'$ is $\text{NP}$-hard if $L \leq_p L'$ for every $L \in \text{NP}$. $L'$ is $\text{NP}$-complete if $L'$ is $\text{NP}$-hard and $L' \in \text{NP}$.

It is easy to see that if $L$ is $\text{NP}$-hard and $L \in \text{P}$, then $\text{P} = \text{NP}$. Likewise, if $L$ is $\text{NP}$-complete, then $L \in \text{P}$ iff $\text{P} = \text{NP}$. The intuitive reason is that if $f$ and $g$ are functions that grow at most as $n^c$ and $n^d$ respectively, then the composition $f(g(n))$ grows at most $n^{cd}$, which is also polynomial.

Assume you found a polynomial-time algorithm $A$ for a $\text{NP}$-complete problem $X$. Now, you could in polynomial time transform another $\text{NP}$-complete problem to $X$ and solve it using $A$. This is why we often say that it suffices to study whether any $\text{NP}$-complete problem can be decided in polynomial time.


Oracle Relations Between Complexity Classes I'm trying to get a better handle on oracle separations between complexity classes but I keep running up against some (seemingly) silly issues that make me think that I'm fundamentally misunderstanding something (or more than one thing).

For example, I understand that for an oracle separation to hold in the unrelativized case it must hold for all possible oracles (which is why we cannot answer P=NP? this way). However, is it not true that for any two complexity classes we can always construct an oracle such that they are equivalent in relation to that oracle? For instance, by choosing a higher level of the arithmetic hierarchy to use as the oracle?

i.e. given two complexity classes $A$ and $B$ such that $A,B \subseteq \Sigma_{n}^{0}$, is it not always the case that $A^{\Sigma_{n+1}^{0}} = B^{\Sigma_{n+1}^{0}}$, given that the arithmetic hierarchy doesn't collapse? If not, why?

You seem to understand the concept even though you described it wrong.    Unless exactly one of {A,B} is uniform, an oracle separation of A from B either means  [showing that there is an oracle O such that  AO ≠ BO ] ,  or means [exhibitings an oracle O such that  AO ≠ BO ].

Yes, it is "not true that for any two complexity classes we can always construct an oracle such that they are equivalent in relation to that oracle".  In particular, most hierarchy theorems relativize.  However, it is the case "that for any two complexity classes we can always construct" a class-oracle "such that they are equivalent in relation to that" class-oracle.  (For example, this one always does that.)  The triangle levels do not have complete sets with respect to syntactic subclasses of R, and each other non-computable level is not low for itself.

Given "two complexity classes $A$ and $B$ such that $A,B \subseteq \Sigma_{n}^{0}$," it is indeed "not always the case that $A^{\Sigma_{n+1}^{0}} = B^{\Sigma_{n+1}^{0}}$," even though "the arithmetic hierarchy doesn't collapse".  See two sentences before this sentence.


Why aren't existential types implemented in any mainstream language? I'm talking about first-order existential types, as summarized here, with pack as the introduction form that bundles up a type with an expression of that type, and open as the elimination form that unpacks the type and its representative expression.

This seems just as fundamental as parametric polymorphism (universal types), so I'm surprised that this construct isn't implemented in e.g. Haskell or OCaml. Does anyone know the reasons for this?

OCaml's idea of modules roughly correspond with existential types ;)

Let's set up some rough semantics in order to frame this correspondence properly. First, I'll give the intro/elimination rules for existential types (I'll only use a variable $\to$ type context $\Gamma$ for the sake of simplicity here):
$$
\frac{\Gamma \vdash e\{\alpha\mapsto \tau\} : \sigma\{\alpha\mapsto \tau\}}{\Gamma \vdash [\tau, e] : \exists \alpha. \sigma} ({\rm Pack}) ~~~~~~~
\frac{\Gamma \vdash e : \exists \alpha.\sigma ~~~ \Gamma, x:\sigma \vdash e' : \tau'}{\Gamma \vdash {\rm let} ~ [\alpha, x] = e ~ {\rm in} ~ e' : \tau'}({\rm Unpack})
$$
where $e\{\alpha \mapsto \tau\}$ substitutes all occurrences of the type variable $\alpha$ with the concrete type $\tau$. In practice, we will also decorate the packed form with its existential type in order to disambiguate the semantics.

Operationally, we have the context reductions:
$$
\frac{e \Downarrow v}{[\tau, e] \Downarrow [\tau, v]} ~~~~~~ \frac{e \Downarrow v}{{\rm let} ~ [\alpha, x] = e ~ {\rm in} ~ e' \Downarrow {\rm let} ~ [\alpha, x] = v ~ {\rm in} ~ e'}
$$
which corresponds to the reduction strategies that reduces the expressions in the existential packages and the expressions to be unpacked.

Finally, we have the extensional $\eta$-reduction rule:
$$
\frac{}{{\rm let} ~ [\alpha, x] = [\tau, v]_{\exists \alpha. \sigma} ~ {\rm in} ~ e \to e \{\alpha \mapsto \tau, x \mapsto v\}}
$$

So for example, the program
\begin{align*}
{\rm let} ~ [\alpha, x] &= [{\rm int}, (0, {\rm succ})]_{\exists \alpha. \alpha \times (\alpha \to \alpha)} ~ {\rm in} ~ ({\rm snd} ~ x : \alpha \to \alpha)({\rm fst} ~ x : \alpha)\\
&\to^{\eta} ({\rm snd} ~ (0, {\rm succ}) : {\rm int} \to {\rm int})({\rm fst} ~ (0, {\rm succ}) : {\rm int}) \\
&\to^* {\rm succ} ~ 0 \\
&\to^\beta 1
\end{align*}

This exact idea is present in OCaml's concept of modules, save that the packed type must be a record (but which can be made to be isomorphic to any other OCaml type). For example, the creation of an existential type is done through the module type keyword:

module type Bundle =
sig
  type α
  val data : α * (α -> α)
end

This signature corresponds to the existential type $\exists \alpha. \alpha \times (\alpha \to \alpha)$. We can witness an inhabitant of this type by instantiating it with the struct keyword:

module BundleInt : Bundle = struct
  type α = int
  val data = (0, (+) 1)
end

which corresponds to the pack/intro $[{\rm int}, (0, (+) 1)]_{\exists \alpha. \alpha \times (\alpha \to \alpha)}$. Unfortunately, there is no explicit ${\rm let} \dots$ elimination form, but something like open BundleInt is equivalent to let [α, data] = BundleInt in ... where α and data are specified in the creation of the module type Bundle.

So while module types aren't exactly the same as your traditional existential types (the variables to be bound are explicitly pushed into the intro-form rather than in the elimination-form), their expressiveness are the same.


Does $\mathcal{P}\neq\mathcal{NP}$ imply $\mathcal{NP}\neq\mathcal{NP}^{\mathcal{NP}}$? I cannot see whether the implication in my question title holds. To me, it sounds reasonable to assume that, but I cannot find any source stating that this is true, false, or unknown at the moment.

So, does $\mathcal{P}\neq\mathcal{NP}$ imply $\mathcal{NP}\neq\mathcal{NP}^{\mathcal{NP}}$?

No, this implication is not known to be true, however it is believed that those are all separate classes.  (Unfortunately, I don't have any references to back up my claim now, but I still post this as an answer to point out the following.)

You are asking whether $\text{P} \neq \text{NP}$ implies that the polynomial hierarchy $(\text{PH})$ does not collapse to its first level.

The class $\text{NP}^\text{NP}$ is also known as $\Sigma_2^P$ which is one of the classes on the second level of the polynomial hierarchy.


Doubt in the correctness of decision tree models for constructing a lower bound If we were to intuitively construct a lower bound for searching an element in a list $A$ containing $n$ integers, it would be in $\Omega(n)$.

But with the decision tree model, the number of leafs is $n$, so we conclude that the lower bound is $\Omega(\log{n})$.

This is the same as finding the maximum element in a list. Intuitively, it is in $\Omega(n)$, but with the decision tree model it is $\Omega(\log{n})$.

Can someone help me understand this discrepancy ?

Thank you in advance.

The bound you're describing is that the depth of the decision tree is at least the logarithm of the number of distinct answers. This bound always holds, but is not always tight. In the case of searching an element in a list, it is tight when the list is sorted, and not tight if we don't assume anything on the list. The reason for this discrepancy is that the bound doesn't distinguish between the two cases — it is too general.

I challenge you to come up with another argument showing that the depth of a decision tree for finding an element in a list is at least $n$ (or even $n+1$, depending on how depth is defined).


Problem contest with matrix and DP I found this problem while I was reading  an ACM  problem and it is about dynamic programming. The problem says that you have a square matrix $n\times n$ filled with 1's or 0's, like this:

$$\begin{bmatrix} 1 &1 &1 &0\\ 1 &1 &1 &1\\ 0 &0 &1 &0\\ 1 &1 &1 &1 \end{bmatrix}$$

Now you have to find the biggest square matrix inside the original matrix which is filled with only 1's.
In my  example, take the matrix of $((1,1)$ to $(2,2)$
$$
\begin{bmatrix}
1 & 1\\
1 &1
\end{bmatrix}
$$

But, we might have to deal with matrices of size 1000X1000 as well. So the algorithm should be efficient and use DP, although I don't know if there is other solution. My Teacher told me that it can be done by Dynamic Programming. But I didn't understand his method.

An $O(n^2)$ algorithm is possible.

Let $A$ be the given matrix.

You compute the side of largest square with the bottom right corner at $(i,j)$, say $S(i,j)$

Now we can compute the side of the larger square for $(i+1, j+1)$ in terms of $S(i,j), S(i+1,j), S(i,j+1)$

as

$$S(i+1,j+1) = \min \{S(i,j), S(i+1,j), S(i,j+1)\} + 1 \quad \text{if}\quad  A[i+1,j+1] = 1$$

and

$$S(i+1,j+1) = 0 \ \text{if }\  A[i+1,j+1] = 0$$

There are other (complicated) $O(n^2)$ algorithms available, which also work for rectangles and can be used for this problem.


Dynamic Programming to Maximize Profit I have this problem to resolve in dynamic programming:

  An ice cream shop owner has 4 stores. To meet the demand in the summer he purchased 7 refrigerators for the ice cream. Because the stores are in different places, there are different points for selling the ice cream. It was estimated the profit (in monetary unit) that could be obtained in each store:

$$
\begin{array}{c|lcr}
N refrigerators & \text{store1} & \text{store2} & \text{store3} & \text{store4} \\
\hline
1 & 4 & 2 & 6 & 1 \\
2 & 6 & 6 & 12 & 4 \\
3 & 10 & 8 & 14 & 8 \\
4 & 12 & 10 & 18 & 16 \\
5 & 14 & 12 & 20 & 20 \\
6 & 16 & 16 & 22 & 21 \\
7 & 18 & 20 & 22 & 24
\end{array}
$$

The problem asks to find the working scheme that maximizes the financial return.

As dynamic programming aims to reuse the code I know that it is necessary to use a recursive function, but when analyzing the problem I assumed that my answer field is in a matrix where the lines are referring to the number of refrigerators and the columns the stores.

Then I assumed that $M(i, j)$ is my function that returns a monetary value, assuming that $i$ is the number of refrigerators, ranging from $1 \le i \le 7$, and $j$ is a particular store, ranging from $1 \le j \le 4$.

I also assumed that my function would have 4 calls of this same function $M(i, j)$, because there are 4 stores to divide 7 refrigerators:

The equation would be:

$$MAX  \{ M(i, 1) + M (i, 2) + M (i, 3) + M (i, 4)\}$$

Where $\sum_{i=1}^4 i \le 7$

As a base case of recursion I put this:

$$M(0, 1) + M (0, 2) + M (0, 3) + M (0, 4) = 0$$

But my problem is not knowing how to treat this problem recursively. Maybe I'm doing the wrong analysis, too. Every help is welcome.

In this particular case, you can just go over all possibilities.

The dynamic programming approach is to compute recursively the maximal profit that can be obtained from using $x$ refrigerators in the first $y$ stores (and not using any in the other stores). I'll let you fill in the missing details.


Syntax directed translation part of which compiler phase? I am reading dragon book for compilers. I am not able to understand in which phase does syntax directed translation actually happen.

A CFG can have set of semantic rules attached to it which is evaluated. For example, we can have semantic rules attached to a CFG which adds the type of identifier in the symbol table. Does it happen in syntax analysis or semantic analysis phase?

I do not have the dragon book with me so my answer may be off. But generally speaking the syntax directed translation means that you start with a sequence of token (so right after the lexer) and produce something. The translation is said to be directed by the syntax because the something must be produced in a very specific way. For each grammar rule, the translation defines the translation of the left-hand-side nonterminal as a function of the right-hand-side nonterminals' translations, and the values of the right-hand-side terminals.

Here is an example. If you have the following grammar rule:
$$stmt \rightarrow\boldsymbol{if}(expr)\text{ }stmt\text{ }\text{ }\boldsymbol{else}\text{ }stmt$$
And if we denote by $[\cdot]$ the translation then the above rule generates the translation rule
$$[\boldsymbol{if}(e)\text{ }s_1\text{ }\text{ }\boldsymbol{else}\text{ }s_2]=T_{if}([e],[s_1],[s_2])$$
where $T_{if}$ if the translation action for this rule.

One obvious use of SDT is to generate the AST of the input. In which case $T_{if}$ would look something like (I use ML-like syntax)
$$T_{if}(e,s_1,s_2)=AstIfNode(e,s_1,s_2).$$
But they are other possibilities. Furthermore, it is possible to generate an AST with attributes so that we can perform semantic analysis at the same time. For example if we have the rule
$$expr\rightarrow expr\boldsymbol{+}expr$$
then a translation for a "calculator-like" language could be
$$T_{+}(e_1,e_2)=\begin{cases}\{type=int,val=e_1.val+e_2.val\}&\text{if }e_1.type=int\text{ and }e_1.type=int\\\{type=error\}&\text{otherwise}\end{cases}$$

If we start to have identifiers, then we can attach a symbol table to the nodes. For a simple language you can build an entire compiler with a SDT (one-pass compiler), going from source code to machine code. But more advanced compilers usually just use SDT to produce an AST and then do more complicated things (notably they modify the AST).


DP for Weighted Interval Scheduling: why is sorting by finish time necessary? Problem :
In the weighted interval scheduling problem, we want to find the maximum-weight subset of nonoverlapping jobs, given a set $J$ of jobs that have weights associated with them. Job $i \in J$ has a start time $s_i$, a finish time $f_i$, and a weight $w_i > 0$. We seek to find an optimal schedule — a subset $\cal{O}$ of non-overlapping jobs in $J$ with the maximum possible sum of weights.
Dynamic Programming Solution: In almost all textbooks or materials I could get access to, a DP algorithm is given as follows: First all jobs are sorted in order of ascending finish time: $f_1\le f_2 \le \dots \le f_n$. Let $OPT(i)$ be the maximum total weight of non-overlapping jobs in $\{1,2, \cdots ,i\}$, $p_i$ be the largest index $j < i$ such that job $j$ and $i$ are compatible. Then we see that
$$OPT(i) = \max\{{w_i + OPT(p_i), OPT(i-1)}\}$$
My question: I think I could understand why this DP algorithm works. However I didn't see the necessasity for the sorting step. What if we sort the finish time in ascending order instead?  As far as I can see, it's also correct.

Simple answer No, we cannot sort start time in ascending order to get a reasonable dynamic programming algorithm.
A counterexample

As illustrated above, we are given four jobs aligned in order of ascending start time, each labeled with its wight. Though some computation, we have $p_4=3$ and $OPT(4)=1+OPT(3)$. By definition,  $OPT(3)$ equals to the optimal value in $\{1,2,3\}$. By selecting job $1$ and job $2$, $OPT(3)$ is maximized and is equal to $3$. Then the optimum subset of the four jobs would be $\{1,2,4\}$, which is not a compatible set.
Necessity for sorting by finish time in ascending order: By sorting finishing time in ascending order, we ensure that for job $i$, $\{1,2,\dots, p_i\}$ is compatible with $i$ since they all finish before the start of $i$. But if we sort start time in ascending order instead, we cannot ensure that. As shown in above counterexample, $p_{4} = 3$, thus $\{1,2,\dots, p_4\}=\{1,2,3\}$ is not compatible with $4$. Suppose that $i$ is in the optimal solution $\mathcal{O}_i$ for $\{1,2,\dots, i\}$, then the optimal solution $\mathcal{O}_{p_i}$ for $\{1,2,\dots, p_i\}$ is also included in $\mathcal{O}_i$. specifically, we have $\mathcal{O}_{i} = \mathcal{O}_{p_i}\cup \{i\}$. Since we couldn't ensure that $i$ and $\mathcal{O}_{p_i}$ are compatible, we may get an invalid solution, which also can be seen from above counterexample.


Show that the multiplication lies in FL I don't know exactly how to solve the exercise below.

  Show that the multiplication lies in $\text{FL}$.

  Hint: A useful approach to a solution is to split the exercise into two parts and to explain that each function lies in $\text{FL}$. The standard multiplication scheme can be used as an intermediate step. Example:

  $\begin{align}
1001 \cdot{} 1100 & = \\
 1001000\\
 + \ \ \ 100100\\
 + \ \ \ \ \ \ \ \ \ \ \ \ 0\\
 + \ \ \ \ \ \ \ \ \ \ \ \ 0\\
\end{align}$

  Other useful approaches are certainly also accepted.

Useful definitions from our lecture notes:

Let $f : \Sigma^* \to \Sigma^*$ be a function, let $t : \mathbb N \to \mathbb N$ be a time bound and let $s : \mathbb N \to \mathbb N$ be a memory space bound.

$\bullet$ It is $f \in \text{FDTIME}(t),$ if there exists a DTM $M$ with an output tape, calculating $f$ and for which $T_M \in O(t)$ holds.

$\bullet$ It is $A \in \text{FDSPACE}(s),$ if there exists an offline DTM $M$, calculating $f$ and for which $S_M \in O(s)$ holds. The fields being written on the output band are not considered for the amount of memory space.

$\text{FP}=\bigcup_{k \in \mathbb N} \text{FDTIME}(n^k), \text{FL}=\text{FDSPACE}(\log n)$

I think the hint wants me to find two functions (one for the multiplication and one for the addition), but I don't see how to find two functions that do the calculation of the example in the appropriate way. Can somebody help me, please?

Hint: Consider the standard multiplication scheme. Suppose that we compute the sum column by column, starting with the LSB. How big is the carry we have to remember?

Comment: Multiplication is actually in NC1 (hard) and even in TC0 (harder).


IP Address CIDR Bitmask Conversion In looking for a programming function to validate an IP address within a subnet, I had to calculate the subnet mask from a given CIDR bitmask value ie. 192.168.0.0/24, the value 24 in this example.

The first step is to convert the bitmask value (24) into an unsigned 32bit integer.  I found this on the internet (specific to our 24 bitmask example):  mask = (( 2^24 ) - 1) * ( 2^(32-24) ).  This gives me an integer value of 4,294,967,040 which is exactly the binary number I am looking for where the first 24 bits are 1, while the remaining bits are 0 11111111.11111111.11111111.00000000.  Obviously, this works for any bitmask value 0-32.

I would like to understand why this works:  mask = (( 2^bitmask ) - 1) * (2^( 32-bitmask ))

The binary expansion of $2^n-1$ consists of $n$ ones. This is because the binary expansion of $2^n$ consists of a one followed by $n$ zeroes. This is similar to $10^3-1 = 999$ in decimal.

If we want these $n$ bits to be the left $n$ bits out of $m$ bits, then we need to add $m-n$ zeroes to the right. This is the same as multiplying everything by $2^{n-m}$. Compare $100 \cdots 54 = 5400$. This operation is usually known as left shift, and many languages support it natively. For example, in C you would use the following code to generate the mask:

  ((1 << 24) - 1) << (32-24)


What constitutes one operation/cycle/move in the RAM model? I saw a RAM model diagram that displayed an input tape, output tape, the program (read-only), the instruction pointer, and the memory registers. However, when I look at questions of time complexity, it is relevant how much time the program needs to spend on one action. Say you want to read one integer symbol from the read tape, add it to an integer from a memory register, and then squish the result into the write tape cell, and then move the read head one to the right and the write head one to the left. How much time or how many moves did I just waste?

Complexity is usually defined using Turing machine model to avoid the issue of the amount of resources taken during a complicated operation like adding integers.

You can use different notation of complexity of a RAM machine and that depends on what you are trying to do. If you want to be able to compare it with standard complexity classes which are defined using Turing machines then you should assign to each operation an amount of resource usage that a Turing machine would require to simulate that operation. The answer also depends on what kind of operations your RAM machine supports.

The standard RAM model consists of a finite control where a program is stored, one or
more accumulator registers $Acc$, an instruction counter, and an infinite collection of
memory registers $R[0], R[1],\ldots$. The instruction can be divided to four categories:

flow-control: unconditional jump, Accept, Reject, Halt, conditional jumps
(the "conditions" are simple like $Acc = 0?$);
input/output: read, write;
data-transfer between accumulator and memory: load, save;
arithmetic: $Acc := 0$, add $R[i]$ to $Acc$;

Two more common costs are uniform and logarithmic. The two are related quadraticaly for the instruction set above (i.e. to convert the uniform to logarithmic you need to square the running time). Logarithmic means taking cost to be logarithm (i.e. the number of bits) of the inputs to the operation whereas uniform means that all operations are considered to take unit time.


Is Morse Code binary, ternary or quinary? I am reading the book: "Code: The Hidden Language of Computer Hardware and Software"  and in Chapter 2 author says:

  Morse code is said to be a binary (literally meaning two by two) code
  because the components of the code consists of only two things - a dot
  and a dash.

Wikipedia on the other hand says:

  Strictly speaking it is not binary, as there are five fundamental
  elements (see quinary). However, this does not mean Morse code cannot
  be represented as a binary code. In an abstract sense, this is the
  function that telegraph operators perform when transmitting messages (see quinary).

But then again, another Wikipedia page includes Morse Code in 'List of binary codes.'

I am very confused because I would think Morse Code actually is ternary. You have 3 different types of 'possibilities': a silence, a short beep or a long beep.

It is impossible to represent Morse Code in 'stirct binary' isn't it?

By 'strict binary' I mean, think of stream of binary: 1010111101010.. How am I supposed to represent a silence, a short beep and / or a long beep?

Only way I can think of is 'word size' a computer implements. If I (and the CPU / the interpreter of the code) know that it will be reading 8 bits every time, then I can represent Morse Code. I can simply represent a short beep with a 1 or a long beep with a 0 and the silences will be implicitly represented by the word length.(Let's say 8 bits..) So again, I have this 3rd variable/the 3rd asset in my hand: the word size.

My thinking is like this: I can reserve the first 3 bits for how many bits to be read, and last 5 bits for the Morse code in a 8bit word. Like 00110000 will mean 'A'. And I am still in 'binary' BUT I need the word size which makes it ternary isn't it? The first 3 bits say: Read only 1 bit from the following 5 bits.

Instead of binary, if we use trinary, we can show morse code like: 101021110102110222 etc.. where 1 is: dit 0 is: dah and 2 is silence. By using 222 we can code the long silence, so if  you have a signal like *- *---    *-  you can show it like: 102100022210, but it is not directly possible using only with 1's and 0's UNLESS you come up with something like a 'fixed' word size as I mentioned, but well this is interpreting, not saving the Morse Code as it is in binary. Imagine something like a piano, you have only the piano buttons. You want to leave a message in Morse Code for someone and you can paint buttons to black. There is no way you can leave a clear message, isn't it? You need at least one more color so you can put the silences (the ones between characters and words. This is what I mean by trenary.

I am not asking if you can represent Morse Code in 57-ary or anything else.

I have e-mailed the author (Charles Petzold) about this; he says that he demonstrates in Chapter 9 of "Code" that Morse Code can be interpreted as a binary code.

Where am I wrong with my thinking? Is what I am reading in the book, that the Morse Code being a Binary a fact or not? Is it somehow debatable? Why is Morse Code is told be quinary in one Wikipedia page, and it is also listed in List of Binary Codes page?

Edit: I have e-mailed the author and got a reply:

-----Original Message-----

From: Koray Tugay [mailto:koray@tugay.biz]

Sent: Tuesday, March 3, 2015 3:16 PM

To: cp@charlespetzold.com

Subject: Is Morse Code really binary?

Sir, could you take a look at my question here: Is Morse Code binary, ternary or quinary? quinary ?

Regards, Koray Tugay

From: "Charles Petzold"

To: "'Koray Tugay'"

Subject: RE: Is Morse Code really binary? Date: 3

Mar 2015 23:04:35 EET

Towards the end of Chapter 9 in "Code" I demonstrate that Morse Code can be interpreted as a binary code.

-----Original Message-----

From: Koray Tugay [mailto:koray@tugay.biz]

Sent: Tuesday, March 3, 2015 3:16 PM

To: cp@charlespetzold.com

Subject: Is Morse Code really binary?

Sir, could you take a look at my question here: Is Morse Code binary, ternary or quinary? quinary ?

Regards, Koray Tugay

I am not hiding his e-mail as it is really easy to find on the web anyway.

This answer isn't as long as it looks; this site just puts a lot of spacing between list items! Update: Actually it's getting pretty long...

Morse Code isn't "officially" binary, ternary, quaternary, quinary, or even 57-ary (if I count correctly). Arguing about which one it is without context is not productive. It is up to you to define which of those five it is based on your application and the encoding requirements for your specific situation. To that end, there are pros and cons to each symbol set size, which you should consider for your situation before making a decision.

For the basis, M.1677, the international Morse Code standard, section 2, defines timings as:

  2 Spacing and length of the signals
  2.1 A dash is equal to three dots.
  2.2 The space between the signals forming the same letter is equal to one dot.
  2.3 The space between two letters is equal to three dots.
  2.4 The space between two words is equal to seven dots.

Note that that defines timings only, e.g. a dash does not mean the same thing as three dots, it is simply the same length. The base unit of time is a dot.

Binary

We can choose binary if we'd like. It is possible to represent Morse Code with "strict binary", as you call it -- that author's approach was to assign the digits to "dot" and "dash". That approach does not work and I do not think the author has a firm grasp of Morse code. But there is a different approach that works. If we choose binary, we essentially represent whether the signal is high or low with each symbol occupying a single dot-lengthed time slice. Note that this is also the approach described on the List of Binary Codes page you cited.

Other binary codings can be chosen as well (e.g. Bob Jarvis' answer) at the expense of increases in difficulty decoding back to audible Morse Code (Bob's encoding cannot be decoded statelessly, for example, the tradeoff is it provides shorter encoded sequences).

Symbols:

Low, off, etc. (0)
High, on, etc. (1)

Encoding Examples:

Signal separator: 0
Letter separator: 000
Word separator: 0000000
Three dots: 10101
Three dashes: 11101110111
The word "son": 101010001110111011100011101
The phrase "is a": 10100010101000000010111

Pros:

Minimal symbol set size
Easily managed with typical digital logic
Easy to decode into audible Morse Code (presuming no validation is done); stateless decoding and does not require storing information about the timing of symbols (every symbol is the same length).

Cons:

Long encodings.
Many opportunities for invalid encodings.
Individual symbol meanings (0, 1) depend on context.

Ternary

With this choice, we define letter and word spacings as rests, and signal spacings are implicit (although you could choose to require dot length rest symbols between signals, if it suits you better).

Symbols:

Dot-length rest (0)
Dot (1)
Dash (2)

Encoding Examples:

Letter separator: 000
Word separator: 0000000
Three dots: 111
Three dashes: 222
The word "son": 11100022200021
The phrase "is a": 11000111000000012

Pros:

Small symbol set size.
Signal separator no longer needed.
Shorter encoding lengths than binary.
Removes some invalid encodings (e.g. 0110 with the binary choice no longer possible).

Cons:

Still lengthy encodings.
Still many possibilities for invalid encodings, in particular, the rests.
Cannot be decoded statelessly† unless you choose to place explicit dot length rests between signals.
Signal separators are implicit‡ unless you choose to place explicit dot length rests between signals.
Some individual symbol meanings (0) depend on context.

Quaternary

Symbols:

Letter separator (0)
Word separator (1)
Dot (2)
Dash (3)

Encoding Examples:

Three dots: 222
Three dashes: 333
The word "son": 2220333032
The phrase "is a": 220222123

Pros:

Very short encoded length.
Possibility of invalid encodings is reduced.
Symbols are semantically accurate.
Arguably, more human-readable.

Cons:

Large symbol set size.
Cannot be decoded statelessly.†
Signal separators are implicit.‡

Quinary

A direct interpretation of Wikipedia's list. Note this is very similar to the binary choice except the various valid combination of binary 0's or 1's are given their own symbols.

Symbols:

Signal separator (0)
Letter separator (1)
Word separator (2)
Dot (3)
Dash (4)

Encoding examples:

Three dots: 30303
Three dashes: 40404
The word "son": 303031404041403
The phrase "is a": 3031303032304

Pros (compared to quaternary):

Can be decoded statelessly.
The only symbol set size that unambiguously, directly and concisely represents the five objects mentioned in section 2 of the standard: "dot" (to which all timings are relative to), "dash", "space between the signals", "space between two letters", "space between two words".

Cons (compared to quaternary):

Higher possibility for invalid encodings.
Increased encoding lengths without adding extra information (tradeoff is decoding ease).
Not as easy to decode as the binary choice, in that each symbol is a different length in time and this association must be maintained somewhere.

57-ary:

Included for completeness.

Symbols:

26 letters
10 numbers
20 punctuation marks and miscellaneous signs
Word separator (space)

Encoding Examples:

The word "son": son
The phrase "is a": is a

Pros:

Shortest encoding
Human readable
Invalid encodings are impossible.

Cons:

Largest symbol set
Difficult to decode into Morse Code; necessary to maintain tables of Morse Code output sequences for each symbol and necessary to detect word boundaries and adjacent letters to determine where to insert various rests.
Impossible to expand beyond the Morse Code specification without adding new symbols (tradeoff for being immune to invalid encodings).
Signal and letter separators are implicit.‡

Termination

For storage as a symbol stream on a device, if you need to do that, it's worth noting that M.1677 defines message and transmission termination sequences. From Part II:

  5 Every telegram shall be terminated with a cross signal (. – . – .)
  6 The end of the transmission shall be indicated by the cross signal (. – . – .) followed by the invitation to transmit signal K (– . –)
  7 The end of work shall be indicated by the station that transmitted the last telegram. The correct indication is the end of work signal (. . . – . –)

Unfortunately, the standard is silent on the ability to distinguish e.g. the string "+K" from the sequence (end-of-telegram, invitation-to-transmit). However, end-of-work is unique. If you are storing morse code, then, you will have to make a choice as to how you want to indicate the end of a stored sequence.

If you are storing an entire conversation, for example, and are using the binary symbol set, you could reasonably consider end-of-work to be the end of sequence indicator, represented as the unique bit sequence 101010111010111. You need to consider the type of data you are storing (e.g. message fragments, entire messages, entire conversations) as well as the facilities offered to you by your storage medium (e.g. ability to prefix with message length) before deciding. I suppose you could go so far as to define your own end of sequence indicator. In any case these are all matters of underlying storage and have too many possibilities to list here. The choice is really up to you based on whatever is appropriate for your situation.

† Cannot be decoded statelessly: These encodings require some state to be maintained in order to decode into audible Morse Code. They all require "If preceding symbol was a dot/dash and current symbol is a dot/dash then insert signal separator". While you could try and "cheat" and automatically append a signal separator to all symbols while reducing word separator to 5 rests and letter separator to 1, M.1677 afaict does not explicitly prohibit consecutive word separators, which breaks this kludge.

‡ Signal separators are implicit: This is directly related to the above note but more semantically oriented. These encodings have implicit signal separators in their notation. That is "zzz" is intuitively three separate z's, the boundaries are "piggybacked" on whatever it is that separates symbols in the encoding itself. Consider the description "three dots in a row"; intuitively we take this to mean three separate dots, but if separators weren't implied this could be taken to be indistinguishable from a dash. Only the Wikipedia-style binary and quinary (or ternary with the explicit signal separator option) representations remove all ambiguity and "shortcuts" here, which can be of great value depending on the situation. It is for this reason that there is a strong argument for the quinary choice.

TL;DR:

As you can see, there are advantages and disadvantages to each, and it's up to you to decide how you want to treat it based on your requirements. There is no right answer. You could attempt to argue that one is more appropriate than the other in general, but these arguments would boil down to pedantic preferences, as without context, there is no correct answer.

Now, all that said, in my own opinion, the quinary choice is the representation that feels the most "right" to me for Morse Code itself (originally I had favored quaternary). It is the only choice that provides all of the following:

Context-free symbols (a symbol on its own contains all information about its meaning without examining adjacent symbols).
Representation of all primitives defined in M.1667.
Separators (signal, letter, word) are not implied by notation or underlying encoding (this is important, if I wrote { dot, dot, dash }, those ,'s are significant and easy to overlook).

However, there are strong arguments for all. The arguments related to encoding are also applicable to the treatment of Morse itself. There is no 100% concrete answer, but it can certainly make a good topic for debate with your friends at the bar.

. . . – . –


Looking for a problem provably not in P My basic position is that everything is in P. Then comes the time hierachy theorem and EXP. That's easy: simulate and then diagonalize. After that comes EXP-completeness; that's difficult to swallow. Papadimitriou basically says that the proof is very similar to that of Cook-Levin theorem and do it yourself. Also, I wish to see the paper why Checkers is EXP-complete, but couldn't find a free version on the net.

Can you show me why a problem can be EXP-complete and not in P provably? How is the diagonalization encoded in the problem instances?

The time hierarchy theorem already does the diagonalization for you.

Let $X$ be any $\mathbf{EXP}$-complete problem. If $X\in\mathbf{P}$, then $\mathbf{EXP}=\mathbf{P}$, since we can solve any problem in $\mathbf{EXP}$ by using the polynomial-time reduction to $X$ followed by the polynomial-time algorithm for $X$. But $\mathbf{EXP}=\mathbf{P}$ contradicts the time hierarchy theorem, because that tells us that there are problems in $\mathbf{EXP}$ that are not in $\mathbf{P}$. Therefore, $X\notin\mathbf{P}$ for any $\mathbf{EXP}$-complete $X$.

Honestly, the proof that checkers is $\mathbf{EXP}$-complete will be long and not at all enlightening: the only thing that simulating Turing machines with checkers positions will teach you is that the craziest systems can support computation. It's much easier to see that the following problem is $\mathbf{EXP}$-complete. The input is the description of a Turing machine $M$, and an input $x$. You accept if $M(x)$ halts within $2^{|x|}$ steps and reject otherwise. Call the language of accepted strings $L$.

So, let $Y\in\mathbf{EXP}$ be a set of strings over, e.g., $\{0,1\}^*$. It is decided by a Turing machine $M$ that runs in at most $2^{n^c}$ steps for some integer constant $c$, on inputs of length $n$. We define a new Turing machine $M'$ with input alphabet $\{0,1,p\}$ ("$p$" for "pad") that behaves as follows:

if its input is of the form $z\,p^{|z|^c-|z|}$ for some $z\in\{0,1\}^*$, it simulates $M(z)$ and accepts or rejects as that machine does;
otherwise, it rejects.

Note that $|z\,p^{|z|^c-|z|}| = |z|^c$.

Now, the reduction of $Y$ to $L$ is as follows. Given a string $y\in\{0,1\}^*$ for which we want to know whether $y\in Y$, we ask whether $(\langle M'\rangle, y\,p^{|y|^c-|y|})\in L$. We can construct this query in polynomial time, since the description of $M'$ is some constant string, and we just need to write an easily computed polynomial number of $p$'s after $y$. And we have $(\langle M'\rangle, y\,p^{|y|^c-|y|})\in L$ iff $M'$ accepts $y\,p^{|y|^c-|y|}$ in at most $2^{|y\,p^{|y|^c-|y|}|}=2^{|y|^c}$ steps, iff $M$ accepts $y$ in at most $2^{|y|^c}$ steps, iff $y\in Y$.

Similar techniques give you complete problems for any time or space complexity class.


Algorithms to correct misspelled word? At present, I am doing a project on Optical Character Recognition (OCR). I am looking forward to improve the results by checking the output words of my OCR code with existing words from a text file. The file contains all English words.
Word is good to go if it exists in the file, but if it doesn't then I want to replace it with a word from the text file. Suppose the word in the image was "horse", and the OCR gives "hurze". Which algorithms should I use for detecting errors and their corrections.
I know that sometimes the correction depends on the context of the sentence. But, the thing is that I am not looking for 100% results. I just want to improve my results for OCR.
Can you suggest me anything else? I am looking forward to ideas.

Standard OCR software already incorporates this idea: it has a corpus of words, along with their frequency of occurrence, and uses this to correct  errors.

How does it work?  OCR doesn't just output a letter at each position; it actually produces a probability distribution on letters.  For example, its output might be something like: I'm 99% sure the first letter is a 'h'; I'm 60% sure the second letter is a 'u', but there's is a 20% chance it is a 'o', and a 15% chance it is an 'a', and so on.  This lets you consider many possibilities for what the word might be, and combine the probabilities from the OCR with the frequency of occurrence of that possibility in English text to come up with an educated guess about what the actual word is.

For instance, if the OCR says "5% chance this is 'hurze", 2% chance this is 'horse'", and you know that 'horse' occurs 100x more often than 'hurze' in English language, you should guess that the corresponding word is probably 'horse', not 'hurze'.

As Yuval Filmus says, another approach is to look for a dictionary word that is within edit distance 1 or 2 of the raw output from the OCR.

If your OCR software is any good, it might already be doing this sort of correction.  Sometimes you can give the OCR software a custom dictionary of words that tend to appear in your documents, to help it do this sort of correction.


Why in BFPRT (median of medians) algorithm the partition of the array by $7$ blocks would work but with the $3$ fail? I am working with the median-median algorithm or  BFPRT algorithm and I seek to understand why would the partition of the array by $7$ blocks would work but with the $3$ fail?

If we divide into blocks of $7$ then we will get:
Solving it by substitution I think the following manner:
It is a recursive tree. In the worst case it takes $T(10n/14)$ time. So in the worst case it goes down to the bottom by $(10/14)^kn=1$ steps; $k=log_{14/10}n$. At each level of recursive tree the total cost is $\le cn$ for some constant $c$. So by the simplified assumptions using substitution $k < n$ $T(n)\le dn \log(n)$

$T(n) \le T(n / 7) + T(10n / 14) + O(n) \le d\frac{n}{7}lg(n/7)+d\frac{10n}{14}lg(10n/14)+cn \le d(\frac{n}{7}lgn - \frac{n}{7}lg7) + d(\frac{10n}{14}lgn - \frac{10n}{14}lg10/14) + cn = d\frac{12n}{14}lgn - d\frac{n}{7}lg7 - d\frac{10n}{14}lg\frac{10}{14} + cn=d\frac{12n}{14}lgn - d\frac{n}{7}lg7 - d\frac{10n}{14}lg10 - d\frac{10n}{14}lg14 + cn \le d\frac{12n}{14}lgn + cn$

So, $T(n) = O(nlgn)$

The same way for blocks of size $3$.

$T(n) \le T(n / 3) + T(2n / 3) + O(n)$ we get $T(n) = O(nlgn)$

Now, how to show that $T(n)$ for 7 is also $O(n)$ and for 3 it can not be $O(n)$. Also, in general how can I guess that the $T(n)$ is also $O(n)$ because here in both cases my thoughts are they both $O(nlogn)$?

Let's take a look at the case of size 7 first. Here, we want to show a linear upper bound for $T(n)$.
Thus, we choose the recurrence relation $T(n) \leq T(n / 7) + T(5 / 7 n) + dn$ (remember, it is an upper bound).
We guess that the solution is of the form $T(n) \leq cn$ for some constant $c$ and prove it with induction:
$$T(n) \leq T(n / 7) + T(5 / 7 \cdot n) + dn \leq c \cdot n/7 + c \cdot 5/7 \cdot n + dn = 6/7 \cdot cn +dn. $$
To this end, we choose $c = 7 d$, resulting in $T(n) \leq cn$.

Now we want to show a lower bound for size 3 (for the worst-case, tho!).
So we have find a lower bound for its recurrence equation, namely:
$$T(n) \geq T(n/3) + T(2/3 \cdot n) + dn .$$
The list of medians takes $T(n/3)$ since there are $n/3$ medians (resp. blocks).
In the worst case, we have to recursively search in an area of size at least $2/3 n$.
Clearly, this recurrence relation is not linear.
To get an intuition for this, imagine that we would have equality.
Assuming a solution of the form $T(n) = cn$, we get $T(n) = 1/3 \dot cn + 2/3 \dot cn + dn$.
Since $d>0$, $T(n) > cn$ which contradicts our assumption.

For more information, check out the analysis on Wikipedia.

The key part is that for block size $3$ the sizes of the recursive calls add up to $n$, which does not help to reduce the running time.

If you have more questions, feel free to ask!


Algorithm for sorting pairs of items I have a real world problem where I have a list of nodes. Each ones contains a name and the name of the node before it in order. I am trying to devise an algorithm to sort these in order. The problem is that any two random nodes will not tell me anything about their order unless they happen to lie next to each other, so I can't use a traditional sorting algorithm.

When I try to work through ideas everything basically comes down to "grab" the node at the start and then place it after the correct node" then repeat with the next node at start of the list. The problem is this has worse case running time of $O(n^2)$ complexity if the items are reversed. Any ideas of how to efficiently solve a problem like this?

I believe you can solve it by:

first sorting the list that you have with some predictable ordering of the names. (maybe A -> Z)
Doing the final sort later, and to find the "previous" element thru name you just have to do a binary search on the ordered list.


Computing overlap of intervals in an integer programming framework Suppose I have 2 intervals C1 = [x1, x2] and C2 = [y1, y2], where x1,x2,y1,y2 are variables in an Integer program, I want to compute the overlap of C1 and C2. I am interested in a tight formulation for computing the overlap as an another variable with as few big M constraints as possible. Any references or formulations are deeply appreciated.

By overlap I understand its length (no its coordinates) since you didn't specify how to handle no overlap case.

First you need to know whether $x_1\le y_1$ which is just a comparison.

Next, you create new variables $l_1, l_2, r_1, r_2$ for which you know that $l_1\le r_1, l_2 \ge  l_1, r_2 \ge r_1$

Now the answer is $\min(\max(l_2 - r_1, 0), r_2 - r_1))$

How you build these constraints it is up to you. You can use approaches similar to https://blog.adamfurmanek.pl/2015/09/12/ilp-part-4/ and https://blog.adamfurmanek.pl/2015/09/19/ilp-part-5/


What is the file system of ram? As much I know about a memory and storing data there would always be a managing type feature in every memory which manages all the data and its location. So, what is the file system of a RAM. I also like to know the format or type (mp3, pdf, png, txt, jpg or binary) of data stored in.

Think of the file system and its files as a big cabinet with lots of physical folders in an office of bureaucrats. The sheets in the folders are arranged in fixed ways such that every bureaucrat knows exactly where to expect which information before taking the folder out of the cabinet.

Not let us assume that a bureaucrat (a program) performs a certain operation on a folder/file. It will take the folder to the desk, spread the sheets on the desk, cut certain things out, glue them together, paint marking son certain sheets, translates the text of a sheet to a new one, discards sheets entirely, add sheets, and do all kinds of crazy stuff on the data on the desk in the way that the bureaucrat wants it to do. After all that, the bureaucrat puts the relevant sheets nicely back into the folder such that everything is orderly, puts the folder back into the cabinet and then throw everything that is left on the desk back into the trash bin.

Note that the bureaucrat's desk is the RAM in this analogy. Now how are things stored on the desk? Well, that depends on what precise step the bureaucrat performs at a time instant. Even more, different bureaucrats doing essentially the same task may do things in a different order. So we can't really say anything about the organization of a bureaucrat's/program's desk/RAM other than whatever is put back into the cabinet/file system is put there orderly. In between, it is up to the bureaucrat how things are stored and in which encoding.

For most data in the RAM, the question how it is encoded does however make sense. However, this encoding can change frequently. For example, when a web browser receives text from a server, it may change the encoding multiple times before the data is actually displayed.

I hope that this analogy helps clearing things up. It has its limits, though, as in a computer, folders are not taken out of the cabinet, but they are rather copied and later overwritten, as this is cheaper in a computer than it is in real life. Also, because the memory sizes of the processes in a computer are not fixed, there is memory management going on, and one can say something about where memory allocation information is stored and how that information is encoded.


What does non-linearity mean in Neural Networks? Why is it necessary? ReLU units are said to be necessary in CNNs to introduce non-linearity which convolution does not involve. This is needed, because many real-world forms of data are non-linear.
What does non-linearity refer to?

A neural network, in its simplest form, consists of layers of neurons.
The first layer of neurons are the input, and the last layer forms the output.
A neuron $x$ on layer $i+1$ is connected to several neurons $y_1,\ldots,y_d$ on layer $i$, and it computes the following function:
$$
x = f(\alpha_1 y_1 + \cdots + \alpha_d y_d + \beta),
$$
where $f$ is a fixed function (nowadays often ReLU), and $\alpha_1,\ldots,\alpha_d,\beta$ are parameters which are learned in the training period. (The output layer often uses a different $f$.)
If $f$ is the identity function $f(z) = z$, then each neuron in the output is just an affine function of the input. This means that no matter how many layers the neural network has, all it can do is compute linear functions.
In order to allow the network to compute more complicated functions, we introduce nonlinearity, in the form of a non-linear function $f$ (that is, a function which is not of the form $f(z) = az + b$), such as ReLU, which is $f(x) = \max(x,0)$. This makes the neural network more expressive.


Recursive definition of a language given the regular expression Consider the language:
$$
L_1 = \{ x \in \Sigma^* : x \text{ does not contain the substring } 110\}
$$

I know that there is a DFA that accepts this language, and furthermore, that the regular expression is:
$$
(0 \cup 10)^* 1^*
$$

I'm asked to obtain a formal recursive definition of $L_1$, that is, find a basis $B \subset \Sigma^*$ and a finite set of functions on strings $\mathcal{F}$ such that $L_1$ is the closure of $B$ under $\mathcal{F}$, i.e. $L_1 = \langle B \rangle_{\mathcal{F}}$

I'm not sure how to go about this. Every way I can think to "encode" the regular expression into "functions" that build the language they're really ugly or involve piecewise definitions (if $x$ doesn't end with 1, otherwise, etc.)

Is there a simple and clean way to do this?

Just replace Kleene stars with $\epsilon$ to find the basis and position, then extend to both direction.

$B=\{\epsilon\}$

$\mathcal{F}=\{X\to0X|10X|X1\}$

$L_1 = \langle B \rangle_{\mathcal{F}}$