Inheritance, and dynamic access to members/attributes and methods in Java-like languages I have a question about inheritance in Java-like OO programming languages. It came up
in my compiler class, when I explained how to compile methods and their invocation. I was using Java as example source language to compile.

Now consider this Java program.

class A {
  public int x = 0;
  void f () { System.out.println ( "A:f" ); } }

class B extends A {
  public int x = 1;
  void f () { System.out.println ( "B:f" ); } }

public class Main {
  public static void main ( String [] args ) {
    A a = new A ();
    B b = new B ();
    A ab = new B ();

    a.f();
    b.f();
    ab.f();
    System.out.println ( a.x );
    System.out.println ( b.x );
    System.out.println ( ab.x ); } }

When you run it, you get the following result.

A:f
B:f
B:f
0
1
0

The interesting cases are those that happen with the object ab of
static type A, which is B dynamically. As ab.f() prints out

B:f

it follows that method invocations are not affected by the compile-time type of the object the method is invoked with.  But
System.out.println ( ab.x ) prints out 0, so member access is affected by compile-time types.

A student asked about this difference: should not the access of members and methods be
consistent with each other?
I could not come up with a better answer than "that's the semantics of Java".

Would you know a crisp conceptual reason why members and methods are
different in this sense? Something I could give my students?

Edit: Upon further investigation, this seems to be a Java idiosyncrasy: C++ and C# act differently, see e.g. Saeed Amiri's comment below.

Edit 2: I just tried out the corresponding Scala program:

class A {
  val x = 0;
  def f () : Unit = { System.out.println ( "A:f" ); } }

class B extends A {
  override val x = 1;
  override def f () : Unit = { System.out.println ( "B:f" ); } }

object Main {
  def main ( args : Array [ String ] ) = {
    var a : A = new A ();
    var b : B = new B ();
    var ab : A = new B ();
    a.f();
    b.f();
    ab.f();
    System.out.println ( "a.x = " + a.x );
    System.out.println ( "b.x = " + b.x );
    System.out.println ( "ab.x = " + ab.x ); } }

And to my surprise this results in

A:f
B:f
B:f
a.x = 0
b.x = 1
ab.x = 1

Note that the overrise modifiers are necessary. This surprises me because Scala compiles to the JVM, and moreover, when I compile and execute the Java program at the top using the Scala compiler/runtime, it behaves like the Java program.

I suspect that this is intimately related to shadowing of fields in Java.

When writing a derived class, I can, as in your example, write a field x that shadows the definition of x in the base class. This means that in the derived class, the original definition is no longer accessible via name x. The reason Java allows this is so that derived class implementations are less dependent on the base class implementation details, thereby (only partially) avoiding the fragile base class problem. For instance, if the base class did not originally have a field x, but then subsequently introduced one, Java's semantics avoid this breaking the derived class implementation.

The variable x in the derived class can have a completely different type than the variable in the base class – I tested this, it works. This is in stark contrast to method overriding, where the type needs to be sufficiently compatible (aka, the same). So when I have a variable of type A in your example, the only type I can derive for it is the one specified in class A (or above). As this can be different from the type declared in class B, it is only type safe to return the value of the field x from class A. (And naturally, the semantics must be the same regardless of what the type of the field is in class B.)


Star free language vs. regular language I was wondering, since $a^*$ is itself a star-free language, is there a regular language that is not a star-free language? Could you give an example?

(from wikipdia) Lawson defines star-free languages as:

  A regular language is said to be star-free if it can be described by a regular expression constructed from the letters of the alphabet, the empty set symbol, all boolean operators – including complementation – and concatenation but no Kleene star.

Here is the proof of $a^*$ being star-free:

  $\emptyset$ is star-free $\Longrightarrow$
  $\Sigma^*=\bar{\emptyset}$ is star-free $\Longrightarrow$
  If $A\subseteq\Sigma$ then $\Sigma^*A\Sigma^*$ is star-free $\Longrightarrow$
  If $A\subseteq\Sigma$ then $A^*=\overline{\Sigma^*(\Sigma \setminus A)\Sigma^*}$ is star-free

In the last line we have $A^*=\overline{\Sigma^*(\Sigma \setminus A)\Sigma^*}$, because any word that is not of form $A^*$ contains a letter in $\Sigma \setminus A$ and vice versa.

Schützenberger (1965) gave an algebraic characterization of the star-free languages: a regular language is star-free if and only if its syntactic monoid is aperiodic. Contrary to the logical characterization (star-free = FO[<]), this algebraic characterization gives an algorithm to decide whether a given regular language is star-free (the regular language can be given by a finite automaton, a regular expression or a regular grammar). Using the logical characterization (due to McNaughton and Papert) one can then decide the following problem: given a WMSO formula, is there a FO formula describing the same language?

M.-P. Schützenberger, On finite monoids having only trivial subgroups, Information and Control 8 (1965), 190-194.

R.~McNaughton and S.~Papert, Counter-free automata, The M.I.T. Press, Cambridge, Mass.-London, 1971.

A full proof of Schützenberger's theorem can be found in various textbooks or survey papers. For an elementary presentation of the corresponding algorithm (without a proof), see

J.-É. Pin, Finite semigroups and recognizable languages : an introduction, in NATO Advanced Study Institute Semigroups, Formal Languages and Groups, J. Fountain (éd.), 1-32, Kluwer academic publishers, (1995).


0-1 knapsack problem with minimum and maximum weight capacity In classical 0-1 knapsack problem we have maximum allowed value for the weight - weight capacity.

Let's restrict total knapsack weight by min and max values

$$
M \leq \sum_{i=1}^{n}{w_i x_i} \leq W
$$

Is there any known algorithm for this problem?
Is there anything known which is better than brute force?

I failed to find anything about the given knapsack problem variation.

We can change the definition of the traditional Knapsack to "the maximum value we can get from the first n items using exactly W weight" instead of "the maximum value we can get from the first n using at most W weight". The easiest way to do this by replacing the following code:

for j from 0 to W do:
    m[0, j] := 0

from the Wikipedia article dynamic program pseudo code with

m[0, 0] := 0

Then we simply need to check for the maximum value of the range m[n, M] , ... , m[n, W].


Proving that the recurrence $T(n) = 2T\left(\frac{n}{2}\right) + 1$ with $T(2) = 1$ is asymptotically $O(n)$ I've already solved the recurrence exactly and found that $T(n) = n - 1$. Therefore, I know that $T(n) = O(n)$.
However, I'm having trouble showing that $T(n) = O(n)$ without solving the recurrence exactly.
My strategy so far has been to prove that $T(n) \leq cn$ ($c$ is a constant) $\forall n \geq 2$ via induction on $n$.
Clearly, the base case holds $T(2) = 1 \leq 2c$ as long as $c \geq \frac{1}{2}$.
For the inductive hypothesis (IH), I assume $\forall k < n$, $T(k) \leq ck$.
Finally, for the inductive step, I have
$$
\begin{alignat*}{2}
T(n) &= 2T\left(\frac{n}{2}\right) + 1 &&\text{ (by definition)}\\
&\leq 2c\left(\frac{n}{2}\right) + 1 &&\text{ (by IH)}\\
&= cn + 1
\end{alignat*}
$$
However, I can't conclude that $T(n) \leq cn$ from this. Where am I going wrong?

If you can solve a recurrence exactly, then there isn't much motivation to solve it approximately, unless the solution is much easier.
Nevertheless, here is a trick that could actually be useful. Define
$$
S(n) = T(n)+1.
$$
Then
$$
S(n) = T(n) + 1 = 2T(n/2) + 2 = 2S(n/2),
$$
and so $S(2^k) \leq 2^k S(1)$ by induction.
Let's see what this trick gives you more generally.
Application 1
Consider the recurrence $A(n) = 2A(\lfloor n/2 \rfloor) + (-1)^n$, with base case $A(1)$.
Define a new recurrence $T(n) = 2T(\lfloor n/2 \rfloor) + 1$, with base case $T(1) = A(1)$. Prove by induction that $A(n) \leq T(n)$. The technique above shows that $T(n) = O(n)$, hence $A(n) = O(n)$.
Application 2
Consider the recurrence $B(n) = 2B(\lfloor n/2 \rfloor) + \log n$, with base case $B(1)$.
Define $R(n) = B(n) + \log n$. Then
$$
R(n) = B(n) + \log n = 2B(\lfloor n/2 \rfloor) + 2\log n = 2R(\lfloor n/2 \rfloor) - 2\log \lfloor n/2 \rfloor + 2\log n.
$$
You can check that $2\log n - 2\log \lfloor n/2 \rfloor = O(1)$, and so the previous technique shows that $R(n) = O(n)$. It follows that $B(n) = O(n)$.
Application 3
Consider the recurrence $C(n) = 2C(\lceil n/2 \rceil) + 1$, with base case $C(1)$.
Defining $D(n) = C(n) + 1$ with base case $D(1) = C(1)$, we see that
$$ D(n) = 2D(\lceil n/2 \rceil). $$
Let us try to prove by induction that $D(n) \leq Kn - L$. Since $\lceil n/2 \rceil \leq n/2 + 1/2$, if the induction hypothesis holds for $\lceil n/2 \rceil$ then
$$
D(n) \leq 2K(n/2 + 1/2) - 2L = Kn + K - 2L.
$$
Choosing $L = K$, we get $D(n) \leq Kn - L$. Choosing $K = D(2)$, the induction hypothesis holds in the base case $n=2$. Altogether, we have proved $D(n) \leq K(n-1)$ (for $n \geq 2$), and so $D(n) = O(n)$, implying $C(n) = O(n)$.


Automaton for substring matching Given $s$ as a string over some alphabet, what is the best known algorithm to compute a corresponding deterministic finite-state automaton (DFA) that accepts any string that contains $s$?

I am mostly interested of the lowest time complexity so if you tell me what is the best known complexity in O notation to build an automaton for a string that would be just as good.

Hendrik Jan is correct about the Knuth-Morris-Pratt algorithm (warning, wikipedia doesn't explain it particularly well, a text on algorithms is probably a better bet). The failure function can be used to extract a DFA that can perform the string matching. It's not immediately obvious that the failure table is a DFA, but with very little work the transition table for the DFA can be constructed. If $W$ is the pattern string you want to match, the time to build the table (and hence construct the DFA) is $O(|W|)$.

The central idea is that the failure table $T$ (I'll try to use the same names as wikipedia, just to get a ready-made example) tells you where you could be up to in the string if the current match doesn't work out, i.e. if you don't see the next character you're expecting, perhaps the beginning of the match you want has already been seen, you're just mistakenly further ahead, so you only want to "back-track" a little (note, there's no real backtracking in the usual algorithmic sense).

So, shamelessly stealing the example from wikipedia, say we have the failure table $T$:

$$\begin{array}{c|cccccc}
i & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\\hline
W[i] & A & B & C & D & A & B & D \\
T[i] & -1 & 0 & 0 & 0 & 0 & 1 & 2
\end{array}
$$

We can construct the DFA as follows; we have $|W|+1$ states, with a backbone of transitions that match the entire pattern. To match the table we'll call the start state $q_{-1}$ and the final state $q_{|W|}$ (so in the example $q_{6}$). The backbone is then the transitions $\delta(q_{i-1},W[i]) = q_{i}$, so in the example, we go from the start state $q_{-1}$ to state $q_{0}$ on an $A$ and from $q_{2}$ to $q_{3}$ on a $D$.

Now the trick is to add the correct "backwards" transitions so that we don't go too far back along the backbone when we get something wrong. This is where we us the failure function. If we're in state $q_{i-1}$ and we don't see $W[i]$ as the next symbol, then we can alternatively transition to $q_{T[i]}$ if we see $W[T[i]]$. From the example, if we're in state $q_{5}$, and we don't see a $D$, but we do see a $C$, we can go to $q_{2}$. Every other symbol returns us to the start state.

Reiterating; there are three types of transitions, the backbone transition if everything's going fine, the transition given by the failure table so we might be able to recover a bit, and $|\Sigma| - 2$ other transitions that take us back to the start state.

The start and final states are a little special of course, the start state can't go back further, so the failure recovery transition appears with the other transitions, and once we reach the final state, it doesn't matter what else we see, so it's a sink state too.

There's one final wrinkle, the case where the failure symbol is the same as the expected (e.g. $W[1]$ and $W[5]$) in this case we can just defer the decision until they're different, or we can create an NFA.

The example then results in a DFA that looks (barring mistakes) like:

The dashed transitions represent the "everything left over" transitions.

It should be easy enough to see that given the table, we can construct the DFA in $O(|W|)$ time (in one pass really). The table can also be constructed in $O(|W|)$ time - the source code on wikipedia is sufficient. If we get clever, of course we can skip the intermediate table step and use the table building algorithm to just create the DFA immediately. This running time is also the best we can hope for, as a DFA that matches only this string has to have at least $|W|$ transitions (and $|W|+1$ states), so we need to read the entire string $W$, which takes $\Omega(|W|)$ steps.


How to choose between UC and PL when using the DPLL algorithm? We know DPLL algorithm is backtracking + unit propagation + pure
literal rule.

I have an example. There is one example to solve following Satisfiability problem with DPLL. if assign of "0" to variables is prior to assign "1" to variables, Which of Unit Clause (UC) or Pure Literal (PL) is used to solve this specific example?

  $\{\lnot A \lor B \lor C\}, \{A \lor \lnot B \lor C\}, \{A \lor B \lor \lnot C\}, \{A \lor B \lor C\}$

Olympiad Solution is: PL and UC.

Our Solution is just UC.

Who can satisfy me why Olympiad solution is correct ?!

Unit propagation is not possible as there are no unit clauses.

Pure literal rule is not applicable as there is no literals that occur
only positively or only negatively.

Update:
I think in node (3) we can user PL or UC. Isn't it?

If you use the original specification of the DPLL algorithm, in which the unit rule is applied to a fixed point and then the pure literal rule, then only the unit rule is needed to reach a satisfying assignment.  If the rule order is reversed then the pure literal rule is used to eliminate the final unsatisfied clause.

DPLL is a complete and sound algorithm for deciding Boolean satisfiability even if the pure literal rule is removed.  In practice, pure literals are typically removed only during the preprocessing of a SAT instance, where the formula is simplified as much as possible before beginning recursive search.  This is because detecting pure literals during search is computationally expensive enough to more than offset any expected runtime gains.


Whats the point of caching if the minimum single clock cycle time is the prorogation delay of the slowest component (fetching from DRAM)? I know that the clock speed is determined by the slowest stage within the processor (usually fetch) because one clock cycle will take as much time as the slowest pipeline stage to ensure everything is synchronized.

So as fetching from DRAM is usually the slowest stage (for example during LDR instruction to memory which isn't in the cache) the time it takes for this should be the time for one clock cycle. So whats the point of caching?

I mean the processor has to wait anyway for the next clock cycle so even though the processor has fetched memory from cache very quickly wouldn't it have to wait anyway for the end of the clock cycle?

You are right that the clock speed is determined by the slowest stage. But on most architectures it is not true that fetching(or any kind of memory access in fact) takes one cycle. This is an illusion provided by the CPU to makes things manageable. In practice if your CPU tries to fetch and the operation cannot be completed in one cycle then it will stall(on pipelined processor it will introduce a "bubble") until it gets the memory content. Thus if your memory takes 100 cycles to read, then the CPU will stall 100 times in the fetching stage. The same applies to read(and to some extent write) stages.

This is why caching is so important: by caching the processor can reduce the fetch/read/write delay and maintain this illusion that it takes one cycle when really it does not. Example latencies for memory read are:

L1 cache: 1 cycle
L2 cache: 10 cycles
DRAM: 100 cycles

Do not take those figures literally, it is very architecture dependent. But you can see that without caching, your CPU would take 100 cycles to fetch each instruction, this is obviously unacceptable.


What is the difference between caching, buffering and paging? Expecting a detailed answer on the OS level I have been reading about caching and buffering it seems about the same to me can't get hold of the differences clearly and paging, for now the only difference I understand between paging and caching is that, pages store locations of data that are frequently accessed and so CPU can use the address to locate the data, whereas in caching the data itself is stored and wanting process directly acquires the data from the cache. I'm not sure if I'm entirely right which is why I posted the above question.

Paging, caching, and buffering are too broad topics to cover in a single post. Briefly, they serve different purposes:

Operating systems use paging as a memory management scheme. A computer stores and retrieves data from secondary storage (usually HDD) for use in main memory (RAM). For example, virtual memory implementations use paging.

Page caching, on the other hand, is a part of the main memory (say RAM) where you store frequently accesses pages since retrieving from HDD slower than retrieving from the main memory. Please note, I am talking about only page caches. There is for example HDD caches, CPU caches, Web server caches. But all of them have the same goal: to speed up data access.

Buffering typically used for data transfer between OS or program and external devices, Input/Output (keyboard, printer, etc).

In some sense caches and buffers are somewhat similar, both for storing temporary data for read/write speedup. However, buffers are usually associated with a certain device (printer, keyboard, or even a particular file). Two different buffers are used for two different files, while raw data from both files may be stored in a single cache. Unlike caches buffers contain metainformation about files or devices. Buffers usually short-lived but caches may live as long as OS or program runs.

This is just very brief information. For further details you may Google and find tons of information on this subject. Or just get a good book on OS.


smn-theorem: Application by instantiating s with other function The smn-Theorem on the basis of Turing Machines and computable functions rather than programs, as in the Wikipedia article for instance, can be defined as follows:

$$
\begin{align*}
&&& s \langle m, n \rangle &&= \lceil M' \rceil \\
&&\implies &\varphi_{s\langle m, n \rangle} &&= \varphi_{\lceil M' \rceil}\\
&&&&&= f_{M'}\\
&&\implies &\varphi_{s\langle m, n \rangle} (i) &&= f_{M'}(i)\\
&&&&& = f_{M_m} \circ f_{M_{\langle n, . \rangle} (i)}\\
&&&&&=\varphi_m \langle n, i\rangle
\end{align*}$$

where $M_{\langle n, . \rangle}$ denotes, that machine $M_{\langle \rangle}$ has $n$ already pre-written on its tape and $\lceil M \rceil$ denotes the Gödel-number of machine $M$.

Now, I am confronted with the claim, that

$$ \varphi_{h(n)}(i) = f\langle n, i \rangle $$

because

$$ f := \varphi_m \in \text{set of computable functions}$$
then
$$f\langle n, i \rangle = \varphi_m \langle n, i \rangle = \varphi_{s \langle m, n \rangle}(i)$$

therefore it has to be that

$$ h(n) = s\langle m, n \rangle $$

so I guess then it has to be like this:
$$h(n) = \lceil M' \rceil = \lceil f_{M_m} \circ f_{M_{\langle n, . \rangle }} \rceil = s\langle m, n \rangle$$

And so $h$ contains $f_{M_m}$ ... basically just because there can be such a function? Am I interpreting this right?

I think you are reading it backwards.

Usually you want to find $h$ such that $\varphi_{h(n)}(i) = f(n,i)$, where $f$ is a computable partial function. Further, you want $h$ to be total recursive (or even more: primitive recursive).

In order to prove that such an $h$ exists, as well as to concretely define it, one picks any index $m$ for $f$, so that $\varphi_m = f$, and chooses $h(n) = s(m,n)$.

Note that, when reading the reasoning above in the other direction, it becomes wrong. That is: it is not the case that, since $\varphi_{h(n)}(i) = f(n,i)$ we can conclude $h(n) = s(m,n)$.

Indeed, $h$ may also be another function, like e.g. $h(n) = pad(s(m,n))$ where $pad$ is a padding function (which returns the Gödel number for an equivalent TM, such that said Gödel number is larger). Infinitely other (computable) $h$ exist.


Why doesn't subset sum solution violate Exponential Time Hypothesis? The quickest algorithm for solving subset sum currently is $2^{n/2}$ (via Wiki).  Why doesn't this violate the Exponential Time Hypothesis which states that “there is no family of algorithms that can solve 3-SAT in $2^{o(n)}$ time.”

Couldn't a 3-SAT problem be translated to a subset sum problem in polynomial time and then solved in $2^{n/2}$ time.  What am I missing here?

Given a 3SAT problem of size $n$, you can convert that to a subset sum problem of size $n^2$ (roughly).  Now you can apply the algorithm for subset sum to solve the subset sum in time $2^{n^2/2}$ (roughly).  Remember, the running time depends on the size (length) of the input, and here the size of the input will be $n^2$, yielding the $2^{n^2/2}$ figure.

That will give you an algorithm for solving a 3SAT problem of size $n$ in $2^{n^2/2}$ time (roughly).  But that's much worse than the naive algorithm, which takes $2^n$ time: $2^n$ is much smaller than $2^{n^2/2}$.  So this reduction does not contradict the exponential time hypothesis: it doesn't give you a way to solve 3SAT faster than $2^n$ time.


Complexity to generate every combination of every size for a given sequence I would like to estimate complexity in space and time of generating every combination of every size for a given sequence.

Exemple :

 seq = [1,2,3]
 combinations = [{1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}]

From what i know, for a given sequence of size n and a fixed combination size k, the number of combination generated is ${n}\choose{k}$, so i suppose than complexity in time and space is $O({{n}\choose{k}})$.

What we want is the sum for every value of $k$,
 $O({\sum_{i=1}^n{{n}\choose{i}}})$

I know that for a sum the complexity equals to the most complex element of the sum.

For the binomial coefficient, if n is even, the biggest one will be $n \choose \frac{n}{2}$

So i can put a an upper born as $O(n.{n \choose \frac{n}{2}})$

Is there a more precise way to determine the complexity of this operation ?

Each element in the sequence is part of the combination or not (a binary choice). Since there are $n$ elements, this gives $2^n$ possible combinations.

Using a gray code to iterate over the elements we can make sure that we iterate over every possible combination by only putting in or taking out a single element every time.

Assuming your elements are numbered $1\dots n$ we can use the following algorithm. If our current combination $C_k$ contains an even amount of elements, toggle element $1$ to get $C_{k+1}$. Otherwise, toggle element $\min(C_k)+1$ to get $C_{k+1}$.

Starting from the empty combination $\{\}$ we get:

\begin{matrix}
\{\} & \text{even} & \text{toggle $1$}\\
\{1\} & \text{odd} & \text{toggle $\min(\{1\}) + 1$}\\
\{1, 2\} & \text{even} & \text{toggle $1$}\\
\{2\} & \text{odd} & \text{toggle $\min(\{2\}) + 1$}\\
\{2, 3\}  & \text{even} & \text{toggle $1$}\\
\{1, 2, 3\} & \text{odd} & \text{toggle $\min(\{1, 2, 3\}) + 1$}\\
\{1, 3\}  & \text{even} & \text{toggle $1$}\\
\{3\} & \text{odd} & \text{toggle $\min(\{3\}) + 1$}\\
\cdots & \cdots &\cdots
\end{matrix}

By separately storing whether we are currently even/odd and flipping it, and storing our combination in sorted order we can always get to the next combination in $O(1)$ time. So it simply takes $O(2^n)$ time to generate all combinations.


Why we can't use non-deterministic turing machines in this case? Can you explain me why we can't show decidability of problem using non-determinism ? I know that this problem (described below) is not decidability, however I can't understand why following reasoning is not working.

Problem
Given a context free grammar $G$, does there exists a word $w∈Σ^∗$ such that $w^4∈L(G)$ ?

My reasoning:
Lets show Turing machine which decide this problem. Let machine guesses some word $w$ (it is possible because word is finite and $Σ$ is finite) and check if (using CYK algorithm) $G$ generates $w^4$.

I totally don't understand why this approach doesn't work. After all, non-determinism is about guessing...

Your reasoning is not wrong. But recall that decidability requires TM machine halt with YES if $\exists w \text{ such that } w^4 \in L(G)$ or NO if $\nexists w \text{ such that }w^4 \in L(G)$. In other words, the TM always halts.

In your approach the TM machine has to guess infinitely many strings and check if their forth power belongs to $L(G)$. A nondeterministic Turing machine cannot check infinitely many strings in finite amount of time.

Decidability problems efficiently solved by non-deterministic Turing machines are also solved by deterministic Turing machines. In other words, their computational powers are equivalent.


Is there a data structure for efficiently searching a string that contains a given substring? This question arose from a practical problem: given a set of texts, find one, which contains a given string (not word).

Let $S$ be a set of $n$ strings, and $l$ the length of the longest string in $S$. What will be the best data structure to efficiently search a string that contains a substring of length $k$ in $S$?

Sequential scan with Knuth–Morris–Pratt algorithm yields $O(n(l+k))$ searching complexity.
I thought maybe something similar to tries exists.

You could append all of the $n$ strings together, and add an arbitrary character '\$' not in the pattern to separate them. Then you could apply the Z algorithm on your original pattern and this new string to yield time complexity $O(nl+k)$ which is more efficient than your suggested $O(nl+nk)$.

Actually, you could still iterate with KMP for $O(nl+k)$ time, beceause the $k$ component is preprocessing the pattern you are trying to find. This only has to be done once, regardless of the number of strings you are checking.


Proving Regularity of Languages that are 1/k of an already known regular language There is this question in Kozen, that states if a language is regular then the first half would also be regular. Also I found a material on the internet that extends the thinking saying a language that is two-thirds of already known regular language is regular. I'm tempted to think that it should also hold true for any general $k>0$ that $m/k$th ($1 \leqslant m \leqslant k-1$) portion of a regular language would also be regular. I need a mathematical proof ( or a constructive proof having mathematical verifications done on it ) for the above statement.
   EDIT: For the "first half Language" which is much better formalised by David in the comments, I tried a similar argument as the answer in the link given by Hendrik. The product automaton notion was intuitively clear. But I was stuck with the transition listings for the 2nd state in the pair of states so formed by constructing the product automaton. I was flummoxed as to how I could be able to get the exact state for the corresponding word 'w' which would be the "first half" of a word accepted by the original regular language.

Let $L$ be a regular language and let $(p, q) \in \mathbb{N}^2$. Then the following language is regular:
$$
  L_{p,q} = \{ u \in A^* \mid  \text{there exist $x$ and $y$ in $A^*$ such that $|x| = p|u|$, $|y| = q|u|$ and $xuy \in L$} \}
$$
Furthermore, for any subset $S$ of $\mathbb{N}^2$, the language
$$
  L_S = \bigcup_{(p,q,r) \in S} L_{p,q}
$$
is also regular. I would like to insist that it works for any any subset $S$, including non recursively enumerable subsets of $\mathbb{N}^2$, which might look a little bit suspicious at first glance...

You can try to prove these results by using automata, but it is much easier to use the fact that a language is regular iff it is recognized by a finite monoid.

Let $L$ be a regular language of $A^*$. It is recognized by a finite monoid $M$, that is, there is a surjective monoid morphism $f:A^* \to M$ and a subset $P$ of $M$ such that $f^{-1}(P) = L$. Now $\mathcal{P}(M)$, the powerset of $M$, is also a finite monoid under the multiplication defined, for $X, Y \in \mathcal{P}(M)$, by $XY = \{ xy \mid x \in X, y \in Y\}$.

Let now $h: A^* \to \mathcal{P}(M) \times M$ be the monoid morphism defined, for each letter $a \in A$, by $h(a) = (f(A), f(a))$. Then for each word $u$, $h(u) = (f(A^{|u|}), f(u))$. I claim that $L_{p,q} = h^{-1}(Q)$ where
$$
   Q = \bigl\{(R,m) \in \mathcal{P}(M) \times M \mid R^pmR^q \cap P \not= \emptyset \bigr\}.
$$
and similarly $L_S = h^{-1}(T)$ where
$$
   T = \Bigl\{(R,m) \in \mathcal{P}(M) \times M \mid \Bigl(\bigcup_{(p,q) \in S}R^pmR^q\Bigr) \cap P \not= \emptyset \Bigr\}.
$$
Thus $L_{p,q}$ and $L_S$ are recognized by the finite monoid $\mathcal{P}(M) \times M$ and hence are regular.

Proof of the claim.
\begin{align*}
  h^{-1}(Q) &= \{u \in A^* \mid (f(A^{|u|}), f(u)) \in Q \} \\
  &= \{u \in A^* \mid f(A^{p|u|}f(u)f(A^{q|u|}) \cap P \not= \emptyset \} \\
  &= \{u \in A^* \mid f(A^{p|u|}uA^{q|u|}) \cap P \not= \emptyset \} \\
  &= \{u \in A^* \mid A^{p|u|}uA^{q|u|} \cap f^{-1}(P) \not= \emptyset \} \\
  &= \{u \in A^* \mid A^{p|u|}uA^{q|u|} \cap L \not= \emptyset \} \\
  &= L_{p,q}
\end{align*}


maximal independent set on grid graph proof I'm trying to figure out proof of maximum independent set from: this link. (1b part).
And I'm bit confused why exactly sum of $w(v)$ is less than or equal to sum of $w(v')$.
Shouldn't it be other way around? As we define $v'$ if it is in $T$ and is in $S$

As we define v′ if it is in T and is in S

I think you're misinterpreting the definition of $v$:

For each $v \in T$, define $v'=v$ if $v\in S$ or as its neighbor in $S$ otherwise

$v'$ is always defined; it's just a question of what it's defined to be. The above definition means that, if $v \in S$, $v'$ is defined to be $v$, and if $v \notin S$, $v'$ is defined to be $v$'s greater-or-equal-weight neighbour in $S$ (the existence of which was established in part 1a). Then $w(v) \le w(v')$ for each $v \in T$ by construction.
(This is the only way I see to parse the definition that makes grammatical sense, though I think it could be worded better, to prevent people reading "define $v'=v$ if $v\in S$" as a "parenthesised unit".)


Board cutting problem To cut a wooden board, a sawmill charges proportional to the length of the board. The cost of cutting a single board into many smaller boards will thus depend on the order of the cuts. As an example, lets say cutting a $10m$ board into two pieces costs $10$. Then to cut a $10m$ long board at marked positions $3m$ and $5m$ costs $10+7=17$ if it is ﬁrst cut at position $3m$ and then at $5m$. On the other hand, if it is cut at $5m$ position ﬁrst, and then at $3m$, it would cost $10+5=15$. As input, you are given a board of length $n$ with $k$ marks on it. You need to give an algorithm that, given an input length $n$ and a set of $k$ desired cut points along the board, will produce a cutting order with minimal cost in $O(k^c)$ time, for some constant $c$

I'm getting $O(k!)$ complexity :(

To me, the way the cutting cost analogy is unnatural. I'm going to work with an equivalent problem instead. Additionally, I'll think about the task in reverse, combining pieces instead of cutting.

An equivalent problem:

  Given a sequence of integers $s_0,s_1,\ldots,s_k$. We want to find the order of adding up all the integers such that the cost of this process is minimize. The add operation only works on each adjacent pair in the sequence and will replace the pair with its sum. The cost of each add operation is the resulting sum.

I'll think about the problem of finding lowest cost first. The order of adding can be traced back if you have the algorithm to find the lowest cost.

Define $M(i,j)$ to be the lowest cost of this process on the subsequence

  $s_i,s_{i+1},s_{i+2}\ldots,s_{j-2},s_{j-1},s_j$

where $0 \le i \le j \le k$

We can then formulate $M(i,j)$ in terms of smaller problems as follows:

  $M(i,j) = \Sigma_{y=i}^{j} s_y + \min\limits_{x \ldotp i \leq x < j} \{M(i,x) + M(x+1,j) \}$

for the case that $j-i>2$

I'll leave the base case of $j-i \le 2$ and the order of which $M(i,j)$ to calculate first for reader to work out.

The algorithm has to calculate $M(i,j)$ for every $0 \le i \le j \le k$ and each time it does that, it has to iterate over $x$. Thus, the time complexity is $O(k^3)$


Instruction Set Architecture (ISA) design Yes, this is a homework question, I've tried working it out and was hoping I could get pointed in the right direction.
Here's the question:
You are designing the instruction set for a new type of computer. The
computer has 64 instructions, 16 general-purpose registers. It supports a
byte-addressable memory of up-to 32MB. Answer the following question:
a. For a 3-operand ADD instruction that only uses register addressing
mode, how long (number of bits) should the instruction be?
b. For a 2-operand ADD instruction, in which one of the operands is a
memory location with direct addressing mode, how long (number of
bits) should the instruction be?

I know the question's been asked recently but both questions and answers weren't helpful.
I know that with 64 instructions and 16 registers, there must be 4 bits per register.  I don't exactly know the usage for the 32MB memory right now.
A similar example of part (a) exists on Wikipedia, where it states 4 instructions are needed for a 3-operand register addressing mode (load reg1 into a load reg2 into b, add reg1 and reg2 to reg3, store reg3 in c).  Because it mentions 4 instructions, I thought that would be 1 bit, but that's a really small amount.  There are 3 registers used in the instruction, which would be 12 bits.
For part (b), I believe one is a memory location with a direct addressing mode (as stated) and the other is like part (a), using register addressing mode.  There are only two operands, but only one is using register addressing mode, meaning only one register is used?  In that case, the length of the instruction should be 4 bits.
I would appreciate any help! If I'm misunderstanding some of the terms please let me know! Thanks!

Hint: If there are $X$ of some resource, then it takes $\log_2 X$ bits to encode which of them you chooses. This includes instructions, registers, and memory locations. If you are encoding $N$ copies of the resource, you will need $N\log_2 X$ bits. The instruction should contain an encoding of everything needed to specify it, including the instruction itself.

(Real life CPUs don't quite behave this way. For example, common instructions could have shorter length.)

Example: A computer has $956$ instructions. The instruction NOP takes $\lceil \log_2  956 \rceil = 10$ bits.

Another example: A computer has $13$, and $100$ I/O ports. The instruction IN , which reads a byte from the port into the accumulator, takes $\lceil \log_2 13 \rceil + \lceil \log_2 100 \rceil = 11$ bits.

Yet another example: A (useless) computer has a single instruction but $10000$ registers. The single instruction takes $10$ of them and does something really complicated. It takes $\lceil \log_2 1 \rceil + 10 \lceil \log_2 10000 \rceil = 140$ bits to encode.


Virtual Memory - Non-contiguous Memory Allocation I'm studying for my operating systems final, and one question that my professor asked that I can't seem to find the answer to is the following:

"Why does virtual memory use non-contiguous memory allocation?"

The textbook only talks about virtual memory in the context of non-contiguous memory allocation, but never explains why. The only reason I can think of is because of page replacement, but I'm not even sure that's right. Anyone have any thoughts on this?

Your professor asked you a tricky question. The answer is - by definition.

The virtual memory is a mechanism to map non-contiguous physical memory to contiguous logical memory (for each running process). Why does the free physical memory become non-contiguous? Well, processes start and stop in unpredictable order, so the memory of stopped processes ought to be reused.


Standard constructive definitions of integers, rationals, and reals? Natural numbers are defined inductively as (using Coq syntax as an example)

Inductive nat: Set :=
| O: nat
| S: nat -> nat.

Is there a standard way to define integers (and maybe other sets like rationals and reals) constructively?

Gilles answer is a good one, except for the paragraph on the real numbers, which is completely false, except for the fact that the real numbers are indeed a different kettle of fish. Because this sort of misinformation seems to be quite widespread, I would like to record here a detailed rebuttal.

It is not true that all inductive types are denumerable. For example, the inductive type

Inductive cow :=
   | nose : cow
   | horn : (nat -> cow) -> cow.

is not denumerable, for given any sequence c : nat -> cow we may form horn c which is not in the sequence by well-foundedness of cattle. If you want a correct statement of the form "all inductive types are countable" you have to severely limit the allowed constructions.

The real numbers cannot be easily constructed as an inductive type, except that in homotopy type theory they can be constructed as a higher inductive-inductive type, see Chapter 11 of the HoTT book. It could be argued that this is cheating.

There are a number of constructive definitions and constructions of the reals, contrary to Gilles claim. They can be broadly divided into two classes:

Cauchy-type constructions in which the reals as seen as a metric completion of the rational numbers. This sort of construction often requires quotients, although one may be able to get away with a coiunductive definition, dependig on how one treats equality. A naive construction typically requires countable choice as well, but Fred Richman gave a completion procedure which works constructively without choice, see his Real numbers and other completions.
Dedekind-type construction in which the reals are seen as (two-sided) cuts of rationals. This sort of construction usually requires powersets or a similar device, although it is possible to do it just with some basic $\lambda$-calculus and the axiomatization of the Sierpinski space $\Sigma$, see Dedekind reals in Abstract Stone Duality.

On the implementation side, we have various constructive formalizations of reals (but not the one in the Coq standard library which is just awful), for instance Robbert Krebbers's and Bas Spitters's Computer certified efficient exact reals in Coq.

For an actual implementation of exact real numbers I point you to Norbert Müller's iRRAM.

Lastly, Gilles remark about denumerable subsets of reals is off the mark. It is perfectly possible to construct or define uncountable sets, in whatever constructive setting you live. For example, the Baire space $\mathbb{N} \to \mathbb{N}$ of all sequences of numbers is alway uncountable, even if you think that every function is Turing-computable -- see my blog post for an explanation.


How to check if a specific ILP problem can be solved in polynomial time or not? How can we know that a specific ILP problem is solvable in polynomial time or not given the constraints?

First of all, let me start by making clear that the notion of 'solvable in polynomial time' is something defined on a class of problem instances. It makes no sense to speak of polynomial time for a single problem as any single problem can be solved in $O(1)$!

That said, there is a notable class of ILP's that is known to be polynomial time solvable. This class consists of the ILP's that can be described with a totally unimodular matrix (or equivalently, if the solution space is an integral polyhedron). This property guarantees that the relaxed version of the ILP has in fact the same solution as the original ILP!

However, this doesn't mean that there aren't other classes of ILP's for which there exists an algorithm that can solve them in polynomial time (In fact, as it is possible that P=NP, it is possible that the class of all ILP's is solveable in polynomial time!)

So, in general, a complete answer to your question is beyond the current state of science, but there are special cases where can say that it is poly-time solvable. However, we cannot say for sure that there even exist classes that are not.


Languages with infinitely many but finite Myhill-Nerode equivalence classes I'm kind of new to automata theory and I'm dealing with the equivalence classes used for example in the Myhill-Nerode theorem right now; in other words aba* / a = ba*; aba* / b = ⌀, and such.

In an exercise I'm asked to find a language defined by an infinite set of equivalence classes, but where each class is actually finite. Unfortunately this seems a bit counterintuitive to me, and I can only manage to find languages with an infinite set of equivalence classes where the classes are infinite.

If someone could help me out with the reasoning, and what I'm missing here, I'd really appreciate it.

A random language would do. If $L$ is chosen by putting every word in $\Sigma^*$ in $L$ with probability $1/2$, then for every two given words $x \neq y$ and any third word $z$, the probability that $xz \in L \Leftrightarrow yz \in L$ is $1/2$. Hence almost surely $x$ and $y$ are not equivalent (since we can choose an infinite sequence $z_i$ so that the words $xz_1,yz_1,xz_2,yz_2,\ldots$ are all distinct). Since there are only countably many pairs of words, we find that almost surely, every word is its own equivalence class.

It is also not too difficult to explicitly construct such a language. It suffices to find a subset $A$ of the natural numbers such that for every $x,y \in \mathbb{N}$ there exists $z \in \mathbb{N}$ such that $x+z \in A \not\Leftrightarrow y+z \in A$ (why?). Let
$$
A = \bigcup_{i=0}^\infty \{4^i+1,\ldots,2\cdot 4^i\}.
$$
Given $x < y$, let $z = 4^y + 1 - y$. Then $z + y = 4^y + 1 \in A$, while $x + z < 4^y + 1$ and $x + z \geq z = 4^y + 1 - y > 2 \cdot 4^{y-1}$ (check!), showing that $x + z \notin A$.


What is the name of the variant of ICP where the correspondence of the points are known? Traditional ICP assumes that the inputs are point clouds with no predefined correspondences between the clouds.

If I know before hand that some / all points in one point cloud corresponds to some / all points in the other point cloud, I assume this becomes an easier problem to solve.

What is the name of this modified version of point set registration and what are some algorithms that solves this?

This problem is called "rigid registration", the correspondences being the "rigid" part.

As D.W. pointed out, you can do a least squares fit (or use something like RANSAC to find the correspondences and then do a least squares fit). In the absence of noise, the least squares fit has a particularly nice formulation which has been known for a long time.

If $\mathbf{x}_i$ and $\mathbf{y}_i$ are the two corresponding sets of coordinates (there are $n$ points), we want to find the rotation matrix $R$ and translation vector $\mathbf{t}$ which minimises:

$$\hbox{arg min} \frac{1}{n}\sum_i \left\Vert \mathbf{y}_i - R \mathbf{x}_i - \mathbf{t}\right\Vert^2 $$

Calculate the covariance matrix:

$$\mathbf{\mu}_x = \frac{1}{n} \sum_i \mathbf{x}_i$$
$$\mathbf{\mu}_y = \frac{1}{n} \sum_i \mathbf{y}_i$$
$$\Sigma_{xy} = \frac{1}{n} \sum_i (\mathbf{y}_i - \mathbf{\mu}_y) (\mathbf{x}_i - \mathbf{\mu}_x)^\intercal$$

Compute the singular value decomposition of the covariance matrix:

$$\Sigma_{xy} = U S V^\intercal$$

Then:

$$R = V U^\intercal$$

This algorithm can be made more robust in the presence of noise. There are also more recent algorithms which are competitive.


Why there is no polynomially large sequence of polynomial large weights that derandomize the isolation lemma? I was studying the paper Derandomizing the Isolation Lemma and Lower Bounds for Circuit Size by Arvind and Mukhopadhyay and came across the following claim (Observation 1.2 on page 3):

"More precisely, for any
polynomially bounded collection of weight assignments $\{w_i\}$ $i \in [n^c]$ with weight range $[n^{c'}]$, there exists a
family $F$ of subsets of $[n]$ such that for all $j \in [n^c]$, there exists two minimal weight subsets with respect to $w_j$.

They claim that this follows from a counting argument that uses the existence of $2^{(2^n)}$ set systems. The article they cite does not contain a proof of this assertion.

Question: What proof are they thinking of? Why is their claim true?

I learned the following argument from Dieter van Melkebeek (but any mistakes are my own). I'm not sure that this is what Arvind and Mukhopadhyay had in mind, because the assumptions are not the same, as I point out after the argument. I am still interested in learning alternative proofs.

The idea will be to start with the collection of all subsets, and iteratively fix it by removing subsets until the conditions are satisfied. This is similar to the deletion method from the probabilistic method.

We will iterate the following algorithm:

F := Powerset([n])
While there is some i in [n^c] such that w_i makes F min unique:
    Update F by removing the element with min w_i weight.

It suffices to show that this algorithm terminates with a non-empty set $F$.

To wit, note that each time we find such an $i$, the minweight of $F$ under $w_i$ increases by at least $1$. Since the max weight of any set under $w_i$ is $n^{c' + 1}$, this means that for each weight $w_i$, we can update $F$ at most $n^{c' + 1}$ times during the algorithm. Thus, in total $F$ is updated at most $n^{ c + c' + 1}$ times. Since each step removes one set from $F$, this means that $F$ is nonempty at the end of the procedure provided that $2^n > n^{ c + c' + 1}$.

Additionally, at the end of the process $F$ can be culled to size at most $2n^{c}$, by picking two min-weight sets for each $w_i$ $i \in [n^c]$.

Since we delete up to $n^{c + c' + 1}$ sets from $F$, we only need to work with a universe of set systems of size ${2^n \choose n^{c + c' + 1} } = O( 2^{(n^{c + c' + 2})})$. This makes me think that this argument is not the one that uses the fact that there are $2^{2^n}$ set systems.


Meaning of double colon $::$ I've came across this expression regarding function composition in some notes by people from computer science, and I don't know what the notation "$::$" means.

\begin{equation}
g \circ f : A \rightarrow C :: a \mapsto g(f(a))
\end{equation}

I get what this expression is trying to tell me, but I am pretty disturbed by the fact that I don't know what "$::$" means exactly and how to read it. Can anyone tell me what is "$::$"?

It stands for "given by" or "defined by". The function $g \circ f$ is a function from $A$ to $C$ which maps $a$ to $g(f(a))$.


Compute equality comparison without comparison operators Is there a possibility to compute the result of an integer equality comparison by only using arithmetic or bitwise operations? Negative values use the two-complement representation.

I am looking for a generic algorithm, which results in two possible values for equality and inequality but not using comparison operations.

Let $W$ be the number of bits, $A, B$ integers to compare.

$Result =
(NOT((A - B) \text{ OR } (B - A))) >> (W - 1)$.

Here NOT negates bits. $A - B$ and $B - A$ is zero iff numbers are equal otherwise they are of different signs which ORed together will give a negative number.
The result is $1$ if numbers are equal and $0$ otherwise.


Understanding the Bitcoin White Paper's Notion of "Signing" and "Verifying" Consider from the Bitcoin white paper a graphic that includes dotted arrows, labeled "sign" and "verify":

What does it mean to "sign" and "verify", as outlined in this paper? Are the terms "private key" and "public key" used in the same way that they are in the RSA encryption algorithm?

Yes. It means "sign" and "verify" exactly as in a public key system such as RSA. Bitcoin doesn't introduce new cryptographic primitives or notions; it simply combines existing ones in a novel way. So you would simply use a public key system such as RSA to implement those operations in Bitcoin. The actual algorithm used is ECDSA, but this predates Bitcoin by quite a while. Arguably the "break-through" in Bitcoin is a clever mix of existing cryptographic techniques and aligning incentives.

Another clever aspect is that Bitcoin solves a different problem than what cryptographers traditionally viewed as "digital cash". That is, Bitcoin doesn't meet all the desiderata that one would hope "digital cash" would have, but clearly it's a pretty effective solution to the colloquial meaning of "digital cash".


Transform Standard-Dual program to Canonical-Dual program Say I have the following Standard-Dual linear program:
$$max<\vec b, \vec y>$$
$$s.t.:A^Ty \le \vec c$$
$$\vec y \ge \vec 0$$
Is there a way to transform it to a Canonical-Dual and equivalent linear program, i.e., that of the following form:
$$max<\vec b', \vec y'>$$
$$s.t.:A'^Ty' \le \vec c'$$
$$\vec y' \in \mathbb R^n$$

Yes. For each variable $y_i$, just add the constraint $-y_i \leq 0$, and then you don't have to assume that $\vec{y} \geq 0$.


Partitioning a boolean circuit for automatic parallelization tl;dr: I have a problem where I have a Boolean circuit and need to implement it with very specific single-thread primitives, such that SIMD computation is significantly cheaper after a threshold. I'm trying to optimize the implementation.
Going into detail, the input is a combinatorial Boolean circuit (so no loops, state, etc.). I'm implementing it in software with a rather unusual set of primitives, such that:

logic gates must be computed one at a time, as the "engine" is single-threaded
NOT gates are free
AND, OR, XOR have a cost of 1 (eg. 1 second)
N identical gates can be evaluated at the same time for a cost of 10 plus some tiny proportional term (eg. a batch of 20 distinct AND gates can be evaluated in 10 seconds, 50 distinct XOR gates in ~10 seconds, etc.)

The objective is to implement the circuit with the given primitives while minimizing the cost.

What I tried
This problem looks vaguely related to the bin packing problem, but the differences - constraints on the order of the items and different cost for each "bin" depending on the number of items - make me think it's not particularly applicable.
I was suggested to use integer linear programming, which sounds like the best fit so far, but I'm not sure how to represent the problem. Specifically, I'd use binary variables to represent whether the implementation gate/batch M is used in place of the circuit gate N, but then I don't know how to express the objectives to be maximized/minimized.

One approach for formulating this as an ILP problem could be to have zero-or-one variables $x_{i,t},y_{i,t},z_t$, with the intended meaning that $x_{i,t}=1$ if the $i$th gate is evaluated in the $t$th instruction (not as part of a batch), or $x_{i,t}=0$ otherwise; and $y_{i,t}=1$ if the $i$th gate is evaluated in a batch in the $t$th instruction, or $y_{i,t}=0$ otherwise; and $z_t=1$ if the $t$th instruction is a batch instruction, or $z_t=0$ otherwise.

Your problem can then be represented as an integer linear program, with some constraints to enforce consistency of these boolean variables:

Each gate is assigned to a single instruction: $\sum_t x_{i,t} + y_{i,t}=1$.
Non-batch instructions are assigned a single gate: $\sum_i x_{i,t} = 1-z_t$.
Non-batch instructions don't set any $y$ values: $\sum_i y_{i,t} \le C z_t$, where $C$ is a large constant equal to the maximum batch size (or the number of gates, if there is no limit).
Gates can only be batched together if they compute the same logic function: $y_{i,t} + y_{j,t} \le 1$ for each pair of gates $i,j$ that have a different logic function.
A gate can only be evaluated once all of its inputs are ready: $x_{i,t} + y_{i,t} \ge x_{j,u} + y_{j,u}$ for each pair of gates $i,j$ such that the output of $i$ is an input to $j$, and for each pair $t,u$ with $t<u$.

(I'll assume you treat NOT gates as free and don't try to assign them to any instruction; they just happen automatically.)

Now any consistent assignment to the $x$'s and $y$'s will correspond to a valid way to implement the circuit.  The cost of this assignment will be $9 \sum_t z_t + c \sum_{i,t} y_{i,t} + k$, where $c$ is the tiny proportional term and $k$ is the total number of instructions in the schedule (both $c$ and $k$ are constants).  If you pick a value for $k$, the maximum number of instructions allowed, you can use an ILP solver to minimize $9 \sum_t z_t + c \sum_{i,t} y_{i,t} + k$ subject to the inequalities above, and this will give you the best way to schedule your boolean circuit using $k$ instructions. Then, I suggest you search over different values of $k$, solving an ILP for each one, to find the best boolean circuit.

Be prepared: ILP is NP-hard, so finding the optimal solution might take a very long time if the circuit is large and you're aren't very lucky.  Some ILP solvers have the ability to terminate their search after a fixed time limit and return the best solution they've found so far, which might be useful if that happens.


Meaning of complexity of a computational problem If I understand correctly, the complexity of solving a computational problem is defined in terms of which instance $I$ of the problem, what size $n$ of the problem instance, and what algorithm $A$ for solving the problem instance.

Is the complexity of the problem at a given size $n$ of the problem instance defined as
$$
\min_A \max_{I\in \{\text{instances of size }n\}} \text{complexity}(A,I,n)?
$$
Note that the solution to the above optimization $A^*(n)$ and $I^*(n)$ are both functions of instance size $n$.

Or is the complexity of the problem defined for some same algorithm for all the problem instances and all sizes of the problem instances?

Or is the complexity of the problem defined for some same instance for all the algorithms that solve the problem and all the problem instance sizes?

You are missing one thing, namely that the optimal algorithm and worst instance are not simply functions of the instance size. Also, I am not sure that minimising/maximising algorithm and instance independently of each other is doing the right thing.

The complexity of a problem is the complexity of an optimal algorithm solving the problem in the chosen machine model. It's as simple as that, but of course we have to define what "optimal algorithm solving the problem" means. Note that we have to fix the machine model (in particular what to count, see below), as complexities can differ between models.

First, "solving the problem" is clear: for all inputs (that are instances of the problem), the algorithm should give the correct answer, i.e. terminate and produce the correct result, or don't terminate. Let's denote the set of all algorithms that solve problem $P$ with $\newcommand{\Alg}[1]{\mathsf{Alg}_{#1}}\Alg{P}$.

Second, what is the "complexity" of an algorithm? There are many ways to investigate runtime; complexity theory has defaulted to worst-case time and Landau classes. Formally, we define the (worst-case) runtime function of some algorithm $A$ to be

$\qquad \displaystyle T_A(n) = \max \{ T_A(x) \mid x \in I_P, |x|= n \}$

where $I_P$ is the set of instances of the problem $P$ (which $A$ solves) and $T_A(x)$¹ is the runtime of $A$ on input $x$² (in clock cycles, state transitions, whatever fits your machine model). Now, the complexity of $A$ is the asymptotic growth of $T_A$. For example, if $T_A(n) = 17n^2 - 5n + 13$, we would say "The complexity of $A$ is $\Theta(n^2)$".

Finally, an optimal algorithm (for $P$) is an algorithm with minimal complexity (among all algorithms in $\Alg{P}$)³.

We abuse notation here: depending on its parameter, $T_A$ means different things. It is usually done this way, though, and we don't need the runtime on individual inputs later on.
Let's assume for the moment that we deal only with deterministic algorithms. Otherwise, there may be many different runtimes for a given input. In that case, we would choose the runtime of the longest computation; see here for reasons why.
Note that Landau-$O$ implies a partial order on functions: $f \leq g \iff \exists c \in \mathbb{N}.\,\limsup\limits_{n \to \infty} \frac{f(n)}{g(n)} \leq c$.


Graph isomorphism problem for labeled graphs In the case of unlabeled graphs, the graph isomorphism problem can be tackled by a number of algorithms which perform very well in practice. That is, although the worst case running time is exponential, one usually has a polynomial running time.

I was hoping that the situation is similar in the case of labeled graphs. However, I have a really hard time to find any reference which proposes an "practically efficient" algorithm.

Remark: Here, we require that the isomorphism preserves the labels. That is, an isomorphism between two finite automata/process algebra terms would imply that the automata/terms are essentially "equal up to renaming of the nodes".

The only reference I found was the one in Wikipedia that states the the isomorphism problem of labeled graphs can be polynomially reduced to that of ordinary graphs. The underlying paper, however, is more about complexity theory than practical algorithms.

I am missing something, or is it really the case that the there are no efficient "heuristical" algorithms to decide whether two labeled graphs are isomorphic?

Any hint or reference would be great.

You might be interested in this paper:

Aidan Hogan:
Skolemising Blank Nodes while Preserving Isomorphism.
WWW 2015: 430-440

It has an algorithm (based on Nauty) for testing the isomorphism of RDF graphs, which are essentially directed labelled graphs that may contain fixed labels. The algorithm takes labels into account to narrow the search space.

If you can represent your input labelled graph as an RDF graph, you could try use the associated software package "blabel" to test isomorphism.


Relevance of depth for $NP$-completeness of fan-in $2$ and fan-out $1$ modest depth circuits? Let $\mathcal C$ be a circuit of $m=f(n)$ input wires

where every input is taken in the set $\{x_1,x_1',\dots,x_n,x_n'\}$ where $x_n\in\{0,1\}$ and $x_n+x_n'=1$ holds (not all $x_i,x_i'$ necessarily needs to be utilized if $f(n)=o(n)$)

where every layer of the circuit is all $AND$ or all $OR$ gates having fan-in $2$ and fan-out $1$, and the AND and OR layers alternate

depth of the circuit is $\leq\log^kn$ at a $k\geq0$

(essentially an $NC^k$ circuit having gates of fan-out $1$).
The question is whether $\exists x_1,\dots,x_n\in\{0,1\}:\mathcal C(x_1,\dots,x_n)=1$.
Usual $NP$-completeness is for $CIRCUITSAT$ where depth can be $poly(n)$ without restricting to fan-out $2$ and fan-in $1$. If depth is $k=O(\log n)$ do we still get $NP$-completeness if gates are fan-in $2$ and fan-out $1$ and number of input wires $poly(n)$?

Is it $NP$-complete at all fixed $k\geq1$ if $f(n)=poly(n)$?

If $k=0$ the problem is in $P$ because the number of input wires is $O(1)$.

Is there a complexity class for the problem if $0<k<1$ holds?

Circuits with fan-out 1 are called formulas.
Polynomial-size fan-in 2 formulas of arbitrary depth can be rebalanced to depth $O(\log n)$ by Spira’s lemma, hence they compute exactly nonuniform $\mathrm{NC}^1$. (The restriction that layers alternate between AND and OR is immaterial, as one can always insert dummy nodes to make it true, while at most doubling the depth.) Thus, your model with $k\ge1$ collapses to $k=1$.
Satisfiability is NP-complete already for 3-CNF. These can be written as depth $O(\log n)$ fan-in 2 formulas by arranging the outer conjunction as a balanced binary tree. (Again, one might insert dummy OR gates to make the connectives alternate if desired.)
For $k<1$, the formula only depends on $2^{(\log n)^k}$ variables, and therefore its satisfiability is computable in time $2^{O(2^{(\log n)^k})}$. Thus, it cannot be NP-complete unless ETH fails. There is no special complexity class for it, it is just NP scaled down to inputs of size $2^{(\log n)^k}$.
Better, satisfiability of circuits of depth $(\log n)^k$ for $k<1$ is not NP-complete unless P = NP: if it is NP-complete, then there exists a poly-time reduction $f$ of CIRCUIT-SAT to itself that maps a circuit of size $n$ to a circuit of size $2^{O((\log n)^k)}$. Using $\log\log\log n/\log(k^{-1})$ iterations of $f$ (which are computable in polynomial time), we reduce CIRCUIT-SAT to satisfiability of a constant-size circuit, which is trivial to decide.


Constructing a PDA with an unequal number of a/b I'm looking at this pdf for problems: http://www.public.asu.edu/~ccolbou/src/355hw5solf10.pdf

I found question 3g to construct a pushdown automata for the following:

{$ {a^i b^j}$ | ${i \neq j}$}

The solution they provided is below:

The issue is, when I use JFLAP to test out, I get aabb to pass - when it should just be aabbb, aaabb, etc.

I looked around, and found another solution that also failed:

Can someone explain to me why these fail on JFLAP and if they are right or wrong? The PDA I'm looking for can accept even if there are objects on the stack. Perhaps these two rely on the fact that acceptance is only reached if there is nothing on the stack?

The intuition is push the number of $a$'s then pop while reading $b$'s. The result should be non-zero: either there are still items on the stack (which we can check), or the stack has been emptied before the end of the string.

There is a problem with instructions like "$b/\varepsilon/\varepsilon$". This instruction means "read $b$ and do not push nor pop". The middle $\varepsilon$ is misleading. It does not mean that the stack is empty. It just means the PDA does not look at it.

The solution is to start by pushing a nice bottom-of-stack symbol $Z$ at the start of the computation. When we  see a $Z$ we know the bottom has been reached.


Context-sensitive grammar for the language of words concatenated with themselves I'm looking for a context-sensitive grammar that describes the following language:
$L = \{ ww \mid w ∈ \{a,b\}^{\ast}, |w| ≥ 1\}$ .

I've got problems with the fact that no rules such as $X \to \varepsilon$ are allowed and therefore I can't place any nonterminal indicating the "middle" of the word. Is there any trick to the problem?

Indeed, there is a simple trick that allows you to add extra information at a certain position: just replace a letter adjacent to the position and mark it with the information, and the original letter.

In your example, have a nonterminal $M$ for the middle, but as it can not be deleted, it also counts as a normal letter. Thus we have two copies $M_a$ and $M_b$ to indicate the letters replaced.
In the end of the derivation the markers should be replaced by their letter content, by simple productions like $M_a\to a$.

In most cases the application of $M_a\to a$ needs to be performed at the end of the derivation process. In some constructions this does not need to be "timed": when the $M$ disappears too soon, the derivation cannot find a proper position and the process will not stop successfully. In other cases one does need a kind of control. This is sometimes done by introducing a nonterminal as a signal that moves along the letters. Again, this signal should also carry a terminal otherwise you end up in the same problems.

Moving information around is easy in so-called monotonic grammars ($\alpha\to \beta$ with $|\alpha|\le\beta|$) using rules like $XA \to AX$, which can be seen as $X$ jumping over $A$. For proper context-sensitive grammars one needs to split this in three steps: $XA \to XA^X, XA^X\to AA^X, AA^X\to AX$. in each production one letter is changed in a proper context. It takes quite some imagination to see this process does not interact with other parts of the derivation. E.g., what happens when the $A$ in the last step is first involved in another derivation step?

This might not work for very short words, when there is more information than positions available. The most simple solution to that is to ignore short strings in your construction, and generate them separately.


Enumerating weighted permutations in sorted order problem Let $S$ be a set of $n$ integers. Consider the following weighted permutations problem.

  Let $m<n$ be an integer. What is an efficient algorithm to enumerate all subsets of $m$ integers of $S$ such that they are listed in order of the sum of the integers in each subset?

Each subset is a permutation, and each permutation has a total weight that is the sum of the integers in the permutation.

The idea is to come up with an algorithm that is not the trivial algorithm of enumerating all subsets, and then sorting them, i.e. more of a "streaming" type algorithm. That is, efficiency in terms not so much of time but of "small" space.

Maybe this is published somewhere in the literature although I have not seen it.

Seems like a straightforward recursive algorithm, combined with streams (also known as lazy lists or generators), should work.  i.e.,

def subsets(m, S):
  if m==0:
      return [{}]
  if S is empty:
      return []
  s = min(S)
  S' = S \ {s}
  T = subsets(m, S')
  U = [u.union(s) for u in subsets(m-1, S')]
  return merge(T, U)

With the obvious definitions and Python-ish notation.  This returns a list in the desired order, i.e., a list of subsets, sorted by the sum of the elements in each subset.  Here I haven't provided the merge routine, but it can be implemented using the standard algorithm for merging sorted lists.

For clarity of exposition, I've written the above using lists and list comprehensions.  However, for an actual implementation, you should use streams (e.g., Python generators and generator comprehensions) rather than lists.  If you do that, there's no need to build all of the lists and represent them in memory; the algorithm shown above can proceed in a streaming fashion.

This is the kind of problem where a language with explicit support for lazy evaluation will shine.  With lazy evaluation, I believe you can implement a beautiful, elegant solution that looks clean but has excellent memory complexity.


How to apply "verification" and "decision" for the SUBSET SUM problem? The SUBSET SUM problem states that:

Given finite set S of integers, is there a subset whose sum is exactly t?

Can someone show me why verification is simpler than decision for this problem?

If anybody could show you that verification is simpler than decision, then she would be famous, having solved the P vs. NP problem.

For SUBSET-SUM, verification means that given a set $S$ which has a subset summing to $t$, someone can convince you easily that this is the case. The way she would do it is by giving you a subset of $S$ summing to $t$.

In contrast, decision means given a set $S$ and a target $t$, decide whether there is a subset of $S$ that sums to $t$. Nobody knows how to do it efficiently, and we conjecture that there is in fact no way to do it efficiently.

A related problem is co-verification: given a set $S$ which has no subset summing to $t$, we want someone to convince us easily that this is the case. Nobody has any idea how such a convincing argument would look like, and we conjecture that there such convincing arguments don't in fact exist (in general). This is the NP vs. coNP problem.


Minimum spanning tree of multi directed graph I have problem of inferring a rooted tree out of a connected simple graph.
The inference can be done by finding its minimum spanning tree, but the result is restricted by additional two types of condition:

There is a known root, which is s in the following example.
We know directions of some edges if they are chosen. These edges are not chosen yet, or the problem becomes a Steiner tree problem.

Note that numbers on edges are their weights. So we will get s -> b -> c -> a if a normal min spanning tree is applied, but the direction of edge ac is wrong. On the other hand, we cannot use Chu–Liu/Edmonds' algorithm for spanning arborescence of directed graphs, because we don't know and cannot infer the direction of edge bc.

We can infer some edges' directions according to the position of the root. For example, in the example, we know s -> b and s -> a.
It seems that the problem can be solved by two steps:

turn the simple graph into a multi-graph. For edges (in the original simple graph) whose directions are unknown, we represent them in a multi-graph using two directed edges between two vertices with inverse directions.
We find the minimum oriented spanning tree of this multi-graph.

Oriented Spanning Tree
In the final section of spanning tree, Wikipedia, oriented spanning tree is mentioned and a paper [levine2011sandpile] is referred. The problem fits the setting. It says:

Given a vertex v on a directed multigraph G, an oriented spanning tree T rooted at v is an acyclic subgraph of G in which every vertex other than v has outdegree 1.

Note that the term "outdegree" is a bit confusing, which I think should be "indegree". But it doesn't matter, because it just restricts the simple subgraph to be a directed tree with root being source or sink.
But it is not clear to me how an algorithm can be implemented according to that paper.

Levine, L. (2011). Sandpile groups and spanning trees of directed line graphs. Journal of Combinatorial Theory, Series A, 118(2), 350-364.
https://en.wikipedia.org/wiki/Spanning_tree

As indicated by the comments, this is a minimum spanning tree problem, which can be solved efficiently by Edmonds' algorithm (or Chu–Liu/Edmonds' algorithm).


Single tape Turing Machine that accepts string with at least five G's and at most three T's? I am looking to create a single tape acceptor Turing machine acting upon the language of any ASCII string, that would only accept strings that contains at least five G's and at most three T's, and rejects any other ASCII string input. I am kind of stuck on how the machine would know that it had encountered greater than or equal to five G's and less than or equal to three T's.

In general, whenever you try to design a machine accepting a language with this kind of "finite conditions", the easiest solution is to hard-code those conditions directly into the states of your machine.
Here, you would have 24 "counting" states, labelled by $(g, t)$ for $0 \leq g \leq 5$ and $0 \leq t \leq 3$. Whenever you read some $G$ while already in state $(g, t)$, you move on to the corresponding state $(g+1, t)$ (and if you read a $T$, you go to $(g, t+1)$). Otherwise, you simply loop on your current state.
Now, you have to enforce your conditions: if you read a $T$ while in a state $(g, 3)$, you reject the word, and if your word end while you are in a state $(g, t)$ with $g < 5$, you reject too.
Of course, there is probably some technical details to work out precisely, and there might exist some clever and trickier ideas to do this, but this method is easy to understand and can be immediately generalised to all the problems of this kind.


"Minimal" intuitionistic type theory? I'm surprised that people keep adding new types in type theories but no one seems to mention a minimal theory (or I can't find it). I thought mathaticians love minimal stuff, don't they?

If I understand correctly, in a type theory with a impredicative Prop, λ-abstraction and Π-types suffice. By saying suffice I mean it could be used as intuitionistic logic. Other types can be defined as following:

$$
\bot \stackrel{def}{=} \Pi \alpha: Prop. \alpha \\
\neg A \stackrel{def}{=} A \to \bot \\
A \land B \stackrel{def}{=} \Pi C: Prop. (A \to B \to C) \to C \\
A \lor B \stackrel{def}{=} \Pi C: Prop. (A \to C) \to (B \to C) \to C \\
\exists_{x: S}(P(x)) \stackrel{def}{=} \Pi \alpha: Prop. (\Pi x: S. P x \to  \alpha) \to \alpha \\
$$

My first question is, do they (λ, Π) really suffice?
My second question is, what do we need minimally if we don't have an impredicative Prop, such as in MLTT? In MLTT, Church/Scott/whatever encoding doesn't work.

Edit: related

To elaborate on gallais' clarifications, a type theory with impredicative Prop, and dependent types, can be seen as some subsystem of the calculus of constructions, typically close to Church's type theory. The relationship between Church's type theory and the CoC is not that simple, but has been explored, notably by Geuvers excellent article.

For most purposes, though, the systems can be seen as equivalent. Then indeed, you can get by with very little, in particular if you're not interested in classical logic, then the only thing you really need is an axiom of infinity: it's not provable in CoC that any types have more than 1 element! But with just an axiom expressing that some type is infinite, say a natural numbers type with the induction principle and the axiom $0\neq 1$, you can get pretty far: most of undergraduate mathematics can be formalized in this system (sort of, it's tough to do some things without the excluded middle).

Without impredicative Prop, you need a bit more work. As noted in the comments, an extensional system (a system with functional extensionality in the equality relation) can get by with just $\Sigma$ and $\Pi$-types, $\mathrm{Bool}$, the empty and unit types $\bot$ and $\top$, and W-types. In the intensional setting that's not possible: you need many more inductives. Note that to build useful W-types, you need to be able to build types by elimination over $\mathrm{Bool}$ like so:

$$ \mathrm{if}\ b\ \mathrm{then}\ \top\ \mathrm{else}\ \bot  $$

To do meta-mathematics you'll probably need at least one universe (say, to build a model of Heyting Arithmetic).

All this seems like a lot, and it's tempting to look for a simpler system which doesn't have the crazy impredicativity of CoC, but is still relatively easy to write down in a few rules. One recent attempt to do so is the $\Pi\Sigma$ system described by Altenkirch et al. It's not entirely satisfying, since the positivity checking required for consistency isn't a part of the system "as is". The meta-theory still needs to be fleshed out as well.

A useful overview is the article Is ZF a hack? by Freek Wiedijk, which actually compares the hard numbers on all these systems (number of rules and axioms).


How to adapt DPLL to solve HORNSAT? This question wask asked in a homework of Computer Theory in Rome, Italy.

  How to simplify the DPLL algorithm in order to solve HORNSAT?

My Approach:

I know that an  Horn clause is an OR of literals where it contains at most one pure literal and any number of negative literals.

I would start with the following algorithm:

FUNCTION $Dpll(S)$:

IF $S = \emptyset $ RET SAT
WHILE $\exists$ one unit clause $(p)$ or $\exists$ one literal $p$ that appears pure in $S$
IF ( $p \in S \wedge \neg p \in S) $ RET UNSAT
ELSE $S = Unit-propagate(S,p)$
ENDIF ENDWHILE
IF $S = \emptyset $ RET SAT
choose one literal $p$ in one clause in $S$
IF $(DPLL(Unit-propagate(S,p) == SAT)$ RET SAT
ELSE RET $DPLL(Unit-propagate(S,\neg p)$

FUNCTION $Unit-propagate(S,p)$

Delete every clause in $s$ that contains $p$
Delete every occurence of $\neg p$
RET $S$

Horn formulas are always satisfiable unless there is at least one unit clause that contains a positive literal.  (Otherwise assigning false to all the variables guarantees the formula would be satisfied.)  The procedure in that case is to unit propagate all unit clauses that contain a positive literal and unit propagate any such new clauses as they occur.  Once this task is completed, if the remaining formula contains no empty clauses then the Horn formula is satisfiable.


Finding a Simple Distribution In a Binary String Unsupervised feature discovery of text that started with its bit string representation would need to discover octets were the first-order parse of such a bit string.  This raises a question:

What is the technique called that can discover that a binary string, for example:

0100100111110010101010101011111011001000111000100101110001111110111010111110010111001010100011111110001101100101001010101111000111101011010011111001111101001111101011111011110011011001111000010100110001

has the simple model (with A x B meaning A occurs B times in the bag):

{00 x 1, 01 x 2, 10 x 3, 11 x 4}

even though it knows only that it should group bits in substrings (tokens) of the same bit length (ie: it doesn't know it should group bits in pairs)?

That is to say, if the binary string input was generated by a perl program:

for(0..100){print ( (('00') x 1, ('01') x 2, ('10') x 3, ('11') x 4)[rand(10)])}

the technique would reject, as less predictive, the distribution (model):

{0 x 7, 1 x 13}

and it would also reject a model that used 2 bit tokens on odd-numbered bit boundaries, as well as models that used 3 bit, or longer, tokens.

A related, more difficult technique, would find the model for a string generated by sampling the bag:

{0 x 1, 1 x 1, 00 x 1, 01 x 2, 10 x 3, 11 x 4}}

That is to say the bit string is a mix of token sizes.

TL;DR: use maximum likelihood and discrete optimization.

Evaluating candidate models: the maximum likelihood principle

If you have a candidate model, you can evaluate how well it fits the data using the maximum likelihood principle.

If $M$ is a model and $x$ is a string, let $P(x|M)$ denote the probability of outputting string $x$ when $M$ is the true model.  Here I assume a generative model that produces $x$ as follows: at each step, it randomly picks one term $g_i \times n_i$ from $M$, appends $n_i$ copies of the string $g_i$ to the output, and repeats until some stopping point (say, stops once we've generated a string of fixed length).

Of course in practice we have the reverse problem: we have observed a fixed string $x$, and want to infer $M$.  Now we'll treat the observation $x$ as fixed.  We define the likelihood of $M$ to be $L(M) = P(x|M)$.  If we have observed multiple strings $x_1,\dots,x_m$, then we define the likelihood of $M$ to be $L(M) = P(x_1|M) \times \cdots \times P(x_m|M)$.

The intuition is: models with larger likelihood fit the data better.  So, if you have a choice of multiple models, choose the one with the largest likelihood -- that's the one that seems most consistent with the data.

In practice, for computational reasons, we often deal with the log-likelihood, $\log L(M)$.  We choose the model whose log-likelihood is largest.  Since the log is monotone, this doesn't change anything fundamental.

if you're comparing a simple model to a complex model, this introduces the risk of overfitting.  The likelihood alone doesn't account for Occam's razor: the principle that, all else being equal, simpler models are more likely to represent the truth.  This can be fixed by introducing some kind of regularization.

Finally, note that the likelihood of a model can be computed efficiently using dynamic programming.  We each prefix $w$ of $x$, we compute $L(w)$ in terms of shorter prefixes, starting from shorter prefixes to longer prefixes, until we have computed $L(x)$.  If you don't immediately see how to do this computation, ask a separate question; it's a standard dynamic programming exercise.  If you're dealing with long strings, you might want to compute using log-likelihoods rather than likelihoods, to avoid underflow.

Fixed-length tokens

If all tokens have the same length, it's probably fairly easy to find a good model.  Assume know the length $\ell$ of all tokens in the model; if we don't, we can try each possibility for $\ell$, one at a time, and take the one that yields the best model.

Since we know the length $\ell$, we can divide the string $x$ up into tokens of length $\ell$.  In this way we can see the set of all tokens that appear in $x$, say $t_1,\dots,t_k$.  Now we know that the model must be of the form

$$M = \{t_1 \times n_1, \dots, t_k \times n_k\}$$

and we merely need to infer the numbers $n_1,\dots,n_k$.

Let's focus on the token $t_1$ and see how to infer $n_1$.  We can find all occurrences of $t_1$ in $x$, and combine them into sequences of contiguous repeats, and let $S_1$ denote the set of repeat lengths.  For instance, if at one place we see $t_1$ repeated 3 times consecutively, and at another place we see $t_1$ repeated 9 times consecutively, then we have $S_1 = \{3,9\}$.  At this point we simply take $n_1 = \gcd S_1$, i.e., $n_1$ is the largest number that divides every element of $S_1$.

We'll of course repeat this for each token $t_i$.  We end up with a complete model, as desired.

A technical detail: This assumes that each token $t_i$ is listed only once in $M$, with a single repeat-factor $n_i$.  In other words, it assumes the model is allowed to look like $\{00 \times 4\}$ but not $\{00 \times 2, 00 \times 3\}$ (the latter has the token $00$ with two different repeat-factors).  If you want to consider the latter kind of model, the problem reduces to finding a set of repeat-factors $R_1$ such that every element of $S_1$ can be expressed as a linear combination of $R_1$.  The optimal solution will depend on the form of regularization you use; without regularization, the optimal solution will always be to simply take $R_1$ to have a single element, $R_= \{\gcd S_1\}$. So if you want to consider models where the same token appears twice, you'll need to specify a particular form of regularization (ask a new question).  For now, I'll assume such models aren't of interest.

So this shows how to solve the problem, in the easy case where all tokens have the same length.

Variable-length tokens

Handling models where the lengths of the tokens are not all the same looks much more challenging.  I can suggest one possible approach, but the best approach will probably depend on the parameter settings you're encountering in practice.

I suggest reducing this to a discrete  optimization problem.  In particular, I suggest you identify a set of tokens $t_1,\dots,t_k$ that you're confident will be a superset of the ones in the real model, and then use optimization methods to solve for the repeat-factors $n_1,\dots,n_k$ that maximize the likelihood of the model.

In more detail: Fix the set of $t_1,\dots,t_k$.  Now the model looks like

$$M = \{t_1 \times n_1, \dots, t_k \times n_k\}$$

where the $t_i$'s are known and the $n_i$'s are unknown (variables).  Consequently we can think of the likelihood $L(M)$ as a function of the $n_i$'s: given any candidate values for $n_1,\dots,n_k$, we can compute $L(M)$ using dynamic programming.

So, I'd suggest you use some existing optimization strategy to find $n_1,\dots,n_k \in \mathbb{N}$ that maximize $L(M)$.  A natural approach is probably some form of local search, e.g., hillclimbing, hillclimbing with random restarts, or simulated annealing.  A suggestion for a set of "local moves" would be to pick a single $n_i$ and change it via one of the following operations: multiply $n_i$ by a small prime number; divide $n_i$ by a small prime divisor of it; set $n_i$ to zero; change $n_i$ from zero to a small number; increment $n_i$; decrement $n_i$.

How do we find the set $t_1,\dots,t_k$ of tokens?  Here a convenient fact is that we don't have to get this set exactly right; it suffices for it to be a superset of the true set of tokens in the actual model.  In particular, setting $n_i=0$ is equivalent to removing the token $t_i$ from the model entirely.  So, we can choose a larger-than-necessary set of tokens $t_1,\dots,t_k$ and let the optimization routine effectively solve for which tokens should be retained and which should be eliminated.  One heuristic would be to choose $t_1,\dots,t_k$ to be the set of all bit-strings of a certain range of lengths (e.g., all bit-strings of length 2 or 3).  Another heuristic would be to use some kind of filtering condition: use the set of all bit-strings $t$ that appear at least some minimum number of times in $x$.  The nice thing is that we can try each of these choices in turn, apply the optimizer to each, get a list of candidate models, and choose the best one (using the maximum-likelihood principle).  For instance, it might not be clear how to choose a threshold for the filtering, but we can try multiple values in a exponentially decreasing sequence and keep the best model obtained.

Similarly, it's also possible to come up with heuristics for the initial values of $n_1,\dots,n_k$ to feed to the optimizer (this will help some optimizers converge to a better solution).  For instance, for each token $t_i$ and each candidate repeat-factor $r$, you could count the number of times that $t_i$ appears repeated $r$ times in a row, then choose the value of $r$ that has the highest count as the initial guess for $n_i$.

How well will this work?  I don't know.  It will probably depend a lot on the parameters of the problem instances you run into in practice.  I would suggest you try it on your data sets, with several different optimization methods and fiddling with the parameters a bit.  If it doesn't work, ask another question where you show us what you've tried, and also show us the typical range of values for the most important parameters: the number of tokens in the model ($k$), the range of lengths of the tokens themselves, the range of values of the repeat-factors $n_i$, the length of the string $x$.


Expectation Maximization Algorithm for simple naive Bayesian network I am trying to understand the following network
A has two children - B & C (aka common cause)

All the variables are binary and can be either 0 or 1.
In data values are missing only for some records. Only values that are missing are values A.

How does the Expectation step looks like in this example? Is it P(A|B,C) and then calculating the counts for P(A = 0| B = 0, C=0) ? I am confused with this.

How does the Maximization step looks like in this example?

I finally found the solution
Expectation step is as follows
Calculate new probabilities of data points as follows
P(A|B,C)
which we break down to

  (P(A,B,C)/P(B,C) =

  (P(B|C,A) * P(C|A)*P(A)) / (sum of all P(B,C) for all A) =

since A is known then B & C is independent
therefore

  (P(B|C,A) * P(C|A)*P(A)) / (sum of all P(B,C) for all A) =

which we need to consider 3 binary variables, gives us 8 cases (2^3)
lets say for A = 1, B = 0, C= 1

  (P(B=0|A=1) * P(C=1|A=1)*P(A=1)) /
  ( (P(B=0|A=1) * P(C=1|A=1)*P(A=1)) + ( (P(B=0|A=0) * P(C=1|A=0)*P(A=0)) )

  =  P(A=1| B=0, C=1) = lets call it value val101

we use this value (val101) to update probability of each unknown data point that has B= 0 and C = 1 and A = 1.
Then update probability of each unknown data point where A=0, B=0 and C=1 with the (1-val101)

we do that for possible combinations of A, B and C
000
001
010
011
100
101
110
111

(I think this is already an M step - Maximization, but here it goes)

To calculate parameter theta for P(A=0) we do the following
count (sum of all probabilities) of each data point where A = 0 and we divide it by the original amount of data points
we do the same for the A =1

then we update conditional parameters
to update parameter theta of P(B=1|A=0)
we take a sum all the probabilities of all data points where A = 0 and B=1
and we divide it by the count (sum all the probabilities) of probabilities of data points where A =0
so its as follows

#(A=0,B=1) / #(A=0)  = theta P(B=1|A=0)

and we do that for all the conditional probabilities which are as follows

P(B=1|A=0)
P(B=0|A=0)
P(C=1|A=0)
P(C=0|A=0)
P(B=1|A=1)
P(B=0|A=1)
P(C=1|A=1)
P(C=0|A=1)

then you are done


Find largest subset of vertices in graph so that every pair of vertices have an edge between them Let's say you have a graph like this:

The largest subset of nodes so that every pair of vertices have an edge between them is $\{3, 5, 7, 12\}$. The second largest subsets are

$\{4, 7, 21\}$,
$\{3, 5, 7\}$,
$\{3, 5, 12\}$,

etc.

Is there an algorithm to find the largest subset efficiently?

Also, keep in mind that I know virtually nothing about graphs (haven't learned at school, haven't taught myself). The data was originally given as a set of pairs of numbers.

Unfortunately, the answer is no.

In graph theory, such a subset is called a clique. (Essentially, a graph is a set of nodes and a set of edges between those nodes, and a clique is a set of nodes in a graph such that every node in the set has an edge to every other node in the set.) What you want is to find the largest clique in a given graph.

This is called the Maximum Clique Problem, and it's NP-hard. The decision problem version, "is there a clique with size $k$?", is in fact NP-complete. So an efficient solution to the Maximum Clique Problem would prove that P=NP and earn you the $1,000,000 prize and eternal fame.


What is the size of the Perfect binary tree with n nodes in last level I want to know how to calculate total number of nodes in a perfect balanced binary tree with $n$ nodes in the last level. I know the answer is $2\cdot 2^{\log n} - 1$. Just curious how this can be calculated

A perfect (binary) tree of depth $k$ has exactly $2^{k+1}−1$ nodes.

There are probably several ways to prove it. A simple way is by induction.
Each level has twice as many nodes as the previous level (since each node has exactly 2 children in a binary tree). The base level - the root - has 1 nodes. Note that the root is depth 0, not 1.

Let's denote the number of nodes in level $i$ by $N_i$. We know,

$N_0 =1$
$N_i = 2N_{i-1} = 2^{i}$

The total amount of nodes (of tree of depth $k$) is $S_k \equiv N_1 + N_2 + \cdots + N_k$, that is,

$$ S_k = 1 + 2 + 4 + 8 + \ldots +2^{k}.$$
This is a geometric series, whose sum is $S_k = 2^{k+1}-1$.

Now for your question:
We are given a perfect (binary) tree with $n$ nodes at the last level, how many nodes does it have overall?
We are given that at the last level (call it level $k$) we have $N_k=2^k=n$ nodes. Then $k=\log_2 n$ and we get that $S_k=2^{k+1}-1=2n-1$; Yes, each level has one more node than the entire tree above it.

A related question:
we are given a perfect (binary) tree with $n$ nodes, what is its depth?
Now we are given that the total number of nodes is $S_k = 2^{k+1}-1 = n$, thus $k=\log_2 (n+1)-1$ (again, the root is considered depth 0 here).


Minimum set cover with incompatible sets I'm interested in a variant of minimum set cover where some sets are ``incompatible'' (they can't be chosen simultaneously).
To state it more formally:
We have a finite base set $X$ and a family $\mathcal{R}$ of subsets of $X$. We also have an undirected graph $G$ with vertex set $\mathcal{R}$ and edges representing incompatibilities between sets. The goal is to find a minimum set cover of $X$ which is also an independent set of $G$.
Does this problem have a name? Or is it a special case of a studied problem? Or can it be reduced to a well-studied problem with a small blowup in runtime? (by "small blowup" I mean not simply polynomial, but preferably a small degree polynomial).
I'm particularly interested in the geometric variant where $X$ is a set of points and the sets in $\mathcal{R}$ are defined as the intersection of $X$ with some simple geometric ranges (in which case tools such as VC-dimension, $\epsilon$-nets, range-searching and so on might come in handy for approximation algorithms). But I welcome any relevant reference.

Your problem can be stated as a minimum weight maximal independent set problem.
Construction:
Construct a bipartite graph $G = (L,R,E)$, where the right partition $R$ corresponds to $\mathcal{R}$ and the left partition $L$ corresponds to $X$. An edge $(u,v) \in E$ iff an element $u$ is contained in the set $v$.
Let $G'$ be the updated graph obtained by adding edges within $R$ based on the incompatibility of vertices in $R$.
Furthermore, assign a weight of $\infty$ on each vertex of $L$ and weight $1$ on each vertex of $R$. Also, attach a new pendant vertex of weight $0$ to each vertex in $R$. Let $G_{w}$ be this new graph.
Now, your problem can be stated as finding minimum weight maximal independent set problem (MMIS) on $G_{w}$. It is a standard problem discussed here. Your problem has a feasible solution if and only if MMIS has a finite value. Also, your problem has a solution of size $k$ if and only if MMIS has a value $k$.
Correctness:
Suppose, a feasible instance of the independent set cover problem is $S_{1}, \dotsc, S_{k}$. Then, the maximal independent set contains vertices in $R$ corresponding to $S_{1}, \dotsc, S_{k}$ and pendant vertices corresponding to the remaining sets. It is easy to see that it is an independent set and it is also maximal. Moreover, the weight of the independent set is exactly $k$.
Similarly, you can prove the other direction, i.e., if there is a maximal independent set of value $k$, there is an independent set cover of size $k$.

Note: Instead of assigning $\infty$ value to the vertices in $L$, you can also assign some sufficiently large finite value, say $|\mathcal{R}|+1$. That will also work.


how to solve NFA acceptance problem in polynomial time I need to show that the language Anfa = {(A,w)| A is an nondeterministic finite automata that accepts w} can be decided in polynomial time. My problem is every solution that I think of requires exponential time.

I would appreciate any help, Thanks in advance..

Hint (expanding on David Richerby's hint): As the NFA reads $w$, keep track of the set of states it could be in at any given time.


What type of an algorithm is being used for directory structure scanning? So after learning about DFS and BFS yesterday in my class I was curious as to how is scanning on various file system being done. I spent quite a bit of time trying to look for some references on the web, but so far I have failed in doing so. I'm assuming that either DFS or BFS are behind the core "scanning" in some file systems.

There's also Dijkstra's algorithm but as I'm not even sure if file system is a weighted or unweighted tree (ie. number of files being the weight or file size) it's hard to say if it's useful or not because I believe that BFS would be better than Dijkstra if it's unweighted tree.

I hope that someone could clear this up as there just isn't anything specific about it on the web.

For most file systems, a directory lists its entries in a certain order, so reading ("scanning") an individual directory will return its entries in that order.

But when it comes to scanning whole directory structures, there is no such thing as "core scanning": there isn't a common implementation for that.

I think depth-first is more popular; e.g. GNU find only supports depth-first scanning.  This may be due to depth-first scanning consuming less memory on average; it can't be due to breath-first search being harder to implement, as it's just a matter of treating your list of files to visit as a queue rather than a stack.


Assembly language translation to machine code (process in "RAM") How does a assembler (at very basic level) work in translation of Assembly language to machine code ? Just want to know that what is happening in RAM ?

[What my understanding is that when  when I type MOV A, B   : in RAM :'M' >> some bytes (ASCII CODE) in memory (RAM)in form of 0v and 5v (voltage may be different but you know what I mean) 'O' will be saved with same method & so V , A , "," , B .Now the programming software also have the part in RAM which we call "library" saved in 0s & 1s in the form of 0v /5v.So my question is that does "translation" mean that typed the 0s,1s of MOV A,B will be compared to saved 0s and 1s (library's)by logic ckt & then depending on the matching or mismatching of those 0s,1s will result in another 0s,1s (opcodes bits/bytes ,will be stored & later executed in RAM)?Am I right or is this a wrong way of thinking? ]

In modern computers, assemblers do not deal directly with in-RAM machine code anymore. Their job is to translate the textual representation of the assembly language to opcode combinations, in a form that is not completely finished because exact addresses are not decided yet.

Both the tetx and its translation are stored in disk files, they only reside in RAM while translation takes place.

A next step is performed by another utility, the linker, which performs address assignments and creates another file, called the executable, and will also reside on disk.

When you want execution to take place, a third program called the loader will read the opcodes from disk and write them in RAM memory where it belongs. Then the loader will tell the operating system that a new task is ready for execution and eventually control will be passed to the program you have written and which is now loaded in RAM.

(This explanation is really simplified as there are many intervening steps and other goodies to consider.)


Can multiple tasks in an RTOS share one stack to save memory? Many small embedded systems have a limited amount of RAM, 10k or less. I know you can run an RTOS on such systems, however, a realistic number of tasks in such a system is very low, mainly because every task needs its own stack area.
Is it possible to share the space needed for the stack of some of these tasks?
I understand that this is possible in a cooperative environment, such that a task can report its willingness to relinquish the processor (and refrain from using its stack). But in an RTOS you don't normally use cooperative multitasking.
But then, maybe it is sufficient to use non-preemptive tasks when sharing stack space, in a certain way that's also "cooperative" in my opinion.

Can it be done in an RTOS? How?

As long as they do not overlap in execution, the tasks can re-use the same stack space.  That is, they can not safely execute in parallel or else one task will corrupt another's stack space.

This corruption may occur due to local variables or parameters stored on the stack, or even due to the occurrence of an ISR.

Hope this helps