How to prove that minimal DFA is unique? My idea is that the number of states in the minimum DFA is equal to the number of equivalent states. So, if there exists another minimum DFA, then it must have different equivalent states than the previous DFA which is not possible.

How do I formally prove this?

EDIT: Maybe something like "since two states are equivalent, they are semantically equivalent and hence, they can't be equivalent and different at the same time" might do if written formally?

Suppose that we are given a regular language $L$ and a DFA ${\cal A} = (Q,q_0,F,\delta)$. Denote the equivalence classes of the Myhill–Nerode relation of $L$ by $S_1,\ldots,S_m$. For each state $q \in Q$, define $L_q = \{w \in \Sigma^* : \delta(q_0,w) = q\}$. From the definition of the Myhill–Nerode relation it follows that each $L_q$ is a subset of some $S_i$.

The Myhill–Nerode theorem shows that there is a DFA with $m$ states, so suppose that ${\cal A}$ has $m$ states. From our comment above it follows that each $L_q$ equals some $S_i$. Rename the states so that $S_i = L_i$ (so now $Q = \{1,\ldots,m\}$). We now read off all the other data of ${\cal A}$:

The starting state $q_0$ is the one whose language contains the empty word $\epsilon$, that is, it is determined by the condition $\epsilon \in S_{q_0}$.
A state $i$ is accepting if $S_i \subseteq L$, and rejecting if $S_i \subseteq \overline{L}$ (it follows from the definition of the Myhill–Nerode relation that these are the only two possibilities).
Let $w_i$ be an arbitrary word in $S_i$, and let $\sigma \in \Sigma$. Then $\delta(i,\sigma) = j$ if $w_i\sigma \in S_j$. Again, the definition of the Myhill–Nerode relation shows that the choice of $w_i$ doesn't matter.

After renaming the states of ${\cal A}$ in a canonical way, we read off ${\cal A}$ from the Myhill–Nerode relation of $L$. It follows that all minimial DFAs for $L$ are equivalent.


What is a "reduction", really? I am studying computational theory with Sipser's textbook. I can't quite understand the definition of "reduction". For example, "this problem can be reduced to ATM ..."

What exactly does "to reduce" mean? I can't draw the picture in my head. Can anyone can help me understand this definition?

This is kind of a broad question, and there are a lot of well-written references. This answer is just a basic starting point.

Intuitively, when we reduce a problem $A$ to a problem $B$, we mean that if we know how to solve $B$, this somehow induces a solution to $A$ (the "somehow" is the reduction). Taking the contra-positive, this also means that if we know that $A$ is unsolvable (according to some fitting notion of unsolvability), then $B$ is also unsolvable.

In undergrad computability course, we usually talk about mapping reductions. A mapping reduction from $A$ to $B$ is a computable function $f:\Sigma^*\to \Sigma^*$, such that for all $x\in \Sigma^*$ it holds that $x\in A$ iff $f(x)\in B$.

The intuition behind this definition is that, assuming we have an algorithm that solves $B$, then we can solve $A$. Indeed, given an input for $A$, we use the reduction $f$ to transform it to an input for $B$, and solve $B$ using our algorithm. The "iff" property of the reduction ensures that the answer we get on $B$ induces an answer for $A$.

As a concrete example, let's consider the halting problem: given a TM $M$ and input $w$, decide whether $M$ halts in its run on $w$.
We want to reduce $A_{TM}$ to the halting problem. That is, we want to show that if we could solve the halting problem, then $A_{TM}$ is also solvable. So what we need to show is a function that takes an input $M,w$ for $A_{TM}$, and transforms it into an input $M',w'$ for the halting problem, such that the $M$ accepts $w$ iff $M'$ halts on $w'$.

We do this as follows. Given input $M,w$, construct $M'$ to be the machine that behaves exactly like $M$, except that we replace the rejecting state of $M$ with a self-loop (that never halts). We then output $M',w$. Now, it is not hard to prove that $M$ accepts $w$ iff $M'$ halts on $w$, and thus we have a reduction. Also note that this reduction is computable, since computing $M'$ from $M$ is a simple matter of changing the behavior of a state.


Embedded arithmetic set expressions In set builder notation, we can represent the set: $$\{ 2, 7\}$$ as: $$\{ x | x=2 \vee x=7 \}$$.

Therefore, the PA arithmetic predicate: $$φ(x) :=  x=2 \vee x=7$$ is capable of representing this set. The boolean expression: $$x=2$$ can also be represented in arithmetic by the function:

$$1-sgn(x-2)²$$

So: $$x=2 \vee x=7$$ is equivalent to: $$(1-sgn(x-2)²) \vee (1-sgn(x-7)²)$$.

Since: $$x \vee y = x+y-xy$$

we can represent:

$$φ(x) := 1-sgn(x-2)² \vee 1-sgn(x-7)²$$

$$φ(x) := 1-sgn(x-2)² + 1-sgn(x-7)²-(1-sgn(x-2)²)(1-sgn(x-7)²)$$

which simplifies to:

$$φ(x) := 1 - sgn((x-7) (x-2))²$$

So, we can have an arithmetic predicate that does not need to use boolean operators and that can represents the set:

$$ \{ a_1, a_2, a_3, ... , a_n \}$$

arithmetically as:

$$φ(x) := 1 - sgn((x-a_1)(x-a_2)(x-a_3)...(x-a_n))²$$

Now I am stuck trying to use a similar technique to represent the embedded set expression:

$$\{1, 2, \{ 4, 9\}, 7\}$$

The inner embedded set { 4, 9 } in the expression above may look somewhat like:

$$φ_2(x) := 1 - sgn((x-4)(x-9))²$$

The outer set may look somewhat like:

$$φ_1(x) := 1 - sgn((x-1)(x-2)(x-φ_a(x))(x-7))²$$

But I cannot figure out how to express:

$$φ_a(x)$$ in terms of: $$φ_2(x)$$

Can this actually, uberhaupt, even be done?

Your problem is that your trick of representing set membership using arithmetic only applies to sets consisting of numbers only. Say you have a set of colours { red, green } then 1 - sgn (x - red)^2 doesn’t make any sense. Even worse is a set containing other sets as elements.


Why is the complexity of the following code $O(n^4)$? for i = 1 to n
    s = 0

    for j = 1 to i - 1
        s = s + j * (i - j + 1)

    r = s * s

I calculated the time complexity of this code to be of order $O(n^2)$, but my professor says it is actually $O(n^4)$ because of the statement $r = s * s$, as $s$ is dependent upon $j$ and $i$ which in turn are dependent on $n$. But don't we consider arithmetic operations to be $O(1)$?

Complexity calculation is a new concept to me, and it confuses me a lot. I would appreciate if someone posts a detailed answer which clears my confusion.

There are two things that could be measured here. First, the time complexity of the code, which is to say the number of steps it takes to execute. In that case we have two possible metrics: (1) count each arithmetic operation as taking 1 unit of time. That's the one you're likely used to. In (2) we count the time an arithmetic operation takes as a function of the number of bits needed to express the operands.

The second possibility is to measure the magnitude of the result, $r$, as a function of $n$. It appears that your professor is looking for the second measure: express $r$ in terms of $n$. That, though, is a bit problematic, since $s$ is reset to zero at each iteration of the outer loop, so the final value of $r$ is just the result when $i=n$ which will be $O(n^6)$.

The upshot is that your calculation of the running time, $O(n^2)$ is the only one that makes any sense here. Ask your professor for clarification.


How can the length of a string be $O(\log n)$? I have just started learning about time complexities and am currently reading Logarithmic Complexity. Here's an example of a piece of code which is $O(\log n)$:

def intToStr(i):
    '''Assumes i is a nonnegative int Returns the string representation of i'''

    digits = '0123456789'
    if i == 0:
        return '0'
    result = ''
    while i > 0:
        result = digits[i % 10] + result
        i = i // 10
    return result

So this just gives is the str of an integer. intToStr(1243) returns '1243'. I completely understand that the above function is of logarithmic complexity.

In continuation,

def addDigits(n):

    '''Assumes n is a nonnegative int
    Returns the sum of the digits in n'''
    stringRep = intToStr(n)
    val = 0
    for c in stringRep:
        val += int(c)
    return val

My book says that: (emphasis added)

  The complexity of converting $n$ to a string is $O(\log n)$, and intToStr returns a string of length $O(\log n)$. The for loop will be executed $O(\operatorname{len}(\mathit{stringRep}))$ times, i.e., $O(\log n)$ times. Putting it all together, and assuming that a character representing a digit can be converted to an integer in constant time, the program will run in time proportional to $O(\log n) + O(\log n)$, which makes it $O(\log n)$.

Can someone please explain how intToStr returns a string of length $O(\log n)$? Doesn't it just return a string of length $n$, where $n$ is the length of the integer that we pass?

The length of the binary representation of a natural number $n$ is roughly $\log_2 n$. As an example, the number represented by the binary string $10^{n-1}$ of length $n$ is $2^n$.

Your sources are misleading. Usually $n$ is reserved for the input length or a related quantity, not the input value. If the input to a function is an integer $m$, then the input length is only $\sim \log_2 |m|$. In particular, intToStr actually runs in linear time in the input length, rather than logarithmic time.


recursive lambda expressions From http://www.seas.gwu.edu/~rhyspj/spring09cs145/lab8/lab82.html

The lambda operator does not bind every occurrence of its variable because "shadowing" can occur. A variable is bound by its nearest enclosing lambda.
In $(\lambda (x) ((y\,\, x) (\lambda (x) (x\,\, y))))$, the $x$ in $(y\,\, x)$ is bound by the outermost lambda, whereas the $x$ in $(x\,\, y)$ is bound by the inner lambda. In this example, both occurrences of $y$ are free.

How shall I understand the lambda expression $(\lambda (x) ((y\,\, x) (\lambda (x) (x\,\, y))))$?

I wonder if the $x$ in $(y\,\, x)$ and the $x$ in $(x\,\, y)$ are the same
or different variables?
If I rename one of them,  will the renamed version be the same as
$(\lambda (x) ((y\,\, x) (\lambda (x) (x\,\, y))))$? E.g.

Is $(\lambda (x) ((y\,\, x) (\lambda (z) (z\,\, y))))$ the same as $(\lambda (x) ((y\,\, x) (\lambda (x) (x\,\, y))))$?
Is $(\lambda (z) ((y\,\, z) (\lambda (x) (x\,\, y))))$ the same as $(\lambda (x) ((y\,\, x) (\lambda (x) (x\,\, y))))$?

Do the two occurrences of $y$ mean the same variable?

Informally speaking the two x's are indeed different variables (technically speaking, they are the same variables but bound by different abstractors).

As for your two inquiries regarding equivalences: in the strictest sense possible, they are not syntactically equivalent ($M \not\equiv N$). However, they are what is called equivalent modulo alpha ($M \equiv_\alpha N$). This basically means that one can be transformed into the other through $\alpha$-conversion (which leaves the behaviour of the term unchanged). The result is that the names of bound variables become arbitrary - as they should be.

Note that most equivalences in lambda calculus are stated modulo $\alpha$, and most lambda logicians seem to regard the formulation and application of the rule as a tedious formality. Once they have specified the $\alpha$-rule (if they even care to do so in the first place), they tend to adopt the following convention: 'from now on, when we say $M$ and $N$ are equivalent ($M \equiv N$), we just mean that they are equivalent modulo alpha ($M \equiv_\alpha N$), unless stated otherwise'. So in most contexts, you can simply say they are 'the same', but I think you should be aware of the details behind it.
Yes. If $y$ were to be substituted for some $z$ in that term, then all occurrences of $y$ will be replaced by $z$.

This is perhaps a useful free resource that covers some of the basics a little more rigorously: http://www.cse.chalmers.se/research/group/logic/TypesSS05/Extra/geuvers.pdf.


Is Turing Reduction always in context to decidable languages? According to Wikipedia's article on Turing Reduction

  It can be understood as an algorithm that could be used to solve A if it had available to it a subroutine for solving B.

Does solving mean always halting (accept/reject)? Should B assumed to be decidable language for the sake of proofs ?

Absolutely not. In fact, these are most useful when $B$ is undecidable.

Diagonalization was used to show the Halting problem undecidable, but most other problems were shown to be undecidable through a reduction:

Suppose we have a subroutine solving $B$
Show that we can use that subroutine to solve $A$.
If $A$ is undecidable, then we have a contradiction, so we know $B$ must also be undecidable.

That said, the a proper Turing reduction should always halt. It's cheating if you say "I can use $B$ to make a program that either solves $A$ or runs forever". That's not useful in general.

(Although if you used $B$ to find a recognizer for $A$ where $A$ is not recursively-enumerable, you could show that $B$ is not decidable/recursively-enumerable, depending on your initial assumption about $B$.)

If $B$ is decidable, and you reduce $A$ to $B$, all you've done is create an algorithm deciding $A$. Which is useful, but you don't need a formal notion of reduction to do that.


Are there data structures that mix a tree structure with lists? I suppose something like this could probably be easily designed, however I was wondering if there's a data structure that somehow uses both list and tree to access data.

Something like this (I'll be informal, but I hope I can give you some idea of what I mean).

Suppose we have a tree with depth $n$. At depth 1 we would have the nodes $X_1,X_2,\ldots X_{n_1}$. For $i_1 \in \left\{1,\ldots n_1\right\}$ the node $X_{i_1}$ could have as children $X_{i_1,1},X_{i_1,2},\ldots X_{i_1,n_{i_1}}$, for $i_2 \in \left\{1,\ldots,n_{i_1} \right\}$ the node $X_{i_1,i_2}$ could have as children $X_{i_1,i_2,1},X_{i_1,i_2,2},\ldots, X_{i_1,i_2,n_{i_2}}$, and so on. However to get quick access to the nodes say at depth $k$ I could also implement a list of pointers to all the nodes $L_k := \left\{ X_{i_1,\ldots, i_k } \right\}$. So for depth 1 I could have the list

$$
L_1 := \left\{ X_1, \ldots, X_k \right\}
$$

At depth 2 instead

$$
L_2 := \left\{ X_{1,1},\ldots, X_{1,m_1},\ldots,X_{n_1, 1} , \ldots, X_{n_1, m_{n_1}} \right\}
$$

So in general the list $L_k$ would contain all the nodes with $k$ indices. I'm pretty sure something like this already exists, however I can remember if there's a specific name or not.

Yes.  Build a tree (with any branching factor you want).

Then, augment the data structure by maintaining one doubly linked list per level that contains all of the nodes at that level.  In particular, in each node you have a "left" and "right" field which goes to the next and previous elements in that doubly linked list (i.e., the next sibling to the right of it and the previous sibling to the left of it).

All of the standard tree operations can be augmented to update/maintain these doubly linked lists as well.  This adds only $O(1)$ extra time to each operation to update the doubly linked lists, so the asymptotic running time for each tree operation remains the same.

This construction can be applied to any tree with any structure you want (binary tree, $k$-ary tree, b-tree, AVL tree, red-black tree, etc.)

I don't know of any particular name for this specific case.  It is an instance of augmenting a data structure.  Many data structures/algorithms textbooks will have a chapter on augmenting data structures.


Why do min/max operations in van Emde Boas trees run in $\mathcal{O}(1)$? I have read in the book

  "Introduction to Algorithms", 3ed by Cormen, Leiserson, Rivest, and
  Stein (Chapter 20)

that Emde Boas trees run min/max operations in $\mathcal{O}(1)$ time since the minimum and maximum element are stored as attributes in each tree. I don't understand this very well. Does this mean that the min and max values are already given in the input, because the minimum and maximum must be calculated somewhere?

No. They are not given as an input! They were stored and updated as an attribute of each tree(Beware that the concept of the "attribute" in real-world programming means a "variable" in a programming language. More details depend on the programming language that you have chosen up to now to develop the data structure). The same situation is taking place in the min[Max]-heap data structure. You can find the minimum [maximum] in a min[max]-heap with $O(1)$ operation by keeping update (in insertion time) the mentioned attribute.


If lower bound of a problem is exponential then is it NP? Assuming that we have a problem $p$ and we showed that the lower bound for solving  $p$ is $\mathcal{\Omega}(2^n)$.

can lower bound $\mathcal{\Omega}(2^n)$ implies the problem in $NP$?

No. For example, the halting problem has an $\Omega(2^n)$ lower bound, but it is not in NP (since it is not computable).

The nondeterministic time hierarchy theorem shows that any NEXP-complete problem is another example (with $2^n$ potentially replaced by a smaller exponential function $c^{n^\epsilon}$).

NP is an upper bound on the complexity of a problem.


Why is constant always dropped from big O analysis? Suppose I have an algorithm that has a performance of $O(n + 2)$. Here if n gets really large the 2 becomes insignificant. In this case it's perfectly clear the real performance is $O(n)$.

However, say another algorithm has a performance of $O(n^2/2)$. Here if n gets really large then $n^2/2$ is exactly half of $n^2$, which is not significantly smaller than $n^2$. So why we drop 1/2 from $O(n^2/2)$ and it becomes $O(n^2)$?

When we evaluate complexity of algorithms, we count the number of computation
steps, or of memory locations.  But these costs are in arbitrary
units. For example we have no idea how long it takes on computer X to
actually execute one step of the algorithm.  If you double the
computer speed, you divide the time taken by 2, independently of the
complexity formula, of the big-O complexity.

Hence this complexity is meaningful only up to a constant.

Hence, the 1/2 factor you mention is irrelevant. It is just the same
as changing the computer, or changing the time unit. If you count in
hours rather than seconds, you can get a whooping improvement factor of 3600.
But you wait just as long to get the answer.

Here I did not mention that since it is supposed to be an asymptotic estimate,
we first remove all that is asymptotically negligible

Another useful aspect of this definition of big-O is that you can
ignore in the analysis the fact that some computations steps are more
expensive than others. As long as there is a bound to the cost ratio
between steps, they can simply be all considered costing the
same. This can impact the total time only by a constant factor.
It does make complexity analysis simpler.


Generating topological sequence from DAG with additional "not appearing before" constraints DAG specifies the relationship of one node must appear after another. What if I add an additional constraint where one node cannot appear before another on top of the DAG?
Is there an algorithm for generating topological sequence from DAG with such constraint? Or maybe I can transform the DAG with this constraint?

Let's say the 2 nodes in question are node x and node y. If you want node x to not appear before node y, then, as Yuval Filmus mentioned in the comments, you want it to appear after y.
What does this mean?
If x is a predecessor of y, then the graph would not be valid, because by definition, a topological sort puts all predecessors before their childrens.
If x is not a predecessor of y, you could add an auxiliary edge from x to y. This ensures that x will definitely appear before y, again by definition of a topological sort.
Followup:
Adding an auxiliary edge may cause some problems, here are some possible solutions to resolve them
Shortest/longest path in weighted DAG: Just set the edge weight as 0
Shortest/longest path(number of edges used): Give all non-auxiliary edges value of 0, treat as SP/LP in weighted DAG


How can I simplify the following Product of Sums: ab+ac'+a'b'+a'c+b'c'+bc? I started with POS: (a+b+c)(a+b'+c)(a'+b+c)(a'+b+c')

and after a long while, I got: ab+ac'+a'b'+a'c+b'c'+bc

and then I'm not sure how to simplify this. I thought maybe I can cancel the ab with a'b', and b'c' with bc and end with ac'+a'c but it doesn't seem to be right if I look at the truth table...

Update It turns out that your initial simplification was incorrect. Here's a correct one. First, observe that
$$
(p+q)(p+q') = pp+pq'+pq+qq'=p +p(q'+q)+0 = p+p1=p
$$
so for the first two terms in your POS we have
$$
((a+c)+b)((a+c)+b') = a+c
$$
and, similarly, for the last two terms we have
$$
((a'+b)+c)((a'+b)+c') = a'+b
$$
so the full product simplifies to
$$
(a+c)(a'+b)\quad\text{ or, if you prefer }\quad ab+a'c+bc
$$
At this stage you haven't simplified this as much as possible. If you construct truth tables, you'll discover that $ab+a'c+bc=ab+a'c$, in other words the $bc$ term isn't needed here. It isn't obvious how one would discover that unless you've seen Karnaugh maps, for instance.


Why is Clique NP-complete while k-Clique is in P for all k? I just stumbled upon this question here Why is the clique problem NP-complete?
 and I am confused by the given answer.
The question about about whether $k$-clique is NP-hard for a fixed $k$ and the answer is no. However, we know that clique in general is NP-hard. Also we know that $0 \leq k \leq n$ must hold (for a graph of size $n$).

What is wrong about the following reasoning:
Assume I have some algorithm $A_i$ that solves $i$-clique for some fixed $i$ in polynomial time.
Now given some general clique problem without a specific $k$ (these problems are supposedly NP-hard), I simply run $A_i$ for $i=1$ to $n$. Now since $n$ is poly and every $A_i$ runs in polynomial time $p_i$, the resulting algorithm also runs in polynomial time $\sum p_i$, but this cannot be the case, since clique is NP-hard.

What is wrong about my reasoning?

The polynomial depends on the parameter $k$. In particular, the algorithm that people have in mind runs in time $O(n^k)$ (better algorithms might exist, but I believe that we don't know a running time better than $O(n^{O(k)})$. The running time of your proposed algorithm is then big O of
$$
 \sum_{k=1}^n n^k,
$$
which is no longer polynomial.


Prefix encoding of algebraic data types I'm new to coding theory and formal proofs, and am struggling to understand how to construct and reason about prefix-free encoding algorithms on algebraic data types. I hope it's clear if I use notation from haskell below.

I'm tasked with writing a generic prefix encoding algorithm (encode) on ADTs, as well as giving guidance to my users in defining their own implementations of encode for their own types if they wish (this being a major reason I want to understand things better).

I've been jumping around sections of Berstel and Perrin's Theory of Codes which has been very helpful, but it's slow going and my goals are pretty narrow here.

One implementation

I believe I have one obvious implementation, which works like this:

  for products, concatenate the results of applying encode to each of
  the children (arguments to the constructor):

data P a b c ... = P a b c ...

encode (P a b c...) = encode a <> encode b <> encode c <> ...

  for coproducts (or a sum of products), assign to each constructor a
  distinct number tag (using a prefix encoding, to be pedantic) which
  will start the code word, then apply the product rule above

data XYZ a b c d... = X a b ... | Y c d ... | Z ...

encode (X a b...) = encode 1 <> encode a <> encode b <> ...
encode (Y c d...) = encode 2 <> encode c <> encode d <> ...
encode (Z ...)    = encode 3 <> ...
...

The product rule I'm comfortable with: I've proved to myself that the cartesian product of two independent prefix codes is also prefix.

The coproduct rule also seems to be obviously correct if we're thinking in terms of sums-of-products, and if the product rule holds.

Where I'm struggling, I think is in reasoning about recursion, for instance for inductively-defined lists:

List a = Cons a (List a) | Empty

I believe my algorithm works in the presence of recursion, but how can I go about proving this using induction? I think my trouble is that "prefix" is a property of the (infinite) set of code words, not any one.

Other possibly-better algorithms

A proof of the algorithm above would be helpful, but my goal is to have an algorithm that tends to generate compact code words (in fact I don't care about decoding at all; only that the range of encode be prefix), and so I want to understand this more fully.

For instance there is a better algorithm for List. An alternative would be:

encode l = encode (length l) <> map encode l

It occurred to me that maybe this is just a special case of a run-length encoding of a variation of the algorithm in section 1, where constructor tags are all concatenated before the concatenation of encoding the list elements.

But why should it be valid to do that? Can this algorithm for lists be generalized to produce better (more compact) prefix codes for arbitrary ADTs?

A code is prefix-free if there does not exist any distinct two values v, w such that encode(v) is a prefix of encode(w).  So, to prove that your encoding is prefix-free, you start by considering two arbitrary distinct values v, w and demonstrate that encode(v) is not a prefix of encode(w).

I suggest you use proof by induction on the "size" of the largest value, so you'll consider two arbitrary values v, w that are both of size at most $n$.  In this case, a reasonable choice for the "size" is the number of times the recursion was applied, i.e., the number of cells in the list.  Your inductive predicate $P(n)$ states that for every pair of distinct values v, w both of whose size is at most $n$, encode(v) is not a prefix of encode(w).  You want to prove $P(n)$ for all $n$.  To do that using the principle of induction, you need to prove $P(0)$ and prove $P(n) \implies P(n+1)$.  Here $P(0)$ is trivial, so we can focus on the inductive step $P(n) \implies P(n+1)$.

For your example of the list data structure, that shouldn't be too hard.  You'll just case-split on the size and structure of v, w.  There are four cases:

case (a): v has size $\le n$, w has size $\le n$
case (b): v has size $\le n$, w has size $n+1$
case (c): v has size $n+1$, w has size $\le n$
case (d): v has size $n+1$, w has size $n+1$

Case (a) is already covered by $P(n)$, so you only need to reason about the three other cases.  Each one can be handled by using the induction predicate.

I'll describe how to prove case (d).  You should be able to see how to handle the other cases similarly.  Let a = hd(v) and k = tl(v), so that v == a::k.  Similarly let b = hd(w) and l = tl(w) so that w == b::l.  We can see that

encode(v) == encode(1) <> encode(a) <> encode(k)
encode(w) == encode(1) <> encode(b) <> encode(l)

Now we assumed that v, w are distinct, i.e., v != w.  It follows that either a != b or k != l.  If a != b, the fact that encode is prefix-free on ground terms implies that encode(a) is not a prefix of encode(b), which in turn implies that encode(v) is not a prefix of encode(w).  If a == b and k != l, the inductive hypothesis $P(n)$ implies that encode(k) is not a prefix of encode(l) (since both k and l have size one less than v, w, i.e., size $n$), which in turn implies that encode(v) is not a prefix of encode(w).

Ultimately, once you've handled all four cases, you'll have proven that encode(v) is not a prefix of encode(w) for an arbitrary pair of distinct values v, w of size $n+1$, from which $P(n+1)$ follows.

The same techniques can be applied to any algebraic data types that is formed as a recursive combination of products and co-products.


Why are not all recursive languages undecidable? I learned that recursive language are  decidable; correct me if I am wrong. However, I have found some arguments that seem to contradict this. These may or may not be correct; please let me know.

If a language is an REL (recursive enumerable language), I know that there exists a TM (Turing machine) that accepts it (regardless of the TM halting or not). Say, however, that for a language $L$ you have found a TM which accepts it, thus indicating $L$ is REL. We know that, given a TM, it is undecidable whether the TM halts or not. Thus, it is not possible to deduce whether $L$ is recursive or not: we have a TM that accepts $L$, but whether the TM halts or not is undecidable and, thus, we cannot comment on whether $L$ is recursive or not; this makes telling whether $L$ is recursive or not undecidable. Hence, recursive languages should be undecidable―which they are not!

What is wrong with the above reasoning?

You are correct. The problem of deciding "$L$ is a recursively enumerable language" is undecidable. However, that does not make $L$ itself undecidable.

Do not mistake a language for its class! Telling whether $L$ is in a class is definitely not the same as deciding membership in $L$.


Why do you have to worry about cache coherence if you are using shared memory? Wikipedia says that shared memory comes with lots of costs associated with cache coherence costs. But I thought the whole idea of shared memory is that all the CPUs access the same memory? So if one CPU changes that memory then other CPUs would access the same value? It would seem like this would require FEWER cache coherence costs? Is the idea that if one CPU changes its local cache before it writes to shared memory then other CPUs have to be notified?

If two different processors share one memory, each having individual cache, they can end up having two different values in the same address.

Imagine each of two processors has private caches L1 and L2. The cache L3 is shared between both processors. Assume the processor A reads data from address X in L3 to L1 and the processor B reads the same data from the same address (address X in L3) to it's private cache L1. Then, if the processor A modifies the value and does a write-back, the processor B can't figure it out without the support of coherence protocol and would still have an old value in it's own cache.

Basically, you are right. The cache coherence protocol is a mechanism to notify processors about shared memory modification caused by other processors.

The main advantage of the shared memory architecture for a programmer is that there is no need  to explicitly describe communication and interaction between processors (like you would do using MPI, for instance). The coherence and consistency of the memory is fully the responsibility of the hardware.


Clarification on class $SPP$? A language $L$ is in $SPP$ if there is a $GapP$ function $f$ such that

$x\in L\implies f(x)=1$ and $x\not\in L\implies f(x)=0$.

By $x\not\in L$ I think we mean $x\not\in SPP$ correct?

I would have thought $x\not\in L$ if there is no such $f$. Why is it not defined this way? In this case we have $x:f(x)\not\in\{0,1\}$. Is such $x\in L$ or $x\not\in L$?

I guess my query is it is not clear that in this case $x\in L$ and $x\not\in L$ cover all strings?

$\mathsf{SPP}$ is a class of languages, so we can ask whether a language is in $\mathsf{SPP}$, not some input in $\Sigma^*$. The function $f$ is fixed before seeing the inputs, as it defines the language. You don't look at the input and then ask if there exists some function.

Think of it this way, $\mathsf{SPP}$ is the class of languages decidable by a certain class of nondeteministic polynomial time machines, namely those for which the difference between the number of accepting and rejecting paths takes values in $\{0,1\}$ (for all inputs). Note that for a general NP machine, given input $x$ this difference can take values in $\{0,1,...,2^{poly(|x|)}\}$. Given such a machine $M$, the associated $\mathsf{SPP}$ language is the set of all inputs for which the difference is $1$.


Is the language of words having same number of a's and b's context-free? I'm trying to use the pumping lemma, to show that the language $$L = \{w \in \{a, b\}^+: na(w) = nb(w)\}$$ is not context free, where $na(w)$ is the number of $a$'s in $w$ and $nb(w)$ is the number of $b$'s in $w$.
I have this: By contradiction, if $L$ is context free, we use the pumping lemma, then let $N$, and $w = a^{floor(N/2)}*b^{floor(N / 2)}$, with $|w| = N$. Then if we divide $w = uvxyz$, with $v \not = \epsilon$ and $x = \epsilon$, we see that when repeating v there appear more a's than b's, then $uv ^ kxy ^ kz$ $\notin$ L. Contradiction.
Is this right or am I missing something?

This language L = { w | w has equal number of as and bs and w≠ ε (since you put a +)  } is a CFL
A PDA would work as follows :
On reading a :
If the stack is empty or the top of the stack is a push a
If the top of stack is b pop b push nothing
On reading b :
If the stack is empty or the top of the stack is b push b
If the top of stack is a pop a push nothing
At the end of input if stack is empty accept else reject


Can I apply Rice's theorem to decide decidability status of these languages? I came across these languages:

A Turing machine prints a specific letter.
A Turing machine computes the products of two numbers

I was guessing whether I can apply Rice's theorem to decide upon above are decidable or undecidable, something like this:

Not all turing machine languages have specific letter, hence the property is non trivial and hence undecidable.
Not all turing machine languages deal with performing product of two numbers, hence this property is non trivial and hence undecidable.

Doubt 1

Doubt is that, Rice theorem can be applied when we are talking about languages of Turing machines, not about Turing machine behavior or characteristics themselves or anything else which is not related to "only" languages they accept. I tried to interpret given problems as if they are talking about the languages accepted by those Turing machines, so that I can apply Rice's theorem to decide their decidability status. Am I correct with this?

Doubt 2

If we have specification of TM along with its transition functions, in some encoded format, cant we prepare an algorithm to parse that encoding and tell whether the TM ever prints specific letter? The encoding must contain a transition which prints desired letter. We then can define algorithm to check if transition is reachable from the start state. If yes, then TM prints desired letter, and hence decidable. But this contradicts with earlier answers that "whether TM prints a specific letter" is undecidable. What is correct here?

Update

After a lot of thinking, I feel we cant apply Rice's theorem here, since both problems put describe nature of output produced by TM, that is on content of tape after TM has processed original content of tape. But the language accepted by TM is content of tape, before TM starts processing. So both problems dont talk about language of TM and hence we cannot apply Rice's theorem to both problems. Am I correct with this?

You're right that both of these are non-trivial properties. The key is, Rice's theorem applies only to non-trivial semantic properties.

So what defines a semantic property?

Intuitively, a "semantic" property is a property of what the machine does, rather than how the machine works. If you treat the machine as a black box that takes input and gives output, with all the internal mechanisms hidden, semantic properties are the ones you can still measure.

Applying this rule of thumb, we see that printing letters and multiplying numbers are both semantic actions (they're things a program does rather than mechanisms by which the program does it), so yes, Rice's Theorem applies, and these properties are undecidable.


Prove n! is fully time constructible We just finished our "Time constructability" lesson in class last week, and we, for example's sake, showed that $n^k, 2^n$ are fully time constructible, i.e. there exists a (multi-tape deterministic) Turing machine that for $n$ given, halts after exactly $f(n)$ steps, and just asked if we could now prove that $n!$ is fully time constructible (and moved on).

I am not sure how the proof goes, but I am thinking it has to use $n^k$ time constructability to some extent, or some identity involving factorials, since we showed $n^k$ is (fully) time constructible using $n^k = n + \sum_{i=1}^{i=k-1}(n - 1)n^i$.

Hints would be appreciated too, really. Thanks in advance.

Let us assume we have find $n!$ on input $n$. Our complexity is terms of length of the input ( we assume it to be $L=O(logn)$ ). Multiplication of a $k$ bit by $l$ bit number via standard multiplication takes $O(kl)$ operations ( also after multiplication number of bits in the resultant if $O(k+l)$ ) . We multiply linearly in a loop from $1$ to $n$ to get $n!$. So number of operations carried out are upper bounded by $\# = L^2  ( 1 + 2 ...(n-1) ) = \frac{L^2n(n-1)}{2} = O(L^22^{O(L)})=o(L!)$. Thus it is space and time constructible.


What time complexity is a reachability algorithm? I've read there are ways you can determine all reachable pairs using Strongly Connected Components. But, I want to calculate all reachable nodes on the fly - so I don't have to store a massive reachability matrix in RAM. What sort of time complexity would be possible for an algorithm to calculate all reachable nodes in a directed graph, from a single node?

Here's a naive algorithm I came up with, I'm not sure of the time complexity of this. $O(V!)$?

It seems to have an $O(V)$ spacial complexity though.

I've read about the Bellman-Ford algorithm with a time complexity of $O(EV)$ which is essentially $O(V^3)$ and the Floyd-Warshall algorithm which is $O(V^3)$. They require $O(V)$ and $O(V^2)$ space complexity, respectively.

The problem is only inputs can be determined in constant time. So, one would have to find (in $O(V)$ time)  all outputs for a particular node. What I actually did in my solution is invert the graph using a similar technique, before running DFS. But I don't know if this is optimal... Also, due to a copy of the graph being stored in memory, my solution has a spacial complexity worse than the bellman-ford algorithm. If this time complexity is also worse, I may as well use bellman fords algorithm

You can calculate all reachable nodes in $O(V+E)$ time and $O(V)$ space, using DFS on the fly.

If you want to use less than $O(V)$ space, then the problem becomes much more challenging.  I recommend looking at how the SPIN model checker works.  See https://en.wikipedia.org/wiki/Bitstate_hashing.  Even then, the space required is probably still $O(V)$, just with a lower constant factor.


Can we find a Turing machine such that there is no Turing machine to decide whether it halts on $\epsilon$? The halting problem states that there is no Turing machine that can determine whether an arbitrary Turing machine halts on $\epsilon$. But I try to ask something different, can we find a specific Turing machine $M$ such that $L_M=\{ 0^n : M$ halts on $\epsilon \}$ is undecidable?
Or at least can we prove there exists such $M$?

The language itself isn't the issue, it is either $L=\{0^n : n \in \mathbb{N} \}$ or $L=\phi$ and the way to distinguish the cases is only by the right side of the definition of $L$.

In other words, can we define a Turing machine such that we (or a Turing machine) can't determine whether it halts or not on $\epsilon$?

Suppose you had such a TM, namely a machine $M$ for which the problem was "Does $M$ halt on empty input?" Certainly that problem would be decidable: one of two algorithms must be correct, (1) Answer "yes" or (2) Answer "no". The fact that we might not know which one is the correct algorithm is immaterial here; the only thing that matters is that we're sure one of the algorithms is the right one, so we know the problem is decidable. In more general terms, any decision problem with a finite number of instances is decidable.


Is it assumed that lower bounds on the size of monotone circuits apply to general Boolean circuits too? A "general" Boolean (combinatoiral) circuit is a labeled (with the labels: AND, OR, NOT, IN, OUT), directed, acyclic graph, that satisfies:

fan-in=2 for the AND and OR nodes
fan-n=1 for the NOT nodes
fan-in=0 for the IN nodes
fan-out=0 to exactly one node (the OUT node)
Unbounded fan-out to the rest of the nodes (but the OUT node)

A monotone circuit is a Boolean circuit with 0 vertices labeled as "NOT".

The size of a circuit is the number of "gates" (vertices with labels "AND", "OR" or "NOT") it contains.

We know many lower bounds on the size of monotone circuits, that we do not know how to prove on a general Boolean circuit (such as this one on the Clique problem).

My question is: do we assume that lower bounds proven on monotone circuits apply also for equivalent general Boolean circuits (since they compute monotone function), and we just don't know how to prove it; or we assume\ know that these lower bounds do not apply to equivalent general Boolean circuits?

In the latter case, could you supply me with an example of a monotone function computed by both a monotone circuit and a general Boolean circuit, whilst the size of the monotone circuit is gretater than the general Boolean circuit? (I have been stuck on this for hours, seeking for such an example, so I believe that there is no such an example..)

Éva Tardos gave a function which can be computed by a polynomial size general circuit but requires an exponential size monotone circuit. The circuit computes a good enough approximation to the Lovász theta function of the input graph.

Razborov gave an $n^{\Omega(\log n)}$ lower bound monotone circuits computing the bipartite perfect matching function, for which polynomial size general circuits exist.


Converting regular language to regular expression by replacing commas with union I know that regular languages are those that can be described by regular expressions. For the language {0,1}*, is the corresponding regular expression (0∪1)* ? If so, does replacing braces with parentheses and commas with union always work when converting from regular language to regular expression?

Regular expression represent one way of describing regular languages, but there are other notations which you can use to depict such formal languages. E.g. you can use the standard grammar notation ( $S \to aB, B \to bC, \ldots $) or you can use a nondeterministic finite automaton and therefor a deterministic finite automaton to describe a regular language.

Both of your given examples are of the notation-type "regular expression", which can have multiple forms. An 'or' can be e.g. represented as union ($u$), by square brackets ($[abc]$) or maybe a comma like you used in your first example. This is just a matter of what convention you agree to.


How does processing speed affect algorithm performance? I'm currently taking a class on algorithms, and we are studying algorithmic efficiency. I understand classifying algorithms based on their time complexity, but I am confused about the following category of questions:

Suppose algorithm A has time complexity C (C being along the lines of n^2, n + 1, 3 * 2^n, etc.), and it takes t seconds to execute A on a given machine for a certain number of inputs n. If you execute A on a machine that is M times faster than the original machine, how many inputs (n) can be processed in t seconds (same number of seconds as on the previous machine)?

I know that the greater the time complexity of an algorithm, the less improvement is gained by speeding up the machine, however I can't seem to figure out a reliable equation to compute the new number of inputs. For algorithms with linear time complexity, I think I am correct with: multiply the time complexity (constant * n) times the increase in speed to get M * constant * n. I haven't found much information about this either in books or elsewhere on the web; if anyone can help me create a better equation it would be much appreciated!

Let's say that the execution time of an algorithm is $\Theta(f(n))$. That means the execution time is between c·f(n) and C·f(n) for all n ≥ N, for some N, c and C. Because of the constant, you can't say anything definite about the maximum problem size that can be solved in time T on a slow and a fast computer.

You can assume that the actual execution time is c·f(n) for a c that you know; that assumption is neither completely unreasonable nor completely justified. Then define for example n' as the value where c·f(n') = k · c·f(n), to get something meaningful for a machine that is k times faster.

Calculating n' depends on the nature of f(n). If f(n) is linear, then n' = k·n. If f(n) is cubic, then n' = $k^{1/3}·n$. If f(n) = c·n·ln n then n' is a bit less than k·n, the exact result is difficult. If f(n)=$2^n$, then n' = $n + \log k$. The last shows why efficient algorithms don't become less important with faster computers in practice: Because the less efficient the algorithm, the less a faster computer can improve the size of a problem that can be solved in fixed time.


Counting to infintiy problem I came across this explanation for count to infinity problem

However, i don't understand that after the BC link broke, followed by which B erroneously updated the path to C at a cost of 3; Now why will A update the cost to C as 4 (after getting updates from B) since its current cost to C is 2 which is lesser than that advertised by B?

I'll describe what happens, and then describe why each router made the decisions that it made using the scenario from the question.

The starting situation is a steady-state where the routers $A$, $B$, and $C$ have the connectivity $$A\stackrel{1}{\to} B\stackrel{1}{\to} C$$
$B$ is connected to $C$ in one hop, $A$ is connected to $B$ in one hop, and $A$ knows that it is connected to $C$ via $B$ in two hops.

The connection from $B$ to $C$ goes down.
$B$ notices this and updates its distance information from $1$ to $\infty$.
Before $B$ notifies $A$ of the change, $A$ broadcasts an update saying that it has a route to $C$ in $2$ hops.
$B$ updates its routing table to record its belief that it can reach $C$ in $3$ hops via $A$.
$B$ broadcasts an update saying that it has a route to $C$ in $3$ hops.
$A$ updates its routing table to record its belief that it can reach $C$ in $4$ hops via $B$.
Et cetera.

From the comments, your issue is with step $6$. If $A$ already has a route to $C$ in $3$ hops, why wouldn't it just ignore the worse route via $B$ in $4$ hops and stay at $3$ hops? Well, the purpose of a router is to route messages. If I give $A$ a message to send to $C$, it needs to know who to send it to so that it eventually reaches $C$. $A$ knows that it will need to send to the message to $B$ for it to most efficiently reach $C$. In particular, $A$ knows that its distance estimate for a route to $C$ is based on the distance estimate of $B$. So if $B$ says that the distance has increased, $A$ knows that the distance has also increased for it (unless it can find a better route).

Of course, this is exactly what we want. Given the following connectivity diagram, if the connection marked by $(*)$ goes down, we want $A$ to start routing via $D$ ($3$ hops) rather than $B$ ($4$ hops) to send messages to $F$. That $B$ had a $2$ hop path in the past shouldn't matter. If $B$ loses all connectivity to $F$ (e.g. the connection between $B$ and $C$ also goes down), we certainly don't want to keep trying to route through $B$ just because it was the best route in the past.
$$\require{AMScd}
\begin{CD}
A @>>> @>>> B @>>> C \\
@VVV @. @V(*)VV @VVV \\
D @>>> E @>>> F @<<< G
\end{CD}$$

To put it a different way, we're talking about a dynamic version of the Bellman-Ford algorithm where edges can be added or removed in an online manner. Removing edges, in particular, makes the updates no longer monotonic. That is, we can no longer only keep the "best" routes we've ever heard, and we instead have to deal with potential "retractions".

Returning the the original, simpler scenario, the issue is when $B$ receives an update from $A$ that $A$ has a $2$ hop route to $C$, $B$ doesn't know that this information is dependent on $B$'s route to $C$. If $A$ had said that its route to $C$ was via $B$, then $B$ would have realized that this route was no longer useful and would not have updated its routing table in step 4. The split horizon modification solves this particular scenario by simply not having $A$ inform $B$ about any routes that $A$ can only reach (directly) through $B$, so step 3 never occurs as far as $B$ is concerned.


Certificates and NP? My book says a language is in NP if it can polynomially verified if a string belongs to the language with a certificate. It puts no restrictions on what the certificate can be.

For instance, for SAT, the certificate could simply be be the assignment values. We just sub them in and see if it satisfies the expression.

But can't we just let the certificate by whether the string belongs or not? So for instance, for SAT, instead of the certificate being the assignment values, we let it be whether the expression is satisfiable or not. In other words, the certificate is the "answer".

If we let the certificate be this, can't be verify any string in polynomial time? Constant in fact, because we would just be returning the certificate itself, since the certificate is the "answer" (whether the string is part of the language or not)

You must be able to verify in deterministic polynomial time that the certificate is correct.

If your certificate for SAT is a truth assignment, you can verify that it's a satisfying assignment in deterministic polynomial time, by substituting the truth values of the variables and simplifying the expression. However, if your certificate was just "It's satisfiable, honest!", then you would only be able to verify that if you could solve SAT in P, which you probably can't. The certificate has to be a proof that the string is in the language, not just a claim that it is.

Indeed, if it was enough to just claim that the string is in the language, then every language would be in NP!  For example, the certificate version of the halting problem would be just the set of all strings "$\langle M, w\rangle\text{ It halts, honest!}$" for all machines $M$ and inputs $w$ such that $M(w)$ halts, and all strings "$\langle M,w\rangle\text{ This one loops - too bad!}$" for all machines $M$ and inputs $w$ such that $M(w)$ doesn't halt.


Floyd's Cycle detection algorithm | Determining the starting point of cycle I am seeking help understanding Floyd's cycle detection algorithm. I have gone through the explanation on wikipedia (http://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare)

I can see how the algorithm detects cycle in O(n) time. However, I am unable to visualise the fact that once the tortoise and hare pointers meet for the first time, the start of the cycle can be determined by moving tortoise pointer back to start and then moving both tortoise and hare one step at a time. The point where they first meet is the start of the cycle.

Can someone help by providing an explanation, hopefully different from the one on wikipedia, as I am unable to understand/visualise it?

You can refer to "Detecting start of a loop in singly linked list", here's an excerpt:

Distance travelled by slowPointer before meeting $= x+y$
Distance travelled by fastPointer before meeting $=(x + y + z) + y = x + 2y + z$
Since fastPointer travels with double the speed of slowPointer, and time is constant for both when both pointers reach the meeting point. So by using simple speed, time and distance relation (slowPointer traveled half the distance):
\begin{align*}
2*\operatorname{dist}(\text{slowPointer}) &= \operatorname{dist}(\text{fastPointer})\\
2(x+y) &= x+2y+z\\
2x+2y &= x+2y+z\\
x &= z
\end{align*}
Hence by moving slowPointer to start of linked list, and making both slowPointer and fastPointer to move one node at a time, they both have same distance to cover.
They will reach at the point where the loop starts in the linked list.


What is a sparse classifier? Given a two-dimensional data set where each point is labeled $ \{0,1\}$, I want to implement a sparse classifier with $L_p \ \text({ 0<p \leq 1) }$.

I have been reading on logistic regression and regularization. Let me give you an example of what I have been working on.  The concrete example is:  Let $\left((x^{(i)},y^{(i)} )\right)_{i\in \{1,\dots, m\}} $ be my data set with  $y^{(i)}\in \{0,1\} $ and $x^{(i)}\in \mathbb{R}^2$. And the cost function I minimized is

$ J(\theta) = - \frac{1}{m} \cdot \sum_{i=1}^m \large[ y^{(i)}\ \log (h_\theta (x^{(i)})) + (1 - y^{(i)})\ \log (1 - h_\theta(x^{(i)}))\large] + \frac{\lambda}{2m}\sum_{j=1}^n \theta_j^2$.

where $h_\theta(x) = \frac{1}{1+e^{-\theta^{T}x}}$.  I thought that this would be a good introduction to sparse.
Currently I use a neural networks and was wondering if I am heading in the right direction in understanding sparse methods.

That leaves me with the question:

What is the definition of sparse classifiers? What would be an example?

I'll provide an example model using linear regression, however the idea translates to classification in a straightforward manner.

Sparse linear regression is used when we have a model $y = X\beta + \epsilon$ where $y \in \mathbb{R}^n$, $X \in \mathbb{R}^{n \times p}$, $\beta \in \mathbb{R}^p$ and $\epsilon \in \mathbb{R}^n$ when $n \ll p$. If we expect only a small number of columns in $X$ to actually contribute to $y$ then we can impose a penalty on $\beta$ such that "non-important" columns $X_i$ have their corresponding $\beta_i = 0$. We can formally write this as $$\arg \min_{\beta} \|y - X\beta \|^2_2 + \lambda\|\beta\|_0$$
where $\|\cdot\|_0$ is the $\ell_0$ norm that counts the number of non-zero entries. Unfortunately fitting this model exactly is difficult. We can approximate this objective by using the $\ell_1$ norm instead. That is we find $\beta$ for $$\arg \min_{\beta} \|y - X\beta \|^2_2 + \lambda\|\beta\|_1.$$ This model is known as LASSO in the context of linear regression and can be fit by a variety of methods in relatively little time.

All of this hinges on $n \ll p$. If your data are of the form when $n \approx p$ or $n > p$ I'm not sure if sparsity will help much, as you should have enough data to guide inference to true $\beta$ values (provided other assumptions hold, heteroskedasticity, independence, etc). The key takeaway is that you have a large number of predictors and you suspect a small amount of them to actually characterize $y$.


About the complexity of deciding whether no two elements of a collection are the same Given a collection of $n$ numbers, $S$, the question is to decide whether all the elements of $S$ are distinct from each other. If they are distinct from each other (no two of them are the same), print "Yes". Otherwise print "No".

I know the worst case time complexity of this question is $\Theta \left ( n\log n \right )$. Of course it is based on comparison among elements. But I can't figure out how to prove this. Perhaps using the decision tree?

I think there is something wrong with your claim that the complexity is $\Theta(n \lg n)$.  At least, it is not quite that simple.  You don't say where you got that claim from, but I don't think it is accurate, at least in general.

The problem can be solved faster, in some machine models.  For instance, there are sorting algorithms with running time faster than $\Theta(n \lg n)$, in some machine models, and there are other ways to solve this problem -- e.g., using a hash table using a 2-universal hash function should yield a solution whose expected running time is $\Theta(n)$, under a reasonable model of computation.

What is your machine model?  A RAM machine?  What notion of complexity are you OK with?  Worst-case running time of a deterministic algorithm?  Are you OK with a randomized algorithm?  The complexity of the problem will depend upon these fine details.


Why the Smallest Operable Data Type in Most Programming Languages Is One-Byte Sized? Why the smallest operable data type in most programming languages is one-byte sized? Is it possible that to operate with a single bit? If it is possible, how to do it in practical?

Most instruction sets contain instructions that modify a single byte, but not instruction that modify a single bit and so higher level languages tend to reflect that.

Though modern high level languages include what is effectively a bit type, called boolean. Usually, it can only take two value (true or false), but a boolean requires a whole byte for storage.

If you need to store many bits, what you can do is to use a specialized data structure, which internally uses bytes or integers for storage (and so it stores 8 or more bits in a single underlying element). Such data structures include std::vector<bool> in C++ and BitArray in .Net.


Efficiently prime factorising an integer with an oracle Suppose you have a program one_factor(N) that, given an n-digit binary number, N, returns one of the prime factors of the number in Theta(n^2) time (note that I used a lowercase n in my theta notation.)

Using this algorithm, I want to find an efficient algorithm to factor an n-digit binary number into primes and print the prime factors. Moreover, I want to know how fast the algorithm runs as a function of n, and I also want to compute the approximate number of times my algorithm uses the one_factor(N) oracle in the worst case as a function of n.

Suppose we can add, subtract, divide, and multiply two n-digit binary numbers in Theta(n) time.

Here are my thoughts:

If the function one_factor(N) returns N, then I know that N is prime, and this can be my stopping condition.
If one_factor(N) returns a factor f, then I know that N/f is also a factor of N.
Thus, with each call to one_factor(N), I can find two factors of N, and I can divide out these factors from N. Then I can repeat the procedure.

I'm not exactly certain that this procedure always works. However, if it does, then I'll be finding two factors for every call to one_factor(N).I have no clue how to find the worst case number of times I call one_factor(N) or how fast my algorithm is though.  It seems pretty difficult to analyze. I think I would be able to come up with an expression in terms of the number of prime factors that the number originally has, but I can't seem to come up with an expression in terms of the number of binary digits.

This does work (see the fundamental theorem of arithmetic), and is exactly how some efficient factoring algorithms work, such as Pollard-Brent. However they use a weaker oracle, one that just returns a factor, not necessarily a prime one.

Since Pollard-Brent (and maybe others) runs very slowly and/or not at all when passed a prime, there is often another specific prime check in place as well.

A proper recursive routine under those assumptions would be (in Python):

def factorize(n):
    if n == 1: return []
    if is_prime(n): return [n]
    f = one_factor(n)
    return factorize(f) + factorize(n//f)

  It seems pretty difficult to analyze. I think I would be able to come up with an expression in terms of the number of prime factors that the number originally has, but I can't seem to come up with an expression in terms of the number of binary digits.

Analyzing it in terms of the number of prime factors is exactly right. You can then get an upper bound on the number of binary digits by noting that a $b$-bit number may have at most $b-1$ prime factors.


Prove or disprove if $L_{1}$ is Turing-recognizable and $L_{2}$ is co-Turing-recognizable then $L_{1}\cap L_{2}$ is decidable I thought about these languages:
$$L_{1} = A_{TM} = \big\{ \langle M, w \rangle \mid M \text{ is TM and }M \text{ accepts } w \big\}$$
$$L_{2} = \overline{HALT_{TM}} = \big\{ \langle M, w \rangle \mid M \text{ is TM and }M \text{ doesn't halt on input } w \big\}$$

Their intersection:
$$L_{1}\cap L_{2}  = \big\{ \langle M, w \rangle \mid M \text{ is TM and }M \text{ accepts and doesn't halt on input } w \big\}$$

If I assume that the intersection is decidable by TM $T$ so I can use $T$ to decide $A_{TM}$ and that's a contradiction.

Is it true?

Your proof is wrong. Note if $M$ accepts $w$, it must halt on $w$, so $L_1\cap L_2$ is the empty set, which is of course decidable.

To disprove the statement, you can set $L_2$ to be $\Sigma^*$, i.e. the language containing all strings. Since $\emptyset$ is Turing recognizable, $L_2$ is co-Turing recognizable. However, $L_1\cap L_2=L_1$ is undecidable.


Determining on whether topology is a tree or a hypercube Assume that the nodes know that the topology G is either a hypercube or a
tree. Assuming a unique initiator, design an algorithm to discover the topology. In other words, you would like a node to reach terminal state TREE if G is a tree, terminal state HYPERCUBE if instead it is a hypercube. Let n be the number of nodes and m the number of edges, you would like to exchange O(m) messages in the worst case.

I will use DFS until I either:

reach a leaf or
a node that has been visited before.

In the first case it is a tree and in the second one it is a hypercube. How does this sound?

In the below code, I assume every the graph is tree. But If I see cycle, I change the STATE to HYPERCube. This happens when a node gets the token twice.

Sample Pseudocode

Initiator
    Spontaneously
    begin
        Unvisited:= N(x);
        initiator:= true;
        VISIT;
    end

IDLE
    Receving(T)
    begin
        entry = sender;
        unvisited:= N(x) - {sender};
        VISIT;
        STATE = "TREE";
    end

VISITED
    Receiving(T)
    begin
        STATE = "HYPERCUBE"
    end

    Receiving(R)
    begin
        VISIT;
    end

Procedure VISIT
begin
    if Unvisited =! 0 then
        next = Unvisited
        send(T) to next;
        become VISITED
    else
        if not (initiator) then send(Return) to entry endif
        become DONE;
    endif
end

As you have noticed, a simple solution is to generate a token at the initiator and then forward the token through the network using a DFS strategy.

If this token encounters a node that is a leaf, the node will record this information in the token before it is sent back. So when the token has completed the DFS, it will have returned to the initiator who then inspects the token to check if it has encountered any leaf.

The O(m) message complexity follows from the message complexity of DFS, and to show this it's sufficient to prove that the token is sent a constant number of times over each edge.


How to perform alphabetically ordered DFS? I've been working on this graph and just completely botching it. I mean to say that my solution may be the worst possible other than if a monkey had thrown darts at the graph to decide the next path.  Anyhow, I'm lost and really trying to get a grasp of where my conclusion and the proper conclusion diverged dramatically.

I wanted to perform a DFS, show discovery/finish times, the DF forest, and edge classifications. I assumed that: 1) The vertices are listed in alphabetical order in each adjacency list. 2) The vertices are taken in the alphabetical order in the main loop of the DFS algorithm.

Should I be treating this as a directed acyclic graph?

$L$ has an edge to $K$, other than that, the DFS forest you've drawn is correct.  And since $K$ would not be expanded before $L$, there should be an edge $LK$ in the BFS forest.


How is a star topology a regular graph? A regular graph is one in which each vertex has the same number of neighbors, but in a star topology the central vertex is connected to more than one vertex. So, why is it referred to as a regular graph?

summarizing the comments:
by the standard definition, a star is not a regular graph.

They might defined "regular" in a different way than common to apply to star topology.  Specifically, in the paper the OP point out "regular" is never defined (and sparsely used).


Do Scheme operators have associativity? Do operators in the Scheme programming language have associativity. For example, the code (- 5 2 1) evaluates to 2, but it could evaluate to 4 if it was evaluated right-associative. However, it is unambiguous if you were to write the expression as (- (- 5 2) 1). The first example, however, leads me to believe that Scheme is left-associative in the case that you do not group all operations into only two arguments at a time.

Scheme computes (- a b c) as a - b - c, i.e., strictly left to right.

It really makes no sense to talk about associativity in Scheme, which applies to how an otherwise ambiguous expression like a # b # c is to be interpreted, either as (a # b) # c or a # (b # c) (or even forbid such combinations). In Scheme no such ambiguity is possible, everything is prefix. And the function called is responsible to decide what to do with it's arguments, even if the number of arguments is variable (as in this case). It is probably more natural to work left-to-right.


Can non-recursively enumerable languages be solved with dovetailing? I'm a bit confused about the dovetailing concept. It seems too powerful. Could it solve non-recursively enumerable languages?

Dovetailing is just a technique for programming Turing machines. It doesn't give Turing machines any additional power. In particular, dovetailing cannot cause a Turing machine to decide an undecidable problem, recognize an unrecognizable language, and so on.

While dovetailing might seem like an arcane technique, it is actually very similar to context-switching, which enables our computers to run many programs in parallel. This doesn't give our computers any more power – on the contrary, context-switching incurs overheads.


Uniqueness of byte arrays Consider the situation, when you're given M byte arrays of size N, and you need to check if all of them have unique content (so there are no two arrays that have the same sequence of bytes). What would be the best option to check this condition?
From my point of view, there are several approaches available for this problem (the examples provided below are relevant for Go programming language ecosystem):
Compare hash sums
Take some fast non-cryptographic hash (like murmur3) and compute hash sum from the every array. Store every sum in a set and find duplicates.  Provided that hash is O(N), the whole operation should be O(M*N):
func unique(arrays [][]byte) bool {
   set := newSet()
   for _, array := range arrays {
       sum := hash(array)
       dump := hex(sum)
       if set.contains(dump) {
            return false
       }
       set.add(dump)
   }
   return true
}

Compare arrays bytewise
In Go there is [bytes.Equal][2] function written in pure assembly which can utilize platform-dependent optimizations. So it's possible to iterate over the arrays and check equality pairwise for O(M^2*N):
func unique(arrays [][]byte) bool {
    for i := 0; i < len(arrays); i++ {
        for j := i + 1; j < len(arrays); j++ {
            if result := bytes.Equal(arrays[i], arrays[j]); result {
                return false
            }
        }
    }
    return true
}

Despite the fact that this algorithm has worse computational complexity, it may run faster due to above-mentioned optimizations.
String(?) algorithm

Take ith byte from every array
Compare bytes;
If all are unique, return true;
If there are repeating values, repeat step #1 for (i+1)th bytes for only those arrays which had equal ith bytes.

This should be also O(M*N), because in the worst case one would have to completely compare all arrays. But it seems like this approach will bring too much overhead (I mean state of algorithm between iterations etc.)
Please share your opinion about the optimal way to solve this problem.

You need to read all items in the worst case. Assume you have written some algorithm which reads items in any order and processes them with any amount of cleverness. And I'm your opponent and try to make you read as many items as possible.

Here's what I do: Whenever your algorithm reads an item I store an "X" just before you read it. I do that except when you have read one array completely, which consists of all X, and you are reading the last item of another array, in which case I store a value that makes this row different from all other rows that were read completely. When you read the very last item, I can decide to store a value that makes all arrays unique, or I store another X and you have two arrays that are identical.

Whatever you do, until you read the very last item you don't know whether two arrays are identical or all arrays are unique.


What is the purpose of k in the transitive closure method? When converting a DFA to a regular expression using the transitive closure method, what is the significance of state $k$ and what values $k$ takes? If $k$ represents the intermediate states then what are the values for $k$? That is while applying the method, for which value of $k$ should we stop finding the regular expressions?

One way you can think about the transitive closure method of converting DFAs to regular expressions (suggested by Michael Sipser in "Introduction to the Theory of Computation") is to think about converting a DFA to a regular expression by progressively ripping out states from the DFA and replacing transitions into and out of that state with new transitions labeled with regular expressions that have the same effect as entering and leaving the state.  Once you have ripped out a sufficiently large number of states, you can directly read off the regular expression from the resulting automaton.

$k$ in this algorithm is used to indicate what states you have eliminated so far.  You number all of the states $1, 2, 3, ..., n$, then use $k$ to indicate the numbers of all states you have eliminated at a particular point.  First you eliminate state 1; then states 1 and 2; then states 1, 2, and 3; etc.  Once you have $k = n$, you've eliminated all states and can just read off the answer.

If you'd like a graphical presentation of how this works, I have a set of lecture slides I used when teaching this construction.  It doesn't formally specify the algorithm or prove correctness, but should give you a visual representation of what the algorithm is doing.

Hope this helps!


Why is reflexivity enough in this HoTT formulation of quotient types? In this formulation of quotient types in cubical type theory I was able to implement an eliminator and use that to implement basically curried function application. However, in all this, the only requirement on the factoring relation is that it is reflexive.

I find this surprising. I would have expected transitivity and symmetry to also be needed somewhere along the way. Is there an intuitive explanation for why reflexivity is enough?

Your Quot construction is a set-truncated quotient by an arbitrary relation $R$ since you never use the reflexivity assumption in the construction. That is, you don't even need the reflexivity of $R$ to perform the quotient and derive its basic properties.

As the HoTT book explains in Section 6.10, it is perfectly possible to make set-truncated quotients by an arbitrary relation because reflexivity, transitivity and symmetry are taken care of by the paths themselves (because there are identity paths, paths can be reversed, and composed). That is, the quotient $A/R$ is equivalent to the quotient $A/\overline{R}$ where $\overline{R}$ is the equivalence relation generated by $R$.

There is one property that you will not get, namely that (using the notations from your file) $(x : A) \to (y : A) \to \mathsf{point}\;x = \mathsf{point}\;y \to R\;x\;y$. For that you need the fact that $R$ is a proposition and an equivalence relation.


Given a randomised algorithm for a problem, is there a corresponding deterministic algorithm? Does every randomised algorithm have a corresponding deterministic algorithm solving the same problem?

I'm going to guess that the deterministic algorithm will take more time, while the randomised algorithm although it has errors will generally be faster. This is from what I have seen of them so far. Let me know if this is wrong.

If the running time of the algorithm is bounded, in the sense that for every input $x$ there is a number $T(x)$ such that whatever the coin tosses are, the algorithm always terminates within $T(x)$ steps, then you can always "try all possibilities" and convert your randomized algorithm to a deterministic one, albeit with a possibly much larger running time.

For polynomial time algorithms in particular, it is conjectured that you can derandomize any algorithm with at most a polynomial blow-up in time, a conjecture usually stated as $\mathsf{P}=\mathsf{BPP}$.


MSO (Monadic second-order logic) Logic On Words Let L be a language over $\Sigma = \{a,b,c\}$ that contains all words, where the length $|w|_b$ (number of all b's) has remainder 1 if divided by 3.

MSO logic over words are definded as follow:

I want to express this language using MSO logic. But my problem is how can I count the b's to calculate the reminder? So it would be easiert if I just look on $|w|$, cause I could use max.

Start with the following: There are three disjoint sets $X_1,X_2,X_0$ that together hold the $b$-positions of the string. The last $b$ is in set $X_1$,


Minimizing cost of bus travel A man has to travel for given number of days by bus.
He can buy either:

$1$ day ticket for $2Rs$ (valid for 1 day)
$7$ days ticket for $7Rs$ (valid for 7 consecutive days)
$30$ days ticket for $25Rs$ (valid for 30 consecutive days)

We are given an array, whose elements are the day numbers on which he travels.

For example, if the given array is
$\{1,3,5,8,9,10\}$, then he travels on these $6$ days. Now we have to minimize the cost of  his travel.
What would be the best approach to solve this problem?

There's a rather simple algorithm for this.

You start at the end of the array, day 10. If you only wanted to travel from that day onwards, you could buy a 1 day, 7 day, or 30 day ticket. 1 day is optimal at a cost of 2.

Then you check the second to last entry, day 9. If you only wanted to travel from that day onwards, you could buy a 1 day ticket (and add the optimal combination of tickets from day 10 at cost 2, total cost = 4), or a 7 or 30 day ticket, which is more expensive.

Again from day 8, the cheapest is a day ticket plus the optimal combination from day 9 on, total cost 6. But then you check day 5: If you buy a single day ticket, you pay 2 plus 6 for travel from day 8, total 7. But if you buy a weekly ticket, the cost is only 7. You then proceed to the beginning of the array.

int n = 6;
int dates [n+1] = { 1, 3, 5, 8, 9, 10, infinity };
int ticket [n];
int cost [n+1];

cost [n] = 0;

for i = n-1 downto 0
    cost for 1 day = 2 + cost [i+1]
    let k7 = smallest k where dates [k] ≥ dates [i] + 7
    cost for 7 day = 7 + cost [k7]
    let k30 = smallest k where dates [k] ≥ dates [i] + 30
    cost for 30 days = 25 + cost [k30]

    if cost for 1 day is smallest
        ticket [i] = 1
        cost [i] = cost for 1 day
    else if cost for 7 day is smallest
        ticket [i] = 7
        cost [i] = cost for 7 days
    else
        ticket [i] = 30
        cost [i] = cost for 30 days
    endif

That's easily done in O (n) for any fixed number of different tickets. The answer would be a bit different if you have "weekly" tickets that are valid from Monday to Sunday, or from Sunday to Saturday, depending on the country, and "monthly" tickets that are valid from the 1st to the last day of a month.


Triangles covering all vertices of a tri-partite graph This question is an extension of this one: Min path cover for a three-layer graph with all paths traversing all layers.
I'm designing fictional fruits. Each fruit has three attributes; color, taste and smell. Also, each of the values of the attributes have some compatibility with the values of the other attributes. So, we get a tri-partite graph. An example is shown below. Here, 1 and 2 are color attributes, 3,4 and 5 are taste attributes and 6 and 7 are smell attributes. Also, color-1 is compatible with taste-3 and smell-6 and so on.

I want to design a minimal number of fruits while still covering all attributes (all 2 colors, all 3 tastes and all 2 smells in this case). For example, the example graph above has the following solution (shown with pink lines, fruit-1 has color-1, taste-3 and smell-6; fruit-2 has color-1, taste-4 and smell-7 while fruit-3 has color-2, taste-5 and smell-6; hence covering all levels of all attributes with 3 fruits):

We know this is optimal since there are three tastes and we couldn't have used less than 3 fruits in this case.
The question is: how to design an algorithm to get the minimum number of fruits required and their configurations given a general graph like the one specified above.
Note that it might not have been possible to cover all attributes even if the graph has no isolated vertices and I asked a question on feasibility here: https://math.stackexchange.com/questions/3998648/possible-to-cover-all-vertices-of-a-tri-partite-graph-with-triangles

First, let's invent a decision version of your problem, in which a number $t$ is given in addition to the graph, and the goal is to decide whether the vertices in the input graph can be covered with at most $t$ triangles.
If the NP-hard problem 3-dimensional matching (3DM) remains NP-hard under the restriction that $|V|$ is divisible by 3 and the target parameter $k=|V|/3$ (which I consider very likely but don't know for sure), then your problem is also NP-hard by reduction from it:
Given such an instance of 3DM, construct an instance of your problem on the same set of vertices by creating a triangle $abc$ for each 3-tuple $abc$ in the 3DM instance, and setting $t=|V|/3$. Clearly a solution to the 3DM instance corresponds to a solution to the constructed instance of your problem. Such a solution is optimal since all 3-tuples are disjoint. In the reverse direction, if all vertices can be covered using just $|V|/3$ triangles then the triangles must all be disjoint, meaning this corresponds to a valid solution to the original 3DM instance. Together, this means that the answer (YES or NO) is the same to both problem instances. Since the construction is polynomial time, and if the restricted variant of 3DM is NP-hard, so is your problem.
To extend this to a full proof of NP-hardness, one approach would be to try to prove NP-hardness of the restricted variant of 3DM -- e.g., by reducing the general variant to it.


Counter Mode Encryption Vulnerabilities Hi All,
I am solving a question about counter mode encryption in symmetric crypto. I am new to the topic and don't really understand the matter, could you help me a little how to solve the following task?

The formula for counter mode encryption is
 Ci = Pi ⊕ E (IV + i, K).
Suppose we instead use the formula
 Ci = Pi ⊕ E (K, IV + i).
Is this secure? If not, what's the possible attack?

If you know one block of plaintext (which in many situations is a reasonable assumption), you can break the second cryptosystem but not the first one (assuming your cipher is secure!). I'll let you figure out how.

You can extend this attack to the case in which one block of plaintext has small entropy, which is an even more realistic assumption.


Is Bresenham's Line Drawing algorithm still used today? If so, I cannot find any examples of this.

Edit: By "used", I mean are they still used in rendering in games or whatever. I haven't seen it used anywhere except in MS Paint because Wu's algorithm looks way better (yet is still not expensive as far as I know).

Google Scholar reports hundreds of mentions since 2012.

Specifically, the patents

System and method of optical reading employing virtual scan lines (US 20100308114 A1, 2010),
System and method for data reading using raster scanning (US 8286877 B2, 2012) and
Compensated virtual scan lines (US 8335341 B2, 2012)

explicitly mention the algorithm, if only in exemplary fashion.

Further searches, e.g. on YouTube, suggest persisting interest in the algorithm; it still seems to be in the mainstream.

That does, of course, not mean that there are no better ones, or that professional products use it still. But since proprietary devices are usually closed-source, we won't be able to answer that question with confidence.


Levenstein distance and dynamic time warp I am not sure how to draw parallel between the Wagner–Fischer algorithm and dtw algo.
In both case we want to find the distance of each index combination (i,j).

In Wagner–Fischer, we initiate the distance by the number of insert we'd have to do from one empty string to another.

let wagnerFischer (s: string) (t: string) =
   let m, n = s.Length, t.Length
   let d = Array2D.create (m + 1) (n + 1) 0

   for i = 0 to m do d.[i, 0] <- i
   for j = 0 to n do d.[0, j] <- j

   for j = 1 to n do
       for i = 1 to m do
          d.[i, j] <- List.min [
                           d.[i-1, j  ] + 1;
                           d.[i  , j-1] + 1;
                           d.[i-1, j-1] + if s.[i-1] = t.[j-1] then 0 else 1; ]
   printfn "edit matrix \n %A" d
   d.[m,n]

in the DWT we initiate the boundary at +infinity because we dont want to 'skip' any numbers of the sequence, we always want to match with another item.

What I dont see is what changes between the DWT and the WF algo that prevent use to update the distance in homogeneous way.
In DWT we systematically add the cost, whereas in the WF algo, we have this non homegenous function wrt different cases

I understand both algo, but dont make the connexion between those differences in the cost function update ..
Any idea to understand the difference intuitively  ?

let sequencebacktrack (s: 'a seq) (t:'a seq) (cost:'a->'a->double) (boundary:int->double)  =
   let m, n = s |> Seq.length, t |> Seq.length
   let d = Array2D.create (m + 1) (n + 1) 0.

   for i = 0 to m do d.[i, 0] <- boundary(i)
   for j = 0 to n do d.[0, j] <- boundary(j)

   t |> Seq.iteri( fun j tj ->
            s |> Seq.iteri( fun i si ->
                        d.[1+i, 1+j] <- cost tj si + List.min [d.[1+i-1, 1+j  ];
                                                               d.[1+i  , 1+j-1];
                                                               d.[1+i-1, 1+j-1]; ] ))
   printfn "edit matrix \n %A" d
   d.[m,n]
//does not work
let wagnerFischer2 (s: string) (t: string) =
   sequencebacktrack s t (fun a b -> if a = b then 0. else 1.) (id >> double)

let b = wagnerFischer2 "ll" "la"

There is in fact a whole bunch of related algorithms. In modern context I believe "time warp" would be called sequence alignment. Depending on whether you want to match complete strings or optimal substrings one gets Needleman-Wunsch and Smith-Waterman.

In your latter algorithm the costs seem to vary, that is one can attribute different costs for deletion and insertion of a character, as well as for changing characters. Your first algorithm seems to fix these costs to $1$ for all three possible changes.


Balance groups based on average, element constraints and size It's a complex situation, where I want to balance groups of numbers based on the average of these numbers, while keeping the group size unchanged and not breaking elements constraints.

Let me explain in detail what I mean:

I need to switch elements between the groups in order to balance the group average.
However the elements with the same color needs to stay in the same group, and the groups must not change size.

What would be a good approach for solving this problem? I'm using c++ to code a matchmaking system for a game, and that's the mathematical problem I'm stuck with currently.

My knowledge of mathematical notations are quite weak, so I would prefer some sort of pseudo-code as answer (if possible)

This is a combinatorial optimization problem.  It is NP-hard (it is easy to see it is as hard as the partition problem).  Consequently, you should not expect any general problem that is efficient, scales to large problem sizes, and always returns the optimal answer.

Instead, you probably will want to use some kind of heuristics.  One approach worth considering is to use integer linear programming or some variant of it.  If your objective function is minimize the spread between largest group average and the smallest group average, then the problem can be encoded as an instance of integer linear programming (ILP) and then you could use an off-the-shelf ILP solver.  If your objective function is to minimize the standard deviation of the group averages, then the problem can be encoded as an instance of integer quadratic programming (MIQP) and then you could use a MIQP solver.  You might want to run them for a limited amount of time and use the best solution found within that time period, rather than run as long as needed to find the exact optimal solution.

The encoding of the problem as integer programming is tedious but fairly straightforward.  You introduce zero-or-one integer variables $x_{i,j}$, with the intended meaning that $x_{i,j}=1$ means that the $i$th item is assigned to the $j$th group.  (When you have multiple elements of the same color, treat them all as a single item with the same value of $i$; they just add more than one to the number of elements in that group.)  Then the number of elements in the group is a linear function of the $x$'s, and the group average of each group is a linear function of the $x$'s, so you can write down constraints for these to be a valid solution as linear inequalities.


What is the time complexity of checking if a number is prime? Could some one please explain how to get the time complexity of checking if a number is prime? I'm really confused as to if it is $O(\sqrt{n})$ or $O(n^2)$.

I iterate from $i=2$ to $\sqrt{n}$ and continuously checking if n%i != 0.

However, do we consider the complexity of the square root function also?

If we do, the Newtons method for finding square roots has a complexity of $n^2$.

When $n$ is the input, we test $\sqrt{n}$ divisors. However, we also have to take into account the complexity of division itself. For a number with $b$ bits, this takes $O(b \log b \log\log b)$ operations, when we are using the Schönhage–Strassen algorithm. Since half of the numbers below $\sqrt{n}$ have $\log(\sqrt{n})$ digits, we may assume the all have this amount of digits. It only matters a factor $\frac12$ at most, and that is absorbed in the $O$.

This gives a computational complexity of $O( \sqrt{n} \log \sqrt{n}\log(\log(\sqrt{n}) ) \log\log(\log(\sqrt{n}) )))$. We can simplify this to $O( \sqrt{n} \log(n) \log(\log(n) ) \log(\log(\log(n) )))$.

However, when notating it using the number of bits $b$ of a number, which is more standard usage, we get a computational complexity of $O(2^{b/2} b \log b \log\log b)$.

You also need to compute $\sqrt{n}$ but that has only complexity $O(b \log b \log\log b)$ when using Newton's method and the Schönhage-Strassen algorithm.

However, this is not optimal. The current best algorithm, the AKS algorithm, reaches a complexity of less than $O(b^{7})$ worst-case , which is much faster.
(To be precise, even $O(b^{6+\varepsilon})$ for any $\varepsilon>0$ has been shown, but that is more complicated than it needs to be for this answer.)


An efficient method to compute a minimum set of sets that form the union of these sets? Let's say we have a set of sets:

$$\mathfrak S = \lbrace S_1, S_2, ... , S_n\rbrace$$

And the union of the all the sets in this set:

$$\mathfrak U = \bigcup\limits_{i=1}^{n} S_{i}$$

And so there is at least one minimum set of sets that is identical to this union:

$$(\mathfrak M \subseteq  \mathfrak S) = \mathfrak U$$

What is the most efficient known method of computing $\mathfrak M$ ?

In case $S_i$ sets are finite your problem is reduced to the Set Cover problem which is NP-complete. You can also attack this problem by any approximation algorithm, e.g. Greedy algorithm, or by using Linear programming.


Shaefer's Dichotomy Theorem Could you please resolve a confusion with Schaefer's theorem for me? Namely, why does it not imply many problems in P are NP-complete? For example, primality testing surely cannot be reduced to one of the six classes in the theorem, so why does that not imply it's NP-complete?

Primality testing is not of the form $\text{SAT}(S)$ for a finite set $S$ of finite-arity relations over the Boolean domain.  Thus, it's not covered by Shaefer's theorem, and Shaefer's theorem says nothing about the hardness of primality testing.  See this answer: https://cs.stackexchange.com/a/43831/755.

See also Why does Schaefer's theorem not prove that P=NP? for a more detailed explanation.


Turing Machine that halts iff the tape contains at least two '1's Contruct a Turing Machine that halts if and only if the tape it is on contains at least two '1's.

My attempt:

The gist of this turing machine is that it has to check all of the cells, and since it is infinite in both directions, one way of indexing it is a follows

Thus it has occurred to me to write a pseudocode for the TM's behaviour like this:

n:= 0           //number of '1's encountered
i:= 0           //index
while(true)
{
  if(n==2)
    halt
  for k=0 upto i
  {
    check()
    if(i even)
      move left
    if(i odd)
      move right
  }
  i++
}

Where check is the function defined as follows:

check()
{
if(current cell contains 1)
  n++
}

But this seems really hard to implement as a turing machine, especially since there are two variables involved. My guess is that I am overthinking and there is a much cleaner, nicer and elegant solution.

So my question is: What would be a better solution?

I managed to solve it in the end.
If anyone is interested, I left a diagram of the TM here


Which is a type of objects in mainstream OO languages: a class, an interface, an abstract class, a metaclass? In Types and Programming Languages by Pierce, Section 18.6 Simple Classes in Chapter 18 Imperative Objects says:

  We should emphasize that these classes are values, not types. Also we can,
  if we like, create many classes that generate objects of exactly the same type.
  In mainstream object-oriented languages like C++ and Java, classes have a more
  complex status—they are used both as compile-time types and as run-time
  data structures. This point is discussed further in §19.3.

The only place which Section 19.3 Nominal and Structural Type Systems says about classes is:

  These type names play a crucial role in Java’s subtype relation. Whenever
  a new name is introduced (in a class or interface deﬁnition), the programmer
  explicitly declares which classes and interfaces the new one extends (or, in
  the case of a new class and an existing interface, “implements”). The compiler
  checks these declarations to make sure that the facilities provided by the new
  class or interface really extend those of each super-class or super-interface—
  this check corresponds to record subtyping in a typed lambda-calculus. The
  subtype relation is now deﬁned between type names as the reﬂexive and tran-
  sitive closure of the declared immediate-subtype relation. If one name has not
  been declared to be a subtype of another, then it is not.

Does the above quote or some other places in Section 19.3 explain the second highlighted sentence in the first quote from Section 18.6, i.e. why

  In mainstream object-oriented languages like C++ and Java, classes have a more
  complex status—they are used both as compile-time types and as run-time
  data structures

? (I don't see Section 19.3 mentions that a class is a type of objects in mainstream OO languages, and even explains it.)

In Chapter 18 Imperative Objects, is an interface a type of objects?

In mainstream OO languages (such as Java, C#, I am not sure if C++ has interface),

is an interface a type of objects?

An interface seems to me a type of classes, since many classes can implement the same interface. Since a class is a type of objects, is an interface a kind?
Is an abstract class essentially the same concept as an interface? (In terms of being a type of classes or something else)
in Python, there is another concept "metaclass". Is a metaclass a type of object, a kind, or something else?

I have a related post a while ago: Is the implementation relation between an interface and a class an instantiation or inheritance relation, or neither?. It also introduces concept "metaclass" of Python, and my confusions between interface, class, abstract class, and metaclass. Appreciate if you could also take that into account.

Thanks.

Unfortunately I don't have a copy of TAPL with me, so I can't figure out exactly what the author intends. But there is a point we should make, that types are something which classifies terms or values, even if there are other pieces that are related to the type.

As such, classes and interfaces are not literally types themselves in Java or C++. Rather, each instance of a class/interface defines a few things simultaneously:

At runtime, we associate with each such defined class, a table of details. This can include where to find code for overrideable methods, but also information like which methods exist, what fields and the like, for reflection.
Both at compile time, and runtime, it defines a type with the same name, which denotes those objects whose runtime class is a subclass of said class.
So here we have a distinction we can make: Each object has exactly one class, but belongs to potentially many different types (the transitive reflexive closure of the subtyping relation).

This is different from the situation in something like OCaml, or likely, those simple objects in TAPL. If there is no means of distinguishing which class created an object, we likely do not want to associate it with a type (as we cannot do anything different with it). In particular, classes in OCaml define a means of constructing an object, so they are a value (just as in the function x -> x + 2).

Following this reasoning, we can think about what metaclasses imply for Python. When we define a metaclass, it creates a particular object, much the same as any other Python object. This portion is a value. Now, later code may reference that value for construction of classes. As stated, we haven't quite made them relate to types yet.

And from here, the answer really comes down to what we decide the types are. It is reasonable to say that objects have a type based on their class (Note again, this is distinct from the denotation given by the type function in Python, which returns a value related to our type). In this situation, yes, metaclasses can be considered to define a kind, as to each class-type, we have an associated metaclass. But we'd be just as reasonable to not consider anything here to be types, and to work only with values and functions.

To really talk about this, we might want to say that Python has a reflection principle: for every class value, we have an associated class type, and vice versa. Extending this we can talk about metaclasses as kinds, (but that will begin requiring subkinding, which may be undesirably complex).

So the key point of distinction we come down to is this: types are classifications, and values are concrete data structures. There can certainly be relations in languages which have run-time type information, but they are not literally identical, and there may be multiple sorts of things defined simultaneously.


Use of Big-O Notation: Size of Input vs Input It is my understanding that, when one is describing time complexity with $\mathcal{O}$, $\mathcal{\Theta}$, and $\mathcal{\Omega}$, one must be careful to provide expressions with regards to the size of the input as opposed to the input itself (particularly in the case of numeric algorithms).

For instance, trial division for integer factorization takes up to $\sqrt N$ divisions to factor the integer $N$.  However, the size of the input is the number of bits, $w = \lg(N)$.  Thus, integer factorization takes $\mathcal{O}\left(2^{w/2}\right)$ time with respect to the size of the input ($w$ bits).

My question: Given the above, would it be considered correct to write in a CS article  (relatively informal--on the scale of a blog post) to write that "integer factorization takes $\mathcal{O}(\sqrt{N})$ time with respect to the input variable $N$," and assume that the reader realizes they should substitute $w=\lg(N)$ to obtain the time complexity with respect to the size of the input?

You have it backwards, but you are on to an important distinction.

$O(N)$ if $N$ is a number in the input is perfectly well-defined and can appear in, say, the $\Theta$-asymptotic of a runtime function.

In your example, note that $\sqrt{N} = 2^{w/2}$ and thus $O(\sqrt{N}) = O(2^{w/2})$ -- it's just another way of expressing the same function class, given the identity $w = \lg N$.

The distinction between $f(N)$ and $f(\langle N \rangle)$ is only important in the context of complexity classes. Many of those are defined along the lines of

  Class $X$ contains all problems for which there is an algorithm with runtime in $O(f(|x|))$ where $x$ is an input string.

For examples, see pseudo-polynomial problems/algorithms.


What is the time complexity of the following loop? function (n)
    i = 1
    s = 1
    while (s <= n)
        i = i+1
        s = s*i
        print "*"
end

Assuming all operations are done in constant time, this loop runs in $\Theta(n!^{-1})$ where $!^{-1}$ is the inverse factorial. Intuitively, the program will enter the loop $i$ times, $i$ being the smallest integer so that $i!\geq n$.


Reduction Vertex cover into Dominating Set I have a question to the reduction from Vertex Cover into Dominating Set.

So my lecture says if I have a undirected Graph $G = (V,E)$ where $S \subseteq V$ is a vertex cover. Then we construct a new graph $G'$ which has the same vertices of G, except the isolated ones. For each edge $\{u,v\}$ in $G$, we add a new vertex that is connected with $u,v$.

So my question is, why I have to form every edge into triangles? Why is it not enough to only remove the isolated vertices?

Every vertex cover without isloated vertices is a dominating set at the same time

Remember that you also have to care for the reverse direction. In this case, you should see whether every dominating set is also a vertex cover (hint: no, but why?).