What's the difference between a type and a kind? I am learning the programming langauge Haskell, and I'm trying to wrap my head around what the difference between a type and a kind is.

As I understand it, a kind is a type of type. For instance, a ford is a type of car and a car is a kind of vehicle.

Is this a good way to think about this?

Because, the way my brain is currently wired, a ford is a **type** of car, but also a car is a **type** of vehicle whilst at the same time a car is a **kind** of vehicle. I.e. the terms type and kind are interchangeable.

Could anyone shed some light on this?

Here, "values", "types", and "kinds" have formal meanings, so considering their common English usage or analogies to classifying automobiles will only get you so far.

My answer pertains to the formal meanings of these terms in the context of Haskell specifically; these meanings are based on (though are not really identical to) the meanings used in mathematical/CS "type theory".  So, this won't be a very good "computer science" answer, but it should serve as a pretty good Haskell answer.

In Haskell (and other languages), it ends up being helpful to assign a type to a program expression that describes the class of values the expression is permitted to have.  I assume here that you've seen enough examples to understand why it would be useful to know that in the expression sqrt (a**2 + b**2), the variables a and b will always be values of type Double and not, say, String and Bool respectively.  Basically, having types assists us in writing expressions/programs that will work correctly over a wide range of values.

Now, something you may not have realized is that Haskell types, like those that appear in type signatures:

fmap :: Functor f => (a -> b) -> f a -> f b

are actually themselves written in a type-level Haskell sublanguage.  The program text Functor f => (a -> b) -> f a -> f b is -- quite literally -- a type expression written in this sublanguage.  The sublanguage includes operators (e.g., -> is a right associative infix operator in this language), variables (e.g., f, a, and b), and "application" of one type expression to another (e.g., f a is f applied to a).

Did I mention how it was helpful in many languages to assign types to program expressions to describe classes of expression values?   Well, in this type-level sublanguage, expressions evaluate to types (rather than values) and it ends up being helpful to assign kinds to type expressions to describe the classes of types they are permitted to represent.  Basically, having kinds assists us in writing type expressions that will work correctly over a wide range of types.

So, values are to types as types are to kinds, and types help us write value-level programs while kinds help us write type-level programs.

What do these kinds look like?  Well, consider the type signature:

id :: a -> a

If the type expression a -> a is to be valid, what kind of types should we permit variable a to be?  Well, the type expressions:

Int -> Int
Bool -> Bool

look valid, so the types Int and Bool are obviously of the right kind.  But even more complicated types like:

[Double] -> [Double]
Maybe [(Double,Int)] -> Maybe [(Double,Int)]

look valid.  In fact, since we ought to be able to call id on functions, even:

(a -> a) -> (a -> a)

looks fine.  So, Int, Bool, [Double], Maybe [(Double,Int)], and a -> a all look like types of the right kind.

In other words, it looks like there's only one kind, let's call it * like a Unix wildcard, and every type has the same kind *, end of story.

Right?

Well, not quite.  It turns out that Maybe, all by itself, is just as valid a type expression as Maybe Int (in much the same way sqrt, all by itself, is just as valid a value expression as sqrt 25).  However, the following type expression is not valid:

Maybe -> Maybe

Because, while Maybe is a type expression, it doesn't represent the kind of type that can have values.  So, that's how we should define * -- it's the kind of types that have values; it includes "complete" types like Double or Maybe [(Double,Int)] but excludes incomplete, valueless types like Either String.  For simplicity, I'll call these complete types of kind * "concrete types", though this terminology isn't universal, and "concrete types" might mean something very different to, say, a C++ programmer.

Now, in the type expression a -> a, as long as type a has kind * (the kind of concrete types), the result of the type expression a -> a will also have kind * (i.e., the kind of concrete types).

So, what kind of type is Maybe?  Well, Maybe can be applied to a concrete type to yield another concrete type.  So, Maybe looks like a little like a type-level function that takes a type of kind * and returns a type of kind *.  If we had a value level function that took a value of type Int and returned a value of type Int, we'd give it a type signature Int -> Int, so by analogy we should give Maybe a kind signature * -> *.  GHCi agrees:

> :kind Maybe
Maybe :: * -> *

Going back to:

fmap :: Functor f => (a -> b) -> f a -> f b

In this type signature, variable f has kind * -> * and variables a and b have kind *; the built-in operator -> has kind * -> * -> * (it takes a type of kind * on the left and one on the right and returns a type also of kind *).  From this and the rules of kind inference, you can deduce that a -> b is a valid type with kind *, f a and f b are also valid types with kind *, and (a -> b) -> f a -> f b is valid type of kind *.

In other words, the compiler can "kind check" the type expression (a -> b) -> f a -> f b to verify it's valid for type variables of the right kind the same way it "type checks" sqrt (a**2 + b**2) to verify it's valid for variables of the right type.

The reason for using separate terms for "types" versus "kinds" (i.e., not talking about the "types of types") is mostly just to avoid confusion.  The kinds above look very different from types and, at least at first, seem to behave quite differently.  (For example, it takes some time to wrap your head around the idea that every "normal" type has the same kind * and the kind of a -> b is * not * -> *.)

Some of this is also historical.  As GHC Haskell has evolved, the distinctions between values, types, and kinds have started to blur.  These days, values can be "promoted" into types, and types and kinds are really the same thing.  So, in modern Haskell, values both have types and ARE types (almost), and the kinds of types are just more types.

@user21820 asked for some additional explanation of "types and kinds are really the same thing".  To be a little clearer, in modern GHC Haskell (since version 8.0.1, I think), types and kinds are treated uniformly in most of the compiler code.  The compiler makes some effort in error messages to distinguish between "types" and "kinds", depending on whether it's complaining about the type of a value or the type of a type, respectively.

Also, if no extensions are enabled, they are easily distinguishable in the surface language.  For example, types (of values) have a representation in the syntax (e.g., in type signatures), but kinds (of types) are -- I think -- completely implicit, and there's no explicit syntax where they appear.

But, if you turn on the appropriate extensions, the distinction between types and kinds largely disappears.  For example:

{-# LANGUAGE GADTs, TypeInType #-}
data Foo where
  Bar :: Bool -> * -> Foo

Here, Bar is (both a value and) a type.  As a type, its kind is Bool -> * -> Foo, which is a type-level function that takes a type of kind Bool (which is a type, but also a kind) and a type of kind * and produces a type of kind Foo.  So:

type MyBar = Bar True Int

correctly kind-checks.

As @AndrejBauer explains in his answer, this failure to distinguish between types and kinds is unsafe -- having a type/kind * whose type/kind is itself (which is the case in modern Haskell) leads to paradoxes.  However, Haskell's type system is already full of paradoxes because of non-termination, so it's not considered a big deal.


Two questions about complexity class Does $2^{n-1}$ and $2^{n}$ share the same complexity complexity class as exponential named as $O(2^n)$? So the former belongs to $O(2^n)$ even though it's one order lower?
What is the name of the complexity complexity class of $O(n2^{n})$?

Since $2^{n-1} = \Theta(2^n)$, in (CS-style) asymptotic analysis the two functions are equivalent. They have the same "order of growth" from the point of view of asymptotic analysis.

When giving big O upper bounds, we often want to suppress lower-order information. Therefore we sometimes write $\tilde{O}(n)$ instead of $O(n\log n)$ or of $O(n\log^2 n)$, and $\tilde{O}(2^n)$ instead of $O(n2^n)$. Generally speaking, $\tilde{O}$ hides (poly)logarithmic factors, that is, $\tilde{O}(f(n))$ is the same as $O(f(n) \log^{O(1)} f(n))$.

A bound of the form $\tilde{O}(2^n)$ is an exponential bound, since $\tilde{O}(2^n) = O(3^n)$ (indeed, $O((2+\epsilon)^n)$ for any $\epsilon > 0$). In fact, sometimes when saying exponential we also allow functions of the form $2^{n^2}$ in which there is a polynomial in the exponent; and sometimes we mean it in the strict sense of $O(c^n)$ for some constant $c>1$.

Finally, let me mention that complexity classes are about the complexity of problems, not the order of growth of functions. For example, the complexity class $\mathsf{P}$ consists of decision problems solvable in polynomial time. It is not the same as the class of all polynomials.


Where to find practical exercises for algorithm analysis? What is a good book or resource to find practical exercises of analysis of the complexity of concrete algorithm implementations (that is, which asymptotic complexity does a particular code have)?

I'm interested not in solving algorithms but in practising finding out their complexity. I have seen a couple of these kind of exercises in my Discrete Mathematics textbook (Rossen), but I haven't been able to find a good resource to find others.

Textbooks in algorithms are chock full with examples of algorithms, often with analysis. For example, take a look at Erickson's "Algorithms", Dasgupta et al "Algorithms". Looking around for lecture notes will get you a lot of others. Analysis of algorithms requires some specialized techniques, a modern overview is Sedgewick and Flajolet's "Introduction to the analysis of algorithms".


Lower-bounds of a given problem I have the following problem:

  You have n objects that have identical weight except for one that is a
  bit heavier than the others. You have a balance scale. You can place
  objects on each side of the scale and see which collection is heavier.

  Goal is to find the heavier object, with the minimum number of weigh.

I know the best algorithm that can solve this problem. Here is the pseudocode:

function findDiffWeight(L[1:n]){

   if(L.size == 1) return L[1]

   int x = sum(L[1 : n/2])
   int y = sum(L[n/2+1 : n])

   if(x>y)  call findDiffWeight(L[1 : n/2])
   if(y>x)  call findDiffWeight(L[n/2+1 : n])
}

But I am struggling with finding the lower bound for this problem. I don't think that there can be a better algorithm that can solve this in less than logn operations.

However how to prove it?
Could you give me some idea about finding lower bound for this problem?

Your algorithm, which requires $\lceil \log_2 n \rceil$ weighings, is in fact not optimal. This paper proposes an algorithm which uses $\lceil \log_3 n \rceil$ weighings, which is optimal by the argument outlined by Tom van der Zanden. Let's assume for simplicity that $n$ is a power of 3, leaving the general case as an exercise. Suppose we are given $3^k$ objects, which we divide into three groups $X,Y,Z$ of size $3^{k-1}$. We weight $X$ against $Y$. If $X > Y$, we recurse with $X$; if $Y > X$, we recurse with $Y$; if $X = Y$, we recurse with $Z$. After $k$ such steps, we will have zeroed in on a single object.

For the lower bound, suppose that we only do $k$ weighings. There are $3^k$ possible outcomes of this weighings – each one can be either "left side heavier", "right side heavier", or "both have the same weight" – and each of them causes the algorithm to output a definite answer. Since any of the $n$ objects could be the heavier one, we must have $3^k \geq n$. This argument will make more sense after you review the $\Omega(n\log n)$ comparison lower bound for sorting.


Algorithm for graphically spacing items I am developing a chart and graph library and am having trouble developing an algorithm.

**This is not a homework assignment for a student. See my open source project: https://github.com/eddieios/CoreChart

The algorithm is to space the Y axis labels in a given coordinate graphical space. It should space the labels at about 50 pixels apart, but have no less than 5 labels. All data points are assumed to be positive integers. The labels should be multiples of 5 (so as to have nice clean numbers). The last label can be smaller or larger than the maximum possible value, but it should be the closer of the two. The algorithm inputs are 1) the maximum possible value from the chart data, 2) the height of the graphical space. The output is a list of labels and their vertical positions.

For example:

Maximum possible chart value = 79
Height of graphical space = 200

Output would be:

Label: 0, Vertical Position: 0
Label: 20, Vertical Position: 50
Label: 40, Vertical Position: 100
Label: 60, Vertical Position: 150
Label: 80, Vertical Position: 200

I have written the following code (Obj-C). But I'm having trouble handling end-cases. For example, if the maxValue = 39, then the labels are set 5 apart. The optimal case here would be to set labels 10 apart. There's something about I'm deciding how many labels there should be that isn't working for all cases.

int maxValue = 39;
float graphHeight = 259.0f;

int numLevels = (int)(graphHeight / 50.0f);

float offset = (int)(maxValue / (float)numLevels);
offset /= 5;
offset = (float)((int)(offset + 0.5));
offset *= 5;

CGFloat stepY = graphHeight * ((float)offset/maxValue);

for (int i = 0; i <= numLevels; i++) {
    NSLog(@"label %f position %f", i*offset, i*stepY);
}

One possible approach which does not require any hairy arguments is to come up with a "nicety" measure, find a range of offsets, and choose the best one. Usually rounding errors are accounted for by taking a $\pm 1$ (in your case $\pm 5$) modification from the starting point. In your case, you would calculate the nicety measure for both $5$ and $10$, and if your nicety measure is reasonable, choose $10$ over $5$.


How to prove that BFS directed-graph traversal algorithm terminates? How to prove that BFS directed-graph traversal algorithm terminates?
(I copy the pseudocode from here) Input: A graph G and a root v of G.

  procedure BFS(G,v):
      create a queue Q
      enqueue v onto Q
      mark v
      while Q is not empty:
          t ← Q.dequeue()
          if t is what we are looking for:
              return t
          for all edges e in G.incidentEdges(t) do
             o ← G.opposite(t,e)
             if o is not marked:
                  mark o
                  enqueue o onto Q

The only potentially non-terminating construct used here is the while loop. So you need to prove that Q eventually becomes empty.

Q contains vertices from the graph. The only operations that add elements to Q are the enqueue operations. Each adds a single vertex. So proving the termination of the algorithm is equivalent to proving that only a finite number of enqueue operations are performed.

The first call to enqueue at the beginning of the program adds one vertex and marks it. The second call to enqueue adds a vertex that was not marked yet, and the vertex is marked at the same time.

Since a vertex is never unmarked, the set of marked vertices can only grow.

The set of marked vertices is included in the set of all vertices. Note that the graph is be assumed to be finite (in an infinite graph, the search might not terminate). Hence there are at most $|G|$ mark operations where $|G|$ is the number of vertices in the graph. Since each enqueue operation has a corresponding mark, there are at most $|G|$ enqueue operations. Therefore there are at most $|G|$ dequeue operations. Since there is one dequeue operation at each loop iteration, there are at most $|G|$ iterations of the while loop, a finite number.


CTL vs LTL - when a formula satisfy a model I'm trying to understand the difference between LTL and CTL. In particular, i'm trying to understand when a model (a transition system eg. Kripke structure) satisfy a formula.
This is my point of view:

a model satisfy an LTL formula if an only if all its path starting
from its initial state  satisfy the formula
a model satisfy a CTL formula if and only if all of its state satisfy the formula. So i have to check that it is valid for all the
path (or for some path if there's a E quantifier) starting from each
state.  -

Is it correct? can someone help me?

For what it concerns LTL, your understanding is almost correct except that there may be more than one initial states in a transition system.

An LTL formula $\varphi$ holds in state $s$ of a transition system $TS$ if all paths starting in $s$ satisfy $\varphi$.

  The transition system $TS$ satisfies an LTL formula $\varphi$ if if all initial paths of $TS$, paths starting in an initial state $s_0 \in I$, satisfy $\varphi$.

For what it concerns CTL, we have

  The transition system $TS$ satisfies an CTL formula $\Phi$ if and only if $\Phi$ holds in all initial states of $TS$.

Note that, similar to the case in LTL, we are only concerned with the initial states of $TS$ in the semantics of CTL. However, this does not imply that you don't need to check other states of $TS$ against a specific CTL formula $\Phi$. This is both $\Phi$-dependent and checking algorithm-dependent.

For example, the well-known checking algorithm (see the lecture note) is a global model-checking procedure, meaning that it does check for any state $s$ in $TS$ whether $s \models \Phi$, and not just for the initial states. This is because the algorithm is computing fixed points recursively: The result of $s \models \Phi$ may rely on each of $s' \models \Phi$, where $s' \in \text{Post}(s)$ is a direct successor of $s$ in $TS$.

Furthermore, it also checks for any state $s$ whether $s \models \Phi_{sub}$, where $\Phi_{sub}$ is any subformula of $\Phi$, by backward search.


Randomized Algorithm with matrices We have two computers, Comp1 and Comp2, which hold binary matrices A and B of size $n\times n$.

We want to check if the matrices of the computers are identical except for exactly 1 entry.

Comp1 has to send $O(n\log^2n)$ bits to Comp2 and Comp2 should return 0 or 1 (for "no" and "yes" respectively) for the answer.

If the matrices differ by exactly 1 entry, Comp2 will answer 1 ("yes") always.

If they don't differ by exactly 1 entry, Comp2 will answer 0 in probability of at least $1/2$.

Both computers can make any manipulation of their matrix before sending a message. Comp1 of course doesn't have to send a part of its matrix. It can send an answer of computation on its matrix, and Comp2 can make also any calculation it wants before answering.

I've tried to solve it but whatever I tried it failed.

Let's start by assuming that we have two bit vectors $A,B$ of size $m$ instead of two matrices – the matrix structure is unhelpful.

Let $w \in \{\pm1\}^m$ be chosen randomly, and let $\varphi = x \mapsto \langle x,w \rangle \pmod{3}$. If $A,B$ differ on the coordinates in $S$ then
$$ \varphi(A) - \varphi(B) = \sum_{i \in S} (A_i - B_i) w_i \pmod{3}. $$
The distribution of this is the same as the distribution of
$$ \Delta = \sum_{i \in S} w_i \pmod{3}. $$
Suppose $s = |S|$. In order to compute the distribution of $\Delta$, let $\omega$ be a primitive third root of unity, and consider
$$ \left(\frac{\omega + \omega^{-1}}{2}\right)^s = \frac{(-1)^s}{2^s} = \left(\frac{1}{3} + \frac{(-1)^s}{3 \cdot 2^{s-1}}\right) \omega^0 + \left(\frac{2}{3} - \frac{(-1)^s}{3 \cdot 2^{s-1}}\right) \frac{\omega + \omega^{-1}}{2}. $$
For concreteness, here is the probability that $\Delta = 0$ for $s = 0,1,2,\ldots$:
$$ 1,0,\frac{1}{2},\frac{1}{4},\ldots $$
These probabilities tend to $1/3$ exponentially fast, alternately being above and below it. In particular, if $s = 1$ then $\Pr[\Delta = 0] = 0$, and otherwise $\Pr[\Delta = 0] \geq 1/4$.

This suggests the following algorithm, in the case in which the two computers are allowed shared randomness:

Both computers extract $k$ random functionals $\varphi_1,\ldots,\varphi_k$ from the common randomness.
Computer 1 sends $\varphi_1(A),\ldots,\varphi_k(A)$ to Computer 2.
Computer 2 computes $\varphi_1(B),\ldots,\varphi_k(B)$, and outputs Yes if $\varphi_i(A) \neq \varphi_i(B)$ for all $1 \leq i \leq k$.

If the two vectors differ in exactly one location, then Computer 2 always outputs Yes. Otherwise, it outputs No with probability at least $1 - (3/4)^k$. Choosing $k = 3$, we get $1 - (3/4)^3 > 1/2$.

What if the computers are not allowed shared randomness? A standard trick allows us to simulate shared randomness using an overhead of $O(\log m)$. In total, the communication complexity is $O(\log m)$.


Encoding System that Assign Same Number of Bits for Each Character I am trying to get a binary string that has been converted from text of a text file, I am able to get that but the problem is, I need each character to be represented by same number of bits, but that is not what I get (please see the below python code and corresponding output).
For example, character i is represented by 1101001, which is 7 bits long, but character  ! is represented by 100001, which is 6 bits long.

Is there any encoding/decoding system where each character takes same amount of bits?

content = open('a.txt', 'r').read()
test_str = content
# using join() + ord() + format()  ... Converting String to binary

Binary = ' '.join(format(ord(i), 'b') for i in test_str)

#Decimal=int(Binary, 2)

# printing original string
print("The original string is : " + str(test_str))
# printing result
print("The string after Binary conversion : \n" + str(Binary))

Output:

The original string is : Hi! Is there a solution?
The string after Binary conversion :
1001000 1101001 100001 100000 1001001 1110011 100000 1110100 1101000 1100101 1110010 1100101 100000 1100001 100000 1110011 1101111 1101100 1110101 1110100 1101001 1101111 1101110 111111

The usual way to solve this problem is by adding leading zeroes. So i would still be represented by 1101001, while ! will be represented by 0100001.

This is similar to how you digital clock might use 06:40 for 6:40, or 12:05 for 12:5.


In memory paging, how does the S.O. know where the page is in secondary Memory? So every process has its own Page Table, the page table references the frame where the page is in physical memory and also has a valid-invalid bit that tells whether it is in physical memory or in secondary memory.

But how does the S.O. knows exactly where the page is saved when the valid-invalid bit it's off?
Is there another table I'm missing? Or it just does a linear search through the whole SWAP space?

The first thing is that when the page-table entry is invalid you are allowed to use all the other bits in the page-table entry for whatever you want.  So, for example, you could use it to store an offset into the swap space, or a disk block number.

But that's actually not the whole story.  Each process on most operating systems has some kind of segment map that describes for each valid range of logical addresses what's in that range.  Ranges that contain read-only data (such as the code segment, usually) don't need to be swapped.  Instead they can just be reread from the executable that contains them if they are needed again.


Consequences of factoring and discrete log in $P/Poly$ What is the consequence of factoring and discrete log being in $P/poly$?

There appear to be pretty much no interesting consequences, from a complexity-theoretic perspective.  See Consequences of Factoring being in P? on CSTheory.  (Any consequence of factoring being in P/poly would also be a consequence of factoring being in P; but as the answers to that question state, there are basically no known complexity-theoretic consequences to factoring being in P.)

A Google search for "consequences of factoring in P/poly" also turns up Factoring Could be Easy.


Language of CFG: $S \to aS | aSbS | \varepsilon$ I'm trying to prove that the language L generated by the CFG $S \to aS | aSbS | \varepsilon$ is the language $L=\{ w \in \{a,b\}^*: \text{every prefix of $w$ has at least as many $a$'s as $b$'s} \}$.I proved the first inclusion $w \in L(G) \implies w \in L$. I can't prove the vice versa. By induction on the lenght of $w \in L$, I could say:

BASE: $|w|=0$, i.e. $w=\varepsilon$ and it's clear.

IND: suppose the thesis is true whenever $|w|<n+1$ and prove for a word of lenght $n+1$. Given $w \in L$, $w=a_1\dots a_{n+1}$ one has $a_1=a$ since $a_1$ is a prefix of $w$. Thus I can first apply the rule $S \to aS$ or $S \to aSbS$. But what now?

Any suggestion would be helpful. Thanks.

Let $w \in L$ be a word of length $n$. If $n = 0$ then clearly $w \in L(G)$, so suppose that $n > 0$. For $0 \leq i \leq n$, let $\delta_i$ be the difference between the number of $a$s and $b$s in the first $i$ characters of $w$; thus $\delta_i \geq 0$ for all $i$. We now consider two cases:

Case 1: $\delta_i > 0$ for all $i > 0$. In that case $w = ax$ for some $x \in L$. Induction tells us that $x \in L(G)$, and so $w \in L(G)$.

Case 2: $\delta_i = 0$ for some $i > 0$. In that case $w=axby$, where $|axb| = i$ and $x,y \in L$. Induction tells us that $x,y \in L(G)$, and so $w \in L(G)$.


Can languages with infinite strings be recursively enumerable? I am not 100% sure about the definition of recursively enumarable languages. Yes I know how are they defined: There has to exist a Turing machine that accepts all wrods of the language and halts but it does not have to halt on different inputs.

But suppose I have a language consisting of uncountable size with words of infinite length. Will Turing machine halt with a word of infinite length?

Consider a language constisting of all binary strings (I can produce such a set by diagonalization - Cantors rule, for example). Is this language recursively enumarable? If so, can you tell me why? I have not found any definition of this that would explain the behavior of TM with such inputs...

As you state, the standard definition of TM acceptance requires that the TM halts after finite time.

It is still possible for a TM to accept languages that contain infinite words, if they can accept without reading the entire word. For example the language of all (finite and infinite) words that contain at least one $0$ is semi-decidable, since if there is a $0$, the TM will encounter it after a finite amount of time and can then accept the word.
The complement of this language however is not semi-decidable, since it is not possible to read an infinite input in finite time (and it is not possible, in the general case, to know that there is no $0$, without reading the whole input).


What are the characteristics of a $\Theta(n \log n)$ time complexity algorithm? Sometimes it's easy to identify the time complexity of an algorithm my examining it carefully. Algorithms with two nested loops of $N$ are obviously $N^2$. Algorithms that explore all the possible combinations of $N$ groups of two values are obviously $2^N$.

However I don't know how to "spot" an algorithm with $\Theta(N \log N)$ complexity. A recursive mergesort implementation, for example, is one. What are the common characteristics of mergesort or other $\Theta(N \log N)$ algorithms that would give me a clue if I was analyzing one?

I'm sure there is more than one way an algorithm can be of $\Theta(N \log N)$ complexity, so any and all answers are appreciated. BTW I'm seeking general characteristics and tips, not rigorous proofs.

Your archetypical $\Theta(n \log n)$ is a divide-and-conquer algorithm, which divides (and recombines) the work in linear time and recurses over the pieces. Merge sort works that way: spend $O(n)$ time splitting the input into two roughly equal pieces, recursively sort each piece, and spend $\Theta(n)$ time combining the two sorted halves.

Intuitively, continuing the divide-and-conquer idea, each division stage takes linear time in total, because the increase in the number of pieces to divide exactly matches the decrease in the size of the pieces, since the time taken by division is linear. The total running time is the product of the total cost of a division stage multiplied by the number of division stages. Since the size of the pieces is halved at each time, there are $\log_2(n)$ division stages, so the total running time is $n \cdot \log(n)$. (Up to a multiplicative constant, the base of the logarithm is irrelevant.)

Putting it in equations (), one way to estimate the running time $T(n)$ of such an algorithm is to express it recursively: $T(n) = 2 T(n/2) + \Theta(n)$. It's clear that this algorithm takes more than linear time, and we can see how much more by dividing by $n$:
$$ \frac{T(n)}{n} = \frac{T(n/2)}{n/2} + \Theta(1) $$
When $n$ doubles, $T(n)/n$ increases by a constant amount: $T(n)/n$ increases logarithmically, or in other words, $T(n) = \Theta(n \log n)$.

This is an instance of a more general pattern: the master theorem. For any recursive algorithm that divides its input of size $n$ into $a$ pieces of size $n/b$ and takes a time $f(n)$ to perform the division and recombination, the running time satisfies $T(n) = a \cdot T(n/b) + f(n)$. This leads to a closed form that depends on the values of $a$ and $b$ and the shape of $f$. If $a = b$ and $f(n) = \Theta(n)$, the master theorem states that $T(n) = \Theta(n \log n)$.


Average Time Complexity of Two Nested Loops Recently I have had this question in one of my interviews.

You have 1 Million sorted integer, you have a value of $x$, compare each pair in this array and if the addition of two pair is less or equal to $x$ then increment the paircounter.

I have implemented this solution in C++ however I will write pseudocode here(I am sorry I am not very good at pseudo-code)

Initialise ARR_SIZE to 1000000

Initialise index_i to 0

Initialise pairCount to 0

Initialise x to 54321

while index_i is less than ARR_SIZE

  Initialise index_j to index_i+1

    while index_j is less than ARR_SIZE

      if array[index_i]+array[index_j] is less or equal to x

        Increment pairCount

      increment index_j

    endof while

    increment index_x

endof while

At first I said it is $O(n \log n)$ but then with the hint the second loop itself average complexity is O(n/2) so overall I said it would be $O(n\cdot n/2)$ but in Big $O$ notation it would be $O(n)$ because $n/2$ is a constant(although I was not too sure). So what is the average complexity of this overall algorithm?

PS: I know that I could have decreased the complexity by adding an extra else, index_j = ARR_SIZE, which would be $O(N)$ complexity, but I couldn't think of it during the interview.

How to solve it in O(N)

Let's take an example sequence of numbers:

1 3 4 6 7 9

Assume we want the number of pairs (A,B) where A + B <= 12.

First, let's compare the 1st (low element) and the Nth element (high element). 9 + 1 <= 12. So that's one pair. But, as our list is sorted, 9 is the biggest number, if (9, 1) <= 12, for any other number X in the list, (X, 1) <= 12! Meaning, we can just add 6-1 (high index - low index) to the count, we don't need to test those numbers separately. Those are pairs (9,1), (7,1) ... (3,1).

Now we increase our low index to 2, we continue to 3. 9 + 3 <= 12 still, so we add 6-2 to the count. We already added (3,1) in the previous step so this is fine. This adds pairs (9,3), (7,3), (6,3), (4,3).

Again we increase the low index. 9 + 4 > 12. When this happens, we decrease the high index and add nothing to the count.

Now low index is 3 and high index is N-1. 7 + 4 <= 12. Adding 5-3... And so on.

If it is unclear why I add high index - low index every time: take for example the 7 + 4 step. I know that, because I am at high = 7, I had to skip 9 because it was too large. So I don't want to add the pair involving 9. I also know that because I am at low = 4, I already counted the pairs involving 1 and 3 in the previous steps. So I need to add pairs (7,4) and (6,4) in this step.

int count = 0;
for (int low = 0, high = list.Count - 1; high >= 1 && low != high; )
{
    if (list[high] + list[low] <= x)
    {
        count += high - low;
        low++;
    }
    else
    {
        high--;
    }
}

Regarding constants and complexity

Judging by your comment, you are confused about what is ignored and why. First, n/2 is not a constant because it depends on n. As n grows, n/2 grows, so it is clearly not constant. The constant that is ignored in n*n/2 is 1/2, and what remains is n*n.

So the complexity is N^2. The actual number of inner loop executions is N^2/2, but this is still O(N^2). The fact you brought up in your comment that the inner loop will run 50 times when 10^2 would indicate 100 times is irrelevant, here's why:

Constants are not meaningful unless they are extremely large (a 2^32 constant because your algorithm tests every 32 bit integer) or you calculate the average case cycle count on a reference architecture.

Otherwise, actual speed depends on the language used, on how many instructions each operation actually performs, prediction, caching, pipelining, etc and it is difficult to compare the constants of 2 different algorithms, just outright counting syntactic constructs is very misguided.

2X operations may run faster than X operations if what is being done, how and in which order is different. So until you dig a bit deeper and look into the things I mentioned above, counting operations in a high level language is pure wishful thinking. It is a sign of a questionable CS teaching in my opinion because it teaches a nonsense model of code execution, instead of using a valid one, but on a simple reference architecture (like Knuth does), if you insist on counting operations.

Consider these two pieces of code:

for (int j = 0; j < N - 1; j++)
    for (int i = j + 1; i < N; i++)
        r += A[i][j];

And:

for (int i = 0; i < N; i++)
    for (int j = 0; j < N; j++)
        r += A[i][j];

The first example has N^2 / 2 inner loop repetitions. The second example has N^2 inner loop repetitions. The inner loop body is the same. But the second one is actually much faster on a standard computer (in fact, a smart compiler with certain settings might rewrite your code if you write the first one - so if you test this, turn off optimization)! This is because the second one has much better memory access locality - it accesses the memory locations in order, while the first one jumps around. This causes a much bigger difference in speed than running the loop twice as many times does. And this is just one of many things which affect run speed and are not immediately visible in the code.

Second example, two pieces of code:

for (int i = 0; i < N - 1; i++)
{
    for (int j = i + 1; j < N; j++)
    {
        int a = A[i][j] * 3;
        a += 5;
        r += a;
    }
}

And:

for (int i = 0; i < N; i++)
    for (int j = 0; j < N; j++)
        r += A[i][j];

Can you tell me which one has a bigger "constant"? Again, the first inner loop runs 1/2 as many times as the second one. But the first one has 3 lines of code inside the inner loop, while the second one has just one. On my machine, the first one is faster. By what factor? I have no idea (I could measure it, but I can't tell you by looking at the code). If you decide on a constant A for the first and B for the second program by looking at the code, A/B will probably not be anything like the ratio of actual execution times, making the constants meaningless.

So the 1/2 constant is meaningless. Whether a program runs twice faster than some other program depends on so many things that it is not productive to account for small constants on such a superficial level.

By the way, you have a bug in your program. The outer loop condition needs to be less than ARR_SIZE - 1 or you are setting index_j to ARR_SIZE in the last outer iteration, and as your indices are 0-based you are reading from beyond the end of your buffer.


Efficient simulation of an NFA, while preserving the paths to the accept states The standard way of simulating an NFA on a computer (for implementing regex engines etc) is to construct a DFA that accepts the same language. Otherwise you get problems like exponential blowup.

However, for my purpose I need to know which paths the NFA went through for accepted words. This is obviously not trivial if I simply use the subset construction method. The NFA could also have $\epsilon$ transitions.

Of course, any such simulation could have a bad worst-case, in which there are a humongous amount of ways that the automaton could accept a given word. However, it'd be nice to have some sort of algorithm that runs, in, say, $O(m+n)$ for a word of length $m$ that the NFA has $n$ ways of accepting.

Is there any efficient way to do this?

There is no need to construct the DFA. Instead, you can construct a dynamic programming table which answers the question "the NFA could be at state $s$ after reading the $k$th prefix of the word" (the parameters are both $s$ and $k$). In order to efficiently fill this table in the presence of $\epsilon$-transitions, you need to compute ahead of time the transitive closure of the $\epsilon$-transitions. As you fill the table, you can include data that will allow you to reconstruct at least some of the accepting paths (or all of them, if you insist, though it will be more tricky to handle the $\epsilon$-transitions). The running time, however, won't be linear but more like $O(q^2m)$, where $q$ is the number of states; perhaps you could optimize this further for sparse NFAs, but probably not to $O(m+n)$.


PDA to accept language with more a's than b's and c's My question is similar to this one. I was wondering if a PDA exists, that accepts any words containing a's, b's and c's in a random order, where the total amount of a's is higher than the amount of the b's and higher than the amount of c's, so for example the word "abcacba" would be accepted.

Note the language where the number of $a$'s is larger than both the number of $b$'s and the number of $c$'s is not context-free, and cannot be accepted by a PDA.

Formally the language can be written as $L = \{ x\in\{a,b,c\}^*\mid \#_a(x) > \#_b(x) \text{ and }\#_a(x) > \#_c(x) \}$.

Intuitively we cannot recognize $L$ using a single pushdown as the count of $a$'s has to be used twice, but in comparing with the number of $b$'s and the number of $c$'s. That is no formal argument, there might be clever tricks avoiding the direct comparison of numbers. Yet there is a possible water tight proof, it uses the pumping lemma for context-free languages.


Trying to understand this Dynamic Programming solution The problem is as follows.

Minimize the sum of absolute differences between a matching of $n$ values from two sets, $A=\{a_1,a_2,\cdots, a_n\}$ and the set $B=\{b_1, b_2,\cdots, b_m \}$, with $n\leq m$.

So, we can use two list of indexes $\ I$, $J$, such that $I\subseteq [n]$,  $J\subset [m]$, and $|I|=|J|=n$. The notation is $[m] = \{1,2,3,\cdots, m\}$.

Therefore, our goal reduces to:

$$ \min_{k=1,2,\cdots, n}  \{|a_{i_k} - b_{j_k}|\ : i_k\in [n],\ j_k\in J\}.$$

I found the problem above in this question (in other words) and trying to understand how the answer provided there, it attempts to solve the problem with dynamic programming.

This is what I understand:

I believe we are building two indexes and are pairing them.
We first sort boys by height
Somehow we then construct a match, but it's not greedy, is it? it utilizes calculating the sum of the absolute difference in height. How was the pairing constructed?

This paragraph is key and I would love to understand it but I don't get it:

you can use dynamic programming to find the optimal matching by building up
optimal matchings that have the first j boys in sorted height order all
paired up somehow among the first k girls in sorted height order (where
j≤k), and using the optimal matchings for the values (j,k−1) and (j−1,k−1)to
decide the optimal matching for the values (j,k), based on whether you pair
up boy j with girl k or not.

So, the question is how the dynamic programing method is working here based on the answer given and pseudo code of the solution it would be helpful.

We are going to build up the matching with a top-bottom approach. Before proceed your intuition is correct. We need two indexes for our solution, that it would be a recursive function $f$ based on a index $i\in [n]$ and index $j\in[m]$.

This is the definition for $f$.
$$f(i,j):= \text{The optimal* matching between the elements from }\{a_1, a_2, \cdots, a_i \}\text{ with $i$ elements from } \{b_1, b_2, \cdots, b_j\}.$$

The first thing as with other recursive methods, is establish the well-defined bases cases of the recursion. These are the following.
$$
\begin{align}
f(i,1) &= |a_i - b_1|\ \ \ \forall i\in [n]\\
f(1,j) &= \min\ \{\ f(1, j-1),\ |a_1 - b_j|\ \} \ \ \ \forall j\in [m]\\
\end{align}
$$
These are when we have just one element from $B$ and just one element from $A$, respectively.

Thinking like $f$ is working yet as we expected, we can define it as follows with $i\in [n]$ and $j\in [m]$.

$$
f(i,j) = \min \ \begin{cases}
f(i-1, j-1) + |a_i - b_j| & \text{we match $a_i$ with $b_j$}\\
f(i, j-1)&\text{we won't pair $a_i$ with $b_j$}
\end{cases}.
$$

Be aware in the recursion for the corner cases, these are when $f$ is not defined. They are  when $i$ or $j$, or even both are less than or equal to zero, for these cases, we are gonna say, $f(i,j) = \infty$.

So, what is the answer (?). Because, we are using top-bottom approach and based on the definition of $f$, after compute $f(n, m)$, it should give us the answer. Notice, that this way is one of many methods using dynamic programming, and sincerely, it is almost the same as the solution your provided in the link, but here it is just more explicit.

Maybe like a pseudocode, we can do this in Python with the following implementation.

@memo
def f(n, m):
    global a, b
    if m <= 0 or n <= 0:
        return float('inf')
    if n == 1:
        return min(f(1, m - 1), abs(a[0] - b[m - 1]))
    if m == 1:
        return abs(a[n-1] - b[0])
    x = f(n - 1, m - 1) + abs(a[n - 1] - b[m - 1])  # take b_m
    y = f(n, m - 1)  # dont take b_m
    return min(x, y)

print f(len(a), len(b))

My @memo decorator is the following, and is the key of a technique that involved dynamic programing, caching o memoization.
    from functools import wraps
    def memo(func):  # memoization
        cache = {}

    @wraps(func)
    def wrap(*args):
        if args not in cache:
            cache[args] = func(*args)
        return cache[args]
    return wrap


Non-deterministic Finite Automata | Sipser Example 1.16 I am working through the Sipser Book (2nd edition) and came across this example, which I do not understand. In the book it states that this NFA accepts the empty string, $\epsilon$.

Could someone run me through why this is the case?

My understanding is that $\epsilon$ will move to $q_3$ which is not an accept state.

You are confusing $\epsilon$ with a letter. It's not a letter! It's just the empty string.

Let us consider a slightly more general model, "word-NFA". A word-NFA is like an NFA, but each transition is labeled with an arbitrary word. We say that the word-NFA accepts a word $w$ if there is a walk from an initial state to a final state such that if we concatenate the edge labels across the walk, we get $w$. In symbols, a word-NFA accepts $w$ if there is a sequence of transitions
$$
q_0 \stackrel{w_1}\to q_1 \stackrel{w_2}\to q_2 \stackrel{w_3}\to \cdots \stackrel{w_n}\to q_n
$$
such that:

$q_0$ is an initial state. (The usual model only allows one initial state, but we can relax that requirement.)
$q_n$ is a final state (also called an accepting state).
Each transition $q_{i-1} \stackrel{w_i}\to q_i$ corresponds to a transition of the word-NFA.
$w = w_1 \ldots w_n$.

An NFA is a word-NFA in which all transitions are labeled by letters (i.e., words of length exactly 1), and an $\epsilon$-NFA is one in which all transitions are labeled by letters or $\epsilon$ (i.e., words of length at most 1). Usually we also require that there be a unique initial state.

A word-NFA accepts $\epsilon$ if there is a sequence of transitions
$$
q_0 \stackrel\epsilon\to q_1 \stackrel\epsilon\to \cdots \stackrel\epsilon\to q_n
$$
such that $q_0$ is an initial state, $q_n$ is a final state, and all transitions are valid. In particular, if some state is both initial and final, then the word-NFA accepts $\epsilon$ (this correponds to $n = 0$).


What is the big-O (worst-case upper bound) for time and space requirement of the different Chomsky classes? Everybody knows the Chomsky-hierarchy for describing formal languages and big-O notation for describing time and space complexity of a function.

We know, that each class in the Chomsky-hierarchy corresponds to an atomata, that can recognize any language in the corresponding class.

The question is: What is the worst-case time and space complexity of these automatas given any language of the above class?

What I found out already:

Chomksy-3 class, the regular languages can be recognized by an FSM of n-states where n is a finite number. IMO this makes it require O(n) space and O(l) time, where l is the length of the input.

Chomsky-2 class, the context free languages can be recognised by a Non-deterministic pushdown automaton. CYK algorithm run $n^3 * G$ where n is the length of the input and G is the number of rules in the grammar in Chomsky Normal form.

But how much space needed? Do we have better bounds?

Chomsky-1 class, the context sensitive languages can be recognised by a Linear-bounded non-deterministic Turing machine.

This class seem to depend on the length of the context to be recognised. Maybe in exponential time.

Chomksy-0 class, the recursively enumerable languages can be recognised by Turing machine.

Can anything stated for this class? If not, why?
Maybe the $P \stackrel{?}{=} NP$ problem is related.

Are the above statements true?

Please give citations to your answer!

Regular languages can be accepted in linear time and constant space.

Valiant's algorithm parses arbitrary context-free languages in time $O(n^\omega)$, where $\omega$ is the matrix multiplication constant. Deterministic context-free languages (which are those used in practice) can be parsed in linear time.

Context-sensitive languages are identical to the class $\mathsf{NSPACE}(n)$. I'm not aware of any non-trivial time upper bound.

Recursively enumerable languages cannot be parsed in general, since $\mathsf{R} \neq \mathsf{RE}$.

The $\mathsf{P}\stackrel?=\mathsf{NP}$ question is completely unrelated. Unfortunately, the undergraduate curriculum usually spends much more time on the old-fashioned Chomsky hierarchy compared to more modern hierarchies afforded by computational complexity theory.


Egg dropping puzzle - clarification of problem statement I was trying to understand the egg dropping puzzle. The problem objective is:

What strategy should you adopt to minimize the number egg drops it takes to find the solution?. (And what is the worst case for the number of drops it will take?)

I understand we want to minimize the egg drops, but what does this worst case number of drops infer to. This makes me more confuse. Can anyone explain its meaning.

Imagine this as a game of two players: the experimenter vs. nature.

The egg breaking limit is not chosen in advance.
Instead, the players together form statements about its possible values, all the way until only one value remains.

On each turn, the experimenter chooses the floor from which to drop the egg.
After that, the nature chooses whether the egg actually breaks or not.

Of course, with some moves of the experimenter, nature can't choose because the previous statements already determine the outcome.
However, note that a good strategy for the experimenter does not make such redundant moves.

With such formulation, the "worst case" here is equivalent to the game-theoretic "if nature plays optimally", and "minimizing the number of moves in the worst case" to "if both play optimally".


Differences between $\text{BPP}$ and $\overline{\text{BPP}}$ vs $\text{co-BPP}$ Is $\overline{\text{BPP}}$ different from $\text{co-BPP}$? I am having trouble understanding the "co" part of these complexities.

I think yes and here is what I think: It seems given that $\text{BPP}$ is the class of languages decided by PTMs with error probability 1/3, then this is equal to $\text{co-BPP}$. But $\overline{\text{BPP}}$ is the class of languages decided by PTMs with success probability 1/3. So $\overline{\text{BPP}}$ is different from $\text{co-BPP}$.

Am I correct on these definitions?
Thanks!

$\newcommand{\co}{\mathsf{co}\text{-}}\co A=\left\{L\subseteq \Sigma^* \mid \overline{L}\in A\right\}$

Saying that the class $A\subseteq P\left(\Sigma^*\right)$ is closed under complement is equivalent to saying $A=\co A$ (verify).

Note that $\overline{A}$ is not the same as $\co A$, here we're simply taking all the languages outside of $A$, and we require nothing about the complement of these languages.

$\newcommand{\BPP}{\mathsf{BPP}}\BPP$ is closed under complement, since we can simply flip the answer (verify yourself that this works), so $\co \BPP=\BPP$.

$\overline{\BPP}$ however is a whole new story, and even contains all undecidable languages, since $\BPP\subseteq \mathsf{PSPACE}$.


Complexity of algorithm partitioning input into parts of size $n/100$ and $99n/100$ Merge sort always divides array of size $n$ into parts each of size $n/2$. It then merges these two parts. So its recurrence relation is $T(n)=2T(n/2) + O(n)$. What if there is an algorithm which is guaranteed to partition the array into two parts of sizes $n/100$ and $99n/100$? So its recurrence relation will be $T(n)=T(n/100)+T(99n/100)+O(n)$.
It feels like this relation is not as good as merge sort in terms of time. I think that such an algorithm's worst case time complexity should be between that of $O(n^2)$ and $O(n\log n)$.
I have two questions:

Is $n/2$ and $n/2$ partitioning the most optimal or $n/100$ and $99n/100$ partitioning also asymptotically optimal?
How to solve the recurrence relation $T(n)=T(n/100)+T(99n/100)+O(n)$?

The simplest way to answer this question is using the Akra–Bazzi theorem, a vast generalization of the Master theorem. Using the Akra–Bazzi theorem, you can show that the solution of the recurrence $T(n) = T(\alpha n) + T((1-\alpha) n) + O(n)$ is $T(n) = \Theta(n\log n)$ for all constant $\alpha \in (0,1)$.
You can also use a recursion tree. This is a tree in which the root is $n$, and any node whose value is $m \geq n_0$ has two children labeled $\alpha m$ and $(1-\alpha) m$. The total cost of the algorithm is proportional to the sum of all values in the tree.
Suppose that $n$ is very large, and consider the first few levels of the tree:

The first level consists of the root, labeled $n$.
The second level consists of two nodes, labeled $\alpha n$ and $(1-\alpha) n$.
The third level consists of four nodes, labeled $\alpha^2 n$, $\alpha(1-\alpha) n$, $\alpha(1-\alpha) n$, and $(1-\alpha)^2 n$.

You can see that the labels in each level sum to $n$. At some point this will stop happening because the tree has leaves when the value drops below $n_0$, but the first $\min(\log_{1/\alpha} (n/n_0), \log_{1/(1-\alpha)} (n/n_0))$ are complete. In contrast, each level sums up to at most $n$, and there are at most $\max(\log_{1/\alpha} (n/n_0), \log_{1/(1-\alpha)} (n/n_0))$ levels. Putting the two together, we see that the complexity is $\Theta(n\log n)$.

With more effort we can find the dependence of the complexity on $\alpha$. For concreteness, let us assume that the recurrence is $T(n) = T(\alpha n) + T((1-\alpha) n) + n$, and consider $S(n) = T(n)/n\log n$, which satisfies the recurrence
$$
S(n) = \frac{\alpha n \log (\alpha n)}{n \log n} S(\alpha n) + \frac{(1-\alpha) n \log ((1-\alpha) n)}{n \log n} S((1-\alpha) n) + \frac{1}{\log n}.
$$
Suppose that $S(n) \longrightarrow C$. Substituting $S(n) = C$ in the recurrence, we obtain
\begin{align}
C &= \frac{\alpha n \log (\alpha n)}{n \log n} C + \frac{(1-\alpha) n \log ((1-\alpha) n)}{n \log n} C + \frac{1}{\log n} \\ &=
\alpha C + (1-\alpha) C + \frac{\alpha \log \alpha C + (1-\alpha) \log (1-\alpha) C + 1}{\log n} \\ &=
C + \frac{1 - h(\alpha) C}{\log n},
\end{align}
where $h(\alpha)$ is the entropy function. Thus, if $S(n) \longrightarrow C$ then $C = 1/h(\alpha)$, which is indeed minimized when $\alpha = 1/2$ and symmetric with respect to $\alpha$ and $1-\alpha$.
Here is another way to see where $h(\alpha)$ is coming from. Consider a random element from the original array. With probability $\alpha$, it belongs to the first half of size $\alpha n$, and with probability $(1-\alpha)$ it belongs to the second half of size $(1-\alpha) n$. In this way, we can trace what happens to the element until it reaches a subarray of size $n_0$ or less. The contribution of this element to the total complexity is the depth at which the terminal subarray is reached, so we are interested in the expected depth of this process.
Let $N_t$ be the size of the subarray at time $t$. Thus $N_0 = n$, and if $N_t \geq n_0$, then $N_{t+1} = \alpha N_t$ with probability $\alpha$, and $N_{t+1} = (1-\alpha) N_t$ with probability $(1-\alpha)$. It is easy to check that $\mathbb{E}[\log (N_t/N_{t+1}))] = h(\alpha)$. Since $\log(N_t/N_0) = \sum_{s=0}^{t-1} \log(N_{s-1}/N_s)$, linearity of expectation shows that $\mathbb{E}[\log (N_t/n_0)] = t h(\alpha)$ (assuming the the process continues forever, even after reaching size $n_0$), and so the expected time to hit a leaf is $\log(n/n_0)/h(\alpha)$.


CFG Equivalent of regular expressions So I was wondering something about the Chomsky hierarchy.

DFAs (and NFAs) accept regular languages, while NPDAs accept context-free languages.

Right-regular or left-regular grammars produce regular languages, while context-free grammars produce context-free languages.

Regular expressions represent regular languages - but is there a context-free equivalent?  i.e. is there some additional term we could allow to appear in a regular expression such that regular expressions with that functionality now represent context-free languages?

A (rather technical) answer, where star-operator is replaced by least fixed point (equivalent to recursive formulation as in CFG) is given by our cstheory cousins: Does there exist an extension of regular expressions that captures the context free languages?

The author (Neel Krishnaswami) of that answer does not know an original source of his construction, but a later comment by Tim Schaeffer refers to the 1973 book Formal Languages by Arto Salomaa. In chapter VI.11 Salomaa introduces regular-like expressions. That book might not be in your possession, but in turn refers to A characterization of context-free languages, Journal of Computer and System Sciences, 1973, by Jozef Gruska, which is open access.

The operator Gruska considers is the following, I loosely quote from his paper. Let $\sigma$ be a symbol and $L,L_1$ be languages.
The $\sigma$-substitution of $L_1$ into $L$, denoted by $L \overset{\sigma}{\uparrow}L_1$ is defined by

$$ L \overset{\sigma}{\uparrow}L_1 = \{ x_0 y_1x_1 \dots x_{k-1} y_k x_k \mid x_0 \sigma x_1 \dots x_{k-1} \sigma x_k\in L, \text{no $\sigma$ in }x_i, y_i\in L_1 \}.$$

After noting that he operation $\overset{\sigma}{\uparrow}$ is associative one defines the $\sigma$-iteration as

$$ L^\sigma = \{z \mid z\in L \cup L\overset{\sigma}{\uparrow}L \cup L\overset{\sigma}{\uparrow}L\overset{\sigma}{\uparrow}L \cup \dots \text{ does not contain an occurrence of } \sigma \}.$$

Note that if we have only a single variable, like $S\to aSbS \mid \lambda$ then this substitution closure $\{aSbS, \lambda\}^S$  is indeed the language generated by the grammar.


Intuition behind eigenvalues of an adjacency matrix I am currently working to understand the use of the Cheeger bound and of Cheeger's inequality, and their use for spectral partitioning, conductance, expansion, etc, but I still struggle to have a start of an intuition regarding the second eigenvalue of the adjacency matrix.
Usually, in graph theory, most of the concepts we come across of are quite simple to intuit, but in this case, I can't even come up with what kind of graphs would have a second eigenvalue being very low, or very high.
I've been reading similar questions asked here and there on the SE network, but they usually refer to eigenvalues in different fields (multivariate analysis, Euclidian distance matrices, correlation matrices ...).
But nothing about spectral partitioning and graph theory.

Can someone try and share his intuition/experience of this second eigenvalue in the case of graphs and adjacency matrices?

(Disclaimer: This answer is about eigenvalues of graphs in general, not the second eigenvalue in particular. I hope it is helpful nevertheless.)

An interesting way of thinking about the eigenvalues of a graph $G = (V, E)$ is by taking the vector space $\mathbb{R}^n$ where $n = |V|$ and identifying each vector with a function $f\colon V \to \mathbb{R}$ (i.e., a vertex labeling). An eigenvector of the adjacency matrix, then, is an element of $f \in \mathbb{R}^n$ such that there is $\lambda \in \mathbb{R}$ (i.e., an eigenvalue) with $A f = \lambda f$, $A$ being the adjacency matrix of $G$. Note that $A f$ is the vector associated with the map which sends every vertex $v \in V$ to $\sum_{u \in N(v)} f(u)$, $N(v)$ being the set of neighbors (i.e., vertices adjacent to) $u$. Hence, in this setting, the eigenvector property of $f$ corresponds to the property that summing over the function values (under $f$) of the neighbors of a vertex yields the same result as multiplying the function value of the vertex with the constant $\lambda$.


What is the exact meaning of a Predicate, decidability and computability? In the Computability, Complexity and Languages book written by Davis in page 5 he defines a predicate as:

  By a predicate or a Boolean-valued function on a set $S$ we mean a total function $P$ on $S$ such that for each $a \in S$, either $P(a) = True$ or $P(a)=False$.

So every predicate is a total function. in Page 30 he says:

  A given partial function $g$ (of one or more variables) is said to be partially computable if it is computed by some program
  A function is said to be computable if it is both partially computable and total.

in page 68 he says:

  Theorem 2.1. $HALT(x, y)$ is not a computable predicate.

Since every predicate is total, so the only reason which causes this theorem to be true is that there must be no program that computes $HALT(x,y)$, it means $HALT(x,y)$ is not a partially computable, if it was then it would be computable because it is total!

Not that in page 76 the writer says:

  Note that a partially computable predicate is necessarily computable

In this link I found two statements that seems to be a contradiction.

  In mathematics, logic and computer science, a formal language is called recursively enumerable (also recognizable, partially decidable, semidecidable or Turing-acceptable) if it is a recursively enumerable subset in the set of all possible words over the alphabet of the language, i.e., if there exists a Turing machine which will enumerate all valid strings of the language.
  The Halting problem is recursively enumerable but not recursive.

I know that decidability terminology is used for sets but computability terminology  is used for languages. if we can say that recursively enumerable sets are partially computable (= partially deciable) then Since Halting problem is r.e. so it is partially computable. If it is partially computable and since it is total so Halting problem must be computable !!!

There is an unfortunate clash of terminology here. Before exposing it, let me just mention that decidable and computable are synonyms. You mention several concepts, including:

Partially computable: A partial function which is computed by some program that doesn't necessarily always halt.
Partially decidable (terminology I personally have never heard): A language (i.e. set of words) that is enumerated by some program.

These are different concepts. Partial computability is a property of (partial) functions. Since languages can also be viewed as predicates, partial computability can also apply to languages, though this is somewhat misleading, since a partially computable predicate is always computable.

Partial decidability, usually known by some of the other names you mention, is a property of languages. Partial decidability can also apply to predicates by considering the language of all input tuples satisfying the predicate.

The halting problem itself has many variants, of which you mention two:

The halting predicate $HALT(x,y)$, true if the program encoded by $x$ halts on input $y$.
The halting problem, which is the language of all pairs $(x,y)$ such that the program encoded by $x$ halts on input $y$.

The halting problem is a language whose corresponding predicate is the halting predicate. Both are partially decidable but not partially computable or computable.


Are Bad churches inhabited? In type theory, some inductively defined data types allow you to prove absurdity. For example

type Bad a = MkBad (Bad a -> a)
extract : Bad a -> a
extract val@(MkBad f) = f val
absurd : a
absurd = extract (MkBad extract)

Now, when you church encode this datatype it leads to

badChurch : Bad a -> (forall X. ((X -> a) -> X) -> X)
badChurch _ = ?

Now, it seems to me that this function type is actually uninhabited and my intuition says that it could be proven using Theorems for free but alas I can't find a way to actually do that.

The deeper question is this: Would showing the existance of a church encoding be enough to prove consistency of a datatype? And contrary; Are there datatypes whose church encoding is uninhabited with which you can not prove absurdity?

Pretend you want to check if you allow a datatype in your language. Would it be enough to check if the type's church encoding exists to safely allow the type in your language?

No, it is not sufficient to check that the 'Church encoding' is uninhabited.

Consider the type:

$$\mathsf{data} \;U = L\ (U → U)\;  |\; A\ U\ U$$

The idea is that $U$ is the type of untyped lambda terms. If you allow this as a data type into your language, it causes problems. At the very least, you can write loops in $U$ if you are allowed to inspect its values by case analysis.

δ : U -> U
δ (L f) = f (L f)
δ x = x

ω : U
ω = δ (L δ)

-- ω ==> δ (L δ) ==> δ (L δ) ==> ...

If you are also allowed to do recursion on the presumption that $U$ is well-founded, these loops leak into every other type.

However, the 'Church encoding' of $U$ is not uninhabited:

$$U' = ∀ R. ((R → R) → R) → (R → R → R) → R$$

In fact, this is a somewhat well-known representation of untyped lambda terms in a sort of higher-order abstract syntax. You can write down (an encoding of) any untyped lambda term you want:

$$id : U' = λ L. λA. L (λ x. x)$$
$$comp : U' = λ L. λA. L (λ g. L (λ f. L (λ x. A\ g\ (A\ f\ x))))$$
$$δ' : U' = λ L. λ A. L (λ x. A\ x \ x)$$
$$ω' : U' = λ L. λ A. A\ (L (λ x. A\ x\ x))\ (L (λ x. A\ x\ x))$$

So, this encoding is certainly inhabited. But, the reason I was using scare quotes earlier is that is clearly still not what we expect the original data type to mean, so it's rather unclear whether this should be considered the Church encoding of that data type. For instance, you will be unable to exhibit the equivalence:

$$U' \cong (U' → U') + U' × U'$$

which is expected of the data definition. Also, $U'$ is arguably a more faithful representation of the syntax of untyped lambda terms, because all we can do is abstract and apply, as those are the only things we know about the abstract $R$ type. $U$, at least presuming the usual semantics of data, allows us to write, "exotic terms," which is what δ and ω actually are (note that they're not the same as $δ'$ and $ω'$). And this makes sense, because these exotic terms are what allow us to write loops using the data type, whereas $U'$ is a perfectly acceptable System F type, and System F is strongly normalizing.

So, clearly, some more thorough check is necessary than mere habitation. You must check that the 'encoding' actually models the properties you're going to allow your data type to have.


What terms type systems exclude? I understand type systems like the simply typed lambda calculus, system F and the calculus of constructions include a different subset of all lambda terms. But what, precisely, are the terms each of those systems include/exclude? Is it possible to express the intuition behind the criteria with words?

In the simply-typed lambda calculus, the type of a function must be fully specified, even when it's irrelevant. A trivial example is the identity function: in the lambda calculus, it's $\lambda x.x$; in the simply-typed lambda calculus, there isn't a single identity function but rather a family of identity functions $\lambda x:T. x$ for every type $T$. This means that the simply-typed lambda calculus has no polymorphism. If you think about data structures, more concrete examples come up — you can't write, say, a generic function like list reversal, you have to write it all over again for each type of list elements. You can't even write basic primitives like nil and cons, only typed-indexed primitives $\texttt{nil}_T$ and $\texttt{cons}_T$.

To give a concrete example in the pure lambda-calculus (without constants), natural numbers can be encoded as Church numerals in the untyped lambda calculus:
$$\begin{align}
  0 &= \lambda f. \lambda x. x \\
  1 &= \lambda f. \lambda x. f x \\
  2 &= \lambda f. \lambda x. f (f x) \\
  &\ldots
\end{align}$$
In the simply-typed lambda calculs, there is a separate family of Church numerals for each type:
$$\begin{align}
  0_T &= \lambda f : T\to T. \lambda x : T. x \\
  1_T &= \lambda f : T\to T. \lambda x : T. f x \\
  2_T &= \lambda f : T\to T. \lambda x : T. f (f x) \\
  &\ldots
\end{align}$$
You can't compose Church numerals of different types, which makes it difficult to use the same number for different things.

In the Hindley-Milner type system (which I'm including because it's an important step), polymorphic functions are possible, but with restrictions. Hindley-Milner requires a new syntactic form in addition to variables, application and abstraction: the let binding $\texttt{let } x = M \texttt{ in } N$. If all or part of the type of $M$ is irrelevant then it can be left as a variable, and the variable $x$ has not a type but a type scheme of the form $\forall \alpha_1,\ldots,\alpha_k, T$ where the $\alpha_i$ are type variables and the type expression $T$ can contain these variables. For example, it is possible to define the identity function once and for all:
$$
\texttt{let } \texttt{id} : (\forall \alpha, \alpha\to\alpha) = (\lambda x:\alpha. x) \texttt{ in } \ldots
$$
Similarly one can define Church numerals and (more practically) data structure manipulation (e.g. of lists, arrays, etc.) without having to duplicate the definitions for every type of element.

This form of polymorphism is known as parametric polymorphism; HM does not allow functions to behave differently depending on the types of their arguments. This allows proving properties of programs, such as “a function of type $\forall \alpha, \texttt{list}(\alpha) \to \texttt{int}$ only depends on the length of the list and not on the value of the elements”. This is known as “theorems for free” after the famous paper by Phil Wadler. An example of a practically useful function that cannot be expressed in HM is $\ge : \forall \alpha, \alpha \to \alpha \to \texttt{bool}$ which defines a total order — by parametricity, any such function is consant or non-terminating. More generally, HM cannot express ad hoc polymorphism (also known as generic programming in type theoretist circles, but beware that “generics” means parametric polymorphism in OOP circles).

In System F, functions can be parametrically polymorphic with no restrictions. Any lambda term can have universal quantifiers on types, which removes the distinction between $\lambda$ and $\texttt{let}$. Ad hoc polymorphism is still impossible (parametricity results still hold). System F allows more polymorphism than HM, at the expense of type inference (which is relatively easy for HM, and undecidable in System F).

Above I gave examples of programs that can't be expressed in HM and can't be expressed in System F either. Let me now give examples of programs that can be expressed in System F but not in HM. Simple examples are a bit more subtle. One simple example is the lambda term $\lambda x. x \, x$. What does it take to type it? In order for $\lambda x:T. x\,x$ to be well-typed, $T$ must satisfy the equations $T = T_1 \to T_2$ (for the occurrence of $x$ in function position) and $T_1 = T$ (for the occurrence of $x$ in application position). In Hindley-Milner, this is impossible, because types have a simple tree structure and a type satisfying these equations would have to be infinite. In System F, this term can be typed by breaking the recursion with a type abstraction:
$$
\Delta_F = \lambda x: (\forall \alpha, \alpha\to\alpha). x \, (\forall \alpha, \alpha\to\alpha) \, x
$$
While this may look of theoretical interest only, this is of highly practical interest when generalized to data structures. The term $\Delta$ condenses the wish for a single object to behave in a polymorphic way. System F, unlike HM, can express objects with polymorphic methods.

Besides ad hoc polymorphism, an important class of terms that still cannot be typed in System F is non-terminating functions. While $\Delta = \lambda x. x \, x$ can be typed in System F, the “utmost” non-terminating term $\Delta \Delta$ cannot be typed.

System F expands the simply-typed lambda calculus by adding terms depending on types. Other directions for expansion are types depending on types, and types depending on terms. These three dimensions for expansion are known as the Barendregt cube or lambda cube. (This should actually be a hypercube, but the lambda calculus itself is built on terms depending on terms, and the half of the hypercube that doesn't have terms depending on terms isn't studied often.)

Types depending on types allow generic data structures to be defined. For example, although HM is sufficient to write polymorphic functions on lists, defining a list type operator requires more than a basic Hindley-Milner or System F type system: it requires the ability to parametrize the types of lists by the type of their elements.

Types depending on terms are known as dependent types. Dependent types are very powerful, at the expense of making type checking more difficult and requiring often large annotations. An example of constraint that requires dependent types is tracking array lengths through a type family $\texttt{array} : \mathsf{Type} \to \mathbb{N} \to \mathsf{Type}$, allowing the typing of functions such as
$$
\texttt{concatenate}_T : \forall n:\mathbb{N}, \forall m:\mathbb{N}, \texttt{array}\,T\,n \to \texttt{array}\,T\,m \to \texttt{array}\,T\,(n+m)
$$

The calculus of constructions includes all possible abstractions (terms depending on terms or types, types depending on terms or types). Even in the calculus of constructions, neither ad hoc polymorphism nor non-terminating functions are possible.


Why do we use RSA if it is not secure against chosen ciphertext attack? I am reading RSA cryptosystem from Farouzan book on network security. The author has mentioned that RSA encryption is prone to chosen ciphertext attack. Then why is this algorithm still so popular?

The exact quote from the book is

  The basic RSA algorithm is vulnerable to a Chosen Ciphertext Attack (CCA)

So the answer to your question is that we don't use the "basic RSA algorithm" in practice. The basic RSA algorithm is also sometimes referred to as textbook RSA. Textbook RSA is malleable, which is why it is vulnerable to a chosen ciphertext attack. The attack works like this.

Eve has a ciphertext $c$ that she wants to learn the corresponding plaintext $m$ for. She has access to a decryption oracle that will decrypt any $c'\neq c$. So, she chooses a random value $r<n$ and computes $c'=c\cdot r^e\bmod{n}$. Note that since $c=m^e\bmod{n}$, we have $c'=(mr)^e\bmod{n}$ and $c'\neq c$.

Eve submits $c'$ to the decryption oracle, which returns $mr$. Eve now divides this by $r$ to recover $m$.

In practice, no one should use textbook RSA. To thwart this particular attack, we use padding. This removes the malleable property of RSA.


Upper (or lower) envelope of some linear functions Given some single variable linear functions $y_1=m_1x+b_1$, $y_2=m_2x+b_2$, $\ldots$, $y_n=m_nx+b_n$, the upper envelope is the function $f(x)= \max \{y_1, \ldots, y_n\}$. We know that this function is a convex piecewise linear function characterized by its breakpoints, where the slope of the function changes.  I know there exists an algorithm with  $O(n \log(n))$ complexity to find the breakpoints.
https://www.sciencedirect.com/science/article/pii/0020019089901361

Question: Can the complexity be reduced if  $m_i \geq 0$ for all $i$.

Suppose that we add $Mx$ to all your functions. This doesn't change the $x$-coordinate of your breakpoints (because $m_1 x + b_1 - m_2 x - b_2$ has the same sign as $(m_1 + M) x + b_1 - (m_2 + M) x - b_2$). Furthermore, for each breakpoint $x$, it just increases the value of the $y$-coordinate by $Mx$. This means that you can recover the original breakpoints, in linear time, given the breakpoints for the linear functions $(m_i + M)x + b_i$.

Now let $M = \max (-m_i)$, which can be found in linear time. The functions $(m_i + M)x + b_i$ all satisfy your condition. Hence if you could solve your problem in $f(n)$, then you could solve the original problem in $f(n) + O(n)$. Therefore you need not expect a more efficient solution for your special case.


Proof that POSITIVE-3-SAT is in the complexity class P I have the following language:

$$\text{POSITIVE-3-SAT} = \{\langle\phi\rangle \mid \phi\text{ is a satisfiable boolean formula in conjunctive normal form,}\\ \text{ in which all clauses consist of exactly 3 literals and in which no variable appears negated}\}.$$

Progress so far:

My concern is that I have not understood the task. I have proposed what I think is a (near trivial) proof.

To show that the language is in P, my approach is to provide a deterministic algorithm which can decide the problem in polynomial time.

By definition, $\text{POSITIVE-3-SAT}$ must comprise of an arbitrarily long number of conjunctions of clauses of the form $(\lambda_1 \lor \lambda_2 \lor \lambda_3)$. Each clause is trivially satisfiable in the case that a truth value of TRUE is assigned to any of the clauses $\lambda_1, \lambda_2, \lambda_3$. On this basis, each clause containing 3 literals can be decided in $O(3)$ steps, $\equiv O(1)$.

If we make the assumption that the language is constrained to only contain a finite number of $n$ clauses, then we can say that the satisfiability of the language can be decided in $O(n) \equiv O(n^1)$ steps.

Thus, $\text{POSITIVE-3-SAT}$ can be decided by a deterministic algorithm in polynomial time.

Thus, $\text{POSITIVE-3-SAT} \in$ NP.

It looks like you misunderstood a bit what you should prove since you missed the much easier way to prove although your (trivial) proof looks correct.

An easier proof

Let us call a boolean formula in conjunctive normal form in which all clauses consist of exactly 3 literals and in which no variable appears negative a positive‑3 formula. So

$$\text{POSITIVE-3-SAT} = \{\langle\phi\rangle \mid \phi\text{ is a satisfiable positive-3 formula}\}.$$

Note that any positive‑3 formula is satisfiable since it becomes TRUE if a truth value of TRUE is assigned to all variables.  So

$$\text{POSITIVE-3-SAT} = \{\langle\phi\rangle \mid \phi\text{ is a positive-3 formula}\}.$$

Here is an algorithm $\mathcal A$. Given an input string $s$, $\mathcal A$ just verifies whether $s$ is the encoded form of a positive-3 formula. If $s$ is, $\mathcal A$ returns yes; otherwise, $\mathcal A$ returns no. That verification step can be done in linear time in terms of the number of clauses in $s$. So $\text{POSITIVE-3-SAT}$ is in P.

The moral of the above proof is that you can use whatever known to you to construct the algorithm. All you need is to specify an algorithm and show that it works as wanted.

It depends on the requirement/convention/stage of your course or the intention of your course instructor whether you needs to explain in detail why that verification can be done in linear time or polynomial time. It looks like that verification step is totally ignored by the proof in the question, which is, in fact, a general accepted practice in the field.


NeuroEvolution: NEAT algorithm innovation numbers I have been reading up on the NeuronEvolution of Augmented Topologies and there's this little thing that's been bothering me. While reading Kenneth Stanley's Paper on NEAT I came on this figure here:

The innovation numbers go from 1,2,3,4,5,6 to 1,2,3,4,5,6,7 on the first mutation.

On the second one it goes from 1,2,3,4,5,6 to 1,2,3,4,5,6,8,9.

My question is why does it skip number 7 and goes straight up to 8 instead? I didn't find anything related to deleting innovation numbers.

Same thing on this second figure, how did Parent 1 lose 6,7 and where did the 8th gene go to in Parent 2?

Here is what I gathered from skimming the paper for just the figure.

Your first figure, which is the figure 3 in the paper, already has the answer in its caption:

  Figure 3: The two types of structural mutation in NEAT. Both types,
  adding a connection and adding a node, are illustrated with the
  connection genes of a network shown above their phenotypes. The top
  number in each genome is the innovation number of that gene. The
  innovation numbers are historical markers that identify the original
  historical ancestor of each gene. New genes are assigned new
  increasingly higher numbers. In adding a connection, a single new
  connection gene is added to the end of the genome and given the next
  available innovation number. In adding a new node, the connection gene
  being split is disabled, and two new connection genes are added to the
  end the genome. The new node is between the two new connections. A new
  node gene (not depicted) representing this new node is added to the
  genome as well.

In figure 3, it could be deduced that the add connection mutation (top half) occur preceding  the add node mutation (buttom half).

When the add connection mutation occurred, the lowest free innovation number was 7. And so the gene created at that moment was assigned the marker of 7.
Later, when the add node mutation occurred, 2 new genes were created. And so they were assign the lowest free innovation number at the time which is 8 and 9.

The innovation number is not the indices of each gene inside the array representing a genome.

The innovation number is just a number permanently branded to each gene, telling us when the gene first occur. As if the year number when human first evolved a gene for hairless body were written down on the gene itself.

The uses of innovation is then explained around your latter figure, which is figure 4:

  The historical markings give NEAT a powerful new capability. The
  system now knows exactly which genes match up with which (Figure 4).
  When crossing over, the genes in both genomes with the same innovation
  numbers are lined up. [...]
  This way, historical markings allow NEAT to perform crossover using linear genomes with out the need for expensive topological analysis.

From this I assumed that innovation number are always ordered increasingly within a genome, but gaps in innovation numbers are allowed to occur within genome.
The order is probably ensured simply by the fact that all operations done on genome was designed to not violate this within-genome ordering.

This makes sense because each gene can be thought of as an instruction to construct a graph.
By keeping the instruction ordered by when it was introduced, it makes sure that reading instruction on genome from left to right makes sense chronologically.


What is "polynomial delay?" I am reading a paper and it uses the expression "polynomial delay" which I don't understand. It is used in conjonction with the big O notation, which I'm familiar with.

Here is a example sentence showing how it is used:

  The loop is executed in time $O(n^2(e+n))$, which makes a polynomial delay for the output of the data.

I've tried searching a bit but I can only seem to find other papers and no definition.

The term "polynomial delay", in this case, appears to refer to the time complexity of generating (or enumerating) subsequent solutions. This is a bit different than our standard notion of runtime, since we usually only consider single executions of a machine or algorithm on an input. The delay complexity measure deals with time spent between enumerations through a set (e.g. a set of solutions).

Suppose you are working with a large dataset or database. You might want to step through or enumerate solutions to some problem using that data as an input. There are at least two steps involved here:

Initialization (perhaps generating your first solution)
Computing the next solution for the purpose of enumeration.

For example, you might use a polynomial space or exponential time algorithm to initialize and preprocess your data. To find or generate multiple solutions to a problem, you may only need to do a little bit of extra work. The time complexity with generating that next solution is the time delay complexity measure that you encountered in that paper. In particular, the time delay between enumerations is polynomial in respect to the input.

Jan Ramon mentions this and other time complexity measures in his talk on "General Graph Refinement with Polynomial Delay":
http://videolectures.net/mlg07_ramon_ggr/


Optimal way for grouping events I am creating an event notification system.

Each event has a user and a subject, such that, 'user did event to the subject'. Now while presenting these the events need to be grouped.

All the events in the same group must either refer to the same user or the same subject and each event must be in exactly one group.  Subject to those constraints, a group can contain any number of events, including just one. I want to calculate the grouping that uses the least possible number of groups.

Note that forming one group for each user, or forming one group for each subject does not, in general, give the smallest possible number of groups. Also, the events cannot, in general, all be placed in the same group, as that usually gives a group containing multiple users and multiple subjects, which is forbidden.

If I start from the first event and start putting it in the group with most possible events (acting all greedy), I will end up with a sub-optimal solution.

I could check all possible groupings but that will blow up exponentially ($2^n$ possible groupings for just n events).

How can I go about optimally grouping these events such that most of the events get grouped one way or the other, minimising the total number of groups?

Sample data -

event1    user1    subject1
event2    user2    subject1
event3    user3    subject1
event4    user2    subject2
event5    user3    subject2
event6    user1    subject3
event7    user2    subject4
event8    user2    subject5
event9    user3    subject5
event10   user1    subject5
event11   user4    subject1
event12   user4    subject2
...

Represent the events as a bipartite graphs: the vertices are the users and subjects and the edges are events (so there's an edge from user $x$ to subject $y$ if there's an event involving that user and subject).  What you're looking for is essentially a minimal vertex cover. A vertex cover is a set $C$ of vertices such that every edge includes at least one vertex from $C$. A minimal vertex cover is one that includes the smallest possible number of vertices.

Example. If the events are "John likes pizza", "John likes candy" and "Jane likes candy", the graph has vertices John, Jane, pizza and candy and the edges are John–pizza, John–candy and Jane–candy. A minimal vertex cover would be John and candy (in this case, there are several other minimal vertex covers).

For general graphs, finding minimal vertex covers is NP-hard but, for bipartite graphs, there is a polynomial-time algorithm because of König's theorem, which says that finding minimal vertex covers of bipartite graphs is equivalent to finding maximum matchings (i.e., a biggest-possible set of edges such that no pair of edges in the set shares an endpoint), which can be done by the Hopcroft–Karp algorithm.  The algorithm for finding a minimum vertex cover from a maximum matching is described in the "Proof" section of the Wikipedia König's theorem page.

Let $C$ be the minimum vertex cover that you just computed, and let the vertices in it be $c_1, \dots, c_k$ (so each $c_i$ is either a user or a subject).  The groups are $g_1, \dots, g_k$, where $g_1$ is all the events that involve the user or subject $c_1$and, for $i>1$, $g_i$ is the set of all events that involve the user or subject $c_i$ that haven't already been included in one of $g_1, \dots, g_{i-1}$.


How is a witness found in a proof of $\mathsf{NP} \subseteq \mathsf{P}/\log \implies \mathsf{P} = \mathsf{NP}$? I'm having a hard time understanding the actual proof of this proposition:

$\qquad \mathsf{NP} \subseteq \mathsf{P}/\log \implies \mathsf{P} = \mathsf{NP}$

The sketch of the proof is on slides 6-8 of this PDF.

So I let $L \in \mathsf{NP}$. That means that there's a deterministic polynomial-time TM $M^1_L$ s.t. $x \in L \iff \exists w. M^1_L(x,w) = 1$. I now need to construct a deterministic poly-time TM $M^2_L$ s.t. $x \in L \iff M^2_L(x) = 1$.

Looking at the proof in the slides above, I realize that given $x\in\{0,1\}^n$, $M^2_L$ needs to somehow find a witness $w$ for $x$ and then simply return whatever $M^1_L(x,w)$ does. But how do I find that witness?

Let's consider an $\mathsf{NP}$-complete like $SAT$: given a formula $\varphi$, is there a turht assignment $\tau$ such that $\tau \vDash \varphi$?
By assumption $\mathsf{NP} \subseteq \mathsf{P/\log}$ we know that $SAT \in \mathsf{P/\log}$. We will show that $SAT \in  \mathsf{P}$ which will imply $\mathsf{NP} \subseteq \mathsf{P}$.

Notations
Let us denote a partial truth assignment as a function from the set of variables to $\mathbb{B}_\bot = \{1,0,\bot\}$ where $\bot$ means the corresponding variable is not determined. We will denote the empty assignment where all variables are left undetermined as $[]$ and the assignment that sets only the value of the variable $x$ to $b$ as $[x\mapsto b]$.
Let $FV(\varphi)$ denote the set of free variables in $\varphi$.
Let us also denote the formula resulting from pluging in the values from a partial truth assignment $\sigma$ into a formula $\varphi$ as $\varphi\sigma$.

Witness Search Problem: $SATSearch$
Consider the witness search problem $SATSearch$: given a formula $\varphi$, find a truth assignment $\tau$ s.t. $\tau \vDash \varphi$ if there is one, otherwise return $None$.
It is easy to see that if the witness search problem can be solved in deterministic polynomial-time then $SAT$ is in $\mathsf{P}$: we just run $SATSearch$ on $\varphi$ and $\sigma = \emptyset$ and we accept iff the answer is not $None$.
Also note that if $SAT \in \mathsf{P/\log}$, then so is $SATSearch$: consider the following polynomial time algorithm for $SATSearch$ that uses $SAT$ as a black box:
$\tau = []$
if not $SAT(\varphi\tau)$ return $None$
for $x \in FV(\varphi)$

if $SAT(\varphi(\tau \cup [x \mapsto 0]))$ then $\tau = \tau \cup [x \mapsto 0]$
else $\tau = \tau \cup [x \mapsto 1]$

return $\tau$
More generally the claim holds for any class which is closed under Cook reductions.

By our assumption $SATSearch\in \mathsf{P/\log}$. Let $M$ be an TM with polynomial running time and advice of length $l(n)=O(\log n)$ where $n$ is the size of the input formula $\varphi$. We show that $SATSearch$ can be solved in deterministic polynomial time.
for all c of length $l(|\varphi|)$

$\tau = M(\varphi,c)$
if $\tau \vDash \varphi$ then return $\tau$

return $None$
If $\varphi$ is satisfiable, then at least for the right advice $M$ will return a witness and we can verify it. If the formula is not satisfiable, no $\tau$ can satisfy $\varphi$ so we will return $None$.
The running-time of the algorithm is polynomial and it uses no advice. So $SATSearch$ can be solved in deterministic polynomial time with no advice.
Therefore we can conclude that $\mathsf{NP}=\mathsf{P}$ if $\mathsf{NP}\subseteq \mathsf{P/\log}$.


Showing that $\lg(n!)$ is or is not $o(\lg(n^n))$ and $\omega(\lg(n^n))$ My instructor assigned a problem that asks us to determine which asymptotic bounds apply to a certain $f(n)$ for a certain $g(n)$, in my case $f(n) = \lg(n!)$ and $g(n) = \lg(n^n)$. For clarity, the convention we use in our class is that $\lg = \log_2$, the "binary logarithm".

I know that by Stirling's approximation, $\lg(n!)$ grows in $O(n\lg(n))$, and evaluating the limit $\lim_{n \to \infty} \frac{n\lg(n)}{n\lg(n)} = C$, some constant > 0, and so $\lg(n!)$ is in $\theta(\lg n^n)$.

$\theta$ also means that my $f(n)$ is is in $O(g(n))$ and $\Omega(g(n))$, but this does not mean that my $f(n)$ is in $o(g(n))$ or $\omega(g(n))$.

For that, I believe I would need to evaluate $\lim_{n \to \infty} \frac{\lg(n!)}{\lg(n^n)}$, but I am not certain.

What strategy would I use to show that $f(n)$ is in $o(g(n))$ or $\omega(g(n))$? Would I evaluate $\lim_{n \to \infty} \frac{\lg(n!)}{\lg(n^n)}$?

You seem tot be trying to prove something that is false. If $f=O(g)$ then $\lim_{n\to\infty}g/f > 0$ so $f\neq \omega(g)$. Similarly, if $f=\Omega(g)$ then $f\neq o(g)$.

Since you already have that $\lg n! = \Theta(\ln n^n)$, that gives you big-$O$ and big-$\Omega$, which preclude little-$\omega$ and little-$o$, respectively.


Proof that complement of HAMPATH is not in NP The Sipser book says, Complement of HAMPATH is not in NP.

I tried to find the solution for this, actually, a rigid proof like HAMPATH, which can state Complement of HAMPATH is in/not in NP, but I could not come up with any.

This is what I think, We are given a path from s to t(which can be a certificate for the problem, or not?), and check if it is not a HAMPATH. But this is easy, we can check this in P time right--Just list down the path, see that if any vertex is repeating in it, or if it is missing any vertex of the graph.

How come we are saying this problem is not in NP

I am very new to P and NP, Please correct my mistakes, and apologies if my question sounds like a silly one.

The complement of HAMPATH is the following problem:

  Given an undirected graph, determine whether it doesn't contain a Hamiltonian path.

A YES instance for the complement of HAMPATH is a graph which doesn't contain a Hamiltonian path. It is not clear what a witness for this property would be. Contrast that with HAMPATH itself, in which the witness for having a Hamiltonian path is simply a Hamiltonian path.

It is not known whether the complement of HAMPATH is in NP, or equivalently, whether HAMPATH is in coNP.

However, it is considered unlikely that HAMPATH is in coNP, since this would imply that NP=coNP, which is considered unlikely by most researchers in the area.


Learning the activation function in a neural network? Neural networks use specific activation functions, commonly used ones are tanh, ReLu.

I have seen that people have experimented with continuously parametrices activation functions, for instance here. Here, the additional parameter $\alpha$ which interpolates from logarithmus to linear to exponental, is optimized during the back-propagation step of the training.

I wonder whether much more general types of activation functions have been considered, such as Taylor-expansion of an unknown function where the coefficients are parameters in the training? It seems is a lot of degrees of freedom, that are not considered conventionally.

So my questions:

What is known about optimimality of actionation functions, apart from empirally testing? Are there mathematical proofs, for instance, that show some necessary properties for ideal learning (for instance, is monotonicity necessary, or could a sinusoidal activation function lead to optimal results too?)
If the answer to question 1 is no: Is there much research investigating the topic of learning activation functions?

Monotonicity is necessary! A neuron (perceptron) is either activated or not activated given an input.  If you're trying to learn "red" and red should activate the neuron; the more red it's the most likely it should be activated (This monotonic gradient is what this activation function represents).  If at certain redness it activates but at more redness it deactivates it makes no sense e.g. it can't learn red (The case for non-monotonic functions).

That they're differentiable functions makes it practical for the back propagation algorithm.

What they explain in your linked article is that they're trying to better approximate other functions e.g. sinusoidal.  They're not trying sinuosoidal as an activation function.
They're combining several monotonic functions to create yet another monotonic function, that is also differentiable.


Computing childrens of ith node of a d-ary tree Assume that we represent a complete d-ary tree in an array[1,...n] (this is a 1-based array of size n).
The formula for indices of children of node no. i is given as:
{(1-i)d+2,
... , min{n,(1-i)d+d+1}}
I am not able to get the intuition to arrive at this formula.
Can someone please help ?

The (traditional) binary heap (as e.g. in heapsort) is exactly your case, with $d = 2$; for 0-based arrays the children of $k$ are at $2 k + 1$ and $2 k + 2$. Analogously, in your case the children of $k$ are at $d k + 1, d k + 2, \dotsc, d k + d$.
The children of $0$ are at $1, 2, \dotsc, d$; children of $1$ start after that ($d + 1, d + 2, \dotsc, 2 d$), children of $2$ are at $2 d + 1, \dotsc, 3 d$, and so on. You should see the pattern here.


Finding all additive orders Suppose there are $m$ items, and each item has a price. We order the subsets of items according to their price. For example, if the price of $x$ is 1 and the price of $y$ is 2, then the order is:

$$
\emptyset < x < y < xy
$$

What is an algorithm for enumerating all orders of subsets that can be generated by such prices? For example, for two items the output should be two orders:

$$
\emptyset < x < y < xy
\\
\emptyset < y < x < xy
$$

For three items, the output should be 12 orders - 2 orders for each permutation of $x,y,z$. For example, for $x<y<z$ the two orders are:
$$
\emptyset < x < y < z < xy < xz < yz < xyz
\\
\emptyset < x < y < xy < z < xz < yz < xyz
$$

One solution is to generate all $(2^m)!$ orders and then check, for each order, whether it is compatible with some prices. However, it is not clear how to do this check, and even with a good algorithm for such a check, it will still very wasteful as most orders will be incompatible. For example, for 3 items we will need to check $8!$ orders to return only 12.

Note: I asked a similar question in math.SE, but the answer is apparently incorrect.

One approach is to recursively extend prefixes of the order. At each recursive call, we have a prefix $\phi$ of the order. We go over all remaining subsets, and for each subset $S$, we check whether the order $\phi < S$ is consistent. For each consistent $S$, we make another recursive call.

How do we check whether $\phi < S$ is consistent? This is a linear programming problem, whose solution we can speed up by starting the simplex algorithm from the "witness" showing that $\phi$ is feasible. There are two things to notice here: First, presumably you are assuming that all weights are positive. Second, we replace each constraints $A > B$ by $A \geq B+1$ (since LPs don't have strict constraints).

There are many optimizations which can be done here. For example, $S$ is always inclusion-minimal among the remaining subsets. Another optimization is to assume that the weights are ordered in a specific way (in your example, $x < y < z$); if you are really interested in all possible orders, you can always go over all permutations later.


What is a local inference system? A inference system is a set of rules that can be used to prove something in some formal model. I understand that.

But what does it mean to a inference system to be local?

For instance, in the page 36 of these MPRI notes there is the following definition:

Definition 4.2 (locality) Let $I$ be an inference system. The system $I$ is local if whenever $T ⊢ u$ in $I$, there exists a proof $\Pi$ of $T ⊢ u$  such that $Steps(\Pi) \subset st(T \cup \{u\})$.

But I am not able to understand this definition because even if I know that  $st(T\cup\{u\})$ is the set of subterms of $T \cup \{u\}$, I don't know what is $Steps(\Pi)$.

$\mathsf{Steps}(\Pi)$ is defined just above, in the paragraph below Definition 4.1. It's the set of node labels in the proof, i.e. the set of propositions that are proved as lemmas in that proof.

Thus a local inference system is a set of propositions such that every deduction $T \vdash u$ can be proved from lemmas that only involve terms that are subterms of the proposition $u$ or of the premises $T$.


While number can be checked for primality in O(n^0.5) then why was it considered to be not in P until AKS test? While a basic algorithm to check for primality of a number 'n' [checking if a divides n for all a less than n] would take O(n), AKS test was the breakthrough after which it was placed in P complexity class.

The bit length of $n$ is $\log(n)$, if we forget about the most significant digits, which is always $1$ except for $n=0$. As a function of $t=\log(n)$ you have $n^{1/2}=2^{t/2}$. It is in terms of the bit length of $n$ that AKS runs in polynomial time, while the naive test doesn't.