Can a Turing machine determine if a set is accepted by a another Turing machine? Can a Turing machine $M_A$ determine if the Turing machine $M_B$ accepts the set $W_k$?

I am curious about the answer to this as I am thinking about using the truth value of it on using it for a recursive enumerability proof.

Is the language of all machines that accept $W$ recognizable?

$$L_W = \{\langle M\rangle : L(M) = W\}$$

The answer is unfortunately no, except in trivial cases. If $W$ is unrecognizable, then $L_W$ is empty (no machine recognizes $W$) and hence decidable (The machine that rejects all inputs decides $L_W$).  In all other cases, $L_W$ is unrecognizable. We can show this using reductions from the unrecognizable rejection problem— the problem of determining whether a machine rejects a word.

If $W=\Sigma^*$, the set of all strings, then $L_W$ is unrecognizable (a standard result: "$M_x(w)$ simulates $M$ on $x$ for $|w|$ steps and accepts if the simulation doesn't accept by then." provides a reduction from the problem of deciding whether $M$ rejects $x$).
If $W\neq \Sigma^*$ is decidable, then $L_W$ is unrecognizable. Consider a program that takes a machine and word $\langle N, x\rangle$ and builds a new machine $N_x(w)$. The new machine decides whether $w\in W$ and accepts if so. Otherwise, it simulates $N$ on $x$ and does what it does. The machine $N_x$ therefore accepts $W$ (if $N$ rejects $x$) or all strings (if $N$ accepts $x$).

If we could recognize whether $N_x$ accepts $W$ or not, we could recognize whether $N$ rejects $x$ or not—an impossibility.
If $W$ is recognizable but undecidable, then $L_W$ is unrecognizable:  Consider a program that takes a machine and word $\langle N, x\rangle$ and builds a new machine $N_x(w)$. The new machine simulates $N$ on $x$ for $|w|$ steps. If the simulation accepts in that time, the machine accepts. Otherwise, the machine tests whether $w\in W$ and does what it does.

Hence $N_x$ accepts the union of $W$ and the set of all strings longer than the number of steps it takes for $N$ to accept $x$. If $N$ rejects $x$, $N_x$ recognizes $W$. If $N$ accepts $x$, $N_x$ recognizes additional words. (Note that because $W$ is undecidable, there must be arbitrarily long strings not in $W$. Otherwise, a DFA could decide $W$ by memorizing the short strings and using a length requirement for the long ones. Hence $N_x$ recognizes a strict superset of $W$ if $N$ accepts $x$.)

If we could recognize whether $N_x$ accepts $W$ or not, we could recognize whether $N$ rejects $x$ or not—an impossibility.


Clarification of the definition of a POMDP From what I understand, a $MDP=(G, A, P, R)$ (markov decision process) is represented as:

A complete directed graph $G=(V, E)$
A set of actions $A_u$ for each vertex $u \in V$
A reward function $R$ that maps any vertex to some reward, i.e., $R \colon V \mapsto \mathbb{R}$.
A probability function $P$ that gives the probability $P_a(u, v)\in [0, 1]$ of taking edge $(u, v)$ after performing action $a \in A_u$ at node $u$

The behavior of any MDP is talked about in terms of some policy $F$, where $F_0$ is the initial state that the policy starts in, and $F(u)\in A_u$ is the action $F$ takes when at node $u$, which is defined for all $u \in V$.

We then say that the MDP starts in $u=F_0$, performs some action $a=F(u)$, then moves to some other vertex $v \in V$ with probability $P_a(u, v)$. It repeats this process, where on turn $t$ it performs an action $b=F(w)$ some node $w \in V$, then moves to some other node $z\in V$ according to probability $P_b(w, z)$.

Now, a POMDP (partially observable markov decision process) is defined in a similar manner, except at each state $u \in V$ instead of knowing it's current state, $F$ is given some observation data $O(u) \in S$, where $S$ is any set. $F$ then constructs a "belief state" $b \in [0, 1]^{\vert V \vert }$ based on that information, which is a set of probabilities associated with each node of how much it "believes" it is in that node.

Now we define $F$ in terms of what action it performs in a given belief state, where the belief state can change with time.

This all makes sense, my question it just that since there are a different set of actions for each node, how does $F$ know what actions $A_u$ it has available without knowing what node $u\in V$ it is in?

The availability of action $ a $ can be understood as $P_a(u, v) > 0$ for some $ v $

If an action $ a $ is not available in $ u $ then it will have not effect, this means that $P_a(u, v) = 0 $ for every possible $v$


Big O analysis for problem where number of items searched is unknown Consider this problem: you are searching an array of elements and are comparing the square of the current element to some number K. Essentially, you are looking to see if the square root of K is in the array. With this algorithm, chances are, you will not search the entire array because you will either find the square root or you will find that the square root is not in the array.

As such, you are searching only a fraction of the array, which lets say has M elements. Does this mean that the big O is still O(M), even though you are not searching all of the elements?

Big-O gives the upper bound function of any analysis. For an algorithm you could represent all (Worst, Average, Best) cases in Big-O notation.

In your case,

Worst case: The required element is not present in the array (or is the last element of the array) : O(M)
Best case: The element is found in the first position itself: O(1)
Average case: Average of all possible case, i.e., the average time complexity of the cases where the element could be found at each possible position:

$$
\begin{align}
 = \frac{(1 + 2 + 3 + ... + M)}{M} \\
 = \frac{M(M + 1)/2}{M} \\
 = (M + 1)/2\\
= O(M)
\end{align}
$$

The average case is what you're looking for, which again O(M) only.


Multithreaded access to a persistent linked list data structure I previously asked a question about persistent data structures here. After that I came across an article that introduced persistent data structures. I have got a question on the following figure from the same article, where it describes how to implement a persistent linked list:

The author says:

  Inserting a new item into a persistent singly linked list will not
  alter the existing list but create a new version with the item
  inserted into it. Instead of copying the entire list and then
  inserting the item into the copy, a better strategy is to reuse as
  much of the old list as possible.

Since the two versions (Red and Yellow + Red) have common nodes (specifically, the last three Red nodes), how can one access these two versions simultaneously, for example in a multithreaded application?

Such list is intended to be immutable - the shared nodes will never be written to. There is no problem with several threads reading from the same memory location.


Retrieving data from website - Parser vs AI I'm currently working on a personal software project (as a hobby) and would like to know which kind of approach I should follow according to you.

My application scans some websites (like Amazon or eBay) to check items of a specific category and show them all together ordered, for instance, by price.

Currently I use Python with LXML to extract strings and numbers from specific positions on the page (searching by HTML element tag or CSS class).

This approach works smoothly, but I'm a little bit concerned about scalability: what if I want to add more web sources? What if Amazon and eBay change the structure of the HTML page?

So far I managed these issues by manually changing the functions I use to retrieve data from each website, but was wondering if there is a better approach, for example using AI/Machine Learning.

Finally the question: is it better to rely on "old-style" and "hard-coded" algorithms for such a scenario or Machine Learning and AI could be more helpful according to you?

Thanks a lot!

It depends what to use on what you are doing. I divide this problem in two categories.

1.Site without changing structure

Suppose, you are building a app which takes data from your national weather department site and normally which has same structure throughout decade. Here using AI for finding data is stupid thing. You should use conventional parsing technique here. and also your are getting data from number of sources but has fixed structure then you can go with this approach.

2.Site with changing structure

As per your example, I believe approach 1 is not so useful. because there are lots of site to parse and these site changes there structure periodically. So I believe using AI for parsing data from these sites is beneficial. I believe you used Optical Character Recognition. you will need similar functionality to your system. Your AI system first load page and see how it looks in browser (not code). Then finds appropriate fields from page using Named Entity Recognition from text which found using OCR

I think applying Named Entity Recognition to directly parsed code is sufficient to find different fields like item name, price, specifications, type etc


Syntax directed translation , definition and actions I have trouble understanding Syntax directed translation/definition/actions. I am reading dragon book but it confuses me even more.

Having production for simple  arithmetic

$$
  \mathit{expr} \rightarrow \mathit{expr} + \mathit{expr} \mathbin{|}  \mathit{expr} - \mathit{expr} \mathbin{|} \mathit{num}
$$

$$
  \mathit{num} \rightarrow 0 \mathbin{|} 1 \mathbin{|} 2 \mathbin{|} \dots \mathbin{|} 9
$$

If I understood it correctly, SDT just adds attributes to the nodes and define rules.

for this production rules can looks like

$$
  \mathit{expr}.\mathit{val} = \mathit{expr}.\mathit{val} + \mathit{expr}.\mathit{val} \mathbin{|} \mathit{expr}.\mathit{val} - \mathit{expr}.\mathit{val} \mathbin{|} \mathit{num}.\mathit{val}
$$

$$
  \mathit{num}.\mathit{val} = 0 \mathbin{|} 1 \mathbin{|} \dots \mathbin{|} 9
$$

this all together is called Syntax directed definiton.

Now what starts to confuse me:

It is often written that SDT is used to transfer infix to postfix notation e.g

$\mathit{expr} \rightarrow \mathit{expr} + \mathit{expr}$ will have semantic rule such as $\mathit{expr}.\mathit{val} = \mathit{expr}.\mathit{val} \mathbin{\|} \mathit{expr}.\mathit{val} \mathbin{\|} \text{'+'}$, where $\|$ represents concating of strings.

Is STD strictly defined to trasnform notation to postfix?

Also, where in this fall actions?

By definition

  A syntax-directed translation scheme is a notation for specifying a
  translation by attaching program fragments to productions in a
  grammar. A translation scheme is like a syntax-directed definition,
  except that the order of evaluation of the semantic rules is
  explicitly specified. Program fragments embedded within production
  bodies are called semantic actions

and example

$$
  \mathit{expr} \rightarrow^{+} \mathit{expr}\ \ \{\, \mathit{print}(\text{'+'}) \,\}\ \ \mathit{expr}
$$

I cannot find what is the usage of this. Which leads to sum of questions:
What is STD (rules) for and what are uses of actions in it?

I appreciate all answers, I read wiki but did not help.

Thanks.

Syntax directed translation uses the hierarchical structure of the input to generate the output. In other words, you exploit the grammar structure to help you to translate the program.

Translating using semantic rules

Semantic actions allow to embed code into a cfg which helps you to translate the program/source code. The following Ruby code should help you to figure out how things work. The following simple translator translates a single line infix expression into postfix expression.

First of all note that I use grammar that is suitable for top-down recursive descent parser, namely without left recursion and unambiguous. Transformation of this grammar is given in your book. So, you have to be familiar at least with a top-down recursive descent parsing method which is simple if you understand and have no problems with direct/indirect recursive calls.

Also please pay attention to how I embedded prints into while loops in order to emit postfix notation. As an exercise try to move the print to another line to get infix notation.

I wrote deliberately in Ruby so that you could play with the code and see it in action and modify it easily. If you have Ruby installed just type ruby parser.rb and see output.

@source = "1*2-3*4"
@index = 0

def get_token()
  @token = @source[@index]
  @index+=1
end

def exp()
  term()
  while(@token == '+' || @token == '-')
    op = @token #store the operator + or -
    get_token() #move to the next input symbol
    term()
    print op # <= semantic action (print operator + or -)
   end
end

def term()
  factor()
  while(@token == '*' || @token == '/')
    op = @token #store the operator
    get_token() #move to the next input symbol
    factor()
    print op # <= semantic action (print operator * or /)
  end
end

def factor()
  if ('0'..'9').include?(@token) #if @token is a digit
    tk = @token #store in temp variable
    get_token() #move to the next input symbol
    print tk # <= semantic action (print a digit)
  else
    puts 'Syntax Error'
  end
end

get_token()
puts exp()

Example outputs:

1*2-3*4 is translated into 12*34*-
1+2-3*7 is translated into 12+37*-

Computing expression value using node attributes

The following piece of code demonstrates node attributes in action to compute the value of an infix expression. Semantic actions this time around are lines which compute attribute of each tree node, that is, actual value of the expression.

@source = "9*3-3*7-2"
@index = 0

def get_token()
  @token = @source[@index]
  @index+=1
end

def exp()
  exp_t = term()
  while(@token == '+' || @token == '-')
    op = @token
    get_token()
    term_t = term()
    # compute attribute of the tree node
    if op == '+'
      exp_t += term_t
    else
      exp_t -= term_t
    end
  end

  return exp_t #return attribute to one level up in the tree
end

def term()
  term_t = factor()
  while(@token == '*' || @token == '/')
    op = @token
    get_token()
    val = factor()
    # compute attribute of the tree node
    if op == '*'
      term_t *= val
    else
      term_t /= val
    end
  end

  return term_t #return attribute to one level up in the tree
end

def factor()
  if ('0'..'9').include?(@token) #if @token is a digit
    tk = @token #store in temp variable
    get_token() #move to the next input symbol
    return tk.to_i #to_i means convert to integer
  else
    puts 'Syntax Error'
  end
end

get_token()
puts exp()

Examples:
9*3-3*7-2 results in 4
9*3-3*7 results in 6
1-1+1*1 results in 1


Non-termination of types in Martin-Löf's Type:Type? In the pre-history of dependent type theory, Per Martin Löf
introduced a calculus that is in some sense the simplest dependent
type theory and the most general form of impredicative polymorphism.
It is often referred to as Type:Type because the kind Type is
itself of type Type.  Unfortunately, it is inconsistent as a
logic. This was discovered by Girard in his famous dissertation [1],
who managed to express the Burali-Forti paradox in Type:Type.
Various people have analysed, generalised and simplified Girard's
analysis, see e.g. [2, 3]. This analysis seems to involve showing that
non-terminating terms can be typed.

I have a question about non-termination: do we get non-normalisation at
the level of types? By that I mean, is there a type $T$ such that the
reduction relation $\rightarrow$ used, explicitly or implicitly, to
define equality of types, gives rise to an infinite reduction sequence
$$
   T \rightarrow T' \rightarrow T'' \rightarrow \cdots?
$$

[1] J.-Y.. Girard, Une extension de l'interpretation fonctionelle de
Gödel a l'analyse.

[2] T. Coquand, A New Paradox in Type Theory.

[3] A. J. C. Hurkens, A Simplification of Girard's Paradox.

Short answer: yes.

Long answer: For $\mathrm{Type}:\mathrm{Type}$, non-termination at the type level is trivial. You can take a constant $X:\mathrm{False}\rightarrow \mathrm{Type}$. Then if you take the inconsistent term $\bot : \mathrm{False}$ you have
$$ X\ \bot : \mathrm{Type}$$
Which is non-terminating at the type level. You might complain that this has a head normal form, which isn't what usually leads to inconsistency in type theory. In this case you can remember that
$$ \mathrm{False}\equiv \forall X.\ X$$
and so
$$ \bot\ \mathrm{Type}:\mathrm{Type}$$

Which has no head-normal form. In general, in this system the types and terms are so intertwined that the non-termination always seeps at the type level.

However, there is another system, called $U^-$, also described by Girard in his thesis, which was discovered to be inconsistent by Coquand (A New Paradox in Type Theory). This system is terminating at the type level, as it only has $\mathrm{system}\ F$ types at the kind level, and we know that terms are normalizing in that system (also a result of Girard!).

This means that non-termination at the type level is not necessary for having an inconsistent pure type system (a fact that I found out somewhat painfully after having proven an open question while depending on this fact).


What is the definition of P, NP, NP-complete and NP-hard? I'm in a course about computing and complexity, and am unable to understand what these terms mean.

All I know is that NP is a subset of NP-complete, which is a subset of NP-hard, but I have no idea what they actually mean. Wikipedia isn't much help either, as the explanations are still a bit too high level.

I think the Wikipedia articles
$\mathsf{P}$, $\mathsf{NP}$, and $\mathsf{P}$ vs. $\mathsf{NP}$ are quite good.
Still here is what I would say: Part I, Part II

[I will use remarks inside brackets to discuss some technical details which
you can skip if you want.]

Part I

Decision Problems

There are various kinds of computational problems.
However in an introduction to computational complexity theory course
it is easier to focus on decision problem,
i.e. problems where the answer is either YES or NO.
There are other kinds of computational problems but
most of the time questions about them can be reduced to
similar questions about decision problems.
Moreover decision problems are very simple.
Therefore in an introduction to computational complexity theory course
we focus our attention to the study of decision problems.

We can identify a decision problem with the subset of inputs that
have answer YES.
This simplifies notation and allows us to write
$x\in Q$ in place of $Q(x)=YES$ and
$x \notin Q$ in place of $Q(x)=NO$.

Another perspective is that
we are talking about membership queries in a set.
Here is an example:

Decision Problem:

  Input: A natural number $x$,
  Question: Is $x$ an even number?

Membership Problem:

  Input: A natural number $x$,
  Question: Is $x$ in $Even = \{0,2,4,6,\cdots\}$?

We refer to the YES answer on an input as accepting the input and
to the NO answer on an input as rejecting the input.

We will look at algorithms for decision problems and
discuss how efficient those algorithms are in their usage of computable resources.
I will rely on your intuition from programming in a language like C
in place of formally defining what we mean by an algorithm and computational resources.

[Remarks:
1. If we wanted to do everything formally and precisely
we would need to fix a model of computation like the standard Turing machine model
to precisely define what we mean by an algorithm and
its usage of computational resources.
2. If we want to talk about computation over objects that
the model cannot directly handle,
we would need to encode them as objects that the machine model can handle,
e.g. if we are using Turing machines
we need to encode objects like natural numbers and graphs
as binary strings.]

$\mathsf{P}$ = Problems with Efficient Algorithms for Finding Solutions

Assume that efficient algorithms means algorithms that
use at most polynomial amount of computational resources.
The main resource we care about is
the worst-case running time of algorithms with respect to the input size,
i.e. the number of basic steps an algorithm takes on an input of size $n$.
The size of an input $x$ is $n$ if it takes $n$-bits of computer memory to store $x$,
in which case we write $|x| = n$.
So by efficient algorithms we mean algorithms that
have polynomial worst-case running time.

The assumption that polynomial-time algorithms capture
the intuitive notion of efficient algorithms is known as Cobham's thesis.
I will not discuss at this point
whether $\mathsf{P}$ is the right model for efficiently solvable problems and
whether $\mathsf{P}$ does or does not capture
what can be computed efficiently in practice and related issues.
For now there are good reasons to make this assumption
so for our purpose we assume this is the case.
If you do not accept Cobham's thesis
it does not make what I write below incorrect,
the only thing we will lose is
the intuition about efficient computation in practice.
I think it is a helpful assumption for someone
who is starting to learn about complexity theory.

  $\mathsf{P}$ is the class of decision problems that can be solved efficiently,
  i.e. decision problems which have polynomial-time algorithms.

More formally, we say a decision problem $Q$ is in $\mathsf{P}$ iff

  there is an efficient algorithm $A$ such that
  for all inputs $x$,

  if $Q(x)=YES$ then $A(x)=YES$,
  if $Q(x)=NO$ then $A(x)=NO$.

I can simply write $A(x)=Q(x)$ but
I write it this way so we can compare it to the definition of $\mathsf{NP}$.

$\mathsf{NP}$ = Problems with Efficient Algorithms for Verifying Proofs/Certificates/Witnesses

Sometimes we do not know any efficient way of finding the answer to a decision problem,
however if someone tells us the answer and gives us a proof
we can efficiently verify that the answer is correct
by checking the proof to see if it is a valid proof.
This is the idea behind the complexity class $\mathsf{NP}$.

If the proof is too long it is not really useful,
it can take too long to just read the proof
let alone check if it is valid.
We want the time required for verification to be reasonable
in the size of the original input,
not the size of the given proof!
This means what we really want is not arbitrary long proofs but short proofs.
Note that if the verifier's running time is polynomial
in the size of the original input
then it can only read a polynomial part of the proof.
So by short we mean of polynomial size.

Form this point on whenever I use the word "proof" I mean "short proof".

Here is an example of a problem which
we do not know how to solve efficiently but
we can efficiently verify proofs:

  Partition
  Input: a finite set of natural numbers $S$,
  Question: is it possible to partition $S$ into two sets $A$ and $B$
  ($A \cup B = S$ and $A \cap B = \emptyset$)
  such that the sum of the numbers in $A$ is equal to the sum of number in $B$ ($\sum_{x\in A}x=\sum_{x\in B}x$)?

If I give you $S$ and
ask you if we can partition it into two sets such that
their sums are equal,
you do not know any efficient algorithm to solve it.
You will probably try all possible ways of
partitioning the numbers into two sets
until you find a partition where the sums are equal or
until you have tried all possible partitions and none has worked.
If any of them worked you would say YES, otherwise you would say NO.

But there are exponentially many possible partitions so
it will take a lot of time.
However if I give you two sets $A$ and $B$,
you can easily check if the sums are equal and
if $A$ and $B$ is a partition of $S$.
Note that we can compute sums efficiently.

Here the pair of $A$ and $B$ that I give you is a proof for a YES answer.
You can efficiently verify my claim by looking at my proof and
checking if it is a valid proof.
If the answer is YES then there is a valid proof, and
I can give it to you and you can verify it efficiently.
If the answer is NO then there is no valid proof.
So whatever I give you you can check and see it is not a valid proof.
I cannot trick you by an invalid proof that the answer is YES.
Recall that if the proof is too big
it will take a lot of time to verify it,
we do not want this to happen,
so we only care about efficient proofs,
i.e. proofs which have polynomial size.

Sometimes people use "certificate" or "witness" in place of "proof".

Note I am giving you enough information about the answer for a given input $x$
so that you can find and verify the answer efficiently.
For example, in our partition example
I do not tell you the answer,
I just give you a partition,
and you can check if it is valid or not.
Note that you have to verify the answer yourself,
you cannot trust me about what I say.
Moreover you can only check the correctness of my proof.
If my proof is valid it means the answer is YES.
But if my proof is invalid it does not mean the answer is NO.
You have seen that one proof was invalid,
not that there are no valid proofs.
We are talking about proofs for YES.
We are not talking about proofs for NO.

Let us look at an example:
$A=\{2,4\}$ and $B=\{1,5\}$ is a proof that
$S=\{1,2,4,5\}$ can be partitioned into two sets with equal sums.
We just need to sum up the numbers in $A$ and the numbers in $B$ and
see if the results are equal, and check if $A$, $B$ is partition of $S$.

If I gave you $A=\{2,5\}$ and $B=\{1,4\}$,
you will check and see that my proof is invalid.
It does not mean the answer is NO,
it just means that this particular proof was invalid.
Your task here is not to find the answer,
but only to check if the proof you are given is valid.

It is like a student solving a question in an exam and
a professor checking if the answer is correct. :)
(unfortunately often students do not give enough information
to verify the correctness of their answer and
the professors have to guess the rest of their partial answer and
decide how much mark they should give to the students for their partial answers,
indeed a quite difficult task).

The amazing thing is that
the same situation applies to many other natural problems that we want to solve:
we can efficiently verify if a given short proof is valid,
but we do not know any efficient way of finding the answer.
This is the motivation why
the complexity class $\mathsf{NP}$ is extremely interesting
(though this was not the original motivation for defining it).
Whatever you do
(not just in CS, but also in
math, biology, physics, chemistry, economics, management, sociology, business,
 ...)
you will face computational problems that fall in this class.
To get an idea of how many problems turn out to be in $\mathsf{NP}$ check out
a compendium of NP optimization problems.
Indeed you will have hard time finding natural problems
which are not in $\mathsf{NP}$.
It is simply amazing.

  $\mathsf{NP}$ is the class of problems which have efficient verifiers,
  i.e.
  there is a polynomial time algorithm that can verify
  if a given solution is correct.

More formally, we say a decision problem $Q$ is in $\mathsf{NP}$ iff

  there is an efficient algorithm $V$ called verifier such that
  for all inputs $x$,

  if $Q(x)=YES$ then there is a proof $y$ such that $V(x,y)=YES$,
  if $Q(x)=NO$ then for all proofs $y$, $V(x,y)=NO$.

We say a verifier is sound
if it does not accept any proof when the answer is NO.
In other words, a sound verifier cannot be tricked
to accept a proof if the answer is really NO.
No false positives.

Similarly, we say a verifier is complete
if it accepts at least one proof when the answer is YES.
In other words, a complete verifier can be convinced of the answer being YES.

The terminology comes from logic and proof systems.
We cannot use a sound proof system to prove any false statements.
We can use a complete proof system to prove all true statements.

The verifier $V$ gets two inputs,

$x$ : the original input for $Q$, and
$y$ : a suggested proof for $Q(x)=YES$.

Note that we want $V$ to be efficient in the size of $x$.
If $y$ is a big proof
the verifier will be able to read only a polynomial part of $y$.
That is why we require the proofs to be short.
If $y$ is short saying that $V$ is efficient in $x$
is the same as saying that $V$ is efficient in $x$ and $y$
(because the size of $y$ is bounded by a fixed polynomial in the size of $x$).

In summary, to show that a decision problem $Q$ is in $\mathsf{NP}$
we have to give an efficient verifier algorithm
which is sound and complete.

Historical Note:
historically this is not the original definition of $\mathsf{NP}$.
The original definition uses what is called non-deterministic Turing machines.
These machines do not correspond to any actual machine model and
are difficult to get used to
(at least when you are starting to learn about complexity theory).
I have read that many experts think that
they would have used the verifier definition as the main definition and
even would have named the class $\mathsf{VP}$
(for verifiable in polynomial-time) in place of $\mathsf{NP}$
if they go back to the dawn of the computational complexity theory.
The verifier definition is more natural,
easier to understand conceptually, and
easier to use to show problems are in $\mathsf{NP}$.

$\mathsf{P}\subseteq \mathsf{NP}$

Therefore we have
$\mathsf{P}$=efficient solvable and $\mathsf{NP}$=efficiently verifiable.
So $\mathsf{P}=\mathsf{NP}$ iff
the problems that can be efficiently verified are
the same as the problems that can be efficiently solved.

Note that any problem in $\mathsf{P}$ is also in $\mathsf{NP}$,
i.e. if you can solve the problem
you can also verify if a given proof is correct:
the verifier will just ignore the proof!

That is because we do not need it,
the verifier can compute the answer by itself,
it can decide if the answer is YES or NO without any help.
If the answer is NO we know there should be no proofs and
our verifier will just reject every suggested proof.
If the answer is YES, there should be a proof, and
in fact we will just accept anything as a proof.

[We could have made our verifier accept only some of them,
that is also fine,
as long as our verifier accept at least one proof
the verifier works correctly for the problem.]

Here is an example:

  Sum
  Input: a list of $n+1$ natural numbers $a_1,\cdots,a_n$, and $s$,
  Question: is $\Sigma_{i=1}^n a_i = s$?

The problem is in $\mathsf{P}$ because
we can sum up the numbers and then compare it with $s$,
we return YES if they are equal, and NO if they are not.

The problem is also in $\mathsf{NP}$.
Consider a verifier $V$ that gets a proof plus the input for Sum.
It acts the same way as the algorithm in $\mathsf{P}$ that we described above.
This is an efficient verifier for Sum.

Note that there are other efficient verifiers for Sum, and
some of them might use the proof given to them.
However the one we designed does not and that is also fine.
Since we gave an efficient verifier for Sum the problem is in $\mathsf{NP}$.
The same trick works for all other problems in $\mathsf{P}$ so
$\mathsf{P} \subseteq \mathsf{NP}$.

Brute-Force/Exhaustive-Search Algorithms for $\mathsf{NP}$ and $\mathsf{NP}\subseteq \mathsf{ExpTime}$

The best algorithms we know of for solving an arbitrary problem in $\mathsf{NP}$ are
brute-force/exhaustive-search algorithms.
Pick an efficient verifier for the problem
(it has an efficient verifier by our assumption that it is in $\mathsf{NP}$) and
check all possible proofs one by one.
If the verifier accepts one of them then the answer is YES.
Otherwise the answer is NO.

In our partition example,
we try all possible partitions and
check if the sums are equal in any of them.

Note that the brute-force algorithm runs in worst-case exponential time.
The size of the proofs is polynomial in the size of input.
If the size of the proofs is $m$ then there are $2^m$ possible proofs.
Checking each of them will take polynomial time by the verifier.
So in total the brute-force algorithm takes exponential time.

This shows that any $\mathsf{NP}$ problem
can be solved in exponential time, i.e.
$\mathsf{NP}\subseteq \mathsf{ExpTime}$.
(Moreover the brute-force algorithm will use
only a polynomial amount of space, i.e.
$\mathsf{NP}\subseteq \mathsf{PSpace}$
but that is a story for another day).

A problem in $\mathsf{NP}$ can have much faster algorithms,
for example any problem in $\mathsf{P}$ has a polynomial-time algorithm.
However for an arbitrary problem in $\mathsf{NP}$
we do not know algorithms that can do much better.
In other words, if you just tell me that
your problem is in $\mathsf{NP}$
(and nothing else about the problem)
then the fastest algorithm that
we know of for solving it takes exponential time.

However it does not mean that there are not any better algorithms,
we do not know that.
As far as we know it is still possible
(though thought to be very unlikely by almost all complexity theorists) that
$\mathsf{NP}=\mathsf{P}$ and
all $\mathsf{NP}$ problems can be solved in polynomial time.

Furthermore, some experts conjecture that
we cannot do much better, i.e.
there are problems in $\mathsf{NP}$ that
cannot be solved much more efficiently than brute-force search algorithms
which take exponential amount of time.
See the Exponential Time Hypothesis
for more information.
But this is not proven, it is only a conjecture.
It just shows how far we are from
finding polynomial time algorithms for arbitrary $\mathsf{NP}$ problems.

This association with exponential time confuses some people:
they think incorrectly that
$\mathsf{NP}$ problems require exponential-time to solve
(or even worse there are no algorithm for them at all).
Stating that a problem is in $\mathsf{NP}$
does not mean a problem is difficult to solve,
it just means that it is easy to verify,
it is an upper bound on the difficulty of solving the problem, and
many $\mathsf{NP}$ problems are easy to solve since $\mathsf{P}\subseteq\mathsf{NP}$.

Nevertheless, there are $\mathsf{NP}$ problems which seem to be
hard to solve.
I will return to this in when we discuss $\mathsf{NP}$-hardness.

Lower Bounds Seem Difficult to Prove

OK, so we now know that there are
many natural problems that are in $\mathsf{NP}$ and
we do not know any efficient way of solving them and
we suspect that they really require exponential time to solve.
Can we prove this?

Unfortunately the task of proving lower bounds is very difficult.
We cannot even prove that these problems require more than linear time!
Let alone requiring exponential time.

Proving linear-time lower bounds is rather easy:
the algorithm needs to read the input after all.
Proving super-linear lower bounds is a completely different story.
We can prove super-linear lower bounds
with more restrictions about the kind of algorithms we are considering,
e.g. sorting algorithms using comparison,
but we do not know lower-bounds without those restrictions.

To prove an upper bound for a problem
we just need to design a good enough algorithm.
It often needs knowledge, creative thinking, and
even ingenuity to come up with such an algorithm.

However the task is considerably simpler compared to proving a lower bound.
We have to show that there are no good algorithms.
Not that we do not know of any good enough algorithms right now, but
that there does not exist any good algorithms,
that no one will ever come up with a good algorithm.
Think about it for a minute if you have not before,
how can we show such an impossibility result?

This is another place where people get confused.
Here "impossibility" is a mathematical impossibility, i.e.
it is not a short coming on our part that
some genius can fix in future.
When we say impossible
we mean it is absolutely impossible,
as impossible as $1=0$.
No scientific advance can make it possible.
That is what we are doing when we are proving lower bounds.

To prove a lower bound, i.e.
to show that a problem requires some amount of time to solve,
means that we have to prove that any algorithm,
even very ingenuous ones that do not know yet,
cannot solve the problem faster.
There are many intelligent ideas that we know of
(greedy, matching, dynamic programming, linear programming, semidefinite programming, sum-of-squares programming, and
many other intelligent ideas) and
there are many many more that we do not know of yet.
Ruling out one algorithm or one particular idea of designing algorithms
is not sufficient,
we need to rule out all of them,
even those we do not know about yet,
even those may not ever know about!
And one can combine all of these in an algorithm,
so we need to rule out their combinations also.
There has been some progress towards showing that
some ideas cannot solve difficult $\mathsf{NP}$ problems,
e.g. greedy and its extensions cannot work,
and there are some work related to dynamic programming algorithms,
and there are some work on particular ways of using linear programming.
But these are not even close to ruling out the intelligent ideas that
we know of
(search for lower-bounds in restricted models of computation
if you are interested).

Barriers: Lower Bounds Are Difficult to Prove

On the other hand we have mathematical results called
barriers
that say that a lower-bound proof cannot be such and such,
and such and such almost covers all techniques that
we have used to prove lower bounds!
In fact many researchers gave up working on proving lower bounds after
Alexander Razbarov and Steven Rudich's
natural proofs barrier result.
It turns out that the existence of particular kind of lower-bound proofs
would imply the insecurity of cryptographic pseudorandom number generators and
many other cryptographic tools.

I say almost because
in recent years there has been some progress mainly by Ryan Williams
that has been able to intelligently circumvent the barrier results,
still the results so far are for very weak models of computation and
quite far from ruling out general polynomial-time algorithms.

But I am diverging.
The main point I wanted to make was that
proving lower bounds is difficult and
we do not have strong lower bounds for general algorithms
solving $\mathsf{NP}$ problems.

[On the other hand,
Ryan Williams' work shows that
there are close connections between proving lower bounds and proving upper bounds.
See his talk at ICM 2014 if you are interested.]

Reductions: Solving a Problem Using Another Problem as a Subroutine/Oracle/Black Box

The idea of a reduction is very simple:
to solve a problem, use an algorithm for another problem.

Here is simple example:
assume we want to compute the sum of a list of $n$ natural numbers and
we have an algorithm $Sum$ that returns the sum of two given numbers.
Can we use $Sum$ to add up the numbers in the list?
Of course!

Problem:

  Input: a list of $n$ natural numbers $x_1,\ldots,x_n$,
  Output: return $\sum_{i=1}^{n} x_i$.

Reduction Algorithm:

  $s = 0$
  for $i$ from $1$ to $n$
  2.1.  $s = Sum(s,x_i)$
  return $s$

Here we are using $Sum$ in our algorithm as a subroutine.
Note that we do not care about how $Sum$ works,
it acts like black box for us,
we do not care what is going on inside $Sum$.
We often refer to the subroutine $Sum$ as oracle.
It is like the oracle of Delphi in Greek mythology,
we ask questions and the oracle answers them and
we use the answers.

This is essentially what a reduction is:
assume that we have algorithm for a problem and
use it as an oracle to solve another problem.
Here efficient means efficient assuming that
the oracle answers in a unit of time, i.e.
we count each execution of the oracle a single step.

If the oracle returns a large answer
we need to read it and
that can take some time,
so we should count the time it takes us to read the answer that
oracle has given to us.
Similarly for writing/asking the question from the oracle.
But oracle works instantly, i.e.
as soon as we ask the question from the oracle
the oracle writes the answer for us in a single unit of time.
All the work that oracle does is counted a single step,
but this excludes the time it takes us to
write the question and read the answer.

Because we do not care how oracle works but only about the answers it returns
we can make a simplification and consider the oracle to be
the problem itself in place of an algorithm for it.
In other words,
we do not care if the oracle is not an algorithm,
we do not care how oracles comes up with its replies.

For example,
$Sum$ in the question above is the addition function itself
(not an algorithm for computing addition).

We can ask multiple questions from an oracle, and
the questions does not need to be predetermined:
we can ask a question and
based on the answer that oracle returns
we perform some computations by ourselves and then
ask another question based on the answer we got for the previous question.

Another way of looking at this is
thinking about it as an interactive computation.
Interactive computation in itself is large topic so
I will not get into it here, but
I think mentioning this perspective of reductions can be helpful.

An algorithm $A$ that uses a oracle/black box $O$ is usually denoted as $A^O$.

The reduction we discussed above is the most general form of a reduction and
is known as black-box reduction
(a.k.a. oracle reduction, Turing reduction).

More formally:

  We say that problem $Q$ is black-box reducible to problem $O$ and
  write $Q \leq_T O$ iff
  there is an algorithm $A$ such that for all inputs $x$,
  $Q(x) = A^O(x)$.

In other words if there is an algorithm $A$ which
uses the oracle $O$ as a subroutine and solves problem $Q$.

If our reduction algorithm $A$ runs in polynomial time
we call it a polynomial-time black-box reduction or
simply a Cook reduction
(in honor of
Stephen A. Cook) and
write $Q\leq^\mathsf{P}_T O$.
(The subscript $T$ stands for "Turing" in the honor of
Alan Turing).

However we may want to put some restrictions
on the way the reduction algorithm interacts with the oracle.
There are several restrictions that are studied but
the most useful restriction is the one called many-one reductions
(a.k.a. mapping reductions).

The idea here is that on a given input $x$,
we perform some polynomial-time computation and generate a $y$
that is an instance of the problem the oracle solves.
We then ask the oracle and return the answer it returns to us.
We are allowed to ask a single question from the oracle and
the oracle's answers is what will be returned.

More formally,

  We say that problem $Q$ is many-one reducible to problem $O$ and
  write $Q \leq_m O$ iff
  there is an algorithm $A$ such that for all inputs $x$,
  $Q(x) = O(A(x))$.

When the reduction algorithm is polynomial time we call it
polynomial-time many-one reduction or
simply Karp reduction (in honor of
Richard M. Karp) and
denote it by $Q \leq_m^\mathsf{P} O$.

The main reason for the interest in
this particular non-interactive reduction is that
it preserves $\mathsf{NP}$ problems:
if there is a polynomial-time many-one reduction from
a problem $A$ to an $\mathsf{NP}$ problem $B$,
then $A$ is also in $\mathsf{NP}$.

The simple notion of reduction is
one of the most fundamental notions in complexity theory
along with $\mathsf{P}$, $\mathsf{NP}$, and $\mathsf{NP}$-complete
(which we will discuss below).

The post has become too long and exceeds the limit of an answer (30000 characters).
I will continue the answer in Part II.


Complexity of solving LP with a non-linear growth in variables/constraints It has been shown that any Linear Program (LP) can be solved in a polynomial number of steps. An example of such algorithm is the ellipsoid method.

  To solve a problem which has $k$ variables and can be encoded in $L$ input bits, this algorithm uses $O(k^4L)$ pseudo-arithmetic operations on numbers with $O(L)$ digits.

I have a problem that can be formulated as a LP, but yet has been proven to be NP-hard. The proof is rather hard and complicated for my understanding, so I just want to argue why it is, at least, not in P.

Consider the following excerpts from here.

I can see why the ellipsoid algorithm (or any LP solving algorithm) would take exponential amount of steps because the number of variables $k$ is exponential in $n$ ($k = m^n$).

Now the number of variables is not exponential anymore ($k = nm^2$) and I can not argue why solving the Dual LP would take an exponential number of steps. The only thing I could come up with is that $L$ (number of input bits) could be exponential in size because of the exponential number of constraints ($m^n$). But that is just a wild guess.

Additionally, if the statement about $L$ is true, than it is exponential in the primal LP as well, meaning that both $k$ and $L$ in $O(k^4L)$ are exponential. Does that mean that solving the dual LP is more efficient than solving the primal one, in which only $L$ is exponential but not $k$?

NB: The context is finding optimal correlated equilibria in succinct games.

The running time of algorithms for linear programming depends not only on the number of variables but also, unsurprisingly, on the number of constraints. This is hidden in the parameter $L$ which is the input size; clearly $L$ is at least the number of constraints. If there are exponentially many constraints, then any generic algorithms must take exponential time, since it has to consider all the constraints.

In some cases it is possible to solve linear programs with exponentially many constraints efficiently. This is the case if there is a separation oracle which, given a variable assignment, outputs a violated constraint (if any). If this can be done efficiently, then the ellipsoid algorithm can solve the linear program efficiently (at least approximately). If your problem is NP-hard then there is (probably) no efficient separation oracle for the dual LP. (Another possible reason for your problem to be hard is that rounding a solution could be hard or, perhaps, impossible.)


Proving that $\text{PCP}(O(\log n),1)\subseteq \mathsf{P}$ I'm studying the PCP theorem.

While it is easy to prove that $\mathsf{P}=\text{PCP}(O(\log n),0)$ , proving that $\text{PCP}(O(\log n),1)\subseteq \mathsf{P}$  i.e. PCP that uses $O(\log n)$ random bits and read 1 bit of the proof is less obvious, what I tried to do is to take some proof $\pi$ of length $n^{O(1)}$ (because effectively the message sent by the prover is bounded by $2^{r(n)}q(n)=2^{O(\log n)}=n^{O(1)}$) then try all the coin tosses each time the verifier read some bit of the message so if the proof is not correct we flip the bit in the proof!

By the basic equivalence of PCPs and MaxCSP problems, there exists a conjunction $C$ of polynomially many boolean literals, s.t.

  $\exists \text{ proof } \pi$ which makes the verifier $V$ accept with probability $\geq p$ $\Leftrightarrow$ $\exists$ an assignment that satisfies at least a $p$ fraction of the literals in $C$.

So you just need to show that the following problem is polytime solvable: given a conjunction $C$ of boolean literals, what is the largest number of literals that can be simultaneously satisfied. That's a very easy problem.

The idea here is that a PCP with query complexity $q$ corresponds to some MaxCSP problem with arity $q$. If the PCP has completeness $c$ and soundness $s$, then the language accepted by the PCP is reducible to a promise version of an arrity $q$ MaxCSP problem where in a 'no' instance at most an $s$ fraction of the constraints can be satisfied, and in a 'yes' instance at least a $c$ fraction of the constraints can be satisfied. These reductions are standard, look up any reference on PCPs.


Determining recursive enumerability of given languages I came across following problem:

  $L=\{M$ is a turing machine $M$ accepts two strings of different length $\}$
  $L=\{M$ is a turing machine $M$ accepts atleast two strings of different length $\}$

Which one Recursively Enumerable (RecEn)? Which one Recursive (Rec)?

I feel both are not recursively enumerable and hence not recursive. We may list strings in some order and run Turing machine on them. But we may never come across two strings of same length accepted by same TM. So we cannot answer both questions "accepts two strings of different length" and "acceptes at least two strings of different length". Am I correct? Also is my approach correct?

If (1) means exactly two strings of different lengths, not r.e. (2) is r.e.: guess two strings, check their lengths are different, verify that $M$ accepts both.

Use the extension to Rice's theorem to prove (1) isn't r.e.


Prove that $L_1$ is regular if $L_2$, $L_1L_2$, $L_2L_1$ are regular Prove that $L_1$ is regular if $L_2$, $L_1L_2$, $L_2L_1$ are regular.

These are the things that I would use to start.

As $L_1L_2$ is regular, then the homomorphism $h(L_1L_2)$ is regular.
Let $h(L_1) = L_2$ and $h(L_2) = L_1$, then $h(L_1L_2) = L_2L_1$ is regular (we already know that) or $h(L_2) = \epsilon$ and we get $L_1$
By reflexing, $L_1L_2 = (L_2L_1)^{R}$, same result.

But i don't know how to, for example, intersect something that gives me $L_1$ in order to preserve closure and finally $L_1$ be regular.

Any help?

Here is a counterexample. Let $L_1$ be any language over some alphabet $\Sigma$ containing the empty string, and let $L_2 = \Sigma^*$. Then $L_2 = L_1L_2 = L_2L_1 = \Sigma^*$ are all regular, but $L_1$ need not be, in fact it could even be uncomputable!


Verifying connectivity of a graph in O(n^2) I trying to solve the following problem in $O(n^2)$:

  We have vertices which represents cities and a textfile containing an edge on each line. How many roads do we need to build to
  make the graph connected - you can travel by road to each city?

Basically, at the start, we have just the vertices. As we read the textfile, we add a new edge each time we read a new line and we should decide after how many edges added is our graph now connected.

An example: An example:  we have 5 vertices, A, B, C, D, E. In the textfile, we have defined these edges: A-B, B-C, A-C, B-D, C-D, A-D, B-E, C-E. The graph have been made connected after building 7 edges, while we have only 5 vertices when we start (5 components).

I solved it the following way: I'm calling the BFS algorithm after adding each edge to the graph until the graph is connected and counting the number of BFS calls. However, since the BFS itself has a time complexity of $O(n^2)$ and I'm calling it n-times, I have a worstcase time complexity near $O(n^3)$.

How would I solve this issue in $O(n^2)$?

You can do one graph traversal to find all the connected components of your graph.

Then add an edge from each connected component to the next : the graph is fully connected and you did only one traversal, that's $O(n^2)$


Show that the pumping lemmas for context-free and regular languages are equivalent for unary languages I want to show that for any language $L \subseteq \{ a \}^* $, $L$ satisfies the pumping lemma for context free languages if and only if it satisfies the pumping lemma for regular languages.

I know that every regular language is also a context free language so I tried to show that direction of the proof first but ran into some difficulties.

Is there a more logical approach to this? Would I have to show that the conditions for both the pumping lemma for regular languages and the pumping lemma for context free grammars are equivalent for this language?

let $ z \in L$ such that $ |z| \geq n $ (where $n$ is the lemma's constant).
By the pumping lemma for CFL, we know that we can write $z=uvwxy$ such that:

$|vwx| \leq n$
$|vx| \geq 1$
for all $i \geq 0$: $uv^iwx^iy \in L$

Because $L$ is over an unary alphabet, we can change the order of the sub-words and the word ($z$) will not change, meaning we can also write $z=wvxuy$.

So. for all $i \geq 0$, $uv^iwx^iy = wv^ix^iuy = w(vx)^iuy$.
Let's write a little different:
$u' = w, v' = vx, w' = uy$. and we have that $u'(v')^iw' \in L$.

It's easy to see that $|u'v'| \leq n$ and $|v'| \geq 1$,
So we can conclude that for the same $n$, the conditions of pumping lemma for regular languages holds.

It might be worth mentioning that every CFL of unary alphabet is also regular (We know that even though a language satisfies the pumping lemma for regular/CF languages, it does't mean that the language is regular/CF).

It can be shown using Parikh's theorem, and showing that for every semi-linear set $S \subseteq \mathbb{N}  $ there is a regular language $L$ such that $\Psi (L)=S$ (or $p(L)$ using wikipedia's notations)


Domino and Tromino Combined Tiling If I have a nx2 grid which I need to fill using 2x1 dominoes and L shaped trominoes in any combination, how many different combinations are possible?

I am aware that when only 2x1 dominoes are used then the cell definition using dynamic programming is:
$$
f\left [ 0 \right ]= 0
$$
$$
f\left [ 1 \right ]= 1, i=1
$$
$$
f\left [ 2 \right ]= 2, i=2
$$
$$
f\left [ i \right ]= f\left [ i-2 \right ]+ f\left [ i-1 \right ], \forall i>2
$$

When L shaped trominoes are added to consideration, we (assume) can use them only in pairs since using odd number L shaped trominoes will leave one 1x1 grid unfilled. so when a pair of such trominoes combine it is equivalent to using a single 3x2 rectangular piece. Everytime we use $\ num=\lfloor n/3 \rfloor $ rectangular pieces and the rest are filled with 2x1 dominoes. Also the total number of combinations would be sum of twice the $\ num$, $\ f[i] $ and number of 2x1 domino combinations of the rest of the grid when the 3x2 piece is used. Is this assumption right? This is how far I have gotten through. If any of you have any hints it would be appreciated. Thank You in advance.

Note: Tile Rotations are allowed

There is a mutual recursion in two variables $f(n)$  for the $n\times 2$ grid and $g(n)$ for the $n\times 2$ grid with a single square sticking out. It does not matter where the square sticks out (first or second row) because their number of tilings is the same.

Note the trominos indeed come in pairs, but they do not need to form a $3\times 2$ block. You can place horizontal dominoes in between. Now that I look at it, it seems there is a recursion with one $f(n)$ if you look at a tromino and its matching partner. This picture suggests $f(7) = f(6)+f(5)+2f(4)+2f(3)+ \dots +2f(1)+2f(0)$. Sounds like a promising recursion to me.

If my initial computations are right, this suggests 1,1,2,5,11,24,53,117, ... which is OEISA052980. This lists another recurrence however. Would be fun if they match.

PS. Yes! Recursions are the same.
$f(n) = f(n-1) + f(n-2) + 2\sum_{k=0}^{n-3} f(k)$. Then subtract $f(n)-f(n-1) = f(n-1)+f(n-3)$. Thus $f(n) = 2f(n-1)+f(n-3)$, which is in the OEIS.


Inclusion of points in rectangles using a sweepline algorithm Given is a set of points $P_{1},....,P_{n}$ with $P_{i} = (x_{i},y_{i})$. No two points have the same x and y coordinates. Given is also a set of m axis-parallel rechtangles $R_{1},...,R_{m}$ in a plane, described by their bottom left corner $(l_{j},b_{j})$ and upper right corner $(r_{j},u_{j})$. No two rechtangles intersect or overlay each other and no point is on the border of a rechtangle.

We need to describe a sweepline algorithm which can output all the points which are not in a rechtangle.

I proceeded like so:

The sweepline is a vertical line going from left to right and stopping and evaluating at each event point. Out event points are the points $P$ and also the $(l,b),(r,u)$ of each rechtangle. We sort all the event points according to their x-coordinate.

We use an AVL-Tree to save the y-coordinates of the lower left corner of a rechtangle and remove it once we reach it's upper right corner. When we reach a point $p$, we will simply evaluate if p is within the borders of a currently active rechtangle by checking if $y_{p} \in [b,u]$ of active rechtangle. If so we mark it as false and proceed.

The solutions are that we are given more complicated and I don't understand them fully. I also don't know if my solution would work and why. It seems to be plausible to me.

They also save at each node of the AVL, the size of its subtrees so they can see how many points smaller than a node there are. Then while evaluating a point $p$, they search for p in the AVL tree and determine $A$ the number of keys smaller than $p$. Then it says that if $A$ is an even number, then the point is not in a rechtangle. Done.

I don't understand how this works. please help.

Thank you very much

I think storing in the AVL-tree only bottom $y$ coordinate is not enough. I think you should store at least both bottom and top coordinates of the active rectangle. Since your rectangles are not overlapping storing only the bottom and top coordinates is enough to solve the problem.

Basically, storing active rectangle in the AVL tree needs to decide whether a point is in a rectangle. Consider the following scenario

  y1 ----------------------------
     |                          |
     |                          |
  y2 ----------------------------
         o y6
  y3 ----------------------------
     |                          |
     |           o y7           |
  y4 ----------------------------

  y5 ----------------------------
     |                          |
     |                          |
  y6 ----------------------------

Initially your $p$ points in the AVL tree. As you sweep you add both $y$ coordinates of the active rectangles in the tree (and remove them as you rich the end of the rectangle).

If at the same time you have more than one active rectangles then by brute force method you would need to go over all rectangles and check whether $p_y \in [b,u]$. However, using AVL tree you could find the point $p_y$ in the tree and check the number of points smaller than $p_y$. If that number is even, say $2k$, then you have exactly $k$ active rectangles below $p$ meaning that $p$ is not in one of them, otherwise (if odd) it is in a rectangle. Look at the above figure, there are 4 points smaller than $y_6$ and so $y_6$ is outside, but there are 3 points smaller than $y_7$ and so $y_7$ is in a rectangle.


is there any hardware device to convert source code into machine language? Is there any hardware device inside computer that helps to convert high level language into machine, like compiler and assembler ?

No, and yes.

The answer is "no", in the sense that the vast majority of computers have no hardware that does what you typically expect a compiler to do; compilers are written in software. Obviously this ultimately runs on hardware, but we're talking general-purpose hardware.

However, the answer is "yes", in the sense that the machine code that is actually executed often isn't the same as the machine code that a programmer sees (i.e. the instruction set architecture, or ISA for short). Almost all modern CPUs do some degree of dynamic translation of the "machine code" into a form that is more suited for out-of-order execution.

Intel/AMD-type CPUs, for example, translate machine code into RISC micro-operations (called "uops"). It is these instructions which are scheduled and executed.

ARM has something similar. Its ISA is much closer to the format that's executed, but ARM also features Thumb instructions, which are dynamically translated into "core" instructions. The short-lived Jazelle DBX/ThumbEE did a similar thing with direct execution of JVM bytecode.

Almost all modern high-performance CPUs do this to varying degrees. Indeed, there is a fuzzy line between "dynamic translation" and "instruction decoding".


Does a weighted Breadth First search have "memory" when moving to the next vertex? I'm in a programming course and one Problem given to us is to mark the order in which BFS visits nodes in a weighted graph.

My question is whether BFS adds the distance of the previous path while adding a new vertex, as that will definitely change the order in which the vertices are added?

How about transforming your original graph to a graph with dummy nodes and just use regular BFS on it?

The idea is: if you have an edge with weight $k$ between $A$ and $B$, remove it. Then add a path between $A$ and $B$ with $k-1$ nodes in between, where all the edges have unit weight.

Now you can use regular BFS on your graph and it will reach the nodes in the same order as it would in the weighted version, without you having to transform the algorithm.

Ps. BFS always spreads out evenly, layer for layer like ripples in a pond. So if the next nodes to be added are A, B and C it will always add those nodes, but in which order does not matter- as long as the edges are unweighted.


Randomized algorithm for 2kCNF satisfiability problem The problem: Let a formula in $\varphi\in 2kCNF$ where there's an assignment $\alpha$ such that for every clause, $l$ in $\varphi$, $\alpha$ satisfies at least $k$ literals of $l$. Suggest a randomized algorithm for finding a satisfying assignment for such $\varphi$.

So basically I've read about the $WALKSAT$ algoritm which starts with some random assignment, $\alpha_1$ and for every iteration chooses randomly an unsatisfied clause, $l$ of $\varphi(\alpha)$ and a literal of $l$. Then, it flips this literal in $\alpha_1$, getting a new assignment, $\alpha_2$.

We repeat this process within a time bound $t$ or until a satisfying assignment has been found.

I've understood that this algorithm could be suitable here. I need to show that there's a probability of $\frac{1}{2}$ finding a satisfying assignment (probably after amplification)

I think we should look at the hamming distance of $\alpha, \alpha^t$ where $\alpha$ is the assignment as described in the question and $\alpha^t$ is unsatisfying assignment after $t$ iterations.

I'd be glad if you could guide from this point.

Thanks!

The analysis of Schöning's algorithm (see for example these CMU lecture notes) relies on the fact that if $\alpha$ is a satisfying assignment, $\beta$ is any assignment, and $C$ is an unsatisfied $k$-clause, then flipping a random variable decreases the distance between $\beta$ and $\alpha$ with probability at least $1/k$. In your case, you can get a better guarantee since $\alpha$ satisfies half the literals in every clause.


Difference between BSP model and synchronous round model in distributed computing I've recently learned about distributed computing and the synchronous model where, assuming  a complete network and no crashes, in each round the following happens:

every node can send a message to all other nodes,
all of these messages are received by all nodes by the end of the current round, and
at the start of the next round, every node performs some local computation (taking into account received messages).

It seems to me that this model is a more specific variant of the classic BSP model of Valiant where the cost of the barrier synchronization and the local computation is ignored.

Am I missing something else that distinguishes the distributed model from the BSP model?

In the CONGEST model of distributed computing, the topology of the computer network is a graph $G$. In each round, each node can send a message to each of its neighbours in $G$. Typically, we assume that $G$ is unknown, we interpret the structure of $G$ as the input, and we are interested in solving graph problems related to the structure of $G$.

This is the key difference. In BSP there is no underlying graph topology that limits communication; in CONGEST there is a graph that determines who can talk directly with whom.

However, things get interesting if we set $G = K_n$ in the CONGEST model. That is, the network topology is a complete graph on $n$ nodes. This way we arrive at a model called the congested clique.

The congested clique is very closely related to the BSP model. The key difference is the following:

Congested clique: the bandwidth constraints are on the edges; for each pair of nodes $u$ and $v$, in each round $u$ can send at most $b$ bits to $v$.
BSP: the bandwidth constraints are on the nodes; for each node $u$, in each round $u$ can send at most $B$ bits in total to all other nodes, and receive at most $B$ bits in total from all other nodes.

Clearly, any congested clique algorithm is trivial to simulate in the BSP model if we have $B = nb$, with only a constant overhead. [I am ignoring some issues related to the local computation.]

Lenzen (2013) shows that the converse is also true: any BSP algorithm can be simulated in the congested clique model if we have $B = nb$, with only a constant overhead.

In summary, if we eliminate $G$ from the CONGEST model, we basically arrive at the BSP model. Hence the graph $G$ is the only difference between the models.


Running time of algorithms that sometimes loop forever Consider the following algorithm that computes the sum of two integers (toy example):

INPUT: Integers (a,b)

 1. Toss a coin c
 2. If c = 0, then loop forever
 3. If c = 1, then compute and output a+b

What is the running time of this algorithm? The "strict" running time (defined as a strict upper bound on the running time over all inputs and all possible random choices of the algorithm) is infinite. The "expected" running time (defined as the average running time over all inputs and random choices) is infinite, too.

Thus, apparently this is an algorithm whose running time (strict/expected) is infinite. However, the algorithm still appears to be useful, since it produces a reasonable result with probability 1/2.

Is there a notion of "running time" in computer science that captures such algorithms? Can you point me to references or a textbook?

Thanks!

The textbook Computational Complexity: A Modern Approach by Arora and Barak looks at the class $ZTIME(T(n))$ (chapter 7), of algorithms whose expected running time is bounded by $T(n)$ (but which do not necessarily halt on all random seeds). This class cannot capture the notion you describe, because you are looking for a function whose range includes $\infty$, whereas Arora and Barak only look at time functions $T\colon \mathbb{N}\to \mathbb{N}$. Another close analogue to what you describe is $RE$, the class of problems recognizable by a Turing Machine which is only guaranteed to halt on yes-instances.

To my knowledge, even the Complexity Zoo doesn't cover algorithms with infinite expected running time. The reason, I suppose, that these algorithms aren't studied is twofold: (1) they are not useful, because an algorithm with an infinite running time produces no answer and (2) they are not needed to solve any problems that cannot be solved by a deterministic computer with a finite or unbounded running time. To see (2), imagine an algorithm $A$ for deciding membership in a language, in the sense that when it halts, it outputs the right answer, but it is not guaranteed to halt for all inputs. Then you can just do a breadth-first search on the configuration graph. The class of problems solvable with these restrictions is $RE$. If the algorithm is guaranteed to have at least one halting path, the class is $R$.


How can a computer deal with real numbers Computers are an exceptionally powerful tool for various computations, but they don't excel at storing decimal numbers. However, people have managed to overcome these issues: not storing the number in a decimal format, which is limited to very few decimal places, but as an integer instead, while keeping track of the number's precision.
Still, how can a computer simplify computations just like humans do? Take a look at this basic  example
$$\sqrt{3} \times (\frac{4}{\sqrt{3}} - \sqrt{3}) = \sqrt{3} \times \frac{4}{\sqrt{3}} - \sqrt{3} \times \sqrt{3}  = 4 - 3 = 1$$
That's how a human would solve it. Meanwhile, a computer would have a fun time calculating the square root of 3, diving 4 by it, subtracting the square root of 3 from the result and multiplying everything again by the square root of 3.
It would surely defeat a human in terms of speed, but it would lack in terms of accuracy. The result will be really close to 1, but not 1 exactly. A computer has no idea that, for instance, $\sqrt{3} \times{\sqrt{3}}$ is equal to $3$. This is only one of the uncountable examples out there.
Did people already find a solution, as it seems elementary for mathematics and computations? If they didn't, is this because it didn't serve any purpose in the real world?

Sage is an open source computer algebra system. Let's see if it can handle your basic example:

sage: sqrt(3) * (4/sqrt(3) - sqrt(3))
1

What is happening under the hood? Sage is storing everything as a symbolic expression, which it is able to manipulate and simplify using some basic rules.
Here is another example:

sage: 1 + exp(pi*i)
0

So sage can also handle complex numbers.
Computers never handle real numbers, since real numbers cannot be represented exactly on a computer. Instead, they either handle approximate representations of real numbers (usually floating point numbers but sometimes fixed point numbers), or they represent real numbers symbolically, as in the example above. Sage can convert between the two representations (in one direction!), and it can handle floating point numbers of arbitrary accuracy. For example,

sage: RealField(100)(pi^2/6 - sum(1/n^2 for n in range(1,10001)))
0.000099995000166666666333333336072

This computes $\pi^2/6 - \sum_{n=1}^{10^4} 1/n^2$ to 100 bits of accuracy (in the mantissa).
Another approach worth mentioning is interval arithmetic, which is a way of computing expressions with a guaranteed level of accuracy, using provable error brackets. Interval arithmetic is used in computational geometry, together with exact representation of rational numbers.
In theoretical computer science there are several other notions of real computation, but they are mostly of theoretical interest. See the answers to this question.


Big O understanding given different input sizes I have a question about big O notation. Let's say I have 3 algorithms which, for an input of size $n$, have time complexity $O(n)$, $O(n^2)$ and $O(n \log n)$, respectively. Assume that all 3 algorithms take $a$, $b$ and $c$ seconds for the worst, average and best cases given an input of size $n$. What could be the actual time of these 3 algorithms given an input of size $2n$? Based on my understanding it should be:

$O(n)$: $2a$, $2b$, and $2c$.
$O(n^2)$: $a^2$, $b^2$, and $c^2$.
$O(n \log n)$: $a \log a$, $b \log b$, and $c \log c$.

My questions are:

Is this correct?
In case not, why?
In case this is correct, would the same hold for $\Theta$ and $\Omega$?

No, this isn't correct, for a number of reasons.

$O(\cdot)$ only gives upper bounds. Being told that $f(n)=O(n\log n)$ doesn't exclude the possibility that $f(n)=n$, $f(n)=1$, etc.
The bounds only apply to sufficiently large $n$. Perhaps your measurements were for values of $n$ that are too small to exhibit the asymptotic behaviour.
Even if $n$ was large enough, consider the algorithm "If my input has odd length, return immediately; otherwise, perform some calculation that takes exactly $n^2$ steps." This has running time $O(n^2)$, so you'd expect an input twice as big to take four times as long. But an odd-length input will take about $n$ steps, whereas $2n$ is even, so an input of that length would take time at least $(2n)^2$, which is much more than four times as much.
The actual running time of the code on an actual computer will depend on all kinds of factors that aren't included in the theoretical analysis. You could be careful to exclude things such as interruptions by other processes, but consider something like disc access. Suppose that your input of size $n$ takes up a quarter of a disc block. Most of the running time of your algorithm might be waiting for that one block to be transferred; the input of length $2n$ will also fit in one block, so you do the same amount of disc I/O and doubling the input takes only a small fraction longer to run. On the other hand, if your length-$n$ input is a whole block, then reading two blocks will take twice the time. Except that the OS will probably cache the second block for you, so probably it won't. Similar effects apply to memory accesses and their interaction with the cache.
Your arithmetic is off. Consider the three functions $f(n)=n$, $g(n)=n^2$ and $h(n)=n\log_2 n$.  Then
$$f(2n)=2n=2f(n)\\
g(2n)=(2n)^2=4n^2=4g(n)\\
h(2n)=2n\log_2 2n = 2n(\log_2 n+\log_2 2) = 2h(n)+2n\,.$$


Detect non existence of a cycle in a graph using Datalog : SMTLIB Format for Z3 I want to detect the non existence of a cycle in a graph using Datalog (which is  a declarative logic programming language).

The proposed solution was:

(set-option :fixedpoint.engine datalog)
(define-sort s () Int)

(declare-rel edge (s s))
(declare-rel path (s s))

(declare-var a s)
(declare-var b s)
(declare-var c s)

(rule (=> (edge a b) (path a b)) P-1)
(rule (=> (and (path a b) (path b c)) (path a c)) P-2)

(rule (edge 1 2) E-1)
(rule (edge 2 3) E-2)
(rule (edge 3 1) E-3)

(declare-rel cycle (s))
(rule (=> (path a a) (cycle a)))
(query cycle :print-answer true)

But my question is how can i get SAT when there is no cycle in the graph and UNSAT when there exists a cycle.

One suggestion (but that does not meet my need) is:

(set-option :fixedpoint.engine datalog)
(define-sort s () Int)

(declare-rel edge (s s))
(declare-rel path (s s))

(declare-var a s)
(declare-var b s)
(declare-var c s)

(rule (=> (edge a b) (path a b)))
(rule (=> (and (path a b) (path b c)) (path a c)))

(rule (edge 1 2) r-1)
(rule (edge 2 3) r-2)
(rule (edge 3 1) r-3)

(assert (not (path a a)))

(check-sat)
(get-model)

which returns as result:

> z3 test.txt
sat
(model
  (define-fun a () Int
    0)
  (define-fun path ((x!0 Int) (x!1 Int)) Bool
    (ite (and (= x!0 0) (= x!1 0)) false
      false))
)

I don't understand why z3 assign 0 to the variables while I only have 1, 2 and 3 as vertices?

Another suggestion was :

(set-option :fixedpoint.engine datalog)
(define-sort s () Int)

(declare-rel edge (s s))
(declare-rel path (s s))

(declare-var a s)
(declare-var b s)
(declare-var c s)

(rule (=> (edge a b) (path a b)))
(rule (=> (and (path a b) (path b c)) (path a c)))

(rule (edge 1 2) r-1)
(rule (edge 2 3) r-2)
(rule (edge 3 1) r-3)

(assert
         (=> (path a a)
            false
            )

 )

(check-sat)
(get-model)

Which returns the result:

> z3 test2.txt
sat
(model
  (define-fun a () Int
    0)
  (define-fun path ((x!0 Int) (x!1 Int)) Bool
    (ite (and (= x!0 0) (= x!1 0)) false
      false))
)

Any idea to resolve this problem?

Note: I need to use Datalog for reasons of complexity.

I don't think you can do it in plain Datalog, but you can do it in Datalog plus negation.

I suggest you define a relation $R$, so that $R(x,y)$ is true if vertex $y$ is reachable from vertex $x$ in one or more steps.  You can define $R$ recursively, namely,

$$R(x,y) = E(x,y) \lor \exists w . E(x,w) \land R(w,y),$$

where $E$ is a relation that represents the edges in the graph ($E(x,y)$ is true iff $(x,y)$ is an edge in the graph).  Now the graph has a cycle iff $\exists x . R(x,x)$ is true.  I think you should be able to translate this in Datalog.

From this you can get a Datalog instance that is satisfiable if there is a cycle in the graph, or unsatisfiable if there is no cycle.

If you want the reverse (an instance that is satisfiable iff there is no cycle), I think you need negation.

The details of how to express that in Z3 code seem off-topic here.


Solution to the following recurrence relation and initial condition? With the initial condition being $a_0$ = 3, and the relation being $a_n = 2a_{n - 1}$, what would the solution be? Any help would be greatly appreciated.

Try to calculate $a_1$. You'll see that $a_1=2\times3$. Then $a_2=2a_1=2\times2\times3=2^2\times3$.

Conjecture that $a_n=3.2^n$ for all $n\ge 0$.

Prove by induction.


What do the symbols M and N mean in this definition of lambda terms? I am learning lambda calculus from the book https://www.irif.fr/~mellies/mpri/mpri-ens/biblio/Selinger-Lambda-Calculus-Notes.pdf and do not understand the meaning of the following symbols.

The definition of the lambda terms is:

Lambda terms: $\mathit{M,N} ::= x | (M N) | (λx.M) $

The question is, what do $\mathit{M}$ and $\mathit{N}$ mean?

I suggest you read the page following the supposedly cryptic notation:

  The above Backus-Naur Form (BNF) is a convenient abbreviation of the following equivalent, more traditionally mathematical definition:

  Definition. [...]

In said definition, it is stated that $M$ and $N$ are simply arbitrary lambda terms. (In a nutshell, it is an inductive definition.)

As to why the author prefers this notation, it is stated right after the definition:

  Comparing the two equivalent definitions, we see that the Backus-Naur Form is
  a convenient notation because: [...] the use of distinct meta-symbols for different syntactic classes ($x$, $y$, $z$
  for variables and $M$, $N$ for terms) eliminates the need to explicitly quantify over
  the sets [of variables and lambda terms].


Is there a formal definition of sub-instances or sub-problems? A decision problem is denoted as a language $L \subseteq \Sigma^{*}$.
For every instance $x \in \Sigma^{*}$, we say $x$ is a yes-instance if $x \in L$ and a no-instance if $x \not\in L$.
For some algorithms (e.g. devide-and-conquer, dynamic programming), we may consider some sub-instances firstly, given an instance $x$.
I want to know whether I can let the substrings or the prefixs (suffixs) of $x$ be (all of) the sub-instances.
Is there a formal definition of sub-instances?

I don't think there is a widely-used formal definition, and that this is so for a good reason. Sub-problems or sub-instances are tools used in the process of designing algorithms (for "divide and conquer" or "dynamic programming" in particular, but also more generally).
The process of (humans) designing algorithms is not a completely formal process: it relies on intuition and informal insight to arrive at an idea of an algorithm, and eventually refine this idea into an actual formalized algorithm.
As for your final question

I want to know whether I can let the substrings or the prefixs (suffixs) of $x$
be (all of) the sub-instances. Is there a formal definition of sub-instances?

This depends on the context. It could be that you're reading some text where someone has given a formal definition of "sub-instance". If not, then I think it is best to work under the assumption that there is no formal definition of "sub-instance" here.
Given that "sub-instance" is only an informal notion, how do you determine whether something is a sub-instance? The only option is to try it out and see if it works. The idea of something being a sub-instance is equally valid as the idea that it isn't a sub-instance. What you need to do is to determine which of the two ideas is more useful in constructing or reasoning about an algorithm.


Is the language of all words of the form $wxw^Rx^R$ context-free? Is the language $\{wxw^Rx^R \mid w,x \in \{0,1\}^* \}$ context-free
My thoughts, Let $x = \epsilon$ and we get $ww^R$, which is context-free. Hence the given language must be context-free.
Am I right?

Denote your language by $L$, and consider
$$
L' = L \cap 10^*1110^*10^*10^+11.
$$
Any word in $L'$ is of the form
$$
10^a1110^b10^c10^d11,
$$
where $d > 0$.
Also, it is of the form $wxw^Rx^R$. Since both $wx$ and $w^Rx^R$ contain the same number of $1$'s, necessarily
\begin{align}
wx &= 10^a1110^{b_1} \\
w^Rx^R &= 0^{b_2}10^c10^d11
\end{align}
where $b_1 + b_2 = b$. We see that $x^R$ ends with $110$ (since $d>0$), and so $x$ starts with $110$. Hence $w = 10^a1$ and $x=110^{b_1}$, implying that $w^Rx^R = 10^a10^{b_1}11$. This shows that $b_2 = 0$ hence $b_1 = b$, and furthermore $c = a$ and $d = b$. That is, the word is of the form
$$
10^a1110^b10^a10^b11,
$$
where $b > 0$. Conversely, every word of this form is in $L'$ (take $w = 10^a1$ and $x = 110^b$).
Let $h\colon \{1,2,3,4,5\} \to \{0,1\}$ be the homomorphism given by $h(1) = 1$ and $h(2) = h(3) = h(4) = h(5) = 0$, and let $d\colon \{1,2,3,4,5\} \to \{2,3,4,5\}$ be the homomorphism that deletes $1$. Then
$$
d(h^{-1}(L') \cap 12^*1113^*14^*15^*11) \cup \{2^n4^n : n \geq 0\} = \{2^n3^m4^n5^m : n,m \geq 0\}.
$$
The latter language is well-known not to be context-free. Since all our operations preserve being context-free, we conclude that $L$ is also not context-free.


Bridge theorems for group theory and formal languages Is there some natural or notable way to relate or link math groups and CS formal languages or some other core CS concept e.g. Turing machines?

I am looking for references/applications. However note that I am aware of the link between semigroups and CS languages (namely via finite automata). (Does this literature on semiautomata ever look at "group-automata"?)

I have seen one paper many years ago that might come close, that converts TM transition tables into a binary operation, possibly sometimes a group in some cases, conceivably based on some kind of symmetry in the TM state table. It didn't explore that in particular, but also didn't rule it out.

Also, in particular, regarding the large body of math research on classification of finite groups, does or could it have any meaning or interpretation in TCS? What is the "algorithmic lens" view of this massive edifice of mathematical research? What is it "saying" about a possible hidden structure in computation?

This question is partly inspired by some other notes e.g.:

Use of algebraic structures in TCS
RJ Lipton on Gromov's theorem

Let me first answer your subquestion: Does the literature on semiautomata ever look at "group-automata"?. The answer is yes. In his book (Automata, languages, and machines. Vol. B, Academic Press), S. Eilenberg gave a characterization of the regular languages recognized by finite commutative groups and $p$-groups. Similar results are known for finite nilpotent groups, soluble groups and supersoluble groups.

Finite groups also play an important role in the problem of finding a complete set of identities for regular expressions. An infinite complete set was proposed by John Conway and this conjecture was ultimately proved by D. Krob. There is a finite number of "basic" identities, plus an identity for each finite simple group. See my answer to this question for references.

In the opposite direction, finite automata theory lead to an elementary proof of basic results on combinatorial group theory, like the Schreier formula. Based on Stallings's seminal paper Topology of Finite Graphs.

Also in the opposite direction, automatic groups are defined in terms of finite automata.

Profinite groups also play an important role in automata theory. An example is the characterization of the regular languages recognized by transition-reversible automata with
possibly several initial and final states.

For a very nice connection between context-free languages, groups and logic, see the article
by David E. Muller and Paul E. Schupp, Context-free languages, groups, the theory of ends, second-order logic, tiling problems, cellular automata, and vector addition systems.


Uniform Hashing. Understanding space occupancy and choice of functions I'm having troubles understanding two things from some notes about Uniform Hashing.
Here's the copy-pasted part of the notes:

Let us first argue by a counting argument why the uniformity property,
we required to good hash functions, is computationally hard to
guarantee. Recall that we are interested in hash functions which map
keys in $U$ to integers in $\{0, 1, ..., m-1\}$. The total number of such
hash functions is $m^{|U|}$, given that each key among the $|U|$ ones can be
mapped into $m$ slots of the hash table. In order to guarantee uniform
distribution of the keys and independence among them, our hash
function should be anyone of those ones. But, in this case, its
representation would need $\Omega(log_2 m^{|U|}) = \Omega(|U| log_2 m)$ bits, which is
really too much in terms of space occupancy and in the terms of
computing time (i.e. it would take at least $\Omega(\frac{|U|log_2 m}{log_2 |U|})$ time to just
read the hash encoding).

The part I put in bold is the first thing is confusing me.
Why the function should be any one of those? Shouldn't you avoid a good part of them, like the ones sending every element from the universe $U$ into the same number and thus not distributing the elements?
The second thing is the last "$\Omega$". Why would it take $\Omega(\frac{|U|log_2 m}{log_2 |U|})$  time just to read the hash encoding?
The numerator is the number of bits needed to index every hash function in the space of such functions, the denominator is the size in bits of a key. Why this ratio gives a lower bound on the time needed to read the encoding? And what hash encoding?

Suppose that we sample a hash function $h$ at random from a collection $\mathcal{H}\subseteq [m]^U$ (we denote by $[m]$ the set $\{0,1,...,m-1\}$). The best possible thing we can require from this choice is that $\left(h(x_1),h(x_2),....,h(x_{|u|})\right)$ are jointly uniformly distributed over $[m]^U$, where $U=\{x_1,...,x_{|U|}\}$ (this in turn implies independence). Fix some $h_0\in [m]^U$, then under the previous requirement we have:
$\Pr\limits_{h\sim\mathcal{H}}[h=h_0]=\Pr\limits_{h\sim\mathcal{H}}\left[h(x_1)=h_0(x_1)\land...\land h(x_{|U|})=h_0(x_{|U|})\right]=\frac{1}{m^{|U|}}$.
It follows that $h$ is uniformly distributed over all possible functions in $[m]^U$ (in any other case we will fail either in uniformity or in independence). This is what is meant by "$h$ should be anyone of these functions".


Asymptotics of of $T(n) = n + T(n - \sqrt{n})$ What is the asymptotic rate of growth of the following recurrence?
$$ T(n) = n + T(n - \sqrt{n}). $$
Since I cannot use the Master's Theorem here, I could not figure it out the answer. My initial guess is $n^{3/2}$, but I'm not sure.
Can anyone help me? What are the big-O and big-Omega complexities here?

You can get a lower bound of $\Omega(n^{3/2})$ as follows. Consider the number of steps it takes to get from $n$ to $n/2$. Since at each step, $n$ decreases by at most $\sqrt{n}$, this takes at least $\sqrt{n}/2$ steps. At each such step, we accumulate at least $n/2$, for a total of at least $n^{3/2}/4$.
You can prove a matching upper bound using a similar approach. While the input parameter is at least $n/2$, it decreases by at least $\sqrt{n/2}$, and so it takes at most $\sqrt{n/2}$ steps to get to $n/2$. During each such step, we accumulate at most $n$, for a total of at most $n^{3/2}/\sqrt{2}$. An identical argument shows that at most $(n/2)^{3/2}/\sqrt{2}$ is accumulated while going from $n/2$ to $n/4$, and so on. Hence
$$
T(n) \leq \frac{n^{3/2}}{\sqrt{2}} \left(1 + \frac{1}{2^{3/2}} + \frac{1}{4^{3/2}} + \cdots\right) = O(n^{3/2}),
$$
since the geometric series inside the parentheses converges.
Numerical experiments suggest that
$$
T(n) \sim \frac{2}{3} n^{3/2}.
$$
We can show this heuristically as follows. Let us imagine that $T$ is a recurrence in continuous time. Then $T(n) - T(n-\sqrt{n}) \approx \sqrt{n} T'(n)$, and so
$$
T'(n) \approx \sqrt{n}.
$$
Integrating, we get
$$
T(n) \approx \frac{n^{3/2}}{3/2} = \frac{2}{3} n^{3/2}.
$$
This can probably be showed by running the argument above more carefully (replacing $n/2$ with $(1-\epsilon)n$).


How to compare the time-complexity of an optimized algorithm with that of the original? I had an algorithm with time-complexity of $O(h\times w)$, knowing $h$ is the height and $w$ is the width of an image being processed (or a simple matrix of size $h\times w$).

I managed to reduce the range that the algorithm process. So rather than dealing with $h\times w$ elements, it is dealing with $n\times m$ elements, where $n<h$ and $m<w$.

To recapitulate the optimization :

Time-complexity of old algorithm is $O(h\times w)$
Time-complexity of new algorithm is $O(h) + O(n\times m)$

Now my question is : how to express this time complexity optimization in terms of $h$ and $w$ ? is it a real optimization ?

I am not sure what you mean by "complexity optimization".

A proper way to compare complexities is by considering their
ratio, which is defined up to a constant factor. Considering the difference makes no sense, as there is always
the invisible constant factor lurking around, invisible but not
negligible.

However your problem here is that you have several variables, not the
same in both variants of your algorithm, and no indication of how they
relate. If you do not say precisely how $n$ and $m$ relate to $h$ and
$w$, there is nearly nothing that can be done.

Given That all you know is that $n<h$ and $m<w$, the best you can say
is that  $n\times m<h\times w$. But they may differ by a constant
additive term or by a constant multiplicative factor, which does not
change the complexity.

So the best you can say is that $O(m\times n)\subseteq O(h\times w)$,
short of more precision on how $n$ and $m$ relate to $h$ and
$w$

Thus $O(h)+O(m\times n)\subseteq O(h)+O(h\times w)$.

But $O(h)\subseteq O(h\times w)$, because both are linear in $h$ and
the first is constant in $w$ while the second is linear.

Hence you get: $O(h)+O(m\times n)\subseteq O(h\times w)$.

All we know is that the complexity is not worse than before.

But that should not worry you too much. You seem to have the wrong
vision of complexity, when asking:

  is it a real optimization ?

Your optimizations aim at improving performance in your range of
applications.

Complexity does not measure performance but scalability. A
  constant multiplicative factor of ten zillions does not change the
  complexity but has a drastic effect on performance. The matrix
  multiplication algorithm that have the best complexity are never
  used because they have abysmal performance. You have to consider
  huge matrices for them to be any use.

Furthermore, raw complexity on arbitrary measure of the size of the
problem may have little practical meaning in some cases. The relevant
size for some complexity analyses may be the number of occurences of a
specific feature of the problem input, rather than the length of the
problem in number of symbols. Some exponential algorithms are
routinely used without problems because the feature causing the high
complexity is actually rarely used, independently of the input size.

Your modification of the algorithm may be a real optimization, that
may give you an algorithm ten times faster, but this may not show in
complexity analysis.

This is why it is sometimes useful to do precise cost analysis. But
that is more difficult since you must account for the different costs
of different elementary operations (which is not required for
complexity analysis).

A possible way to assess your optimization is benchmarking, rather
than tedious theoretical counting.

Your question did not say whether you were considering worst case or
average complexity. I did not ask because my remarks apply in both
cases.

Note: The fact that the algorithm has better performance, with the same
worst case complexity does not imply that the average complexity was
improved.


Training a model based on polynomial regression and then putting that into a linear regression, vs just using the linear regression I'm doing some machine learning work in python with sklearn. Basically the problem is trying to predict how long an event will take based on 4 correlated pieces of data. What I've been doing is I have four polynomial regression trained on each piece of data respectively. Then I take the output of these polynomial regressions and train a linear regression based on that. Testing this against historically data has show that the two step process has about 10% less sum-squared-error than just using the linear regression. Should I not be doing it this way? What is the theory behind just using a one step process vs. using both steps?

There's no one answer about how you should/shouldn't do it.  There are two perspectives out there:

If it works, go for it. One perspective is: if it gives good results, that's all that matters.  So, if you get more accurate regression, great for you.  Try a bunch of approaches and pick whatever works best (taking care to avoid overfitting).

Model the underlying phenomenom. The other perspective is: choose a model that represents how the underlying physical process works.  So, from this perspective, we can't say what you should do, since you haven't told us how the underlying process works; we have no basis for evaluating whether that's a reasonable way to model reality.

There are many possible models one could imagine that map 4 continuous features $x_1,x_2,x_3,x_4$ to a continuous output $y$.  You could use linear regression:

$$y = a_1 x_1 + a_2 x_2 + a_3 x_3 + a_4 x_4 + b$$

Or you could use polynomial regression:

$$y = p(x_1,x_2,x_3,x_4)$$

where $p(\cdot)$ is some multivariate polynomial in 4 variables with degree at most $d$ (for some $d$ you choose).  Or you could use what you're doing:

$$y = a_1 p_1(x_1) + a_2 p_2(x_2) + a_3 p_3(x_3) + a_4 p_4(x_4) + b$$

where $p_1(\cdot),\dots,p_4(\cdot)$ are univariate polynomials with degree at most $d$.

Or you could fit some other nonlinear function (see nonlinear regression), or  fit a piecewise linear function, or use cubic splines, or use kernel smoothing or LOESS regression (see local regression).  There are so many options.  We can't tell you which to use from the information you've provided.

Advice. Usually, a good rule of thumb is that if you understand the underlying process well, use a model that matches the underlying reality.  If you don't know the underlying process, try multiple approaches and see which works best (using cross-validation to avoid overfitting).


Sort an array with a constant number of unsorted elements I am trying to sort an array that I know to have a constant number of unsorted elements (elements that are not in their right place).
In the solution I looked at they say you can do this in $O(n)$ time:
you can find any unsorted element in $O(n)$ and then move it to the right place in $O(n)$ also. I am not seeing how you can do these things in $O(n)$.
I mean, I thought of an algorithm that iterates from 1 to $n$ ($n$ is length of the array), checks if the element at the index is in it's sorted place and if the answer is no then you can use partition for bringing it to the right place (partition works in $O(n)$).
Because I have a constant number of elements that are not in their right place I will use partition constant $\times n$ times which means the algorithm is $O(n)$ as asked. Problem is that checking for every index if the element in the index is in his right place is $O(n)$ and doing it for every index is $O(n)$ so it sums up to $O(n^2)$ so maybe the solution is not right. (Every other solution I wrote also has this problem)
I will be glad for any help.

Denote the array by $A_1,\ldots,A_n$. If $A_i > A_{i+1}$ then at least one of the two elements is out of place. We scan the array, and each time we find such a pair, we remove both elements. In $O(n)$ time, we obtain a sorted subarray $B$ together with $O(1)$ many unsorted elements, forming a set $C$. We sort $C$ in $O(1)$ and merge it with $B$ in $O(n)$.


How can you iterate through a hash table in constant time? I am studying data structures and the book "How to Think About Algorithms" by Jeff Edmonds (pages 46-47) claim that:

  "Hopefully, all the elements that are in your set happen to be placed into different entries in the table. In this case one can

  determine whether or not an element is contained in the set,
  ask for an arbitrary element form the set,
  determine the number of elements in the set,
  iterate through all the elements,
  and add and delete elements

  in constant time i.e independently of the number of items in the set."

when speaking about hash tables. I don't understand how it is possible to iterate through all the elements in constant time. Shouldn't it be $O(N)$ since we iterate through all of them?

What you said is true. You can't iterate through all the elements in a hash table in constant time. It would take $O(N)$. But the author is not actually talking about all the elements in the hash table, but to iterate though each single element (in which there is only one element, making it constant). It comes down to the assumption here:

"all the elements that are in your set happen to be placed into different entries in the table."

In this case for each element, there is a single node. If this was not true you need to form a link-list for the hash table table, that is when there is collision. Then for each element it's no longer a constant time. But whatever item in the hash table happens to have the longest list.

Again, the explanation isn't clear here. As it looks like the author is saying iterating through all the elements in a hash table, and not iterating through for each element.


The name for this genetic algorithm variant What is the name for this variant of genetic algorithm. I'm sure I have read about this in Wikipedia, but now I could not find it:

There in no thing as sequential population. The phenotypes lives and dies just like people. The death comes after random period of time. During life phenotypes can have children. The better phenotype is (fitness function) the bigger is chance to have (more) children. The better phenotype is the better can be it's candidate form wife or husband. Yes, phenotypes have sex (man or woman).

Most EAs may be divided into generational algorithms, which update the entire population once per iteration, and steady-state algorithms, which update the sample a few candidate solutions at a time.

Steady-state GAs (popularized by the Darrell Whitley and Joan Kauth's GENITOR system) iteratively breed a new child or two, assess their fitness and then reintroduce them directly into the population, thus killing some preexisting individuals to make room (take a look at Essential Metaheuristics by Sean Luke for further details).

So a steady-state GA fits part of the description ("death comes after random period of time").

Other characteristics ("the better phenotype is (fitness function) the bigger is chance to have (more) children") are shared with generational algorithms.

Gender-specific selection / crossover operators / GAs fit the last part of the description ("phenotypes have sex (man or woman)"):

  instead of selecting individuals from a single group for mating, a gender genetic algorithm create two groups and permits mating only between opposite groups; the selection from two groups helps to increase diversity.

Anyway many GA variants based on a more natural governing framework are possible:

delayed reproduction / breeding age (most life forms aren't able to  breed during  the early  stages of  their life);
life span for individuals (no  matter how poor the fitness is, it
would still stay in the population for a length of time) / predetermined death age;
progressive ageing (Individual Aging in Genetic Algorithms by Ashish
Ghosh, Shigeyoshi Tsutsui and Hideo Tanaka);
Age-Layered Population Structure (ALPS) evolutionary algorithms (The Age-Layered Population Structure by Gregory S. Hornby)
...