Why is addition as fast as bit-wise operations in modern processors? I know that bit-wise operations are so fast on modern processors, because they can operate on 32 or 64 bits on parallel, so bit-wise operations take only one clock cycle. However addition is a complex operation that consists of at least one and possibly up to a dozen bit-wise operations, so I naturally thought it will be 3-4 times slower. I was surprised to see after a simple benchmark that addition is exactly as fast as any of the bit-wise operations(XOR, OR, AND etc). Can anyone shed light on this?

Addition is fast because CPU designers have put in the circuitry needed to make it fast.  It does take significantly more gates than bitwise operations, but it is frequent enough that CPU designers have judged it to be worth it.  See https://en.wikipedia.org/wiki/Adder_(electronics).

Both can be made fast enough to execute within a single CPU cycle.  They're not equally fast -- addition requires more gates and more latency than a bitwise operation -- but it's fast enough that a processor can do it in one clock cycle.  There is a per-instruction latency overhead for the instruction decoding and control logic, and the latency for that is significantly larger than the latency to do a bitwise operation, so the difference between the two gets swamped by that overhead.  AProgrammer's answer and Paul92's answer explain those effects well.


Relaxation possibilities of the lower bound worst case sorting algorithms without quantum computation The sorting algorithms (merge-sort, quicksort...) are tought to have an absolutely hard lower bound which can not be outperformed by computation alone and this bound is $n*log_{2}(n)$,
The reason for this bound is that those algorithms are using the division by two devide and conquer method and as such they generate a binary tree that begins at a root and from there on branches two times from each node until it reaches the bottom to produce exactly $n$ leaves at the bottom level.
Since it is a binary tree, it has exactly $log_{2}(n)$ levels from the root down to the leaves and as such it costs $log_{2}(n)$ "computational decisions" to generate the tree and $n$ decisions to walk over all leaves, so $n*log_{2}(n)$ looks absolutely valid at first.
I don't argue about the factor $n$ before the $log_{2}(n)$,  what I argue about is,  why is it everywhere such a strict advocating consensus about to always use $log_{2}(n)$ in computer science.
Imagine for example instead if I don't use the binary devide&conquer method, but if I adress the indices of the list which are prime numbers, using the values of those indices as representational values to compute the differences of the indices between the primes. The resulted tree structure from such an algorithm will have many more branches than two at most of the nodes and the generated tree size will be much much lower.
An computational approximation of an list with 1000000000 and the assumption of having 10 splits instead of two would result in 270 times less computational decisions when the $log_{10}(n)$ insead of the $log_{2}(n)$ would be used and I'm quite confident that this can be relaxed to an even much smaller tree in general, if I'm not oversimplifying it at least.

Fist of all the $\Omega(n \log n)$ lower bound only applies to comparison-based algorithms, that is only to algorithm that can only obtain information on the relative orders of two input elements by pairwise comparisons.
They do not have to be divide and conquer algorithms and they do not have to generate any tree. The lower bound simply follows from the fact that there are $n!$ possible permutations of the input elements and any correct algorithm must be able to output all of them (given the inverse permutation as its input).
This means that the number of branches on the longest computation of the algorithm must be at least:
$$
\log ( n! ) > \log (n/e)^n
=  n \log n - n \log e
>  n \log n - 1.44 n = \Omega(n \log n).
$$
Also, even in the case of comparison based-algorithms, an absolute lower bound of  $n \log n$ (without the constant hidden in the $\Omega(\cdot)$ notation, as you write in the question) on the number of comparisons cannot possibly exist since, when $n=2^k$, each element in Mergesort is compared at most $k-1$ times, showing that the total number of comparisons is at most $n(k-1) = n \log n - n$.
Your proposed algorithm is not clear to me but, in general,
if you change the model of computation by allowing other operations to be performed in addition to comparisons then the $\Omega(n \log n)$ lower bound does not apply anymore.
For example, given any constant $c$, in the word-RAM model you can sort a collection of $n$ elements between $0$ and $n^c$ in linear time using Radix sort, as long as the chosen word size $w$ allows to write $n$ in a (constant number of) memory word(s), as it is usually the case (it is standard to assume $w=\Theta(\log n)$).


Definability of Truth Assignments I have a question about definability of truth assignments. Suppose that I am working in the context of propositional logic. Let me give some definitions first.

Let $L$ be a propositional language with the set $Prop_{L}$ of propositional variables. A truth assignment is a map $v\colon Prop_{L}\to\{F,T\}$. Denote the collection of truth assignments in $L$ by $TA_{L}$. Note that in a language $L$ with $|Prop_{L}|=n$ for some $n\in\mathbb{N}$, $|TA_{L}|=2^{n}$, while in a language with $|Prop_{L}|=\aleph_{0}$ (denumerably many), $|TA_{L}|=2^{\aleph_{0}}=\mathfrak{c}$ (continuum many).

Definition 1. Let $\Sigma$ be a set of propositional formulas. The set of models of $\Sigma$ is
$$Mod(\Sigma):=\{v:v\ \mbox{is a truth assignment and $v(\varphi)=T$ for each $\varphi\in\Sigma$}\}.$$

Definition 2. Let $K\subseteq TA_{L}$. Then $K$ is definable if $K=Mod(\Sigma)$ for some set $\Sigma$ of formulas.

I have tried to prove a couple of things. In a propositional language with only finitely many propositional variables, any set of truth assignments is definable. Now, I want to show that, in a propositional language with denumerably many propositional variables, any finite set of truth assignments is definable. Imitating the idea in the proof about finite language, I have an outline of the proof about infinite language. Here is the detail:

Convention.
Let $p$ be a propositional variable and $v$ a truth assignment. Define
$$
p^{v}:=
\begin{cases}
p &\mbox{if}\ v(p)=T;\\
\neg p &\mbox{otherwise}.
\end{cases}
$$
Then it can be seen easily that $\widehat{v}(p^{v})=T$.
(Here $\widehat{v}$ denotes the extension of $v$ to the set of propositional formulas.)

Claim. In a language $L$ with $|Prop_{L}|=\aleph_{0}$, any finite set of truth assignments is definable.

Proof.
Assume that $Prop_{L}=\{p_{1},p_{2},\ldots\}$. Let $K\subseteq TA_{L}$. Assume that $K$ is finite. Then $K=\{v_{1},v_{2},\ldots,v_{k}\}$ for some $k\in\mathbb{N}$. Let $1\leq i\leq k$. For each $j\in\mathbb{N}$, define
$$\varphi^{i}_{j}:=p^{v_{i}}_{1}\wedge p^{v_{i}}_{2}\wedge\cdots\wedge p^{v_{i}}_{j}$$
and define
$$\chi_{j}:=\varphi^{1}_{j}\vee\varphi^{2}_{j}\vee\cdots\vee\varphi^{k}_{j}.$$
Let $\Sigma=\{\chi_{j}:j\in\mathbb{N}\}$. Claim that $K=Mod(\Sigma)$.

Now, the part $K\subseteq Mod(\Sigma)$ is easy. What is hard for me is the reverse inclusion: any truth assignment satisfying $\Sigma$ must be $v_{i}$ for some $1\leq i\leq k$. Since I am dealing with infinitely many propositional variables, to show that two truth assignments coincide is to show that they agree on infinitely many propositional variables. Yet I have no idea how to show that, because truth assignments in $K$ seem to involve only finitely many propositional variables. Could anyone please advise me about this?

Any suggestions would be greatly appreciated :)

Let $T=\{\tau_1,\cdots, \tau_k\}$ be the set of truth assignments. Consider the tree of the truth assignments $2^\omega$.

Consider the formula
$\Gamma_T = \{ \underset{\tau \in T}\lor \tau_{|n} \mid n \in \omega\}$
where $\tau_{|n}$ is the formula that expresses $\tau$ up to atom $p_n$, i.e. $\underset{i\leq n}\wedge l_i(\tau)$
where
$l_i(\tau) = \begin{cases}
p_i & \tau(p_i)=\top \\
\lnot p_i & \tau(p_i)= \bot
\end{cases}$.

It is easy to show that every $\tau \in T$ we have $\tau \vDash \Gamma_T$.

For any $\tau \notin T$, there is some $n\in \omega$ such that $\tau_{|n}$ is different from those in $T$ and therefore $\tau$ does not satisfy $\underset{\tau \in T}\lor \tau_{|n}$ and therefore $\tau\nvDash \Gamma_T$.

There is a topological characterization of the sets of truth assignments that can be defined. Consider $2^\omega$ as space of points with product topology. Consider the sets of points that can be captured using sets of formulas. They are closed under finite unions (consider the disjunctions of the pairs of formulas from the product) and arbitrary intersections (union of two sets).

You may be interested in Stone duality and type (model theory).


Block matching pattern matching problem I've struggling with this problem for a while.

Given text $T=t_1t_2\ldots t_n$ and pattern $P=p_1p_2\ldots p_m$ over alphabet $\Sigma=\mathbb{N}$, we say there's a block matching of $P$ in index $i$ if there exist $m$ successive blocks $S_1,\ldots,S_m$ such that $$p_1=\sum_{s_1 \in S_1}s_1 \land p_2=\sum_{s_2 \in S_2}s_2 \land \cdots \land p_m=\sum_{s_m \in S_m}s_m. $$

For example:
$T=\text{1 2 3 5 1 2 3 2}$
$P=\text{6 5}$

Then we have block matching in index 1 because $1+2+3=6$ and $5=5$.
Schematically it looks like: $\text{|1 2 3||5| 1 2 3 2}$

We also have a block matching in index 4 because $5+1=6$ and $2+3=5$.
Schematically it looks like: $\text{ 1 2 3 |5 1||2 3| 2}$

The task is to find all indices where we have block matching.

I couldn't do better then a $\mathcal{O}(mn)$ but I believe there's a FFT application here.

Any hints?

If the numbers are all integers at most $k$, then you can apply a fast algorithm for substring matching with don't-care symbols (see below) to solve the problem in $O(kn(\log m + \log k))$ time by applying the following transformation:

Map each text character $t$ to $t-1$ zeros followed by a 1.
Map each pattern character $p$ to $p-1$ don't-care symbols followed by a 1, and also prepend a 1 to the overall pattern.

Basically, 1s represent "boundaries" in both strings, and we look for a way to make each boundary in the pattern line up with some boundary in the text.

This paper describes an $O(n+m+\alpha)$-time algorithm, where $\alpha$ is "the total number of occurrences of the subpatterns" (I didn't read the full paper, so I'm not sure exactly what that means).  In any case it mentions the 1974 algorithm of Fischer and Paterson, "String matching and other products", which solves the problem in $O(n\log m\log \Sigma)$ time -- though that link is behind a paywall, googling should find other information on it.


Relations between different time complexities of an algorithm If I have an algorithm A that, in the worst case, has a lower bound of $Ω(n\log n)$ and an upper bound of $O(n²)$, how can I go about determining possible time complexities for best and average cases?

For instance, only one of the following is possible:

a. Best case $\Theta(n)$

b. Worst case $\Theta(n\sqrt{n})$

c. Average case $\Theta(n^3)$

d. Worst case $\Theta(n)$

Now right off the bat I know we can eliminate (d) since it’s also dealing with the worst case, and being that $n$ is out of the given bounds, falling below $n\log n$.

What I’m stuck on is how to approach the other worst case option since it falls in the range and am even more confused about how to deal with the two choices that aren’t even worst case.

Let us use the following notations:

$L$ is any lower bound on the running time.
$U$ is any upper bound on the running time.
$B$ is the best case running time.
$W$ is the worst case running time.
$A$ is the average case running time.

These parameters are related in the following way:

$$ L \leq B \leq A \leq W \leq U. $$

You can solve the question using these relations.

Make sure that you understand why they hold.


An axiomatic theory of computational models? There are many different computational models, e.g. Turing machines, register machines, lambda calculus, etc.

I am wondering if there exists an axiomatization of computation, that abstracts away from the specifically constructed computational model.

I.e. is there a more general theory about computation that deals with computational machines that are not perfectly specified, but that still captures their common characteristic as computation machines?

The question "what is a computational model" is quite open ended and is difficult to answer definitely. It's a bit like asking "what is geometry". But people have given some answers.

As far as I can understand you, you are looking for a general theory of computation (so, not a model that "contains other, for what's that supposed to mean, nor an "axiomatization" of a specific thing). One such theory is offered by partial combinatory algebras (PCA), which are very simple structures that subsume many models of computation, including: Turing machines (with and without oracles), $\lambda$-calculus (with many of its extensions), enumeration operators, and even topological models of computation. There are further variants of PCAs: ordered PCAs, typed PCAs, etc.

One should never just "collect models of computation" but also ask how to relate them, so we should think about transformations between PCAs. John Longley gave a very good account of these, namely the applicative morphisms. Speaking a bit vaguely, an applicative morphism is an interpretr of one PCA implemented in another PCA.

If you are interested in this topic you can consul Jaap van Oosten's book on realizability.


Generate integer from 0 to 1 with equal probability I am trying to get around this problem of my own making. I want to generate 0 or 1 with another function(gr0_4()) which generates random number from 0 to 4.

I am wondering if I can approach this way:

a). if gr0_4() = 0 or 1 then I will use 0

b). if gr0_4() = 2 or 3 then I will use 1

c). if gr0_4() = 4 I will repeat the a) and b) steps.

Is my understanding correct that the "a" and "b" step each has 50% probability of happening?

def gr0_1():
  while True:
    x = gr0_4()
      if x == 0 or x == 1:
        return 0
      elif x == 0 or x == 1:
        return 1

What if I want to use gr0_1() to create gr1_7() i.e. create number between 1 to 7 with equal probability?

Can I use below reasoning to create that function gr1_1().

As 7 consists of 3 bits. I can generate each bit with equal probability using gr0_1(). So I will call gr0_1() three times and based on that value I get, I will set/unset the corresponding bits to generate a number between 1 to 7 including the numbers 1 and 7. However I can get the number 0 but I don't want that so I will repeat the process again. Will the probability of each number generation between 1 to 7 will be 1/7 in that case also?

Some simple mathematical calculation will be nice to answer this. I tried to read up on rejection sampling but couldn't understand much.

Yes, this is exactly rejection sampling and it works in the way you think it works, assuming that your initial procedure gr_04() generates the numbers $0$–$4$ with equal probability (you say it's random but you don't say it's uniform).

If $X$ is distributed uniformly on $\{0, \dots, 4\}$, then $\Pr(x\in\{0,1\}) = \Pr(x\in\{2,3\}) = 2/5$. With probability $1/5$, you'll have to try again but, on your second attempt, the probability of getting $0$ or $1$ is still equal to the probability of getting $2$ or $3$.  The number of attempts you have to make before you get something in $\{0, \dots, 3\}$ is just a geometric random variable with parameter $p=4/5$ and this has expectation $(1-p)/p = 1/4$ so, on average, you'll have to make $5/4$ calls to gr_04(), including the one that succeeds.

The analysis of your second example is similar: your procedure generates each possible answer with the same probability and each attempt succeeds with probability $7/8$, so you'll need an average of $8/7$ calls to gr_01(), which means an average of $(8/7)(5/4)=10/7$ calls to gr_04().


Meaning of $NL$ Complexity Class I am aware of the complexity classes $P$, $NP$ and $L$. But I am not clear what $NL$ or Non-deterministic Log Space intuitively means. The part what I am unclear about is what is the meaning of Non-deterministic Space?

A Turing machine in a $L$ case would read an input, read/write on the work tape that is logarithmic in size, update its internal state, move the read write head on the work-tape and read head on the input tape. And at appropriate time it halts.

What does Non-determinism on work tape mean and how does the Turing Machine behave. I am totally lost on this one? An intuitive explanation would help.

Nondeterminism is not about tape or space. It is just a computational model.

One way of thinking of how a nondeterministic TM works is parallel computation. Given an input $x$, a nondeterministic TM may start many parallel (branches of) computation and wait for answers. If all branches terminate then the whole computation terminates. In addition if at least one of them  terminates with YES then the TM accepts the input. In particular a nondeterministic TM may run exponentially many branches at the same time.
However a deterministic TM is not allowed to run more than one process (branch) at the same, so less powerful in terms of time. But in terms of decidability they are equivalent.

For example consider 3SAT problem with variables $x_1, \dots, x_n$. Then on nondeterministic TM we can check all $2^n$ settings of the variables at the same time, while on a deterministic TM we will have to check each settings one by one in sequence.

NOTE: unlike a deterministic TM a nondeterministic TM is a hypothetical abstract model which is not something we use in our everyday life.

Definition of space complexity for nondeterministic Turing machines:

  If $M$is a nondeterministic TM where all branches halt on all inputs then its space complexity is the maximum number of tape cells it scans on any branch of its computation.

In particular if a TM scans at most $O(log(n))$ working tape cells on every input of length $n$ then we say its space complexity is logarithmic. It also worth noting that requiring $O(log(n))$ space does not restrict running time. A TM may decide in exponential time but still use logarithmic space.

Typically, when dealing with sublinear, $log(n)$, space bounds we use Turing machines with two tapes: input read only tape, and working tape which contributes to space complexity.

Then formally $L = SPACE(log(n))$. $L$ is the class of languages that are decidable in logarithmic space on a deterministic TM. That means that a deterministic TM decides using no more than log space. If we switch from a deterministic TM to a nondeterministic TM then we have $NL = NSPACE(log(n))$, that is, the class of languages that are decidable in logarithmic space on a nondeterministic TM.

Thus, meaning, or more formally members, of $NL$ complexity class is all languages decidable:
1) on nondeterministic two tape TM
2) using at most $ O(log(n))$ space on work tape.

Example: the language of the problem deciding for a graph whether or not there is a simple path between nodes $s$ and $t$. This language is in $ NL$ class, but if it is in $L$ class is unknown.


Simple way to prove $\left \{ 0^{n}1^{m} \mid (n-m) \bmod 5=0 \right \}$ is regular? Prove: $\left \{ 0^{n}1^{m} \mid (n-m) \bmod 5=0 \right \}$ is regular.

Is it reasonable to get a DFA with at least 30 states for this language? is there an easier way to prove it is regular?

$(n-m)\bmod 5$ can only be $0,1,2,3,4$. So intuitively, the language in the question is a regular language. We can show that conclusion rigorously in the following two ways.
Regular expression
The simplest way is to verify that the language is described by the following regular expression.
$$(00000)^*(\epsilon+01+0011+000111+00001111)(11111)^*.$$
Intuitively, the language consists of words each of which is zero or more five 0s, followed by some number of 0s, followed by the same number of 1s, followed by zero of more five 1s.

Minimal DFA
Here are the states of the minimal DFA for this language.

$Z_{0}$, which represents words each of which is zero or more five 0s.
$Z_{1}$, which represents words each of which is zero or more five 0s, followed by 0.
$Z_{2}$, which represents words each of which is zero or more five 0s, followed by 00.
$Z_{3}$, which represents words each of which is zero or more five 0s, followed by 000.
$Z_{4}$, which represents words each of which is zero or more five 0s, followed by 0000.
$S_{0}$, which represents words each of which is zero or more five 0s, followed by nothing or 01 or 0011 or 000111 or 00001111, followed by zero or more five 1s, ending with 1.
$S_{1}$, which represents words each of which is zero or more five 0s, followed by 0 or 001, or 00011 or 0000111 or 1111, followed by zero or more five 1s, ending with 1.
$S_{2}$, which represents words each of which is zero or more five 0s, followed by 00 or 0001 or 000011 or 111 or 01111, followed by zero or more five 1s, ending with 1.
$S_{3}$, which represents words each of which is zero or more five 0s, followed by 000 or 00001 or 11 or 0111 or 0001111, followed by zero or more five 1s, ending with 1.
$S_{4}$, which represents words each of which is zero or more five 0s, followed by 0000 or 1 or 011 or 00111 or 0001111, followed by zero or more five 1s, ending with 1.
$R$, which represents all other words, which are words that are not of the form $0^*1^*$.

In other words, besides the "rejecting" state $R$ that behaves as a black hole, we have, for $i=0,1,2,3,4$,

a state $Z_i$ which represents words of the form $0^*$ whose number of 0s is the same as $i$ modulo 5.
a state $S_i$ which represents words of the form $0^*1^*1$ whose number of 0s is the same as $i$ plus its number of 1s modulo 5.

It should be not be difficult for you to figure out the initial state, the accepting states and the transitions between the states.

Is it reasonable to get a DFA with at least 30 states for this language?

It is totally fine if you can construct a DFA with 30 states or 2019 states for this language. That will show the language is regular.
On the other hand, it is sometimes interesting or helpful or challenging to find the DFA with the minimal number of states. For this language, 11 states is the minimum.

Here are two related exercises.
Exercise 1. Show $\left \{ 0^m1^n \mid (n-m) \bmod 5=2 \right \}$ is a regular language. How many states are there in the minimal DFA for it?

Exercise 2. Show $\left \{ 0^k1^m2^n \mid (k+m-n) \bmod 2=0 \right \}$ is a regular language. How many states are there in the minimal DFA for it?


Does a computation tree for a probabilistic Turing machine have to be a binary tree? Ever example of computation on a probabilistic Turing machine that I have read uses only a binary tree to show the computational branches of a probabilistic Turing machine. I know that an NTM may use as many branches as needed during a computation, so is this also the case for a PTM? Or is a PTM limited to only binary branching?

There are many ways to think of how a probabilistic Turing machine works.  One way is to imagine that it has the ability to flip a fair coin (sample a random bit) at any point.  In that case, it's reasonable to imagine a binary tree, where each branch corresponds to a coin flip -- the fact that we are choosing a random bit / flipping a 2-sided coin is why it is a binary tree.  Another way to think of a probabilistic Turing machine is that it has an additional input tape that is full of random bits.  There you could imagine a binary tree, which each branch corresponds to another bit on that additional input tape.

Typically probabilistic Turing machines can sample a random bit, i.e., a random number from the set {0,1}.  If you want a random number from a different range, you must emulate that by repeatedly sampling random bits and doing something with them.


NP Completeness of 3-SAT problem I have started reading on algorithmic complexity for my thesis work. Already have studied on Polynomial time reducibility, NP-Complete, NP-Hard. Now trying to prove NP completeness of some of the classical problems. I have started with 3-SAT problem.
3-SAT problem — was shown to be NP-complete:

Input: A boolean Formula F in CNF where each clause contains at most three variables.
Question: Is that formula satisfiable?

Show now that the simple 3-SAT problem is also NP-complete:

Input: A boolean Formula F in CNF where each clause contains at most three variables and only clauses of length two may contain negated variables.
Question: Is that formula satisfiable?

Can any please explain the main idea? Thank you in advance.

Main idea: For each variable $x_i$ introduce a new variable $y_i$ and add a new clause $(\lnot x_i, \lnot y_i)$. Replace each occurence of $\lnot x_i$ in the original clauses by $y_i$.

The new clauses ensure that $y_i$ can be set to true if and only if $x_i$ is false. Thus we neither add nor remove satisfying assignments for the original clauses, while the new clauses can always be satisfied.


NP-hardness reductions Suppose I have two generic problems $A_{1}$ and $A_{2}$: the instance of $A_{i}$ is a graph $G$ and a number $t$, and the question is whether a certain parameter $P_{i}(G)$ is at least $t$.

Suppose I want to reduce the NP-c problem $A_{1}$ to $A_{2}$. If I can show that $P_{1}(G) \geq x$ if and only if $P_{2}(G) \geq y$ for any $G$ with at least say $100$ vertices, do I have an admissible reduction?

If your problem is with the 100 vertices limitation, then you're in the clear.
Consider the following reduction: given input $\left( G,t \right)$, if $G$ has under 100 vertices, exhaustively test all witnesses and check if $\left( G,t \right)\in A_1$, this can be done since $A_1\in NP$. Depending on whether or not $\left( G,t \right)\in A_1$ output some constant word in/not in $A_2$.

If G has more than 100 vertices, then your reduction outputs $\left(G,y\left(G,t\right)\right)$. Since you proved $\left( G,t \right)\in A_1 \iff \left(G,y\left(G,t\right)\right)\in A_2$ it's a reduction from $A_1$ to $A_2$. You will probably want (if you're dealing with polynomial time reductions) to show that $y\left(G,t\right)$ is computable in polynomial time.

The asymptotic behavior of the reduction's running time does not depend on how you treat small inputs (in this case, graphs with less than 100 vertices).

Edit: I should note that inputs can get arbitrarily large while keeping the graph small, by increasing $t$. However i assume that (as is with many natural graph problems e.g. clique, independent set) that if $t\ge f(|V_G|)$ for some increasing function $f$, you can simply decide whether or not $(G,t)\in A_1$.


Shannon Entropy of 0.922, 3 Distinct Values Given a string of values $AAAAAAAABC$, the Shannon Entropy in log base $2$ comes to $0.922$. From what I understand, in base $2$ the Shannon Entropy rounded up is the minimum number of bits in binary to represent a single one of the values.

Taken from the introduction on this wikipedia page:

https://en.wikipedia.org/wiki/Entropy_%28information_theory%29

So, how can three values be represented by one bit? $A$ could be $1$, $B$ could be $0$; but how could you represent $C$?

Thank you in advance.

Here is a concrete encoding that can represent each symbol in less than 1 bit on average:

First, split the input string into pairs of successive characters (e.g. AAAAAAAABC becomes AA|AA|AA|AA|BC). Then encode AA as 0, AB as 100, AC as 101, BA as 110, CA as 1110, BB as 111100, BC as 111101, CB as 111110, CC as 111111.
I've not said what happens if there is an odd number of symbols, but you can just encode the last symbol using some arbitrary encoding, it doesn't really matter when the input is long.

This is a Huffman code for the distribution of independent pairs of symbols, and corresponds to choosing $n = 2$ in Yuval's answer. Larger $n$ would lead to even better codes (approaching the Shannon entropy in the limit, as he mentioned).

The average number of bits per symbol pair for the above encoding is
$$\frac{8}{10} \cdot \frac{8}{10} \cdot 1 + 3 \cdot \frac{8}{10} \cdot \frac{1}{10} \cdot 3 + \frac{1}{10} \cdot \frac{8}{10} \cdot 4 + 4 \cdot \frac{1}{10} \cdot \frac{1}{10} \cdot 6 = 1.92$$
i.e. $1.92/2 = 0.96$ bits per symbol, not that far from the Shannon entropy actually for such a simple encoding.


Why is $\log n = O(2^n)$? In my theoretical computer science book I have the following statement regarding the space complexity of $f(n)=2^n$:

$$\log(n) = O(f(n))$$

I can't understand how this is true, any help will be greatly appreciated.

As stated, $\log (n) = O (2^n)$ is trivially true.

All that it says is that $\log n$, in the end, grows no faster than $2^n$. For $2^n$, you can substitute $n$, $\sqrt n$, indeed any root of $n$.

However carelessly stated, I think this really refers to the following:

To represent a number of size $2^n$, you need $n$ bits.
So, to represent a number of size $n$, you need $\log n$ bits.

Bits are a measure of space.

I made heavy weather of this before, as I thought it was referring to the time it takes to calculate $2^n$. In case it is, I'll leave this in:

For $n$ a non-negative integer, and $f(n) = 2^n$

$$
f(n) =
\begin{cases}
1 &\text{for }\, n = 0 \\
(f (n \div 2))^2\times 2^{(n \mod 2)} &\text{for}\; n \gt 0
\end{cases}$$

The implied algorithm is clearly $\Theta (log \, n)$. But this is time complexity. In space complexity, it is $\Theta(1)$.

$\Theta (f)$ are the functions that, adapting the words of Wolfram
Mathworld, are no worse but also no better than $f$.
$O (f)$ are the functions that are no worse than $f$.


How to teach abstraction needed for programming? I experience that my students are fixed to compute with concrete values and are not keen to think in terms of general solution like creating a mathematical function $f(n)$ , needed to write programming functions f(n).

What is a good method of teaching them this lesson, becoming able to think in abstractions like functions on natural numbers?

To the extent that this question is on topic here (that is, without reference to literature on mathematical education), I would propose that experimenting with concrete instances is not antithetical to the development of abstract concepts.

In an educational setting in computer science, it should be clearly stated and agreed upon that formal reasoning is the goal, and aquiring an intuitive grasp on things is not enough. After this is established (not trivial, literally counterintuitive), abstractions and concrete examples can help each other, not get in the way of each other.

The thing is, formal reasoning is not something that we do, it is what we are as a field - which is why studying the history of computing is so important. It can be tedious though, unnerving sometimes. It must be gradually developed as a habit. Intuitions are naturally captivating, and that is why we tend to rely on them to motivate our students, but there is something captivating about formalization too. Our challenge is to bring it to the center of the stage.


New Applications of Network Flow I am thinking of explaining the topic of Network flow to an audience of computer sciecne students, and I want to make it more enjoyable by giving some real life examples where a software Developer may find Network Flow useful.
I want to refrain from using standard problems like Baseball problem, marriage problem, edge disjoint.
I need Ideas for such problem which needs to be represented as a graph and then using Network flow we can find the solution.

Network flow has been used for all sorts of interesting and surprising tasks in computer vision and image processing.  For instance, it has been used for image segmentation, image stitching, seam carving, image denoising, stereo image correspondence, and more.

See, e.g., https://en.wikipedia.org/wiki/Graph_cuts_in_computer_vision, What's the relationship of max-flow-min-cut and Markov Random Fields?, https://cs.stackexchange.com/a/37423/755, https://en.wikipedia.org/wiki/Image_segmentation#Graph_partitioning_methods


Element wise product sum of two arrays I have two arrays, namely $a$ and $b$. Both have the same length $n$. I have to find the maximum value of $\sum a_i b_j$, in which every element can be used at most one time. My algorithm for solving this problem is:

Sort both $a$ and $b$ in non increasing order.
Pick the values from the array in order of greatest to smallest. Calculate their product and add them to sum.

On the arrays $a = \{2,3,4\}$ and $b = \{4,5,6\}$, the algorithm runs as follows:

Firstly, sorting the arrays: $a = \{4,3,2\}$ and $b = \{6,5,4\}$.

Then picking values from the first to last, gives the answer $(4\cdot6) + (3\cdot5) + (2\cdot4) = 24 + 15 + 8 = 47$.

Here what I have used is a greedy algorithm. How to prove its correctness? What I want to know is, how to prove that this algorithm always gives the maximum answer?

Generally, to prove a greedy algorithm is optimal what you do is come up with a theorem that captures the idea of “moving away from” the greedy strategy and show that that decreases the optimal value. It’s important that you phrase the theorem in a way that can be iteratively applied, as otherwise it might be that the objective function goes down immediately after departing from the greedy algorithm, and then goes back up. In this case, you want

  Theorem: If $a\geq b$ and $c\geq d$ then $ac+ bd\geq ad+bc$

Given any way of pairing numbers, this theorem says that if you swap two numbers so that you move closer to the greedy algorithm then the value cannot go down, and if you swap two numbers so that you move further from the greedy algorithm the value cannot go up. So prove this, and the correctness of the greedy algorithm follows.

It’s sufficient to consider only vectors of length two because any permutation of the vectors can be generated from exchanging two numbers. Equivalently, $S_n$ is generated by its two-cycles for every $n>1$


Regular expression containing lambda What is the meaning of lambda here:
$$(b+c)^*(a+\lambda)(b+c)^*(a+\lambda)(b+c)^*(a+\lambda)(b+c)^*$$.

I know that lambda is used in the context of NFA?

Let's suppose we break down the expression to:$$(b+c)^*(a+\lambda)(b+c)^*$$

and to:$$(b+c)^*(a+\lambda)(b+c)^*(a+\lambda)(b+c)^*$$

How the above would generate an empty string?
Somebody please guide me.

Zulfi.

To generate an empty string you take: $(b+c)^*$ as $\epsilon$, and all the following elements which have a Kleene-star as $\epsilon$ (I will use $\epsilon$ instead of $\lambda$).

Then you have: $$\epsilon(a+\epsilon)\epsilon(a+\epsilon)\epsilon$$
Which is equivalent to: $$(a+\epsilon)(a+\epsilon)$$

Which is essentially picking two options a or $\epsilon$ twice back to back. If you take $\epsilon$ transition each time, which is actually a transition that does not consume an input, it will essentially accept an empty string as input.


Is the "data path cycle" the same thing of the "fetch-decode-execute cycle"? I am reading the book Structured Computer Organization (5th edition) by Tanenbaum and at a certain point, in the second chapter, he talks about data path cycle and fetch-decode-execute cycle, and I am not understanding if they are really the same thing.

The data path cycle should be the number of small and minimal steps that a CPU goes through each cycle. On the other hand, the fetch-decode-execute cycle is the number of small steps that could be generalised like this:

Fetch the instruction from the memory and put it into a register
Change programming counter to point to the next instruction
Determine the type of the instruction fetched
If the instruction uses a word, determine where it is
Fetch the word, if needed, into a CPU register
Execute instruction
Go to step 1.

The fetch-decode-execute cycle is common to all computers, so each data path cycle should be a fetch-decode-execute cycle, right?

Data path cycle is not widely used terminology.  I believe Tanenbaum made it up.  I don't have the 5th edition, but if I look up Tanenbaum's slides on Google (for example: http://www.verlab.dcc.ufmg.br/_media/cursos/arquitetura/2011-1/transparencias/tanembaum_4.pdf) it appears that he is using data path cycle to refer to a single clock cycle.  As in "the amount of time for all the signals to propagate all the way through the data path."  Think of it as the amount of time required to perform one micro-instruction.

But Tanenbaum uses a multi-cycle-per-instruction microcoded organization, so the fetch-decode-execute cycle (for instructions rather than microinstructions) usually involves multiple clock cycles.


Is there a theory of exception hierarchies? I'm familiar with a dozen of programming languages which have exceptions in some way, yet I came to witness two "pathological" tendencies.

There doesn't seem to be a common pattern or hierarchy of exceptions. Every language basically rolls its own version, and if the exceptions make it into the standard, then the kinds of exceptions that one finds in the standard would be rather arbitrary (mostly those which were implemented while creating language tools, such as reading source code from string or an exception to invoke debugger, or the one which happens when the file cannot be found etc.)

Exceptions defined by the language are very rarely reused by user programs. There would be usually one or two popular exceptions ("not implement" for example). Though most times programmers will create their own exceptions. (Compare this to, for example, creating new numeric types or new collection types).

This looks like a terrible omission to me. How comes no one knows what kinds of errors will be needed in user programs? I was hoping for there to be a kind of nice hierarchy, similar to numeric types, collections, object system etc.
Worse yet, Goolge and Wikipedia provide very little help on the subject. So far I've only found a paper on functional exception which opens in a passage:

This paper argues that lazy functional programming not only makes
built-in exception handling mechanism unnecessary, but provides a
powerful tool for developing and transforming programs that use
exceptions

(A Functional Theory of Exceptions, Mike Spivey, 1988)
But I think that exceptions are good. I don't want to transform programs that use exceptions, on the contrary, I want to make the use of exceptions less chaotic.
The question:
Is there a theory of exceptions? If so, what is it called? What are, if any, the cornerstone works outlining the basis of it?

There's a large number of publications on exceptions, with quite a few theoretical investigations. Here is an unstructured and far from complete list with some examples. Sorry, I don't have
time at the moment for a more focussed reply.

B. Randell, System Structure for Software Fault Tolerance.
J. B. Goodenough. Exception handling: Issues and a proposed notation.
J. B. Goodenough. Structured exception handling.
B. G. Ryder, M. L. Soffa, Influences on the Design of Exception Handling.
D. Teller, A. Spiwack, T. Varoquaux, Catch me if you can: Towards type-safe, hierarchical, lightweight, polymorphic and efficient error management in OCaml.
X. Leroy, F. Pessaux, Type-based analysis of uncaught exceptions.
R. Miller, A. Tripathi, Issues with Exception Handling in Object-Oriented Systems.
S. Drew, K. J. Gough, J. Ledermann, Implementing Zero-Overhead Exception Handling.
B. Stroustrup, Exception Safety: Concepts and Techniques.
D. Malayeri, J. Aldrich, Practical Exception Specifications.
H. Nakano, A Constructive Formalization of the Catch and Throw Mechanism.
A. Nanevski, A Modal Calculus for Exception Handling.
P. de Groote, A Simple Calculus of Exception Handling.
H. Thielecke, On Exceptions and Continuations in Presence of State.
J. G. Riecke, H. Thielecke, Typed Exceptions and Continuations Cannot Macro-Express Each Other.
M. van Dooren, E. Steegmans, Combining the Robustness of Checked Exceptions with the Flexibility of Unchecked Exceptions using Anchored Exception Declarations.
J. A. Vaughan, A logical interpretation of Java-style exceptions.
S. Marlow, S. Peyton Jones, A. Moran, Asynchronous Exceptions in Haskell.
B. Jacobs, F. Piessens, Failboxes: Provably Safe Exception Handling.


Number of satisfying assignments How many satisfying assignments does the following formula have?

(x1 ∨ x¯2 ∨ x¯3)(x1 ∨ x2)(x¯1 ∨ x¯2)

You have 8 options:

T F F

T T F

T T T

F T T

F F T

F F F

T F T

F T F

When the first column is x1 the second is x2 and the third x3

Lets try each one:
(T or T or T)and(T or F)and(F or T)=T and T and T=T

(T or F or T)and(T or T)and(F or F)=F
And so on...

You can continue from here and you will get the right answer


Find the kth smallest element in an unsorted array of non-negative integers I need to find the kth smallest element in an unsorted array of non-negative integer.

kth smallest element is the minimum possible n such that there are at least kth elements <= n.

The rub here is that the array is read only so it can't be modified. Also i have to do it in constant space.

Can anybody help come up with the most optimal solution ?

There is a simple randomized algorithm running in expected $O(n\log n)$ time. The algorithm is a variant of the better known algorithm QuickSelect.

The algorithm maintains a pair of values $a \leq b$, initially $-\infty$ and $+\infty$ (or, the minimum and maximum values of the array). At each round, it chooses a uniformly random element $c$ in the range $[a,b]$ from the array, and computes its order statistics, i.e., the value $\ell$ such that $c$ is the $\ell$th smallest element in the array.

If $\ell = k$, then we return $c$.
If $\ell > k$, we replace $b$ with $c$.
If $\ell < k$, we replace $a$ with $c$.

If $a = b$ then we return $a$. Otherwise, we continue for one more iteration.

Each iteration takes time $O(n)$, so in order to estimate the running time of the algorithm, we need to estimate the number of rounds. We will keep track of the number of "live" elements, initially $n$. The algorithm ends when the number of live elements gets down to 1 (or even sooner, if there are repeated elements).

Let us denote by $n_t$ the number of elements after $t$ rounds, so that $n_0 = n$. The exact distribution of $n_{t+1}$ given $n_t$ depends on the location of the $k$th order statistics among the live elements. Let us suppose that the $k$th order statistics is the $\ell$th live element. Without loss of generality, $\ell \leq (n_t+1)/2$. Suppose that we choose the $r$th order statistic, so $r$ is uniform over $1,\ldots,n_t$. Then:

If $r = 1,\ldots,\ell-1$ then $n_{t+1} = n_t - (r-1)$.
If $r = \ell$ then $n_{t+1} = 0$.
If $r = \ell+1,\ldots,n_t$ then $n_{t+1} = r$.

In total, the expected value of $n_{t+1}$ is
$$
\frac{1}{n_t} [(n_t + \cdots + n_t-\ell+2) + (\ell+1 + \cdots + n_t)].
$$
The number of summands is constant, and the worst case is when $\ell = (n_t+1)/2$, in which case the expected value of $n_{t+1}$ is
$$
\frac{(\frac{n_t+1}{2}+n_t)\frac{n_t-1}{2}}{n_t} \leq \frac{3}{4}n_t.
$$
Induction shows that $\mathbb{E}[n_t] \leq (3/4)^t n$, and so the expectation drops below 1 for $t = O(\log n)$.

While this doesn't quite show that the expected number of iterations is $O(\log n)$, more refined arguments do, and they moreover show that the number of iterations is $O(\log n)$ with high probability.

Here are some hints on how to implement the algorithm. The crucial step is to choose a uniformly random element $c$ in the range $[a,b]$ from the array. There are at least two ways to go about it, both taking $O(n)$:

Reservoir sampling

Initialize $N = 0$ and $X = \bot$.
Go over all elements of the array. For each element $x$, if $a \leq x \leq b$:

Increment $N$.
Replace $X$ with $x$ with probability $1/N$.

Return $X$.

Linear scan

Count the number of elements in the array between $a$ and $b$ — say the answer is $N$.
Draw a random integer $i$ between 1 and $N$.
Go over the array again, and return the $i$th element between $a$ and $b$.


How does one choose an optimal alphabet for finding a Huffman encoding? Huffman encoding will perform best when the distribution of symbols of an alphabet that the string to be encoded uses is dyadic.

Given an arbitrary bit string S, how can we find the best alphabet for encoding? Suppose S is an ASCII file. Then given the regularity of 1-byte characters that such files exhibit, we would expect that an optimal, or at least pretty good, alphabet should contain, say, 8-bit or 16-bit words (which we then build codes for after constructing the Huffman tree).

Is there an algorithm for finding the optimal word width (assume we use constant-length words).

I would guess that to evaluate an alphabet, it would only be fair if we considered the costs of storing the actual encoding as well. This addresses the case where the alphabet is just one symbol - the entire original string. Technically the message would just be one bit, but the the encoding tree that's stored would have to indicate that the one bit used is a code for the original string, so we've just increased our message by two bits trivially!

(Constant-length encoding information such as width size, encoding table size, etc., need not be considered for the comparisons, of course).

The size required to store the Huffman code table scales like the number of codewords. We expect the number of unique $k$-letter words to be exponential in $k$, in fact roughly $2^{kH}$, where $H$ in the source entropy, though since the file is not infinite, for large $k$ we will actually see less. Still, this suggests that for logarithmically large $k$, most of the $k$-letter strings will be almost unique, and so the overall compression for such a $k$ would typically be quite small. In view of that, you can just try several values of $k$, and choose the best one. After you do some such experiments, you can formulate and perhaps prove a hypothesis as to the optimal value of $k$ in different situations.


"Most Similar Vector Problem" on an Integer Lattice I am currently working on problem that I think could be expressed as an integer lattice problem, and hoping to find some guidance on this forum.

Given $u \in \mathbb{R}^n$ and a bounded integer lattice $L = \mathbb{Z}^n \cap [-M,M]^n$, I would like to find an integer vector $v \in L$ such that the angle between $u$ and $v$ is as small as possible. That is, I would like $$v \in \text{argmax}_{w \in L} \frac{u.w}{\|u\|\|w\|}$$

Here, the objective function is just the cosine between the vectors $u$ and $w$.

I am wondering if this problem can be formulated as a well-known integer lattice problem (such as a closest vector problem). If so, is there an algorithm that I could use to solve it? Any help or resources would be greatly appreciated.

I don't know of a good approach to this, or whether there's any literature on it.

However, if you're completely stuck, one possible approach is to use integer quadratic programming and binary search.

WLOG we can assume $\|u\|=1$ (otherwise replace $u$ with $u/\|u\|$).  Now the decision problem is, given $\alpha$, to determine whether there exists $w$ such that $u \cdot w / \|w\| \ge \alpha$, i.e., such that $(u \cdot w)^2 \ge \alpha^2 \|w\|^2$.  Define

$$\Phi(w) = \alpha \|w\|^2 - (u \cdot w)^2.$$

Note that $\Phi$ is a quadratic function in the unknowns $w_1,\dots,w_n$, and the decision problem can be solved by maximizing $\Phi(w)$ subject to the constraints $-M \le w_i \le M$.  The answer to the decision problem is yes iff there's a solution to this integer quadratic program where $\Phi(w) \ge 0$.  Now if you could solve the decision problem, you could use binary search on $\alpha$ to find the largest $\alpha$ for which a solution exists.

Unfortunately this requires integer quadratic programming, which might be very hard.  One heuristic approach might be to relax to semidefinite programming instance (with real numbers instead of integers), look for a solution (in the reals), round to the nearest integer point, and see if that gives you a valid solution.  This is not likely to give you an exact solution but it's possible it might give you some kind of approximation to the correct answer.  Unfortunately, I have no idea how good or bad an approximation it might be.


Automata that recognizes Kleene closure of permutations of three symbols This is an automata theory homework question.

I need to create DFA that meets the following criteria:

Alphabet $\Sigma = \{ a, b, c \}$
Machine accepts empty string and strings of length that is a multiple of three, with every block of three containing one $a$, one $b$ and one $c$.

So far, I came up with this machine, it is obvious:

However, I can't get it to accept empty string. Does it mean there is a transition q0 → q3?

Update1:  Following corrections by Dave Clarke I made some corrections.

A regular expression for this machine is $(www)^*$ where $w = \{abc,acb,…\}$. Therefore to represent multiple of three, I need to copy this (on the picture) machine 3 times. Final state should have arrows pointing to the first copy, for transitions marked 'a', 'b','c'.
As it was pointed out, since this is DFA, I need to add missing states. This can be accomplished by adding "dead" states.
Empty string should correspond to $\varepsilon$-transition from qStarting → qFinal.

Update2:
As it was pointed out, my regular expression is wrong ! It should be $(w)^*$. Here is the final machine, that I think should be correct.(I didn't include "dead" state)

There are a few things wrong with this automata:

It does not accept the empty string.
It is not a DFA – there should be no undefined transitions in a DFA.
It only accepts strings of length three, not multiples of three.

You are on the right track. Dealing with 1. and 3. above are fairly straightforward.
 Feed in an empty string. What state do you end up in? What does it mean to accept?
Feed in some longer strings. What's the pattern?
Dealing with 2. is rudimentary too, just a matter of filling in the missing transitions.

It's a good idea to read and understand again the definition of DFA, in particular, understanding what is allowed and what is not allowed.

EDIT: Here is a prettier solution:


Show $H_1(x)$ is partially computable I need to show that $H_1(x)$ defined as follows is partially computable.

\begin{equation}
H_1(x)=
\begin{cases}
1 \;\;\;\;\;\text{ if } \Phi(x,x) \downarrow \\
\uparrow \;\;\;\;\; \text{ otherwise}
\end{cases}
\end{equation}

The thing is my textbook, that is  "Computability, Complexity, and Languages" by Davis, Sigal and Weyuker, lacks of examples and walkthroughs so, personally, I find hard solving even the easiest exercises.

I think I can prove $H_1(x)$ partially computable, if I can find a program $\mathcal P$ that executes it.

First of all for the Universality Theorem:

$$\Phi(x,x) = \psi^{(1)}_{\mathcal P}(x) \text{ and } \# (\mathcal P)=x$$

so I can write a program that computes $\psi^{(1)}_{\mathcal P}(x)$:

\begin{array} \\
\;\;\;\;\;\;\;\;\;Y \gets 0 \\
\;\;\;\;\;\;\;\;\;\text{IF } X \neq 0 \text{ GOTO } A \\
[E] \;\;\;\text{ GOTO } E \\
[A]\;\;\;\; Y \gets Y+1
\end{array}

I don't know if I am on the right track. I would greately appreciate every comment, suggestion, nudge in the right direction, because I really feel kind of lost.

Attempt #2: First of all I am so very sorry for not providing you enough details. Basically:
$$\Phi^{(n)}(x_1, \ldots, x_n, x_{n+1}) = \psi^{(n+1)}_{\mathcal P}(x_1, \ldots, x_n, x_{n+1})$$

in plain English $\psi^{(n)}_{\mathcal P}(x_1, \ldots, x_n)$ is the value of the output at the terminal snapshot; $\Phi^{(n)}(x_1, \ldots, x_n, y)$, where $\#(\mathcal P) = y$  is the universal program $\mathcal U_n$, which works as an interpreter, it keeps track of the current snapshot by decoding the number of program being interpreted, decides what to do next and do it. So $f(x) = \Phi^{(1)}(x,y)=\psi^{(2)}_{\mathcal U_1}(x,y)$. So my answer would be:

\begin{array} \\
\;\;\;\;\;\;\;\;\;\text{IF } \Phi(x,x) \text{ GOTO } C \\
[A] \;\;\;\text{ GOTO } A \\
[C]\;\;\;\; Y \gets 1
\end{array}

or

\begin{array} \\
\;\;\;\;\;\;\;\;\;\text{IF STP}^{(2)}(x,x,y,k)  \text{ GOTO } C \\
[A] \;\;\;\text{ GOTO } A \\
[C]\;\;\;\; Y \gets 1
\end{array}

where $STP^{(n)}(x_1, \ldots, x_n, y, t)$ is a primitive recursive predicate that happens to be true if the program with number $y$ on input $(x_1, \ldots, x_n)$ eventually stops after $t$ steps.

Many such exercises are best solved by writing down programs in your favorite programming language. However, a typical programming language cannot examine its own source code, or the source code of a subroutine, or of another program, whereas a Turing machine can. So we need to enrich the language with two special constructs:

eval(x,y) which runs source code x on input y and returns the result. This is more or less the universal Turing machine. (Yes, the Python toplevel interactive shell is the same thing as a universal Turing machine.)
uneval(f) which accepts a function f and returns its source code. This allows us to inspect source code, and to simulate it step-by-step (we can implement a "debugger" by hand once we get acces to source code).

Strictly speaking, eval is not needed because it can be implemented in a general-purpose programming language. It amounts to implementing an interpreter for the language inside the language itself, a favorite programming exercise of people who design programmng languages.

So, to so solve your exercise in Python:

def H1(x):
  "Simulate the machine x on input x. Return 1 if it halts, cycle otherwise."
  eval(x, x)
  return 1

That was easy, and to the point. Fiddling with Turing machines just obscures the fact that this is a very easy exercise (although at some point you do need to convince yourself that Turing machines can do all the things that a programming language can do, and vice versa).

By the way, when you pose questions here, you should not assume that everyone knows your textbook by heart. You should explain notation such as $\Phi(x,x)$. I had to guess what you meant.


Is detecting easy instances of NP-hard problems easy? My question is the following. Assume that $\Pi$ is an NP-hard problem. Given an arbitrary instance $I$ of $\Pi$ and assume that an adversary knows that this instance is easy to solve, is it possible to find a deterministic polynomial-time algorithm to solve this particular instance $I$?

For example: Suppose that $\Pi$ is GRAPH COLORING. The adversary gives you a graph $G$ with $n$ vertices.

The adversary knows that $G$ is complete but you don't. Can you find a polynomial-time algorithm that says "This graph is colorable with $\Delta +1$ colors"?
The adversary knows that $G$ has some property $P$ but you don't. Can you find a polynomial-time algorithm that says "This graph is colorable with $b$ colors"?
...

The problem isn't really well-posed.  For any particular instance, there is a single solution, say $S$.  Consequently, we can imagine an algorithm that has the answer $S$ hardcoded in: no matter what input you give it, all it does is just print $S$.  This answer counts as a deterministic polynomial-time algorithm that solves this particular instance $I$.

Therefore, the answer to your question is "Yes", but for uninteresting reasons.  It's possible you might need to think more about how to formulate your question to match what you really want to know.

The final part of your question is actually a bit different.  It doesn't ask about a single instance $I$.  Rather, it asks about a special case of the problem, i.e., an infinite family of instances that is a proper subset of all possible instances for $\Pi$.  In that case, the answer is "it depends"; some special cases might remain NP-hard, and others might be in P.

Finally, I don't know what it means to say "The adversary knows X but you don't".  I'm free to write an algorithm that assumes X is true and only works when X is true.  "Knowledge" is a funny thing and not well modelled by the kinds of tools you seem to be talking about; complexity theory is more about "existence" than "knowledge".


Converting Recursion into Into Iteration While reading Code Complete second edition, I came across this line:

  You can do anything with stacks and iteration that you can do with
  recursion.

Is this true? or there are functions, that must be implemented recursively, and can't be done otherwise ?

Your CPU uses stacks and iteration to run any program, including programs based on recursion.

If you are unsure how this works, I suggest picking up an appropriate textbook.


grammatical complexity of propositional and monadic predicate validities? (and grammars for recursive but not context-sensitive languages?) Consider two sets: the set of validities of propositional logic and the set of validities of monadic predicate logic. Call the first set $VP$ and the second set $VQM$. Both of these sets are decidable, so there are Turing machines that recognize both them and their complements.

I'm interested in how the decidability of these two sets translates into grammars for them, along the lines of the Chomsky hierarchy. I have three questions:

(1) Are there context-sensitive grammars that generate $VP$ and $VQM$? The answer would be yes if the Turing machines that recognized these sets were linearly bounded, but I don't think they are.

(2) If these languages aren't context-sensitive, can anything be said about a grammar that generates them?

I would have a better grasp of the second question if I understood something about grammars between the top two levels of the Chomsky hierarchy, context-sensitive and unrestricted.

(3) There is a natural class of automata between linear-bounded Turing machines and unrestricted Turing machines: polynomially bounded TMs, exponentially bounded TMs, etc. Do these classes of TM track anything on the grammar side of the Chomsky hierarchy? If not, is there any structure to the gap between context-sensitive grammars and full-on unrestricted grammars?

(Just to be clear: I'm not talking about a grammar for propositional logic, but a grammar for its validities.)

EDIT: I thought I'd add a comment about why I'm interested in these questions. I know there is an unrestricted grammar that generates the (recursively enumerable but not recursive) set of validities of (full-on, polyadic) predicate logic. But since $VP$ and $VQM$ are not just recursively enumerable but recursive, I was wondering if the grammars that generate them might have more structure, in the Chomsky-hierarchy sense, than the grammar that generates the validities of all of predicate logic. In other words, I'm wondering if there is a grammatical way of detecting the difference between sets of validities that are recursive (as in the case of propositional and monadic predicate logic) and sets of validities that are merely recursively enumerable. What can be said about grammars of recursive but not recursively enumerable languages? Most references on the Chomsky hierarchy say nothing about this gap, but I don't know if that means there's nothing to be said.

There is a linear space deterministic algorithm for deciding whether a given propositional formula is tautological. The algorithm goes over all truth assignments and verifies that the formula evaluates to TRUE under all of them.

Regarding monadic predicate logic, Lewis (journal version) determined that the nondeterministic time complexity is $2^{\Theta(n/\log n)}$, but I'm not sure if the nondeterministic space complexity is known. Perhaps you could sift through the papers citing Lewis.


Reference Request: Overlaps between complexity theory and dynamical systems? Per Wikipedia:

  In mathematics, a dynamical system is a system in which a function
  describes the time dependence of a point in a geometrical space.
  Examples include the mathematical models that describe the swinging of
  a clock pendulum, the flow of water in a pipe, and the number of fish
  each springtime in a lake.

  At any given time a dynamical system has a state given by a set of
  real numbers (a vector) that can be represented by a point in an
  appropriate state space (a geometrical manifold). The evolution rule
  of the dynamical system is a function that describes what future
  states follow from the current state. Often the function is
  deterministic; in other words, for a given time interval only one
  future state follows from the current state however, some
  systems are stochastic, in that random events also affect the
  evolution of the state variables.

Is there any result on dynamical system (i.e. solving dynamical equations, finding asymptotic states to a system, dynamics in chaotic system) with complexity theory, hardness for finding a solution, etc.?

Thanks

This is a well-researched area. For a representative result, see Kawamura's proof that solving ODEs is difficult.

A different line of works studies the hardness of computing Nash equilibria and related problems. See for example the recent breakthrough of Bitansky, Paneth and Rosen, who base hardness of cryptographic assumptions; earlier work based it on complexity theoretic assumptions.


Proving that a certain graph contains a 4-cycle Show that if $G$ is a graph with $|E| \geq 2|V|^{3/2}$, then $G$ must contain a $4$-cycle

Can someone explain/point me in the right direction on this?
Let's say we say $|V|= 4$, using the equation above we get $|E|= 16$.

I drew it out and I was unable to come up with $16$ edges. Do I completely misunderstand the graph equation?

The question says "IF $G$ contains a certain number of edges, then..." and, as you've demonstrated, if $G$ has only four vertices, then it can't contain that many edges, since a graph (without self-loops) can contain at most $\tfrac12|V|\,(|V|-1)$ edges. So, for the condition to be true, we must have
$$\begin{align*}
    2|V|^{3/2} &\leq \tfrac12|V|\,(|V|-1) \\
    4|V|^{1/2} &\leq |V|-1 &\text{(dividing through by $\tfrac12|V|$)}\\
    16|V| &\leq |V|^2-2|V| + 1 &\text{(squaring both sides)}\\
    |V|^2-18|V|+1&\geq 0 &\text{(collecting terms)}
\end{align*}$$

Then, by the quadratic formula, we see that $|V|\geq 9 + 4\sqrt5 \approx 17.94$ (or $|V|\leq9-4\sqrt5$ but we're only interested in positive solutions for $|V|$).
It's not a problem that $17.94$ isn't an integer: the number of vertices must be greater than or equal to that number, so we actually have $|V|\geq 18$.


Can $f$ be not computable even if $L$ is decidable? I am trying to teach myself computability theory with a textbook. According to my book, a function $f$ over an alphabet $A=\{a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z\}$ is only computable iff the language

$$
L = \{s\#^j\sigma : s\in A^*, \sigma \in A, \text{ the }j\text{'th symbol of } f(s)\text{ is } \sigma\}$$

is decidable. Why is that? Couldn't a function $f$ be not computable even if $L$ is decidable?

If $L$ is decidable then you can use it's decider to compute $f$:
for the first symbol of $f(s)$ run the decider on the input $s\#x$ for any $x\in A$. For one of them, the decider will answer YES--this is the first letter in $f(s)$.

Continue doing this (e.g., for the second letter, decide if $s\#\#x \in L$, etc.), and reveal $f(s)$ letter-by-letter until the time where the decider answers NO for all $x\in A$, which means you reached the end of $f(s)$.

So if $L$ is decidable, $f$ is computable. Conversely, if $f$ is not computable, it can't be that $L$ is decidable.


If P = NP, then how not cannot solve NP-hardness (the one that doesn't intersect with NP-complete) in polynomial-time? My question is that if P = NP, then we can solve any NP-hard problems (the one which is NP-complete and the one which is not-NP-complete) by saying that since we have a polynomial time algorithm to solve the NP problems and since the reduction works in polynomial time. Therefore, polynomial to polynomial is polynomial, and so we can solve any NP-hardness problem. For example, we can solve the TSP by calling to an NP-complete problem which have polynomial time since P=NP, and since the reduction is polynomial time, therefore we can solve TSP in polynomial time.

  How could disprove this argument? What is the clue to say that NP-hardness(the one which doesn't intersect with NP-complete) can not be solved in polynomial time even if P=NP.

I know that if P = NP, then we can only solve any problem in NP (but not in NP-hard). But I want to know what it makes NP-hard (the one that have no intersection with NP-complete) is not solvable in polynomial time even if P=NP since we have polynomial time reduction and polynomial time algorithm given P=NP.

Thank you

You have your reductions the wrong way around. A problem $X$ is NP-hard if every problem in NP can be reduced to $X$. That is, saying that $X$ is NP-hard means that, if we had an efficient algorithm for $X$, we would have an efficient algorithm for every problem in NP: $X$ is easy implies all of NP is easy.

So, suppose that P$\,=\,$NP. Then, all of NP is easy, but that tells us nothing about $X$, because the implication goes the wrong way. Maybe $X$ is easy; maybe it's hard. In fact, some NP-hard problems are definitely hard: the halting problem is NP-hard but it's undecidable, regardless of what the relationship between P and NP turns out to be.


Is there a binary representation where the encoding distance grows with the arithmetic distance? I need to binarily encode/decode small integers (around 10 bits), in such a way that the hamming distance of the encoded number grows monotonically with the (absolute value) arithmetic distance of the numbers.
Edit: the monotonicity doesn't needs to be absolute. There is probably a cost to pay breaking it, but the cost should be as low as possible. Is preferable to reduce the hamming distance at short scales, and if unavoidable, break it at larger scales.
For example:
The question is: Is there already such an encoding (better if it has error correction)?
I need to use it in python, so if there is already a python library to do the encode/decode, it would be perfect.
The "monotonically growing" requirement is a loose requirement. It is not strictly necessary. It just is convenient that the hamming distance reflects the arithmetic distance in some way.
The hamming distance can be replaced wit some other measure of encoding distance, like Jaccard distance.
The requirement is that close integers share most of their binary encoding, and still there is error correction.

You can get some kind of tradeoff between unary and binary.
Start by choosing some integer $k$ and set $w=2^k-1$.
Then write $x$ as $x=r+w+w+\ldots+w$, where $r$ is the remainder of $x$ when divided by $w$. Let $\bar{a}$ denote the binary encoding of $a$. You can encode $x$ as $e(x) = \bar{r}\bar{w}\bar{w}\ldots\bar{w}$.
This encoding is of length $k\times x/w$ and you have $d_{hamming}(x,y)$ which should be in the range from $\frac{1}{w}(|x-y|-1)$ to $\frac{k}{w}(|x-y|+1)$ (give or take some rounding errors on my part).
The smaller $k$ you choose, the better correspondence between Hamming distance and absolute difference, but the longer the encoding.
You can also use Gray code instead of binary to squeeze a bit more out of it.


Efficient algorithm for retrieving the transitive closure of a directed acyclic graph I'm trying to solve a graph problem (it's not for homework, just to practice my skills). A DAG $G(V,E)$ is given, where $V$ is the set of vertices and $E$ the edges. The graph is represented as an adjacency list, so $A_v$ is a set containing all the connections of $v$. My task is to find which vertices are reachable from each vertex $v\in V$. The solution I use has a complexity of  $O(V^3)$, with transitive closure, but i read that in a blog it can be faster, although it didn't reveal how. Could anyone tell me another way (with better complexity) to solve the transitive closure problem in a DAG?

The fact that our graph is acyclic makes this problem much simpler.

Topological sort can give us an ordering of the vertices $v_1,v_2,\dots,v_n$ such that, if $i < j$, then there is no edge from $v_j$ back to $v_i$. We've listed the vertices such that all edges in go "forward" in our list.

(edited to fix analysis and give slightly faster algorithm)

Now we just go backwards through this list, starting at the last vertex $v_n$. $v_n$'s transitive closure is just itself. Also add $v_n$ to the transitive closure of every vertex with an edge to $v_n$.

For each other vertex $v_i$, going from the end backwards, first add $v_i$ to its own transitive closure, then add everything in the transitive closure of $v_i$ to the transitive closure of all the vertices with an edge to $v_i$.

The running time is $O(n+m+nm) = O(n^3)$ in the worst case, with $n$ the number of vertices and $m \in O(n^2)$ the number of edges. Topological sort takes time $O(n+m)$. Then we do another $O(mn)$ work in the backward pass: As we go backwards through the list, for each edge, we have to add up to $n$ vertices to somebody's transitive closure.

Note that you can get a nice constant-factor speedup by representing everyone's transitive closure by bit-arrays. Say you only had $n=64$; then you would use a single 64-bit int where bit $i$ is 1 if $i$ is in my transitive closure and 0 otherwise. Then the part where we add everything in $i$'s transitive closure to $j$'s is really fast: We just take $c_j$ |= $c_i$. (Binary OR operation.)

For $n > 64$, you'd have to keep them in arrays and do some arithmetic, but it would be much faster than an Object set.

Also, I know the big-$O$ in the very worst case is still $O(n^3)$, but to beat this in practice you'd have to have something much more complex. This algorithm also does very well on sparse graphs.


How to use Artificial Intelligence in Computer Chess In some (historical) papers, chess has been referred to as the drosophila of artificial intelligence. While I suppose that in current research, the mere application of a search algorithm is at best advanced computer science, I believe that there are still area's where can apply (and practice) AI-techniques.

A simple example would be opening book learning where one can teach the program whether to use or to not use certain moves in the opening because the program is unsuited to certain types of position. We can use a form of re-inforcement learning and automate this: I suppose I could play the program against itself and increase the probability of winning lines and decrease the probability of losing lines.

The more complex example is to use a learning evaluation function (for example, one could tweak the values of piece-square tables). However, I'm thinking:

given all the noise due to there being an enormous amount of realistic positions (as opposed to the amount of realistic opening lines)
and with the cost (duration) of a computer chess game, and the need to play loads.

How can one do this effectively? (or should I look at other techniques, for example neural networks.)

The whole state space for chess is enormous - it can be roughly estimated as 1043 (Shannon number (Shannon, 1950), (Wikipedia)).

The idea you present - Reinforcement Learning agents playing with each other to learn the game - was successfully applied to Backgammon - TD-Gammon (Tesauro, 1995), (Chapter in Reinforcement Learning by Sutton&Barto). It also used Neural Networks to estimate game's value function. This problem is however much simpler, as number of states in Backgammon is significantly smaller than in chess, namely: 18,528,584,051,601,162,496 (Backgammon Forum Archive thread).

If you, however, would end the game after few initial moves and aim only to learn "good openings" you could succeed with analogous approach. The main problem would be to evaluate the game after the opening game, which seems hard. Just a similarity measure to the established positions after well known openings is not enough, because position can be far from them if opponent would make a stupid move (so it wouldn't be because of learning agent's mistake, so the position even if "incorrect" should be evaluated as a good outcome).

References:

SHANNON, Claude E. "Programming a computer for playing chess." In Philosophical Magazine, 7th series, 41, no. 314 (March 1950): 256-75.
Gerald Tesauro. 1995. Temporal difference learning and TD-Gammon. Commun. ACM 38, 3 (March 1995), 58-68


How to show that L*=(L*)*? I am studying formal language theory and have been asked to prove the following:

$\forall L, L^*=(L^*)^*$

I've started with

$def. L^* = \bigcup_{i \in \mathbb{N}} L_i, L_0=\{{\epsilon}\}, L_1=\{L\}, L_{i+1}=\{uv|u\in L_i, v\in L\}$

$then (L^*)^* = \bigcup_{i \in \mathbb{N}} L_i^*, L_0^*=\{{\epsilon}\}, L_1^*=\{L^*\}, L_{i+1}^*=\{uv|u\in L_i^*, v\in L^*\}$

$L^*L_0^*\in(L^*)^* = L^*\epsilon^* = L^*$ $\therefore L^* \subseteq (L^*)^*$

$L^*L_0^* = L^*, L^*L^*_1 = L^* (def), L^*L_{i+1}^*=L^*_iL^*=L^*L^*$ but the * operator is closed under concatenation, thus, $L^*L^* \in L^* \therefore (L^*)^* \subseteq L^*$

$\therefore L^* = (L^*)^*$

I simply don't have an intuition on whether this attempt at a proof is correct and I would appreciate any insight about it since the subsequent problems are to show $L^+=(L^+)^+$ and then to argue whether $(L^*)^+=(L^+)^*$

It's a big problem if you can't tell whether your proof counts as a proof or not. Perhaps it's better to write the proof "in words". Here is an example.

Since $M \subseteq M^*$ for every language $M$, clearly $L^* \subseteq (L^*)^*$. Now suppose $w \in (L^*)^*$. Then $w = w_1 \ldots w_\ell$ for some $w_1,\ldots,w_\ell \in L^*$. Then for each $i$, $w_i = w_{i,1} \ldots w_{i,\ell_i}$, where $w_{i,j} \in L$. So $w = w_{1,1} \ldots w_{1,\ell_1} \ldots w_{\ell,1} \ldots w_{\ell,\ell_\ell} \in L^*$. This shows that $(L^*)^* \subseteq L^*$, and so $L^* = (L^*)^*$.

This is probably very similar to the proof you give, but your proof is written "in symbols" and so it is somewhat hard to parse.


Difference between Binomial and Fibonacci heap (marking) I am confused why Binomial heaps do not utilize marking.

Concerning Fibonacci heap children:

Each tree in a Fibonacci heap is allowed to lose at most two children before
that tree needs to be "reprocessed" at a later step. The marking step in the
Fibonacci heap allows the data structure to count how many children have
been lost so far. An unmarked node has lost no children, and a marked node
has lost one child. Once a marked node loses another child, it has lost two
children and thus needs to be moved back to the root list for reprocessing.

How do Binomial heaps not need marking? It seems like in Fibonacci, this is in place so that when a marked node loses another child, it knows to move it back to the root and reprocess. I do not understand how Binomial heaps can possibly handle this without marking.

In binomial heaps the structure of the trees in the heap is very strict, they all have a number of elements that is a power of two. When a node is removed it is the root of a tree, and all the children (which are again roots trees with a power of two elements) are merged with the other original trees.

There are no nodes that have an "imperfect" number of children, and there is no marking needed to indicate that.


"Implied atomic propositions" in propositional boolean formula Suppose we have a propositional boolean formula F and let M be the set of all models of that formula.

I am wondering if there is an efficient way to find all atomic propositions that are implied by the formula. Informally, this means that they can only have one specific value in all models M.

Does this problem have a specific name in literature? What is the complexity?

Examples:

Formula "(A)": the predicate A is implied by the formula, it can only ever have the truth value true in any model of the formula.

Formula "(A or B)": no predicate is implied by the formula, there are models where A is false, there are models where A is true, there are models where B is false, there are models where B is true.

Formula "A and (B or C)": in all models of this formula, A has to be true.

Suppose we had a TM $M$ which, given $F$ and some atomic $A$ occurring in $F$ it can efficiently (PTIME) decide whether all models of $F$ make $A$ true, i.e. whether $F \models A$.

Then we can efficiently decide the validity of any formula $G$ as follows.

Take $A$ to be any atom not in $G$. Craft $F := \lnot (G \land (\top \lor A))$, and use $M$ to decide if $F \models A$.

We then have
$$
(F \models A) \iff (F \models \bot) \iff \models \lnot F \iff \models G \land (\top \lor A) \iff \models G
$$

The first $\iff$ is nontrival, but easy to prove by considering the models where $A$ holds, and the others where $\lnot A$ holds, and exploiting our choice of $A$. It is left as an exercise ;-)

So, we constructed a polynomial reduction of validity to this problem.
Since validity is coNP hard, we deduce this problem is also coNP hard.


L(G) = ∅ is undecidable? For a grammar $G$, why is the problem of whether $L(G)=\emptyset$ is undecidable?
I'm confused as, for recursive languages there exists a Turing machine which will halt every time and give an answer(accepted or rejected) for each and every string input.
So we can decide whether it accepts strings or not.

For any particular string $x$, the question of whether $x \in L(G)$ is decidable (if G is not unrestricted), and that's what you've described.

However, the problem you've given is not whether a particular string is in $L(G)$, but whether any string is in $L(G)$. There are infinitely many strings to try. We can test each one in sequence, and if it is in $L(G)$ then we know it is not empty. But if $L(G)$ is empty, how do we know when to stop? There are infinitely many strings, so we never know if the next string is the one that's in the language. So we never know when to stop.

That said, the decidability greatly depends on what type of language/grammar $G$ is. For context-free languages, this is decidable, since we can make a pushdown automaton and perform a search to see if an accepting state is reachable. But for other, more complicated types of languages this may very well be undecidable.


Birkhoff-von Neumann theorem for bistochastic digraphs A weighted digraph (with loops) is bistochastic, iff

the weights are non-negative,
for all non-sink nodes, the sum of the edge weights of the out-edges is $1$, and
for all non-source nodes, the sum of the edge weights of the in-edges is $1$.

The Birkhoff-von Neumann theorem for a bistochastic matrix states that a bistochastic matrix is a convex combination of permutation matrices. It would be nice to characterize the bistochastic digraphs with a given underlying digraph in a similar way as a convex combination.

Attempted reduction to the Birkhoff-von Neumann theorem: If the underlying digraph has no source and sink nodes, then we can conclude from the Birkhoff-von Neumann theorem that the convex combinations of the in-degree = out-degree = 1 subdigraphs with n-nodes give all possible bistochastic digraphs (because a $n\times n$ permutation matrix corresponds to a in-degree = out-degree = 1 digraph with $n$-nodes, and only subdigraph can occur in the convex combination since no edge can be canceled out).

If the number of source nodes is equal to the number of sink nodes, then connecting each sink with exactly one source allows to reduce the problem to the previous case (because the weight of the newly added edges can only be 1). But if the number of source nodes is different from the number of sink nodes, then I guess that there exists no bistochastic digraph for that underlying digraph. The weights seem to define a flow on the digraph, so the min-cut max-flow theorem should help.

Even so this reduction seems to work, the case distinctions feel less attractive than the Birkhoff-von Neumann theorem. I would prefer to reduce it completely to the Birkhoff-von Neumann theorem (by connecting each sink with each source?), or reduce it completely to the min-cut max flow theorem (or something similar).

From Roger A. Horn "Topics in Matrix Analysis", section 3.2 page 164-165.

  A matrix $Q$ is said to be doubly substochastic if its entries are nonnegative and all its row and column sums are at most one.

The doubly stochastic matrix
$\begin{bmatrix} Q & I-D_r\\I-D_c & Q^T\end{bmatrix}$
is a dilation of $Q$, where $D_r$ and $D_c$ are diagonal matrices with the row and column sums of $Q$ respectively. This dilation allow to reduce the generalization of the Birkhoff-von Neumann theorem for substochastic matrices to the original theorem

  Every doubly substochastic matrix is a finite convex combination of partial permutation matrices.

The bistochastic digraphs are doubly substochastic matrices, so the generalized Birkhoff-von Neumann theorem can be applied directly for them. Or one can just apply the same reduction directly. This means taking the original digraph and a copy of the digraph where all edges are reversed, and connecting the sources and sinks to their copy by suitable oriented edges of weight 1.

However, it turned out that the notion of a doubly substochastic matrix is more suitable with respect to the original motivation for this question than the notion of a bistochastic digraph. It is a good thing that the above construction directly covers that case too.


Simplest argument that language decidable in constant time cannot be $\mathsf{NP}$-hard? My question is specifically about $\emptyset$, but more generally about any language that can be decided in (deterministic or nondeterministic doesn't really make a difference here) constant time. Obviously, $\emptyset$ cannot be $\mathsf{NP}$-hard since there is nothing to map "yes"-instances to, but I'd prefer a one line argument using a time hierarchy theorem, ideally. Currently I'm arguing (very informally speaking) that since constant time is $\subsetneq \mathbb{o}(n \log n)$, constant time is strictly "less powerful" than any deterministic polynomial time due to the deterministic time hierarchy theorem and thus - since $$\mathsf{Polytime}(f(n)) \subseteq \mathsf{NPolytime}(f(n))$$ - also strictly less powerful than nondeterministic polynomial time. So, constant time languages can't be $\mathsf{NP}$-hard.

This doesn't sound elegant to me at all (although it should be correct I hope, even if not phrased as formally as I'd write it down for something to hand in). What's the most elegant argument you can come up with, preferably using not-too-advanced complexity theory?

Let $L \in P$ be non-trivial (not empty and not containing everything). If $L$ is NP-hard then $P=NP$. Indeed, given any language $L' \in NP$, by definition of NP-hardness there is a polytime reduction $f$ such that $x \in L'$ iff $f(x) \in L$. Since $L \in P$, this gives a polytime algorithm for $L'$, showing that $L' \in P$.

Conversely, if $P=NP$ then $L$ is NP-hard. Indeed, given $L' \in NP$, we can decide $L'$ in polynomial time using some algorithm $A$. Fix some yes instance and some no instance of $L$, and use $A$ to come up with a polytime reduction from $L'$ to $L$, which always returns one of the two fixed instances. This shows that $L$ is NP-hard.

Summarizing, if $L \in P$ is non-trivial then $L$ is NP-hard iff $P=NP$.


Optimal data structure for a time-windowed streaming graph in order to compute fast statistics I apologize if this is the wrong place or too trivial a question for this community. What is the best data structure to store a time-windowed streaming graph in order to compute fast statistics over all nodes in the graph, for e.g., running computation of average degree?

I believe the best way to describe this is as follows: Let $G=(V,E)$ be a sparse time-evolving network modeled as an undirected graph with $n$ nodes and $m \geq n$ edges over time (in hours) $t = t_0, t_1, \dots $. Suppose further, that at any time point $t_i$, any edges that are more than $k$ hours are removed. In addition, nodes that have no edges connecting to it are removed.

My idea (for e.g. the average degree) is as follows: keep track of an array of edge arrival times as well as a degree array of size $n$ where each element represents the total degree. At any new time point $t_i$, we would add 1 to the degree array corresponding to the two nodes with the new edge. We would then remove all edges that are older than $k$ hours (i.e. added before $t_i-k$). Any nodes that are edge-less are removed. At all time points, a running average of the degree is computed by taking the average of the degree array.

If I'm not mistaken, this algorithm would be $O(n)$ in run-time and $O(n)$ in space. Is there any better way of doing this?

The best data structure I could find from previous posts such as this one, recommend adjancency lists. Additionally, is there any advantage in using disjoint set data structures such as in the post here?

There's an efficient streaming algorithm for computing the average degree.  Note that if you have the sum of the degrees and the number of vertices, you can compute the average -- so we'll try to keep track of those two values.

Also note that if you delete or insert an edge, it is easy to update the sum of the degrees.  If you delete or insert a vertex, it is easy to update the number of vertices.

Taking all of this into account, we do $O(1)$ work (amortized) per time step, and at every time step we can infer the average degree.  This is as efficient as one could possibly hope for.


General method behind converting recursive inorder, preorder and postorder traversals of a binary tree to a non-recursive one? I am reading both recursive and non-recursive using stack methods to implement inorder, preorder and postorder traversal of a binary tree at https://en.wikipedia.org/wiki/Tree_traversal#Depth-first_search_2, which I also copied below.

What confuses me most is that

I find the non-recursive implementations using stacks are not easy to understand.
It also seems to me that the three non-recursive implementations are ad hoc on each own, and I can't find if there is a way to unify their creations.

Can they be reformuated and/or created from the recursive implementations in some unified way, so that I can write them out by just looking at the recursive implementations?

Since a compiler can implement recursions using stacks, I believe it is possible to do that.

One reply I saw

  Usually, I replace a recursive algorithm by an iterative algorithm by
  pushing the parameters that would normally be passed to the recursive
  function onto a stack. In fact, you are replacing the program stack by
  one of your own.

Stack<Object> stack;
stack.push(first_object);
while( !stack.isEmpty() ) {
   // Do something
   my_object = stack.pop();

  // Push other objects on the stack.

}

  Note: if you have more than one recursive call inside and you want to
  preserve the order of the calls, you have to add them in the reverse
  order to the stack:

foo(first);
foo(second);

  has to be replaced by

stack.push(second);
stack.push(first);

In the idea of the reply, the non-recursive implementation of preorder is easier to understand than the non-recursive implemenations of the other two. The non-recursive implemenations of the other two don't seem to follow the idea at least closely, and can they be written to follow the idea closely?

Thanks.

Note the implementations from Wikipedia are

  Pre-order

preorder(node)
  if (node = null)
    return
  visit(node)
  preorder(node.left)
  preorder(node.right)

iterativePreorder(node)
  if (node = null)
    return
  s ← empty stack
  s.push(node)
  while (not s.isEmpty())
    node ← s.pop()
    visit(node)
    if (node.right ≠ null)
      s.push(node.right)
    if (node.left ≠ null)
      s.push(node.left)

  In-order

inorder(node)
  if (node = null)
    return
  inorder(node.left)
  visit(node)
  inorder(node.right)

iterativeInorder(node)
  s ← empty stack
  while (not s.isEmpty() or node ≠ null)
    if (node ≠ null)
      s.push(node)
      node ← node.left
    else
      node ← s.pop()
      visit(node)
      node ← node.right

  Post-order

postorder(node)
  if (node = null)
    return
  postorder(node.left)
  postorder(node.right)
  visit(node)

iterativePostorder(node)
  s ← empty stack
  lastNodeVisited ← null
  while (not s.isEmpty() or node ≠ null)
    if (node ≠ null)
      s.push(node)
      node ← node.left
    else
      peekNode ← s.peek()
      // if right child exists and traversing node
      // from left child, then move right
      if (peekNode.right ≠ null and lastNodeVisited ≠ peekNode.right)
        node ← peekNode.right
      else
        visit(peekNode)
        lastNodeVisited ← s.pop()

Can they be reformuated and/or created from the recursive implementations in some unified way, so that I can write them out by just looking at the recursive implementations?

Yes, they can be reformulated in a unified way.

We take the <pre/in/post>_order recursive calls together with the visit procedure call, reverse them and push the corresponding nodes on the stack s, marking each node with its purpose: TRAVERSE or VISIT. I think the examples below explain the idea better.

Preorder traversal

So, iterativePreorder can be reformulated as

iterativePreorder(node)
  s ← empty stack
  s.push(<node, TRAVERSE>)

  while (not s.isEmpty())
    <node, mark> ← s.pop()
    if node = null
      continue
    if mark = TRAVERSE
      s.push(<node.right, TRAVERSE>)
      s.push(<node.left, TRAVERSE>)
      s.push(<node, VISIT>)
    else
      visit(node)

It's easy to see the above pseudocode can be transformed into the iterativePreorder procedure provided in the question by

eliminating two consecutive push/ pop operations on the same node;
not pushing null-nodes on the stack.

In-order traversal

Skipping the boilerplate code, we get:

iterativeInorder(node)
...
    if mark = TRAVERSE
      s.push(<node.right, TRAVERSE>)
      s.push(<node, VISIT>)
      s.push(<node.left, TRAVERSE>)
...

Postorder traversal

iterativePostorder(node)
...
    if mark = TRAVERSE
      s.push(<node, VISIT>)
      s.push(<node.right, TRAVERSE>)
      s.push(<node.left, TRAVERSE>)
...

The iterativeInorder and iterativePostorder procedures cited in the question don't look like the above code because they make use of the traversal patterns arising in those cases. Like the fact that under in-order traversal we go straight to the leftmost leaf of the input tree, visit it, go one level up and do the same thing for the right subtree of the current node, etc.


Is $L \subset 1NL$ when $L \neq NL$? A log-space Turing machine has a read-only input tape, a write-only output tape and uses at most $O(\log n)$ space in its read-write work tapes. The classes $L$ and $NL$ contain those languages which are decided by deterministic or nondeterministic log-space Turing machines, respectively. The two-way Turing machines may move their head on the input tape into two-way (left and right directions) while the one-way Turing machines are not allowed to move the input head on the input tape to the left.

Hartmanis and Mahaney have investigated the classes $1L$ and $1NL$ of languages recognizable by deterministic one-way log-space Turing machine and nondeterministic one-way log-space Turing machine, respectively. They have shown that $1NL \subseteq L$ if and only if $L=NL$.

See the paper here(it is free to download):

https://ecommons.cornell.edu/handle/1813/6253

I wonder this question:

Is $L \subset 1NL$ when $L \neq NL$?

Moreover, I wonder this another question:

Is there any reference that shows whether at least one of the options $L \subset 1NL$ or $1NL \subset L$ or $L = 1NL$ should be true?

Thanks in advance!!!

If they can only move the head right, they are equivalent to finite automata.


Do algorithms reduce? Given two problems A and B.

Given two algorithms a' and b'. a' solves A and b' solves B.

If A reduces to B and B reduces to A.

Then can we say anything about a' and b'? Are they the same?

A reduction can be thought of a way to "rephrase" a problem in terms
of another. This can be denoted using $A \to B$, $A$ reduces to
$B$. This means that if you have an algorithm that solves $B$
then you also have an algorithm that solves $A$, since $A$ reduces
to $B$, $A \to B$. Now you also have $B \to A$ so in some way, your
problems are equivalent since they can be reduced to each other.

However, this does not imply much about the algorithms themselves
because they can be arbitrarily bad. For example, the sorting problem
has time complexity $O(n \log n)$. But an awful algorithm that sorts by
testing all possible permutations has time complexity $O(n!)$.

The only thing we can say is that the algorithms aren't better (their
time complexity isn't lower than) the problems themselves.


Why don't 2 GPUs double the graphics performance of a computer compared to a single GPU? Obviously, if you have 2 GPUs, it is double the hardware, and thus it should be double the power of a single GPU (assuming all GPUs are the same, of course). So why is this not the case? I searched this question on Google and things about optimization and things came up, but I still don't understand.

When you are using two processors, not every task your GPU's encounter is parallel by nature. There are a certain portion of tasks which are strictly serial, and can be processed by only one processor at a given time.

If a set of tasks were to be 100% parallel your dual GPU set up should give double the speed (in theory).

A little mathematics for you: Ahmdal's law for speedup is given by

$$S = \frac{1}{[B+\frac{(1-B)}{n}]}$$, where B is the percentage of tasks that is serial in nature, n is the number of processors and S is the speedup.

Put B=0 and you wil get S, ie Speedup=2.

Practically dual GPU gives us maximum 80% speedup.


How many $(x, y)$-paths of length $20$ are there, where $x$, $y$ adjacent vertices in cycle $C_5$? As the title of the question suggests, let $x$ and $y$ be two adjacent vertices in the cycle $C_5$. How many $(x, y)$-paths of length $20$ are there?

Hint: consider powers of adjacency matrix of $C_5$ (Wiki: Matrix powers).


Why does memory data isn't organized in two or more lines? I understand that computer memory data is sequential;
It is one long line organized in one or more address/es, each of which containing one or more fixed size word/s which contain raw data (in an initial manner, just offset value/s, I would assume).
Why does memory data isn't organized in two or more lines (why it's just one long line, or at least, so it would appear, via a user interface such as some text editor)?

The notion of a "line" is an abstraction we impose.  Currently our memory works as follows: you provide an address to the memory module that you want to read, and it returns the value at that address; or if you want to update memory, you provide an address and the new value, and it overwrites the value at that address with the new value.
Why do we build memory that way?  Well, the current way is simple and works, and can be implemented efficiently in circuits.  If you wanted to consider some other alternative, you'd have to think about what are the benefits and what are the costs.  I'm not clear on exactly how your counter-proposal would work, but I expect it would add complexity (which ultimately might add to the cost of implement the memory subsystem, and also might make the system harder to understand for programmers) without a benefit that would make it worthwhile.  If you wanted to dive into this in more detail, you'd probably start by learning how RAM works at the circuit level.  Our current RAM is highly optimized to minimize the number of gates needed, i.e., to minimize cost.


Language for teaching basic programming I'm interesting in teaching programming to middle school students.  I'd like a programming language with the following criteria:

Simple - pared down to the absolute minimum needed to support sophisticated programming without too much code.  As such, for this language, I'm not interested in pointers and am weary of object-orientation (although functions are good).
Powerful - I'd like to be able to program 21st-century elements, including graphics, networking, and distributed processing.
Debuggable - I'd like an elegant Integrated Development Environment with a human-readable debugger (i.e. not some strange error message with a stack trace, but a clear explanation that an average middle school student can use to determine what is wrong with the code).

The standard programming languages (C,C++,C#,Java) fail the first criterion.  Basic programming languages like Scratch fail the second (and possibly third) criterion.
Scripting languages (perl, python, php) fail the last criterion.

I'd like to know if someone knows of such a beast, before I sit down to make it up myself.

You should perhaps look into Racket (formally known as Scheme, a derivation of Lisp). It's the language taught to first year CS students at my University. Since it's a functional programming language, the syntax and concepts are quite simple compared to C/C++, there are several libraries that can do some basic drawing or networking related things, and Dr. Racket as several debugging features... including a Stepper (i.e it will show and perform one substitution at a time when you click the "next" button). I think that it may be worth looking into: http://racket-lang.org/. It has several other features that you may like, such as teaching modules (beginner, intermediate, advanced, full student levels) and pretty good documentation and examples. The book: How To Design Program (http://www.htdp.org) is a great teaching reference for this language which has a few nice examples using some of the libraries I mentioned above.


Python Prime Numbers Code Problem I was trying to write my own code for primes in Python. I know that code already exists, but I am doing this to challenge my knowledge and make my own solution. I was wondering if any of you guys would tell me what's wrong with it.

factor_list = [ ]

def integer_test(x):

    if type(x) == int:
        return True
    else:
        return False

def factor_checker(x):

    count = 0
    y = x
    while count <= y:
        print(count)
        count += 1
        if integer_test(x / count) == True:
            factor_list.append(count)

factor_checker(45)

print(factor_list)

When I try to input a number for factor checker and then look at the factor list, I just get an empty list. What is wrong?

Thanks.

You don't get an empty list. See this. However you won't get the desired results because in python int divided by int is always int.  You may want to try this:

import math

factor_list = [ ]

def integer_test(x):

    if math.floor(x) == math.ceil(x):
        return True
    else:
        return False

def factor_checker(x):

    count = 0
    y = x
    while count <= y:
        print(count)
        count += 1
        if integer_test(1.0 * x / count) == True:
            factor_list.append(count)

factor_checker(45)

print(factor_list)

In this code x/count is a double. So the integer_test will only return true if it's ceiling and floor return the same number i.e the integer itself.