Right most set bit O(log N) I tried to do the problem Find first set bit in Geeks for Geeks, and this is the code I used.
public static int getFirstSetBitPos(int n){
    int counter = 0;
    while (n > 0){
        if ((n&1) == 1){
            return counter + 1;
        }
        n >>= 1;
        counter ++;
    }
    return 0;
}

The problem asks to solve it in a time complexity of O(logN), and my code is O(N). When I looked at the editorial, it had this solution.
// Java Code for Position of rightmost set bit
class GFG {

    public static int getFirstSetBitPos(int n)
    {
        return (int)((Math.log10(n & -n)) / Math.log10(2)) + 1;
    }

    // Drive code
    public static void main(String[] args)
    {
        int n = 12;
        System.out.println(getFirstSetBitPos(n));
    }
}
// This code is contributed by Arnav Kr. Mandal

I don't understand this return (int)((Math.log10(n & -n)) / Math.log10(2)) + 1; I would appreciate if someone could explain.
I am new to programming and an aspiring competitive programmer.

Questions about programming are off-topic, however there are a few computer science questions hidden in here: what n & -n does, and how floating point is represented.
The n & -n operation isolates the rightmost bit of a word in two's complement arithmetic. This is a very useful operation to know about.
Consider, for example, the following 8-bit word:
10010000

You can find the two's complement of this by taking the logical not of all the bits:
01101111

And then adding 1:
01110000

If you then take the logical and of this with the original word, you get:
00010000

This is the rightmost set bit of the original word. Please try a few examples for yourself to understand how this operation works.
Once you understand that, the rest is simply calculating base-2 logarithm of this number, essentially finding the highest/leftmost set bit, using an unnecessarily complicated method:
$$\log_2 x = \frac{\log_{10} x}{\log_{10} 2}$$
Quite apart from the fact that this is going to raise a floating point exception if you pass it zero (because what's $\log 0$?), and quite apart from the fact that the computational complexity of Math.log10 is not specified in the Java standard, floating-point numbers are stored in scientific notation in base-2 internally. The number $128.0$, for example, is stored as $1.0 \times 2^7$. So this is just an overly-complex way of extracting the exponent field of a floating-point number:
public static int getFirstSetBitPos(int n)
{
    return (int)Math.getExponent((float)(n & -n)) + 1;
}

The idea that you were probably supposed to have, however, is to use some kind of binary search. For a 32-bit integer, for example, you can tell if there is a set bit in the lowest-order 16 bits using a logical and with an appropriate mask:
(n & 0xFFFF) == 0

If there is a bit set in this range, then the answer to your question, the "find first set" of a number, is between 0 and 15, otherwise it's between 16 and 31. Either way, you have halved the search space. Turning this into an algorithm is left as an exercise.


Faster algorithm to search in a set of strings Suppose that we are given a pattern $p$, which is a set of characters (order doesn't matter).  We are also given a set of strings $A$. I want to find all of the strings in $A$ whose characters are all contained in $p$ (without taking the order of these characters into consideration), i.e., to find all $s \in A$ such that every character in $s$ is also in $p$.

The algorithm that I use is to loop every string in $A$ first, and, then, loop every character in each string, so the time complexity is $O(nm)$. My question is: is there any faster algorithm? Bit operation or matrix is ok.

Here is an example:

Pattern "abcdef"

Set A  {a, b, ac, ag, bde, cbd, daf, cg, abzdef, d}

Desired results : a, b, ac, bde, cbd, daf, d

Filtered: ag, cg, abzdef (as g,z don't belong to the original string "abcdef")

You only need to read the strings in set $A$ and the characters in pattern $p$ once. You can store each character of $p$ in a hash table* for (expected) constant time lookup, and, then, perform a linear scan in $A$ to obtain the desired result. The running time of this solution is $O(n+m)$, where $n$ is the length (i.e., the total number of characters) of $A$ and $m$ is the length of $p$.

* A solution that is more space-efficient than the hash table (and guarantees constant time lookup) is to use a bit array $P$ to store pattern $p$. This array will be indexed by the ASCII values of all possible characters that you want to consider in your application; for instance, $P$ will have 26 index positions in the case of the English alphabet: one per distinct character. The $i$-th bit of $P$ will be set to $1$ if the $i$-th character appears in $p$, and to $0$ otherwise. Thus, you can scan $A$ in linear time and discard every string that contains at least one character $c$ such that $P[v_c]=0$, where $v_c$ is the ASCII value of $c$.


Appropriate graph clustering algorithm I'm looking for an appropriate technique to search for clusters. My underlying data is 70,000 respondents to about 2500 multiple choice questions. Most respondents have not answered most questions. I have no expectations as to how many clusters I might expect or how clustered this data might be but am interested to explore if there are personality types wrt. to the kinds of questions asked, and if so, how well defined they are.

My thinking is that the best approach might be to transform the data into a graph and run a cluster analysis on that. Each node is a respondent and each edge is a distance between '0' or '1' derived from how similarly the respondents answered whatever questions they both responded to (or no connection at all, if they answered very few common questions) but I'm struggling to identify an appropriate algorithm for this situation.

Note: it seems likely that this graph setup will violate the principle of triangularity ie. there is no reason to suppose that $ dist(i, \ j) \leq dist(j, \ k) + dist(k, \ i) $ will always hold.

I would treat each multiple choice answer as a "feature" of a given user. If we assume your 2500 multiple choice questions each had 4 possible answers, you would then have a sparse matrix that is 70,000x10,000. You could have a varying number of answers per question and still use this approach.

You could then cluster this via k-means or similar data clustering.

If you really want to do graph clustering, you could treat the sparse matrix as a bipartite graph, with 70,000+10,000 nodes, and edge exists where a user has given a certain answer. You could then apply graph clustering techniques like modularity maximization or graph partitioning.

Detecting these groups/clusters/communities falls under the category of unsupervised learning.


How to determine letter boundaries in Huffman encoded strings? I'm trying to understand the Huffman compression algorithm.

Lets assume the word : YESSSS

According to Huffman tree we will get :

S : 4 times -> Code : 0
Y : once    -> Code : 01
E : once    -> Code : 00

at the end YESSSS will become : 01 00 0 0 0 0

So far everything is clear.

Now my problem is in the space between the binary words. How this can be stored in memory ?

In another words ?

How to computer will know that that :

the first character has two bits
the second character has two bits
the fourth other characters has only one bit

Because 01 00 0 0 0 0 doesn't have the same meaning than 01 00 00 00

01 00 0 0 0 0 means : YESSSS
01 00 00 00 means : YEEE

Any ideas please ?

Huffman codes are prefix-free codes (no codeword is a prefix of another), and so they are uniquely decodable. That means that if you encode a message using a Huffman code, then there is no other message that results in the same encoding.

Here is why. Suppose that $w$ is some binary string. We will show that $w$ encodes at most one message, in the Huffman code $\{c_1,\ldots,c_n\}$. Let's try to factor $w$ as $w = c_i w'$. I claim that this can be done in at most one way. Otherwise, we would have $w = c_i w' = c_j w''$, and so either $c_i$ is a prefix of $c_j$ or the other way around. If there is no such factorization, then $w$ encodes no message. Otherwise, suppose $w = c_i w'$. Then the first character of the message (if there is any) is $i$, and the rest is encoded by $w'$.

Prefix-free codes can be decoded very efficiently: to find the prefix $c_i$ alluded to in the preceding paragraph, just follow the Huffman tree until you get to a leaf. There is no look-ahead. There is a more general class of codes, uniquely decodable codes, which are codes satisfying what we proved in the last paragraph: every string is the encoding of at most one message. Such codes could require arbitrary large look ahead: consider for example $\{00,10,1\}$ and a word $1 w^n$. If $n$ is even then this is broken up $1(00)^{n/2}$, if $n$ is odd then $10(00)^{(n-1)/2}$. In order to tell which is which, we need to look ahead to the end of the string.

Given that prefix-free codes are easier to decode, but uniquely decodable codes are more general, you could ask: do we gain something by allowing uniquely decodable codes which are not prefix-free? This is answered by the Kraft–McMillan inequality: every uniquely decodable code $\{c_1,\ldots,c_n\}$ satisfies
$$ \sum_{i=1}^n 2^{-|c_i|} \leq 1, $$
and conversely every set of codeword lengths satisfying this inequality correspond to some prefix-free code. So prefix-free codes are as general as it gets.

The proof is not too difficult. Suppose $c_1,\ldots,c_n$ is uniquely decodable, with maximum codeword length $M$. Consider the encodings of all words of length $\ell$. Weight each encoding $x$ by $2^{-|x|}$, and sum. You get
$$ \left(\sum_{i=1}^n 2^{-c_i}\right)^\ell. $$
On the other hand, since the code is uniquely decodable, for each possible length, $2^{-|x|}$ must sum to at most $1$. Since words of length $\ell$ are encoded by strings of length at most $M\ell$, we conclude
$$ \left(\sum_{i=1}^n 2^{-c_i}\right)^\ell \leq M\ell. $$
Taking $\ell$th roots and letting $\ell \to \infty$, we recover the inequality.

For the other direction, suppose that the integers $\ell_1,\ldots,\ell_n$ satisfy $\sum_{i=1}^n 2^{-\ell_i} \leq 1$. Without loss of generality, we can assume that the sum is exactly $1$: otherwise, suppose that the sum is $A/2^B$ (for integer $A$), and add $2^B-A$ new integers equal to $B$.

I claim that either $n = 1$ or there must be a subset of these summing to exactly $1/2$. Indeed, suppose $n > 1$, and arrange all weights in non-decreasing order $\ell_1 \leq \dots \leq \ell_n$, and look at the running sums $2^{-\ell_1} + \dots + 2^{-\ell_i}$. There must be a first index at which they cross $1/2$, say $2^{-\ell_1} + \dots + 2^{-\ell_i} \geq 1/2$ but $2^{-\ell_1} + \dots + 2^{-\ell_{i-1}} < 1/2$. Write the latter sum as $S = A/2^B$, where $B \leq \ell_{i-1} \leq \ell_i$ and $A < 2^{B-1}$. Then $S + 2^{-\ell_i} = (A + 2^{B-\ell_i})/2^B \geq 1/2$, so $A + 2^{B-\ell_i} \geq 2^{B-1}$. Since $2^{B-\ell_i} \leq 1$, we must have $2^{B-\ell_i} = 1$ and $A + 2^{B-\ell_i} = 2^{B-1}$, so $S + 2^{-\ell_i} = 1/2$.

When $n = 1$, the code $\{\epsilon\}$ is a prefix-free code with codeword lengths $0$. For $n > 1$, divide the weights into two sets $L_0,L_1$ such that $\sum_{i \in L_0} 2^{-\ell_i} = \sum_{i \in L_1} 2^{-\ell_i}$. Construct two prefix-free codes $C_0,C_1$ from the lengths obtained by subtracting $1$ from all weights in $L_0,L_1$, respectively. Now glue these codes together by prefixing $C_0$ by $0$ and $C_1$ by $1$.


Variant of TSP: allow each vertex to be visited at most twice We are given a finite set $V$ and a set of distance $d : V\times V \rightarrow R\ge 0$ and we wish to compute a tour. Suppose we allow each vertex to be visited at most twice in the tour. How can we prove this is NP complete?

Let $T = (V,d,k)$ be an instance of Metric-TSP, where $V$ is a vertex set, $d: V\times V \rightarrow \mathbb{R}_{\geq 0}$ is a distance with triangle inequality, and $k\in \mathbb{R}_{\geq 0}$.

Suppose that $T$ is a positive instance of Metric-TSP (i.e. there exists a tour with total length $\leq k$. Then $T$ is also a positive instance for your variant (just take the same tour).

Suppose $T$ is a positive instance of your variant, and let $t = (v_1, v_2,\ldots,v_r)$ denote a "tour" with total length $\leq k$. Whenever there is a vertex $v$ which appears twice in $t$ one can safely delete one of the two appearances as every vertex will still be visited and by the triangle inequality the total length of $t$ can only decrease. Once you have deleted all the duplicates, you are thus left with a tour of length $\leq k$, which shows that $T$ is also a positive instance of Metric-TSP.

Thus, there is a trivial reduction (namely the identity) from Metric-TSP to your variant. As Metric-TSP is NP-complete and your variant is in NP, your variant is also NP-Complete.


Divide two strings to form palindrome Given two strings, A and B, of the same length $n$, find whether it is possible to cut both strings at a common point such that the first part of A and the second part of B form a palindrome.

I've tried bruteforce, and this can be achieved in $O(n^2)$. I'm looking for any kind of optimization that is faster than $O(n^2)$. I'm not familiar with backtracking and DP. So, can anyone throw some light?

Some notations in Python convention

$S[:i]$ means the first $i$ letter of string $S$.
$S[-i:]$ means the last $i$ letter of string $S$. ($S[-0:]$ is the empty string, which is not Python convention.)

$S+T$ means the concatenation of $S$ and $T$.

The problem in clearer terms

Given two strings, $A$ and $B$, of equal length $n$, find whether $A[:i]+ B[-(n-i):]$ is a palindrome for some $i$.

Brute force

For each $i$ in $0, 1, \cdots, n$, we can check if $A[:i]+ B[-(n-i):]$ is a palindrome. This search by brute force runs in $O(n^2)$. Its average time-complexity is $O(n)$ under some reasonable assumptions. It is very easy to implement.

Algorithm in $O(n)$

Let us take a closer look what happens when we get a palindrome. For example,
$$\begin{aligned}
A&=ab12321xy\\
B&=\text{**}5\text{***}4ba\\
C=A[\text{:}7]+B[-2\text{:}]&=ab12321ba\quad \text{which is a palindrome.}
\end{aligned}$$

Note that 12321 in $C$ is a palindrome that sits in the middle of $C$, which is not surprising since the central part of a palindrome is also a palindrome. Since the lengths of $A$ and $B$ are the same, that 12321 should sit in the middle of $A$ as well.

Note the remaining part after $12321$ has been removed, $abba$ is also a palindrome.

The above indicates the following simple algorithm.

Compare the letters at the front of $A$ with the corresponding letters at the behind of $B$ one by one so as to find $i_0$, the largest $i\le n/2$ such that $A[:i]+B[-i:]$ is a palindrome.
Starting from the center of $A$, expand both ways to find the longest palindrome sitting in the central of $A$. Let $c_A$ be its length. If $2i_0 + c_A\ge n$, return yes.
Starting from the center of $B$, expand both ways to find the longest palindrome sitting in the central of $B$. Let $c_B$ be its length. If $2i_0 + c_B\ge n$, return yes.
If we have reached here, return no.

Exercise

Given two strings, $A$ and $B$, devise an $O(n)$ algorithm that determines whether $A[:i]+ B[-(n-i):]$ is a palindrome for some $i$, $0\le i \le\text{len}(A)$ and $0\le n-i \le\text{len}(B)$.
(This exercise should be easy if you know Manacher's algorithm.)


Efficient membership check in multiple ranges Suppose a program has a set $S$ of $n$ numerical ranges, each described by a pair: (lower bound $l_n$, upper bound $u_n$).

The program receives a number $x$; it must return all ranges in $S$ that enclose $x$.

An example in practical terms: in timeseries data, you have a set of $n$ independent events that occur over ranges of times. Given a point in time, you want to find the events that coincided with that point.

The naîve $O(n)$ solution:

out ← {}
for r in S:
  if (r.l ≤ x and r.u ≥ x):
    out.add(r)
return out

Is there a strategy for sublinear membership checking (in terms of $n$)?

An interval tree can retrieve intervals containing a specified point in $O(\log n)$. If the set of intervals is fixed, it is very easy to implement.


Convert this language to Context Free Grammar I'm having trouble understanding how to convert this language to context free grammar.

$\{a^ib^jc^k\mid i > k, 0\le j \lt3, k \ge 0\}$

Part im getting stuck on is how to deal with a and c, whenever a c is added, you must also add an a, but with them at opposite ends of the string how do you properly build grammar for it? Since the below is not possible:

\begin{align}
C &\rightarrow aC \\
C &\rightarrow c
\end{align}

I've read the below post many times and tried to apply it but still not able to get it.

How to prove that a language is context-free?

Someone able to show me how this can be done?

If you need to prove the language is context-free, showing a PDA that accepts $L$ is enough.

Sometimes, formulating the rules that generate exactly the language $L$ is not so trivial; in such cases you can start by a constructing the PDA that accepts $L$, then convert it to a CFG.

The transformation PDA $\rightarrow$ CFG can be found:

Lecture notes

Answer on this site


How to resolve issue of circular definition for an `If` statement I am trying to define an If statement, but am stuck because the definition/implementation of If is circular from what I have tried. For example, here is one definition:

class If {
  provide: Condition
  provide: TrueBlock
  body:
    If (Condition) {
      call(TrueBlock)
    }
}

You can then use it like this:

If (true) {
  Something()
}

But the thing is, the definition itself uses If to define it:

class If {
  ...
    If (Condition) {
      call(TrueBlock)
    }
}

The only other way I can think of defining it is by saying that an If statement is an "atomic statement", and so it doesn't have an implementation. (The compiler or whatever would then have special instructions to treat it uniquely).

class If {
  provide: Condition
  provide: TrueBlock
}

That would be the whole definition of If. No implementation required.

Wondering if this is sort of the right approach to this problem. The problem being that you can't really implement an If statement without resorting to using If itself. And so you define it as atomic.

One general rule of Turing completeness is that you need some form of conditional branching built into your model. A Turing machine, for example, can transition to a new state based on what it sees on the tape. Programming-language-wise, a while loop works, as does an infinite loop with a conditional break statement, or if and goto.

As such, if you have no form of conditional branching built into your model already, you can't create one out of nowhere—if your model isn't Turing complete, you'll need to add something else from outside to the model to make it so.

An "atomic" if statement will do the trick, certainly, as will something like Lisp's conditional. But whatever it is, it'll have to be implemented by the compiler or interpreter, rather than being created within the language itself.


Time complexity of Vertex Cover vs Clique for fixed k I have 2 ways of solving Independent Set problem of fixed size $k$ for graph $G = (V, E)$:
- Vertex Cover algorithm running in $O^*(1.47^{V - k})$ (optimized recursive algorithm)
- Clique algorithm running in $O({V\choose k})$ (simple enumerate subsets of $V$ and check algorithm)

How can I determine which one has a lower time complexity? I'm not very familiar with algorithms for NP-complete problems and $O^*$ notation. Would plotting those functions suffice? I think that VC algorithm can have any polynomial $n^{O(1)}$ as a multiplication because of the $O^*$ notation and this could affect the running times, but I'm not sure.

For any fixed $k$, $O(\binom{V}{k}) = O(V^k)$ is polynomial, whereas $O^*(1.47^{V-k}) = O^*(1.47^V)$ is exponential. Exponentials grow much faster than polynomials.

Plotting the curves is not so helpful, since these are asymptotic statements.

That said, if you're interested in particular $V$ and $k$, then your best option is to empirically check which of these algorithms is faster. Asymptotic notation is not helpful here, since it hides constant factors, and these could make a big difference for concrete values of $V$ and $k$.


Can I run Dijkstra's algorithm using priority queue? I think I can run Dijkstra's algorithm using any data structure. I do not see any implementation details of Dijkstra's algorithm.

Is a priority queue a possible data structure? Will running Dijkstra's algorithm using a priority queue reduce or increase the complexity? Will I overshoot the problem?

Yes, you can use priority queues to improve the complexity of the algorithm from $O(V^2)$ to $O(|E| + |V| \log|V|)$ where $E$ is the number of edges and $V$ is the number of nodes.

You should consider carefully the number of nodes in your graph and the desired run time before adding complexity to your implementation.

See here for a brief explanation of performance vs difficulty trade offs.

To summarize the blog, using a regular queue can still speed up Dijkstra's algorithm by up to a factor of 4 in most cases, with rarely occurring graphs running in $O(V^3)$. The link says "never" occurring, but that would depend on the actual problem you are solving.

See this for the original research on using min-priority queues to speed up Dijkstra's algorithm, it is the fastest known implementation for Dijkstra's algorithm.


Functional Dependencies and BCNF Consider the following schema:  Students(Id, Name, AdvisorId, AdvisorName, FavouriteAdvisorId)

What are the functional dependencies here? Ir seems that it would be:

 Id --> Name AdvisorId AdvisorName FavouriteAdvisorId

If we know the student id then we know his name, his advisor, his advisor id and his favouriteadvisorid. But the correct functional dependencies given are:

 Id ---> Name FavouriteAdvisorId

 AdvisorId ---> AdvisorName

Why is this?

Perhaps because a student with two majors might have an advisor in each department, so the ID wouldn't uniquely determine the advisor (and hence the AdvisorID and, perhaps, the AdvisorName). Remember, the definition of $A\rightarrow B$ is that if two tuples in the relation have the same value for attribute $A$, they must have the same value for attribute $B$.


Japanese Multiplication simulation - is a program actually capable of improving calculation speed? Or am I doomed from the start? On SuperUser, I asked a (possibly silly) question about processors using mathematical shortcuts and would like to have a look at the possibility at the software application of that concept.

I'd like to write a simulation of Japanese Multiplication to get benchmarks on large calculations utilizing the shortcut vs traditional CPU multiplication. I'm curious as to whether it makes sense to try this.

My Question: I'd like to know whether or not a software math shortcut, as described above is actually a shortcut at all.

This is a question of programming concept. By utilizing the simulation of Japanese Multiplication, is a program actually capable of improving calculation speed? Or am I doomed from the start?

The answer to this question isn't required to determine whether or not the experiment will succeed, but rather whether or not it's logically possible for such a thing to occur in any program, using this concept as an example.

My theory is that since addition is computed faster than multiplication, a simulation of Japanese multiplication may actually allow a program to multiply (large) numbers faster than the CPU arithmetic unit can. I think this would be a very interesting finding, if it proves to be true.

If, in the multiplication of numbers of any immense size, the shortcut were to calculate the result via less instructions (or faster) than traditional ALU multiplication, I would consider the experiment a success.

When considering algorithms for multiplying large numbers, the first think to keep in mind is the asymptotic complexity. Generally speaking, algorithms with better (smaller) asymptotic complexity are faster, though this only goes so far. So the first thing to do to find out whether Japanese multiplication is "worthwhile" is to calculate its asymptotic complexity. You have to be careful with respect to the model of computation, but in your case it probably won't make a big difference; probably your algorithm has "bad" asymptotic complexity.

The second thing to notice is that the multiplication logic is already there in the CPU, and no code that you can write will be faster than calling the built-in multiplication instruction. Of course, this is only good for multiplying machine words (or multiwords, in some cases). That means that your algorithm had better take advantage of the multiplication capabilities of your processor. While not affecting the asymptotic complexity, it does considerably affect the constants. All fast multiplication algorithms use machine multiplication instructions.

The best way to know whether the algorithm is any good in practice is to program and optimize it. Use a language like C which produces fast code, and then you can compare it to libraries such as GMP. This is the only convincing way to claim that your algorithm is better than existing ones, though you should expend some effort on optimization.

Finally, you claim that Japanese multiplication is better than CPU multiplication algorithms since it only uses addition. Textbook multiplication algorithm also only use addition, since everything is in binary. But probably this can be optimized further at the expense of using more gates, by having logic for small multiplications. You can look up what algorithms CPUs use, perhaps they're similar to Japanese multiplication.


How to embed Pearson distance into Euclidean space I have a lot of numerical vectors, each of dimension 1000. I would like to compare them according to their Pearson distance. This works fine but comparing all vectors to each other is quadratic time and too slow. Ideally I would like to be able to perform efficient approximate nearest neighbour searches instead.

If I could embed the vectors into Euclidean space then I could use standard tools to do this.

  Is there a way to embed vectors from a space using the Pearson distance into Euclidean space?

Yes.  Normalize the vectors, then use the Euclidean ($L_2$) distance.

In particular, map the vector $v=(v_1,\dots,v_n)$ to the vector

$$\tilde{v} = ((v_1-\mu)/s,\dots,(v_n-\mu)/s)$$

where $\mu=(v_1+\dots+v_n)/n$ is the mean of the elements and $s=\sqrt{(v_1-\mu)^2 + \dots + (v_n-\mu)^2}$.  (In the special case where $s=0$, define $\tilde{v}=(1/\sqrt{n},\dots,1/\sqrt{n})$.)  Then the vector $\tilde{v}$ has unit length.

Now the Pearson distance $d_P$ satisfies

$$d_P(u,v) = 1 - \tilde{u} \cdot \tilde{v} = \|\tilde{u} - \tilde{v}\|^2 / 2,$$

where $\|\cdot\|$ is the Euclidean ($L_2)$ norm.  (See here and here for a derivation of the above equation.)

Thus, minimizing the Pearson distance between $u,v$ is equivalent to minimizing the Euclidean distance between $\tilde{u},\tilde{v}$.  So once you've mapped vector $v$ to its embedding $\tilde{v}$, you can use a standard nearest neighbor data structure (with Euclidean distance) to answer nearest neighbor searches.


Parentheses after Typing Environment I've been reading about System F Omega lately, and I keep stumbling across a construct in typing rules that I cannot find an explanation of: Γ(x) = k. For example, in A Short Introduction to Systems F and F Omega:

Γ(a) = k
--------
Γ ⊢ a : k

I see the same construct in Hereditary Substitution for Stratified System F. I understand the bottom part fine. It would read something like: "In context Γ, a has kind k". I've not been able to find an explanation of the top part, and the sources I referenced both assume familiarity with this construct. If I had to guess, I suspect that it means something like "In context a, running a kind-checking algorithm on a gives you kind k as the result". Is that accurate? What online resources describe this construct?

$\Gamma$ here is overloaded notation. The meaning of the expression $\Gamma(x) = \tau$ above the inference line here is given under the "Type rules." section of A Short Introduction to Systems F and F Omega on page 5. In this setting, $\Gamma$ is an inductively-defined function sending variables (in $\Gamma$ considered as a context, i.e. a list of variables) to their types.

A more illustrative, syntactic way to write the rule you give might be: $\frac{}{\Gamma,\ x : \tau\ \vdash x : \tau}$, where $\Gamma$ ranges freely over contexts. Note that the order of variables in a context here does not matter, so this rule allows us to project any variable in a context as a term.


Someone explain the Venn diagram for the logic equation (A+B)(B+C) I posted a similar question  here, however I have another question regarding Venn diagrams and logic circuits...

In this problem:

$$(A+B)(B+C)$$

Wouldn't the Venn diagram look something like this?

Because it simplifies to $B + AC$? And you can either have the $B$ region, the $AC$ region, or both?

However, apparently it's supposed to look something like this:

Which I don't understand... Because by the logic that you have $AB$ and $BC$, couldn't you justify saying that you can also shade in $A$, or shade in $C$ (by themselves)?

OR, does saying $A$ mean you shade in EVERYTHING that contains $A$? And only don't shade in the intersection if you had something that said $A * \overline{B}$?

The misunderstanding here is the same as in your previous question. If $B$ is true, the formula is true whatever the values of $A$ and $C$ are. This means that the whole of the $B$ circle needs to be shaded.  Shading just the part at the top corresponds to saying "The formula is true if $B$ is true and $A$ and $C$ are both false." That is certainly true, but it's not the whole story.

For example, your proposed shading says that the formula is false if $A$ is true, $B$ is true and $C$ is false. But the formula is true in that case! You must shade every region of the diagram that makes the formula true. In this case, that means every region in the $B$ circle, and also the intersection of the $A$ and $C$ circles.  (Corresponding to, "The formula is true if $B$ is true, or if $A$ and $C$ are true, or both.")


On the analysis of Christofides's algorithm Suppose you have even number of vertices, they form as a complete graph denote the graph by $G$. Now, suppose we compute the minimum weight perfect matching denoted by $P$ (so $P$ has alternating edges, i.e. one is a perfect matching and one is not along all the path $P$ through all vertices of $G$). Now, suppose $T^*$ is TSP tour of $G$.

Show that the inequality is true:
$$ \operatorname{cost}(P) \le \min \{ \operatorname{cost}(N_1), \operatorname{cost}(N_2) \},$$
where $N_1$ and $N_2$ are any two perfect matchings on $T^*$.

Note that this inequality from the analysis of Christofides's algorithm, see this nice paper.

Since $P$ is a minimum weight perfect matching, by definition
$$ \operatorname{cost}(P) = \min_N \operatorname{cost}(N), $$
where $N$ goes overl all perfect matchings. In particular, $\operatorname{cost}(P) \leq \operatorname{cost}(N)$ for any particular perfect matching $N$.


How to implement deep copy? Is there any scientific work about deep copying? So far I have only found source codes (Java, Python, ...). However, there are various approaches and nobody seems to evaluate them.

Reflection-based (Python)
Auto-generated shallow-copy-based (Java)
Compiler-generated polymorphic deep copy (anybody?)

The last one seems to be the most efficient one, but I do not know if it is implemented anywhere.

You have to be very careful of what you mean when you say "deep-copying". This came up in a thread at StackOverflow in relation to C++. The first question you need to address is can an automatic "deep-copy" even be done?  Consider just a few basic quesetions:

If the type of a data element is a referential type can you determine whether a deep copy implies copying the reference or the referred to type? That is, can you identify the ownership of these items?
Does the presence of a singleton, or external resource, prevent a deep copy, or does the copy refer to the same resource?
Given that data relations often form graphs with cycles. Could such a relationship automatically be detected? Even if yes, what would if mean to start the deep copy at an inner-node of such a structure?

This is likely why you only find references which are very language specific. Each language has its own notion of copying. This default copy is not likely to match the expected notion of a deep-copy in all situations.

I would say it is not possible to even specify what deep-copy is without explicitly enumerating the types available in a given language. This would essentially require that all research about deep-copying is specific to a particular language (even if that language is theoretical).

If you are looking for efficiency comparisons you would then also be stuck in the domain of a very particular language. You could possible define a reduced compound data type common to several languages and evaluate the efficiency of copying such structures. Such results however would not be applicable to any language with more complex data types.


How does this proof show that sequences of $O(1)$ polynomially bounded Kolmogorov complexity are NOT the polynomial computable ones? I'm trying to understand a proof from the paper: Balcázar, José L.; Gavaldà, Ricard; Hermo, Montserrat: Compressiblity of infinite binary sequences, Published in: Complexity, Logic, and Recursion Theory, A. Sorbi, ed., Marcel Dekker 1997, ISBN 0-8247-0026-0, 75-91.

Theorem 19 For every recursive time bound f , there is an infinite sequence that is in $C4[O(1), poly]$ but not $DTIME(f (n))$-computable. (The sequence is automatically in $C5[O(1), poly]$ and in $CK[O(1), poly]$.)
Proof: The main idea is to build a tally set $T\subseteq\{0\}^*$ with the following properties:

$\chi^T$ is not $DTIME(f (n))$-computable, where $\chi^T$ is the characteristic sequence of $T$ over $\{0\}^*$

$T \in\ DTIME(g(n))$, for some nondecreasing time-constructible time bound $g$ such
that $g(n) \gt f (n)$.

strings in $T$ are very far one from another; more precisely, $T$ contains only strings of
the form $0^{s(m)}$
, where $s$ is defined inductively by:
$s(1) = 1;$      $s(m + 1) = g(s(m))$
[...]

(the proof proceeds by using the third property to show that it's easy/polynomial to create $\chi^{T \leq n}$ up to an uncertainty in exactly one hard bit, and so it is possible to consider two machines, one answering $1$ and an other answering $0$ for it, fulfilling the requirement of $\chi^T$ being in $C4[O(1), poly]$ )
This Theorem is claiming to build a tally set that does the job, and I understand how the proof proceeds, once it is taken granted that the set with the specified properties exists, but I don't see its existence proven.
How do we know that such a tally set exists for every recursive $f(n)$ that is not $\mathrm{DTIME}(f(n))$ computable as specified in property (1)?
And why do we have to guarantee in property (2) that the $g(n)$ bound is greater or equal to $f(n)$?
Am I missing something basic about tally sets, or sets vs characteristic sequences in general, or some trivial hierarchy theorem?

Wow, that was sooooo long ago. Something like the early nineties...

The point is, for that T, at the time of writing, the construction proper was assumed to be well-established in the background knowledge of any potential reader. Thus, we did not give details. Essentially, what you do is a Cantor-like proof as in the non-numerability of the reals: for each i, run the i-th DTIME(f) machine on a string of s(i) zeros, and add that string to T if and only if the simulated machine rejects it. (Colloquially that string was often called "the cookie".) Then g is to be any time-constructible function that allows for this process to be completed - for this we will need it considerably larger than f. There is a slight circularity in that the process depends on s, which depends on g, which is defined as sufficient time to run the process. But it is easy to upper bound this time and select a sensible g.

Hope this helps! (And hope this works. It is my first time writing anything into stackexchange.)


Propositional Logic Time complexity If i have a propositional logic formula, every time i add a variable the number of interpretation grow up by 2.

So if i have a propositional formula with 3 variables i have 8 interpretations.

So, is the time complexity of the SAT problem of propositional logic a $O(2^{x})$ ?

Your question hints at multiple misconceptions which I'm going to address.

  If i have a propositional logic formula, every time i add a variable the number of interpretation grow up by 2.

First, let's be clear about terminology.

variable vs literal -- the formula $a \lor b \land a$ has three literals but two variables.
model vs interpretation -- every logical formula has exactly one of two possible interpretations, true and false.

It would be correct to say: the number of models grows exponentially (with base 2) in the number of variables.

  So, is the time complexity of the SAT problem of propositional logic a $O(2^x)$?

No, that does not follow.

What is $x$? In complexity theory, we usually express complexity in the input length. So if $x$ is the number of literals, that thought makes sense; if it's the number of variables, it does not. However, in the worst cases (if we consider search space alone), the number of variables and literals is the same.
The number of possible models (e.g. valuations of the variables) alone is not trivially an upper bound on the complexity. The brute-force algorithm also has to evaluate the formula for every candidate, so you have to add a linear factor at least (depends on the computational model and cost model you use).
When somebody says, "the complexity is X" that implies a lower bound in addition to an upper bound. Your observation does not provide a lower bound, even after correction.

That is because the size of the search space does not correlate with solving complexity. Take sorting, for instance: finding the correct permutation has a search space of size $n!$ and yet we can solve the problem in linearithmic time. SSSPP is another common example.


How to prove NP-completeness of this mail-problem? Let's say we have n postmen that are bringing people mail in a neighbourhood, and that they start and end at the same post office. This situation can be decribed with a directed graph, where the vertices represent the people's houses the mails are brought to. If the graph has an edge from a to b, it means it is an accepted path to travel. Each postman must go from one house a to the next house b and cannot detour to a house c during that time. The post office manager says that a yes instance to this problem means that there exist n cycles so that

Each of the cycles contains a vertex x (represents the post office).
Every vertex except for x only appears once in each n cycle.
Each n cycle is of equal length.

The manager then wonders how to prove that this problem containing 3 cycles (3 equals n, so there are 3 postmen in this case) is a NP-complete problem?
Thank you.

Given an instance of partition $X=\{x_1, x_2, \dots, x_n\}$ you can build the graph $G=(V,E)$ where $V=\{0, 1, \dots, n\}$ and, for any pair of indices $i$, $j$ with $0 \le i<j \le n$, there is an edge $(i,j) \in E$ of weight $x_i$. Additionally, $E$ contains all edges $(i,0)$ for $1 \le i \le n$ with weight $0$.
The deposit will be vertex $0$. If you are able to find two cycles $C_1$, $C_2$ of the same length then the sets $\{x_i : i \ge 1 \wedge i \in C_1\}$ and $\{x_i : i \ge 1 \wedge i \in C_2\}$ will be a partition of $X$.
Similarly, a partition of $X$ induces two cycles of the same length in $G$.
This shows that the problem is $\mathsf{NP}$-hard even with just $2$ postmen.
You can generalize this reduction to any number $k$ of cycles by adding $k-2$ additional vertices $y_1, \dots, y_{k-2}$ along with all edges $(0, y_i)$ of weight $\frac{1}{2}\sum_{i=1}^n x_i$ and $(y_i, 0)$ of weight $0$.


Does this progressive image compression exists? I want to know if this progressive image compression that I have in mind exists and it it does I want know its name and/or get some references about it.

The algorithm consists of converting one high resolution image in multiple low resolution images (all of the same size, not like in wavelet transform) with the following properties:

If you have one of them, any of them, you can reconstruct a low resolution approximation to the original image.
You can compose many of those in any order to get better approximations to the original image.
If you combine all low resolution images you get the original image or a very good approximation of it without perceptible artifacts.
Algorithm is real-time, i.e. it can display a meaningful partial reconstruction of the original image at any time of the reconstruction process (independently of received sub-images and their order).

Does this algorithm exits? Is it possible at all?

I know about image reconstruction techniques, but those use similar but different images to reconstruct a higher resolution one and the result is always noisy and full of artifacts. This is not I am asking for.

I believe that the Stationary Wavelet Transform (SWT) meets your requirements:
https://en.wikipedia.org/wiki/Stationary_wavelet_transform

1) Any given level of coefficients could be used to reconstruct the original image by running normal reconstruction but assuming zeros for the other levels.

2) Each level of coefficients stores data about a different range of spatial frequencies in the original image, and thus they can be recombined arbitrarily.

3) Unless you quantize when or after you perform the transform, the SWT is lossless.

4) I haven't done any processing time evaluation, but optimized libraries are available: https://www.mathworks.com/help/wavelet/ug/discrete-stationary-wavelet-transform-swt.html

In general though, unless you require translation invariance, you would benefit from the downsampling in the more common Discrete Wavelet Transform (DWT). The downsampling results in smaller images which requires less space to store and time to process. No information is lost by this downsampling as the frequency filters in the DWT filter out and then store (in the higher resolution levels) the frequencies that then get lost in the downsampling. The lower frequencies simply need fewer samples to be accurately reconstructed (https://en.wikipedia.org/wiki/Nyquist_frequency).


Algorithm for automatic construction of natural deduction proofs I was wondering if there exists any algorithm for automatic construction of nautral deduction proofs. I'm interested in propositional logic and first order logic.

If there is no algoritm, can you provide some proof of this fact?

PD0: I'm not interested in any page for solving these kind of problems. My question is more theorical.

PD1: This is not homework, just personal interest.

Usually we require the theorems of a proof system to be recursively enumerable, so you can at least write an algorithm that will eventually produce a proof of any theorem. This is usually a relatively easy algorithm to implement. Of course, if you give it something that is a non-theorem, you won't be able to tell with this approach.

For classical propositional logic, we could, of course, use truth tables to check whether something is a tautology first, and then do this search for a proof. This would give a computable (i.e. recursive) algorithm. It would be more direct and efficient to use a constructive proof of completeness for classical propositional logic though. There are certainly even more direct and efficient ways to search for a classical propositional logic proof.

For intuitionistic propositional logic, there is the proof system LJT described in Contraction-free sequent calculi for intuitionistic logic and implemented in tools like Djinn.

Theoremhood for a first-order theory in (classical or intuitionistic) first-order logic is generally not computable. Some particular first-order theories are decidable, but most aren't. They are at least semi-decidable via the argument in the first paragraph. There are, of course, tons of automated theorem provers that will attempt to find proofs, but they may fail. For theorems, they may fail due to resource limitations1. For non-theorems, they just don't have a way of showing that something is contingent. They could find a proof for the negation of your formula, but that technically doesn't rule out your formula being a theorem since your theory could be inconsistent. Model checking techniques could be used to attempt to find counter-models to show that some formula can't be a theorem (but may still be contingent). Most model checking tools are not aimed at full first-order logic though. They have essentially the same theoretical and practical limitations as automated theorem provers.

1 Just because something is computable doesn't mean it's computable within our universe.


Lower Bound for Time Complexity of Pairing Problem Given an array X and array Y both of length n, the pairing algorithm will return the elements of the arrays matched so that the smallest element in X will be matched with the smallest element of Y, the second smallest in X matched with second smallest in Y and so on. i.e the algorithm will yield the pairs: $(x_{1},y_{1}),...,(x_{i},y_{i}),...,(x_{n},y_{n})$, $x_{i}$ being the i'th smallest element in X.
I need to find the lower bound for the time complexity of the problem.

I think the lower bound is O(n) because when the two arrays are sorted we only need to match the elements with the same index in each array - so we'll need to go over n indices = O(n). But this just proves the existence of the possible time complexity of O(n) and doesn't prove it's the minimum.

Is O(n) the lower bound? And if so what is the proof?

This answer uses the convention that the elements of $X$ are $x_1,\ldots,x_n$ (in their original, unsorted order), and similarly the elements of $Y$ are $y_1,\ldots,y_n$. This differs from your convention.

The complexity of this problem in the comparison model (as well as in related models, such as bounded degree algebraic decision trees) is $\Theta(n\log n)$.

For the upper bound, we can solve the problem by sorting both lists.

For the lower bound, if we fix the second array to be $y_i = i$, then we are essentially sorting the first array $X$. Stated differently, there is a reduction from sorting to this problem, with the same value of $n$ and no extra comparisons. Since sorting takes $\Omega(n\log n)$ comparisons in the worst case, this problem also requires $\Omega(n\log n)$ comparisons.

So far we have only discussed worst-case complexity, and the same argument also works for average-case complexity. The best-case complexity is $\Theta(n)$. This means that we can find a correct algorithm that runs in time $O(n)$ on some input; and every correct algorithm requires $\Omega(n)$ comparisons on every input.

For the upper bound, consider the algorithm that first checks whether both $X$ and $Y$ are increasing ($2(n-1)$ comparisons). If so, it returns the mapping $(x_i,y_i)$. Otherwise, it transfers control to an arbitrary correct algorithm.

The lower bound follows from the same reduction from sorting, since sorting is known to require at least $n-1$ comparisons on any input. Indeed, the same argument used to prove this shows that any algorithm for the pairing problem requires $2(n-1)$ comparisons on any input.


Datastructure for lookup of single point in range (3d)? I'm new to CS and being aware of what algorithms exist, but what data structure allows you to have fast lookups of single points within a distance in 3d?

e.g. (with 2d circles instead of 3d spheres)

I would expect the first location to return null, and the second one to return circle a.

Circles can not overlay, circles/spheres differ in radius.

I would assume this to be nearest neighbor, but maybe some optimizations can be made considering you are often outside the area?

I would not use a nearest neighbor query, they tend to be expensive compared to window query or range query. However, most indexes that support nearest neighbor also support window queries.

You can use any spacial index that supports shapes, quadtree, R-Tree (especially RStarTree), ...:

Insert your circles into the index. This is often only supported as inserting rectangles, so you may have to insert the MMB (minimum bounding box).
For querying, indexes commonly support window queries (rectangular, axis-aligned windows(boxes)). Just set the window size to 0 by defining the min/min/min corner and max/max/max corner of the query to be equal to your search point. This should return all MBBs that intersect with your search point.
Finally, for all returned circles, you have to manually calculate whether they really intersect with your search point (they may not intersect because the MBB is larger than the circle.

For example-implementations (Java) of various spatial indexes have a look here (shameless self advertisement).


Methods for proving upper bound on a-approximiation algorithms? I'm dealing with some simple randomized and on-line algorithms, both kind produce some lower/upper bound on quality of the output instance.

For example, there's a simple randomized algorithm for the MAX-E3SAT problem, where there are $m$ clauses each consisting of three distinct 3 variables in $\{x_1, ..., x_n \}$.

There's a theorem that if there exists an algorithm which is $(\frac{7}{8} + \epsilon)$-approximation, then $P = NP$.

What method can and should I use for proving such theorems?
Could you please provide an example?

More over, regarding the MAX-E3SAT problem, what method can and should I use to prove such claim:

For any instance of MAX-E3SAT the optimum is at least $\frac{7m}{8}$ ?
I'm not looking for the proof of this claim, just the method for proving it.

Thanks a lot

You mention two results giving tight bounds on the approximability of MAX-E3SAT: an upper bound (algorithm) and a lower bound (hardness). The upper bound is much simpler than the lower bound in this case. Indeed, using basic probability you can show that a random assignment satisfies $7/8$ of the clauses in expectation, which gives an approximation algorithm whose approximation ratio is at least $7/8$ in expectation. If you don't like randomized algorithms, this algorithm can be derandomized using the method of conditional expectations.

The other direction is much harder, and relies on the PCP theorem and Raz's parallel repetition theorem. It was shown by Håstad in his seminal paper Some optimal inapproximability results. This is all described in Arora and Barak's textbook, but I warn you that the textbook is quite advanced.


Computational power difference between all interconnected qubit vs few interconnected qubit Recently I came across some news that Google and IBM are planning to  unveil a 50 qubit quantum computer. I read that in this design, each qubit is not connected to all other qubits rather only to the two nearby  qubits(neighours). In layman terms, what difference will this create in terms of the system's computational power?

I can't find the article but the architecture  image is below. Hopes that will help.

A linear chain of qubits has two big disadvantages over a planar grid of qubits:

1) Resilience. If you arrange your qubits into a line, and any one of them doesn't work well, your quantum computer has been cut in half. In a grid you instead end up with a hole that, while inconvenient, can be routed around.

2) Closeness. In a linear chain, the qubits are on average farther apart. So if you want to interact two states, it may take longer to swap them towards each other so that they can interact. That being said, in highly parallel algorithms where you're already saturating all the connections with operations, you tend to be able to combine the swaps with the interactions you wanted to do anyways for no extra cost (e.g. see the paper "Quantum Simulation of Electronic Structure with Linear Depth and Connectivity").


Computing counts of combinations (?) I'm not sure what terminology to use. Here is some input:

John  has items: A B D
Peter has items: A C D

And I want to produce such a table, that would count the # of people having these items (0-count is not required to be outputted):

A     2
B     1
C     1
D     1
A,B   1
A,C   1
A,D   1
A,B,D 1
A,C,D 1

What's the name of such a table and what sort of efficient algorithm could I use to produce it?

Functional programming style more preferable. An Excel solution would be great though I'm not sure it's doable.

It would be used to determine if there are any correlations.

Thank you.

PS here is a rudimentary example solution in Scala which isn't efficient:

scala> val items = List('A', 'B', 'C')
items: List[Char] = List(A, B, C)

scala> val people = List(List('A', 'B'), List('B', 'C'))
people: List[List[Char]] = List(List(A, B), List(B, C))

scala> val combos = (1 to items.size).view.map(items.combinations(_).map(_.toSet).toSet).flatten
combos: scala.collection.SeqView[scala.collection.immutable.Set[scala.collection.immutable.Set[Char]],Seq[_]]#Transformed[scala.collection.immutable.Set[Char]] = SeqViewMN(...)

scala> combos.map(s => s -> people.count(p => s.subsetOf(p.toSet))).toMap
res15: scala.collection.immutable.Map[scala.collection.immutable.Set[Char],Int] = Map(Set(A, C) -> 0, Set(B) -> 2, Set(A, B, C) -> 0, Set(A, B) -> 1, Set(A) -> 1, Set(C) -> 1, Set(B, C) -> 1)

These combinations of items are sometimes called itemsets.  There are algorithms for finding itemsets that are especially common in a database; see association rule learning.

In general there is no efficient algorithm for producing such a table, as the size of the table can be exponentially large in the size of the input.  Consequently any algorithm will take exponential time on at least some inputs (i.e., will be extremely slow on at least some inputs).  You might want to consider what you plan to do with the table and whether there's a way to achieve your ultimate goal, without building the table explicitly; that might turn out to be a better approach.


How is this sorting algorithm Θ(n³) and not Θ(n²), worst-case? I just starting taking a course on Data Structures and Algorithms and my teaching assistant gave us the following pseudo-code for sorting an array of integers:

void F3() {
    for (int i = 1; i < n; i++) {
        if (A[i-1] > A[i]) {
            swap(i-1, i)
            i = 0
        }
    }
}

It may not be clear, but here $n$ is the size of the array A that we are trying to sort.

In any case, the teaching assistant explained to the class that this algorithm is in $\Theta(n^3)$ time (worst-case, I believe), but no matter how many times I go through it with a reversely-sorted array, it seems to me that it should be $\Theta(n^2)$ and not $\Theta(n^3)$.

Would someone be able to explain to me why this is $Θ(n^3)$ and not $Θ(n^2)$?

This algorithm can be re-written like this

Scan A until you find an inversion.
If you find one, swap and start over.
If there is none, terminate.

Now there can be at most $\binom{n}{2} \in \Theta(n^2)$ inversions and you need a linear-time scan to find each -- so the worst-case running time is $\Theta(n^3)$. A beautiful teaching example as it trips up the pattern-matching approach many succumb to!

Nota bene: One has to be a little careful: some inversions appear early, some late, so it is not per se trivial that the costs add up as claimed (for the lower bound). You also need to observe that swaps never introduce new inversions. A more detailed analysis of the case with the inversely sorted array will then yield something like the quadratic case of Gauss' formula.

As @gnasher729 aptly comments, it's easy to see the worst-case running time is $\Omega(n^3)$ by analyzing the running time when sorting the input $[1, 2, \dots, n, 2n, 2n-1, \dots, n+1]$ (though this input is probably not the worst case).

Be careful: don't assume that a reversely-sorted array will necessarily be the worst-case input for all sorting algorithms.  That depends on the algorithm.  There are some sorting algorithms where a reversely-sorted array isn't the worst case, and might even be close to the best case.


Convert CTL* formula to CTL I have a CTL* formula: $\mathsf{EF}[p\land \mathsf{AX}[q\ \mathsf{U}\ r]]$ but in my application, I am limited to CTL. To my understanding, this formula is no valid CTL and I wonder whether I can transform it (preserving semantic, of course). The CTL* formula should express "there exists a path on which $p$ holds and from that point, in all subsequent states, $q$ holds until $r$ eventually holds".

Is this correct and is there a way to convert it to CTL?

A somewhat late response:

The formula $AX(p U q)$ is equivalent to the CTL formula $AXA(pUq)$: Consider a state that satisfies the former, then in all the paths from it, after one transition it holds that $pUq$. Thus, in all the paths after one transition, we reach a state from which all the paths satisfy $p U q$, so the state satisfies the latter. The converse is obvious, sine the second formula is harder to satisfy.

So an equivalent CTL formula is
$EF[p\wedge AXA(pUq)]$.


Does the transitivity of big-O notation hold for asymptotically nonnegative functions? I'm reading the book Introduction to Algorithms and in Chapter 3 it is said that if $f(n)$ and $g(n)$ are asymptotically positive then

$$
f(n) = O(g(n)) \text{ and } g(n) = O(h(n)) \text{ implies } f(n) = O(h(n))
$$

However, I don't see why this wouldn't also be valid if you just required $f(n)$ and $g(n)$ to be asymptotically nonnegative.

Edit:
Here is the definition of $O$ used in the book:

$$
\begin{aligned}
O(g(n)) = \{f(n):&\text{ there exist positive constants $c$ and $n_0$ such that}\\
&0 \le f(n) \le cg(n) \text{ for all } n \ge n_0
\}
\end{aligned}
$$

Suppose $f(n)$, $g(n)$ and $h(n)$ are asymptotically non-negative functions such that $f(n) = O(g(n))$ and $g(n) = O(h(n))$.

Then, by definition, there exist positive constants $c_1, c_2, m_1, m_2$ such that

$$
0 \le f(n) \le c_1 g(n)
$$

whenever $n \ge m_1$ and

$$
0 \le g(n) \le c_2 h(n)
$$

whenever $n \ge m_2$.

Choose $c = c_1 c_2$ and $n_0 = \max\{m_1, m_2\}$.
Note that both $c$ and $n_0$ are positive.
Then, whenever $n \ge n_0$, we have

$$
0 \le f(n) \le c_1 g(n) \le c_1 c_2 h(n) = c h(n)
$$

which implies that $f(n) = O(h(n))$.


does every graph have a complete, preferred, stable and grounded extension? I was looking at graph extensions in argumentation theory and was wondering, which of those extensions does every graph have? and which of those only some graphs have? and is there a proof for each?

thanks

As a complete extension is an admissible set containing exactly these arguments it defends, there is always at least one complete extension, that may be the empty set and nothing else.

Grounded extension is a minimal complete extension, hence there is always one, and it also has the property to be a unique fixed point.

Perferred extension are maximal complete ones, hence starting from the same principle (there is at least one complete extension) there should always be at least one.

As far as I know, the notion of stable extension is not so well-defined and their existence therefore depends on the chosen definition.

You can probably work out additional properties from the paper

Baroni, P., Caminada, M., & Giacomin, M. (2011). An introduction to argumentation semantics. The Knowledge Engineering Review, 26(04), 365-410.


Fastest way to solve a system of linear equations I have to solve a system of up to 10000 equations with 10000 unknowns as fast as possible (preferably within a few seconds). I know that Gaussian elimination is too slow for that, so what algorithm is suitable for this task?

All coefficients and constants are non-negative integers modulo p (where p is a prime). There is guaranteed to be only 1 solution.  I need the solution modulo p.

A LU decomposition of a $n \times n$ matrix can be computed in $O(M(n))$ time, where $M(n)$ is the time to multiply two $n \times n$ matrices.  Therefore, you can find a solution to a system of $n$ linear equations in $n$ unknowns in $O(M(n))$ time.  For instance, Strassen's algorithm achieves $M(n) = O(n^{2.8})$, which is faster than Gaussian elimination.  See https://en.wikipedia.org/wiki/Invertible_matrix#Blockwise_inversion.

Rather than trying to implement this yourself, I would suggest using a library: e.g., a BLAS library.


Recursive functions from O(n) complexity to O(log n) For some recursive questions that require recursing on an input with a small piece removed (hence linear in the size of the input), can we reduce run time by recursing on two halves of the input each time?

For example, take this recursive reverse_string function ...

    def reverse_string1(s):
        if len(s) < 2:
             return s
        return reverse_string1(s[1:]) + s[0]

... compared to this function that does the same string reversal:

   def reverse_string2(s):
       if len(s)<2:
             return s
       mdpt = len(s)/2
       r1 = reverse_string2(s[:mdpt])
       r2 = reverse_string2(s[mdpt:])
       return r2 + r1

Does the latter function successfully reduce the runtime complexity from linear to logarithmic?

r1 = reverse_string2(s[:mdpt])
   r2 = reverse_string2(s[mdpt:])

Here you go in recursion twice. In both recursions you will again recurse twice, etc, which makes $2*2*2... = O(2^{\log n}) = O(n)$. So the complexity is the same.


What does $CS - CF$ means? What does $L_1 \in CS - CF$ means?

I think the meaning is $L_1$ can be generated by context-sensitive grammars, but cannot be generated by context-free grammars.

Am I understanding this correctly? Just to be sure.

You understand this correctly. the set $CS - CF$ denotes the strict difference between these two levels of the Chomsky hierarchy. If you are reading this in a textbook, you will soon learn that $CS-FS \not= \emptyset$, that is, context-sensitive grammars are strictly more expressive than context-free ones. For example, context-sensitive grammars can count, whereas context-free ones, not so much: the language $\{a^nb^nc^n | n \in \mathbb{N}\} \in CS-CF$.


Probability with an unusual pseudo-random generator I will preface this with the actual question taken from lecture:

  An unusual pseudo-random generator outputs integers between 1 and 4, inclusive, in such a way that each value, v, occurs with a probability that is inversely proportional to v. For example, 4 is half as likely to occur as 2, and 1 is three times as likely to occur as 3. Determine the probability P(v) for all possible values of v. Explain in detail, and give the final answer(s) explicitly, in decimal notation.

This seems like a very simple probability question; however, I just want to make sure I am looking at this the correct way.  It says that each value occurs with a probability that is inversely proportional to v.  I understand that the sample space here is S={1,2,3,4}, but wouldn't this not be possible due to the fact that the probability of 1 would be 1 (which is the inverse of 1).  Thus, P(v) would not sum up to be equal to 1, which is a basic property of probability on events.

Just double checking that I am looking at this question the correct way, and whether or not it is a trick question.  Thanks!

EDIT: I understand that this question lies more as a statistical problem; however, it is from a CS class, so I thought it would still be appropriate to post here.

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


Tag, index and offset of associative cache My main issue of a homework problem is trying to figure out the different parts of the chart. I have a 3 way set associative cache with 2 word blocks, total size of 24 words. I am given $3, 180, 43, 2, 191, 88, 190, 14, 181, 44, 186, 253$ to try to map.

What I have so far and where I am stuck:

My main problem is trying to figure out how to find the index and offset of associative (3-way set) cache. Since I have 3 sets, is it: $3 \bmod 3 = 0$, so $0$ is the index? $180 \bmod 3 = 0$ index as well? And would it looks like the following:

$$
\begin{array}{|c|c|c|c|c|c|c|c|} \hline
\text{Block} & \text{Ix} & \text{Hit/Miss} &
\text{Set 0} & \text{Set 0} &
\text{Set 1} & \text{Set 1} &
\text{Set 2} & \text{Set 2} \\\hline
3 & 0 & \text{miss} & \mathit{mem}[3] \\
180 & 0 & \text{miss} & \mathit{mem}[3] & \mathit{mem}[180] \\
43 & 1 & \text{miss} & \mathit{mem}[3] & \mathit{mem}[180] & \mathit{mem}[43] \\
2 & 2 & \text{miss} & \mathit{mem}[3] & \mathit{mem}[180] & \mathit{mem}[43] && \mathit{mem}[2] \\
191 & 2 & \text{miss} & \mathit{mem}[3] & \mathit{mem}[180] & \mathit{mem}[43] && \mathit{mem}[2] & \mathit{mem}[191] \\\hline
\end{array}
$$
etc...

Somehow I feel like this is all wrong, because of some sample problems I have seen. But in class, this is how I remember it being explained. Helping me understand the fundamentals of this problem would be so helpful and I appreciate all the help I can get. Sorry if it doesn't seem like I have put a lot of work into this, but I am familiar with only directly mapped cache and the sample problems I have seen aren't very explanatory.

Before getting to your question, let's recall what set-associativity means, and how one can figure out how to split the address into tag, index and offset. If you prefer to learn by examples, jump to after the fold.

Cache

A cache is just a faster, yet smaller, memory.
It might take a long time to access data in the main memory, but it is very fast to access the cache. So we better save data in our small and fast cache rather than in our big and slow main memory.
However, the cache is small, so it cannot hold the entire data of the main memory.
Instead, it will hold some part of the data stored in the main memory.

Which part of the data?
We don’t know in advance - this would depend on the actual usage of the data (i.e., it depends on the software we run).
In general we would like to be able to put in the cache any part of the main memory,
and we would need to figure out where to put each memory-address in the cache, and how to identify which memory-address lies in each cache-cell. The index and tag bits will do just that (see below for a better explanation). But before we get there, let’s make things a bit more complex: we stop discussing addresses of the main memory and start discussing memory blocks.

Blocks and offsets

Many times, when we access the memory, we access consecutive addresses. That is, many times if we access address 0, then shortly after we will access address 1 (and 2, and 3....). So maybe when we first access address 0, and put it in the cache, it will be smart to bring along addresses 1 and 2 and 3 [...] and put them in the cache as well.
This "chunk" of information that we bring into the cache is called a block. The cache always hold blocks of consecutive memory addresses. It is possible that each block in the cache contains the data of only 1 memory-address. It is possible that a block contains the data of 2 (consecutive) addresses. Maybe it contains 128 consecutive addresses... Each cache has its own parameters.

Since the cache "knows" only blocks rather than specific addresses, we need a way to distinguish different addresses within a specific block. For this we have offset bits.
If a block contains $x$ addresses of the memory, then any $x$ consecutive addresses constitute a single block.
Given a specific address in the memory, we can look at its bits representation: the MSB will be the "block number" and the LSB would be the offset inside the block. That is, to get the block number out of a specific address we can simply ignore the last $\log_2 x$ bits (LSB), and the rest will indicate the number of the block associated with these $x$ addresses. The lower $\log_2 x$ bits are called offset bits and they are used to tell the cache which address within the block we wish to access.

Set Associativity

Now to the more interesting part of caching. Where does each block go within the cache? This seems like a stupid question: why don't any block go anywhere in the cache. The answer is that if any block can be anywhere, then it may be very difficult to locate that block when we need it -- we will have to search through the entire cache for that block, and this search may be slow/expensive.

The solution is that the cache is split into “sets”. Each memory block is assigned to one specific set. This assignment never changes.
Whenever you access that memory block: if it is in the cache it will be in that assigned set; if it is not in that assigned set, it is not in the cache and you need to bring it from the memory.

  Example: let's say the cache have a place for only 2 blocks (Place A, and Place B), and the memory contains 10 blocks (block0 to block9). We can decide that in the first “set” (Place A) we put only even blocks, and in the second set (Place B) only odd blocks. Now if we access block 5 (say), then we only need to check the second set (Place B), because it can only be there. This may save us HALF the search time (or half the cost of searching a block).

In the above example, each “set” could hold only one block, but in general, each set can hold $n$ blocks at the same time: this kind of cache is called $n$-associative.

In other words, an $n$-associative cache is split into sets, where each set holds $n$ memory blocks. This allows us to determine the amount of different sets: it is the size of the cache (in blocks) divided by $n$.

Let’s have two examples:

1-associative: each set can hold only one block. As always, each address is assigned to a unique set (this assignment better be balanced, or all the addresses will compete on the same place in the cache). Such a setting is called direct mapping
fully-associative: here each set is of the size of the entire cache. That is, if the cache is of size $t$ blocks, a fully associative cache is in fact a $t$-associative cache. How many sets are there? one! and all the blocks are assigned to this single set. Therefore, each blocks can be saved “anywhere” at the cache, because all the cells of the cache belong to the same set.

index and tag

We said that each block gets an assignment to one of the $k=size/n$ sets. To make things simple, this assignment is determined by looking at lowest $\log_2 k$ bits of the block number. These are called the “index” bits: they index to which set the block will go into.

  Pop Quiz 1: How many index bits are there in a fully associative cache?

Answer (think about it for a second before looking at the answer):

   In a fully associative cache there is only one set. So we don’t need an index to choose a set, there is only one! Formally, $k=1$ and we need $\log_2 k=\log_2 1=0$ index bits.

next,

  Pop Quiz 2: How many index bits are there in a direct mapping cache?

Answer

   In a direct mapping cache, we have $k=size/1$ different sets. Thus we need $\log_2 k$ index bits.

Next, there are the “tag” bits. To explain these, let’s think on a fully-associative cache.
To make things simple, let’s assume the cache is of size 2 blocks. Assume this two cache-cells are full with information from the main memory: the first cell holds block 0 and the second one holds block 190.
Now we access an address in block 220. But it is not in the cache, so we need to bring it from the memory and replace one of the blocks that are currently in the cache. But wait! How do we actually know that the cache doesn’t hold block 220?
Right. The cache must “remember” that the first cell holds block 0, and that the second one holds block 190. No other choice. This information (0 or 190) is called the tag: to each cell of the cache we add a little tag with that indicates what block is currently there. Simple, right?

But saving information in the cache is expensive, and we don’t want to save information we never use. In the above example every address could be placed anywhere in the cache, but this is not the case for other associativity levels: Each address can go only to its assigned set as determined by the “index” bits. So if there are two sets, where the first can hold only blocks 0,2,4,6,8, and the second set can hold only blocks  1,3,5,7,9, then we don’t need to save the entire block number in the cache-- block 4 can never appear in the second set, and block 7 can never appear in the first set. This means we don’t need to save the last bit (the one that determines the parity), but we need to save the rest. Indeed, the last bit serves as the index, and the rest serve as tag, thus, by knowing the set+the tag we know exactly which block  is currently kept in each cache-cell.

Now back to your question, which exemplifies the above ideas:

The 3-way associativity means that the cache is split into sets, and each set can hold up to 3 blocks. The question gives us that each block is 2 words.

So instead of having 3 sets, where each can hold 2 different addresses/block (as you had in the table you drew), the cache has a large number of sets, and each set has a room for 3 blocks.

How many sets exactly?  well, the cache has 24 words, that is 12 blocks, that is 4sets (of 3 blocks each!). This gives us the size of the index field: 2 bits. [The index decides which set we go into, and there are only 4 sets, so the index needs to be only 2 bits..].

This was the first part of the story. The other part is that a block is two words. Therefore, e.g., when the address 0 is accessed, the cache (set 0) will hold the first two memory words. Thus, if the address 1 is later access, it will be a hit. Since both addressed 0 and 1 are in the same block, we need a way to distinguish them. This will be the "offset" bit.

The above suggests that the 8bit address is to be parsed as

tttttiio

where o=offset  (distinguishes between the 2 words in each block), i is the index (specifies the set) and t is the tag (tells us which block is occupying each cache cell..

So, unless I'm being too careless in thinking it over, the mapping will look like this (building on your table).

Block   Add      Index     Hit/Miss   Set 0         Set 0      Set 0     Set 1      Set 1      Set 1     Set 2      Set 2      Set 2     Set 3      Set 3      Set 3
3   =00000011    01        miss      mem[00000]
180 =10110100    10        miss      mem[00000]                                                                     mem[10110]
43  =00101011    01        miss      mem[00000]     mem[00101]                                                      mem[10110]
2   =00000010    01        hit       mem[00000]     mem[00101]                                                      mem[10110]

etc... Note that by mem[ttttt] I denote the specific block by writing its 5-bit tag value.

tl;dr
A nice illustration to all this "set-associativity" thingy can be found here.


Is it really possible to prove lower bounds? Given any computational problem, is the task of finding lower bounds for such computation really possible? I suppose it boils down to how a single computational step is defined and what model we use for the proof, but given that, do we really prove a lower bound then in general? What I means is that can we prove something like "problem $X$ cannot be solved faster than $t(X)$ time" rather than "problem $X$ can be solved in $t(X)$ time or faster"?

I have tried to find information specifically on lower bounds and proofs of them, but I can't really find any of interest, any recommendations on books/papers/websites on the subject?

We can absolutely prove such things.

Many problems have trivial lower bounds, such as that finding the minimum of a set of $n$ numbers (that are not sorted/structured in any way) takes at least $\Omega(n)$ time. The proof for this is simple: a hypothetical algorithm that runs in $o(n)$ time can not examine all of the numbers in the input. So if we ran the algorithm on some input, we could observe that it never examined a particular element of the input. Changing that element to the minimum, we can get the algorithm to fail.

A less trivial lower bound is the $\Omega(n \log n)$ lower bound for sorting in the comparison-based model. The proof for that goes along the following lines: given an input of $n$ numbers, there are $n!$ possible outputs (the input could be any permutation of the sorted list, so the output can also be any permutation of the input). If we are limited to only doing comparisons, then our algorithm (on average) needs to perform at least $\log_2(n!)=\Omega(n \log n)$ comparisons in order to be able to give $n!$ different outputs.

Lower bounds can be even stronger. There are several problems (notably the $EXPTIME$-hard problems) for which there is an exponential lower bound. Problems in this class include computing optimal strategies for games such as (generalized) chess, checkers and go. The proof of this is via the Time Hierarchy Theorem, which states (subject to some restrictions on $f$):

  Given a function $f$, there exists a computational problem that can be solved in time $O(f(n))$ but can not be solved in time $o(\frac{f(n)}{\log n})$.

So basically, if you can think of a function $f$ there exists a problem that requires that much time to solve.

Finally, another avenue of not necessarily proving a time lower bound but something even stronger is showing the undecidability of a problem (e.g. halting, post correspondence).


How do you represent an r.e. complexity class with a list of TMs? In this book ‘Theory of computation’ By Dexter Kozen on page 313,exercise 127 he says "A set of total recursive functions is recursively enumerable (r.e.) if there exists an r.e. set of indices representing all and only functions in the set. For example, the complexity class P is r.e., because we can represent it by an r.e. list of TMs with polynomial-time clocks." How do you do what he is talking about for any collection of languages that is r.e.? How do you represent an r.e. complexity class with a list of TMs? What is an example of an enumerator that does this for any r.e. class C?

Its easy to iterate through all turing machines - simply iterate through all strings, and pick the ones that actually represent a TM.

I think its possible to iterate through all $P$ by iterating through all turing machines, and for each one to add a "clock" that counts the number of steps and halts after some polynomial time.


Randomized Median Element Algorithm in Mitzenmacher and Upfal: O(n) sorting step? In the last section of chapter 3 (page 54) in Probability and Computing: Randomized Algorithms and Probabilistic Analysis by Mitzenmacher and Upfal, a randomized algorithm is discussed for finding the median of a set $S$ of distinct elements in $O(n)$ time. As a substep the algorithm requires sorting a multiset $R$ of values sampled from $S$, where $|R| = \lceil n^{3/4} \rceil$. I'm sure this is a fairly simple, and straight forward question compared to the others on this site, but how is sorting a multiset of this size bounded by $O(n)$?

I assume the algorithm is using a typical comparison-based, deterministic sorting algorithm that runs in $O(n\log$ $n)$. So, If I have the expression $O(n^{3/4}\log(n^{3/4}))$, isn't this just equivalent to $O(\frac{3}{4}n^{3/4}\log(n)) = O(n^{3/4}\log(n))$? How does the reduction down to $O(n)$ proceed?

Your analysis is correct, and you can conclude that $O(n^{3/4} \log(n)) = O(n)$ immediately. By L'hopital's rule $\log(n) = o(n^c)$ for any fixed $c > 0$, and in particular for $c = 1/4$. Therefore $O(n^{3/4} \log(n)) = O(n^{3/4} n^{1/4}) = O(n)$.


How to determine the size of training data using VC dimension? I want to determine the size of training data ($m$) when I know the parameters $VC(H)$, $δ$ and $e$. As I know the $VC$ bound satisfy this equation:

$$ \mathrm{error}_{\mathrm{true}}(h) \le \mathrm{error}_{\mathrm{train}}(h) + \sqrt\frac{VC(H) \times \ln\left(\frac{2m}{VC(H)} + 1\right) + \ln(4δ)}m
$$

but how can I determine the size of training data ($m$) if I know the others?

Suppose you're aiming for a specific error rate. Suppose for the moment that there is no training error. You have an inequality involving all your known parameters and the unknown $m$, and you can solve it to obtain a value of $m$ that guarantees the specific true error rate, assuming that there is no training error. If you then run classification, you can correct for the training error and repeat.

The bound obtained through usage of VC dimension could be very pessimistic, and I don't know how useful it is in practice. Perhaps your instructor will address this later on in the course (or perhaps the issue will be swept under the rug).


A problem similar to the Bin packing problem? I'm working on a problem that is very similar to the bin packing problem, but for me, the objective is to minimize the maximum weight given m bins. The problem statement is:

Given n items, each with a certain weight less than some maximum weight (w_max), how do you pack them into m bins so that you minimize the maximum weight (over all bins)?

I'm looking at a possible approach that would simply iterate by grouping the two smallest weight items until the number of groups equals the number of bins.

Has anyone heard of a similar problem and know of an approach to solve this with some guarantees?

One way to solve your problem is to use binary search over the maximum weight.  In other words, pick a threshold $t$, and check whether it's possible to pack your items into $m$ bins, without using more than a total weight of $t$ in each bin.  This is exactly the bin packing problem: is it possible to pack the items into $m$ bins of capacity $t$?  You can apply any algorithm for bin packing to this problem.  Then, use binary search on $t$.

Be warned that it is NP-hard, so don't expect an efficient algorithm that produces the optimal solution in a reasonable amount of time for large problem instances.


Finding the element that occurs more often than the other I want an algorithm that calculates which element, among two, appears more often than the other in a sorted array. The array will have only two types of elements.

Example : $aaaaaabbb$

Here $a>b$.

I have to find an constant time algorithm. Is it possible? The only thing I could come up with was using stack. Push all $a$'s and pop them with $b$. But it takes $O(n)$ operations. Any better approaches? Need a hint (no solution).

I am guessing that the solution you are meant to give is to check the middle entry in the array.
Below is a spoiler as to why this works. Hover with mouse to see, but I suggest you try to figure it out alone first.

   If the middle number is $a$, then since the array is sorted, $a$ appears more than $b$, and otherwise $b$ does.

However, it is not really true that this is a constant time algorithm, as it assumes you can compute the length of the array in constant time.

This is impossible in a standard TM, and even in a RAM model. It requires at least $O(\log n)$ operations in the latter, where $n$ is the length of the array.


Given n distinct numbers show that the second smallest element can be found in n + lg n - 2 comparisons in the worst case This is a question from Introduction to Algorithms by CLRS (Exercise 9-1-1).

The approach I thought of is

compare the first two numbers, assign the lower number min and the bigger one to next_min
loop through numbers 3 - n,
if the number is lower than min, set min to that number.
else if the number if lower than next_min set next_min to that number

If this is the optimal solution how can I prove the number of comparisons is n + lg n - 2.

The algorithm with $n + \lceil \lg n \rceil -2$ comparisons uses "tournament" (lecture note from utdallas).

To form a tournament tree: Compare $A[2i−1]$ with $A[2i]$ for $i = 1$
to $n$. We compare the "winners" in pairs and so on.
Collect all the keys that directly lost to the maximum and compute their maximum. That is, the second largest key.

The time complexity is $(n-1) + (\lceil \lg n \rceil - 1) = n + \lceil \lg n \rceil -2$.

Actually, the lower bound for "finding the second largest/smallest element" is $n + \lceil \lg n \rceil -2$, which can be proved by adversary argument (at the end of the lecture above).


How to prove that Exact Cover is NP-complete using SAT? I found this solution online here, but I do not understand the logic behind transforming the instance of SAT to an instance of Exact Cover.

Here's the solution from the link (where C is the clause(s), A is the universe, and F is the subsets of the universe):

C1=(x1 ∨ x2) C2=(x1 ∨ x2 ∨ x3) C3=(x2) C4=(x2 ∨ x3)

A={x1, x2, x3, C1, C2, C3, C4, p11, p12, p21, p22, p23, p31, p41, p42}

F={{p11},{p12},{p21},{p22},{p23},{p31},{p41},{p42},
X1, f={x1, p11}
X1, t={x1, p21}
X2, f={x2, p22, p31}
X2, t={x2, p12, p41}
X3, f={x3, p23}
X3, t={x3, p42}
{C1, p11},{C1, p12},{C2, p21},{C2, p22},{C2, p23},{C3, p31},{C4, p41},{C4, p422}}

I understand how this proves that it is NP-complete, but I do not understand how A and F was populated. In other words, I am unable to figure out the "algorithm" behind creating the p11...p42 variables.

I understand how this proves that it is NP-complete

It isn't a "proof" by any means. It's an example of how a reduction might work, but it hasn't been stated as a formal proof.

From your example, it looks like the algorithm/proof is as follows:

The universe consists of $3$ types of elements: one element $x_i$ for every variable $i$, one element $C_j$ for every clause $j$, and one element $p_{i,j}$ for every occurrence of a variable $i$ as a literal in clause $j$.
For every variable $i$, we create two sets; the true set and the false set. The true (resp. false) set contains $x_i$, together with, for every clause in which variable $i$ appears negated (resp. non-negated), $p_{i,j}$. As an example, if $x_1$ appears as a literal in clause $2$ and $\neg x_1$ appears in clauses $3,4$, we create the sets $\{x_1,p_{1,2}\},\{x_1,p_{1,2},p_{3,4}\}$.
For every element $p_{i,j}$, we create a set $\{C_j,p_{i,j}\}$ and a singleton set $\{p_{i,j}\}$.

As the variable true/false sets are the only sets containing $x_i$, for each variable $i$, a solution to Exact Cover must contain exactly one of the corresponding true/false sets. This gives a correspondence between the variable true/false sets selected in Exact Cover solutions and variable assignments to the SAT instance.

Moreover, any Exact Cover solution must, for every clause $j$, contain for some $i$ the set $\{C_j,p_{i,j}\}$ (since these are the only sets containing $C_j$). If $i$ is a positive literal in clause $j$, this means the false set for variable $i$ cannot be in the solution, since it also contains $p_{i,j}$. Similarly, if $i$ is a negated literal in clause $j$, we cannot have selected the true set for variable $i$. Thus, variable $i$ satisfies clause $j$ in the variable assignment corresponding to the selected variable true/false sets.

Conversely, given a satisfying assignment to the SAT instance, we can simply select the variable true/false sets corresponding to the assignment. For every clause we can select any set $\{C_j,p_{i,j}\}$ for which $i$ is a satisfying literal of clause $j$. This covers the $x_i$'s and $C_j$'s. The remaining $p_{i,j}$'s can be covered by singletons.


Checking if there are 2 elements in an array that sum to X in O(n lg n) I have thought about the most useful way of checking an array for 2 elements that sum to X.
The trivial solution is to check the sum of every element with every element, and the complexity of this solution is $O(n^2)$.

My solution is:
Say the array is A.
It's length is N.
Elements are from A[0] to A[N-1]

Pseudo-Code is:

Check_Sum(A,left,right) {
  mid <-- floor( (left+right)/2 )

  if(A[left]+A[right]=X)
    return true

  return Check_Sum(A,left,mid)||Check_Sum(A,mid,Right)
}

My question is: Is the complexity of my solution equal to $O(n \lg n)$?

Sort the array say ascending order- Takes O(nlogn)

Keep two pointers in the array say fingers. Finger f1 at the first element and finger f2 at the last element.

Sum the elements to get f1+f2:
if f1+f2  == X you have found your solution
else if f1+f2 > X decrease f2 to point to the element to its left
else increase f1 to point to the element to its right

This step will take O(n) making the overall cost O(nlogn)

This solution is also referred to as the finger pointing solution. Can be used in any sorted collection where you can traverse in both the direction for eg in trees.


Isn't Domain of a variable nothing but a constraint? In Constraint programming we have Variables and their Domains and then all the constraints, but if you at the concept of a domain of a variable it is nothing but another type of constraint, you are saying that this variable can take all these values.
Is there any particular reason why domain is defined as a different concept than constraints?

As you observe, restricting the domain of a variable has exactly the same effect as applying a unary constraint to it.

One situation where you might prefer to use unary constraints rather than restricted domains is when you want to control very tightly the relations that are allowed to be used in constraints. For example, if you want to investigate the computational complexity of CSP with a particular class of constraint languages.  On the other hand, such investigations often assume that all unary relations are included in the constraint language, which is equivalent to fixing a global domain but allowing the domain of any variable to be any subset of that.  (This is known as the "conservative" case because of certain algebraic properties of the constraint langauges.)


Frigo's cache-oblivious algorithms paper I am reading Frigo's "Cache-Oblivious Algorithms" paper and I need help understanding his cache complexity expressions for the base cases.

He starts on page 3 with "An $s \times s$ submatrix is stored on $\Theta (s + s^2/ \mathcal{B})$ cache lines.  I can see the reason for $s^2/ \mathcal{B}$ is because we have $s^2$ numbers in total and we can fit $\mathcal{B}$ worlds per line.  But where is the other $s$ coming from?  Is this because we need to store $s$ pointers to each of the $s$ rows of the matrix?

Matrix Multiplication

Next, we have the matrix multiplication algorithm.  First, I like to confirm when do we actually get a cache miss.

If the matrix is small, does that mean it is already in cache and we never miss?
If divide and conquer is needed, then is the matrix brought into cache when it is small enough so that is why we have cache misses at that point?

Here, in the base case (Case I), it says we need $\Theta ( (mn + np +mp)/\mathcal{B})$.  I can see the reason here being we just have the total number of entries in each matrix, divided by how many can fit in one cache line.

But after that, I don't see how the other cases come about.  For example, in Case II, if $n, p \in [\alpha \sqrt{ \mathcal{M}}, \sqrt{ \mathcal{M}}]$, then the $n \times p$ size matrix B can be brought into cache and it will occupy $np/\mathcal{B}$ cache lines, but what are the $n$, $m$, and 1 in the expression of equation (5) 's base case for?

In Case III, equation 6 shows the base case if $m \in [\alpha \sqrt{ \mathcal{M}}, \sqrt{ \mathcal{M}}]$ then the base case cache complexity is $\Theta (1 +m)$.  Is this $m$ the $m$ cache lines for this matrix?  What happened to the $n \times p$ matrix B?  Is it already in cache.  If so, didn't we also incur cache misses before loading it?

Then finally, isn't Case IV the same as Case I's base case?  Why is there a 1 in the $\Theta$?.

Matrix Transpose

Next, the paper discusses matrix transpose.  Here, in Case I, I can see $2mn/\mathcal{B}$ is the number of lines in cache needed to store a total of $m \times n$ entries in the matrix.  But what is the 1 overhead for?

Then, for Case II, it says "The output array consists of nm elements in $m$ rows"...However, I thought the output matrix $B$ defined above has $n$ rows!?  Where is the $m$ rows coming from?

Then a bit later in the paragraph, we get that since $n \geq \alpha \mathcal{B} /2$,  the cache complexity is $O(1+m)$.  Is this because

\begin{align*}
n \geq \alpha \mathcal{B}/2 \to m + nm/\mathcal{B} \geq m + \alpha /\mathcal{B} =O(1+m) ?
\end{align*}

Finally, in Case III, equation (8), when the matrix A is small, it is $m \times n$, so it will take $mn/\mathcal{B}$ cache lines...but again, why this $m$ and $n$ in $O(m +n + mn/\mathcal{B})$?

The version of the paper I am reading does not contain that statement on page 3 that you quote, "An $s \times s$ submatrix is stored in $\Theta(s+s^2/B)$ cache lines." However, it does state that the authors are going to consider matrix multiplication in the case the matrix is stored in row-major order.

In that layout, matrix location $(i,j)$ is stored at memory location $m*i + j$, where $m$ is the number of columns in the matrix. If $m \geq B$ where $B$ is the cache line size, successive rows of an $s \times s$ submatrix will occupy distinct cache lines.

As such, there are at least $s$ lines occupied. As you noted, there are at least $s^2/B$ cache lines occupied, since there are $s^2$ elements and only $B$ fit in a cache line. So, the value is $\Theta(\max(s, s^2/B))$ when $m \geq B$, and in Landau notation, maximum and sum are interchangeable.


How to index a tree to allow efficient search for paths? By "indexing" I mean assigning addresses or labels or whatever to nodes to make them easier to locate, similar (in its effect, not necessarily in the implementation) to how a database can be indexed.
I feel this question must be pretty elementary, but as a CS noob I don't know how to search for the answer. I may not even be phrasing the question correctly.
So let me describe a hypothetical use case. Say my program stores a chess game (including variations) as a tree, with each node representing the state of the game after a move. Given any two nodes which are guaranteed to be in the tree, what is the most efficient way to find the path (a sequence of intervening nodes) from one to the other? I'm mostly concerned with time complexity, although I'd like to save space as well (not sure how to express myself more precisely).
Edit: to clarify what I want, say I have a Python program like this:
tree = Tree(game_record)  # there's a tree constructed from a game record

# this tree can be traversed by calling `advance` and `backtrack`
tree.advance(child=0)  # advance the game into the first child of the current node
tree.backtrack()  # backtrack to the parent of the current node

# and it can tell you which node it's currently at
current_node = tree.current_node()

# now this is my question: at first we're at one node
node1 = tree.current_node()
# after some advancing and backtracking, we arrive at another
node2 = tree.current_node()
# I want a method that returns the path from node1 to node2
tree.find_path(node1, node2)  # should return something like [node3, node4, ...]

# what would be a good way to implement this method?

Walking the whole tree is probably not it. I'm thinking that maybe each node can be assigned an informative address, perhaps an array. One scheme would be to let a child's address be one element longer than its parent's, where the extra element uniquely identifies the child. So if the first node has address [0], its children would have [0, 0], [0, 1], ... and the children of [0, 1] would have addresses like [0, 1, 0], [0, 1, 1], and so on. With this scheme the nodes on the path between any two nodes can be directly read off from their addresses.
With a tall tree though, the addresses can get quite long. Not a real concern for a chess program, but this way of indexing a tree just feels inefficient and inelegant to me. Is there a better way to assign addresses? Or is there a completely different approach to this problem?

Root the tree in an arbitrary fashion. Given two nodes $x,y$, let $x_0 = x, x_1, \ldots$ and $y_0 = y, y_1, \ldots$ be the paths going up the tree all the way to the root. If $x_i = y_j$ then the unique path between $x$ and $y$ is $x_0,\ldots,x_i=y_j,\ldots,y_0$.
In order to find this path quickly (at the cost of a little bit of memory), generate the two paths in parallel, $x_0,y_0,x_1,y_1,x_2,y_2,\ldots$, storing the resulting vertices in a hash table, until they collide. This happens at time $\max(i,j)$, which is the same as the path length $i+j$ up to constant factors.

While the description above suggests that you have to store the entire tree ahead of time, this is not necessarily the case. In general, all you need to do is to have a consistent way of determining which of the neighbors of a given vertex is its parent. Whether this is possible without storing the entire tree depends on the problem. When it is possible, you can generate the tree "as you go", which prompts us to reduce the space complexity of the algorithm (perhaps you don't need to store the path from $x$ to $y$, but only to generate it vertex by vertex).

If space is at premium, you can save a factor of $k$ by storing only a $k$'th fraction of the vertices. Say that a vertex is ($k$-)special if the hash of its index is divisible by $k$. Perform the search as above, but only store special vertices. On average, this will cut the number of vertices stored by a factor of $k$. However, it doesn't give you the exact intersection point. Suppose that your sequences contain the special points $x_{i_1},\ldots,x_{i_a}$ and $y_{j_1},\ldots,y_{j_b}$, where $x_{i_a} = x_{j_b}$. To find the exact intersection point, it suffices to consider the small parts $x_{i_{a-1}+1},\ldots,x_{i_a}$ and $y_{j_{b-1}+1},\ldots,y_{j_b}$.
If space is still at premium, you can use exponential search followed by binary search. We go over $k=1,2,4,8,\ldots$, and for each value of $k$, determine only the first $k$-special vertex after the initial vertices $x,y$. Suppose that for some $k$, these special vertices coincide. Now generate the sequence of $k/2$-special vertices, until they coincide. Let $x_{i_a}=y_{j_b}$ be the first time these sequences coincide. Then we can narrow the search down to $x_{i_{a-1}+1},\ldots,x_{i_a}$ and $y_{j_{b-1}+1},\ldots,y_{j_b}$. Now we generate the sequence of $k/4$-special vertices, starting at $x_{i_{a-1}+1},y_{j_{b-1}+1}$ (unless these vertices are the same, in which case we are done); and so on. The running time is still linear, but the space requirements is down nearly to a constant (in expectation).
We can get the space down to a deterministic constant by defining special in terms of the depth of a vertex rather than in terms of its index, but depth is not necessarily easy to compute.