When would the worst case for Huffman coding occur? I am doing a project on Huffman coding and wanted to know when it wouldn't be ideal to use or rather when would the Huffman coding produce low compression. Since it mainly revolves around the frequencies of the characters present in the input text, I believe the answer is also going to be related to that.

This is what I got from wiki.

The worst case for Huffman coding can happen when the probability of a symbol exceeds 2^(−1) = 0.5, making the upper limit of inefficiency unbounded.

So if a character appears more in our input text, would it ensure good or bad compression? According to wiki, if the probability of symbol exceeds 0.5 (meaning that if a character appears more in our input text), it would be produce bad compression. But from what I understand, in Huffman coding, the more a character appears, the more better it is for us to get compression right?

Well anyway I just want to know in which type of files or text data, our Huffman coding would get bad compression. Maybe I am overthinking, but a little help would be great.

Thanks.

P.S: I don't think this question is subjective, I know that there is a specific answer to it. All I want is a worst case, I don't presume it's subjective?

According to NIST:

  The worst case for Huffman coding (or, equivalently, the longest Huffman coding for a set of characters) is when the distribution of frequencies follows the Fibonacci numbers. For this and other relations see Alex Vinokur's note on Fibonacci numbers, Lucas numbers and Huffman codes.

According to Alex Vinokur a sample Huffman encoding of a sample Fibonacci distribution was 2.3846 times longer than the original. See example 3.1.1.
As I understand it the inefficiency gets worse as the alphabet increases which is why wikipedia talks about unbounded inefficiency.

Note that is not the fact that a single character is prevalent that's the issue it is the distribution of the frequencies that's the problem.

A more useful description comes from your wikipedia quote:

  The worst case for Huffman coding can happen when the probability of a symbol exceeds $2^{-1} = 0.5$, making the upper limit of inefficiency unbounded. These situations often respond well to a form of blocking called run-length encoding;

This happens when a few letters in the alphabet are much more prevalent then others; a skewed distribution as described in the NIST quote above.
This is common in uncompressed bitmap files.

The reason for this is that:

  The Huffman algorithm considers the two least frequent elements recursively as the sibling leaves of maximum depth in code tree. The Fibonacci sequence (as frequencies list) is defined to satisfy F(n) + F(n+1) = F(n+2). As a consequence, the resulting tree will be the most unbalanced one, being a full binary tree.

This is why run length coding or other forms of compression are usually applied prior to Huffman coding.
It eliminates many of the worst case scenario's for Huffman coding.
If it turns out the run length encoding is suboptimal it can simple be skipped.

Zip's deflate algorithm uses de-duplication + run length encoding followed by huffman encoding.

Huffman codes and binary trees
A Huffman code is closely related to a binary tree, however unlike a binary tree a Huffman code only stores its information in the leaf nodes.
The optimal input for Huffman compression is one where the output tree is fully balanced. I.e. where all letters of the Huffman alphabet are equally likely, but where more bits are used in the encoding than needed.
E.g. a text file where 8 bits per character are used even though only 64 different letters are in use. The distribution of letters in a typical language is much flatter than a Fibonacci sequence and thus well suited to Huffman.

Note that it is not necessary the case that all input letters for Huffman should be same size, they can very well be different sizes.
Usually this is not considered in order to simplify the implementation.

Strategies for avoid worst case behavior
Do a frequency analysis on your input data prior to Huffman encoding.


Two's complement addition I am currently learning about a CPU's status register and was confused about the difference between the carry flag and the overflow flag. Then I found article [1] which explains it very well, but I stumbled across one paragraph I don't really understand:

  The rules for two's complement detect errors by examining the sign of
  the result.  A negative and positive added together cannot be wrong,
  because the sum is between the addends. Since both of the addends fit
  within the allowable range of numbers, and their sum is between them, it
  must fit as well.  Mixed-sign addition never turns on the overflow flag.

Let's look at 1111 and 0111. Both are valid 4-bit two's component values with a different sign. If I add them, I the carry-flag is turned on because the result of this addition is a 5-bit value.

The author says that errors in twos complement calculations can be found just by looking at the overflow bit. The overflow bit in this example would not get turned on, but in my opinion, this is an error. Why does the author claim this then? Why does the author tell the reader multiple times to ignore the carry bit when doing twos complement calculations?

[1] http://teaching.idallen.com/dat2343/10f/notes/040_overflow.txt

If you perform the addition, you get 1111+0111 = 0110 (ignoring the carry bit). In decimal, this reads $-1 + 7 = 6$, which is indeed correct. There is no error.

You can check that when adding a positive number and a negative number, if the result is non-negative then there will always be carry, which can be safely ignored.


Is O(ln n) "exponentially faster" than O(n)? I improved the complexity of an alogrithm from $O(n)$ to $O(\ln(n))$. Is it legitimate to call this an "exponential speedup" in a scientific publication? Usually I think going from NP to P when I hear the phrase "exponential speedup". I'd like to avoid overselling my work.

How should we measure (asymptotic) speedup?

Say we wish to compare two functions, $f(n)$ and $g(n)$, and say something on their asymptotic behavior, that is, how they behave for large enough $n$'s, in the limit $n \to \infty$.

Let's start with a few examples.

  Example 1:  $f(n)=2n$ and $g(n)=n$.

Here it is obvious that $f$ is "twice as slow" as $g$; This is true for any $n$ and also in the limit. This needs not be the case. For instance

  Example 1.1:  $f(n)=2n$ and $g(n)=n+1000$.

Well, now, for $n<1000$, $f$ is actually faster than $g$. But still, if we take large $n$'s, we want to say that $f$ is twice as slow as $g$, or in other words, the speedup is 2.

Why 2? Because the ratio between $f$ and $g$, in the limit, is 2.

Let's take a different example to emphasize this issue.

  Example 1:  $f(n)=n+10$ and $g(n)=n$.

Here, $f$ is slightly slower than $g$. What is the speedup between $f$ and $g$? By how much is $g$ faster? The answer is "by 10 clocks". But speedup is measured as a ratio - "twice" as fast means it would take (approx.) twice the time to run the slower function. Here the ratio is approaching 1
$$\lim_{n\to \infty} \frac{f(n)}{g(n)} \to 1$$
That is, the 10 clocks don't make any (multiplicative) difference. Running 10000 clocks and running 10010 clocks, is practically the same (the speedup is $<0.1\%$).

I hope the above establishes that the (asymptotic) speedup between $f$ and $g$ should be defined as
$$\lim_{n\to \infty} \frac{f(n)}{g(n)}.$$

When the speedup is not a constant, then the best way to describe the speedup is to set $g(n)=k$ and ask how $f(n)$ behaves as a function of $k$. If $f(n) \propto k^2$, then the speedup is "quadratic". If $f(n)\propto k^3$ the speedup is cubic. If $f(n)\propto 2^k$, the speedup is called exponential. Not that it is important to set $g$ as the base unit ($=k$). Otherwise, If we take $f$ as the base unit, then a quadratic speedup translates to $g(n)=\sqrt{k}$, which may be a bit confusing. Maybe its better to think at the other direction: instead of considering the speedup from $f$ to $g$, look at the slowdown from $g$ to $f$. (.. if $g$ is twice as fast as $f$, then $f$ is twice as slow as $g$)

If we agree on this, we can check the speedup between $f(n)=n$ to $g(n)=\log n$.
$$\lim_{n\to \infty} \frac{f(n)}{g(n)} = \lim_{n\to \infty}\frac{n}{\log n}$$
Let's change the limit variable, to make $g$ the base unit for the comparison: set $k=\log n$, then,
$$\lim_{n\to \infty} \frac{f(n)}{g(n)} = \lim_{k\to \infty} \frac{2^k}{k}$$
That is the ratio between them, in the limit, has an exponential gap. As mentioned, this is called exponential speedup.


What is the intuition behind the relationship between space and time for an algorithm? I believe I have heard that you can never have more space than the algorithms running time. I could be wrong, maybe other way around. What is the intuition behind this?

A Turing machine moves the tape by one space per time unit. Worst case, if all moves were in the same direction, the space used would be exactly the same as the time used.


PARTITION with 0-sum assumption The PARTITION problem:
$\{\{x_1,...,x_n\}: \exists I\subseteq[n], \sum_{i\in I}x_i=\sum_{i\notin I}x_i\}$
is well known to be NP-complete.

  My question: does the partition problem remain NP-complete (as a promise-problem) if we are given that $\sum_{i=1}^n x_i=0$?.

A problem that arises in this assumption is that one can always take the empty-set, so we also need to require that $I$ is nontrivial.

Note that for the related SUBSET-SUM problem, it is easy to show that the problem remains NP-complete (reduce from subset-sum of positive numbers by adding the negation of the sum).

My guess is that the problem remains NP-complete, but no proof yet.

No. The problem is trivial, since taking $I$ to be the empty set always results in a solution to the problem.

Yes, it is NP-complete. Note that if there is a solution, that is

$\Sigma_{i\in I} x_i = \Sigma_{i\not\in I} x_i$

then

$\Sigma_{i\in I} x_i - \Sigma_{i\not\in I} x_i = 0$.

Since we have

$\Sigma_{i\in I} x_i + \Sigma_{i\not\in I} x_i = 0$

then $\Sigma_{i\not\in I} x_i = 0$ and $\Sigma_{i\in I} x_i = 0$.

Proof of NP-hardness is by reduction from partition. For a given instance of the partition problem, a multiset $S$ of integers, where $\Sigma_{s\in S}=2N$, create an instance of Partition with 0-SUM, by adding 2 copies of $-N$ to $S$.

Clearly, if the Partition instance has a solution then so does the modified problem, by adding $-N$ to each half of the partition. If the Partition with 0-SUM restriction has a solution, then so does the original Partition problem: since all the integers in the original partition problem are positive, each 0-SUM "half" of the 0-SUM partition must contain one of $-N$, and the rest must sum to $N$.


Reduction to proof undecidability of the problem: machine M and N accept infinitely many words I am struggling with the following problem:
Decide whether this problem is decidable or not: For two given Turing Machines M and N, there exists infinitely many words accepted by both machine M and machine N. In other words, is language { encodedMachine(M)#encodedMachine(N) | intersection of language of M and language of N is infinite } decidable?

Intuitively it feels like this is undecidable problem and halting reduction might be used to proof this, but I have no idea how to start this reduction.

Here is the reduction from the halting problem, whether a given TM halts on empty input, as given in Yuval's comment.

For a TM $M$, let $K$ be the same as $K$ but ignoring inputs. That is, for any input, $K$ will first erase the input so that it looks like an empty input is given. Then $K$ will simulate $M$ on empty input. When the simulation halts, $K$ accepts. Now consider whether $\langle K\rangle\#\langle K\rangle$ is in the language specified in the question.

Exercise. Construction a reduction from the other halting problem, whether a given TM halts on a given input $x$.


Using MyHill Nerode theorem to prove a language is non-regular The language is $S = (a^nb^m | n \geq m)$.

I'm having trouble understanding MyHill Nerode theorem. Basically if I want to use MyHill Nerode theorem to prove $S$ is non-regular, I have to show that there are infinitely many equivalence classes. So in this case if I choose $S = a^n$ is simply not working since $n \geq m$ and thus $a^mb^m \in S$. So I think I have to pick $S = b^m$ and $a^nb^m \in S$ but $a^nb^n \notin S$. Does my assumption accurate or any suggestion?

The classes are defined over words of the alphabet such that two words $x, y$ are equivalent if for any word $z$ we have $xz \in L$ if and only if $yz \in L$.

Consider for each $n\in \mathbb{N}$ the class $C_n$ defined as $$C_n = \{x \in S : \#_b(x) \geq 1 \text{ and } \#_a(x) -\#_b(x) = n\}.$$

Note that for each word in this class we can append exactly the strings $b^i$ where $i \leq n$. So for two different values $n_1$ and $n_2$ where $n_1 < n_2$ the word $b^{n_2}$ is a valid suffix to words in $C_{n_2}$ but not in $C_{n_1}$. Hence we have infinitely many such classes. Words ending with the letter $a$ accept additionally more $a$s and hence do not even belong to these classes and we have even more classes. Since we have infinitely many classes, the language is not regular.


Create an algorithm for computing the shortest path in O(m + nlogn) So I'm trying to write an algorithm for computing the shortest path with constraints on the vertices you can visit in $O(m + n \log n)$ time. In this problem, we are given an indirect weighted (non negative) graph $G = (V, E)$, a set of vertices $X \subset V$, and two vertices $s, t \in V \setminus X$. The graph is given with adjacency lists and we can assume that it takes $O(1)$ time to determine if a vertex is in $X$. I'm trying to write an algorithm which can compute the shortest path between $s$ and $t$ in $G$ such that the path includes at most one vertex from $X$ if such a path exists in $O(m + n \log n)$ time. I know that this algorithm would require a modified Dijkstra's algorithm but I'm unsure how to proceed from here.
Could anyone please help me out?

Many such problems can be solved by modifying the input instance rather than a known algorithm.  In your case you can consider your graph as directed and create a new directed graph $G'$ the is split into $2$ "layers", $A$, and $B$.

Layer $A$ contains a copy of all the vertices in $V$, layer $B$ contains a copy of all the vertices in $V \setminus X$. Given a vertex $v$ let $v_A$ be it's copy in $A$ (if any) and $v_B$ be its copy in $B$ (if any).

The edges of $G'$ are as follows:

For each edge $(u,v) \in E$ with $u,v \in V \setminus X$ add to $G'$ the edges $(u_A, v_A)$ and $(u_B, v_B)$ with the same weight as $(u,v)$.
For each edge $(u,v) \in E$ with $u \in V \setminus X$, and $v \in X$, add the edge $(u_A, v_A)$ with the same weight as $(u,v)$.
For each edge $(u,v) \in E$ with $u \in X$, and $v \in V \setminus X$, add the edge $(u_A, v_B)$ with the same weight as $(u,v)$.
Ignore all the edges $(u,v)$ with $u,v \in X$.
Finally, for each vertex $v \in V \setminus X$, add the edge $(v_A, v_B)$ with weight $0$.

Your problem now amounts to that of finding the shortest path between $s_A$ and $t_B$ in $G'$, which can be done in $O(m + n \log n)$ time using Dijkstra's algorithm.


Formalisms in concurrent and/or distributed programming? My background came from imperative languages, primarily C, C++, and Python. I picked up Scala, Erlang, and a bit of Haskell a few years later and have since become very interested in functional programming and the formalisms behind it.

I am also interested in concurrent and distributed programming and have been looking into formalisms behind that, especially those that have seen at least a tiny bit of the "light of day" (e.g. real world use, or at least an implementation somewhere). So far I know of Communicating Sequential Processes, the Actor model, Algebra of Communicating Processes, and the Calculus of Communicating Systems. Among these I know the Actor model has realized itself in languages like Erlang, Scala, and Haskell.

I am wondering if there are foundations I should learn and practice before tackling these fields, if there is a "classic" one that I should study first, and if there are any other popular ones that I may have missed?

The most widely used formalism is the $\pi$-calculus by Milner, Parrow and Walker. It is an extension of CCS, and comes in many variants, some of which (the asynchronous $\pi$-calculus) attempt to be a formalisation of the actor model. There are now many typing disciplines for $\pi$-calculi, the simplest of which are probably Honda's session types. Such types are slowly diffusing from research papers to research implementations.


There exists an algorithm to find grammar of complement of a function? I'm wondering if there exists an algorithm to solve the following problem:

  Given a grammar $S$ of a context-free language $\mathcal{L}$, find a grammar
  $S'$ such as $L(S) = L(S')^c $.

I note that the complement of a context-free language is also a context-free language, so the questions is well stated.

Contrary to what you wrote, context-free languages are not closed under complement.  See Examples of context-free languages with a non-context-free complements for some examples.  As a result, there is no such algorithm.

Also: It's decidable whether $L(S)=\emptyset$, but it's not decidable whether $L(S)=\Sigma^*$.  If you could compute the complement, then you could decide the latter using the algorithm for the former.

In contrast, deterministic context-free languages are closed under complement, and the proof of that fact likely identifies an algorithm that will work when you have a deterministic context-free language.  Another way to handle it: convert to a deterministic pushdown automaton, then it is clear how to complement it.


How to understand the mathematical constraint of potentials? Good evening!
I am studying scheduling problems and I have some difficulties understanding constraints of potentials:

Let be $t_j$ the time when a task $j$ starts, and $t_i$ the time when a task $i$ starts. I'm assuming that $a_{ij}$ is the length of the task $i$ but I'm not sure. Why is a "constraint of potential"  mathematically expressed by:

$$t_j-t_i \le a_{ij}$$

Shouldn't it be the reverse, $t_j-t_i \ge a_{ij}$? If we know that the length of task $i$ is $a_{ij}$, isn't it impossible to do something in less that the necessary allocated time?

I suspect there's some misunderstanding about the definition/meaning of $a_{ij}$.  The time to complete task $i$ depends only on $i$ (not on $j$), so it wouldn't make sense to use notation like $a_{ij}$ for the length of task $i$: we'd instead expect to see only the index $i$, but not $j$, appear in that notation.

I suspect you'll probably need to go back to your textbook or other source on scheduling and look for a precise definition of the notation that it uses.  If your textbook doesn't define its notation, look for a better textbook.

As far as the constraint $t_j - t_i \le a_{ij}$, that is expressing that $t_j$ should start at most $a_{ij}$ seconds after $t_i$ starts.  So, it'd make more sense for $a_{ij}$ to be a permissible delay that expresses the maximum time you can wait to start task $j$, once task $i$ has been started.


proving that if graph has perfect elimination order than the graph is perfect I need help with this problem:
Let say that G has a perfect elimination order, than I have to prove that G is perfect.
Can someone help me with that?
I've tried to solve it with induction but I did not succeed..

Here's a route you can take.
Prove (or use the fact) that a graph is chordal iff it has a perfect elimination order. Now, it will suffice to show that a chordal graph is perfect. For that, you can take the strong perfect graph theorem stating that a graph is perfect iff it contains no odd hole and no odd antihole. Proceed by contradiction.


Effect of Copy-On-Write on 2 processes sharing address space I am studying operating systems and was going through Copy On Write mechanism.
From Wiki:

  When one process modifies the memory, the operating system's kernel intercepts the operation and copies the memory; thus a change in the memory of one process is not visible in another's.

It says a particular virtual page is remapped if any of the processes that are sharing the address space tries to modify any data value. So, I tried testing it by writing following code :

#include<stdio.h>
#include<stdlib.h>

int main()
{
        pid_t pid;
        int a = 30;
        pid = fork();

        if(pid == 0)
        {
                printf("Parent\t %x\t %d\n",&a,a);
        }
        else
        {
                printf("Child\t %x\t %d\n",&a,a);
                a = 25;
                printf("Child\t %x\t %d\n",&a,a);
        }

        return 0;
}

Now when I run the program, the output I get is :

$ ./test
Child    ae9dfe3c        30
Child    ae9dfe3c        25
Parent   ae9dfe3c        30

I understand why the address in first and third line are same but my doubt is why is the memory location in second line same as the other two? It should be different because the child process is modifying the value of a ?

The fork primitive makes a copy of the process. From within the processes, the parent and the child are almost identical; the few differences are the return value of the fork primitive and a few characteristics such as the process ID.

Copy-on-write is an implementation optimization. It isn't visible from inside the process. You'd need to look inside the kernel to see it, or use some reporting tools that expose this information. For example, you can observe it indirectly through memory usage statistics.

What you're printing out are the virtual addresses of the variables. They're the same: that's the whole point of fork — it creates a (near-)identical copy of the process.

Under the hood, when the child modifies the value of a, the kernel makes a copy of the page that contains it. Before that point, the variable a in the parent process and in the child process are stored in the same memory. After that point, they are stored in different memory: the parent and the child now each have their own page. But the two processes map their respective pages at the same address — the address of a variable doesn't change (it can't change, because that's how the code locates the variable).


The relationship between degree and the number of leaves of a tree? What is the relationship between $\text{deg}(T)$ and the number of leaves of $T$, if $T$ is a tree?

As you said the degree of a tree, probably $T$ is a rooted tree. Hence, the relation between the number of leaves $n$ is $\text{deg}(T) \leq n$, as each child of the root is terminated to at least one leaf


Embedding high dimensional vectors into low dimensional space preserving similarity I have a collection of high dimensional vectors such as $\vec{a}_{i} \in \mathbb{R}^{n}$ where $n$ is 3000. What I want to do is to embed these vectors into a space such as $\vec{b}_{i} \in [0, 255]^{n}$ where $n$ in this case is now 32. I want to embed it (using any hash trick or something like that) in a way that will preserve similarity. For example, if I have the following two vectors that are very similar to each other:

$\vec{a}_{1} = (1.2, 0.1, 0.4, 12.8, \ldots)$

$\vec{a}_{2} = (1.1, 0.1, 0.4, 12.5, \ldots)$

I want these two vectors to end in the same "bucket" of this other space where the vectors belongs to $[0, 255]^{32}$. Note that I don't want to use it for search, I want similar vectors to be in the same "bucket" in this other low dimensional space. I was trying to use LSH but I wasn't able to figure out a way to solve this.

Locality-sensitive hashing is one reasonable approach for this.  I suggest reading standard resources on locality-sensitive hashing (LSH).  In your case, a locality-sensitive hash is a hash function that maps $h:\mathbb{R}^n \to S$ where if $x,y \in \mathbb{R}^n$ are close enough, then we'll have $h(x)=h(y)$ with high probability.

To get started, tead https://en.wikipedia.org/wiki/Locality-sensitive_hashing and https://cstheory.stackexchange.com/q/10053/5038.

Do understand that LSH is fundamentally probabilistic: if $x,y$ are similar, they will have a high probability of being mapped to the same bucket, but this cannot be guaranteed.

Alternatively, you might be interested in metric space embeddings.  An embedding $E:\mathbb{R}^n \to \mathbb{R}^d$ has the property that if $x,y$ are close (i.e., $\|x-y\|_2$ is not too large), then $E(x),E(y)$ will be close (i.e., $\|E(x)-E(y)\|_2$ will be not too large).  This could then provide a solution to your scheme, if you are satisfied that similar inputs map to buckets that are "nearby" but not necessarily identical.

For more on metric space embeddings, you can start with https://cs.stackexchange.com/a/27923/755, https://cstheory.stackexchange.com/a/6818/5038, https://cstheory.stackexchange.com/q/21487/5038, https://cstheory.stackexchange.com/questions/tagged/embeddings.


Can we derandomize subexponential algorithms given P=BPP? Under $BPP=P$ conjecture randomization does not have much power for poly time algorithms.

Can we say the same about randomized subexp algorithms like number field sieve?

Derandomization results transfer "upwards" using the technique of padding. Assume $\mathsf{P}=\mathsf{BPP}$. Suppose that some problem $A$ can be solved in randomized superpolynomial time $t(n)$ (which is time-constructible). Let $A'$ be the same problem, but with inputs padded to length $t(n)$. Then $A' \in \mathsf{BPP} = \mathsf{P}$. The following algorithm then solves $A$ in deterministic time $t(n)$: pad the input to length $t(n)$, then apply the polynomial time algorithm for $A'$.

Conversely, it is possible (given the current state of knowledge) that subexponential time algorithms can be randomized, but polynomial time algorithms can't (and it might be possible to construct a relativized world in which this happens unconditionally). That is, results don't transfer "downwards".


What kind of language would you suggest for an University compiler project? I'm not an instructor. I'm a student doing such course. And I'm just trying to figure out what to do, because we're not given an input language.

What kind of (input) language would you suggest for an University compiler project?

It's a project typical to the compiler course in CS programs.

However, I've been confused about, whether it would be easier to design a language for the project or use some existing programming language.

It should be able to handle the following requirements:

Readable (no binary noodles)
Comments
At least two different types of data (type errors must be captured at the latest during the run)
Integrity technology
Making choices (if tms)
Playback (loops, recursion etc)
Parameterizable subroutines (functions, methods, etc) that can use local variables

Additional features

Tables (multidimensional, 0.5 cr, one-dimensional 0.25 cr)
String input and output (0.25 cr)
String interpolation or printf-style formatting by yourself (0.25 cr)
    Complex printf formats (0.25 cr)
Records and variants (0.5 cr)
Generic (Static) Types (0.5 cr)
Classes and Late Binding (0.5 cr)
First-class functions (0.5 cr)
Garbage collection (entirely self-made) (1 cr)
Recursive pattern match (garden Haskell) (0.5 cr)
Lazy calculation (1-2 cr depending on the implementation technique)

Additionally the implementation would include:

Relatively effective interpreter without separate intermediate language 0 cr
Generation of intermediate language (eg own, JVM or LLVM) 1 cr
Generation of a machine language (eg AMD64 or ARM) from its own intermediate language
Naive register allocation 1 cr
Smart register allocation (eg graphing) 2 cr

Also, what existing programming languages would fit into all of these? Does it have to be a functional language or does even C implement all of these?

I think you are trying to achieve too much in a single exercise. It would, in my opinion, be better to separate the compiler construction part of the exercise from the comparative language part.

Good code generation and optimisation are difficult for some of the additional features you have cited. In my view it is better that students learn to do some decent lexing, parsing, optimisation and code generation before having to handle some of the more complex features of languages.

If you create a portmanteau of a language you end up with lots of examples of rotten and partially functioning compilers which do not help them learn.

It also matters what the target language you are going to use. Are you asking them to generate CIL, Byte Code, C  or some other output format? Each of these has different pedagogic reasons for their choice.

Choosing a language to build an example compiler for is like choosing a first programming language. There is no right choice.

To start building compilers I often recommend compiling something like Pascal or even simpler. (The choice of compiler implementation language depends on the tool set you choose to teach.)


Is the problem to construct a $\mathcal{O}\mbox{*}(1.4^n)$ (or better) time algorithm for subset sum still open? Is the problem to construct a $\mathcal{O}\mbox{*}(1.4^n)$ (or better) time algorithm for subset sum still open? I wanted to check the problem before finishing a paper.

The most recent reference I found to this open problem is on next paper:

  'SETH-Based Lower Bounds for Subset Sum and Bicriteria Path, Amir
  Abboud et al.' 2017
  link

citing:

  'Open problems around exact algorithms, Woeginger' 2008
  link.

The way to tell if it is open is to read more recent papers to see if any of them make progress.  If not, it's still open.  The way to find more recent papers is to look up that paper on Google Scholar and look through all the papers that site it.  If someone has made progress, it's likely they'll cite that paper.

In general, don't expect to necessarily find a paper somewhere that says "it's still open".  People aren't necessarily going to bother repeating "yup, still open" every year.


Complexity classes: What if different algorithms exist for different sizes of input? If I understand(*) correctly, a decision problem is some function $f(x)$ whose function argument $x$ can be represented by data of a limited length (e.g. not an irrational number) and whose value is either 0 or 1.

If there exists some algorithm which can calculate the function value $f(x)$ in less than $\sum_{i=0}^{i_\text{max}}K_in^i$ steps (while $i_\text{max}$ and $K_i$ are constant) for every function argument with a length of $n$ (bits, bytes, digits, characters...), the decision problem belongs(*) to the complexity class $P$.

My actual questions:

Let's say for every "length" $n$ there is an algorithm that takes less than $\sum_{i=0}^{i_\text{max}}K_in^i$ steps to calculate $f(x)$ for a function argument $x$ which has a length of exactly $n$ (bits, bytes, ...).

(However, these algorithms do not necessarily work for every function argument $x$, but depending on the "length" $n$ of the function argument $x$ we have to use different algorithms.)

Would this imply that there exists one single algorithm that can calculate $f(x)$ for any argument $x$ in polynomial time?
If the answer is "no": Would the decision problem belong to the complexity class $P$ or not?
If either of the two answers is "yes": How is the situation in other complexity classes than $P$?

(*) Please excuse me if I use wrong terminology or my premises are wrong. I'm not a mathematician and my interest about complexity theory comes from the field of computing device development.

What you are describing is non-uniform algorithms. You have to be careful when defining them. For example, consider the following algorithm, for inputs of length $n$:

  Look up the answer in a large table.

If this algorithm runs in polynomial time in your model, then the non-uniform version of your computation model can compute all decision functions.

There are two common ways to define non-uniform computation models in complexity theory: using advice and using circuits.

Advice. One possibility is to have a uniform algorithm (working for all input lengths) which gets an additional "advice" which only depends on the input. Let's see how such an algorithm can efficiently decide the following language:

$$ L_H = \{ w : \text{the $|w|$th Turing machine halts on the empty input} \}. $$

(Here $|w|$ is the length of $w$.)

The algorithm gets an auxiliary advice $a_n$, and just returns $a_n$. The advice $a_n$ is simply whether the $n$th Turing machine halts on the empty input.
Incidentally, this example shows that non-uniform models can compute uncomputable functions.

One standard complexity class which can be defined in this way is $\mathsf{P/poly}$, which consists of all decision problems computable by polynomial time algorithms having access to a polynomial size advice.

Circuits. Cook's theorem shows (essentially) that if $L$ can be decided in polynomial time, then for every $n$ we can construct a polynomial size circuit deciding the length $n$ instances of $L$. These circuits are uniform in the sense that they can be constructed by an algorithm.

This suggests the following natural non-uniform model: polynomial size circuits. In this model, for every input length we can supply an arbitrary polynomial size circuit (that is, there is a polynomial $p(n)$ such that the $n$th circuit has size at most $p(n)$). Every problem in $\mathsf{P}$ can be decided in this model, as mentioned above. But this model is much more powerful — indeed, it can compute the uncomputable language $L_H$ mentioned above: the $n$th circuit either computes the constant 0 function or the constant 1 function. It turns out that this circuit model is exactly equivalent to the class $\mathsf{P/poly}$ defined above.

Non-uniform models of computation are important in complexity theory, since many lower bound techniques apply directly to them. For example, one approach for proving $\mathsf{P} \neq \mathsf{NP}$ which used to be popular is proving superpolynomial lower bounds for circuits computing some NP-complete problem such as $\mathsf{SAT}$. Nowadays this approach seems less promising. But various weaker non-uniform models are the object of intensive study in complexity theory.


What characterises vertices at fixed indices in all topological orderings? Let $G$ be a DAG with $v \in V$. Suppose that there exists some $i$ such that for all topological orderings $v_1, \ldots, v_n$ we have $v_i = v$.

What's a set of necessary and sufficient conditions about $v$ for this to occur?

Theorem: A given vertex $v$ always comes first, $i = 1$, iff it has no incoming edges and every other vertex has at least one incoming edge.

Right-to-left implication: no vertex other than $v$ can come first, since they all have incoming edges.

Left-to-right: for $v$ to come first it has to have in-degree 0.  If some vertex $w$ has in-degree 0 with $w \neq v$ and there's a topological ordering where $w$ has a left neighbour $u$, then swapping $w$ and $u$ yields another topological ordering: the only vertices which have new relative positions are $u$ and $w$, and since $w$ has in-degree 0 no constraint is violated by putting it before $u$.

Repeatedly move the leftmost such $w$ one step to the left; this will end when one such $w$ comes first, contradicting the assumption that $v$ always comes first.  Hence no $w$ exists.

QED

By a symmetric argument, a vertex always comes last if it alone has out-degree 0.

Theorem: $v$ is fixed-index iff it is comparable to every other vertex (i.e. for all $w$, either $w = v$ or there is a path from $v$ to $w$ or there is a path from $w$ to $v$).

Right-to-left: compare $v$ to all other vertices. All $w$ with a path to $v$ must come before $v$ and all $u$ with a path from $v$ to $u$ must come after $v$.  That leaves only one index at which $v$ can occur.

Left-to-right: assume for the sake of contradiction that there exists some $w$ to the left of $v = v_j$ in some topological ordering, where $w$ is incomparable to $v$, i.e. there is neither a path from $v$ to $w$ nor from $w$ to $v$.  Let $u = v_i$ be the rightmost among those, $i < j$.

Consider $t = v_{i+1}$.  By $u$ being the rightmost incomparable vertex left of $v$, either $t = v$ or $t < v$.  If $u$ were comparable to $t$ then $u$ would also be comparable to $v$ (by transitivity through $t$) so it isn't.  Hence we can swap $u$ and $t$ and remain topologically ordered.  Continue doing this until $u$ and $v$ get swapped, contradicting $v$ being fixed-index.

Similarly derive a contradiction from the existence of an incomparable vertex to the right of $v$.  Hence there is no incomparable vertex.

QED

Some consequences:

Let a digraph $G$ be Weakly Connected if the undirected counterpart is connected; define Weakly Connected Components analogously.

Any interleaving of the topological orderings of two weakly connected components is a topological ordering of their union.  In particular, one can put the entire ordering of one component immediately before or after a given vertex in the other component, so no vertex can be fixed-index (so long as both components are non-empty).

Corollary: a DAG with a fixed-index vertex is weakly connected.

A more direct and constructive proof: $path(s, v) + path(v, t) = path(s, t)$ where the precise definition of $path$ and $+$ is left as an exercise ;-)

There is no implication in the other direction: consider the complete bipartite graph on 2+2 vertices, edges left-to right, with $a, b$ on the left and $c, d$ on the right; then $a$ and $b$ come before $c$ and $d$, but $a$ and $b$ can always be swapped, and so can $c$ and $d$.  This graph is weakly connected but has no fixed-index vertex.

It is also not the case that all paths from $v_i$ to $v_k$ go through $v = v_j$ when $i < j < k$.  For (counter)example, $V = \{a, b, c\}$ and $E = \{(a, b), (a, c), (b, c)\}$ which has only one topological ordering. Let $(v_i, v, v_k) = (a, b, c)$; then there is a path of length 1 from $a$ to $c$ which doesn't go through $b$.


Minimum number of adjacent swaps needed to sort a circle of elements I have been thinking about some problems in combinatorics and I came across a problem I'm having trouble with.

Suppose you have a list $L$ of length $n$ (wlog the elements of the list are 1,2,3,...,n) and you want to sort it circularly (meaning [3,1,2] is sorted) with swaps of adjacent elements, but you are also allowed to consider the first and last elements as adjacent. What is the minimal number of swaps required?

The way to think about this, I think, is to consider the elements of $L$ arranged around a circle, in order. There are $n$ ways to do this, each with a different element at the top. What I want to do is just arrange $L$ in each way, sort it while counting the swaps, then take the minimum.

The problem I have is that elements of the list don't stay fixed: for example I can move 1 into the correct place, but when I move 2 into the correct place, I might move it past 1, which would mess up the position of 1. I am not really sure this is a good idea, since I'm not sure where the "correct place" of an element is, since any place around the circle could be correct.

Another idea I have is to fix 1 and sort the circle around 1 (i.e. I move 2 into place relative to 1, then 3 and so on). Then do it for 2 and so on, then take the minimum of the number of swaps I did while fixing each element. But is it true that this gives the optimal sequence of swaps?

This doesn't seem like an efficient solution either, since I am actually doing swaps on a list rather than some clever calculation. I know that the number of swaps in e.g. bubble sort is the number of inversions in the list. Is there a similar calculation I can do for circular lists?

Suppose we have two lists $L$ and $M$ of length $n$. They are identified as circular lists if and only if, when you write out $(L_1 \ldots L_n)$ and $(M_1 \ldots M_n)$, they give the same permutation, when considered as an element of $S_n$.

We can consider the graph $\Gamma$ with vertex set $(123\ldots n)^{S_n}$ (that is, the $n$-cycles in $S_n$). $\Gamma$ has an edge $(v, w)$ iff there is a transposition of adjacent elements (adjacent when we write $v$ down as $(v_1, \ldots, v_n)$) taking $v$ to $w$. This is well-defined since the only different way to write a cycle is by cyclically permuting it - the adjacent elements stay adjacent.

Given a circular list $L$, the problem is now finding the distance in $\Gamma$ from $L$ to $(1\ldots n)$.

To actually compute this, I used the GAP algebra system. We can take some steps to define the edges in a nicer way.

Let $G = S_n$. $G$ acts on the vertex set $V$:

$$\sigma \cdot (v_k)_{k=1}^n = (v_{\sigma(k)})_{k=1}^n$$

Also notice there is one vertex orbit, since any vertex can be relabelled to any other vertex.

Using this, we can define the group action in GAP:

G := SymmetricGroup(n);
ncycle := PermList(Concatenation([2..n], [1]));
all_ncycles := ncycle^G;
action := function(cycle, g)
    list := WritePermAsList(cycle);
    result := [1..n];
    for i in [1..n] do
        result[i] := list[i^g];
    od;
    return WriteListAsPerm(result);
end;

where WritePermAsList just writes e.g. the permutation (1,2) as the list [1,2] and so on.

Now we have the action, we can define a graph Gamma with vertex set $V$ with NullGraph and use AddEdgeOrbit to add all edges corresponding to the permutations we want to allow. In this case, we want to allow permutations of the form $(i\;i+1)$ and $(1 \; n)$. So we do AddEdgeOrbit(Gamma, [1, 1^Permutation(sigma, ncycles, action)]) for each sigma we want to allow.

Now computing the answer to the question I asked: "What is the minimal number of swaps required [to sort $L$]?" is just Distance(Gamma, 1, i) where i is the vertex representing our circular list $L$ since 1 represents $(1\ldots n)$ in our graph and we want to sort meaning get to $(1\ldots n)$.

I think this method isn't even that bad since I only really need this for small (length less than 10) lists. The simple structure of the graph means that we don't actually need to store all that much information about it (certainly we don't need to keep a huge list of vertices and edges in memory).

There are probably more insights about how to reduce this problem to something else, but this was good enough for me.


Is it NP complete to decide whether a graph has $k$ disjoint triangles? I'm trying to prove that $$k\text{-Matching}\le_p k\text{-Disjoint-Triangles}$$
but I was told that the $k\text{-Matching}$ (decide whether a graph has a matching of size $k$ ) can be solve in polynomial time. Then I'm stuck here.

Could anyone help me out here?

For the special case where $n$ is a multiple of 3 and $k=n/3$, this is the PARTITION-INTO-TRIANGLES problem, which is proved to be NP-complete here.
The idea is to reduce 3-DIMENSIONAL-MATCHING (3DM) to PARTITION-INTO-TRIANGLES. I quote the construction here.

Let $X = \{x_1, x_2, \ldots, x_q\}$, $Y = \{y_1, y_2, \ldots, y_q\}$, $W = \{w_1, w_2, \ldots, w_q\}$ and $M \subseteq X\times Y\times Z$ be the generic input instance of 3DM. Construct an initial set of vertices $V$, called the "public vertices", as the union of $X$, $Y$ and $W$. For every triple $m = (x_a, y_b, w_c)$ in $M$, construct the graph $G_m = (V_m, E_m)$, depicted in Figure 1. Here $V_m$ contains the three public vertices $x_a$, $y_b$ and $w_c$ plus three "private vertices" $v_m^1$, $v_m^2$ and $v_m^3$. The ten edges in $E_m$ are $v_m^1v_m^2$, $v_m^1v_m^3$, $v_m^2v_m^3$, $x_av_m^3$, $x_av_m^2$, $y_bv_m^3$, $y_bv_m^1$, $w_cv_m^1$, $w_cv_m^2$ and $x_1y_b$. The whole graph $G_M$ is obtained from the union of all the gadgets $G_m$ as follows: $G_M = (V_M, E_M) = (\cup_m V_m,\cup_m E_m)$.


Question about proof of Kannan's Theorem The wikipedia page (here) assumes the existence of some $L \in \Sigma_4 - SIZE(n^k)$. How can one show that such a language exists?

This is related to a homework question, I'd prefer some hint to the answer. Using the hierarchy theorems, we can find some language $L \in SIZE(n^{k+1})$ for which $L \not \in SIZE(n^k)$. I doubt all such languages would be in $\Sigma_4$, but maybe some of them with a special property may be?

It seems we could just as well take something in $\Sigma_3$. Could we maybe take the language $L$ decided by the smallest such circuit? So then we could make a sentence like

$x \in L \iff \exists C_n $ such that for $\forall$ circuit families $C'_n \exists x'$ so that $C_n(x) = 1$ and $(|C'_n| > |C_n|$ OR $C'_n(x') != C_n(x'))$?

But it seems like this choice depends on $|x|$.

Following your way:

Let us denote by $C_{n,s,i}$ the i'th $n$ inputs, $s$ size circuit (relative to the lexicographic ordering of the strings describing such circuits), Then:

$x\in L \iff \exists i \hspace{1mm} \phi\left(C_{|x|,|x|^{k+1},i}\right)\forall j<i : \neg \phi\left(C_{|x|,|x|^{k+1},j}\right)\land C_{|x|,|x|^{k+1},i}(x)=1$.

$\phi(C)$ is a formula which states that $C$ cannot be computed by an $n^k$ size circuit, and can be written as a $\Pi_2$ statement (as you did in your original post).

The idea is the same as yours, trying to decide some language in $SIZE(n^{k+1})\setminus SIZE(n^k)$. The only addition is using the lexicographic ordering and forcing minimality. This way we force that for any length $n$ string, the quantification over the circuit index $i$ yields the same circuit.

After grouping the quantifiers (and moving $\forall j<i$ right after $\exists i)$ you get a $\Sigma_4$ formula.


Upper-bounding the number of comparisons for Sorting to $\Theta(n)$ using a physically big number like Number of Particles in the Universe I recently read an article Scott Aaronson - Big Numbers . That has made me think about the effective upper-bound for sorting.

According to the article, some of the big numbers like the number of particles in the universe and age of universe in milliseconds are less than $10^{100}$.

In any realistic computational device, the data to be sorted will have to be lesser than these numbers. (As otherwise, it would be impossible to store the numbers physically).

$\log_2(10^{100}) \approx 333$

Hence, if we take a number $C > 333$, we can show that number of steps required for sorting an input of size $n$ will always be lesser than $Cn$

This makes sorting an $O(n)$ time operation using algorithms like QuickSort or HeapSort.

Is there a point I've wrongly considered while making this assumption?

Should we consider physical constraints while analyzing algorithms? If not, why?

The reasoning is not wrong as such, but applying such constraints tends to make asymptotic analysis meaningless; for example we could simply choose $C' = 10^{100}$, and as all inputs are smaller than this, every algorithm is $O(1)$.

Despite the ability to limit the analysis physically and end up with trivial observations, asymptotic analysis (without imposing those limits) does give practical information about algorithms. When we run them, we can certainly notice the difference between, say, Merge Sort and Bubble Sort - even when we have physically very small instances (even less than 1000).

So by speaking about algorithms in this more general (though not necessarily physically accurate) way, we get genuine information about how we can expect algorithms to perform based on how big the input is. More importantly it allows us to compare them.

From a different perspective, if we accept that all possible instances are smaller than some (really really big) constant, then all algorithms take constant time, what we then need to consider is what that constant is - if it amounts to longer than a few years, we haven't learnt anything useful to humans who only live a few years. If we lived longer than the life of the universe, then perhaps we wouldn't care about anything smaller than the size of the universe.


Number of permutation cycles in matrix transposition I am trying to solve a problem on Sphere Online Judge (SPOJ) link to which is: http://www.spoj.com/problems/TRANSP/

The matrix can be thought of as a permutation and its transposition as another permutation. I need to convert the first one into another. I have found a relation between the Cycles in the Permutation and the number of swaps required as:

Minimum Swaps = Total Elements in Permutation - Number of Cycles

However, I don't know how to calculate the matrix of size $2^a 2^b$ where $a+b \leq 500000$.

Let's take a simple example:
$$ \begin{pmatrix} a & b & c \\ d & e & f \\ g & h & i \end{pmatrix}' = \begin{pmatrix} a & d & g \\ b & e & h \\ c & f & i \end{pmatrix}.$$
So we need to exchange $(b,d),(f,h),(c,g)$, i.e. the answer is 3. Now try to generalize this to $A \times B$ matrices. Obtain a formula, substitute $A = 2^a$ and $B = 2^b$, and find a way to efficiently compute the result modulo a small prime $p$.

When $A = 2^a$ and $B = 2^b$, things look nicer. The permutation taking a position in the original matrix to the corresponding position in the transposed matrix corresponds to left shift by an amount $a$. Suppose $g = \mathrm{gcd}(a,b)$ and $a' = a/g,b' = b/g$. We can now think of the operation as a left shift by the amount $a'$ of a string of length $a'+b'$ over an alphabet of size $G = 2^g$. The number of orbits is then the number of necklaces of length $a'+b'$, which has an explicit formula. (The shift amount doesn't matter since $a'$ is invertible modulo $a' + b'$ due to $(a',b')=1$.)


Coding Theory Optimal Code with given max length Why do we need at least 2 Code Words of the max length in optimal Codes?

Any why do they just differ in their Prefix?

Could someone give me more insight into this?

Have to proof that for a given optimal Code C with max length L there are at least 2 Code Words of max length that just differ in their prefix.

I have nothing to start so some start would be good.

I have no given definition of optimal Code in my script and I don't know if it has to be a block code that I see in most definitions.

So first, some terminology.

A uniquely decodable code is a code where every string has at most one decoding.

A prefix code is a code where no code word is a prefix of any other. This is an interesting property because it means that the system is uniquely decodable without using lookahead.

A uniquely decodable code is optimal if it has minimal average code word length.

An optimal prefix code is, just as the name suggest, a prefix code that is also optimal.

The main result that you should know about uniquely decodable codes is the Kraft-McMillan inequality. It states that if you have an alphabet of size $r$ ($r=2$ if the codes are binary), and a uniquely decodable code with code word lengths $l_1, l_2, \ldots, l_n$, then:

$$\sum_i r^{-l_i} \le 1$$

And, conversely, for any code word lengths that satisfy the above inequality, there exists a prefix code with the same code word lengths.

Taken together, this means that for every uniquely decodable code, there is an equivalent prefix code.

I'm going to suggest looking at the link above, and work through the proofs. This should give you the head start that you need.

One of the questions that you asked, whether the two maximum-length code words differ only in the prefix, is true for optimal prefix codes, but doesn't have to be true for uniquely decodable codes in general. But as noted, for every uniquely decodable code, there is an equivalent prefix code.


Proof that a quantum computer is equivalent to some logical circuit My question is about the quantum computer. I have tried to prove that the quantum computer is equivalent to some logical circuit.
I know this has already been proven, but I will present my attempt:

First we know that the quantum computer is composed of quantum logic gates
https://en.wikipedia.org/wiki/Fredkin_gate. According to this link, this gate is universal
So any quantum computer can be made up of those gates
Now we make a logical circuit simulating the Fredkin gate
Then each quantum circuit can be simulated by a logical circuit

Is this proof valid?

It's not a valid proof (yet) because you haven't described how you plan to do step 3.  You also haven't described how you plan to deal with superpositions of states.


Indexing into a pattern database - Korf's Optimal Rubik's Cube solution As a fun project, I've been working on a C# implementation of Richard Korf's - Finding Optimal Solutions to Rubik's Cube Using Pattern Databases.

https://www.cs.princeton.edu/courses/archive/fall06/cos402/papers/korfrubik.pdf

I actually have it working, I'm just trying to improve my solution.

One thing that Korf glazes over in his paper is how he stores and indexes into the pattern databases. Ideally, I think we want to use an instance of a rubik's cube to generate an index into an array.

My question is about the best way to generate this index.

My solution is to generate a minimal perfect hash. This involves keeping ALL of the cubes in memory until I have discovered the entire pattern database then generating a minimal perfect hash based off of that. The MPH takes a couple hours to run depending on the pattern database size, but I only need to do it once since I save it to disk. In the end, I can throw away the cubes themselves storing only the MPH. That way I can take a randomized rubik's cube, apply the pattern, then look up the array index in the MPH to get an estimated solution length.

I believe Korf and Shultz describe a better way to determine the cube's index in their 2005 paper called "Large Scale Breadth-First Search"

https://www.aaai.org/Papers/AAAI/2005/AAAI05-219.pdf

This paper describes an algorithm to generate an index based off of the lexicographical ordering of a permutation. Basically you can take the permutation {1, 2, 3} and figure that it is the smallest with an index of 0. {1, 3, 2} is next up with an index of 1 and so on.

I feel like I should be able to apply this algorithm to a rubik's cube to get its index within a pattern database, but I'm having a hard time figuring out how it would work in practice.

The corners only pattern database for instance contains all rubik's cubes that have had their edge stickers taken off. There are exactly 88,179,840 cubes in this set. Any corner cubie on a rubiks cube can be in one of 24 different states. The state of the 8th corner cubie can be calculated based on the other 7 so cubes in the corners only pattern database each have 7 values between 0 and 23

e.g.
{0, 3, 6, 9, 12, 15, 18, 21} defines the "solved" cube with all edge stickers removed.

if I rotate the front face 90 degrees the permutation might be:
{0, 3, 11, 23, 12, 15, 8, 20}

Is there a way to get an index out of these sort of permutations?

You don't explain what the numbers from 0 to 23 mean, but according to this answer, you can represent the state of the corners using eight pairs $(p_i,o_i)$, where $(p_0,\ldots,p_7)$ is a permutation of $(0,\ldots,7)$, $o_i \in \{0,1,2\}$, and $o_7$ (say) is determined by $o_0,\ldots,o_6$. In total, this gives $8! \cdot 3^7 = 88179840$ degrees of freedom. Assuming that you can decompose your $\{0,\ldots,23\}$ to pairs $(p_i,o_i)$, you can easily convert a position to an index by encoding separately the permutation $(p_0,\ldots,p_7)$ (which the AAAI paper explains how to do) and the values $o_0,\ldots,o_6$, which you can encode in base 3. Putting the two values together in the obvious way (for example, $3^7p + o$ or $8!o + p$), we get an index.


How can one reduce 3-CNF-SAT and k-CNF-SAT to each other? I am studying for NP problems.
To prove k-CNF-SAT is NP-hard, there must exists something that can be reduced to k-CNF-SAT. So what I thought is to reduce 3-CNF-SAT to k-CNF-SAT and reduce k-CNF-SAT to 3-CNF-SAT both proves that it is NP-hard.

I know that 3-CNF-SAT is NP-Complete, because of its number of literals, but this property seems dedicate no effect to proof.
Thanks for any suggestion.

Note: k-CNF-SAT is a conjunctive normal form which k > 3.
And my question is same as the title, I have no idea about this question, since I just only know 3-SAT is a special case of k-SAT.

To reduce $k$-CNF to CNF: every instance of $k$-CNF is an instance of CNF, so the reduction is trivial.

To reduce CNF to $k$-CNF, where $k \ge 3$: convert the CNF formula to a circuit that computes it; then convert the circuit to a 3-CNF formula using the Tseitin transformation.  (If your definition of $k$-CNF requires that there be exactly $k$ literals in every clause, then you can pad: introduce $k$ new variables $y_1,\dots,y_k$; for every clause that has less than $k$ literals, add $\lor y_1 \lor y_2 \lor \dots$ to pad it out to exactly $k$ literals; and then add clauses that force all of $y_1,\dots,y_k$ to be false.)

If this is too terse, see our reference question and a good textbook to learn the fundamentals of reductions.


Detecting coplanarity by given pairwise distances Consider an undirected weighted graph $G = (V,E)$, where $V \subset \mathbb{R}^3$ so the points are 3D, and the weight of an edge equals the (Euclidean) distance between its endpoints.  Note that we're not given the coordinates of the points in V.  We may not even be given all pairwise distances, so the graph need not be complete, and it may even be sparse.

Suppose we're given $k$ and told that there are $k$ planes such that all the vertices belong to at least one of those plane. We want to find $k$ such planes, with an added restriction:

In order to determine whether 4 points are coplanar given only their pairwise distances, the most straightforward method is to use the Cayley-Menger determinant.  For our problem, this would require the graph to be fairly dense, since we'd need to know most of the pairwise distances to apply Cayley-Menger.  The restriction is to find $k$ planes without using the Cayley-Menger determinant.

If this is impossible, can we obtain a proof that states this is impossible?  In other words, can we prove that for any such graph $G$ and given $k$, if we have enough information to find $k$ planes for $G$ by some means, then we have enough information to use Cayley-Menger to find $k$ planes?

I think that if the input graph is 3-connected, and you assume some arbitrary origin and orientation, you can recreate the original points. Especially if you can find K_4 to seed the triangulation process.

Once we have the points, greedy strategies become available. They might not be optimal, but maybe they're enough for your purposes.

I've asked about recovering the embedding as a separate question.

Random Greedy

Until we have fewer than three not-disqualified points, arbitrarily pick three of them, yield the plane going through them, and mark all points on the plane as disqualified.

Take the remaining not-disqualified points (if any), pair them with some arbitrary disqualified points, and yield the plane going through them.

The planes we yielded covered all of the points. The number of planes we yielded is at most $\frac{n}{3}$, and each requires scanning through the remaining points, so this algorithm takes $O(n^2)$ time (faster than computing a determinant).

If the number of planes $k \ll n$, then we have reasonably good odds of hitting one of the large planes. I'm not sure what the expected running time is, but I would wild-guess it at $O(n \, k^3 \log k)$. (That's based on the coupon collector problem implying we need $\approx k \log k$ hits to collect $k$ planes, and that the odds of a hit are $\approx (1/k)^2$ so the expected time between hits is $\approx k^2$).

Prioritized Greedy

Another thing we can do, if we can solve for the points, is iterate over all triplets and count how many points are on that plane. Then we repeatedly yield the plane covering the most points, until no points are left.

If we don't account for disqualified points when choosing the next plane, then this takes $O(n^3 \log t)$ time where $t$ is the number of planes we return. If we do re-prioritize, then I think it can still be done in $O(n^3 \log t)$ (the number of disqualified points on other planes can only change by 2 so it might be possible to rebalance in some clever way).

This approach should do better, but again I don't think it's guaranteed to have $t=k$. We can probably arrange the points so that taking the plane covering most of them sends us down the wrong path.


Runtime analysis of bit sorting algorithm with input size and integer size I'm struggling to analyze the runtime of this algorithm mainly because it depends on two parameters - the length of the input n, and also the bit size of individual n (bitnum). Most documentation I can find solve recursion based on n solely. The algorithm is:

def sortB(seq,bitnum):
    # length of seq
    n = len(seq)
    lists = []
    for j in range(0,256):
        lists.append([]);
    for i in range(0,n):
        bits = (seq[i] >> bitnum) & 255;
        #print("bitnum :", bitnum)
        #print("seq[i] :", seq[i] >> bitnum)
        lists[bits].append(seq[i]);
        #print("bits ",bits)
    i = 0;
    for j in range(0,256):
        seqj = [0]*len(lists[j])
        k = 0
        for m in lists[j]:
            seqj[k] = m
            k = k + 1

        if (bitnum > 0):
            bitnum = bitnum - 8
            seqj = sortB(seqj, bitnum)

        for m in seqj:
            seq[i] = m
            i = i + 1

    return seq

I tried to think about this and basically I get this far:

Because the recursion happens based on the number of times bitnum is decremented by 8
   $b = bitnum$

$T(n,b-8)$

I solve the recursion of $T(b) = 256T(b-8)$

and I get T$(b) = 256^{(b/8)}$  which simplifies to $2^{(b)}$

Therefore, the whole algorithm gets multiplied by a factor of $2^{b}$: I get a runtime of $O(2^{b} n)$ which is in $O(n)$? But I feel this is wrong since the upper bound on the running time isn't taking this new factor (b) into account.

If you treat $b$ as a constant, then $O(2^b n)$ is $O(n)$, and $O(n)$ is right.

If $b$ is not a constant, $O(2^b n)$ is not $O(n)$.

I think it would help to review Landau notation.  The running time is whatever it is; it is some value $T(n,b)$ that depends on both $n$ and $b$.  The big-O notation helps us understand how this value grows as you increase $n$ but hold $b$ fixed, or how it grows as you increase both $n$ and $b$.  You have to decide which of those you want to understand (do you want to understand its behavior as you increase $n$ while holding $b$ fixed?  do you want to understand how it grows when you increase $b$ while holding $n$ fixed?  do you want to understand how it grows when you increase both of them?  that will lead to different results and different ways of applying big-O notation).


Is $A$ regular if $A^{2}$ is regular? If $A^2$ is regular, does it follow that $A$ is regular?
My attempt on a proof:

Yes, for contradiction assume that $A$ is not regular.  Then $A^2 = A \cdot A$.
Since concatenation of two non-regular language is not regular $A^2$ cannot be regular.  This contradicts our assumption.  So $A$ is regular.  So if $A^2$ is regular then $A$ is regular.

Is the proof correct?
Can we generalize this to $A^3$, $A^4$, etc...?  And also if $A^*$ is regular then $A$ need not be regular?
Example: $A=\lbrace 1^{2^i} \mid i \geq 0\rbrace$ is not regular but $A^*$ is regular.

Consider Lagrange's four square theorem. It states that if $B = \{1^{n^2}| n \geq 0\}$ then $B^4 = \{1^n | n \geq 0\}$. If $B^2$ is regular, take $A = B$ else take $A = B^2$. Either way, this proves the existence of irregular $A$ such that $A^2$ is regular.


Recursive relations in binary trees I have an exercise in my algorithm's Course for which I have the correction but do not understand it.

1.Exercise .

Let Th be a full binary three of height h(meaning all the levels all completely full).

(1.a) : Let f(h) be the number of leaves of Th(nodes of the last level).
Establish a relation for f(h) and solve it recursively. Give the exact expression for f(h) in terms of h, and the asymptote expression (in Big-O notation)

Correction

f(h)=2*f(h-1) for h >= 1 and f(0) =1.
f(h)=2*f(h-1)=4*f(h-2)=8*f(h-3)=...=2^hf(h-h)=2^hf(0) =2^h.
Complexity : O(2^h)

I simply do not understand why h-1. Because suppose we have a full binary tree with h=2 . If h=2, then number of leaves = 4 . Applying the correction resolution:
f(2) = 2*f(2-1) = 2*f(1) = 2, which is different from the number of leaves, which is 4.

I think you're just confused about the definition of "height".  You write that you expect $f(2)=4$, where $f(h)$ is the number of leaves when the height is $h$.  A full binary tree with four leaves looks like this:

     o
   /   \
  o     o
 / \   / \
o   o o   o

So, in this case, you're taking the height to be the number of edges between the root and a leaf, and a tree of height $h$ has $h+1$ levels of nodes.

But you also write $f(2) = 2f(2-1) = 2f(1) = 2$, implying that $f(1)=1$.  A full binary tree with only one leaf looks like this:

     o

However, that tree has one level of nodes, so it has height zero.  The height $1$ tree is

     o
    / \
   o   o

so we see that $f(2) = 2f(2-1) = 2\times 2 = 4$, as expected.
Perhaps you were thinking of the following tree, which has one leaf and height $1$, but isn't a full binary tree.

     o
     |
     o


About sorting numbers in linear time If one is given $n$ numbers picked uniformly at random from the interval $[0,1]$ then is it possible to sort them in linear time?

It seems to me that some such method exists which uses binary representations of these numbers and compares the sequences of 0s and 1s between any two of them only partially and that somehow is enough!?

What is confusing me is that this somewhere seems to need a source of random bits and that is not clear to me where. How many?

Does one account for the time taken to generate these binary representations?

If the numbers are upper bounded by $n$ then apparently there is some probabilistic way of sorting them in linear time with a success guarantee $\geq 1 - \frac{1}{n^c}$ for some constant $c$.

What is this method?

If your input consists of integers, that is your elements are from the set $\mathcal{U}=\{0,\ldots,u-1\}$, you can sort faster than $O(n\log n)$ assuming your model of computation is the word RAM.

you can sort deterministically (even on using $\text{AC}^0$ computations) in time $O(n \log\log n)$
there is a randomized algorithm that sorts in $O(n \sqrt{\log\log n})$
if your word size $w=\log u$ is in $\Omega( \log^{2+\varepsilon} n)$ for some $\varepsilon>0$ then the input can be sorted in linear time

If you are interested in the references, check out Erik Demaine's lecture notes. Note that all these results use in some sense the effect that you can parallelize some computations on the word ram using bit tricks. It does not requires that the numbers are picked uniformly at random from $\mathcal{U}$.


Does increasing k in a k-way set-associative cache always lead to a better miss rate? As far as I know a 2-way set-associative cache works better than a one-way one considerably but going to 4 and 8-way caches leads to a marginal improvement. My question is: does increasing K (going more than 8) lead to better miss rate although marginal?

It's not guaranteed; it may depend on the data. Let's say an 8-way associative cache can hold 8 items at position 512k + j for each fixed j, and a 4-way associative cache can hold 4 items at position 1024k + j. My algorithm accesses locations 1024k + 512 + j for just four values k all over again. And locations 1024k + j for lots of values k, so there is basically no cache reuse.

In this case, 4-way associative caches has lots of hits and 8-way almost none. (There may be some mistake made somewhere, but you should figure out a pattern where 4-way ends up better).

For random access patterns, and for not carefully constructed patterns, higher associativity will be better. There is of course the problem that picking one out of 8 sets will take more time than picking one out of 2 or out of 4 sets.


Is search a binary heap operation? According to the Wikipedia page, search is "not an operation" on binary heaps (see complexity box at top-right).

Why not? Binary heaps may not be sorted, but they are ordered, and a full graph traversal can find any object in $O(n)$ time, no?

Is the page wrong or am I?

Actually it depends on your point of view, or level of detail.

The heap, or better priority queue, as abstract data structure usually supports operations like is-empty, add-element, delete-min. And usually not find-element. This is the data structure seen as a specification, fixing the set of operations and their behaviour. The implementation is unknown, it can be a linked tree or array.

The wikipedia page however is concerned with the implementation. That is even clear from the title binary heap. (You understand the binary heap by looking as if it is a tree, you implement it using an array). In this implementation it is easily seen how to program your operation find-element. Technically, that is another abstract data structure (as it has an additional operation aprt from standard heap operations).

In practice heaps (priority queues) are often used for graph algorithms like Dijkstra. There it is important that the priorities stored in the heap can be changed (if we find a shorter route). That is only possible if we are able to find the element in the heap so we can adjust its priority (and reposition the element in the heap). Usually that is done by building another structure on top of the heap so we can efficiently find the positions where elements are stored.


What complexity class would this version of generalized chess fall? By now I understand that generalized chess is harder than NP, and is EXPTIME-complete for the decision problem "Given an nxn board with a given position, can white force a win?" because the proof would require an exponential amount of steps to show that each branch of the tree eventually leads to a win. Therefore it's not in NP.

But if you were to ask the decision problem "Given an nxn board with a given position, can white win?" and apply it to generalized chess, would this variation be in NP? Because the verifiability of this proof would only require polynomial time (just play out the winning game). For this decision problem, would it fall in NP, because a problem solvable by a DTM in EXPTIME and verifiable in polynomial time would be NP-complete, yes?

because the proof would require an exponential amount of steps to show that each branch of the tree eventually leads to a win. Therefore it's not in NP.

It is possible that generalized chess is in $NP$. We do not have a proof that $NP \not = EXPTIME$ or a proof that a certificate for generalized chess would take an exponential amount of steps. It is highly likely, though.

  But if you were to ask the decision problem "Given an nxn board with a given position, can white win?" and apply it to generalized chess, would this variation be in NP? Because the verifiability of this proof would only require polynomial time (just play out the winning game).

This is unknown. It is known that if two players work together to reach a given position then this may take an exponential amount of moves but this doesn't apply to the specific case of whether white can win and doesn't allow us to conclude whether the problem is in $NP$ or not (because even if it takes an exponential amount of moves, maybe there is a "smarter" certificate that can prove this exponential sequence of moves exists in polynomial time).

  because a problem solvable by a DTM in EXPTIME and verifiable in polynomial time would be NP-complete, yes?

No. Shortest path can be solved in exponential time (polynomial time even) and is in $NP$, but it's (likely) not $NP$-complete. Moreover, it is possible that there are problems that require exponential time to be solved and are in $NP$, but that are not $NP$-complete, see e.g. $NP$-intermediate.


Coloring book. Finding region by point Let me explain what I want to achieve. I'm working on the coloring book project. On the input, I'm getting transparent images with black borders (Like this). Currently, I've created the 2D Matrix with colors in points. And basing on this Matrix I want to form an array of regions.
Region:
class Region {
    var set = Set<Point>()

    func contains(_ point: Point) -> Bool {
        return set.contains(point)
    }
}

The region represents points that form bordered parts(e.g. gun barrel, button, hat).
My future logic will be this:

Users taps.
Get point.
Find the region that contains that point.
Color all the points in that region.

The problem is that I don't know how to form those regions :). Can you please help me solve this problem? Maybe it's some famous algorithm but I just don't know how to google it properly.
P.S. I hope this is the correct place to ask this kind of question.

Once you get the point, you can use Flood Fill Algorithm to replace the current color in the region containing the point with the new color.

Basically, this algorithm starts from a specified point and then recursively(or iteratively) keep replacing the current color with the new specified color in the neighbouring points till it reaches the boundary of the region.

It detects the boundary by checking for points having different color(different from current and new color). So you don't have detect/store the regions in advance.


Showing an equivalent definition of $CO-RE$ Let $L_1$ be a language.

I would like t prove that $L_1\in CO-RE$ if and only if exists a language $L_2$ s.t. $L_1=\{ u\,\, |\,\, \forall_{v\in\Sigma^*} : <u,v>\in L_2  \}$ and $L_2\in R$.

I'm not quite sure on where do I start here from?

I've tried writing down what I know and trying to develop any ideas, but got stuck at the very begining.

Since $L_1\in CO-RE$ then $\overline{L_1} \in RE$. That is, exists a TM $M$ s.t. $M$ accepts any $u\in \overline{L_1}$ (that is $u\notin L_1$) and either rejects or loops forever for $u\in L_1$.

But I dont see how does this assist me to construct such a language $L_2$ that will both be in $R$ and assist me?

And even if I do succeed, how am I to show the other way around - that if such a language $L_2$ exists that satisfies the above conditions, $L_1\in CO-RE$?

Equivalently: $\overline{L_1}$ is RE iff there is some $\overline{L_2}$ that is $R$ so that $\overline{L_1}=\{u  | \exists v : <u,v>\in \overline{L_2}\}$ is RE.

$\Rightarrow$

Take $\overline{L_2}=\{<u,v> | v\text{ represents an execution accepting u in the MT accepting }\overline{L_1}\}$. It's R because you just simulate the MT following v and it'll either work or not. And it vefiries the property $\overline{L_1}=\{u  | \exists v : <u,v>\in \overline{L_2}\}$ because a word is accepted iff some execution accepts.

You could also take $\overline{L_2}=\{<u,n> | u\text{ is accepted by an execution of size} n\}$.

$\Leftarrow$

Enumerate all $v$, for each, test is $<u,v>\in\overline{L_2}$ and if it is, accept. If the word is in $\overline{L_1}$ then some $v$ will work so it'll be accepted. So $\overline{L_1}$ is indeed RE.

Your property says is that being RE is the same thing as being the projection of a R set.


What is the name of this positive integer set data structure? Google is failing me, so here goes:

The data structure is used to describe a set of positive integers.
It works conceptually, by keeping track of disjoint ranges [a,b) on the number line.
These ranges are stored, in a sorted manner. For two consecutive ranges [a, b), [c, d) the invariant is that a < b < c < d.
The ranges are stored flat in an internal array, meaning that for the ranges [a, b), [c, d) the internal representation is [a, b, c, d].
To look up if an integer x belongs to the set, we perform a binary search. If x is found in the array at an even position, x is a member; if x is not found in the array, but can be inserted at an odd index while preserving order, it is also a member. Otherwise x is not a member.
The internal array does not necessarily contain an even number of elements; if there is an odd number of elements, the last range is open-ended above. [a, b, c] is the set [a,b) ∪ [c,∞)
Conceptually you start excluding numbers up from zero until you reach the first number in the array, then you include numbers up until the second number of the array, then you exclude until the third, include until the fourth, etc.
Union of a collection of sets is made by iteratively taking the least element from the set with the smallest least element. If that element used to occupy an even index, we increment a counter, if it used to occupy an odd index, we decrement. Whenever the counter moves away from zero, or falls to zero, we include the just-removed element in the new array, otherwise we discard it.
Complement of a set is computed by inspecting the first element of the array. If it is zero, remove it, it it is not zero, prepend zero.
This data structure is often used to store information about Unicode properties, as it very compactly describes consecutive ranges of Unicode code points.

What is the name of this beast?

The name of the data structure, as @Evil correctly pointed out, is an Inversion List.

And boy is that Wikipedia article a stub.


How are conditionals implemented at hardware level? Can anyone explain how are conditionals implemented in the CPU?

Is special circuitry used?

The semantics of any non-jump CPU instruction is to increment the program counter PC (a.k.a. instruction pointer) so that the subsequent instruction can be executed next.

Uncoditional jumps overwrite PC with a new, fixed value, written in the instruction. (Or, for relative jumps, add to PC said value)

Conditional jumps instead consider two possible values for PC: one pointing to the next instruction, another written inside the instruction (possibly as a PC increment, for relative jumps). Then, they test some given register, obtaining a bit. For instance, the register might be a flag, which is taken as is. Otherwise, the register might be tested for parity, sign, zero, etc. so to obtain a single bit. This bit controls which one of the two PC values is the one to write in the PC register. Usually, a hardware commutator is responsible to choose between the two ones, exploiting the control bit.


Deriving the average number of inversions across all permutations In the answer by Raphael to the question "Is there a system behind the magic of algorithm analysis?", there is an equation:

$$\qquad\displaystyle \mathbb{E}[C_{\text{swaps}}] = \frac{1}{n!} \sum_{A} \operatorname{inv}(A) \tag{1},$$

where $A$ is an array, $\mathbb{E}[C_{\text{swaps}}]$ is the expected number of swaps it takes to sort a random permutation with Bubblesort, $n$ is the length of $A$, and $\operatorname{inv}(A)$ is the number of inversions of $A$.

Then (1) is equal to the following equation:

$$\qquad\displaystyle \mathbb{E}[C_{\text{swaps}}] = \frac{1}{2} \cdot \binom{n}{2}. \tag{2}$$

But I don't understand how to prove (2) based on (1). Could anyone please give me a proof?

You can not go directly from one equation to the other; you need to add a whole proof which is separate from what I explain there. Hence my statement "it has been shown".

A boring proof using induction is here.

For a constructive proof, you can follow the idea from here:

Show that the maximum number of inversions is $\binom{n}{2}$.
Observe that every permutation and its reverse pair up: their respective
sets of inversions are complement to each other, so both together add $\binom{n}{2}$ inversions to the sum.
Since this pairing neatly and uniquely covers all permutations, we get that the total number of inversions across all permutations is $\frac{n!}{2} \cdot \binom{n}{2}$.

The claim follows immediately.


Are there any specific problems known to be undecidable for reasons other than diagonalization, self-reference, or reducibility? Every undecidable problem that I know of falls into one of the following categories:

Problems that are undecidable because of diagonalization (indirect self-reference). These problems, like the halting problem, are undecidable because you could use a purported decider for the language to construct a TM whose behavior leads to a contradiction. You could also lump many undecidable problems about Kolmogorov complexity into this camp.
Problems that are undecidable due to direct self-reference. For example, the universal language can be shown to be undecidable for the following reason: if it were decidable, then it would be possible to use Kleene's recursion theorem to build a TM that gets its own encoding, ask whether it will accept its own input, then does the opposite.
Problems that are undecidable due to reductions from existing undecidable problems. Good examples here include the Post Correspondence Problem (reduction from the halting problem) and the Entscheidungsproblem.

When I teach computability theory to my students, many students pick up on this as well and often ask me if there are any problems we can prove are undecidable without ultimately tracing back to some kind of self-reference trickery. I can prove nonconstructively that there are infinitely many undecidable problems by a simple cardinality argument relating the number of TMs to the number of languages, but this doesn't give a specific example of an undecidable language.

Are there any languages known to be undecidable for reasons that aren't listed above? If so, what are they and what techniques were used to show their undecidability?

Yes, there are such proofs. They are based on the Low Basis Theorem.

See this answer to Are there any proofs the undecidability of the halting problem that does not depend on self-referencing or diagonalization? question on cstheory for more.


Computational complexity of the clique problem What is the best known approximation for the computational complexity of the clique problem? Is it accurate to consider it $O(2^n)$?

Wikipedia is usually a good starting reference to well-known problems as the clique. There is a list of the fastest known algorithms for CLIQUE including references.

Apparently, the fastest algorithm we know runs in time $O(1.1888^n)$, so that's the best upper bound on the complexity of CLIQUE we have. As for lower bounds, we don't have a super-polynomial one, or otherwise P=NP? would have been solved.


How can we form a graph from this problem? So from the above diagram, we can move either right or down. So a binary tree is built that way. It's written "If we had intermingled common nodes across different branches, we would have got a graph instead" I am unable to visualize how a graph can be formed out of this. Will it be a graph with only 2 columns? Please help

Source: https://loveforprogramming.quora.com/Backtracking-Memoization-Dynamic-Programming

If you just want the visualization, then have a look at this


Distribute objects in a cube so that they have maximum distance between each other I'm trying to use a color camera to track multiple objects in space. Each object will have a different color and in order to be able to distinguish well between each objects I'm trying to make sure that each color assigned to an object is as different from any color on any other object as possible.

In RGB space, we have three planes, all with values between 0 and 255. In this cube $(0,0,0) / (255,255,255)$, I would like to distribute the $n$ colors so that there is as much distance between themselves and others as possible. An additional restriction is that $(0, 0, 0)$ and $(255, 255, 255)$ (or as close to them as possible) should be included in the $n$ colors, because I want to make sure that none of my $(n-2)$ objects takes either color because the background will probably be one of these colors.

Probably, $n$ (including black and while) will not be more than around 14.

Thanks in advance for any pointers on how to get these colors.

All colors will be on the surface of the RGB cube, unless I'm mistaken, for the same reason that all electrical charge appears on the surface of electrical conductors. This suggests the following method to determine colors:

interpret the RGB color space as an XYZ Cartesian space;
interpret candidate colors as charged particles, e.g., electrons;
find the low-energy state of the system through e.g. simulated annealing;

For $n \sim 15$, a highly accurate simulation should be fairly quick; you could use a Runge Kutta technique, or even Euler's method with a small time step could probably do it (much easier to implement/understand). I might suggest the series "Numerical Recipes" for numerical integration/quadrature techniques of interest.

Once particles converge, you have the arrangement of colors by interpreting points as colors. Initially, particles can be arranged randomly on the cube's surface, with a little spacing (helps convergence and stability issues). Putting small groups on faces of the cube should work.

To avoid getting stuck in a local (rather than global) minimum, you can "pulse" some small random electric field after convergence and see whether the system goes back to the same configuration, or a different one. It's somewhat unlikely that randomly placed particles will do that in this scenario, but possible.

EDIT:

As pointed out in the comments, the assumption that optimal solutions should lie only on the surface probably doesn't hold for all geometries in the discrete case.

Fortunately, this has little bearing on the rest of the technique described above. Particles can be initially placed anywhere; just leave some room between pairs of particles for stability and covergence, and then iterate the system to convergence, then pulse a few times (possibly with increasing intensity) to see if you can get the system to converge to some different (possibly better) configuration.

Also note that I believe this method will maximize something like "(harmonic?) average distance between pairs of particles". If you want to maximize the minimum distance between pairs of particles, or some other average (geometric?) between pairs of particles, this may not give you the best solution.

In any event, I feel like this technique will give you an easy way to come up with good approximately-optimal sets of colors... getting actual "optimal" solutions is probably not required for your use-case. Naturally, if an exact and provably optimal solution is desired, numerical simulation is probably not the best way to go.


Finding all cliques of a graph Given a graph with $n \leq 50 $ vertices. Count all $k$-cliques of this graph, where $k = 1, \ldots , n$.

I need the most efficient algorithm.

Your problem (assuming I understand your English correctly) is counting the number of cliques in a graph of size $n = 50$. Counting the number of cliques in a graph is #P-complete (see this paper, which shows that counting the number of independent sets in a graph is #P-complete even for bipartite graphs).

Several efficient exponential time algorithms for the problem (efficient in the sense that their running time is $O(c^n)$ for $c<2$) are described in Jeff Erickson's lecture notes - see section 4.2 on page 4. The simplest algorithm, whose running time is $O(\phi^n)$ (where $\phi$ is the golden ratio), is as follows. For an arbitrary vertex $v \in G$ with neighborhood $N(v)$, we have the following recurrence for the number $I(G)$ of independent sets in $G$ (to get the number of cliques, complement $G$):
$$ I(G) = \begin{cases} 2I(G-v), & N(v) = \emptyset, \\ I(G-v) + I(G\setminus(N(v)+v)), & \text{otherwise}. \end{cases} $$

This algorithm might be practical for $n=50$. If it isn't, you can try the other algorithms described in the lecture notes. Some of them require some modification for your case, and therefore the running times listed there might not hold in your case.


iterative lengthening search example I am looking for an example of the "iterative lengthening search". I have searched and I was only able to find definitions like

  iterative lengthening search an iterative analog to uniform cost
  search. The idea is to use increasing limits on path cost. If a node
  is generated whose path cost exceeds the current limit, it is
  immediately discarded. For each new iteration, the limit is set to the
  lowest path cost of any node discarded in the previous iteration

I'd be deeply grateful for an example, that enables me to understand.

Iterative deepening is not actually the same as iterative lengthening, but they're very similar concepts.

In an iterative deepening search (using depth-first), you use the depth (a measure of distance between nodes) as a limiting factor. So, if you're performing an iterative deepening depth-first search starting at point a, and you set a depth limit of 2, you're asking the algorithm to perform a depth-first search from point a, but to not continue the depth-first search after you get two points away from your starting point a.

e.g.

                       a             In our example, the algorithm would never
                      / \            visit point e. It is more than 2 points
                     b   c           away from a (its depth is greater than 2)
                   /
                  d
                 /
                e

The algorithm will therefore explore all paths from a that are equal to a length of 2 (do not go deeper than depth 2).

In an iterative deepening search, you slowly increase (iterate) the depth at which you limit the search. It tries all paths of length 1 and then all paths of length 2 and so on. This means if there's a path of length 1 to a goal that you're trying to find, this algorithm would find it before trying any paths of length 2, 3, 4, et cetera.

Similarly, an iterative lengthening search uses the cost (or "length") of a path to limit the search rather than the depth. This is useful in situations where connections are weighted. The algorithm would explore all possiblities with a cost of 1 or less, then all possibilities of a cost of 2 or less, and so on. For a real-life example, the cheapest (cost) way to get somewhere is not always the same as the simplest (depth) way to get there. You might have to catch seven buses and a helicopter, but it's cheaper than renting out the Concorde for a single flight. You could consider an iterative deepening search to be a specific case of an iterative lengthening search where you define the "length" that you're iterating as the depth.


Assuming that $P \neq NP$, show that there exist sets $A$ and $B$ in $NP$ such that neither $A \leq _T^p B$ nor $B \leq _T^p A$ My question is as follows: Assuming that $P \neq NP$, show that there exist sets $A$ and $B$ in $NP$ such that neither $A \leq _T^p B$ nor $B \leq _T^p A$, where $A \leq _T^p B$ if there exists a polytime deterministic oracle machine that computes $A$ given access to $B$. That is, $A \leq _T ^p B$ if $A = M^B$ for some Turing machine $M$. I am getting stuck right at the start of the proof.

We have previously shown that there exists $B \in NP$ such that it is not $NP$-complete nor in $P$ by setting up a set of requirements and using delayed diagonalization. Given an $NP$-complete language $A$, and an enumeration of oracle polytime Turing machines $\{ M _e \}_{e\in \mathbb{N}}$, the requirements were
$$R_{2e}: \exists y (A(y) \neq M_e^B(y)) \\ R_{2e + 1} : \exists y(B(y) \neq M_e(y)).$$

I want to try a similar strategy to build $A$ and $B$ in $NP$, thus having requirements
$$ R_{2e} : \exists y (A(y) \neq M_e^B(y)) \\ R_{2e +1}: \exists y (B(y) \neq M_e^A(y)) $$

I don't really know how to start the process in this case, or if this is even the right method here. I would be thankful for some advice on how to continue or on a better strategy. Thanks in advance!

There is a well-known classical result of the theory of $p$-degrees stating that every non-zero $p$-T-degree splits into two incomparable $p$-T-degrees.

So assuming $P\neq NP$, by the splitting theorem, the $p$-T-degree of Turing-complete problem for $NP$ splits into two non-T-complete incomparable $p$-T-degrees.

REFERENCES

Sublattices of the polynomial time degrees

LADNER, R. E. (1973), Polynomial time reducibility, in Proc. 5th Annual ACM Sympos. on Theory of Comput., pp. 122-129

LADNER, R. E. (1975), On the structure of polynomial time reducibility, J. Assoc. Comput. Math. 22, 155-171


Using FFT to solve pattern matching problem with don't cares I've studied about $FFT$ and it's use in string matching, but there are several issues that bother me. First I'll describe the problem and the solution I've seen in class:
Suppose we have alphabet $\Sigma = (a, b, \phi)$ where $\phi$ is "don't care", meaning it matches with every letter, including itself.
We have a text $T = t_{_0}t_{_1}t_{_2}...t_{_n}$, and a pattern $P = p_{_0}p_{_1}p_{_2}...p_{_m}$, assuming $n$ is much bigger than $m$. We say that we have match in index $i$ if for every $0 \leq k \leq m$:
$$P[k]=\phi  \space or\space T[i+k]=\phi \space or\space P[k]=T[i+k]$$
Therefore we introduced new "multiplication" function over $\Sigma$:
$$
f(a,b) =
\begin{cases}
0 & \text{if a = b;}\\
1 & \text{else;}\\
\end{cases}
$$
The idea was to translate every appearance of $a$ and $\phi$ to $0$, and $b$ to $1$, reverse $P \text{ (P$^R = p_{_m}p_{_m-1}p_{_m-2}...p_{_0})$}$, treat both strings as polynomial coefficient vectors and multiply them according to the regularity of $f$. Then in their product vector, $C$, indices that are 0's will tell us there's a match starting in that index in text.
In order to do that efficiently we used $FFT$, however, $FFT$ works with standard multiplication, so in order to bypass that obstacle we calculated $T^c \cdot P^R +T \cdot (P^R)^c$, where $c$ superscript means to "not" the string, for example: $(100010)^c = 011101$, and $+$ means normal addition of vectors. Now I have 2 questions bugging my mind:1) How that thing we did in "not"-ing the strings helps solving the problem about the multiplication. I mean I've tried several examples and it works, but why it works?2) If I wanted to expand this method to bigger alphabet, how could I do it? There's something very binary-oriented in the core of "not"-ing the string, relying on the fact that I have only one pair of letters that create discrepancy.

The idea behind the NOT is that $T^c P^R + TP^{Rc}$ is measuring disagreement rather than agreement. Disagreement can come in two ways: text says $0$, pattern says $1$ ($T^c P^R$); and text says $1$, pattern says $0$ ($TP^{Rc}$). That's why you need two summands.

In more detail, $T^cP^R$ measures the number of indices at which the text was $0$ and the pattern was $1$; $TP^{Rc}$ measures the number of indices at which the text was $1$ and the pattern was $0$; and their sum measures the number of indices at which the text and the pattern didn't match.

When the alphabet has size $r$, you can use a similar approach with $r$ summands (an even simpler solution uses $r(r-1)$ summands). I'll let you figure out the details. (No hints will be given, and solutions won't be verified.) Extra points if you manage to do this with the (possibly) optimal $\lceil \log_2 r \rceil$ summands.