Turing Machines: What is the difference between the language realised by a problem and the language for which the TM accepts on? A decision problem A corresponds to the language L1 if L1 contains all of the solutions to A.

A language L2 is defined as the set of all inputs to which a TM halts and accepts.

What is the link between these two languages?

An algorithm solves a problem. Let’s assume that our algorithm is made to solve problem A.

The TM which implements this algorithm should halt and accept on all solutions to problem A. Due to the fact that the algorithm solves A.

Let’s now define L2 as the set of all inputs that the TM halts and accepts on. This will be the set of solutions to problem A.

If we define L1 as the set of all solutions to problem A.

Then in this sense, L1 and L2 should be the same.

I imagine that your confusion is when to use one or the other when defining the language. I am
not sure when you should use each one, however I usually note that if the Turing Machine recognises a language L which is the solution set to a problem A, then this TM can solve problem A.

Remember recognises means it halts and accepts on L.


Is the empty string a terminal symbol? I ask this question with regards to a grammar in Chosmky Normal Form. The definition states that the rules must be of the following forms:

A $\rightarrow$ BC
A $\rightarrow$ a
S $\rightarrow$ $\epsilon$

And A,B and C are non-terminal symbols, B and C are different from S and a is a terminal symbol. The definition also states that the last rule can only be present if the language of the grammar accepts the empty string (source). Now if $\epsilon$ is a terminal symbol, than this is a contradiction as the second rule can be transformed to S $\rightarrow$ $\epsilon$, seeing as A must not be different from S. This leads me to conclude that $\epsilon$ is not a terminal symbol, is this correct?

It's true that, in general, definitions don't include the empty string in the set of "terminals", as there's no need for that (e.g. the production rules for a context-free grammar are defined as a relation $V \rightarrow (V \cup \Sigma)^*$ - the star covers all productions of the form $A \rightarrow \epsilon$; in all other contexts, it can be omitted because it has no effect on concatenation).

Note, however, that in the case of a CNF grammar, you couldn't just make a simple convention for "terminals" to include the empty string and cut down to just the first two rules, because rules of the form $A \rightarrow \epsilon$ are not allowed for all non-terminal $A$, just for $S$.


Name for type of actions that only care for outcome There is a definition for kind of actions that only care for outcome.
Classic example for such an action is remove from collection:
When you try to remove an item that doesn't exist in collection, there are two possible outcomes: failure with item doesn't exist or success (because the outcome is that the item doesn't exist).
I'm interested in the second one.
How do you call remove that succeeds when the item it is trying to remove is not present?

This doesn't actually answer the question but it fits to be an answer.
What I looked for is idempotent (when I asked this question I was actually looking for this word, but failed to express myself properly).
The definition is quite different from the question asked here:

  In computing, an idempotent operation is one that has no additional
  effect if it is called more than once with the same input parameters.
  For example, removing an item from a set can be considered an
  idempotent operation on the set.

But indeed, any operation that is idempotent will meet the question criteria.


PDA with an unusual double inequality I have an odd PDA problem that I cant seem to construct. I haven't come across one like this before.

$L = \{w\in\{a,b\}^{*} : 3\#_{a}(w) \leq 5\#_{b}(w) \leq 4\#_{a}(w)\}$

Could I get some pointers on how to tackle such a problem like this so I can be more familiar with the approaches here.

It's your exercise, so you should solve it yourself... but I will give you two hints.

Study the methods used in Grammar for a language with 1/3 of a's.  They are helpful.
Use non-determinism.  Build a non-deterministic PDA.  (How do you think non-determinism might help here?)


How to prove the set of Turing machines that accept a string and its mirror is undecidable? I'm trying to prove the undecidability of the following language.

$$L=\{\langle M \rangle\mid M\text{ is a Turing machine and there is a string }w\\\text{ s.t. }M\text{ accepts }w\text{ and }M\text{ rejects }w'\},$$
where $w'$ is the mirrored version of $w$.

I know that my first steps should be to find a reduction from $A_{\text{TM}}$, which is undecidable but the rejection part of the mirrored string is proving troublesome.

It's the standard reduction from the Halting problem: given a machine $M$ and an input $w$ to it, construct a new machine $M$ that accepts your favourite string and rejects its reverse if $M(w)$ halts, and accepts nothing if $M(w)$ does not halt.

This technique applies to any question of the form "Prove that it's undecidable whether a Turing machine accepts a string or language of some specific kind."

Or just use Rice's theorem, if you've been taught that.


No FSM/Regex exists for this language right? The language is this:

$L = \{w \in \{a,b\}*:$ each $a$ has a matching $b$ somewhere in $w$ $\}$

This wouldn't have an FSM since you'd need infinite states of depth for each unmatched a you have, right?

Expanding on Daniel Martin's answer.
None of the following interpretations yields a regular language:

$L = \{ w \in \{a,b\}^*  : \exists n \ge 0,  \; w = a^n b^n \}$
$L$ contains all the words $w \in \{a,b\}^*$ such that the number of $a$s in $w$ is not larger than the number of $b$s in $w$.
$L$ contains all the words $w \in \{a,b\}^*$ such that the number of $a$s in $w$ is equal than the number of $b$s in $w$.
$L$ contains all the words $w \in \{a,b\}^*$ such that there is a injective/bijective mapping that maps each a $a$ that appears in a generic position $i$ in $w$ with a $b$ in $w$ that appears in a position $j>i$.

The proof is the same for all cases: if $L$ was regular then,
for a sufficiently large $n$, the word $w = a^n b^n \in L$ could be written as $w = a^{n-k} a^k b^n$ (with $1 \le k \le n)$ in such a way that $a^{n-k}a^{k \cdot h} b^n \in L$ for all choices of $h \in \mathbb{N}$ (see pumping lemma for regular languages).
This is a contradiction since $a^{n-k}a^{2k} b^n = a^{n+k}b^{n} \not\in L$.


Neither Left nor Rightmost Derivations Consider a simple grammar and its derivations. The derivations could be done in leftmost or rightmost patterns and can also be done in no particular order as the derivation order has no effect on the language generated by a grammar.

Apart  from practical considerations, such as implementation difficulty and orderliness of derivations, is there any other reason why we usually do not discuss about arbitrary derivations (not rightmost or leftmost)?

The main reason is that context-free grammars, once introduced, were quickly adapted to provide a theoretical basis for program language compilation.  For this usage, the goal is to parse as quickly as possible using as little storage as possible.  For that the best approach is to scan the input source once from 'left-to-right' [we interpret the source as a sequence of characters all on a single line], and be done with the parse exactly when done scanning the source.  Two derivation patterns naturally fit into this protocol: leftmost-first derivations performed top-down in forward order, and rightmost-first derivations performed bottom-up in reverse order.


Quicksort Algorithm with Pivot element as Median I have read that when pivot element is choosen as Median, then QS Algorithm gets nearly balanced splits and have time complexity of O(nlogn), but my doubt is what if all the elements of the input are same like (2,2,2,2,....,2) and pivot is still the median element, then what type of partitions QS will get as left and right subarray and what will be the time complexity. O(nlogn) or O(n^2)

This is not a homework question, I'm not in school/college anymore.

It depends on the partition algorithm used. Some might be $O(n^2)$ if they put all equal elements on the same side while others remain $O(n \log n)$ if they split the equal elements.


Where should "imply" be placed in this formalisation? I have to formalize the following sentence:

If any house is green then there exists a horse that is white.

I have formalized it the following way:
$$\forall(x)(\mathit{house}(x)\rightarrow \mathit{green}(x))\rightarrow \exists(y)(\mathit{horse}(y) \rightarrow \mathit{white}(y))$$
A friend formalized it in a slightly different way:
$$\forall(x)((\mathit{house}(x)\rightarrow \mathit{green}(x))\rightarrow \exists(y)(\mathit{horse}(y) \rightarrow \mathit{white}(y)))$$
Notice how in my formalisation, the right-most implication is separated from the $\forall(x)$, while in his formalisation the $\forall(x)$ encompasses the last implies as well.
I believe my way is correct because I think the sentence means that all houses being green implies that there's a white horse, and not that for any green house there's a white horse.
We haven't been able to reach a conclusion by ourselves, so any help would be appreciated!

Here is how to break your statement up:

If (any house is green) then (there exists a horse that is white).

An equivalent statement would be

If some house is green, then some horse is white.

The condition is "there exists a house which is green", and the consequence is "there exists a horse which is white".
If we wanted a different quantifier for the condition, we would change it to

If all houses are green, then some horse is white.

As you mention in the comments, this is more of a question in the semantics of the English language. This doesn't necessarily make it a bad question, since it highlights the need for a logical formalism which transcends such linguistic difficulties.
You can formalize the original statement as
$$
(\exists x \, \mathit{house}(x) \land \mathit{green}(x)) \to
(\exists y \, \mathit{horse}(y) \land \mathit{white}(y)).
$$
The prenex form is
$$
\forall x \exists y \, (\mathit{house}(x) \land \mathit{green}(x)) \to (\mathit{horse}(y) \land \mathit{white}(y)),
$$
or equivalently,
$$
\forall x \exists y \, \lnot \mathit{house}(x) \lor \lnot \mathit{green}(x) \lor (\mathit{horse}(y) \land \mathit{white}(y)).
$$


Universal Lossless Compression? It is not possible to losslessly compress all files of size $n$ using a single algorithm, as there are more files of size $n (2^n)$ than of size $p, p: p < n ( 2^n-1)$. Via the pigeon hole principle, if we only tried to compress files of size $n$ with a single algorithm, there would be at least one file it was impossible to compress.

If we wanted to be able to compress files with differing lengths $n_k$, the number of files of length $n_k$ we can compress for each $n_k$ becomes even smaller.

Today when reading a story about how a file that was several gigabytes when compressed uncompressed to one gigabyte, I had an idea for a universal compression algorithm.

Let $a_i$ be a compression algorithm.
Let $g_j$ be a file.
$|g_j|$ denotes the length of $g_j$.
Let $f(a_i, g_j)$ be a function that returns $(|g_j| - |a_i(g_j)|)$.

Let $S_N = \{g_j : |g_j| \le N\}$.

Let $A =  \{a_i : \, \forall \, g_j \in S_N \, \exists a_i in A : f(a_i, g_j) \gt \lceil(\log_2{\#A})\rceil\}$.
$\#A$ denotes the number of elements in $A$.

Let $m$ be the length of the label of the compression algorithm chosen. The first $m$ bytes of every compressed file denote the compression algorithm chosen.
$m = \lceil(\log_2{\#A})\rceil$.

Then you can compress all $g_j \in S_N$, by iterating through A until you find $a_i : f(a_i,g_j) - m \gt 0$.

Even better.

For each $g_j$, let $a_j$ be the corresponding compression algorithm.

Let $h(a_i, g_j) = f(a_i,g_j) - m$.

$${ \, \forall \, a_i \in A, g_j \in S_N, a_j = \displaystyle{ \underset{a_i \in A, g_j \in S} { \operatorname{argmax} } } \, (h(a_i, g_j))}$$

Is there a reason why the above is not done?

While the above is an algorithm, and one could argue that the pigeon hole principle thus applies, this does not imply what it may at first seem to imply.  The above algorithm call it $a^v$ is a little different.

Let $a_i: S_N \to Y_N^i$ denote that algorithm $a_i$ maps a family of files $(S_N = \{g_j : |g_j| \le N\})$ is mapped to another family of files $Y_N = \{y_j : y_j = a_i(g_j)\}$.

$\forall a_i \in A, a_i: S_N \to Y_N^i$.
However, $a^v : S_{N+m} \to Y_{N+m}^v$.
So $a^v$ compresses a different family of files from $a_i \ in A$.

The pigeon hole principle merely states that $a^v$ cannot compress all files of length $N+m$; this is irrelevant, since $a^v$ only intends to compress a small subset of files of length $N+m$ (those whose first $m$ bits are the labels of some $a_i \in A$.

Then you can compress all $g_j ∈ S_N$, by iterating through $A$ until you find $a_i|f(a_i,g_j)−m>0$.

I'm not sure what the notation means (the pipe here, and also $\#A$ elsewhere), but still: this is not a meaningful algorithm since the set

  $\qquad A = \{a_i : \, \forall \, g_j \in S_N \, f(a_i, g_j) \gt \lceil(\log_2{\#A})\rceil\}$

is empty.

I think you got lost in notation. $S_N$ = $\Sigma^{\leq n}$ and $A$ is the set of all algorithms that compress all strings in $S_N$ by at least some non-zero number of bits. As you cited, there are no such algorithms.

In the updated question, you write:

  $\qquad A =  \{a_i : \, \forall \, g_j \in S_N \, \exists a_i \in A : f(a_i, g_j) \gt \lceil(\log_2{\#A})\rceil\}$

This definition is circular, hence $A$ is not well-defined. Did you mean

$\qquad A = \{ a \mid \exists g \in S_N. f(a, g) > x \}$

with $x > 0$ something that does not depend on $A$?

Now $A$ is infinite (and undecidable as per Rice's theorem) and, arguably, completely useless: any string s can be compressed well by the trivial algorithm

compress_s(x) {
    if x == s
        return "0"
    else
        return "0" + x
    end
}

Note that this version of $A$ contains all these bogus algorithms. So, you have thrown all information while compressing, instead encoding the string in the algorithm's source code (mathematically and literally).

And, as others note, the resulting algorithm would still be subject to the pidgeon-hole principle.

  Is there a reason why the above is not done?

Even if it were possible, it'd be horribly inefficient. In essence, the idea of your algorithm is:

  Try all (compression) algorithms (I know); pick the smallest result and encode the result together with its code.

That's clearly neither a clever nor a useful algorithmic idea.


Issues with using greedy algorithm (Interval scheduling variant) I am trying to solve a problem of finding incompatible jobs set using greedy algorithm. However, I am not sure if greedy algorithm can solve this problem or I need to perform another approach.

I have a set of jobs with start and finish time and I want to find the smallest subset of this jobs such that all the jobs are incompatible with at least one job of this subset.

Suppose

job  start   end
1    1       3
2    2       11
3    4       6
4    7       8

My required job set J is {2} since  all the jobs are incompatible with at least one job of the job set J. I tried to use greedy algorithm like sorting jobs by start time, end time ( adding one  and removing all the ones incompatible and so on) But it is not optimal. As you can see in this example. If I add job 1 and then remove all the job incompatible with it, I will remove job 2, Then I will have to add 3 and 4 in the jobset J.

Am I going the right way?

It is clear from your edited post that you will need to use dynamic programming.

Consider solution with the recurrence based on minimum number of time intervals necessary to conflict with all other time intervals, and include a parent pointer so that you can create the set after the algorithm completes.


Algorithm to convert a fixed-length string to the smallest possible collision-free representation? I have a US-based telephone number (in the format 000-000-0000) and need to convert it to a "shorter" representation. Using base32/64 produces too long of a string. I've discovered CRC-16, which produces a string of length 4, however, I'm not sure it's a suitable tool for the job (I want to prevent collisions).

Basically, if the input is 000-000-0000 (without the dashes), I want the output to be something like 4xg4. In this use case, the advantage is that I have 10 digits, thus I could "convert" them to something smaller that uses letters as well.

Are you aware of any algorithm implementation for this?

As ratchet freak says, you have ten decimal digits, which should give $10^{10}$ possible values. But in practice, there are a few more restrictions. The format of a North American telephone number looks something like this:

[2-9][0-8]\d - [2-9]\d\d - \d\d\d\d

This gives 8*9*10 * 8*10*10 * 10*10*10*10 values. In addition, the fifth and sixth characters can't both be 1, which removes 1% of these. This means there are 5,702,400,000 possible telephone numbers. (Let's call this number $T$.)

If you want to encode these using an alphabet with $b$ different characters, you'll need a code $\lceil \log_b T \rceil$ characters long. So if you want a code four characters long, you'll need $b \geq 275$. If you want a code five characters long, you'll need $b \geq 90$. And if you want a code six characters long, you'll need $b \geq 43$.

Unfortunately, this is the best you can do, unless you have additional information about what numbers you'll be getting. This comes down to the pigeonhole principle, a remarkably straightforward theorem that's quite useful in CS. It's mathematically impossible to use fewer characters than this without ever having any collisions. You can make collisions extremely unlikely, but never fully prevent them.

(You can also make some of the codes be shorter without collisions, but as a consequence some of them will have to be longer. Again, pigeonhole principle.)

P.S. Note that, while base64 also produces a six-character string (since 64 is between 43 and 90), you can take advantage of the fact that you only need 43 to choose a "nicer" character set. For example, you can get rid of o, O, 0, Q, I, l, and 1 to cut down on confusion in writing. My suggestion would be 23456789ABCDEFGHJKLMNPRSTVXYZabdeghknpqrt-=.


Is this computational complexity of the k-NN (custom distance) correct? I read on a book that in general k-NN (no optimizations), given

$d$ dimensions
$n$ examples

every computation of distance is $O(d)$. Since every example has to be compared with all the other ones, the complexity is $O(dn^2)$

I am doing 1-Nearest-Neighbors with Dynamic Time Warping as distance "metric".

The complexity to my calculations, was, given:

$d$ dimensions
$n$ examples
$m$ instances of feature for each example
(bonus) $c$ classes

$O(m^2)$ complexity of a single comparison of DTW algorithm

$O(d\,n^2)$ complexity of general k-NN

Thus in a single training/test, the complexity for all the computation is:

$O(d\,n^2\,m^2)$

If I have $c$ classes, and $c$ classifiers, one for each class, with each having custom features, the overall complexity is

$O(c\,d\,n^2\,m^2)$

Is this correct? Or I'm missing something?

EDIT:
An example contains temporal data which gives out another dimension.
You can imagine an example as a matrix where $d$ is the number of features (columns), and $m$ the number of instances of features (rows).

So I can have a table like this

<$m$> | $f_1$ | $f_2$ | $f_3$ | ...

$m_1$ | $a$ | $b$ | $c$ | ...

$m_2$ | $a'$ | $b'$ | $c'$ | ...

When I compare for a single feature two examples, the DTW distance is a scalar value for each feature, so the comparison becomes

$dist_1$ | $dist_2$ | $dist_3$ | ...

with $dist_i$ scalar $\forall i$ and $|\{dist_i | \forall i\}| = d$

The time complexity to calculate each $dist_i$ is $O(m^2)$ (DTW algorithm has quadratic complexity, or $m\cdot m'$ if different number of lengths).

The running time of a nearest neighbor classifier is the time to compute the distance between two examples, multiplied by the number of pairs of examples you need to compute the distance between.  So, all you need to do is figure out each of those two numbers.

For ordinary k-nn, it takes $O(d)$ time to compute the distance between two $d$-dimensional examples, and to classify an example, you need to compare it to all other examples, i.e., $n$ pairs.  So, the running time to classify a single point with ordinary k-nn is $O(dn)$ (not $O(dn^2)$ as you wrote).

For your scheme, it appears it takes $O(dm^2)$ time to compute the distance between two examples (you need to run the DTW algorithm $d$ times, and running DTW once takes $O(m^2)$ time).  The number of pairs doesn't change; to classify a single example, you still compute the distance to each example in the training set, so $n$ distance computations.  Therefore, the running time to classify a single point in your scheme is $O(dm^2n)$ (not $O(dm^2n^2)$ as you wrote).


Bloom Filter which does not fit in RAM Is it possible to efficiently create a bloom filter with 10^12 buckets on a single machine with 32GB of RAM and a hard drive. We can assume that the keys are already on the disk and are small in size?

A Bloom filter doesn't have "buckets".

You can make a Bloom filter of any size you want.  The smaller it is, the higher the false positive rate.

This should be covered in any good introduction to Bloom filters, of which there are many.


Given a computable function $f$ and a decidable language $L$, is there a Turing machine $M$ such that $M$ both decides $L$ and computes $f$? 1) (cited from "Introduction to the Theory of Computation" by Michael Sipser)

  Let $M$ be a Turing machine, we say that $M$ decides a language $L$ if $M$ is a decider which recognizes $L$.

2) (cited from "Computational complexity: a modern approach" by Boaz Barak and Sanjeev Arora)

  Let $f \colon \Sigma^{∗} \rightarrow \Sigma^{∗}$ and let $T \colon \mathbb{N}
 \rightarrow \mathbb{N}$ be some functions, and let $M$ be a Turing machine. We say that $M$ computes $f$ if for every $x \in \Sigma^{∗}$, whenever $M$ is initialized to the start configuration on input $x$, then it halts with $f (x)$ written on its output tape.

I think these two definitions shows two different functions of TMs, and it seems that there is not conflict between them.

So, given a computable total function $f$ and a decidable language $L$, is there a Turing machine $M$ such that $M$ both decides $L$ and computes $f$ ?

Yes it clearly exists; informally you can build such $M$ in this way:

$M$ makes a copy of its input $x$
then without touching such a copy, $M$ decides if $x$ is in $L$ (possibly "destroying" the working copy of $x$),
if $x \in L$ it enters a "subprogram" (set of states) in which all states are accepting and such subprogram uses the copy of $x$ to compute $f(x)$ (leaving the result in the output tape and ending in an accepting state)
if $x \notin L$ it enters a "subprogram" (set of states) in which all states are NON accepting and such subprogram uses the copy of $x$ to compute $f(x)$ (leaving the result in the output tape and ending in a NON accepting state)


Show that RP is closed under concatenation I'm trying to prove the following problem:

  Show that $RP$ is closed under concatenation

Now, let's say that the two languages are $L_{1}$ and $L_{2}$ (both in $RP$). Then I accept a word iff the TM of $L_{1}$ accepted the first part of the word (with a probability $\geq\frac{1}{2}$), and the TM of $L_{2}$ accepted the second part of the word (with a probability $\geq\frac{1}{2}$).

But then each word in the language $L_{1} \circ L_{2}$ would be accept with a probability of $\frac{1}{2}\cdot\frac{1}{2}=\frac{1}{4}$, so the language $L_{1} \circ L_{2}$ will not be in $RP$.

So what is the correct proof to the problem?

Do the following $poly(|x|)$ times:

  Check for every possible (contiguous) partition of the input string $x = x_1x_2$ and apply the $\mathrm{RP}$ machine to each of $x_i$ if the answer is $\mathrm{YES}\:\mathrm{YES}$ outputs $\mathrm{YES}$ and halt.

If after polynomially many times, still no definite $\mathrm{YES}$ answer has been put down, output $\mathrm{NO}$ with a little bit of fear as it is always like so with $\mathrm{RP}$ algorithms.


Calculating direct sum of 2 binary numbers If we have say,key=‘0110‘ and =‘1100‘, how will ⊕key mod 2 be calculated and what will be the answer equal to?

The operation $\oplus$ is the same as bitwise XOR. The same symbol is used for direct sum, but there is otherwise absolutely no relation.


Can bar codes theoretically be considered a type of digital memory? Bar codes act just like any other device that contains data that you can read from. Can bar codes thus be considered a type of computer memory?

I believe the principle is quite similar to the optical discs like CDs or DVDs.

They work just like an SD memory card but instead of a card reader we use barcode scanner to read the digital data stored in the bar code.

Can bar codes be useful in other types of applications instead of identifying products? Can barcodes or similar technology be used in computers?

There is no god-given definition of (read-only) digital memory. We can think of several reasons for a writing system to be considered digital:

Can be read by a computer.
Cannot be read by a human.
Has high density.
Designed for use by computers.

Barcodes satisfy the first two properties, but not the third one: their density is rather low. Nevertheless, both traditional barcodes and modern QR codes were designed to be read by machines, and this gives credence to your claim.


Find an algorithm that finds a minimal hitting set for sets limited in size Given a family of sets $F=\{S_1,...,S_m\}$, where $S_i{\subseteq}\{1..n\}$, with the assumption that the maximum size of any set $S_i$ is at most $k$ ($|S_i|{\leq}k\ {\forall}i\in\{i..n\}$).

I'm tasked with finding a hitting set $H$, a set that contains at least one member from each set $S_i$ ($H{\cap}S_i\ne\emptyset\ {\forall}i\in\{1..n\}$). And to prove that the algorithm gives produces a set that is at most k times larger than the minimal hitting set.

What algorithm does it and how do I prove that it does it.

I've tried the greedy algorithm (take the number that covers the most sets, remove those sets, repeat).

I've also tried making the problem into a two sided graph where one side is the numbers, the other side are the sets and edges connect sets with their members, and applying a minimum cover set algorithm.

For both instances I couldn't show that the hitting set it gives is at most a set k times larger than the minimum.

Here are two algorithms for the case $k=2$, also known as Vertex Cover; we think of the sets $S_i$ as edges and of the elements $\{1,\ldots,n\}$ as vertices. We can assume that each edge connects two vertices, since singleton edges can easily be eliminated.

Both algorithms below can be extended to the case of general $k$.

Algorithm 1: Maximal matching Pick a maximal matching, and take all vertices containing it. This is a vertex cover since if there is an edge which isn't covered, the matching isn't maximal. Every vertex cover must contain at least one vertex per edge in the matching, and our solution contains two vertices per matching edge, hence it's a 2-approximation.

Algorithm 2: Linear programming Consider the following LP relaxation: there is a variable $0 \leq x_i \leq 1$ for every vertex, and a constraint $x_i + x_j \geq 1$ for every edge $(i,j)$. Find a solution minimizing $\sum_i x_i$, and take all vertices such that $x_i \geq 1/2$. This is clearly a vertex cover, and its value is at most twice the value of the LP, hence it's a 2-approximation.


Proving Quicksort is $O(n^2)$ So I'm trying to figure out why the worst case of Quicksort is $O(n^2)$.
I know this a very well known problem, but the funny thing is where ever I look (even Wikipedia) gives the following explanation: "The worst case is the most unbalanced case where the problem splits to a problem of size $n-1$ and a problem of size $0$ (i.e. when the array is already sorted)".
Then they use the master theorem and find it is $O(n^2)$.
Marvelous. So simple. But wait.
Do we know upfront that the worst case is $O(n^2)$? No, that's what we need to prove.
"The most unbalanced case" meaning it is the worst case? Is there any theorem that states this?
So what is actually a coherent proof that Quicksort is $O(n^2)$?
Or in other words, what is the proof for the missing part?
We can derive that the run time can be described as $T(n) = T(n_1) + T(n_2) + O(n)$ where $n_1 + n_2 + 1 = n$. How to prove $T(n)$ is the largest when $n_1 = 0$ and $n_2 = n-1$?
I already know this is the most unbalanced case. Why is it actually the worst case?

The running time of quicksort satisfies the recurrence
$$
T(n) \leq \max_{n_1+n_2+1=n} T(n_1) + T(n_2) + Cn,
$$
with base cases of $T(1) = C$ and $T(0) = 0$, say. Let us now prove by induction that $T(n) \leq Cn^2$. The base cases obviously hold. As for the inductive step,
\begin{align}
T(n) &\leq \max_{n_1+n_2+1=n} C(n_1^2 + n_2^2) + Cn \\ &=
\max_{0 \leq m \leq n-1} C(m^2 + (n-1-m)^2) + Cn \\ &=
C(n-1)^2 + Cn + \max_{0 \leq m \leq n-1} 2Cm(m-(n-1)) \\ &\leq
C(n-1)^2 + Cn \\ &\leq Cn^2.
\end{align}

Why is the worst case when $n_1 \in \{0,n-1\}$? This is because the function $n^2$ is convex, that is, the maximum of $x^2+(n-x)^2$ over $x \in [0,n]$ is attained at one of the endpoints. In more complicated situations, we could trying showing this directly, by inductively showing that $T(n+2)-T(n+1) \geq T(n+1)-T(n)$, which should imply (I think) that the maximum of $T(n_1)+T(n_2)$ is attained at one of the endpoints.


What if there is a polynomial-time algorithm to minimize NFA? Knowing that NFA-minimization has been proven to be P-SPACE complete, what if there is a polynomial-time algorithm to minimize NFA? Does that imply that P = PSPACE?

If any PSPACE-complete problem is proved to be in P, then that proves that P = PSPACE, i.e., every problem in PSPACE can be solved in polynomial time.

Why?  Suppose we have a polynomial time algorithm for NFA minimization.  Since NFA minimization is PSPACE-complete, any other problem in PSPACE can be solved by reducing the problem to NFA minimization, then applying the polynomial-time algorithm for NFA minimization.  The definition of PSPACE-complete ensures that the reduction step will complete in polynomial time, so solving that problem can be done in polynomial time.


How many operations at maximum needed to compute powering of a number, i.e. $N^k$? Suppose $N$ is $L$-bit long and $k$ is also $L$-bit long.

How to show that it takes at most O$(L^2)$ operations to compute it.

For example $N = 1010$ and $k = 10$. Then $N^k = 6^2 = 100100$. But I am not familiar with how $100100$ comes up without going back to decimal and using the fact that $6*6 = 36$. Therefore, I also find it hard to realize that it takes at most O$(L^2)$ operations to compute the powering of a number.

It depends on what you mean by operations. If multiplication of unbounded numbers is considered one operation, then repeated squaring takes at most $2L$ operations. In that case we don't care about the size of $N$.

If we only consider multiplication of $L$-bit integers as a unit operation, then multiplying $ML$-bit integers takes $O(M^2)$ operations using the high-school algorithm (in fact, much better algorithms are known), and so repeated squaring, in which the integers have size $L,2L,4L,\ldots,2^LL$, takes $O(1^2 + 2^2 + \cdots + 2^{2L}) = O(2^{2L}L)$ operations. Using fancier multiplication algorithms that take $\tilde{O}(L)$ operations (if they exist in this setting) reduces the number of operations to $\tilde{O}(2^L)$.


Finding pair of sum in sorted array in time complexity less than $O(n)$ In a sorted array, I am trying to find just one pair that sum up to a certain value. I was wondering if anyone could help me improve my code in performance or memory. I know the code which is $O(n)$. If there are other method for finding pairs the sum up to a certain value that is much more efficient.
I was asked this in an interview recently and interviewer told me that there exists a solution with $O(\log n)$ time complexity.
Any ideas are appreciated.

Your interviewer is wrong.
Suppose that you had an algorithm which gets as input a sorted integer array $A_1,\ldots,A_n$, outputs Yes iff $A_i + A_j = 0$ for some $i \neq j$, and always accesses at most $n-1$ inputs.
Suppose first that $n = 2m$ is even, and consider the following sorted integer array $B$:
$$ -2m, -2(m-1), \ldots, -4, -2, 1, 3, \ldots, 2(m-1)-1, 2m-1. $$
This array contains no solution to $B_i + B_j = 0$. For any index $i$, we can create a sorted integer array $B^{(k)}$, differing only in the $k$'th entry, which does have a solution to $B^{(k)}_i + B^{(k)}_j = 0$.
Now run the given algorithm. Whenever it tries to access a position $A_i$, answer the value $B_i$. By assumption, the array terminates without querying some position, say $A_k$. Therefore the algorithm behaves the same when given as input the arrays $B$ and $B^{(k)}$, although the answer is No for the first one and Yes for the second one.
When $n=2m+1$ is odd, a similar argument works with the following sorted integer array:
$$ -2m, -2(m-1), \ldots, -4, -2, 1, 3, \ldots, 2(m-1)-1, 2m-1, 2m+1. $$


How to determine the dimensions of the bias vector in a Convolutional layer (tensor flow)? In the Deep MNIST Tutorial for Tensor Flow, (and in general), we create a convolutional layer with a weight tensor, say W,  of shape (patch dims, #input channels, # output channels). However, when we define the bias tensor, b, its shape is only (#output channels).

When we convolve W and the input x, with correct padding, we will get a volume with depth = #output channels. How can we add a single bias vector to such a volume?

Are we supposed to expand the bias vector to take on the spatial dimensions of the input x?

No.  The bias vector should indeed have the same dimensions as the output vector (not the dimensions of the input).  In a neural network, after summing the weights times the inputs, the bias is added pointwise, then you apply the activation function (e.g., ReLu).  The equation for a single neuron is something like

$$y = f(\sum_i c_i x_i + c_b)$$

where $x_1,\dots,x_n$ are the inputs, $c_1,\dots,c_n$ are the weights on the inputs, $c_b$ is the bias, and $f$ is the activation function.  Notice how we have one bias number per neuron, i.e., per output.  (This equation gets modified a bit for convolutional neural networks but the relevant part still remains the same: we have one bias value per output.)


Prove the following problem is NL-complete Suppose
$$A = \left\{\langle G, d, s, t\rangle \;\Bigg|\;
\begin{array}{l}
  \text{\(G\) undirected}, \\
  \text{\(s\) and \(t\) are nodes in \(G\)}, \\
  \text{there is a path of length \(d\) from \(s\) to \(t\) and no path of shorter length}
\end{array}\right\}$$
I can easily see that this language is in NL, but I am having trouble proving that this is NL-complete.

Let $G'$ be the graph with self-loops added to every vertex. Take $n$ copies $G'_1,G'_2,\ldots,G'_n$ (without the edges) and connect $x \in G'_i$ to $y \in G'_{i+1}$ if $(x,y) \in G'$. The shortest path between $s \in G'_1$ and $t \in G'_n$, if any exists, is now of length exactly $n-1$.


Another version of the online set cover problem? Here is a note about online set cover problem:
we are initially given the $m$ sets, but we do not know which elements they contain. At any time $t$, we get a new element $e_t$ and learn which sets contain $e_t$. We then have to irrevocably pick a set that will cover $e_t$ if it is not already covered. The goal is again to minimize the number of sets we pick.

However, I'd like to think about another version: we have a group of sets $\mathcal{S} = \{ S_1, S_2, \cdots, S_m \} $ and a universal set $U=\{ e_1, \cdots, e_n \}$.
$U$ can be covered by $\mathcal{S}$. But we don't know what elments each $S_i \in \mathcal{S}$ contains. Then $S_1$ comes and now we know what elements $S_1$ contains. Meanwhile, we have decide either you will use $S_1$ to cover $U$ or you discard it. Then, $S_2$ comes, you know what elements $S_2$ contains and decide to keep $S_2$ or discard it. The process is repeated until the sets you keep can cover $U$.

I want to ask if there is an algorithm works in the way I mentioned. Must we check all the $S_i \in \mathcal{S}$ in order to get a solution of set cover? Or what is the expected number of sets that have to be checked in order to get a solution of set cover?  If we can also design a $O(\log n\log m)$ approximation ratio algorithm for this online version.

A simple adversary argument shows that you must take every set you are offered, unless it's entirely covered by elements already taken. Indeed, otherwise there must be some element $x$ which hasn't appeared before; perhaps it will never appear again, so you must take the set.

Consider now the following instance:
$$
\{x_1\},\{x_2,\},\ldots,\{x_{m-1}\},\{x_1,\ldots,x_m\}.
$$
The algorithm takes all $m$ sets, but the last one would have sufficed. This shows that the approximation ratio can be as bad as $m$, the number of sets.


Comparing nodes in A* Nodes in the open list in A* will be sorted by their f-cost, but if the f-cost of two nodes are equal, will their h-costs instead be compared? I'm asking because I've seen implementations where the h-costs are compared and where they aren't, so which version is the right one? What is the benefit of doing either?

g-cost: Cost from start to node

h-cost: Heuristic from node to end

f-cost: g-cost + h-cost

Edit: From  Hart, P. E.; Nilsson, N. J.; Raphael, B. (1968). "A Formal Basis for the Heuristic Determination of Minimum Cost Paths"

"Select the open node n whose value of f is smallest. Resolve ties arbitrarily, but always in favor of any node n ∈ T."

It is stated that "T" is the goal set (I thought there was only one goal node?)

My interpretation is that if the goal node is in the open set, then it should be picked first, meaning resolving ties via h-cost is certainly a correct way because h(end) = 0.

It's not problematic to have more than one goal node in A* if you just want to reach any goal node. You simply keep running the search until you have expanded the first goal node.

Provided that your $h(x)$ function is consistent (or just admissible if your graph is a tree) the way of breaking ties does not affect the optimality of the search. As A* always expands all nodes with $f(x) \lt C^*$ where $C^*$ is the true cost of the optimal solution, and never expands nodes with $f(x) \gt C^*$, the number of nodes that gets expanded will end up being the same (or almost the same, as we will see).

Consider this case: We have two nodes $a$ and $b$, who are both on the open list, and we have that $f(a) = f(b)$ and $h(a) \lt h(b)$. We choose to expand $a$ because of the lower $h$-value and discover that a goal node $g$ is a neighbor to $a$. As $h(x)$ is at least admissible the actual distance between $a$ and $g$ can not be shorter than $h(a)$ and therefore $f(g) \geq f(a)$. There are now two cases:

- If $f(g) \gt f(a)$, then we also have that $f(g) \gt f(b)$ and we therefore need to expand $b$ before we can conclude that we have found the fastest way to $g$.

- If $f(g) = f(a)$, then we also have $f(g) = f(b)$, but this only happens if the distance between $a$ and $g$ is $0$ and in that case $h(a)$  must also be $0$. We now have both $b$ and $g$ on the open list and their $f$-value is the same and so we expand $g$ as it is a goal node. In this case we do not need to expand $b$.

Had we expanded $b$ first, the exact same thing would have happened and we would have had to expand $a$ as well unless $h(b)$ was $0$. In other words, taking the lowest $h$-value first has no influence on the number of nodes expanded unless it is the case that $h(x) = 0$, in which case it does make sense to expand this node first. Note however, that only if the actual distance from $x$ to the goal is also $0$ (it could be more that $h(x)$) do we actually save a node from being expanded. So while A* always expands all nodes with $f(x) \lt C^*$ and never expands nodes with $f(x) \gt C^*$, the nodes with $f(x) = C^*$ could be expanded or not expanded depending on your tie-braking and the structure of the graph.


Is it possible to have multiple languages accepted by a DFA? Is it possible to have multiple languages in a DFA? in my example in the image, I think the language L={w | w = 0x where x is {0}* } is accepted and the language L={w | w = 0x11 where x is {0}* } could be accepted as well.

Revisit the definition of the language a finite automaton accepts: it is the set of exactly the words the automaton has an accepting computation for. All these words, but no others. This set is always unique.

Here, the accepted language does indeed have subsets

$\{ 00x \mid x \in \{0\}^* \}$ and
$\{  0x11 \mid x \in \{0\}^* \}$.

You will have to check if that are really all accepted words. This may be simpler to do after minimizing the automaton.


Relationship between Undecidable Problems and Recursively Enumerable languages I have read the Wikipedia article on Recursively Enumerable languages. The article suggests that the halting problem is recursively enumerable but undecidable. My idea till today was that the halting problem belongs to a class of languages which are not even recursively enumerable. But the article suggests that the halting problem is recursively enumerable. My doubt is about the relationship between undecidable problems and recursively enumerable languages. Are all undecidable problems recursively enumerable languages?

If there is a problem which belongs to the class of non recursively enumerable languages, will it be always undecidable?

Also could any one suggest a problem which is not even recursively enumerable?

Are all undecidable problems recursively enumerable languages?

No. See my answer to your third question.

  If there is a problem which belongs to the class of non recursively enumerable
  languages, will it be always undecidable?

Yes. In particular, recursive (decidable) languages are a subset of the recursively enumerable languages, so anything that's not recursively enumerable isn't recursive (decidable).

  Also could any one suggest a problem which is not even recursively enumerable?

The complement of the halting problem is not recursively enumerable. Suppose that it were. Then you could begin recursively enumerating the set $H$ of halting programs at the same time that I'm recursively enumerating the set $H'$ of non-halting programs. Every program would eventually be listed by one of us; if you listed it, you'd shout "accept" and I'd stop enumerating, and if I listed it, I'd shout "reject" and you'd stop enumerating. We'd have an effective procedure for deciding the halting problem.

Note that this generalizes: the complement of any recursively-enumerable (but non-recursive) problem is non-recursively-enumerable, for the reason outlined above.


How do you call alternatives in the grammatical productions? I have encountered a question, which asks what is a syntactic form. This motivated me to ask myself, what is the anatomy of the grammatic rule,

     S ::= A | B | C

Anatomy established that S is called LHS whereas A | B | C is called expectedly RHS. But, how do you call the individual alternatives within the RHS? Is it related to your syntactic forms?

how do you call the individual alternatives within the RHS?

As @Rafael mentioned, they are called alternatives.

Parsing Techinques: A Practical Guide, 2nd ed. (2008) by D. Grune and  C.J.H. Jacobs, page 15:

  There is a more compact notation, in which several right-hand sides for one and the same left-hand side are grouped together and then separated by vertical bars, |. This bar belongs to the formalism, just as the arrow $\to$, and can be read “or else”. The right-hand sides separated by vertical bars are also called alternatives.

  Is it related to your syntactic forms?

From the same source (p. 13):

  Non-terminals [S, A, B, C in the example] are called (grammar) variables or syntactic categories in linguistic contexts.

It seems the terms syntactic form and syntactic category are used somewhat interchangeably.
So, if an alternative is a variable, then it represents a syntactic form, but if it has more complex structure (it can contain terminals, or several non-terminals), then we might say that from the point of view of the grammar's author the alternative does not represent a syntactic form. But someone else can always turn it into one by defining a new non-terminal with an appropriate RHS.

Since B.C. Pierce's syntactic forms include terminals (true, false, 0), I agree with the accepted answer that the term syntactic form is used somewhat informally and is not defined precisely.


Compute the Hamming code with odd parity for the memory word 1101 1001 0001 1011 This is the problem I have:

  Compute the Hamming code with odd parity for the memory word 1101 1001
  0001 1011 (2 pts.). In your solution, mark the parity bits as in the
  following example, where parity bits are: 3, 5, 11, and 13

0001 0100 1011 1100 1001 1
  P  P      P  P

  Note: This is only an example on how you should mark the parity bits.
  It is not a correct code word by any means.

There are 2 things I do not understand:

A 16-bit memory word needs 5 check bits from this formula $2^k -1 \ge m + r$,
where m is the number of data bits and r the number of check bits. But in the exercise we have just 4 check positions.
The check positions usually occupy the positions that are power of 2, for example $2^0$, $2^1$, $2^2$... So why are they asking to use other positions for the check bits?

They clearly say that the example is only given as an example. If you believe you need 5 parity bits - use 5 bits. They use 4 bits in their example for no good reason.
True, they still wish you to mark it clearly. I guess the reason is (a) to make sure you know that the parity comes in powers of 2, and (b) to ease their grading. note you should not use positions 3,5,11, and 13! these are again only their example, and the note below the example clarifies you need not pay attention to it.

(at least, that's the way that I understand the question. There is a small ambiguity there that allows one to understand it the way you did)


Big-O notation for nested loops that might skip iterations When you have an algorithm that may skip a lot of iterations due to a hash table lookup, do you still count the iterations that are exited immediately?

Hypothetical example:

var n = input.length; //eg, [1,4,6,2,0,8]

for (var i = 0; i < n; i++) {
  visited[i] = true;

  for (var j = 0; j < n; j++) {
    if (visited[j] === true) {
      continue;
    }
  }
}

Another example:

function dfs(node) {
  if (visited[node]) {
    return 0;
  }

  visited[node] = true;

  var edges = edges[node];

  for (var i = 0; i < edges.length; i++) {
    dfs(edges[i]);
  }
}

//dfs(graph_that_has_cycles);

If the average number of times the inner loop is $O(f(n))$ then the total complexity is $O(n \times f(n))$.

Finding that average can be tricky when the condition is not trivial. however assuming that it never drops a loop will give you a worst case. This worst case will also be valid when the amount of inner loops skipped is a constant factor.

However in the first example the loop can be simplified to

for (var i = 0; i < n; i++) {
  visited[i] = true;

  for (var j = i+1; j < n; j++) {
      //...
  }
}

This is $O(n^2)$. Because $\Sigma_{i=0}^n i = \frac{n(n+1)}{2} = O(n^2)$


How to use Pumping Lemma for $L = \{www | w∈\{0,1\}^*\}$ I'm trying to understand how to use a contradiction proof via the Pumping Lemma to prove a language is not regular. Everybody always uses examples like $\{ 0^n1^n | n>=0\}$, where it can be broken up into two parts $xy$ and $z$ and where these parts are different. How can I apply it to a language consisting of the concatenation of 3 identical strings?

Let's take the alphabets as a and b in-order to avoid confusion.

Suppose that A1 is a regular language. Let p be the “pumping length”
of the Pumping Lemma. Consider the string $s = a^pba^pba^pb$. Note that $s ∈ A1$
since $s = (a^pb)^3$, and $|s| = 3(p + 1) ≥ p$, so the Pumping Lemma will hold.

Thus, we can split the string $s$ into 3 parts $s = xyz$ satisfying the conditions.

i. $xy^iz ∈ A1$ for each $i ≥ 0$

ii. $|y| > 0$,

iii.$ |xy| ≤ p.$

Since the first $p$ symbols of $s$ are all $a’s$, the third condition implies that $x$ and $y$ consist only of $a’s$. So $z$ will be the rest of the first set of $a’s$, followed by $ba^pba^pb$.

The second condition states that $|y| > 0$, so $y$ has at least one $a$. More precisely, we can then say that

$x = a^j$ for some $j ≥ 0$,

$y = a^k$ for some $k ≥ 1$,

$z = a^mba^pba^pb$ for some $m ≥ 0$.

Since $a^pba^pba^pb = s = xyz = a^ja^ka^mba^pba^pb = a^{j+k+m} ba^pba^pb$, we must have that $j + k + m = p$. The first condition implies that $xy^2z ∈ A1$, but

$xy^2z = a^ja^ka^ka^mba^pba^pb$

$ = a^{p+k}ba^pba^pb$

since $j + k + m = p$. Hence, $xy^2z$ not an element of $A1$ because $k ≥ 1$, and we get a contradiction. Therefore, $A1$ is a nonregular language.


Limits to the definition of a language Is there any limit to what we can define as a language? Is any set of symbols a language?

For example, given the alphabet $\Sigma$, do we say that the language $L = \Sigma$ has alphabet $\Sigma$?

Also, what is the intuitive modern equivalent to languages (as defined WRT complexity classes)? I always hear languages described as problems, but what are we really saying when we say that a language is a problem?

Is there any limit to what we can define as a language?

No. Any set of strings over some alphabet is a language. Typically, in computer science, we're only interested in the case where the alphabet is finite and usually, though not always, we only consider finite strings, too.

  Is any set of symbols a language?

A set of symbols is an alphabet. A language is a set of strings whose characters are in some alphabet, though you could also consider an alphabet to be a language of words of length 1..

  For example, given the alphabet $\Sigma$, do we say that the language $L=\Sigma$ has alphabet $\Sigma$?

As above, yes.

  Also, what is the intuitive modern equivalent to languages (as defined WRT complexity classes)?

A language is a language; the definition hasn't changed over time so I'm not sure what you mean by a "modern equivalent". A complexity class $C$ is a class of languages, classified by the amount of some resource (typically time or space) required to determine whether, for some $L\in C$, an input word is a member of $L$.

  I always hear languages described as problems, but what are we really saying when we say that a language is a problem?

Languages and decision problems are essentially the same thing. Given a language $L$, the corresponding decision problem is "Given a word $w$, is $w\in L$?" More formally, a problem is a collection of objects of some kind (e.g., graphs or formlas) such as the 3-colourable graphs or satisfiable 3CNF formulas. A language then, is an encoding of the elements of a problem as strings, e.g., strings representing the adjacency matrices of 3-colourable graphs.


Why does this sort algorithm work? The following O(n^2) sorting algorithm works but I can't figure out why.

array a // length n, indexed 0 to n-1

for ( i = 0; i < n; i++)
   for ( j = 0; j < n; j++)
       if(a[i]<=a[j])
            swap(a[i],a[j]);

It seems it is not bubble sort as after a single iteration neither the minimum or maximum is in place. (And also it needs n^2 comparisons instead of n*(n-1)/2)

How would you prove this algorithm sorts ? How is this sort algorithm called?

An execution of the sort for the example :

initial target
194600925
592040703
20865352
814014281
792862803

target after iteration 0
814014281
194600925
20865352
592040703
792862803

target after iteration 1
194600925
814014281
20865352
592040703
792862803

target after iteration 2
20865352
194600925
814014281
592040703
792862803

target after iteration 3
20865352
194600925
592040703
814014281
792862803

target after iteration 4
20865352
194600925
592040703
792862803
814014281

It is a variant of bubble sort, however the endpoints of the array shift throughout the progress of the algorithm.

In particular it maintains the following invariant:

  at the end of the $i$-th iteration, the elements in indices $1..i$ are sorted.

At the first step it finds the maximal element and puts it in index 1.
(prefix length =1). Then, at every iteration $i$ it adds the element in position $i$ to the prefix, and performs a (degenerate) bubble sort on the first $i$ indices. This bubble sort takes only one step since except for the one new element, the other $i-1$ elements are already sorted. The maximal element will now be at position $i$. The length of the sorted prefix keeps increasing at every iteration until the entire array is sorted.

I don't know if this sorting approach has a name. It looks like a type of insertion sort.


Best way to translate while loops to functions for software verification I have a verification engine where while loops are translated into functional code, like this:

def f() = ... while(c) b ...

def f() = ... fwhile() ...
def fwhile() = if(c){ fwhile() }

We want for the users to be able to annotate while loops with a decreases construct which says that certain measure decreases at each iteration. This is used to prove termination as follows:

while (x > 0) {
 decreases(x)
 x = x - 1
}

The problem is that the checker of the decreases uses the hints given by the preconditions of the functions it is working with. We cannot specify that the precondition is the while loop condition since it may be false at the first call. From my side, I proposed the following translation:

def f() = ... if(c) fwhile() else ...
def fwhile() = b if(c) fwhile() else ...

I would like to have some feedback on the correctness of my approach as well as if there are any better options, since still this will require moving in function f a part of the while which should be naturally contained in the fwhile function.

I recommend that you translate

while(c) b

to

def myWhile() = if (c) then (b ; myWhile())
myWhile()

With this translation, the precondition of myWhile is the loop invariant of the original while loop.  So, this becomes the question of how to find the loop invariant of a loop.  In general, that requires manual annotation.  If you do a search, you should be able to find a lot of information on finding loop invariants.


Synchronisation and ordering in distributed systems I have been wondering, what are some ways to handle synchronisation and/or sequencing issues in distributed systems. For example, assume multiple homogeneous nodes listening on a stream of messages and updating a data store based on those messages. Let's say 2 updates for a particular record enter the queue, one at t1 and the other at t2 (t2 > t1). Further, the t1 packet is consumed by a node n1 and the other one by n2. Now, what would happen if due to computational or network latencies, n2 processes the packet earlier than n1 and updates the data store. Since n1 has an older update, it should not update the data store.

One way I can think of, is to maintain a per attribute versioning of the record and generate a sequence number for each message based on which updates should be made. We could also use timestamps but we would run into issues if the clocks across the nodes drift.

Is there a standard universal way of tackling these sequencing issues? Is this what ZooKeeper does? Are there any interesting reading materials on this topic?

At a high level, you are considering consistency models (@wiki) in distributed systems, like a distributed replicated data store in your example. Consistency models specify what values may be returned by a read given that memory operations may only be partially ordered. Note that this has imposed restrictions on the order in which all the operations are performed.
There are lots of different consistency models, as indicated in the wiki article. Informally each of them defines a partial order over the operations. One of the common implementation methods is to utilize broadcast service. Not surprisingly, there are various broadcast service with different ordering (what you are probably interested in) and reliability (concerning fault tolerance) requirements. The following description is quoted from Chapter 8 "Broadcast and Multicast" of the book "Distributed Computing: Fundamentals, Simulations, and Advanced Topics (2nd Edition) By Hagit Attiya and Jennifer Welch. 2004.":

Ordering: Do processes see all messages in the same order or just see the messages from a single process in the order they were sent? Does the order in which messages are received by the broadcast service preserve the happens-before relation?
Reliability: Do all processes see the same set of messages even if failures occur in the underlying system? Do all processes see all the messages broadcast by a nonfaulty process?

This Technical Report: A Modular Approach to Fault-Tolerant Broadcasts and Related Problems; 1994 gives a more comprehensive formal framework of broadcast service. It has also related the consensus problem with atomic broadcast. Consensus is also popular in distributed data storage systems, by implementing a replicated state machine.

As for your comment:

I would also be interested in any implementations of these which are in production or used by large scale companies?

Most distributed storage systems have considered such consistency models issues and their implementations. Again, different storage systems are targeted for different application scenarios, and thus adopt different consistency models and implement different ordering strategies.
I will name a few keywords and it is not difficult for you to find papers or articles about them: Amazon's Dynamo, Yahoo!'s PNUTS, Google's Bigtable, ZooKeeper, COPS@SOSP'11, Cassandra, HBase, ...


What type of function is main()? As the functions are of 2 type:1.Pre-defined/library functions,2.User defined functions.

What type of function is main() function?

This doubt comes in my mind while writing a program we define the main() function as we do the others.

Please help!!!

Library functions are functions that somebody else coded, and are available for use.

User-defined functions are functions that the user defines. This is the case of the C/C++ main().

You can think of main() as a placeholder or hook. The user supplies it, but the standard library knows to call it after initializing itself.


Converting CFG from GNF to CNF I am working with grammars that need to be in Greibach Normal Form. I want to check whether a grammar recognises a string. In order to perform CYK the grammar would have to be converted into CNF. Is there an established way of carrying out such conversion?

You can just apply the usual procedure that converts any context-free grammar (CFG) to Chomsky normal form (CNF), since a CFG in Greibach normal form (GNF) is still a CFG.

In the case of GNF, the task is, in fact, easier. All you need is to apply the following two rules repeatedly, as described by Wikipedia, until there is no nonsolitary terminals nor more than 2 nonterminals on the right-hand sides of the production rules.

Eliminate rules with nonsolitary terminals. In the case of GNF, this is used to eliminate the first terminals in the production rules.
Eliminate right-hand sides with more than 2 nonterminals.


Constraint-based Type Inference with Algebraic Data I am working on an expression based language of ML genealogy, so it naturally needs type inference >:)

Now, I am trying to extend a constraint-based solution to the problem of inferring types, based on a simple implementation in EOPL (Friedman and Wand), but they elegantly side-step algebraic datatypes.

What I have so far works smoothly; if an expression e is a + b, e : Int, a : Int and b : Int. If e is a match,

match n with
  | 0 -> 1
  | n' -> n' * fac(n - 1)`,

I can rightly infer that the t(e) = t(the whole match expression), t(n) = t(0) = t(n'), t(match) = t(1) = t(n' * fac(n - 1) and so on...

But I am very unsure when it comes to algebraic datatypes. Suppose a function like filter:

let filter pred list =
  match list with
    | Empty -> Empty
    | Cons(e, ls') when pred e -> Cons (e, filter ls')
    | Cons(_, ls') -> filter

For the list type to remain polymorphic, Cons needs to be of type a * a list -> a list. So, in establishing these constraints, I obviously need to look up these types of my algebraic constructors - the problem I now have is the 'context-sensitivity' of multiple uses of algebraic constructors - how do I express in my constraint equations that the a in each case needs to be the same?

I am having trouble finding a general solution to this, and I am unable to find much literature on this. Whenever I find something similar - expression based language with constraint-based type inference - they stop just short of algebraic datatypes and polymorphism.

Any input is much appreciated!

See: Mini ML Specifically the Type Inference section.

This contains sample code in F# for a complete parser of a simple functional language. More importantly the Type Inference section implements the Hindley-Milner algorithm which is what is found in most type inference system. The author also provides links to two other important documents to help in understanding Hindley-Milner; one being a kind of high level introduction and the other being a paper that describes the implementation of the algorithm in code.


Heap Data Structures What is the difference between min heap and max heap? is it possible to shuffle the elements during insertion time? If so then how come the complexity is  logn

The difference between min and max heap is in the invariant holding before and after any insertion or deletion.
Namely in a max heap the keys of the son's of a node are always smaller then the node itself (i.e. biggest key is root). In a min-heap the son's keys are always bigger (i.e. smallest key is root).

When inserting a new node with key x you insert it in the first empty leaf of the structure (usually the leftmost leaf). this will probably invalidate the invariant, therefore we need now to adjust the heap. just compare the newly inserted node's key with its parent recursively and swap them if the heap invariant doesn't hold.
Repeat the adjusting step until the father is smaller/bigger than it's son [minheap/maxheap].
The complexity of an insertion is log(n) because the heap always has a height of log(n) and the adjusting part of the insertion (which is also the most expensive) starts from a leaf (the node we just inserted) and brings it (in the worst case) to the root.

for more material see: https://en.wikipedia.org/wiki/Min-max_heap


What strategy should I use to sovle this interview problem? May I apply DP on this? The problem description is as below and it feels like a DP problem but I am not sure, thank you for helping!

You have a certain dose of a drug, say, 200 milliliters, and now some patients need this drug. The doses for each patient may vary from person to person, for example, 2.5 milliliters for A, B, C, 5 milliliters for D, E, and 7 milliliters for F, and so on. The question is, in short, how can you allocate the drugs so that you have the least amount of drugs left?
Example input: total drug dose 10 (milliliters).
A needs 3, B needs 5, C needs 2, D needs 4, E needs 2.
Output: A, B, C or A, B, E (perfect allocation with no drugs left).
Note: there may be decimals.

I appreciate any hints or solutions to this problem.

This problem is NP-hard. The decision problem, whether a perfect allocation exists, it self is NP-hard. The decision variant is actually the same as the subset sums problem. Given a set of numbers $S$ and a target number $k$, is there a subset of $S$ that sum up to $k$. The problem itself is a variation of the Knapsack problem.

However, the subset sum problem and the knapsack problem are both weak NP-hard problem. Both admit pseudo polynomial dynamic programming solutions (polynomial in the values of the input). So here is a dynamic programming solution for your problem. For each $i \in \{0, \dots n\}$, let us define the function $dp_i : [M] \rightarrow {0, 1}$, where $M$ is the sum of all needs of drugs from all patients. Now set $dp_0(0) = 1$. And for each $i$, we compute $dp_i$ as $dp_i(k)$ equals to 1 if and only if there is a subset of the first $i$ patients that need exactly $k$ units. The transitions are as follows:
$$dp_i(s) = \max\{dp_{i-1}(s), dp_{i-1}(s) - \mathrm{need}(i)\}.$$

An efficient way to implement it is by using bitwise operations on bitsets (a standard trick), where $dp_i = dp_{i-1} | (dp_{i-1}<< \mathrm{need}(i))$, where $|$ is logical or-operator and the $<<$ is left-shifting.


Question on the paper ``Self-Testing/Correcting for Polynomials and for Approximate Functions'' I am having some trouble really getting to a precise understanding of some of Self-Testing/Correcting for Polynomials and for Approximate Functions and would greatly appreciate help. Here is my understanding of section 3, Self-Testing Polynomials.

My main problem is that the definition of the function $g$ seems to require a theorem that isn't cited. Details below.

One is given a program $P$. This program (supposedly) computes a polynomial function $f$. This polynomial $f$ is defined implicitly by saying that $f$ is the interpolating polynomial, over some finite field $F$, of data points $(x_0,y_0)$, $(x_1,y_1)$, $\dots$, $(x_n,y_d)$. In other words, $f$ is the lowest degree polynomial satisfying for all $i=0,1,\dots,d$, $f(x_i)=y_i$. In any case, $P$ ought to be very quick to compute, the best case scenario certainly being where $P$ is a list of (supposedly) all values of $f$ pre-computed.

One wants a quick way to verify that $P$ does its job as advertized, at least mostly.

During the proof that the program Polynomial Self-Test has the desired properties, one introduces the function $g$ defined as
$$\forall x\in F,\quad
g(x)=\mathrm{maj}_{t\in F}
\left\{\sum_{i=1}^{d+1}\alpha_i P(x+i\cdot t)\right\}$$
where the $\alpha_i$ are the field elements that satisfy, for any polynomial $Q$ of degree $\leq d$,
$$Q(X)=\sum_{i=1}^{d+1}\alpha_i Q(X+i\cdot T)$$
These exist and can be defined in terms of the inverse of a Vandermonde matrix, and the paper even tells us they are binomial coefficients up to a sign.

The goal is nicely summed up by the authors: prove that under certain circumstances, the function $g$ thus ``defined'' is indeed the interpolating polynomial of the data, and mostly agrees with $P$:

  It is not clear to me how to interpret the definition of $g$. There are two definitions one could come up with:

    1) $g(x)$ is the value that comes up most often from all the $\sum_{i=1}^{d+1}\alpha_i P(x+i\cdot t)$, but this would require us to break ties (probably arbitrarily). This is unacceptable considering a lemma further down that tells us that under certain conditions $g$ is precisely the function $f$ sought after

    2) If we consider the totality of values $\sum_{i=1}^{d+1}\alpha_i P(x+i\cdot t)$, for all $t\in F$, there always is a $50\%+\epsilon$ majority of one value. In which case the definition is unambiguous, but which would require a proof, likely saying that if $\delta$ is small enough (and hopefully ``small enough'' can entirely de defined in terms of $d$ and $\delta$, i.e. not using the cardinality $|F|$ of the finite field $F$)

    2') Or we could leave $g$ undefined in those cases where no $50\%+\epsilon$ majority arises, but that would surely make the analysis more complicated.

  It seems only the second one makes sense, and when considering a proof that comes afterwards, it seems this is indeed the definition they are using. However, it would require proof that with $\delta$ small enough, a  $50\%+\epsilon$ always happens.

Here $1-\delta$ is defined as (I believe there is a typo in the paper here):

When doing a similar analysis with $F_2$-linear maps $F\to F_2$ for a field of characteristic $2$, there is a very cute result from representation theory that tells us that if $f$ satisfies the defining equation of a linear map ``$f(x+y)=f(x)+f(y)$'' often enough, then it agrees with an actual linear map at least as often (in terms of Hamming distance). It seems the authors are aiming for a similar result here, but there is a piece missing as far as I can tell.

The definition of $g$ should be interpreted in the following way:

  Any function $g$ for which $g(x)$ is a majority value of $\sum_{i=1}^{d+1} \alpha_i P(x+i\cdot t)$ satisfies what follows.

Since it is later proved that $g = f$, it follows that $g(x)$ is always a strict majority (if it weren't, you would be able to define two different realizations of $g$, and prove that both of them are equal to $f$, contradicting their being different).

If you don't like this interpretation, you could fix a tie-breaking rule and use it to define $g$ conclusively. For example, you could take $g(x)$ to be the smallest majority value of $\sum_{i=1}^{d+1} \alpha_i P(x+i\cdot t)$. The exact tie-breaking rule makes no difference, since the proof shows that it is never actually used.

This kind of definition is common in the literature, and it is best to get used to it. Sometimes the authors explicitly mention that ties can be broken arbitrarily, but otherwise it is just implicitly assumed.


How do I prove a certain upper bound on the runtime of a probabilistic 2-SAT solver? As a homework we had to prove a set of upper bounds on a given probabilistic algorithm to find a satisfying assignment for a satisfiable 2-CNF formula. The problem is reproduced below. I'm sorry for all the incorrect language; English is not my native language and scientific language is especially difficult for me.

  Observe the following algorithm:

    input: A 2-CNF formula $F(x_1,\dots,x_n)$ with $n\ge1$ where each clause contains two literals.

    Choose an arbitrary assignment $a$ for $x_1,\dots,x_n$
    while $F(a)=0$ do
     select a clause $C$ from $F$ with $C(a)=0$
     select a literal $l$ from $C$
     flip the value of $l$ in $a$

    output: $a$

  Let $F$ be a 2-CNF formula in $n$ variables (let each clause have two literals without loss of generality) and let $h$ be an assignment that satisfies $F$. Show that the expected runtime of the aforementioned algorithm is bounded above by a polynomial.

  Hint: Show that the following bounds for the expected number of loop iterations $t(i)$, where $i$ is the number of variables in which the initial assignment $a$ differs from $h$, hold:

  $t(0)=0$ and $t(n)\le t(n-1)+1$,
  $t(i)\le1+\frac12t(i-1)+\frac12t(i+1)$ for $i=1,\dots,n-1$,
  $t(i)\le i(2n-i)$ for $i=0,\dots,n$.

It was easy for me to prove upper bounds (1) and (3), where (3) was proved using (1) and (2), but I wasn't able to prove (2). In fact, I believe that (2) might be incorrect.

The idea behind (2) is that when a clause $C$ is chosen in step 3, either one or both literals in $C$ are assigned incorrectly (i.e. not like in $h$) because if both were assigned like in $h$, $C(a)=1$ and $C$ would not have been chosen. Thus, the probability $P$ for increasing the number of correctly assigned literals is greater or equal to $0.5$.

Boundary (2) would work for a probability of exactly $0.5$, but I don't see how this follows. If $t(i)$ would be monotonous, this would be easy to see, but $t(i)$ might not be monotonous. For instance, construct a 2-CNF formula where $h$ and $\bar h$ (where $\bar h$ is $h$ with the value of all literals flipped) are the only satisfying assignments. Obviously, $t(0)=t(n)=0$ and $t(i)>0$ for all $i=1,\dots,n-1$.

Can anybody help me with this proof? I handed in the assignment last Thursday without a conclusive proof for (2), but it bothers me that I was unable to find a solution for (2).

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

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

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

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

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

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

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

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

Now we have

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

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

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

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

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

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

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


Flows with Negative Values? Define a "non-standard" flow to be a flow where the quantity flowing through an edge may be negative.

  Formally, given a directed graph $G$, and two designated and distinct
  vertices $s$ and $t$ (such that no edges are leaving $t$, and no edges
  are entering $s$), a non-standard flow $f : G_E \to \mathbb{R}$ is a
  valuation on the edges such that

  For each $v \in G_V\setminus \{s, t\}$, the sum of the values of $f$
  on the edges entering $v$ is equal to the sum of the values of $f$ on
  the edges leaving $v$.

Assuming all the capacities are positive, does the Max-Flow Min-Cut theorem still hold for non-standard flows?

Furthermore, is there a network with positive edge capacities, such that the maximum non-standard flow through the network is larger than the maximum (standard) flow through the network?

The standard proof for Max-Flow Min-Cut theorem uses the non-negativity of the flow to claim that each flow is smaller than each cut. I would guess that this tells us that the counterexample (if any) would have a cut that has negative flow into its incoming edges.

The maximum flow calculated using only positive flow values on each edge can indeed be smaller than the maximum if flow can also be negative. You can easily see why in a trivial graph with only two nodes and two edges:

  ---- capacity 1 --->
A                      B
  <--- capacity 1 ----

If A is the source node and B is the sink, you can obviously see that if only positive flows are allowed, you get a max flow of 1 but if negative flows are allowed you'd get 2 (with the bottom edge flowing "backwards").

As I commented, the way to figure out the capacity of a graph that allows negative flows as well as positive ones is to restate the problem. Instead of allowing negative flows, add an additional reversed edge everywhere there's a normal edge in the original graph. Then solve the problem with only positive flows. In the trivial example above, you'd have two edges running each direction, and when you found the maximum using only positive flows, you'd get the right answer, 2.


Example of a parsing/rewriting system? I am studying formal languages and playing with writing my own parsers for them. I have a context free grammar parser already that works well. I am wondering if anyone can point me towards actually implemented examples of rewriters. For example, suppose I had the rules

WORD: [A-Z]+

QUOTE: "

And I wanted to input a lot of words,put quotes around each one, and write out the string. Or go back and forth. Something like this:

(WORD [' '])+   <--> (QUOTE WORD QUOTE [' '])+

That seems kind of possible to implement automatically without ambiguity, but I was hoping someone had seen something along that line that already exists.

Thue language is based on string rewriting and it's just 179 lines of c code.

Pure is an LGPL'd functional language based on term rewriting.

Not an example, but a course with really complete slides on the theory of term rewriting systems.


Partition the indices of 2d array to minimize sum of sub-matrices Given an $n\times n$ Matrix $M$, and the indices $[{1,2,3,4,...,n}]$ are divided into several intervals : $[1,x_1],[x_1,x_2],...[x_k,n]$, which further extract several squared sub-matrices along the $M$'s diagonal - $M[1...x_1,1...x_1],M[x_1...x_2,x_1...x_2],...M[x_k...n,x_k...n]$.

Suppose $Sum(Matrix)$ is the sum of all elements in a matrix. How to design an algorithm to find out an optimal partition that minimizes $Sum(M[1...x_1,1...x_1]) + Sum(M[x_1...x_2,x_1...x_2])+...+Sum(M[x_k...n,x_k...n])$

To visualize , find out a partition that minimizes the sum of all shaded elements in the table below

First we note that with $\mathcal{O}(n^2)$ precomputation, where we store the 'prefix sums', we can find the sum of all the elements in a given square subgrid in $\mathcal{O}(1)$ time.

Now, let $DP[i]$ be the optimal answer, if the input matrix had only the first $i$ rows and first $i$ columns. The final answer that we are looking for is $DP[n]$.

The base case would be $DP[0] = 0$.

To compute $DP[i]$, we iterate over all $j$ such that $1 \le j \leq i$, and we consider the last interval in the partition to be $[j, i]$. For a fixed $j$, the minimum sum would be $DP[j-1] + Sum(M[j \ldots i][j \ldots i])$. So that leads to the equation

$$DP[i] = \min_{1\leq j \leq i} (DP[j-1] + Sum(M[j \ldots i][j \ldots i]))$$

So, $DP[i]$ can be computed in $\mathcal{O}(n)$ time, and the whole problem takes $\mathcal{O}(n^2)$ time and space.


Type-system combining type-states and typed effects? Has anyone succeeded in implementing or designing a type-system that combines both type-state (linear types) and effect types (e.g. Koka)?

Edwin Brady has done some work in that area using dependent types in IDRIS. Take a look at his work, in particular Programming and Reasoning with Algebraic Effects and Dependent Types and Resource-dependent Algebraic Effects.


"Functional dependencies" with cardinality constraints Let us write $\{ A_1, \ldots, A_k\} \rightrightarrows^n \{B_1, \ldots, B_m\}$ for a relation $R$ if for all $\langle a_1, \ldots, a_k\rangle$ we have $\left\lvert \pi_{B_1, \ldots, B_m} \sigma_{\bigwedge_{i = 1}^k A_i = a_i} R\right\rvert \le n$ (and $A_i$, $B_j$ are attributes from the schema of $R$), i.e, for any choice of values for the attributes $A_i$ at most $n$ corresponding tuples of values for $B_j$ can be found in $R$. Then $\{A_1, \ldots, A_k\} \rightrightarrows^1 \{B_1, \ldots, B_m\}$ is just the functional dependency $\{A_1, \ldots, A_k\} \rightarrow \{B_1, \ldots, B_m\}$, and $\emptyset \rightrightarrows^n \{B_1, \ldots, B_m\}$ is an upper bound on the number of possible $B_j$-tuples occurring in $R$ (regardless of any selection).

One may come up with a bunch of possible inference rules similar to Armstrong's axioms, for example

reflexivity: $\mathcal{A}' \subseteq \mathcal{A} \implies \mathcal{A} \rightrightarrows^1 \mathcal{A}'$,
augmentation: $\mathcal{A} \rightrightarrows^{n} \mathcal{B} \implies \mathcal{A} \cup \mathcal{C} \rightrightarrows^{n} \mathcal{B} \cup \mathcal{C}$,
transitivity: $\mathcal{A} \rightrightarrows^{n_1} \mathcal{B}$, $\mathcal{B} \rightrightarrows^{n_2} \mathcal{C} \implies \mathcal{A} \rightrightarrows^{n_1 n_2} \mathcal{C}$,
decomposition: $\mathcal{A} \rightrightarrows^{n} \mathcal{B} \cup \mathcal{C} \implies \mathcal{A} \rightrightarrows^{n} \mathcal{B}$, $\mathcal{A} \rightrightarrows^{n} \mathcal{C}$,
composition: $\mathcal{A}_1 \rightrightarrows^{n_1} \mathcal{B}_1$, $\mathcal{A}_2 \rightrightarrows^{n_2} \mathcal{B}_2 \implies \mathcal{A}_1 \cup \mathcal{A}_2 \rightrightarrows^{n_1 n_2} \mathcal{B}_1 \cup \mathcal{B}_2$.

Indeed, by setting $n = n_1 = n_2 = 1$, we obtain Armstrong's axioms.

Let $\Sigma = \{\mathcal{A}_i \rightrightarrows^{n_i} \mathcal{B}_i\}_{i = 1}^N$ be a set of such "cardinality constraints". Again following the conventions from functional dependencies, let us write $\Sigma \vDash \mathcal{A} \rightrightarrows^n \mathcal{B}$ if $\mathcal{A} \rightrightarrows^n \mathcal{B}$ holds in every relation $R$ where all constraints in $\Sigma$ hold. Let $\min_\Sigma(\mathcal{A}, \mathcal{B})$ be the smallest $n$ such that we have $\Sigma \vDash \mathcal{A} \rightrightarrows^n \mathcal{B}$. How can we compute (or bound) $\min_\Sigma(\mathcal{A}, \mathcal{B})$? Is there a way to minimize $\Sigma$ and obtain (the smallest) $\Gamma$ such that $\min_\Gamma(\mathcal{A}, \mathcal{B}) = \min_\Sigma(\mathcal{A}, \mathcal{B})$ for all sets of attributes $\mathcal{A}$, $\mathcal{B}$?

I'd be interested in references or algorithms regarding the constraints defined above. Have they been studied? What is the standard terminology or notation?

After searching around for paper some more (unfortunately, I found nothing in Ling Liu, M. Tamer Özsu eds. Encyclopedia of Database Systems), I managed to find out that these dependencies are called numerical dependencies. In particular, standard notation for my $\mathcal{A} \rightrightarrows^k \mathcal{B}$ is $\mathcal{A} \xrightarrow{k} \mathcal{B}$, which is also referred to as a $k$-dependency.

Unfortunately, they are not finitely axiomatizable:

John Grant and Jack Minker (1985). Normalization and axiomatization for numerical dependencies. In: Inf. Control 65(1), pp. 1-17. https://doi.org/10.1016/S0019-9958(85)80017-6

The entailment problem is in EXPSPACE. However, there is a sound branch-and-bound algorithm that may be used:

Paolo Ciaccia, Matteo Golfarelli and Stefano Rizzi (2013). Efficient derivation of numerical dependencies. In: Inf. Syst. 38(3) pp. 410-429. https://doi.org/10.1016/j.is.2012.07.007

A general survey of the generalization of functional dependencies is

Loredana Caruccio, Vincenzo Deufemia and Giuseppe Polese (2016). Relaxed Functional Dependencies—A Survey of Approaches. In: IEEE Tran. Knowl. Data Eng. 28(1) pp. 147-165. https://doi.org/10.1109/TKDE.2015.2472010

An extension of numerical dependencies is $\mathit{CFD}^c$, conditional functional dependencies with cardinality constraints. This paper defines them, and gives some algorithms for satisfiability and entailment:

Wenguang Chen, Wenfei Fan and Shuai Ma (2009). Incorporating cardinality constraints and synonym rules into conditional functional dependencies. In: Inf. Process. Lett. 109(14) pp. 783-789. https://doi.org/10.1016/j.ipl.2009.03.021


How is the (local) clustering coefficient defined for vertices with degree 1 We want to compute the clustering coefficient $C$ for an undirected graph $G = (V, E)$.

The clustering coefficient $C$ for a graph $G$ is the average over all local clustering coefficients $C_i$, whereby $C_i$ is the local clustering coefficient of a vertex $v_i$ such that $i$ is a generic index and $v_i$ is a member of the network, i.e. $v_i \in V$.

The local clustering coefficient $C_i$ is defined as the ratio between the number of existing edges within the neighborhood of a vertex and the number of possible edges within the neighborhood of a vertex. Therefore, $C_i = \frac{2n}{k_i (k_i -1)}$, such that $n$ is the number of edges within the neighborhood of vertex $v_i$ and $k_i$ is the degree of vertex $v_i$.

For vertices with $k_i = 1$, the denominator becomes $0$ and the whole term becomes undefined.

Given that the clustering coefficient is the ratio between the number of possible edges in the neighborhood of a vertex and the actual number of edges, a vertex with $k_i = 1$ cannot have any edges within its neighborhood, as there no such neighborhood. Hence, is it reasonable to use $C_i = 0$ in cases where $k_i = 1$?

Yes, it is reasonable and common to have $C_i = 0$ when $k_i < 2$. This is sometimes a matter of taste, and some software libraries like igraph lets the user define how to handle the small-degree cases (i.e., whether to return 0 or NaN).


Breaking down CNF clauses I have an assignment where i have to encode certain problem to conjunctive normal form so i can solve it by using SAT solver. I have been able to encode my problem correctly but the solver is quite slow and most likely the cause for this is the length of some clauses which i have.

So my question is:

How can one break down long clauses into smaller ones and therefore speed up the SAT solver, lets say i have following clause:

$ (x_1 \vee x_2 \vee x_3 \vee ... \vee x_n) $ where n can potentially be large number.

Is there any way to split this into smaller clauses which would be logically equivalent?

The reason why the SAT solver is slow is unlikely to be the size of the clauses, but rather the hardness of the problem itself.

In any case, any instance of CNF-SAT can notoriously be transformed into an equisatisfiable formula with at most three literals per clause by replacing each clause in the form:

$$
( x_1 \vee x_2 \vee \dots \vee x_n)
$$

with:

$$
 (x_1 \vee x_2 \vee y_1) \wedge (\neg y_1 \vee x_3 \vee y_2) \wedge \dots \wedge (\neg y_{n-4} \vee x_{n-2} \vee y_{n-3}) \wedge (\neg y_{n-3} \vee x_{n-1} \vee x_n)
$$

where $\{y_i\}_{i \in \mathbb{N}}$ are fresh variables.


diagonal lemma and the negation function Carnap's diagonal lemma asserts that for every computable formula f, accepting a natural number as argument and resolving to {false,true}, there exists a logic sentence s for which:

s $\leftrightarrow$ f($\ulcorner s\urcorner$)

With $\ulcorner s\urcorner$ the Gödel encoding for logic sentence s.

I have a problem with the example function f($\ulcorner s\urcorner$) = $\neg$s. It looks like according to Carnap's diagonal lemma, there exists a logic sentence s for which the following could hold:

s $\leftrightarrow$ $\neg$s

This is obviously, in one way or another, a wrong interpretation of what the lemma says or implies, but I cannot explain why it is wrong ... What's wrong?

The way you've stated the diagonal lemma is odd (and I've not seen it put that way before). The standard phrasing is:

  For every formula $\varphi(x)$, there is some sentence $\sigma$ such that $$PA\vdash \sigma\leftrightarrow\varphi(\ulcorner\sigma\urcorner).$$

Note that there is no $f$ here! Rather, we're talking about properties: intuitively, the conclusion is that PA proves "$\sigma$ is true iff $\sigma$ has property $\varphi$." This makes things a little easier to see, in my opinion: in order to implement your argument we'd want to let $\varphi$ be the formula "is false."

So what your argument lets us conclude is that no such $\varphi$ exists - that is, Tarski's theorem.

Now let's shift to the language of the OP, and see how the version of the diagonal lemma that you state emerges.

Suppose $f$ is a computable function from (codes for) sentences to $\{0,1\}$ (treating $0$ as false and $1$ as true). Then $f$ is representable in PA, say by $\psi_f$. Let $\varphi_f$ be the formula $$\psi_f(\ulcorner\sigma\urcorner)=1.$$ Then applying the diagonal lemma as stated above with $\varphi=\varphi_f$ we get some $\sigma$ such that $$PA\vdash\sigma\leftrightarrow \psi_f(\ulcorner\sigma\urcorner)=1$$ (which could suggestively be written in a minor abuse of notation as "$PA\vdash\sigma\leftrightarrow f(\ulcorner\sigma\urcorner)$" - conflating $0/1$ with true/false and conflating $f$ with its representing formula).

The argument you gives shows that the map $n$ sending a sentence to the truth value of its negation is not computable; more snappily, the set of true sentences of arithmetic is not computable. (Note that this is actually weaker than the conclusion gotten above, since every computable function is definable.)


Finding Degree of match with Soundex or Metaphone I am working on a search where user would search names. Spelling mistakes are bound to happen. I have used edit distance, soundex and metaphone implementations in java so far. Each one separately and then different combinations too. Finally, a combination of soundex and metaphone seemed to work. There are more than 30 thousand names that would be searched for the match when ever a user enters a name. The search is sequential and would stop when ever a match is found. Now the problem is. Lets say in fol figure:-

   User Input Name = "Peeter"

----------------------------------------------------
 Serial       Name
----------------------------------------------------
   1           Tom
   2           Petay (Near match say 70%)
   3           Jack
   4           Peteh (Near Match say 75%)
   5           Peter (The closest Match say 100%)
----------------------------------------------------

The closest match for "Peeter" is "Peter" and near match is "Petay", "Peteh" etc. The search would stop at "Petay", returning "Petay" as the name which would be least expected by the user. So for me, 2 solutions comes to mind.

Search all 30 thousand names every time, get a list of all matches and ask user to choose the best match
Secondly, present 3 or say 5 top matching (by top matching i mean the closest match, let say more than 90% similar sounding) names to user.

I already have implemented option 1 but it returns some times more than 100 matches! it would not be possible for the user to go through all of them. So is there any way to implement option 2 mentioned above? i.e to find out to what degree soundex or metaphone match is made to a name.

Thanks in advance.

You can use K-nearest with the data points you have like % ,freq, or score of the edit and soundex algo.


Residual graph of a graph with bidirectional edges? Let's suppose we have a directed graph $G$ which has at least a pair of vertices $v,w$ such that $(v,w) \in E, (w,v) \in E$.

$e.g:$

In the example, there is an edge going from $C$ to $A$ and viceversa.

So, my question is, what would be the way to model this graph with a residual graph?

The residual graph is not a graph modeling method. It represents how we can change the flow on edges of a graph $G$ in order to increase the total flow when we compute the maximum flow.

The residual capacity used when you construct the residual graph is defined as
$$
  c_f(u,v) =
  \begin{cases}
     c(u,v) - f(u,v)  & \text{if $ (u,v) \in E$} \\
     f(v,u) & \text{if $ (v,u) \in E$} \\
     0 & \text{otherwise}
  \end{cases}\
$$

So, we cannot have both $(u,v)$ and $(v,u)$ in $E$ even though the antiparallel edges do not contradict the main network flow properties.

Your graph contains antiparallel edges which you should get rid of before you run a maximum flow algorithm on that graph, e.g., Ford-Fulkerson algorithm.

You could transform this graph into equivalent one with no antiparallel edges as following. You choose one antiparallel edge and "split" it into two edges. For example take $AC$ and introduce a new vertex $F$ and two new edges $AF$ and $FC$ with weights equal to $5$, i.e., $w(AF)=w(FC) = 5$. Similarly for every pair of antiparallel edges in the graph.


Number of leaf nodes in n-element red-black trees Why the number of (NIL) leaf nodes in n-element red-black trees is n+1?

By definition, a red-black tree is a full binary tree in which each node is assigned either red or black and the leaves are labeled as NIL-node while internal nodes are labeled as non-NIL node. In a full binary tree all of the nodes have either 0 or 2 children. Thus, assuming that a full binary tree has n internal nodes, the number of leaf nodes will be n + 1. So what you are asking is: if red-black tree has n non-NIL nodes why does it have n+1 NIL-nodes ?


Is it possible to have 2 languages with different syntax but the same semantics? I have two questions

Is it possible to have 2 languages with different syntax but the same semantics? If not why not else give an example of 2 languages .

Is it possible to have 2 languages with same syntax but different semantics? If not why not else give an example of 2 languages .

I understand that the syntax is the external visible representation of a program and the semantics is the meaning of a program can some one please help answer these questions thank you.

Sorry if I wasn't clear but I was looking for examples of languages for example for the first question i have C# and VB.NET does that seem appropriate?

Sure. I think it may be hard to answer the question using production languages since you are unlikely to find two "real" languages with identical semantics or identical syntax.

Let's consider a simpler example to illustrate the concepts. Take JSON (which I suppose isn't a programming language, per se, but the idea carries over). Now, change it so that instead of separating key-value pairs with colons we use equals signs and instead of separating items with commas we use semi-colons. Now it looks like this:

{
  "name" = "Bob";
  "age" = 23;
  "titles" = [ "Mr."; "Dr."; "Sir" ]
}

This is clearly semantically the same as the following, syntactically different string:

{
  "name" : "Bob",
  "age" : 23,
  "titles" : [ "Mr.", "Dr.", "Sir" ]
}

A bit of a simple example, but it should illustrate the point.

As far as the other direction is concerned, that is also true. For example, consider the standard for loop found in many languages:

for (int i = 0; i < 10; i++) {
  // do something...
}

This loop runs the initialization step once at the beginning, tests the condition before each iteration of the body, then runs the update step at the end of each iteration. But I could define a language with the same syntax but where the condition is evaluated at the end of the iteration and the update occurs at the beginning. The standard version is semantically the same as:

int i = 0;
while (i < 10) {
  // do something
  i++;
}

whereas my new definition is equivalent to

int i = 0;
do {
  i++;
  // do something
} while (i < 10);

which is clearly different.


What is the algorithmic complexity of this? I'm practicing leet code questions and want to understand more fully how to determine Big O notation. What is the algorithmic complexity of my solution to the following problem?

O(n^2) ? For every item in n I could loop an additional n[i] times. Or is it O(n) ?

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

Input: [2,3,1,1,4]

Output: true

Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

var canJump = function(nums) {

  let validIndices = {};
  for(let i = nums.length - 1; i >= 0; i--) {
    let currentNum = nums[i];
    if(currentNum + i >= nums.length - 1) {
      validIndices[i] = true;
    } else {
      while(currentNum > 0) {
        if(validIndices[i + currentNum]) {
          validIndices[i] = true;
        }
        currentNum--;
      }
    }
  }

  return !!validIndices[0];
};

Your algorithm has O(n^2) worst case complexity. You have a for loop of O(n). Inside your for loop you have a while loop which is O(currentNum). So if your currentNum is O(n) (ex nums[i] = length.nums for each i) then the complexity is O(n*n) = O(n^2).

Hint

Try not to recalculate things. You could use Dynamic programming technique. You need:

def canJump(i):
    if valid[i] has been assigned a True or False value:
        return valid[i]
    #else calculate valid[i]
    if i + nums[i] > len(nums):
        valid[i] = True
        return valid[i]
    for jump in range(1, len(nums[i])):
        valid[i] = any(False, canJump(i + jump))
    return valid[i]

print(canJump(0))

This is just a pseudocode. I have not tried it.
This way you only visit an element of nums once so it’s O(n).

[EDIT]
Actually I am wrong. My code is also O(n^2). Here is an O(n) solution.

at_least = n
for i from n-1 to 0:
    if nums[i] + i >= at_least:
        at_least = i
if at_least == 0: True else False

Now I think this is right. Sorry for the confusion. I got confused too.


maximum coverage version of dominating set The dominating set problem is :

  Given an $n$ vertex graph $G=(V,E)$, find a set $S(\subseteq V)$ such that $|N[S]|$ is exactly $n$, where $$N[S] := \{x~ | \text{ either $x$ or a neighbor of $x$ lies in $S$}\}$$

My question is if the following (new problem) has a definite name in literature, and if not what should be the most appropriate name.

  New Problem: Given an $n$ vertex graph $G=(V,E)$ and an integer $k$ , find a set $S(\subseteq V)$ of size $k$ such that $|N[S]|$ is maximized.

For the second problem, some of the names I have seen in the literature are maximum-graph-coverage; partial-coverage; k-dominating-set, (however, the exact same names are also used in other contexts).

The problem in which you must select $k$ vertices to maximize the number of vertices dominated is known as the budgeted dominating set problem. The problem or its connected variant is studied at least by Lamprou, Sigalis and Zissimopoulos [1] and Khuller, Purohit and Sarpatwar [2]. It also appears in the recent survey of Narayanaswamy and Vijayaragunathan [3].

[1] Lamprou, Ioannis, Ioannis Sigalas, and Vassilis Zissimopoulos. "Improved Budgeted Connected Domination and Budgeted Edge-Vertex Domination." arXiv preprint arXiv:1907.06576 (2019).

[2] Khuller, Samir, Manish Purohit, and Kanthi K. Sarpatwar. "Analyzing the optimal neighborhood: Algorithms for budgeted and partial connected dominating set problems." Proceedings of the twenty-fifth annual ACM-SIAM Symposium on Discrete algorithms. Society for Industrial and Applied Mathematics, 2014.

[3] Narayanaswamy, N. S., and R. Vijayaragunathan. "Parameterized Optimization in Uncertain Graphs—A Survey and Some Results." Algorithms 13.1 (2020): 3.