How to reverse a subarray of an array How to reverse the order of elements in an array between indices $i$ and $j$.
Ex: For the array [A,B,C,D,E,F], calling the function reverse(array, 1,4) will modify the array to be [A,E,D,C,B,F].
I want to optimize the solution to work with multiple calls on the same array, so pre-computations allowed. What would be the most efficient way to do so?

Let me restate the problem.  We're given an array $A_0$ and a sequence $(\ell_1,r_1),\dots,(\ell_m,r_m)$.  Set $A_{i+1}=\text{reverse}(A_i,\ell_i,r_i)$.  The goal is to compute the array $A_m$.

The naive way to solve this is to just incrementally apply the reverse operations, i.e., incrementally invoke Yuval's reverse algorithm $m$ times.  The running time of the naive solution is $\sum_{i=1}^m (r_i-\ell_i)$.  The question is, can we do better?

The answer is, yes, in some cases.  It's possible to build a data structure to optimize the sequence of reversal operations, in a way that's faster than the naive solution.  With sufficient cleverness, you can get the total running time down to $O(n + m \lg n)$ -- in comparison, the naive algorithm could potentially be as large as $O(nm)$, in the worst case.  I'll explain how to do it below.

We can model the desired rearrangement by a permutation $\pi$ on the array indices.  Such a permutation acts on arrays: given any array $\pi$ and any permutation $\pi$ on the indices, we can obtain an array $\pi A$, namely, the array $A'$ given by $A'[\pi(j)]=A[j]$.  Notice that the operation $\text{reverse}(A,\ell,r)$ should return the array $\pi A$, where $\pi(j)=\ell+r-j$ for $\ell \le j \le r$ and $\pi(j)=j$ for all other $j$.  Let $\text{rev}(\ell,j)$ denote this permutation.

This gives us a new strategy for solving the problem: first, compute $\pi = \text{rev}(\ell_m,r_m) \circ \cdots \circ \text{rev}(\ell_1,r_1)$; then, compute $A_m = \pi A_0$.  The latter step can be done in $O(n)$ time, with no additional space.  So, how quickly can we compute $\pi_m$?

Here is one way to compute $\pi_m$.  We will represent a permutation $\pi$ as an interval tree, i.e., a binary tree where each leaf has an interval on the indices.  The intervals on the leaves will be pairwise disjoint, their union will be $\{1,2,\dots,n\}$, and they will be in sorted order (from left to right).  Each internal node will hold an interval representing the union of the intervals on all of its descendants.  Also, we'll annotate each leaf with an affine function of the form $f(x)=x+\alpha$ or $f(x)=\alpha-x$.  The idea is that if we have a leaf with interval $[a,b]$ and function $f$, then $\pi(j)=f(j)$ for $j=a,a+1,\dots,b$.

In this way, we can represent a permutation as this sort of interval tree.  Notice that the identity function can be represented as an interval tree with one leaf, with interval $[1,n]$ and function $f(x)=x$.  Also, the permutation $\text{rev}(\ell_m,r_m)$ corresponding to a single reversal operation can be represented as an interval tree with three leaves, namely $[1,\ell_m-1],f(x)=x$, $[\ell_m,r_m],f(x)=\ell_m+r_m-x$, and $[r_m+1,n],f(x)=x$.

Now suppose we have an interval tree representing $\text{rev}(\ell_m,r_m) \circ \cdots \circ \text{rev}(\ell_{i+1},r_{i+1})$.  Let me explain how to derive an interval tree representing $\text{rev}(\ell_m,r_m) \circ \cdots \circ \text{rev}(\ell_i,r_i)$.  Basically, we search the interval tree to find all leaves whose interval overlaps with $[\ell_i,r_i]$, and split them in two pieces if they partially overlap (one piece that doesn't overlap, the other piece containing the rest that is contained within $[\ell_i,r_i]$).  Then, for each such leaf that overlaps $[\ell_i,r_i]$, if it currently contains the function $f$, we replace it with the function $g \circ f$, where $g(x)=\ell_i+r_i-x$.

So, we iteratively do this.  When we're done, we have an interval tree representation of $\pi$.  Now we can compute $\pi A_0$ in linear time.  The running time to construct the interval tree is now dependent on the number of intervals that get treated differently.  In other words, say that indices $j,j'$ are treated differently if there exists some $i$ such that $j\in [\ell_i,r_i]$ but $j'\notin [\ell_i,r_i]$ (or vice versa); otherwise, say that $j,j'$ are treated the same.  Now construct the equivalence classes of the "treated the same" equivalence relation.  Each equivalence class is one interval in the final interval tree, so the total running time is related to the total number of such equivalence relations.  In particular, if there are $k$ intervals in the final interval tree (i.e., $k$ such equivalence classes), then the running time is $O(mk+n)$.

It's possible to speed this up even further by annotating each internal node with an affine function as well.

The idea is that such an interval tree represents a permutation $\pi$ as follows: if we have a leaf with interval $[a,b]$ and function $f_0$, and its parent has function $f_1$, and its grandparent function $f_2$, and so on up to the function $f_d$ on the root, then for every $j \in [a,b]$, we have $\pi(j) = (f_d \circ \cdots \circ f_1 \circ f_0)(j)$.  In other words, the effective function on this leaf is the composition of all of the functions on the path from the leaf to the root.

This tree representation is even better: it allows you to derive the tree for $\text{rev}(\ell_m,r_m) \circ \cdots \circ \text{rev}(\ell_i,r_i)$ from the tree for $\text{rev}(\ell_m,r_m) \circ \cdots \circ \text{rev}(\ell_{i+1},r_{i+1})$ in $O(\lg k)$ time, where $k = $ the number of intervals in the tree.  Basically, we may have to split at most two intervals (one on the left side, if it partially overlaps $[\ell_i,r_i]$ on the left, and one on the right).  Then, we need to compose a function $g(x)=\ell_i+r_i-x$ to all of the leaves whose intervals is contained within $[\ell_i,r_i]$.  The latter can be done by identifying $O(\lg k)$ nodes of the tree whose (disjoint) union is $[\ell_i,r_i]$ (by construction you can always find such a set of nodes), and then composing $g$ with the function at each of those nodes: for each such node, if its function was $f$, you update it to $g \circ f$.

Consequently, the total running time of this improved solution is $O(n + m \lg k)$, where $k$ is the number of intervals in the final interval tree.  A conservative upper bound is $O(n + m \lg n)$ to perform $m$ reversal operations on an array of size $n$.  This is better than the naive algorithm, whose running time could be as bad as $O(nm)$.


Can you use binary files to reverse engineer cpu architecture? I wanted to know if it was possible to add code directly to a computer without an operating system or any programming language. To do that, I thought that maybe I could use the binary files to reverse engineer the actual cpu architecture. Just a random thought but I would like to know if that is possible.

This was certainly possible with early microcomputers such as the Altair 8800. Each instruction or data value was encoded as a binary number, set up by flipping a line of toggle switches up or down, and when the switches were all set correctly another switch was used to write that number into the next memory address.
Once you have done this once or twice you realise how tedious it is. Hence the rapid development of peripherals such as paper tape readers, punched card readers and eventually keyboards, all of which require some sort of operating system, even if a primitive one. In parallel, programming aids such as assemblers, programming languages, compilers and IDEs made programming simpler and quicker, at the cost of creating distance between the programmer and the hardware.
I doubt it would be possible to write binary instructions directly into the memory of a modern laptop, partly because of all the layers of peripherals and operating system functions that stand between you and the CPU, and partly because such a feature could be maliciously misused, so there are security features that prevent it. But it is certainly possible with a microcontroller board such as an Arduino - or you could build your own Altair 8800 !


Partition a bipartite graph to a complete matching and an independent set I am looking for a reference for the following theorem:

Let $G$ be a bipartite graph with partitions $X$ and $Y$, each with the same number of vertices ($n$).

There is a nonempty subset $Y_1 \subseteq Y$, and a partition of $X$ to disjoint subsets $X_1$ and $X_2$, such that:

There is a complete matching between $X_1$ and a subset of $Y_1$;
There are no edges between $X_2$ and $Y_1$.

Intuitively, $X$ can be seen as a set of men and $Y$ can be seen as a set of women. An edge between $x \in X$ and $y \in Y$ means that "$x$ and $y$ like each other" ("like" is considered a symmetric relation).

The goal is to find a subset of the women ($Y_1$) and a subset of the men ($X_1$), such that each man can marry a woman he likes without upsetting any of the other men ($X_2$), because no unmarried man likes any married woman.

This sounds similar to Hall's marriage theorem, but the premise is simpler. And, I am mainly looking for a reference that I can cite.

Some special cases:

If the graph is full (i.e. any man likes any woman), then we can take $Y_1=Y$, $X_1=X$, $X_2=\phi$.
If the graph is empty (i.e. no man likes no woman), then we can take $Y_1=Y$, $X_1=\phi$, $X_2=X$.
If there is $y \in Y$ with no neighbours (i.e. a woman that doesn't like any man), then we can take $Y_1={y}$, $X_1=\phi$, $X_2=X$.
If there is $y \in Y$ with a single neighbour $x \in X$  (i.e. a woman that likes a single man), then we can take $Y_1={y}$, $X_1={x}$, $X_2=X-{x}$.

The question becomes more problematic when all $y \in Y$ have at least two neighbours.

This question was subsequently posted on Math.SE. It received a complete answer by Zur Luria which I am quoting here.

I think I can prove your conjecture using Hall's theorem.
First of all, any perfect matching is also an envy-free matching, so if $G$ satisfies Hall's condition then there is an envy-free matching.
Otherwise let $S \subseteq X$ be a maximal subset such that $|N(S)|<|S|$. If $S=X$ then any $y$ that isn't in $N(S)$ isn't wanted by any $x$. If $|S|<n$ then the subgraph of $G$ on the vertices$X\smallsetminus S,Y \smallsetminus N(S)$ satisfies Hall's condition (otherwise we can make $S$ larger), and so it has a matching that matches all of the vertices in $X\smallsetminus S$. This matching is envy-free.


Floyd–Warshall algorithm ,Behavior with negative cycles I am sorry my English is not very good.
my problem might look simple for everyone here.
I have read about Floyd–Warshall algorithm in wikipedia,every thing was good but when I start reading "Behavior with negative cycles" I face problem in understanding this sentence:
"There is no shortest path between any pair of vertices i, j which form part of a negative cycle, because path-lengths from i to  j can be arbitrarily small (negative)"
I don't understand what it exactly mean.
can anyone help me please.
Behavior with negative cycles

Given a graph, suppose to have a cycle given by Nodes $i \ $,$\ j$,$\ k$ of negative cost.

Example:

$w(i,j)=2,\ w(j,k)=4,\ w(k,i)-7$

+---+    +2      +---+
| i |+---------->| j |
+-+-+            +-+-+
  ^                |
  | -7             |+4
  |     +---+      |
  +----+| k |<-----+
        +---+

Suppose you want to find the shortest path between $i$ and $j$.

You have

$P=\{(i,j)\}$ with $cost(P)=2$

but you can loop through the negative cycle and have:

$P'=\{(i,j),(j,k),(k,i),(i,j)\}$ with $cost(P')=1$
 $P''=\{(i,j),(j,k),(k,i),(i,j),(j,k),(k,i),(i,j)\}$ with $cost(P'')=0$
and so on.

You could loop forever through the negative cycle and decrease the cost of the path.

Same if you consider an undirected graph with an edge that has negative weight.


Can we define an ε deterministic finite automaton? I am studying automata and I was wandering if there is a definition of ε-DFA automaton. Is it feasible to define it?

Expanding on adrianN's comment, sure, you can define one if you want but what would be the point?

I guess the definition you have in mind is that the transition function has the form $\delta\colon Q\times (\Sigma\cup\{\varepsilon\})\to Q$. That is, for each state $q$ and each symbol $a$ in the alphabet, there's exactly one state that the automaton moves to after reading that symbol.  For each state, there's also a state the automaton can move to without reading a character of input (this is $\delta(q,\varepsilon)$).

Let's briefly investigate the properties of such a machine.  First, note that, if you don't want a $\varepsilon$-transition from some particular state, you can set $\delta(q,\varepsilon)=q$.  We can also see that this new type of automaton accepts exactly the regular languages. It's a special kind of NFA, so it can't accept any non-regular language.  And any DFA is just one of these automata where $\delta(q,\varepsilon)=q$ for every state $q$, so every regular language is accepted by an automaton of this kind.

So, what have we achieved?  The advantage of DFAs is that they're easy to analyze but it can be hard to construct a DFA to accept a particular language – if you don't believe me, design an algorithm that converts arbitrary regular expressions straight to DFAs, without using NFAs as an intermediate stage.  Conversely, NFAs are quite easy to construct but it can be hard to analyze what they're doing – for example, compare how annoyingly difficult it is to precisely define the language accepted by an NFA, compared to a DFA.

This new type of automaton seems to combine the disadvantages of both: requiring exactly one transition per state per symbol and at most one $\varepsilon$-transition per state means that it's still going to be fiddly to design an automaton that does what you want.  But the fact that the $\varepsilon$-transitions introduce nondeterminism means that it'll be harder to analyze what's going on. Meanwhile, the power of these new automata is exactly the same as the automata we already had, so we don't seem to have gained anything.


Preservation of context-free languages under prefix and suffix elimination Let $\Sigma=\{0,1\}$ be our alphabet. Let $L$ be some context-free language, which is known to start and end with 0's, meaning that every word $x$ in $L$ has a form $x=0y0$. Let $M$ be a language obtained from $L$ by deleting one starting and one ending $0$, $L=0 \cdot M \cdot 0$.

My question:

Is $M$ still context-free? It seems yes, however I can't prove it. I have tried to construct a push down automaton for $M$ from that of $L$. However, starting $0$ seems to give possibly infinite amount of configurations. So I don't know what to do.

If this question appeared somewhere, I would be grateful if you could provide a reference or a link.
Thanks.

I answer for the case that an arbitrary number of leading or trailing $0$ can be deleted. This supposes that your $L=0M0$ is wrong; it would mean that all words in $L$ start and end with $0$. Since the rest of your question does ot seem to imply this and since that case would be rather trivial, I ignore this equation and answer what I understand from the rest of the question.

You are right. There is no bound on the number of 0 in the beginning, and each one of them can put something on the stack. Thus there is an infinite number of possible stack configurations that can be reached after reading them.

My idea is this: essentially we replace the transitions that read $0$ by ones that read the empty string $\lambda$. The problems are now that $0$ inside $M$ must still be read and that the $\lambda$-transitions could be executed inside $M$, too.

Therefore we make three copies of the sets of states and transitions. In the first one we replace input $0$s  by $\lambda$ in all transitions. All transitions reading an input different from $0$ lead to the corresponding state in the second copy of the state set.

The second set works like the original PDA reading the word from $M$. For every transition that reads $0$ we add a copy that leads to the corresponding state in the third set; these amount to guesses that the current $0$ starts a final block of only $0$.

The third set works much like the first (reading $\lambda$ instead of $0$), only for inputs other than $0$ it rejects.

For the $L=0M0$ case you can adapt this contruction as follows: all the new $\lambda$-transitions from the first set lead immediately to states of the second set. In this way only one leading $0$ is simulated. For the termination: go to a special final state after simulating the read of one $0$.


Rounds in communication complexity - definition What does rounds in communication complexity mean in setting of deterministic/non-deterministic $2$ party communication or multi party setting?

Is it number of bits exchanged between players participating/involved?

In multiparty setting what does simultaneous and non-simultaneous messaging means? Is it related to round?

The notion of round should be quite similar to the intuitive idea of  "one step of the protocol". At any round you are allowed to send 1 message (of any size) and/or receive one message. The message you send at round $i$ may depend on all the information you have up to round $i$, but it cannot depend on the message you receive at round $i$ (or later). It follows that any information that depends on the the message you receive at round $i$ may be sent only at round $\ge i+1$. This sequentiality is the core of splitting into rounds, they just formulate the causality of the protocol

Since the above doesn't determine the size of each message sent, one can define the communication complexity to be exactly the number of bits communicated throughout.

As for simultaneous transmission of messages:
In the above informal description I wrote:

  At any round you are allowed to send 1 message (of any size) and/or receive one message.

note the and/or part. If simultaneous transmission is allowed, then each party sends a message and receives one. If no simultaneous messages allowed, then the party either sends or receives a message, but not both. This makes the partitioning to rounds more crisp: every time the sender party changes, it is a new round.

finally, I repeat the recommendation of @hengxin, and refer you to the book of Kushilevitz and Nissan.


Is this correct : whether or not a type 3 grammar generates $\Sigma^*$ is not c.e An example from Sipser's book, Introduction to the Theory of Computation, shows that it is not decidable for a $TM$ to recognize whether a $CFG$ (or a type 2 grammar) generates $\Sigma^*$, where $\Sigma$ is the alphabet. Call this language $CFG_{all}$

But the above language is also not computably enumerable.  There can be a reduction from $CFG_{all}$ to $\bar{A_{TM}}$, where $\bar{A_{TM}}$ is the language s.t. the input $TM$ does not accept any input. $\bar{A_{TM}}$ is not computably enumerable.

But could we say that whether or not a type 3 grammar generates $\Sigma^*$ is also not c.e. ? (since type 3 grammars are a subset of context-free grammars). While it is true that a finite automaton can recognize $\Sigma^*$, this language is different right from whether a type 3 grammar generates $\Sigma^*$?

Just to clarify the source of my confusion, in summary, it is decidable for a $TM$ to decide whether a pushdown automaton recognizes $\Sigma^*$ or accepts any input, but it is not decidable or even computably enumerable for a $TM$ to recognize that a CFG generates $\Sigma^*$. Similarly, it is decidable for a $TM$ to check if a finite automaton accepts $\Sigma^*$, but it may not be decidable for a $TM$ to check if a type 3 grammar generates $\Sigma^*$. It's somehow the difference between recognizing and generating.

EDIT: apparently for a pushdown automaton to recognize $\Sigma^*$ is not decidable

To see if a type 3 grammar (regular) generates $\Sigma^*$ just build the minimal DFA accepting the language, and check if it is just initial = final state, with loop on all symbols. All constructions involved are effective.


Virtual address translation I'm in an OS class now. I've been wrestling this problem for a while and can't convince myself of a solution. My professor is very busy and hasn't made time to help. Also, this question is from an example exam, not something I would be graded on.
In this question, we're given a virtual address to translate: 0xFEC. We're also told to use segmentation in accordance with the table and a 14-bit address. Looking at our address in binary, we have 0000 1111 1110 1100. We'll disregard the two most significant bits, as instructed giving 00 1111 1110 1100.
Taking the two leading bits as our segment tells us to use the base for the Code section, which is given to be 12. Then, we go to decimal and add.
dec(00 1111 1110 1100) + dec(12K) = ...
7018 + 12,288 = 19306
The thing that tells me this is incorrect, is that the number 7018 which is approximately 7K is much greater than 3.6K (the given size of the code section). :/
I'm really lost here, and I haven't found any examples of people moving addresses with segmentation or with decimal end numbers.
I think I'm wrong when interpreting the addition, but I'm not sure how.

I suspect that the problem may lie in your title.

There's a whole lot of real-world variety imaginable in memory architectures, and your book will describe them in the abstract. Importantly, in the real world the particular combination of segmentation and virtual addresses is not used. Intel's x86 architecture supports it, but most Operating Systems don't bother and just set all segments to be identical.

This question therefore does assume something non-standard, which means there needs to be some specification of how the hypothetical mechanism works. Importantly, does segmentation happen before or after virtual address translation?

In the model where segmentation checks happen first, 0x0FEC is not in the code segment. The top bits suggest it is, but the code segment is only 3686 bytes, not 4077 bytes.

Since the virtual address does not lie in any segment, using it would fail even before a virtual-to-physical translation happens.

Now in the model where segment bounds are checked later, you'd first create a physical address, which would use the 12K base address and the 4076 offset. This produces an physical address of almost 16K, past the 15.6K end of the code segment.


How to use the concept of loop invariant to reduce errors in loops? Most of time while writing loops I usually write wrong boundary conditions(eg: wrong outcome) or my assumptions about loop terminations are wrong(eg: infinitely running loop). Here is an small example where I got stuck several times, the example is a sub problem that I skinned out for solving insertion sort algorithm.

/**
 * Inserts the given value in proper position in the array.
 * @param array
 * @param rightIndex The index till which sub array is sorted.
 * @param value The value to be inserted into sorted sub array.
 */
function insert(array, rightIndex, value) {
    // assert sorted(array, rightIndex)
    for(var j = rightIndex; j >= 0 && array[j] > value; j--) {
        array[j + 1] = array[j];
    }
    array[j + 1] = value;
    // assert sorted(array, rightIndex+1)
};

The mistakes that I did initially were:

Instead of j >= 0 I kept it j > 0.
Got confused whether array[j+1] = value or array[j] = value.

That time I don't have any tool to verify where I am doing wrong, fortunately on Googling I came to know about loop invariants.

To get hold of the above concept I thought to apply the concept here, although I am not mathematician but trying some equation I thought this
would be good invariant.

$$array[0...j] <= val < array[j+2...rightIndex+1]$$

As far as I understood the concept, its a loop invariant because the inequalities contains the loop variable j. How to utilize this equation here?

Being naive at this concept I am stuck and don't know how to use this invariant in my loop. How to gain confidence about the correctness of my loop?

I'm not terribly familiar with the topic, and as such let's discuss a simpler
variation of your problem. In particular, rather than consider a sorted subarray,
let's suppose our function is given a sorted array instead.

So we are given a value e and a sorted array a[0..r], and our goal
is to have the array a[0..r+1] sorted after insertion of e. For reference, let us
introduce some abbreviations.

$$ Sorted \; a[m..n] ∶≡ (∀ i : m..n • aᵢ ≤ aᵢ₊₁) $$

Now our program has precondition and post-condition

Pre : Sorted a[0..r] ∧ a = A₀
Pos : Sorted a[0..r+1] ∧ e ∈ a[0..r+1] ∧ a is a permutation of A₀ with e inserted

The A₀ is used to make sure that no elements of a are deleted or rewritten;
indeed, setting all elements of the array to e gives us a sorted array that contains
e! But we can simplify matters by simply putting a constraint on the code:
only array swaps are allowed.

Pre : Sorted a[0..r]
Pos : Sorted a[0..r+1] ∧ e ∈ a[0..r+1]

Now a usual way to obtain an invariant from the post-condition is to replace a constant with
a variable and adding an equality to regain the post-condition, so let's try replacing 0 in Pos with j
and add an equality for the two:

Sorted a[j..r+1] ∧ e ∈ a[j..r+1] ∧ j ≈ 0

This clearly establishes the post-condition, so we're on the right track!
Let's simplify it further by breaking the equality up:

Sorted a[j..r+1] ∧ e ∈ a[j..r+1] ∧ j ≤ 0 ∧ 0 ≤ j

Now half of this is easily made-true by taking j ≔ r+1 and aᵣ₊₁ ≔ e
---since Sorted a[r+1..r+1] ≡ aᵣ₊₁ ≤ aᵣ₊₁ and e ∈ a[r+1..r+1] ≡ aᵣ₊₁ ≈ e---
and thus this half we take to be the invariant

P : Sorted a[j..r+1] ∧ e ∈ a[j..r+1] ∧ 0 ≤ j

and the rest we take to be the negation of the loop guard, and so our loop has condition

B : 0 ≤ j - 1

Summarizing so far:
if our loop has guard B and invariant P, then if the loop terminates we must have
the guard is false and the invariant still holds, ie
$Sorted\; a[j..r+1] ∧ e ∈ a[j..r+1] ∧ j ≤ 0 ∧ 0 ≤ j$, and from this the post-condition is
established!

To continue the derivation of our program, we need to the loop (whatever it is, since we have
not yet found it) to terminate, since the above summary said if the loop terminates.
The guard gives us that j is a positive value and so a good
candidate for a bound on the number of iterations in the loop.
It can be decreased by each iteration of the loop by incrementing it, j ≔ j -1, and so that is what we try do.

Of course the invariant, by definition, must be left-true by the body of the loop.
In particular, assuming the invariant and the guard, we must show that the invariant still holds
after execution of the proposed loop-body j ≔ j -1.

  P still holds after execution of j ≔ j - 1
≡⟨ definitions ⟩
  Sorted a[j-1..r+1] ∧ e ∈ a[j-1..r+1] ∧ 0 ≤ j-1
≡⟨ 0 ≤ j - 1 follows from B ⟩
  Sorted a[j-1..r+1] ∧ e ∈ a[j-1..r+1]
≡⟨ e ∈ a[j-1..r+1] ≡ e ≈ aⱼ₋₁ ∨ e ∈ a[j..r+1], and this follows from P ⟩
  Sorted a[j-1..r+1]
≡⟨ By P we know that Sorted a[j..r+1],
   so a[j-1..r+1] is sorted precisely when aⱼ₋₁ ≤ aⱼ ⟩
  aⱼ₋₁ ≤ aⱼ

So we need the decrement to be guarded by this condition.
But what if this condition does not hold; ie instead we have aⱼ < aⱼ₋₁?
Then we can obtain the needed condition by swapping the indices and so
the loop body becomes

if aⱼ < aⱼ₋₁ then swap(j, j-1);
j ≔ j-1;

So we've obtain a terminating loop and so our summary above means we are done.
So the resulting program is:

j ≔ r+1;
aᵣ₊₁ ≔ e;
while 0 ≤ j - 1:
   if aⱼ < aⱼ₋₁ then swap(j, j-1);
   j ≔ j - 1

That is,

aᵣ₊₁ ≔ e;
for(int j = 0; 0 < j; j--)
   if aⱼ < aⱼ₋₁ then swap(j, j-1);

Let's try it out.

Given sorted array a = [1,2,3,4,5] and value e = 3
we get $r = 5$ and so, letting | denote where we are looking
in the array, the loop looks as follows:

j  a
6  [1,2,3,4,5 | 3]
5  [1,2,3,4 | 3,5]
4  [1,2,3| 3,4,5]
3  [1,2| 3,3,4,5]
2  [1| 2,3,3,4,5]
1  [|1, 2,3,3,4,5]

In particular, note that since the array is initially sorted, the moment
we stop making swaps we no longer make any swaps at all and just decrement
the counter. With this mind, we can be a bit perverse (for the sake of efficiency?)
and write

aᵣ₊₁ ≔ e;
for(int j = 0; 0 < j; j--)
   if aⱼ < aⱼ₋₁ then swap(j, j-1) else return;

Hope this helps!


Minimum number of givens for General Sudoku of size $n^2 \times n^2$ Here, it is well known that the minimal number of givens for a size $9 \times 9$ board of Sudoku requires 17 "givens" in order to be solved (i.e., no puzzle can be solved with $\le 16$ givens).

What is the minimal number of givens for a size $n^2 \times n^2$ board? Is there a table of "best-known" minimal values?

I'm speculating that there is only an asymptotic/approximate bound as the $n=3$ case was not known, let alone higher values of $n$. For $n=4$, the best-known is 55, and $n=5$ is 151.

The minimum number of clues for a puzzle of $n^2$ x $n^2$ is known for $n = 2$ (4 x 4 Sudoku), of which the minimum clues is 4 (25% of cells filled). There are 13 such non-equivalent puzzles. (based on info at "enjoysudoku.com").

The minimum number of clues for a puzzle of $n^2$ x $n^2$ is also known for $n = 3$ (9 x 9 Sudoku), of which the minimum clues is 17 (about 21.0% of cells filled). About 49,000 such non-equivalent Sudokus have been discovered.

For $n = 4$ (16 x 16), the fewest clues known in any puzzle is 55 (about 21.5% of cells filled), but it is not known if this is the fewest possible. (based on info at "enjoysudoku.com").

For $n = 5$ (25 x 25), little work has also been done to find the fewest clues possible, and comparatively few Sudokus of this size have been constructed. One 25 x 25 Sudoku is known to have 328 clues. So from a cursory study, the fewest clues for (n=5) is 328 or fewer (about 52% or fewer cells filled). Note: this Sudoku was not an attempt to be an example with few clues. I listed it only to provide an initial upper bound.


Create a PDA that accepts the following language I need to create a PDA that accepts by empty stack and accepts the language formed by strings over the alphabet $\{a, b\}$ of the form: $uw$, where $w$ is the string $u$ reversed and doubled. So, for example, if $u=ab$ then $w=bbaa$ (the $ab$ is reversed then its characters are doubled).
Examples of strings in the language: $\epsilon$, $aaa$, $baaabb$, $abbbbbbaa$, etc.
I'm really struggling with setting up a PDA that satisfies the criteria. Any help is appreciated.

The PDA operates as follows :

Push the symbols you read to the stack

Non-deterministically guess when u ends and w starts

Now for the rest of the string , we consider 2 symbols by 2 symbols , if the 2 symbols are not the same reject , if the 2 symbols are the same , compare them to top of stack , if they are not the same symbol reject , if they are the same pop the stack

After reading the entire input , if the stack is empty accept , else reject

Ex : s = ab bbaa , we push a,b to stack , then we guess u ends and w starts , now we read  b , then b , both are same symbol , we look at top of stack we have  b we pop the b , now the stack has a , and we will read aa , repeat the above again and we accept
If you get how it works , you may want to try to sketch the PDA
Here is a sketch of the PDA to check your answer  :


Number of digits in a binary product Assume i have 2 numbers in binary form (or, more precisely, assume to know the number of their digits, DF1, DF2):

101010101001010101010101010111111111111111111111010101
10101111111111111111010101

Is there a formula for the exact number of binary digits (DP) of the product?

  DP = F (DF1, DF2)

[I need this, in a practical case, to size a target array]

I assume you want to know the maximum possible bits that a product of two numbers might have. Under that assumption, let the first number $a$ have $m$ bits, and the second number $b$ have $n$ bits.

Then, $$a \leq 2^{m} - 1 $$
Similarly, $$b \leq 2^{n} - 1$$

Then, the product is:
$$a \cdot b \leq 2^{m+n} - 2^m - 2^n + 1$$
Now, both $2^m$ and $2^n$ are greater than $1$ (since $n, m > 0$).
So, $$a \cdot b < 2^{m+n} - 1$$

Therefore, at most $m+n$ bits are sufficient for the product of the two numbers. Of course, lesser bits might suffice. Also, the sign bit is not included in the computation, and each of $a$, $b$, and $a \cdot b$ might have a separate sign bit.

If you really need to optimize on space, you can check $a$ and $b$ for special cases. Some cases could be:

$a$ or $b$ is $0$: You need 1 bit
$a$ or $b$ is $1$: You need as many bits as the other number
One of the numbers is a power of $2$: It will contain exactly one $1$, say at position $i$ (LSB is position 0). Then, the multiplication is equivalent to left shifting the other number by $i$ bits.

You might think up other special cases if you really need to.

Edit: As pointed out by Sam in the comments, if you impose the restriction that the most significant bit has to be 1 (unless the number itself is 0), you can get a lower bound too.
Since the MSB is 1, we have:
$$a \geq 2^{m-1}$$ and $$b \geq 2^{n-1}$$.
Thus, $$a \cdot b \geq 2^{m + n - 2} = 2^{(m+n-1) - 1}$$

To represent $2^{(m+n-1)-1}$, you require $m+n-1$ bits, and so to represent $a \cdot b$, you need at least $m+n-1$ bits. This leaves the special case when either of the numbers is $0$, and assumes there are no leading 0's in any of the numbers.

As a conclusion, if you know the number of binary digits/bits of your number (as you mention in your question), you are most likely implying that there are no leading $0$'s and the left-most bit is $1$ (exception being when the number itself is 0, where you can simply assign 1 bit for the resulting product). In such a scenario, the product will have either $m+n$ bits or $m+n-1$ bits.


How to show that the language made up of strings with nlogn 0s is not regular with the pumping lemma? How to show that the following language is not regular with the pumping lemma?

$$L=\left\{0^{n\lceil\log_2 n\rceil} \,\middle|\, n\in \mathbb{N}-\{0\}\right\}.$$

(Dense-length lemma for regular languages) Let $R$ be an regular language that has infinitely many words. Then there exists a number $d$ such that for any word in $R$, there is another word such that the difference of the lengths of both words is less than $d$.

The above lemma says, basically, the lengths of words in a regular language cannot be too sparse anywhere. It can be proved easily using the pumping lemma for regular languages.

Let us take a look at $L$. The lengths of its word are $\{n\lceil\log_2 n\rceil \,\mid n\in \Bbb{N}-\{0\}\}$. When $n$ goes larger and larger, the lengths become sparser and sparser because of the factor $\lceil\log_2n\rceil$. In fact, if $n>2^d$, $m>2^d$ and $n\not=m$, then $\left|n\lceil\log_2n\rceil-m\lceil\log_2m\rceil\right| > d$. So $L$ cannot be regular because of the above lemma.

Exercise 1. Prove the dense-length lemma for regular languages.

Exercise 2. Prove the dense-length lemma also holds for context-free languages that have infinitely many words.

Exercise 3. Does the dense-length lemma hold for context-sensitive languages?


Closed-form solution to recurrence equation I have a recurrence relation of the form:

$f(0) = f(1) = 1, f(2) = 2$ (initial conditions).

$f(2n) = f(n+1) + f(n) + n$ for $n>1$.

$f(2n+1) = f(n) + f(n-1) + 1$ for $n>1$.

I have been able to simplify this equation a little bit, but I can't seem to find a closed-form solution (and neither can Mathematica with RSolve).

The first few values of $f(n)$ for $n = 0$ to $10$ are:

[1, 1, 2, 3, 7, 4, 13, 6, 15, 11, 22]

Define
$$
\begin{align*}
A(x) &= \frac{1}{x^2} + 1 + x + x^3, \\
B(x) &= \frac{x^3}{1-x^2} + \frac{x^2}{(1-x^2)^2} - \frac{1}{x^2} - 1 - 2x^2 \\ &=
-\frac{1}{x^2} -1 - x^2 + \sum_{m=0}^\infty x^{3+2m} + \sum_{m=0}^\infty (2+m) x^{4+2m}.
\end{align*}
$$
Then the generating series $F(x) = \sum_{n=0}^\infty f(n) x^n$ satisfies the identity
$$ F(x) = A(x) F(x^2) + B(x), $$
and so in some sense is given by the "formula"
$$
F(x) = B(x) + A(x) B(x^2) + A(x) A(x^2) B(x^4) + A(x) A(x^2) A(x^4) B(x^8) + \cdots.
$$
Unfortunately, this formula holds only in the sense of analytic continuation.

If we use Dirichlet series instead of ordinary generating series, we can probably compute the asymptotics of the sequence, along the lines described here. We leave that as an exercise to the reader.


Decidability of whether CFL = RL Let L1 be a language generated by a CFG.
Let L2 be a language generated by a regular grammar.
Is L1 = L2 ?

Is the above problem decidable or undecidable ?

If L1 = L2 then L1 $\cap$ L2' = $\phi$

So the above problem can be written as

CFL $\cap$ RL = $\phi$ or CFL = $\phi$ which is decidable.

So the answer should be decidable according to me but my professor marked it wrong saying it's undecidable

Where am I going wrong ?

If $L_1 = L_2$ then $L_1 \cap \overline{L_2} = \emptyset$

While that is true, the reverse is false. The right-hand side is also true if $L_2 \supsetneq L_2$. Therefore, deciding the right-hand side does not solve equality.


Solutions to Diophantine Equations using a Min Heap I've recently come across this problem:

  Find all solutions to the equation $a + 2b^2 = 3c^3 + 4d^4$ for which $a, b, c, d$ are all less than $100,000$.
  Hint: use one min-heap and one max-heap.

I can think of an algorithm involving two min-heaps (one for the LHS and one for the RHS), but can't figure out how a max-heap can be used. It needs to be efficient.

How could a max-heap be incorporated?

A min-heap with entries $x_i$ is equivalent to a max-heap with entries $-x_i$ (or more generally, $A - Bx_i$ for any $B > 0$, or even more generally, $\phi(x_i)$ for any monotone decreasing $\phi$). So you can convert your solution with two min-heaps to a solution with one min-heap and one max-heap, as well as to a solution with two max-heaps.


How can I compare two different neural networks, from a theorical point of view? Let's say I have a problem (i.e. Given f(x), find x) and two neural networks(i.e. feedforward and recurrent). I would like to know if one works better than the other one. I could run the twos on a computer, but other programs might interfere and I wouldn't know if the implementations I'm running are really the best ones humankind could create. Moreover, how could I be sure that the feedforward network worked better than the recurrent, when it might have just been "lucky"?

So, here is the question: can I compare the efficiency of two neural networks(with known sizes, structures and functions) from a theorical point of view? And if the answer is yes, how?

Thank you in advance.

Essentially, no.  The only way to know which neural network is going to give you better accuracy is to try them on a realistic data set.  The theory we have is not well-enough developed to allow us to reliably predict which will do better on a particular data set.

A secondary remark.  When you remark "other programs might interfere", that's not correct.  Even if other programs are running (on a multi-tasking machine), they won't affect the accuracy.  They might take the process of running or training the neural network on your data set take longer, but they won't affect the results.


Emulating equal operator using multiplication I have two values $A$ and $B$, I want to know if I can implement the equals $=$ operation as the product of the two values. I can apply any function to $A$ and any function to $B$, but I need to use multiplication at the end.

Basically I want to find $f$ and $g$, such that:

$$ f(A) \cdot g(B) = \begin{cases}
1, & A = B \\
0, & A \ne B
\end{cases} $$

For example, if I use $g(x) = 1/x$ I get something close to what I want
$$ A \cdot 1/B = \begin{cases}
1, & A = B \\
A/B, & A \ne B
\end{cases} $$
Is it possible to do that? If so, what are the functions $f$ and $g$ that I should use?

Suppose that $f,g$ were functions satisfying $f(A) g(A) = 1$ and $f(A) g(B) = 0$ if $A \neq B$. Take any $A \neq B$. Then $f(A) g(B) = 0$, and so either $f(A) = 0$ or $g(B) = 0$. If $f(A) = 0$ then $f(A) g(A) = 0$, and if $g(B) = 0$ then $f(B) g(B) = 0$. So no such functions exist.


Prove that the language is not regular without using Pumping Lemma I am practising problems on Regular Languages and I came across this question:

  Prove that the language $$\{a^m b^n : m ≥ 0, n ≥ 0, m \ne n\}$$ is not
  regular. (Using the pumping lemma for this one is a bit tricky. You
  can avoid using the pumping lemma by combining results about the
  closure under regular operations.)

I have tried to prove it using pumping lemma in the following way:
Let p be a sufficiently large integer, then we construct the string:
$$s = a^pb^{p + p!}$$
Now by pumping lemma conditions, the string $s$ can be written as $xyz$ where $|xy| \le p$. Hence $xy$ contains only $a$'s.
If we choose any substring $y$ of length $k \le p$ from $xy$, we can always find a $C$ such that
$$p+C*k = p + p!$$

We can also prove it if we choose $s$ to be just the single character string $a$ and then we pump down.

Q1. Please let me know if there is a flaw in the above proofs.
Q2. How can closure properties be applied to prove the above? Till now I have applied closure properties to prove regularity, but never the converse.

1) your proof is correct (and nice).

2)They could mean prove that the complement is not regular (this is a classic result, and the proof is simpler). More generally, if you saw in course some languages that are not regular, you can probably reduce one of them to this one by closure operations.

Another technique without pumping lemma is to show that the number of Myhill-Nerode equivalence classes is infinite.


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

I thought of it this way, since f(n) is Ω(n),then f(n) belongs to the set of functions defined by Ω(n), ie,{n,$n^2$,$n^3$ ....}.  So g(n) will change accordingly , ie , g(n) will be of complexity O(n),O($n^2$),O($n^3$) ...etc. Is it correct to directly substitute functional values into O(f(n)) to get a sense of the complexity?

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


When scheduling intervals across multiple resources, why sort? I am reading this book and am at a point when the Interval Partitioning Problem is discussed. The pseudocode they provide for it is the following:

Sort the intervals by their start times, breaking ties arbitrarily
Let I_1, I_2, ..., I_n denote the intervals in this order
For j = 1, 2, 3, ..., n
    For each interval I_i that precedes I_j in sorted order and overlaps it
        Exclude the label of I_i from consideration for I_j
    Endfor
    If there is any label from {1, 2, ..., d} that has not been excluded then
        Assign a nonexcluded label to I_j
    Else
        Leave I_j unlabeled
    Endif
Endfor

Here n is the number of intervals and d is the depth of the intervals (the maximum number of overlapping intervals)

What I don't understand is why sort the intervals in the first place. I think the algorithm would work even without this step. In other words, it would work no matter the order of I_1, I_2, ..., I_n. Am I correct? Is there something I am missing?

EDIT: Doesn't the algorithm below also produce an interval partitioning, but with the advantage of being faster because no sorting is performed?

Let I_1, I_2, ..., I_n be an arbitrary ordering of the intervals.
For j = 1, 2, ..., n
    For each interval I_i where 1 <= i < j which overlaps with I_j
        Exclude the label of I_i from consideration for I_j
    Endfor
    If there is any label from {1, 2, ..., d} that has not been excluded then
        Assign a nonexcluded label to I_j
    Else
        Leave I_j unlabeled
    Endif
Endfor

Why sorting? One reason is efficiency: the algorithm can easily be improved to run in time $O(nd + n \log n)$ instead of $O(n^2)$. The other reason is that it is not immediately clear (at least not to me) what label to assign to intervals when processing them out of order: you may get yourself stuck later on.

Here is why it's faster: By iterating over the intervals in order of increasing start time, we can limit the inner for-loop to d iterations. Since all intervals that precede I_j have already been considered in an iteration of the outer for-loop before the current iteration, we know these intervals are already 'scheduled': they have a label assigned to them. Since there are only d labels, there are only d intervals (namely the latest for each label) that can possibly overlap with I_j. The inner for-loop only needs to look at these d intervals for each iteration of the outer for-loop, resulting in a total running time of $O(nd)$ after sorting ($O(n \log n)$ time).

The line For each interval I_i that precedes I_j in sorted order and overlaps it does not clearly capture this. Instead the algorithm should keep track of the set of intervals containing for each label the most recently encountered interval labelled as such. The inner for-loop should iterate over this set, containing only $d$ intervals.
Your second algorithm in it's current form is not correct, in that it does not always find an optimal solution. Consider the three intervals $\{(1,2),(3,4),(1,4)\}$ which can be partitioned in two sets of pairwise disjoint intervals: $\{(1,2),(3,4)\}$ and $\{(1,4)\}$, i.e. the algorithm should find a label for all intervals when $d=2$. When your second algorithm takes these intervals in order $\langle(1,2),(3,4),(1,4)\rangle$ it may do the following:

For interval $(1,2)$ labels 1 and 2 are available (none of the preceding intervals overlap, because there are no preceding intervals). We choose label 1.
For interval $(3,4)$ labels 1 and 2 are available (none of the preceding intervals ($\{(1,2)\}$) overlap). We choose label 2.
For interval $(1,4)$ all preceding intervals overlap, no labels are available. The algorithm fails to label this interval.


Why don't hard drives actually delete data? As far as I understand it, when you delete a file from trash/recycle bin the file isn't actually erased from memory but is instead marked as being okay to be over written.

So, my question is as to why this is the case. Is it simply for speed/convenience reasons or is actually deleting data just a much harder (or impossible) thing to do?

I ask because of the potential security vulnerabilities, such as reselling older hardware and etc.

There are two possible criticisms here, which should actually be leveled at the operating system, more accurately the file system:

Why does the OS not superficially erase data when a file is erased?
Why does the OS not thoroughly erase data when a file is erased?

Regarding point 1, historically speaking, you don't want to do this, since you might change your mind later on, and this way the data is still there. Of course, modern operating systems which have a recycle bin (some of them, say Linux and OS X, only implement this on their GUI) don't really benefit from this advantage. Rather, one reason you don't want to erase data superficially is that it is still possible to recover the data, say using lab analysis. Perhaps this is even feasible by reading the location many times and measuring the amount of errors. However, there is still something to gain here: malicious software would have a much harder time reading your data even if it is just erased superficially.

Regarding point 2, if you rigorously erased the data each time a file is erased, then you will probably shorten your hard drive's life. In addition, deletion would become a slow operation, which may hurt performance when many temporary files are created, a technique which had been common in the past.

If you really care about erasing your data before reselling older hardware, you can obtain software that will thoroughly erase the data and thus make it much harder to recover. If you're afraid that your hard drive, containing sensitive information, could be stolen at any point, then you should erase your sensitive data using the same kind of software.

It remains to consider the casual user who is worried about malicious software reading erased files. Such a user could benefit from superficial erasure of files. I am not aware of any file system providing this service.

If you're not using an actual hard drive but some other storage device, you might encounter other difficulties, check out this question on askubuntu.

As a workaround, and as suggested by the answers to the aforementioned question, you can encrypt your hard drive instead.


AVL tree such that each insert causes rotation (single or double) Could you give me an example of an AVL tree for which inserting an element at an arbitrary (i.e. every) position causes a rotation (double or single)?

I have tried to come up with an example, but I didn't manage to.

Short answer: it depends.

The answer depends on what is the set of the possible elements of the AVL tree.

Natural numbers, no duplicates allowed.

Yes, there is an AVL tree requiring a rotation on the next insertion, whatever that is:

      1
     / \
    0   3
       / \
      2   4

The next insertion has to be a natural $\geq 5$ and cause a rotation.

Similarly,

      0
       \
        1

will rotate as soon as any natural (which has to be $\geq 2$) is inserted.

Integer numbers, no duplicates allowed.

Yes, there is an AVL tree requiring a rotation on the next insertion:

      0
     / \
   -1   1
   /     \
 -2       2

The next insertion has to be $\leq -3$ or $\geq 3$.

Rational numbers, real numbers, strings.

No, there is no AVL tree requiring a rotation on the next insertion. We now prove this claim.

These sets satisfy the following property, which we now assume.

Assumption. Let $V$ be the set of the possible elements of the AVL tree. Given any two $x,y \in V$, with $x < y$, there exists $z \in V$ satisfying $x < z < y$.

Proposition. For every $n$, any AVL tree having height $n$ admits at least one insertion requiring no rotations (a simple insertion).

Proof. We proceed by induction on $n$.

For $n \leq 1$, it is trivial.

By the induction hypothesis, assume every AVL tree with height $< n$ admits a simple insertion. Take $T$ to be any tree with height $n$, and name $S,U$ its immediate subtrees. W.l.o.g., assume $height(S) \leq height(U) = n - 1 < n$ (otherwise, swap $S,U$). Hence, $S$ admits a simple insertion $p$.

Modify $p$ so to ensure that, once inserted into $T$, it is inserted into the $S$ side. This is trivial if $p$ falls "inside" the elements of $S$. If instead it is the new minimum/maximum of $S$, make sure it is larger/smaller than the root of $T$, exploiting our assumption above.

Hence, performing an insertion of $p$ into $T$ can not cause any rotation inside the $S$ subtree. Further, it can not cause a rotation around the root of $T$, since this insertion can increase $height(S)$ at most by one, so the AVL invariant $|height(S) - height(T)|\leq 1$ still holds. Hence, there is a simple insertion in $T$.

QED.

Duplicates allowed.

The above proof also holds when duplicates are allowed. In that case, one can insert a duplicate of the root of $T$ in either side.


Does every Partially Ordered relation and its dual have the same number of topological orderings? Given the Hasse Diagram of a Partially Ordered Relation, is it the case that both the POSET itself and its dual POSET have the same number of topological orderings? I have tried a few examples, and although it does seem to be the case, I need a formal way of proving the same. So please help me with this.

Is it the case that both the poset and its dual poset have the same number of topological orderings?

Yes, you have observed/discovered a fact about partially ordered set (poset). In fact, there is a stronger and more pleasing fact, which is a special case of the duality of order theory.

The dual order of a topological ordering of a poset is a topological order of the dual order of that poset.

Given a poset $p$, let $p^{d}$ be the dual order of $p$.  Let $p\rightarrowtail$q mean $q$ is a topological ordering of $p$. Then the above claim can be expressed as

$$ p\rightarrowtail q\ \Leftrightarrow p^d \rightarrowtail q^d$$

Proof: All we need to do is to follow the definitions. Let the underlying set of $p$ be $S$, which is also the underlying set of $q$, $p^d$ and $q^d$. For a poset $p$, we use "$\preceq_p$" to denote the binary relation on of $p$ $S\times S$.

"$\Rightarrow$":

Let $s_1,s_2\in S$ such that $s_1\preceq_{p^d} s_2$. Then by the definition of the dual order, $s_2\preceq_{p} s_1$. By the definition of a topological sort, $s_2\preceq_{q} s_1$. By the definition of the dual order, $s_1\preceq_{q^d}s_2$.
Since $q$ is a total order, so is $q^d$.

"$\Leftarrow$":

Let $s_1,s_2\in S$ such that $s_1\preceq_{p} s_2$. Then by the definition of the dual order, $s_2\preceq_{p^d} s_1$. By the definition of a topological sort, $s_2\preceq_{q^d} s_1$. By the definition of the dual order, $s_1\preceq_{q}s_2$.
Since $q^d$ is a total order, so is ${(q^d)}^d=q$.

In fact, the implication "$\Leftarrow$" is the dual of the implication "$\Rightarrow$". Replacing $p$ by $p^d$ and $q$ by $q^d$ in the implication "$\Rightarrow$", we get "$\Leftarrow$".

Q.E.D.

The claim above shows that given a poset $p$, whenever we can construct a topological order $q$ for $p$, we also have $q^d$, a topological order for $q^d$.
Hence $q\to q^d$ maps the topological orders of $p$ to the topological orders of $p^d$.

Similarly, whenever we can construct a topological order $r$ for $p^d$, we also have $r^d$, a topological order for ${(p^d)}^d=p$.

The map $q\to q^d$ and $r\to r^d$ are inverse functions to each other. So, each map is, in fact, a one-one correspondence. So the number of topological orderings of $p$ equals the number of the topological orderings of $p^d$.

Be careful that the topological orders of the original poset $p$ and its dual $p^d$ might not be same, although they are dual to each other.

For example, we can check the poset $p=\{a,b,c\}$ with $a\preceq_p b$ and $a\preceq_p c$. All topological orders of $p$ shares the unique least element $a$ but don't share greatest elements. All topological orders of $p^d$ shares the unique greatest element $a$ but don't share least elements.

Exercise. A poset is connected if the directed graph representing the poset is connected. Show that the maximum number of topological orderings of a connected poset of $n$ vertices is $(n-1)!$.


How to measure the complexity of the discrete logarithm problem? The answers to this question on Crypto Stack Exchange basically says that, to measure the complexity of the logarithm problem, we have to take the length of the number representing the size of the group into account. It seems arbitrary, why don't we chose the size of the group as the argument? Is there a criterion to know what argument to chose? In fact, I know I overlooked something important since the complexity changes hugely if we do it by the size of the group.

It doesn't matter whether you choose the size of the group $|G|$ or the size of the integer representing it $n$ as a parameter, since $n \approx \log |G|$. There are two reasons that usually the complexity is described in terms of $n$ rather than $|G|$:

$n$ is the length of the input (more accurately, the input has length $\Theta(n)$), and we usually measure the complexity of algorithms as a function of the input length.
Usually $n$ is a small number such as $1024$, whereas $|G|$ is a huge number such as (roughly) $2^{1024}$.


Confused b/w non-deterministic finite state automata vs finite state automata I am reading this example of FSA from book Martin & Jurafsky "Speech and Language Processing".

As per definition of FSA you can only transition to one state after consuming one input. In this example if the input is say "twenty" to which state it will transition q2 or q1 ?
Say if the input was "twenty one". After consuming first string which state it will transition to?

The automaton in the image is indeed nondeterministic.

You need to think a little differently about nondeterministic machines. It's no longer a question of "what happens when X?" but about "what can happen when X?". For each input, there can be many different computations, even with different outcomes.

Note how the definition of acceptance is different. For DFA, it's "the (unique) computation is accepting"; for NFA, it's "there exists an accepting computation".

Here, in your example, if the input is "twenty", there are two computations:

$q_0 \to q_1$ and
$q_0 \to q_2$.

Since the second is accepting, "twenty" is in the language of this automaton.

Side note: A TCS book that uses twenty as terminal symbol and generally avoids LaTeX for it's mathematics typesetting is highly suspect. I recommend that if you run into any problems, look for a standard textbook before worrying too much.


Counting the number of squares in a graph Given an undirected graph, how would one go about calculating the number of squares in the graph? That is, a square is a cycle of length 4.

I know that it is possible to count the number of triangles (cycles with length 3) in polynomial time. Is it possible to calculate the number of squares in polynomial time as well, and how would one go about doing this?

There is a simple $O(n^4)$-time algorithm which I will let you discover yourself. A better algorithm follows from the following formula for the number of squares:
$$
\operatorname{Tr} (A^4) - \sum_i d_i^2,
$$
where $A$ is the adjacency matrix and $d_i$ is the degree of the $i$th vertex. Using this formula you can compute the number of squares in $O(n^\omega)$, where $\omega < 2.373$ is the matrix multiplication constant.


Can g(n) be same for big O and omega notation for f(n) I have been studying asymptotic notation and I understand that in big O notation $f(n) <=c1*g(n)$ and in omega notation we have $f(n)>= c2*g(n)$ where $c1$ and $c2$ are some constant.

Now I was wondering if the function $g(n)$ here are the same and the big O and omega of $f(n)$ is determined by constants $c1$ and $c2$. Or if the $g(n)$ is different for O and omega.

If $g(n)$ is indeed same can anyone explain with example how is it possible as I can think of the examples in which $g(n)$ is different in both cases.

If you write down $f \in O(g)$ and $f \in \Omega(g)$ then you clearly intend both instances of "$g$" to refer to the same function. Otherwise, it would be pretty confusing.

Note how this is equivalent to $f \in \Theta(g)$.

If, however, you write down $f \in O(n^2)$ and $f \in \Omega(n)$ and want to unfold both the definition of $O$ and $\Omega$, you'll have to instantiate two different "$g$"s. That is, you'd write

$\qquad c_1 g_1(n) \leq f(n) \leq c_2 g_2(n)$

for all $n \geq n_0$ for some $c_1, c_2 > 0$ and $n_0 \geq 0$. Here, we know that $g_1 = n \mapsto n$ and $g_2 = n \mapsto n^2$.


Proving a language is not Semidecidable I have the language $L = \{ \langle M_1, M_2 \rangle : L(M_1) \subset L(M_2)\}$ and I'd like to prove that it is not Semidecidable. To do so, I need to use a reduction from $\neg H$. I cannot use Rice's theorem. I'm having a hard time with this, and would appreciate a walkthrough.

Using contradiction suppose $L=\{\left< M_1,M_2 \right>|L(M_1)\subset L(M_2)\}$ is semi-decidable. So there exists Turing machine $T$ which for input $\left<M_1,M_2\right>$ if $L(M_1)\subset L(M_2)$ will halt and accept.

We should use this Turing machine $T$ to make another Turing machine $T'$ which halt and accept on input $\left<w,M\right>$ if $M$  doesn't accept $w$. To do so, you have to make another Turing machine $M'$ using $w$ that you are sure $w\notin L(M')$. Thus you can give $\left< M',M\right>$ as input to $T$ and look for its output. If it accept it means that $L(M')\subset L(M)$ which means $w\notin L(M)$.


Difference between intended interpretation and extended interpretation in first-order logic I am currently reading "Artificial Intelligence - A modern approach" and I really do not get the difference between intended interpretation and extended interpretation in first-order logic.

Are extended interpretations all possible assignments from a symbol in my knowledge base to an object in the world? And is the intended interpretation the interpretation the "author" of the sentences wanted to have?

So when there is a symbol like "John" in my sentences does that mean that it really refers to the human being John in the real world (if I have intended interpretation).

And the extended interpretation could be: "John" in my sentences refers to the human being Mary in the real world.

Are the extended interpretations a set of all possible interpretations and is the intended interpretation one specific interpretation in this set?

So do I interpret my sentences either intended or extended?

And if I say in my interpretation that John and Mary (as constants) refer to the same object in my model can I unify them then, i.e. UNIFY(John,Mary) = {John/Mary}?

You should only care about intended interpretation.  I don't like the concept of the extended interpretation.  The latter is only included to make precise the concept of quantification, but I think it makes things more confusing instead.

Before understanding what an intended interpretation is, you should really know what a model is, and what a language or signature is.  To follow their example:  A language can be consisting of the constants Richard and John, the predicates (the arity in backets) Brother (2), OnHead (2), Person (1), King (1) and Crown (1).  Finally you have the unary function LeftLeg (1).

That was the language, and though we use words as Brother, this should really impose no meaning, we could just as well have written it A.

A model, on the other hand, or what they call an intended interpretation is a domain, together with *interpretations of the above predicates, constants and functions.  Here's an example:

Domain = { Richard, John, Crown, Dog }
Brother = { (Richard, Crown), (Dog, John) }
OnHead = { (Dog, John), (Richard, Dog), (Crown, Richard) } (the crown' on Richard's head, Richard's on Dog's head, Dog's on John's head)
Person = {John, Dog}
Richard = Richard (oops, heavy overloading!)
John = Dog (oops, heavy overloading!)

I didn't complete the definition, but I hope you get the point.  If you put all those above together as a KB, (Domain, Richard, John, Brother, OnHead, Person, etc...), you get your inteded interpretation.

The extended interpretation you should ignore.  Completely.  At least if you understand what $\forall x P(x)$ means for some first order sentence $P$.  And $\exists x P(x)$.


What are potential pitfalls with having a minimal kernel that runs managed code? Suppose I want to build an operating system based on a very small native lower kernel that acts as a managed code interpreter/runtime and a larger upper kernel compiled to a non-native machine language (Java bytecode, CIL, etc.). Examples of similar operating systems would be Singularity and Cosmos.

What pitfalls and development challenges exist writing an OS with this sort of infrastructure in contrast to a purely-native solution?

Depending on the language, there can be many development challenges:

Pointers: If a language doesn't have pointers, it will be a challenge to do relatively-easy tasks. For example, you can use pointers to write to VGA memory for printing to the screen. However, in a managed language, you will need some kind of "plug" (from C/C++) to do the same.
Assembly: An OS always needs some assembly. Languages like C#, Java, etc. don't work so well with it, unlike C/C++. In C or C++ you can also have inline assembly which is very, very useful for many tasks. There are MANY cases where this is needed (examples in x86): loading a GDT, loading an IDT, enabling paging, setting up IRQs, etc.
Control: If you are using something like Cosmos, you aren't having full control. Cosmos is a micro-kernel and essentially "bootstraps" your "kernel". You can implement something like Cosmos from scratch if you really wanted to, however, that can take a long, long time.
Overhead: With managed languages, there is A LOT of overhead compared to C or even C++. Things like Cosmos need to implement a lot of things before even a C# hello world kernel can be run. In C, you are ready to go, no real setup needed. In C++, there are just a few things that need to be implemented to use some of C++'s features.
Structures: In C/C++ there are structs which many managed languages do not have, and so, you would need to implement some way of having something like a struct. For example, if you want to load a IDT (Interrupt Descriptor Table), in C/C++, you can create a struct (with a packed attribute), and load it using the x86 ASM instruction lidt. In a managed language, this is much harder to do...

Managed languages, syntax-wise, are easier, however, for many OS related things are many times not very-well suited. That doesn't mean they can't be used, however, something like C/C++ are often recommended.


Examples of Dependent Types I'm gathering examples from everything that I've read about Dependent Type Theory mainly from Dependent types at Work paper.

This is my list so far of some dependent types (with abbreviations of mine):

[NVec]: $A^n$ vectors of length n with elements of type $A$
[NMMAtrix]: $A^{m\times n}$ matrices
[Fin]: Finite sets of size $n$
[SList]: Sorted lists
[NBTree]: Height-balanced trees of a certain height
[SBTree]: Sorted binary trees
[PAIR]: A pair of integers where the second is greater than the first

How can I justify that the types from my list are indeed dependent types.
I appreciate another example to add it to my list.

I think it helps to keep in mind the propositions as types mantra. Every type can be read either as a propostion or a set. This gives us two readings (let's just consider types dependent on natural numbers):

A dependent type $P : \mathtt{nat} \to \mathtt{Type}$ is like a family of sets $P(0), P(1), P(2), \ldots$
A dependent type $P : \mathtt{nat} \to \mathtt{Type}$ is a property of natural numbers where we think of $P(n)$ as the proofs that $n$ has property $P$

With this in mind it may be easier to make sense of dependent types. For instance, consider:

$\mathtt{Mat}(n)$: the type of matrices of size $n \times n$
$\mathtt{Less}(a,b)$: the proofs that $a < b$

Then $\mathtt{Mat}(n)$ should be thought of as a collection of sets, one for each $n$, while $\mathtt{Less}(a,b)$ is a relation (a binary predicate) on pairs $(a,b)$.

Your first three examples (NVec, NMMatrix, Fin) are dependen types of the first kind. The other ones are of the second kind.

Strictly speaking, when you say "a pair of integers where teh second is greater than the first", that is not a dependent type but an element of the dependent sum, i.e,

$$\mathtt{PAIR} = \textstyle\sum_{(a,b) : \mathtt{nat} \times \mathtt{nat}} \mathtt{Less}(a,b),$$

i.e., a triple $(a, b, p)$ where $p$ is a proof that $a < b$. Similarly, your NBtree and SBTree examples are really dependent sums of the form $\sum_{t : \mathtt{Tree}} P(t)$, not dependent types. The sums of course use dependent types $P(t) = \text{"proofs that the tree $t$ is height-balanced"}$ and $P(t) = \text{"proofs that the tree $t$ is sorted"}$.


what does "vector" mean in computer science? I am trying to understand how computers work under the hood, and I came across following sentence.

"Computer technology is based on electronic circuits able to process vectors of 0's and 1's. For that reason all data are encoded by strings of 0's and 1's."

So does the vector mean normal string/number 0 and 1?

Thank you

Vector here is essentially the same as string, sequence, or array, with the possible connotation of having fixed length.

Here is another way to express the same idea:

  Computer hardware operates on bits. Therefore we have to encode all data in bits before a computer can process it.


Is this grammar right associative (why?) Given a grammar as follows:

$\left<stmt\right> \rightarrow \left<id\right> = \left<expr\right>$

$\left<const\right> \rightarrow A | B$

$\left<expr\right> \rightarrow \left<term\right> \times \left<expr\right> | \left<term\right>$

$\left<term\right> \rightarrow \left<factor\right> + \left<term\right> | \left<factor\right>$

$\left<factor\right> \rightarrow (\left<expr\right>) | \left<id\right>$

I think this grammar is right associative because it expands on the right. Where I am confused is it can be expanded using other non-terminals on the left. For example,

$\left<expr\right> \rightarrow \left<term\right> \times \left<expr\right> | \left<term\right>$

Could be expanded via $\left<term\right>$ on the left, I think. Does this make the associativity ambiguous? Assuming it could be ambiguous, how would I fix this to make the grammar completely right associative?

$\left<expr\right> \to \left<term\right>×\left<expr\right> | \left<term\right>$

could certainly expand $\left<term\right>$. But the operator in that expansion (if there is one) is certainly not $×$; it would have to be $+$. So associativity doesn't apply, since associativity is only about expressions involving two of the same operator.

So yes, in both operator productions in that grammar, the operator is right-associative.


Smallest integer with k 1-bits that is the sum of two integers with g,h 1-bits respectively Given integers $g, h, k, n$ how to find the smallest integer with $k\ 1$-bits that is the sum of two integers with $g, h\ 1$-bits respectively. Moreover, all three numbers (summands and sum) can have at most $n$ bits, i.e. the result is the n-bit number with $k\ 1$'s  and $(k - n)$ zeros, for instance $\underbrace{0...0}_\text{n -k}\underbrace{1...1}_\text{k}$. These $1$-bits don't have to be consecutive. Of course, such a number may not exist at all. You can think of this output integer (if it exists) as a permutation of a set of $n - k$ zeroes and $k$ ones.

I have a strong feeling that this is a dynamic programming problem but I can't get what is a subproblem here. I actually have no clue about DP relation for this problem. Could anyone give me some hints?

UPDATE. I've came up with the following plan:

Let $dp(g, h, k, n, carry)$ be such a sum, where $carry$ is an optional bit for carrying.
Then $dp(g, h, k, n + 1, 0)$ = $min\{dp(g,h,k, n,0),\ \ \ \ \  \ \ \ \ \ \ \ \ \ \ :(0, 0) \\2^n + dp(g,h,k - 1, n,1)\\ 2^n + dp(g - 1, h, k-1, n, 0), \ \ :(1, 0) \\ 2^n + dp(g, h - 1, k - 1, n, 0), \ \ :(0, 1)  \}$

$dp(g, h, k, n + 1, 1)$ = $min\{dp(g - 1, h, k, n, 1),\  \ \ \ \ \  \ \ \ \ \ \ \ \ \ \  \ :(1, 0) \\ dp(g, h - 1, k , n, 1),\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ :(0, 1) \\  dp(g-1,h-1,k, n,0)\ \ \ \ \ \ \ \ \ \ \  \ \ \  :(1, 1)\\
2^n + dp(g - 1, h - 1, k - 1, n, 1)\}$

I realized that this is too complex for me to handle on my own. I don't know what are the initial values (or base case of recursion in top-down approach) of this DP-table should be. Provided $g + h = k \leq n$ it is obvious that $dp(g, h, k, n, ?) = 2^k - 1$. As the question mark indicates, I don't understand what to do with the optional carrying bit in this case. I do not really understand how I should indicate there is no such sum, etc. Also, how to fill this DP-table? Should I use top-down approach? I need further help to proceed.

We are looking for a sum $z = x + y$, where $z$ has $k$ bits set, $x$ and $y$ have $g$ and $h$ bits set, and $z$ is as small as possible. We assume $g ≥ h$. A solution can be found directly, without any dynamic programming.

We add the numbers $x$ and $y$ from the lowest to the highest bit, taking carries into account. If we add two bits 0 + 0 without a carry, these bits can be removed without changing the number of bits set, but making the result smaller.

We can also take any pairs where we add 1 + 0 without carry, or 0 + 1 without carry, and move those pairs to the lowest bit positions. This doesn't change the number of bits set, but moving a 1 bit in the result to a lower bit position will not make the result larger, but may make it smaller.

Now if we add two bits 0 + 0 with carry, then we can remove these bits as well, but it is slightly more complicated. Obviously we can remove them if they are the highest bits. Otherwise, since adding 0 + 0 with or without carry does not produce a carry, and we removed all pairs 0 + 0 without carry, and moved all pairs 0 + 1 or 1 + 0 without carry to the lowest bit positions, the next higher bits must be 1 + 1. Adding 0 + 0 with carry gives a result of 1 and no carry, then adding 1 + 1 without carry gives a result of 0 with a carry. If we remove the two 0 bits, then we add 1 + 1 with carry, which gives a result of 1 with a carry. The number of bits set is unchanged, but a zero bit is removed in the result, making the result smaller.

So we are adding any number of pairs 0 + 1 or 1 + 0, then we may have a pair 1 + 1 producing a carry, followed by any number of pairs 1 + 1, 1 + 0 or 0 + 1. Starting with the addition 1+1 we will always have a carry, and adding 1 + 1 with carry produces a 1 with carry, while adding 1 + 0 or 0 + 1 with carry produces a 0 with carry. Reordering these pairs makes no difference to the number of bits set, but by moving all pairs 1 + 1 as far as possible to the lower positions we move 1-bits to lower positions in the result, making the result smaller.

Adding the initial 1+0 and 0+1 pairs produces exactly one bit set in the output for each bit set in the input. Adding 1+1 produces 0 output bits; each further pair produces one output bit set less than the input bits, and finally one bit will be set in the output from the final carry. If this optional range consists of j pairs, then we lose j output bits (for example, 111 + 111 = 1110, j = 3, six bits set in the input, 3 bits set in the output).

We see that we have no solution if $k > g + h$. If $k = g + h$ then one optimal solution is $x = (2^g - 1)·2^h$, y = (2^h - 1).

If $k < g + h$, then we let $j = (g + h) - k$. We need to lose exactly $j$ bits set, so the range of bit producing carries must be $j$ bits long. In this range, from j+1 to 2j bits are initially set; we get the smallest possible sum if we have as many pairs 1+1 as possible. If g + h ≤ j then there is no solution. We construct the numbers x, y as follows:

We have $a$ 1+1 pairs, where $a = min (k, j, h)$. Then we add $b = j-a$ pairs at higher and $c = k - a$ pairs at lower bit positions. Of these pairs, we have $g-a$ pairs 1+0, and $h-a$ pairs 0+1.

As an example: Let k = 10, g = 14, h = 3. j = 7, a = min (k, j, h) = min (10, 7, 3) = 3, b = j-a = 7-3 = 4, c = k - a = 10 - 3 = 7. We have

x =   1111 111 1111111
y =   0000 111 0000000
z = 1 0000 110 1111111


Predicting energy consumption of households I have the dataset which you can find here, containing many different characteristics of different houses, including their types of heating, or the number of adults and children living in the house. In total there are about 500 records. I want to use an algorithm, that can be trained using the dataset above, in order to be able to predict the electricity consumption of a house that is not in the set.

I have tried every possible machine learning algorithm (using weka) (linear regression, SVM etc) . However I had about 350 mean absolute error, which is not good. I tried to make my data to take values from 0 to 1, or to delete some characteristics. I did not managed to find some good results.

I also tried to use R tool, and I did not have good results either...

I would be very grateful, if someone could give me some advice, or if you could examine a little the dataset and run some algorithms on it. What type of preprocessing should I use, and what type of algorithm?

I have posted a similar question last month, but I did not get any useful answers.

I am not an expert in machine learning, but here is one problem: most of your data is binary. Since you have many such paramters, very little can be derived in terms of correlation between any given parameter and the target quantity. Therefore, statistic methods will have a hard time.

Furthermore, you have a small data set but many parameters. Get rid of some.

Another problem can be that you have mutually exclusive data: for example, the first three parameters (URBAN, RURAL and MOUNTAINOUS) can not be set at the same time. You might want to combine them into one category parameter; thus, the algorithms don't have to find a multi-dimensional anti-correlation and correlate the vector to energy consumption, but use that one parameter directly. Note how this also reduces the number of parameters.
If you can make assumptions about which areas inherently cause more energy consumption, consider turning the parameter into an appropriate interval (of reals).

As a general rule, machine learning is what you do if other methods don't work. In this case, I don't see the need for machine learning unless you show that reasonable other approaches fail.

For instance: Research energy consumption of the appliances you have parameters for and assume average values resp. values fitting the total area covered. Research and/or make reasonable assumptions for the number of light bulbs, air conditioning, etc based on total area. If this does not already solve your problem, it should reduce the number of parameters with unknown influence.


Difference between heuristic and approximation algorithm? i have a problem regarding the following situation.

I have two arrays of numbers like this:

index/pos     0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15
Array 1(i):   1   2   3   4   7   5   4   3   7   6   5   1   2   3   4   2
Array 2(j):   4   4   8  10  10   7   7  10  10  11   7   4   7   7   4

now suppose the second array is very hard to compute but I have noticed that if I add

A[i] + A[i+1]

in the array 1 I get the number very close to the number A[j] in the array 2.

Is my solution a heuristic or approximation?
If I had a reason to believe that I will never overshoot the value of A[j] by +-x with this algorithm and can prove it, would then  my solution be a heuristic or approximation?

Is there any literature that deals with heuristic vs. approximation questions for P class problems where the solution can be achieved in polynomial time but the input is just too big for a poly time algorithm to be practical.

thank you

A heuristic is essentially a hunch, i.e., the case you describe ("I noticed it is near", you don't have a proof it is so) is a heuristic. As is solving the traveling salesman problem by starting at a random vertex and going to the nearest not yet visited each step. It is a plausible idea, that should not give a too bad solution. In this case, it can be shown that it won't always give a good solution.

An approximation algorithm is usually understood to give an approximate solution, with some kind of guarantee of performance (i.e., it solves TSP, and the total cost is never off by more than a factor of 2; or even better, it solves TSP and, depending on <some parameters that can be varied> the solution is never worse than optimal by more than a factor $1 + \epsilon$, where $\epsilon$ depends on <parameters>).


How is a JIT compiler different from an ordinary compiler? There's been a lot of hype about JIT compilers for languages like Java, Ruby, and Python. How are JIT compilers different from C/C++ compilers, and why are the compilers written for Java, Ruby or Python called JIT compilers, while C/C++ compilers are just called compilers?

JIT compilers compiles the code on the fly, right before their execution or even when they are already executing. This way, the VM where the code is running can check for patterns in the code execution to allow optimizations that would be possible only with run-time information. Further, if the VM decide that the compiled version is not good enough for whatever reason (e.g, too many cache misses, or code frequently throwing a particular exception), it may decide to recompile it in a different way, leading to a much smarter compilation.

On the other side, C and C++ compilers are traditionally not JIT. They compile in a single-shot only once on developer's machine and then an executable is produced.


$\omega$-automata where string is accepted iff a final state is accessible from starting state I am wondering if $\omega$-automata with the following acceptance condition are valid.
An input string is accepted iff one of the final states occurs at least once.
This differs from Buchi automata in that the final state only has to occur once, not infinitely often.
Does this kind of automata have a name? Is it interesting or important?

Yes, it was studied before. In one of the early papers on accepting infinitary languages Landweber introduced five acceptance types that included those of Büchi and Muller. On the lowest level where two types that referred to the set of states entered, and the other three levels considered the more classic set of states entered infinitely often.
Your type is called 1-acceptance (if I recall right) and a string is accepted if a state from an accepting set $D$ is entered at least once. The dual 1'-acceptance required that the states entered are always within $D$.
One level up one requires that a state from $D$ is entered infinitely often (Büchi), respectively that from some moment on the states are within $D$.
These definitions can be considered not only for finite state automata, but also for automata with external storage, like pushdown automata. One common fact for all such automata is that the 1-acceptance (your type) is of low "topological" complexity. Those $\omega$-languages are of the form $L\cdot \Sigma^\omega$, where $L$ is an ordinary language of the type of automata. This means one cannot accept $(a^*b)^\omega$.
In general there is a clear link between topological complexity of the $\omega$-language and the acceptance type.
L.H. Landweber, Decision problems for $\omega$-automata, Math. Systems Theory 3 (1969) 376-384.


A reference for pseudocode for Monge-Elkan algorithm? Does anyone have a good reference to pseudocode for Monge-Elkan string comparison algorithm?

I have access to the two  original papers, but they do not show the pseudocode of the actual algorithm. Also, I have seen some implementations in Java (preference), but they are part of the larger package and with a complex inheritance and composition hierarchies.

I was wondering if someone can point me to a pseudocode for the algorithm, so that I could implement it myself.

There are apparently several different variants of the Monge–Elkan metric. You can check out Cohen, Ravikumar and Fienberg, A comparison of string metrics for matching names and records, which describes several different metrics (not only Monge–Elkan). Many other online references also exist.


Schaefer's dichotomy theorem and reformulating 3-literal clauses Does Schaefer's dichotomy theorem establish that a general 3-sat clause cannot be transformed into an equivalent set of 2-sat/Hornsat/affine clauses (using auxiliary variables) or just that this would be very unlikely in that it would imply P = NP?  I ask because I know that there are some types of problems involving 3-literal-clauses which can be transformed into equivalent 2-sat/Hornsat clauses.  I'm thinking specifically of 2-or-3 SAT which can be solved by 2-sat/anti-Hornsat clauses or 1-or-3 SAT which can be solved using affine clauses.

Schaefer's dichotomy theorem doesn't purport to claim anything about what transformations might be possible / not possible.

However, as Yuval says, we don't need Schaefer's theorem.  We already know that 3SAT is NP-complete.  Therefore, we know that if there is a polynomial-time transformation that transforms a 3SAT instance into an equisatisfiable 2SAT instance, then P = NP.  Put another way, if P $\ne$ NP (as many researchers suspect to be the case), then there is no polynomial-time transformation that transforms a 3SAT instance into an equisatisfiable 2SAT instance.  Put yet another way, finding such a transformation that provably works is at least as hard as proving that P = NP.

The same holds for a transformation to any other set of formulas that are known to have a polynomial-time algorithm for testing satisfiable (e.g., the conjunction of Horn clauses).


Empirical Risk and True Risk - Generalization Error Proof I showed that, over an uncountable domain,learner A and a distribution P, such that for every sample size m and all samples S from $P^m$
$$
: L_S(A(S)) − L_P (A(S))| = 1
$$
Now I wanna prove for countable domains. Lets assume X = N. I wanna prove that, for sample size m, and every $\epsilon> 0$, there exists a learner A and a distribution P over X, such that
for all samples S from $P^m$ we have
$$
|L_S(A(S)) − L_P (A(S))| ≥ 1 − \epsilon
$$
Not sure how to go about it. Any help is appreciated.

This answer (as, I presume, the question) uses the notation of the book Understanding Machine Learning: From Theory to Algorithms by Shai Shalev-Shwartz and Shai Ben-David.
Suppose our domain set is $\mathbb N$ and we are interested in binary classification. We want to show that there exists a distribution $P$ on $\mathbb N$ and a learning algorithm $A$ such that the difference between the empirical error $L_S(A(S))$ of the hypothesis $A(S)$ produced by $A$ given the finite sample set $S$ and the true error $L_P(A(S))$ is large, i.e. the hypothesis $A(S)$ performs well on the training data but does not generalize.
So to prove the statement, let $m \geq 0$ and $\varepsilon > 0$ and consider a binary classification scenario over the domain set $\mathbb N$.
We define a learner $A$ as follows: Given a set $S \subset \mathbb N \times \{0, 1\}$ of $m$ samples, $A$ outputs the hypothesis
$$ h_S(x) =
\begin{cases}
y, & \text{if } (x, y) \in S \\
0, & \text{otherwise}.
\end{cases} $$
Clearly, the empirical error of the hypothesis produced by $A$ will be $0$ for any training set $S$ as we defined the output of $A$ specifically to be correct for all samples in $S$.
It remains to construct a probability distribution over $\mathbb N$ such that the true error of the hypothesis $A(S)$ is at least $1 - \varepsilon$ for any choice of $S$.
Recall that the true error of a hypothesis $h$ w.r.t. a distribution $P$ is defined as
$$L_P(h) = \Pr_{(x, y) \sim P}[h(x) \neq y].$$
We now fix the labels in our distribution to always be 1 to ensure that $A(S)$ errs on all inputs not contained in the sample set $S$.
Hence the task now reduces to assigning probabilities to each $n \in \mathbb N$ such that the combined probability of any $m$ points forming such a sample set is bounded by $\varepsilon$.
To achieve this, consider the distribution $P \colon \mathbb N \to [0, 1]$ with
$$
P(n) =
\begin{cases}
\varepsilon / m, & \text{if } n \leq m - 1 \\
\varepsilon / (m \cdot 2^{n - m + 1}), & \text{otherwise}.
\end{cases}
$$
If we consider any sample set $S \subset \mathbb N$ of size $m$, we find that
$$ \Pr_{x \sim P}[x \in S] =  \sum_{n \in S} P(n) \leq \sum_{n \in S} \frac{\varepsilon}{m} = \varepsilon.$$
Hence, using the learner $A$ on a sample set $S$ of size $m$ drawn using the distribution $P$ yields a hypothesis $h_S$ with
$$
\begin{align}
L_P(A(S))
&= \Pr_{x \sim P}[h_S(x) \neq 1] \\
&= \Pr_{x \sim P}[x \notin S] \\
&= 1 - \Pr_{x \sim P}[x \in S] \\
&\geq 1 - \varepsilon.
\end{align}
$$
To finish everything off, recall that we defined $A$ such that $L_S(A(S) = 0$, yielding
$$|L_S(A(S) - L_P(A(S))| \geq 1 - \varepsilon.$$


Is there a general algorithm to fill holes in terms of the Calculus of Constructions? Suppose that you extend the Calculus of Constructions with "holes" - i.e., incomplete pieces of code that you didn't fill yet. I wonder if there is an algorithm to fill those roles automatically. For example (using Morte's syntax):

Case A:

λ (pred : ?)
-> λ (Nat : *)
-> λ (Succ : Nat -> Nat)
-> λ (Zero : Nat)
-> (Succ (pred Nat Succ Zero))

On this situation, a type inference algorithm can identify that ? can obviously only be ∀ (Nat : *) -> (Nat -> Nat) -> Nat -> Nat, because pred receives Nat : *, Succ : Nat -> Nat, Zero : Nat, and must return Nat, because it is the first argument of Succ.

Case B:

(Id ? 4)

Where 4 is λ-encoded and Id is the identity function (i.e., ∀ (t:*) -> λ (x:t) -> x). On that situation, ´?´ is again clearly ∀ (N:*) -> (N -> N) -> N -> N, because that is the type of 4.

Case C:

(Id (Equals Nat 7 (add 3 ?)) (Refl 7))

Here,Equals and Refl are defined in a similar fashion to Idris. ? can obviously only be 4, but how do you figure that out? One way would be using the fact that ? : Nat, and Nat is a type which we know how to enumerate, so we can just try all Nats til it typechecks. That can be done for any enumerable type.

Case D:

(Id (Equal Nat 10 (MulPair ?)) 10)

Here, ? can only be of type Pair Nat; it has only more than one valid answer, though: it can be (Pair 10 1), (Pair 2 5), (Pair 5 2) and (Pair 1 10).

Case E:

(Id (Equal Nat 7 (Mul 2 ?)) 7)

Here, there is no valid answer, since 7 isn't a multiple of 2.

All those examples made me notice that we can make a general algorithm that identifies some known patterns and gives an answer by handpicking a specific algorithm (type inference, brute-force, and so on), kinda like Wolfram Alpha figures out the right strategy to solve an Integral. But that sounds like an engineering/hardcoded approach. Is there a principled way to solve this problem? Is there any research study/area on it?

There is certainly a lot of research into this problem! It often goes by the name of elaboration. It is an undecidable problem in general, as you may have guessed. The "holes" are often called meta-variables or unification variables.

As I explain a bit in this answer, the problem reduces to higher order unification, on which several people have written whole PhD dissertations.

As you note in your examples, some cases are somewhat easy, and can be solved by the application of simple rules, whereas some seem significantly more difficult, and have more of a "theorem proving" feel to them.

A third possible case is a "type class" type problem, where ? represents some kind of structure, such as a group or field structure, as in

mul ? 2 3

with mul : forall G:Group, G.carrier -> G.carrier -> G.carrier or some variant. Here we need to find a G such that G.carrier == nat.

In general, you want to have 3 different "regimes" for each type of problem, the simple unification, theorem proving, and type class resolution problems respectively.

We explain this a bit in the following paper:

Elaboration in Dependent Type Theory, de Moura, Avigad, Kong & Roux.

You might want to look at the references of that paper for more info.

I've you've got a strong stomach, here is the open-source for elaboration in Lean.

Here is a wiki post that describes the interface to the elaborator in Idris.


Turing NP complete but not Karp NP complete? Is there some examples of candidate problems that have Turing reduction from SAT but no known Karp reduction?

Conversely is there some examples of candidate problems that have Turing reduction to SAT but no known Karp reduction?

The complement of any NP-complete problem (including SAT itself) is polynomial-time Turing-interreducible with SAT but, there's a Karp reduction if, and only if, NP$\,=\,$co-NP.


Is the difference between two regular expressions a new regular expression? Let say the following:

Given Ax and Bx two literals which represent POSIX regular expressions.

Let def A as the set of literals that match Ax. The same def for B.

Using relative complement operation, is there always regular expression for $A/B$ set, for every pair of Ax,Bx?

I attach an example:

Ax := a.*
Bx := a.*b$
// The difference A/B would be
Cx := a.*[^b]$

Regular languages are closed under relative complement. Since regular expressions encode exactly the regular languages, you can always find a regular expression that matches the relative complement of two other regular expressions.


Tips for creating “Context Free Grammar” I am new to CFG's, Can someone give me tips in creating CFG that generates some language

For example

$L =\{ w v w^R \mid v,w\in \{a,b\}^*\wedge|v| \text{ is even } \}$, where  $w^R$ is the reverse of
     string $w$.

I'm having trouble understanding the language .. I want to build DFA to convert it

Mmmm.

Let me note that in fact $L =\{ w v w^R \mid v,w\in \{a,b\}^*\wedge|v| \text{ is even } \}$ equals $\{ v  \mid v \in \{a,b\}^*\wedge|v| \text{ is even } \}$.

Al strings in $L$ are of even length, and conversely all strings of even length can be otained by taking $w=\varepsilon$.

That should help.


Union of two non-context-free languages Let L1 = L2 union L3
find values such that L1 is context free and L2 and L3 are not.

So far I have:
L1 = $a^nb^n$
L2 = $a^*b^*$
L3 = $a^+b^+$

Is this acceptable?? Since L2 covers everything including epsilon and L3 is the same but does not include epsilon?

I know L2 is regular so I guess that is also not a CFL.
Another problem is that the a's and b's aren't linked in L2 and L3, so either one can always have more a's than b's and vice versa.

Hint. For any language $L$, $$A^* = L \cup (A^* - L).$$
Now, choose an appropriate language $L$ to solve your problem.


What are elementary operations in time complexity definition? Wikipedia gives us the following defintion of time complexity:

  "In computer science, the time complexity is the computational
  complexity that describes the amount of time it takes to run an
  algorithm. Time complexity is commonly estimated by counting the
  number of elementary operations performed by the algorithm, supposing
  that each elementary operation takes a fixed amount of time to
  perform."

Now what are these elementary operations ? Are they arithmetic operations or some simpler operations ?
Thanks in advance!

The set of elementary operations and their cost constitute a model of computation. The most common model of computation used to analyze algorithms is the Random access machine. Briefly, memory is divided into words of size $O(\log n)$ bits, where $n$ is the size of the input to the algorithm. A program consists of a sequence of instructions. The exact set of instructions isn't really set in stone, but usually includes arithmetic instructions (addition, subtraction, multiplication, division with remainder), possibly bitwise instructions, memory dereferencing, control flow, and so on. In the unit cost RAM, the most common model, each instruction operations on a single word, and costs one unit of time.

Other relatively common models of computation include various models of Turing machine, the bit complexity model (in which words consist of a single bit), and logarithmic cost RAM.


Combinatorics: how many ways can we mark nodes in a DAG as black or white, if every node downstream of a black node is also black? We are assigning the colours white/black to the vertices of a DAG, under the condition that if $V$ is black and there is a path $V \to W$ for some vertex $W$, then $W$ is black.

Examples:

In the case of a linear chain of $N$ nodes, the answer is $N+1$ - either all the nodes are white, or one of the N nodes is black meaning all subsequent nodes in the chain are black.
In the case of $N$ nodes and zero edges, the answer is $2^N$.

A trivial solution is to generate all valid of the graph colourings, and then count the number of them. This can be done recursively in exponential time.

I'm looking for an efficient solution to the above problem. There is a seemingly O(n) dynamic programming algorithm that solves this for trees; I wasn't able to generalise it for the arbitrary DAG case.

Your problem is #P-complete. The set of solutions can be identified with the set of antichains with the poset corresponding to the DAG (the correspondence identifies a coloring with the black vertices that have no black parents), counting the number of which has been shown to be #P-complete by Provan and Ball in The complexity of counting cuts and of computing the probability that a graph is connected.