Shortest sub-sequence of one string, that's not a sub-sequence of another string Given two strings $x$ and $y$ over the alphabet $\{A,C,G,T\}$, I'm trying to determine a shortest string $z$ such that $z$ is a subsequence of $x$ and not a subsequence of $y$.

  Example: a shortest string that is a subsequence of AATGAAC but not a subsequence of ATCGATC is AAG.

A dynamic programming algorithm seems to work.

Given a prefix $X_k = x_1 x_2\dots x_k$ of string $X$ ($X$ is of length $s$, so $X = X_s$), a prefix $Y_m = y_1 y_2 \dots y_m$ of string $Y$ ($Y$ is of length $t$, so $Y_t = Y$), and a length $L$, we determine if there is a subsequence of $X_k$ which is also a subsequence of $Y_m$, such that the sub-sequence is of length exactly $L$ and ends at $x_k$. Call that (boolean) value: $\text{is_there}[k,m,L]$.

We will also need to know if there is a subsequence of $X_k$ which is also a subsequence of $Y_m$ such that the subsequence is of length exactly $L$ and ends at or before $x_k$.  Call that boolean value $\text{is_there_any}[k,m,L]$.

These satisfy the recurrences:

$$\text{is_there}[k,m,L] = \text{is_there}[k, m-1, L] \vee (x_k = y_m \wedge \text{is_there_any}[k-1,m-1,L-1])$$

and

$$\text{is_there_any}[k, m, L] = \text{is_there}[k, m, L] \vee \text{is_there_any}[k, m-1, L]$$

The smallest $L$ such that $\text{is_there}[k, t, L] = false$ for all $k$ gives you the result. (Note that $t$ is the length of $Y$).

If the length of the shortest such subsequence is $S$, This can be implemented in $O(stS)$ time and $O(stS)$ space by a triply nested for-loop with $L$ on the outside, then $k$, then $m$.

Something like:

Compute isThere for L = 1.
foreach L in (2 ... s)
    foreach k in (1 ... s)
       foreach m in (1 ... t)
         is_there[k,m,L] = blah
         is_there_any[k,m,L] = blah


Pumping Lemma for irregular language, how to choose and divide the string The language on the alphabet $\{a,b\}$ is $$L=\{ab^nab^{n+1} |n>0\}$$

so i have to take a string w = xyz:

what's the best string to choose such that $|w| > n$? and then what about the division?

like $ w=ab^nab^{n+1}$ is a correct option? Then how can I divide this into three pieces? My attempt:

$ x = ab^s $ with  $ 0 ≤ s ≤ n -1 $

$ y= b^ta $   with   $  0 < t ≤ n - t $

$ z = b^k $   with        $ 0 ≤ k < n - t - s $

w = abn-1abn.

We have to consider all the division xyz = w with |y| >= 1 and |xy| <= n. So

x = apbr

y = aqbs

z = btabn

where:

p + q = 1
r > 0 implies p = 1
q + s > 0
r + s + t = n - 1

Let's now consider w' = xy0z=apbr+tabn. If x is the empty string, then w' is missing the initial 'a' (and maybe some b), so w' is not in L. Else if x is not empty, we know that y contains at least one occurrence of 'b', so w' can't be in the form abnabn+1 and w' is not in L.


Rearranging strings so that the Hamming distance between them is 1 This is a question from CodeFights.com:

  Given an array of equal-length strings, check if it is possible to rearrange the strings in such a way that after the rearrangement the strings at consecutive positions would differ by exactly one character.

  Example

  For inputArray = ["aba", "bbb", "bab"], the output should be
  stringsRearrangement(inputArray) = false;
  All rearrangements don't satisfy the description condition. (sic)
  For inputArray = ["ab", "bb", "aa"], the output should be
  stringsRearrangement(inputArray) = true.
  Strings can be rearranged in the following way: "aa", "ab", "bb".

I found an exponential-time algorithm, but is there a polynomial-time algorithm? Is this problem NP-complete?

I know that a closely related problem, the Hamming Salesman Problem (HTSP), is NP-complete, and this problem is certainly reducible to HTSP, but I don't know if HTSP is reducible to this one.

Grid graphs are finite node-induced graphs of the infinite planar grid (whose vertices are integral points, and two vertices are linked when their Euclidean distance is 1). A. Itai, C. H. Papadimitriou, and J. L. Szwarcfiter proved that the Hamiltonian path problem on grid graphs is NP-complete.

To reduce that to your problem, suppose the grid graph has $m$ rows and $n$ columns. The $i$-th row is labeled with the string $a^ib^{m-i}$, and the $j$-th column is labeled with the string $a^jb^{n-j}$. Then a vertex corresponds to the concatenation of the two labels of its row and column. Now it is easy to show the unit disk graph under Hamming distance over all these concatenated strings is exactly the same as the original grid graph.


Average time complexity of linear search It is usually assumed that the average time complexity of the linear search, i.e., deciding whether an item $i$ is present in an unordered list $L$ of length $n$ is $O(n)$ (linear).
I have read several proofs, usually assuming either:

that $i$ and the elements of $L$ take values in an infinite domain, in which case the probability of $i$ being is $L$ tends towards 0 and the algorithm will iterate over all elements.
that $i$ is present exactly once in $L$, in which case the expectancy on the number of iterations is $(1 + 2 + … + n)/n \in O(n)$.

However, I would like to introduce the case where $i$ and the elements of $L$ take values in a finite domain of size $d$. Is this case studied somewhere? I have failed to find proof online, but I have found one that finds that the complexity is $O(d)$, and would like to know whether it is correct.
I assume that each element of $L$ is a random value from $[1..d]$. I want the expectancy $E$ on the number of iterations of the linear search algorithm. I also assume that $L$ has infinite size, without loss of generality, I do not want to question the fact that linear search is $O(n)$ on average, it clearly is. My point is that linear search is both $O(n)$ AND $O(d)$. I have interest in the case where $d \ll n$.
At the first iteration, there is a $1/d$ probability that the sought element is found and the algorithm stops. In other cases, i.e. with a probability of $(d-1)/d$, the algorithm iterates. Recursively, I have $E = 1 + E\cdot(d-1)/d$, which boils down to $E=d$.
Also, this seems related to the fact that $\sum_{n=0}^{\infty} \frac{n}{e^n} \in O(1)$, if the recursion is unrolled. My proof, however, seems almost too easy. Is there a fail somewhere?

The right way to prove this is to use the notion of expected value.
Given an array $[x_1, …, x_n]$, an index $1\leqslant k \leqslant n$ and a value searched $1\leqslant i \leqslant d$, the probability that $x_k = i$ is $\frac{1}{d}$.
Now what we want to calculate is the expected value of the first index $k$ such that $x_k = i$. For that, we need to know the probability, for each index $k$, that $x_k$ is the first value equal to $i$. This probability is $p_k = \frac{1}{d}\left(1-\frac{1}{d}\right)^{k-1}$ (meaning that we did not encounter $i$ within indices $1…k-1$ but in index $k$).
The expected value is then $\sum\limits_{k=1}^{n}kp_k = \frac{1}{d}\sum\limits_{k=1}^nk\left(\frac{d-1}{d}\right)^{k-1}\leq \frac{1}{d}\sum\limits_{k=1}^{\infty}k\left(\frac{d-1}{d}\right)^{k-1}$.
We can show that this last quantity is equal to $\frac{1}{d}\frac{1}{\left(\frac{1}{d}\right)^2} = d$.
This indeed means that the average time complexity is $O(d)$.


3Col reduction Variation, Special edges I have a question concerning NP reduction.
My question asks me to show that if I have a graph with Edges that connect 3 nodes together instead of 2, (Y style I assume). I need to prove that finding out if the TRI-Graph is 3 coloring is NP-Complete.
I'm not asking for the answer. But I've been racking my brain on how to approach the reduction.
I'm curious to know if you guys have suggestions on which problem I should use to reduce it to my trigraph.
I've tried SAT3, CLIQUE, but those tri-edges make it very hard, maybe I'm going about it the wrong way.
Anyhow, any help would be appreciated. Thanks in advance.

You can reduce from $3$-coloring.
Given an instance (graph) $G=(V,E)$ of $3$-coloring, create a tri-graph $G'=(V', E')$ by transforming each edge $e=(u,v) \in E$ to a tri-edge $(u,v,z_e)$ in $G'$ (where $z_e$ is a new vertex).
A 3-coloring $c : V' \to \{1,2,3\}$ of $G'$ induces a $3$-coloring of $G$: simply color $v \in V$ with color $c(v)$.
A 3-coloring $c : V \to \{1,2,3\}$ of $G$ can also be transformed into a $3$-coloring of $G'$ by coloring each vertex $z_e$, where $e=(u,v) \in E$, with the unique color in $\{1,2,3\} \setminus \{c(u), c(v)\}$.


how to make a Turing machine of a cipher? For example, lets consider the simplest model of cipher: the Caesar cipher. According to the theory I read the Caesar cipher consist in substitute a letter by another in considering a shift in an alphabet given by a certain number.

I know that a Turing machine consist of: a tape, a header that writes or reads information from that tape, and a set of states that consist in moving to the left or right on the tape. Also the initial state and the final state and reject states.

So if I would like to make a TM that accept the Caesar cipher I suppose that the information that would be on the tape, for example, the message "hello", that I want to convert to a cipher text by a shift of n=3 in each character so I will get the word "khoor".

Because I need to put that message on a TM tape I guess that I can convert it into a binary string, would that be necessary or can I work with original characters?

For example if my TM tape look like this (I am supposing that "h" is 0011 and that "k" is 1010 for example):

|0|0|1|1|e|e|e|e|

where e is the empty character and the header is in the leftmost position pointing to 0, so if I want to convert this "h" into "k" I can read one by one each binary digit (from left to right), converting into its corresponding binary digit to the converted letter and writing it in some beginning position at the right. Would that be ok? So I will have something like:

|e|0|1|1|e|1|e|e|

After the first iteration, I have read the leftmost digit, 0, changed into 1 and then copy it after the empty position. I can do the same with all the remaining digits.

Would that approach be good enough, in this case, to simulate the Caesar cipher in a TM, and also if I want to decipher the converted text can I do a similar process?

Bottomline, maybe somebody could show a model for a Caesar cipher using a TM?

Thanks for your help.

Honestly, the answer to "How do I model X using a Turing Machine is:"

Implement the algorithm using a programming langauge, probably a simple one like lambda-calculus
Translate from that language into a Turing Machine

We could tell you how to write a machine that does a Caesar cipher, but it would just be us doing the above steps for you.

Turing Machines are very un-intuitive to program in, and they're usually not used to model algorithms directly, more as a theoretical baseline of what an algorithm is. But while there are lots of proofs that model Turing Machines in general, usually you don't deal with specific machines.

If you really need to model things directly with TMs, try using a variant of them, such as RAM machines (which would probably be much easier for modelling a Caesar Cipher), and/or multi-tape TMs, then use the known translations to ordinary machines.


Get term type during evaluation using Hindley-Milner type system I've implemented a lambda calculus evaluator and use the Hindley-Milner algorithm to infer terms types and ensure type correctness without the user having to explicitly annotate types.

But now I'd like to add a typeof operator that given a term, it returns the type of the term. So far, what I do is keep a hash map of terms to types that is populated during type checking. So if I do typeof 123, when the type checker determines the type of 123, it'll add 123 = Number to the hash map and look it up when typeof 123 is evaluated.

The problem with this approach is that if I have this term:

let _typeof = \a.(typeof a) in (_typeof 123)

Since \a.(typeof a) is polymorphic and has type a -> Type, the result will be a instead of Number as I'd expect. If instead I had this:

(_typeof.(_typeof 123) \a.(typeof a))

Then I'd get the right type Number since \a.(typeof a) is not polymorphic.

So all I need is a way to handle polymorphism. I'm having a hard time getting my head around it and I wonder if there is a known way to do this.

Hashing of terms to types sounds like a hack to me (or possibly premature optimization and a hell created by stateful programming). During type inference you should tag every subterm with its computed type. Then during evaluation typeof simply projects the type.

The hell is in the deatils, of course. Here are some initial thoughts about how this would go (I did not actually implement this, but if I did, I would start from Poly in PLZoo).

We define the following datatypes:

a datatype ty of polymoprhic types
a datatype preterm of raw terms (the parser gives you these)
a datatype term of tyepchecked terms (type inference converts preterms to these)
a datatype value of values

Maybe like this, using OCaml syntax:

(* the result of parsing is a preterm *)
type preterm =
  | PreType
  | PreNumeral of int
  | PreTypeof of preterm
  | PreVar of string
  | PreLet of string * preterm * preterm
  | PreApp of preterm * preterm
  | PreLambda of string * preterm

type ty =
  | Type (* the type of all types *)
  | Number
  | Parameter of int
  | Arrow of ty * ty

(* after type inference every term is tagged with its type *)
type term = term' * ty
and term' =
  | Type
  | Numeral of int
  | Typeof of term
  | Var of int (* using de Bruijn indices *)
  | Let of term * term (* using de Bruijn indices *)
  | App of term * term
  | Lambda of term (* using de Bruijn indices *)

(* a typing context *)
type ctx = ty list

(* a runtime environment *)
type env = value list

(* values are explicitly tagged with their types *)
and value = value' * ty
and value' =
  | ValType of ty
  | ValNumeral of int
  | ValLambda of env * term

The parser gives us a preterm. Then we define

infer : ctx -> preterm -> term

and an evaluator

eval : env -> term -> value

The evaluator now has an easy time evaluating typeof e as

let rec eval env = function
  ...
  | Typeof e ->
    let (_, t) = eval env e in
      (ValType t, Type)
  ...

Let us work through your example

let _typeof = (λ x . typeof x) in _typeof 123

First, infer would find out that _typeof has type α -> Type. In the application _typeof 123 it would try to match (a fresh instance of) α against the type Number and would succeed with setting α = Number. It would then conclude that the type of _typeof 123 is Type.

Second, when eval gets to evaluation of _typeof 123 it actually sees something like

(App ((Var 0, Arrow (Parameter 0, Type)), (Numeral 123, Number)), Type)

which is an application of bound variable 0 to the numeral 123, together with typing information: the bound variable 0 has type Arrow (Parameter 0, Type) which corresponds to α -> Type, the numeral has type Number, and the entire expression has type Type. The evaluator first evaluates

(Var 0, Arrow (Parameter 0, Type))

which involves looking up the 0-th variable in the environment. It gets back a pair ((env', e), Arrow (Parameter 0, Type)) where (env', e) is a closure representing λ x . typeof x. Then it evaluates the argument and gets (ValNumeral 123, Number). It remains to evaluate e applied to (ValNumeral 123, Number) which is done the usual way with a recursive call to eval in env' extended with (ValNumeral 123, Number). Here e is going to be something like

(Typeof (Var 0, Parameter 0), Type)

which corresponds to the expression typeof x, except that x is replaced by de Bruijn index 0 and is tagged to have "any type". Now we need to pay attention (here is where you have a mistake that gives you α instead of Number): we first evaluate (Var 0, Parameter 0) by looking up the 0-th elemenent of (ValNumeral 123, Number) :: env', so we get (ValNumeral 123, Number). Now we evaluate Typeof by taking the second component, which is Number. It would be wrong to evaluate Typeof by simply returning Parameter 0, we actually have to evaluate its argument and then take the type of that). The final value therefore is

(Type Number, Type)

as expected.


Efficient implementation of sets Let U be a pre-determined and fixed universal set (and |U| = n = 2k for some integer k, so the set may be huge).

I create many arbitrary subsets of U in running time (These sets may be or may not be sparse).

I do not need to check whether an element is in a set.

But I need to be able to

check whether a set is empty,
do the basic set operations difference and intersection, and
calculate the cardinality of a set.

What is the most time-efficient data structure for this? It should be also space-efficient, if possible.

I have bit vector in my mind. Elements of U are numbered from 0 to n-1. Each of n bits represents the existence of the corresponding element.

For k ≤ 5 or k ≤ 6 (depends on the computer architecture and the programming language) I can implement these sets as [unsigned] integers.
But there will be a need for multi-word arithmetics in general case. So I believe, the space complexity of any set is ϴ(n) and time complexities of operations are ϴ(n) using bitwise operations and hamming weight.

Yes, using a bitvector, the running time will be $\Theta(n)$, i.e., $\Theta(2^k)$, for all operations.

If most sets are small in cardinality, a better option may be to use a sorted list of the elements in the set.  In this way, you can compute the intersection or difference of two sets of size $m_1,m_2$ in $\Theta(m_1+m_2)$ time (they work similar to the "merge" operation in mergesort).  You can compute the cardinality of a set of size $m$ in $\Theta(m)$ time, and test emptiness in $O(1)$ time.  If the size of the sets is small compared to $n$, this might be much faster.

You can make the cardinality operation take $O(1)$ time when using a sorted list by augmenting the data structure: when you construct the list, compute its cardinality and store that in a separate slot along with the list.  Now cardinality lookup takes $O(1)$ time.  It is easy to keep track of the cardinality of the new set when performing an intersection or differencing operator.

If there is some "pattern" to the set of elements in the set, another option might be to use a binary decision diagram (BDD).  You think of each element of $U$ as a $k$-bit vector, and think of a set as a set of $k$-bit vectors.  Then, you can use a BDD to represent that set.  Alternatively, we can associate to any set $S$ of a function $f:\{0,1\}^n \to \{0,1\}$ so that $f(x)=1$ if $x \in S$; then represent $f$ as a BDD (this is equivalent, and just a different way of thinking about the same thing).  If there is sufficient "structure" in the elements of the set, this might allow a more concise representation of the sets and more efficient operations.  The running time to compute the intersection or difference of two BDDs is related to the sizes of those BDDs.  In many contexts BDDs might be ineffective (they add implementation complexity with no improvements in performance), but in some special cases they might be useful.


What is an $NP^{NP}$-complete problem? So in this paper I'm reading (https://adamsmith.as/papers/fdg2013_shortcuts.pdf), the authors talk about an $NP^{NP}$-complete problem, in relation to Answer Set Programming. I know what P, NP, etc. are but I don't unerstand what they mean with $NP^{NP}$. Also I can't Google it because Google doesn't recognize superscript.

I did find out it's also mentioned in this book, but they still don't provide an explanation.

Can anyone ecplain this class of problems to me?

$NP$ is the class of problems that, roughly speaking, you can solve by guessing an $y$ of polynomial size (with some magic to guarantee that you guess "right") and then doing a polynomial computation involving $y$ and the original input.

$NP^{NP}$ is the class of problems solvable in this way, if you have access to an oracle for $NP$. After guessing $y$, you're not just allowed to do some polynomial computation, you're also allowed (within this calculation) to solve problems from $NP$ (through an oracle, so in constant time).

The classical $NP$-complete problem of boolean satisfiability is to compute $\exists_x R(x)$ where $R$ is some boolean formula (and $x$ is a shorthand for $x_1,\ldots,x_n$). Its $NP^{NP}$-complete analogue is to compute $\exists_x \forall_y R(x)$.

A slightly more intuitive $NP^{NP}$-complete problem is that of formula minimization: given a formula, can you find a formula of length $\leq k$ that expresses the same (boolean) function?

$NP^{NP}$ is also known as $\Sigma_2 P$, and you will be able to find more info by searching for "polynomial hierarchy" (see, e.g., Wikipedia's article).


If a sparse language is NP complete, then are all languages in NP in P/poly? If a Sparse Language is NP complete, then are all languages in NP in P/poly? I know that sparse languages are in P/poly, but does a polynomial time reduction give an addition to the circuit that is super polynomial? A sparse language is such that $\forall n \in \mathbb{N}, |L \cap \{ 0,1 \} ^{n} | \leq p(n)$ for some polynomial $p(n)$.

Yes, see Mahaney's theorem. It states that if a sparse language is $\mathbf{NP}-$complete, then $\mathbf{P=NP}$, and since $\mathbf{P\subseteq P_{poly}}$, then $\mathbf{NP\subseteq P_{poly}}$


Optimal Selection of Non-Overlapping Jobs I'm trying to find what the family of problem is - as well as an approach - for the following:
I have a set of tasks T = [t1, ..., tn] to do, each of which has a corresponding reward ri.
Each task takes place during a fixed interval - ie: task 1 is from times 1-4, task 2 from 2-5, and task 3 from 9-15.
This means that I would have to pick either task 1 or 2 depending on which is more valuable, and then task 3 which does not conflict with either of the previous.
I'd like for this to scale to n tasks, and also to m "CPU's" - where more than one task can be executed in parallel.
This reminds me of the knapsack problem, but maybe an interval graph would provide a better approach?
Any suggestions on how to approach this problem, or any relevant references?

If you consider each task as a node of a graph, and each conflict as an edge, this is a weighted maximum independent set problem.
It is NP-hard, but you should get good results with a mixed integer programming solver, such as CBC.


Number of binary search trees with maximum possible height for n nodes I'm using the definition of the height of a tree as the longest possible path from the root to a leaf by its number of edges, e.g. a tree of 2 nodes has a height of 1.  With that in mind, what would be the number of binary search trees (don't have to be balanced) that have the maximum possible height for n-nodes?

So far, I know that the maximum height of any binary search tree of n-nodes is n-1 since we're counting edges.  So for example, a binary search tree of 3 nodes has a maximum height of h = 3-1 = 2 and there are 4 possible trees with n-nodes that have the maximum height of 2.

I also know that for n-nodes, there are (2n)!/((n+1)!n!) possible trees.

I'm able to find this manually for trees where n is small but would like to find a formula for any n.

EDIT:
The BST definition I am working with defines a Binary Search tree as a binary tree where each node has at most 2 children and does NOT need to be nearly-complete, so you could have a tree of 3 nodes with a height of 2.  It also satisfies the BST property where all nodes in the left subtree of a node x has keys smaller than x's key and all nodes in the right subtree of a node x has keys larger than x's key.

The number of trees with $n$ nodes of height $n-1$ is $2^{n-1}$. Indeed, every internal node has exactly one child, which can either be the left child or the right child. Since there are $n-1$ internal nodes, this gives $2^{n-1}$ options.


Use max operation in a constraint in Linear Programming I have liner programme with set of $x_{3n}$ variables where $x_{ij}$ are {0,1}. I am solving this linear programme using LP-Solve.

Using these variables, I want to form following constraint :

$max(x_1 , x_2.., x_n) + max(x_{n+1} , x_{n+2}.. , x_{2n}) + max(x_{2n+1} , x_{2n+2}..., x_{3n}) >= q$

Constraint is :
Sum of max variable in set of variables should be greater than q.

How can I write constraint using $max$ operation in LP Solve?

Introduce variables $m_1,m_2,m_3$ to represent the three maxes.

Add the linear inequality $m_1 + m_2 + m_3 \ge q$.

Then, add the following extra inequalities for $m_1$:

$0 \le m_1 \le 1$
$m_1 \le x_1 + x_2 + \dots + x_n$
$x_1 \le m_1$, $x_2 \le m_1$, $\dots$, $x_n \le m_1$

and similarly for $m_2$ and $m_3$.


Are hash onions inherently sequential? An open problem in complexity theory is whether NC equals P.

I'm somewhat confused because I would have thought that it's obvious that NC != P because of hash onions. A hash onion is when you start with some input $i$ and repeatedly hash $n$ times:

$$H(i), H(H(i)), ..., H^n(i)$$

Given an input $i$ the amount of work to compute $H^n(i)$ is $O(n)$ so hash onions are part of P. And because the hash function $H$ acts like a random oracle you can't do better than sequential queries to $H$, therefore hash onions are not part of NC.

What am I missing?

For all engineering purposes, you are right, if you choose a cryptographically strong hash function $H$.

For theoretical purposes, nope.  There's no proof.  Your argument is based on unproven assumptions, hence it can't be regarded as a proof that NC $\ne$ P.  In particular, we don't know of any hash function $H$ that we can prove is cryptographically strong, or that we can prove is inherently sequential when repeated like this. All of our hash functions are either heuristic (we think they are good but we have no ironclad proof) or are based on other assumptions (such as that factoring is hard; something we suspect but have no proof of).  And assuming that $H$ behaves like a random oracle is an unproven assumption.  So if you're a theorist and what you care about is proving that NC $\ne$ P, none of these count as a suitable proof.

Personally, I do consider them pretty good evidence that in all likelihood NC $\ne$ P... but it's not a proof.


Known facets of the Travelling Salesman Problem polytope For the branch-and-cut method, it is essential to know many facets of the polytopes generated by the problem. However, it is currently one of the hardest problems to actually calculate all facets of such polytopes as they rapidly grow in size.

For an arbitrary optimization problem, the polytope used by branch-and-cut or also by cutting-plane-methods is the convex hull of all feasible vertices. A vertex is an assignment of all variables of the model. As a (very simple) example: if one would maximize $2\cdot x+y$ s.t. $x+y \leq 1$ and $0\leq x,y\leq 1.5$ then the vertices $(0,0)$, $(0,1)$ and $(1,0)$ are feasible vertices. $(1,1)$ violates the inequality $x+y\leq 1.5$ and is therefore not feasible. The (combinatorical) optimization problem would be to choose among the feasible vertices. (In this case, obviously $(1,0)$ is the optimum). The convex hull of these vertices is the triangle with exactly these three vertices. The facets of this simple polytope are $x\geq0$, $y\geq 0$ and $x+y\leq 1$. Note that the description through facets is more accurate than the model. In most hard problems - such as the TSP - the number of facets exceeds the number of model inequalities by several orders of magnitude.

Considering the Travelling Salesman Problem, for which number of nodes is the polytope fully known and how much facets are there. if it is not complete, what are lower bounds on the number of facets?

I'm particularly interested in the so-called hamiltonian path formulation of the TSP:

$$min \sum_{i=0}^{n-1}(\sum_{j=0}^{i-1}c_{i,j}\cdot x_{i,j}+\sum_{j=i+1}^{n-1}c_{i,j}\cdot x_{i,j})$$ s.t.

$$\forall i \neq j:\ \ 0 \leq x_{i,j}\leq 1$$
$$\forall i \neq j\ \ \ x_{i,j}+x_{j,i}\leq 1$$
$$\forall j \ \ \sum_{i=0}^{j-1}x_{i,j}+\sum_{i=j+1}^{n-1}x_{i,j}\leq 1$$
$$\forall j \ \ \sum_{i=0}^{j-1}x_{j,i}+\sum_{i=j+1}^{n-1}x_{j,i}\leq 1$$
$$\sum_{i=0}^{n-1}(\sum_{j=0}^{i-1}x_{i,j}+\sum_{j=i+1}^{n-1}x_{i,j})=n-1$$

If you have any information about polytopes of other formulations of the TSP, feel free to share that too.

For asymptotic bounds, Fiorini, Massar, Pokutta, Tiwari, and de Wolf recently showed exponential lower bounds on the number of facets of any polytope that projects to the TSP polytope (the TSP polytope, being the convex hull of feasible TSP solutions). This is stronger than what you ask for, and implies that even adding extra variables will not make the TSP polytope efficiently representable.

Their paper is follow up to the classical 1988 paper by Yannakakis, who showed the same result but only for polytopes that satisfy a certain symmetry condition.


Looping through random integers - will it halt with probability 1? Say I have a simple program that has the pseudocode like this:

min = 1
max = 100
c = 5
random = randomInt(min,max)
while(c != random):
    random = randomInt(min,max);

Theoretically, from what I understand, I cannot guarantee this will halt. However, is this true for both PRNGs and say, random integers generated using atmospheric noise? Is there a difference? And by convention, can I say this will "almost surely" halt (probability 1), but still cannot guarantee this? I'm still trying to wrap my mind around the edge case of a program with an almost sure chance of halting, and how this is viewed from a computational perspective.

For deterministic algorithms, the statement "Algorithm $A$ halts on input $x$" is well defined. However, when $A$ is randomized (i.e. has access to some random source during its computation) this question becomes meaningless, as you need to know what was the outcome of the random source in order to answer it.

You can ask "does $A$ always halt on $x$", i.e. does it halt for every possible output of the random source. In your case, assuming the source produces uniformly distributed elements in the given range, the answer is no, since e.g. the infinite sequence "444..." is a possible outcome of the source, and this will cause $A$ to never halt.

However, "Algorithm $A$ halts on input $x$" is now an event, i.e. it is a subset of your sample space (we associate this event with the set of random outputs who cause $A$ to halt). Events have probabilities, so you can ask "What is the probability that $A$ halts on $x$"? If your source is uniform, then the probability that your algorithm doesn't halt is $p=\prod\limits_{i=1}^\infty\left(\frac{99}{100}\right)^i=0$. So in your case it is correct to say that the algorithm halts with probability $1$, but it is incorrect to say it always halts.

As for whether or not the randomness source matters, the answer is definitely yes. Consider the source which first chooses a number from the range uniformly at random, and then remembers it and outputs it to you in any later request (i.e. the source has memory, and different outcomes are not independent). In that case, your algorithm does not halt with probability $\frac{99}{100}$. For a source which always outputs $5$, it is true to say the the algorithm always halts (and not only with probability $1$, which is a weaker statement).


How to convert NPDA to PDA? I have been given this  Nondeterministic pushdown automata and I need to convert it to deterministic pushdown automata, I have been stuck with this for a while now, I know that there cant be transitions where the pda doesnt read anything from the stack but i dont know how to solve this.

Thanks in advance!

Suppose your stack alphabet is $\Gamma =\left\{Z_0,X\right\}$. You can eliminate transitions which don't pop stack, by guessing which stack symbol is at the top. like this:

before:
$(a,\epsilon)/XXX$

after:
$(a, X)/XXXX$, and
$(a, Z_0)/XXXZ_0$


Find a threshold such that one function is always bigger than the other Given the recursively defined function  $c$:
$$c(m,n)=\begin{cases}0&\text{for }m=0\\
n^2+n+1&\text{for }m = 1\text{ and }n\ge 0\\
c(m-1, 1)&\text{for }m>1\text{ and }n=0\\
c(m-1,c(m,n-1))&\text{for }m>1\text{ and }n>0\\
\end{cases}$$

and the function $d$:

$$d(n) = \underbrace{2^{2^{.^{.^{.^{.^{2}}}}}}}_{\text{$n+2$ }}$$

The inputs $m$ and $n$ are both natural numbers. I'm asked to find an $x$, such that for all numbers $y \ge x$, $c(y,y) > d(y)$.

I rewrote the two functions using Python in order to calculate some values:

 c(m, n):
    if m == 0:
        return 0
    else if m == 1 and n >= 0:
        return n**2+n+1              # return n^2+n+1
    else if m > 1 and n == 0:
        return c(m-1, 1)
    else if m > 1 and n > 0:
        return c(m-1, c(m, n-1))

 d(n):
    exp_num = n-1
    result = 2
    while exp_num != -1:
        result = 2**result           # result = 2^result
        exp_num = exp_num - 1
    final_result = 2**result         # final_result = 2^result
    return final_result

Some inputs and outputs:

c(1, 1) = 3

c(2, 2) = 183

d(1) = 16

d(2) = 65536

d(3) = 20035299... 19156736, a number with 19729 digits.

I believe the threshold is $3$, as c(3, 3) doesn't seem to be realistically computable considering there are over 19K digit in A(4, 2). Unfortunately I have no idea how to prove this. Any help would be much appreciated.

As you suspected, the threshold is indeed 3.

Here is one approach to prove that for all numbers $y \ge 3$, $c(y,y) > d(y)$.

Step 0, show that $c(\cdot, \cdot)$ is strictly increasing with respect to each variable when the second variable is not 0.
Step 1, show that $c(1,n) \gt n^2$ for all $n\ge0$.
Step 2, show that $c(2,n) \gt 2^n$ for all $n\ge0$.
Step 3, show that $c(3,n)\gt d(n)$ for all $n\ge0$.
Step 4, show that $c(y,y) \gt d(y)\text{ if }y\ge3$.

Exercise. Show that $c(3,y) > \underbrace{2^{2^{\cdot^{\cdot^{\cdot^2}}}}}_{2y+2 \text{ copies of }2}$ for all $y\ge0$.


How many words are in this sets? I have problems to determine the size of the following sets in dependancy of the parameters $m, n>0$:
$$M_{m,n}=\{a^iwa^{m-i}\mid 0\le i \le m,\;w\in\{a,b\}^n\}$$
It is easy to see that $|M_{m,n}|\le (m+1)\cdot 2^n$ since there are $m+1$ possibilities for $i$ and $2^n$ possibilities for $w$. If the sets would take the words $w$ from a disjoint alphabet (e.g. $w\in\{b,c\}^n$), then the number of elements would be exactly $(m+1)\cdot 2^n$. But for $w\in\{a,b\}^n$ each set $M_{m,n}$ is ambiguous in the sense that the some words could be obtained from different $i$'s and $w$'s. For example $w=a^n$ leads to the same word $a^{n+m}$ for each $i$. By the way, this example yields $|M_{m,1}|=m+2$ because there is $1$ element for $w=a $ and $m+1$ elements for $w=b$. Another ambigious example for $n=2$ is $$a^i\;ab\;a^{m-i}=a^{i+1}\;ba\;a^{m-i-1}$$ for $0\le i \le m-1$, which together with the thoughts for unary $w$'s yields $|M_{m,2}|=2m+4$.

However, for increasing $n$ it becomes more and more difficult and unfortunately I am not able to generalize my approach. What I am hoping for is that $|M_{m,n}|$ is still in $\Theta(m\cdot 2^n)$. Any help?


Design an NFA to accept a, ad, abc, abd, but not e, abcd? I've made the following diagram to accept a, ad, abc, abd but I don't it to accept e, abcd, how can I limit that?

Updated
I modified the diagram in another attempt:

Your automaton has loops so it accepts an infinite language.

For finite languages $\{w_1, \dots, w_n\}$, it's easy to write them as regular expression

$\qquad w_1 \mid \ldots \mid w_k$

and apply Thompson's construction. If the resulting automaton is too ugly for your taste, determinize and minimize according to the canonical textbooks.

Warning: Determinizing automata for finite languages can blow up automaton size exponentially.

Note how this approach scales neatly to more concise representations of finite languages and even infinite languages -- all you need is a regular expression. Or any other formalism equivalent to finite automata, as the proofs of equivalence are usually constructive.


Examples of NP Complete key exchange algorithms There's a number of questions on the internet (this site and others; e.g. Why hasn't there been an encryption algorithm that is based on the known NP-Hard problems? ) discussing NP hardness of different asymmetric cryptosystems. How well established are NP hard key-sharing systems? That is, systems for establishing a shared key (that can then by used in symmetric encryption) that are based on problems that are known to be NP hard.

I was prompted to this question upon reading about https://en.wikipedia.org/wiki/Anshel-Anshel-Goldfeld_key_exchange and wondering if it could be shown to be NP complete when implemented on $GL_n(F_2)$ or $GL_n(\mathbb{R})$, cause these look like awfully hard constraint-satisfaction or quadratic optimization problems at a first glance. The corresponding problem this is based on is the Simultaneous Conjugacy Problem.

I'm aware that there is an important distinction between problems that are merely NP hard in the worst case -- but easy on most random instances, as opposed to problems that are "average-case NP" -- given a set of random instances, solving half of them is still hard. I'd be interested in hearing about key-sharing systems that rely on either notion of hardness.

There are no known public-key cryptographic algorithms that have been proven to be NP-hard to break.  None.  So we can't provide you examples, because none are known.

Answer to your original question:

The analysis at Why hasn't there been an encryption algorithm that is based on the known NP-Hard problems? also applies to public-key exchange.

Cryptography requires average-case hardness.  NP-hardness relates to worst-case hardness; it has no notion of a distribution on inputs, probability, or any kind of "average".  Worst-case hardness does not appear to imply average-case hardness: there are many problems that are believed to be hard in the worst case, but easy in the average case. Status of Impagliazzo's Worlds?
 has some pointers on this topic.


What is the name of this code transformation that uses associativity of addition? I am learning about compiler optimization technique and there is a technique that use associativity of addition to transform code.

For example, consider the following expression:

(a + b) + ((c + d) + e)

It can be transformed into:

a + (b + (c + (d + e)))

Does anybody know the name of this transformation?

According to LLVM it is called "Reassociate expressions" and uses the flag "-reassociate"
According to here:

-reassociate: Reassociate expressions
This pass reassociates commutative expressions in an order that is designed to promote better constant propagation, GCSE, LICM, PRE, etc.
For example: 4 + (x + 5) ⇒ x + (4 + 5)
In the implementation of this algorithm, constants are assigned rank = 0, function arguments are rank = 1, and other values are assigned ranks corresponding to the reverse post order traversal of current function (starting at 2), which effectively gives values in deep loops higher rank than values not in loops.


AC-3 Algorithms on CSP problem, What is happened when enocunter to an empty domain variable? Suppose We Applying Arc-Consistency (AC3) algorithms on one Constraint Satisfaction Problem, if domain of one variable be empty, what is the next step of this algorithm?

According to This Link and to Wikipedia's description of AC3: once one domain is empty, the algorithm stops, indicating there is no solution to the CSP.

This book says: if one domain of the non assigned variables becomes empty then backtracks to....

My challenge is about the behavior of this algorithms, i.e, in which
phase (when) AC-3 stops, and when it's select Backtrack.

  Update: Anyone could describe the behaviors of AC-3 on empty domain in
  each phase?

References: This question asked 5 month ago on SO but I think the answer is wrong, because I add some references that shows other things.

You've misunderstood the book.  It's not describing the AC-3 algorithm; it's describing some other algorithm.  The book is describing an algorithm that combines both guess-and-backtrack together with arc consistency.  The AC-3 algorithm doesn't do any guess-and-backtrack; it uses only arc consistency checks.

Thus, AC-3 does terminate if there is some variable whose domain set becomes empty; in this case, AC-3 declares the constraint system unsatisfiable (inconsistent).  This is the correct thing to do, in the context of the AC-3 algorithm.

Of course, if you're talking about some totally different algorithm (like the book is), that other algorithm might do something totally different.  No great surprise there.

I don't see anything wrong with the answer to the Stack Overflow question you link to.


Number of possible programs in a language Is the number of possible programs usually finite or infinite? I'm playing with the idea of generating all possible programs for a language - is that even a finite number or must we be more specific, finite RAM etc?

When considering such questions we usually disregard limitations of real computers and think about a programming language theoretically.

A general-purpose programming language (any language used in practice falls into this category) has infinitely many programs. Furthermore, all programs can be generated systematically. Implementing a program which generates all programs may be a useful learning experience, but has little actual value. The number of all programs of length $n$ is exponential in $n$ and so is unfeasable, except for fairly small values of $n$.


Assertion of Type Inference Rules/Type Checking I have a problem in a book I am trying to accomplish.

I understand the overall type of the expression is boolean and how it derives. (y * x) will be rule 4 (counting from top right). (y * x) + x when evaluated will be rule 3 and the overall expression when evaluated will be rule 5.

What I want to figure out is what is the correct way to illustrate the my working? Can someone give or link an example of the correct way to answer a question like this?

Question 2

Proposed solution:

Well, you need to construct a typing derivation which has what you want to prove as a conclusion, and no open premise (i.e., leaves must be axioms, or rules with no premises). In the case of your example, the conclusion will be

$$ int\;x,\,int\;y\;\vdash\;(x < (x \times y) + x) : bool $$

so the proof will start by

$$ {int\;x,\,int\;y\;\vdash\;x : int \quad\quad\quad
  int\;x,\,int\;y\;\vdash\;((x \times y) + x) : int}
  \over {int\;x,\,int\;y\;\vdash\;(x < ((x \times y) + x)) : bool} $$

and then you continue building up the tree until you reach leaves (i.e., rules with no premises). This will immediately be the case in the left branch since you only have a variable.

Here is the full proof (as an image):


Why does radix sort work? I understand how radix sort works and how to implement it, but I don't understand why it works.

Are there any underlying mathematical or logical principles that it relies on?

Radix sort sorts numbers by sorting on the least significant digit first. This is somewhat counterintuitive compared to the rather straightforward method by sorting on the most significant digit first.

The key point to radix sort is that the digit sorts used in each iteration of radix sort are stable: numbers (digit here) with the same value appear in the output array in the same order as they do in the input array. Given this, you can convince yourself of the correctness of radix sort by simply observing how a set of two-digit numbers are sorted. (Actually, we are using mathematical induction on the number of digits. However, a simple example with a set of two-digit numbers suffices here.)

In the first iteration, the numbers are sorted by their least significant digits. Now consider the second iteration which then sorts these numbers by the leftmost digits. Given two number $a = a_1 a_0$ and $b = b_1 b_0$, if $a_1 \neq b_1$, then after the second iteration, they are in the right order. If $a_1 = b_1$, then we know that the order between $a$ and $b$ should be consistent with $a_0$ and $b_0$. This is the case because the digit sort used by the second iteration is stable.


The throughput of the ALOHA protocol if the Binomial distribution was used In all the examples of ALOHA I've seen, the Poisson distribution is used. Theoretically, how could the throughput be calculated if a Binomial distribution was used instead?

For example, in the case that the offered load follows a Binomial distribution with probability $p$, I know that the probability of $k$ attempts within $t$ time slots is as follows:

$$\Pr\big[k \text{ attempts within $t$ time slots}\big] = \binom{t}{k}p^k(1-p)^{t-k}\,.$$

I know that the throughput, $S$ is equivalent to $G$ (average offered load) multiplied by the probability of success:

$$S = G\cdot\Pr\big[\text{successful}\big]\,,$$

but what would this be in the case that a binomial distribution is used?

I don't think it makes sense to use the binomial distribution.

The point of using the Poisson distribution is that network nodes are assumed to want to transmit with an exponential distribution at some rate. This is a reasonable model for objects that randomly emit stuff – for example radioactive decays follow this distribution.  Given a bunch of things emitting stuff at intervals sampled from the exponential distribution, the number of emissions in some time interval is given by a Poisson distribution.  In other words, the Poisson distribution arises naturally from a model of the individual nodes. A particular property of the Poisson distribution is that it has infinite support: it assigns a probability to the event that you have a million transmission attempts within ten time slots.  Another feature of using exponential distributions is that it allows one to model the back-off time after a collision.

In contrast, using a binomial distribution doesn't come from any natural model of the individual nodes' behaviour. It only allows you to model "were there at least $n$ transmissions attempts during this time slot?" for some $n$ of your choosing. It doesn't seem able to deal with back-off and it doesn't seem able to deal with multiple collisions within a single time slot.


The image of a recursive language under a computable function Let $f:\Sigma^{*}\to\Sigma^{*}$ be a computable function and let $L$ be a recursive language. Is $f(L):=\left \{{f(w)|w\in L} \right\}$ recursive?

Here, I see clearly, that $f^{-1}(L)$ is recursive (simply by applying $f$ on an input $w$, and then see if $f(w)$ belongs to $L$).

My intuition tells me that $f(L)$ should also be recursive. For an input $w$, we should verify if there exists $x\in \Sigma^{*}$ such that $f(x)=w$. We can apply $f$ on every word lexicographically. Surely, if $w\in f(L)$, the machine accepts. But otherwise, the machine does not halt. So maybe my intuition is wrong?

Inspired by this question, I have come up with the following.

Assume that $\langle\cdot\rangle$ is an encoding for TM's, for which the encoding of one Turing machine is never a prefix of the encoding of another.

Let $f$ be defined as the identity on an input which does not contain a TM enconding as a prefix. If the input contains such a prefix, $f$ returns this prefix.

$f$ is computable and it is well defined due to the encoding property.

Let $L=\left\{ \langle M\rangle n \mid \text{$M$ halts on the empty input after $n$ steps} \right\}$.

Then $L$ is recursive but $f(L)=\left\{ \langle M\rangle \mid \text{ $M$ halts on the blank tape} \right\}$ which is not recursive.


Time complexity of a recursive enumeration in the problem of finding n-tuples of naturals greater than 1 with bounded product I have to determine the time complexity of a recursive enumeration in the problem of finding n-tuples $(k_i, ..., k_n)$ of naturals greater than 1 with product less or equal to $K$. Problem can be formally expressed as: $$\begin{align}0<\prod_{i=1}^nk_i\leqslant K\in\Bbb N,\ k_i \in \Bbb N^{+}\setminus\{1\}&\  \forall i\in\{1,\ldots,n\},\end{align}$$

The number of steps required to enumerate all n-tuples of naturals greater than 1 is:
\begin{equation}
f(K, n) = \sum_{k=2}^{\lfloor \frac{K}{2^{n-1}}\rfloor} \bigg(1 + f(\lfloor \frac{K}{k} \rfloor, n - 1)\bigg)
\end{equation}
\begin{equation}
f(K, 0) = 0
\end{equation}

I can provide trivial time complexity analysis. As every $k_i \leq \frac{K}{2^{n-1}}$ and there $n$ factors which can be in interval $[2,  \frac{K}{2^{n-1}}]$, we have that the maximum number of steps is $(\frac{K}{2^{n-1}} - 1)^n$. Therefore,  complexity in big-O notation should be $O\bigg(\frac{K^n}{2^{n^2-n}}\bigg)$. I do not know if this observation is of any relevance to the time-complexity analysis.

I thought about this problem a lot and I think that I devised a suitable
solution. I focus here on asymptotic analysis with respect to $K$, and my aim
is to provide tighter upper bound than one that I suggested in the
question. Therefore, I now observe slightly different problem
where $k_i \geq 1$. In that case the number of steps $T(K,n)$
required to enumerate all n-tuples of naturals greater or equal one 1 with
product less than or equal to $K$ is:
\begin{equation}
T(K, n) = \sum_{k=1}^{K} T(\lfloor \frac{K}{k} \rfloor, n - 1)
\end{equation}
\begin{equation}
T(K, 0) = 1
\end{equation}
where $T(K, 0)$ is the number of elementary operations in the basic case.

For any bound $x$, we know that:
\begin{equation}
T(x, 1) = \sum_{k=1}^{x} T(x, 0) = x
\end{equation}

Moreover, for $T(x, 2)$ we have:
\begin{equation}
T(x, 2) = T(\frac{x}{1}, 1) + T(\frac{x}{2}, 1) + T(\frac{x}{3}, 1)... + T(\frac{x}{x}, 1) = \frac{x}{1} + \frac{x}{2} + \frac{x}{3} ... + \frac{x}{x}
\end{equation}
We can see that this is in fact finite partial sum of harmonic series:
\begin{equation}
T(x, 2) = x \sum_{k=1}^{x} \frac{1}{k} = x H_x
\end{equation}
where $H_x = \sum_{k=1}^{x} \frac{1}{k}$ is the x-th harmonic number.

Now with $T(x, 2) = x H_x$, $T(x, 3)$ can be expressed as:
\begin{equation}
T(x, 3) = T(\frac{x}{1}, 2) + T(\frac{x}{2}, 2) + ... + T(\frac{x}{x}, 2) = x H_x + \frac{x}{2} H_{x/2} + ... + \frac{x}{x} H_1
\end{equation}
Now we can bound $T(x, 3)$:
\begin{equation}
T(x, 3) = x H_x + \frac{x}{2} H_{x/2} + ... + \frac{x}{x} H_1 \leq x H_x (1 + \frac{1}{2} + ... + \frac{1}{x}) = x H_x^2
\end{equation}

By induction, we get that $T(K, n) = K H_K^{n-1}$. Harmonic number can be
approximated with integral:
\begin{equation}
H_K = \int_{1}^{K} \frac{1}{t} dt = \ln K
\end{equation}

Therefore, an upper bound on complexity is given with $O(K \log^{n-1} (K))$.


How to make an unambigous grammar of a programming language We know that the decision problem of whether an arbitrary context-free grammar is ambiguous is undecidable. My question is how are made the unambigous grammar of programming language? My guessing is that maybe starting from a simple grammar, which is easy to prove that is not ambigous, then adding some rules for which the new grammar is also not ambiugous, of course there must be some theorems which say what kind of rules can be added.
If my guessing is correct I would like to know that theorems.

Grammars of real programming languages are often more restricted than CFG in order to enable efficient parsing. You may have heard of LL(k) and LR(k) grammars, for instance. All these grammars are, by definition, unambiguous; the corresponding language classes are (strict) subsets of DCFL.

You would realize a grammar is ambiguous (or otherwise not in the grammar class at hand) when the algorithm constructing a parser from it fails. Speaking in computability terms, membership for these grammar classes is decidable.


Computability vs Complexity? In Theoretical Computer Science, which one is more important? Computability of a problem or Complexity of a problem?

Both computability and complexity are theoretical abstractions. A theoretical abstraction is most useful, if the gap between theory and practice is small.

It is well known that there is a large gap between a problem whose solutions is computable in theory, and one whose solution is computable in practice. Complexity theory managed to shrink that gap considerably, to the point where the remaining gap is caused by factors like cache behavior, parallelization, large scale distribution and similar advanced practical issues.
Computability theory has been able to prove that certain problems can't be solved. One might believe that there can't be any gap between theory and practice here, but this is not the case. It seems like Gödel's incompleteness theorems from 1931 would prove that the consistency of the Peano axioms can't be decided. However, Gentzen proved the consistency of the Peano axioms in a paper published in 1936. I know that there is a nice theoretical explanation for this, but I'm (still) unable to judge the practical consequences, and I guess I'm not alone in this.
Complexity theory still struggles to rigorously prove lower bounds for most important practical problems, even so it slowly advances in this direction. One may question whether these theoretical lower bounds are important at all, because we have no guarantee that the practical lower bounds have to respect these theoretical bounds. However, it turns out that the practical lower bounds closely match the theoretical lower bounds, so that this objection is unfounded in practice.
The above comparison might suggest that computability theory is not much use in practice compared to complexity theory. However, things like the Chomsky hierarchy and a bunch of other similarly useful results should easily disprove this suspicion.


Finding lambda of Master Theorem Suppose I have a recurrence like $T(n)=2T(n/4)+\log(n)$ with $a=2, b=4$ and $f(n)=\log(n)$.

That should be case 1 of the Master theorem because $n^{1/2}>\log(n)$. There is also a lambda in case 1: $f(n)=O(n^{(1/2)-\lambda})$. Is this correct? And how can I find this lambda?

As you correctly noted, the case 1 of the Master theorem applies here. In other words, the case 1 applies if $f(n) = O(n^{\log_b a - \lambda})$ for some constant $\lambda > 0$.

Indeed, we will have to see if we can find some $\lambda > 0$ so that in this case, $\log n = O(n^{\log_4 2 - \lambda}) = O(n^{1/2-\lambda})$. Easy, we can pick any $\lambda < 1/2$. Finally, be careful what the Master theorem now tells you: the solution to the recurrence

$$T(n) = \Theta(n^{\log_4 2}) = \Theta(n^{1/2}) = \Theta(\sqrt n).$$


Solving recurrence relation for running time of combination formula I'm trying to solve the following Time complexity recurrence relation:
$T(n,k)=T(n-1,k-1)+T(n-1,k)+1$
that  come from following code:
int C(n, k) {
  if (k == 0 || k == n) return 1;  // stop recursion.
  return C(n-1, k-1) + C(n-1, k);
}

Unfortunately, I have no idea to solve $T(n,k)$. Any hint that helpful be appreciated.

Let $C(n,k) = T(n,k) + 1$. Then
$$ C(n,k) = C(n-1,k-1) + C(n-1,k). $$
This is exactly the recurrence of binomial coefficients, though there are also other solutions, for example $2^n$.
You can take the initial conditions to be $T(n,n) = T(n,0) = 1$, and so $C(n,n) = C(n,0) = 2$. You can check that
$$ C(n,k) = 2\binom{n}{k} $$
satisfies both the initial conditions and the recurrence relation. Hence
$$ T(n,k) = 2\binom{n}{k} - 1. $$


Given L is a regular language, prove that Perm(L) is Context-Free Given a regular language $L$ defined over $\Sigma = \{0, 1\}$. We define a new language $$Perm(L) = \{w \mid \exists x \in L, w \in perm(x)\}, $$ where $perm(x)$ is the set of all permutations of the word $x$.
We have to show that $Perm(L)$ is context-free.
I have looked at the properties that neither CFL nor Regular languages are closed under permutation. Also, the problem comes with the following hint.
Hint: Build a PDA for $perm(L)$ which guesses a permutation of the input string and runs the DFA for $L$ on it, and uses the stack to check that it indeed guessed a valid permutation of the input string. The fact that the alphabet has only two symbols will be crucial for the latter check.
I am unable to use this hint to proceed further. Any help is appreciated!

For every symbol $\sigma_i$ that the PDA reads, it guesses a symbol $\tau_i$. It simulates the DFA on the word $\tau_1 \ldots \tau_i$, and will only accept if the DFA accepts. Using the stack, it maintains the following counter:
$$
(\#_a(\sigma_1 \ldots \sigma_i) - \#_b(\sigma_1 \ldots \sigma_i)) -
(\#_a(\tau_1 \ldots \tau_i) - \#_b(\tau_1 \ldots \tau_i)),
$$
and only accepts if this equals zero at the end. Since
$$
\#_a(\sigma_1 \ldots \sigma_i) + \#_b(\sigma_1 \ldots \sigma_i) =
\#_a(\tau_1 \ldots \tau_i) + \#_b(\tau_1 \ldots \tau_i),
$$
the counter equals zero iff $\tau_1 \ldots \tau_i$ is a permutation of $\sigma_1 \ldots \sigma_i$ (this only works because the alphabet is binary).
To see that this approach doesn't work for a ternary alphabet, it suffices to consider
$$
\operatorname{Perm}((abc)^*) \cap a^*b^*c^* = \{ a^nb^nc^n : n \geq 0 \}.
$$


Proof of a lower bound of the recurrence relation (the CLRS's 4.6-2 exercise) I am trying to find a solution to the ex. 4.6-2 of the Introduction to Algorithms by Cormen, Leiserson, Rivest, Stein (the third edition). It requires, for recurrence relations $T(n)=aT(n/b)+f(n)$ where $a\geq 1, b > 1$, $n$ is an exact power of $b$  and $f(n)$ is an asymptotically positive function, to prove that if $f(n) = \Theta(n^{\log_ba}lg^{k}n)$, where $k\geq0$, then $T(n)=\Theta(n^{\log_ba}lg^{k+1}n)$.

Since $T(n) = n^{\log_ba} + g(n)$ where $g(n) = \sum_{j=0}^{\log_b n - 1} a^{j}f(n/b^{j})$, I decided to consider the $g(n)$ function at the first. And I have shown $g(n) = O(n^{\log_ba}lg^{k+1}n)$ already (I think so).

But the doing the proof $g(n) = \Omega(n^{\log_ba}lg^{k+1}n)$ became a challenge for me.

Below is my research (with the simplified assumption $k$ is an integer). By condtition, there is such constant $c$ that

$g(n) \geq$

$c \sum_{j=0}^{\log_b n - 1} a^{j}(n/b^{j})^{log_ba}log^{k}(n/b^{j}) =$

$cn^{\log_ba}\sum_{j=0}^{\log_b n - 1} log^{k}(n/b^{j}) =$

$cn^{\log_ba}\sum_{j=0}^{\log_b n - 1}(logn - logb^{j})^{k} =$

$cn^{\log_ba}\sum_{j=0}^{\log_b n - 1}\sum_{i=0}^{k} {k \choose i}log^{k-i}n(-logb^{j})^{i} =$

$cn^{\log_ba}log^{k}n\sum_{j=0}^{\log_b n - 1}\sum_{i=0}^{k} {k \choose i}(-logb^{j}/logn)^{i} =$

$cn^{\log_ba}log^{k}n \biggl(log_bn + \sum_{j=0}^{\log_b n - 1}\sum_{i=1}^{k} {k \choose i}(-logb^{j}/logn)^{i} \biggr) \geq$

$c'n^{\log_ba}log^{k+1}n - cn^{\log_ba}log^{k}n\sum_{j=0}^{\log_b n - 1}\sum_{i=1}^{k} {k \choose i}(logb^{j}/logn)^{i} =$

$A(n) - B(n) = \Theta(n^{\log_ba}lg^{k+1}n) - B(n)$

Actually I am stuck with it. I can not show that $B(n)$ grows slower than $A(n)$. For instance, since $(logb^{j}/logn)^{i} \le 1$ we are able to enhance our $\geq$ condition by the substitution $B(n)$ to some fucntion $B'(n)$ with the sums of binominal coefficients only. But then finally $B'(n)$ has $n^{\log_ba}log^{k+1}n$.

So how to prove $g(n) = \Omega(n^{\log_ba}lg^{k+1}n)$ ?

All we need to prove is the following, where $b>1, k\ge 0$ and $k$ may or may not be an integer.
$$\sum_{j=0}^{\lfloor\log_b n\rfloor} \left(\log_b\left(\frac n{b^{j}}\right)\right)^k=\Omega((\log_b n)^{k+1})$$

In order to show the idea of the proof clearly, assume that $n = b^m$. The above estimate is
$$\sum_{j=0}^{m} (m-j)^k=\Omega(m^{k+1})$$

Here is the proof.

$$\sum_{j=0}^{m} (m-j)^k=\sum_{i=1}^m i^k\ge\sum_{i=1}^m \int_{i-1}^{i} u^k du=\int_{0}^{m} u^k du = \left.\frac{u^{k+1}}{k+1}\right |^m_0= \frac{m^{k+1}}{k+1} $$


Need help to derive the Complexity! Please help me regarding this one! What will be the communication and computation complexity of this code??

While (m>0) do
{
   While ((m mod 2)==0) do
       {
          m ← ⌊m/2⌋
         //parties communicate m times;
       }
m = m – 1;
}

This code been modified from the book "Fundamental of computer algorithm" by Sahni.So according to that, it seemed computational complexity is O(logm) as m decreases by a factor of at least 2. But can i say communication complexity is O(logm) as well?? Probably not; i'm really confused!!

If $m > 0$ is even then the two parties communicate $m/2$ times at their first round of communication. If $m > 1$ is odd then they communicate $(m-1)/2$ times at their first round of communication. In particular, the communication complexity is not $O(\log m)$, but at least $\Omega(m)$. In fact, it is also $O(m)$, but you'll have to figure out why yourself.


Is two-coloring parts of a bipartite graph so that for each uncolored vertex, the incoming edges from each color are roughly equal NP-complete? Let's say we have a bipartite graph $G=(V_1\dot\cup V_2,E)$.

We're now looking for a two-coloring (red/blue) of the vertices of $V_1$, so that for all vertices $v\in V_2$ the sum of edges coming from red vertices differs at most by 1 from the sum of edges coming from blue vertices.

In other words, we're looking for a two-coloring $c:V_1\to\{-1,1\}$ so that the following formula holds:
$$
\forall v\in V_2:\left( \sum_{v'\in V_1\\\{v,v'\}\in E}c(v')\in \{-1,0,1\}\right)
$$

My question: Is finding such a two-coloring (or showing that no such two-coloring exists) NP-complete?

There's a (somewhat) linear algebra formulation of this problem, though it doesn't seem to be very helpful:

Let $V_1 = \{v_1,...,v_n\}$. Then we can define for every vertex $v\in V_2$ the row vector $(k_{1,v},...,k_{n,v})$ with
$$k_{i,v} =\begin{cases} 1,&\text{if } \{v_i,v'\}\in E\\ 0,&\text{else}\end{cases}$$.

If we now let $c_i\in \{-1,1\}$ be the color of vertex $v_i$, then the requirements for the two-coloring can be written as:
$$
\forall v\in V_2:\qquad (k_{1,v},...,k_{n,v}) \cdot \pmatrix{c_1\\...\\ c_n} \in \{-1,0,1\}
$$
or equivalently with $V_2 = \{v'_1,...,v'_m\}$:
$$
\pmatrix{k_{1,v'_1}&...&k_{n,v'_1}\\...&...&...\\ k_{1,v'_m}&...&k_{n,v'_m}} \cdot \pmatrix{c_1\\...\\ c_n} \in \{-1,0,1\}^m
$$

Your bipartite graph describes a set system whose elements are the vertices in $V_1$ and whose sets are the vertices in $V_2$. Your condition is the same as asking whether the discrepancy is at most $1$.

If all sets have even size (i.e., all vertices in $V_2$ have even degree), then the discrepancy is always even, and so you are interested in whether a given set system in which each set has even size has discrepancy zero. It turns out that this is NP-hard even if all sets have size 4. This problem is known as Max-2-2-Set-Splitting.

There are much stronger NP-hardness results on discrepancy, such as Tight hardness results for minimizing discrepancy by Charikar, Newman and Nikolov. You can find pointers on Max-2-2-Set-Splitting there.


speed of preorder traversal I want to know the speed of preorder traversal of  an tree. I do not mean its order of magntude which we know is O(n).
I want something like 27n  operations where an operation is precisely defined.
Thanks

It's not answerable in the abstract, without a lot more specifics.  It depends on intimate specifics of the computer architecture, what counts as "one" operation, how the tree is represented, and many other details that are usually considered a distraction for purposes of analysis of algorithms.  And it wouldn't really be useful in practice anyway; these days, the time it takes for an algorithm to complete depends on a lot more than the number of operations.  Not all operations take the same amount of time, and more importantly, the memory hierarchy plays a huge role in influencing the running time, and you can't measure its impact by counting operations.


Is the set of all possible finite alphabets uncountable? In my opinion it is uncountable since we can think every natural number as a member of one alphabet like $\quad0\in\sum_0 ,1\in \sum_1, ... \quad$ And there are also other symbols than natural numbers in alphabets. So there is no possible 1:1 and onto mapping from set of all alphabets to natural numbers. Thus they cannot be enumerated which means they are uncountable. Is there anything wrong with my approach?

Your approach can essentially be summarized as:

I define an injection between $\mathbb{N}$ and my set $S$.
This injection is not a bijection because some elements of the codomain are left unmapped.
Therefore there exists no bijection between $\mathbb{N}$ and $S$.

Stated like this, it is perhaps clear that the last statement does not follow from the others. An example of where this reasoning would fail is if we let $S = \mathbb{Z}$ and let the injection be the identity function (mapping naturals to themselves). This leaves all the negative integers in the codomain unmapped, but we know that $\mathbb{Z}$ is countable.


Not able to find any pattern for $4T(n/2)+n^2 n^{1/2}$ I have tried my best but I'm not able to find any pattern for the $n^2n^{1/2}$ part. This question must be solved  iteratively and I get totally clueless after two iteration.s I've to find tight bound in big-O.

Here is what happens when you expand the recurrence:
$$
\begin{align*}
T(n) &= n^{5/2} + 4(n/2)^{5/2} + 4^2(n/2^2)^{5/2} + 4^3(n/2^3)^{5/2} + \cdots \\ &=
n^{5/2} \left(1 + \frac{4}{2^{5/2}} + \left(\frac{4}{2^{5/2}}\right)^2 + \left(\frac{4}{2^{5/2}}\right)^3 + \cdots \right).
\end{align*}
$$
Since $4/2^{5/2} = 1/\sqrt{2} < 1$, the large bracketed expression converges, and so the answer is $T(n) = \Theta(n^{5/2})$.


Monotone Frameworks: Transfer functions for flow edges instead of labels So, in generic program analysis, we have a lattice $L$ with a join operation $\sqcup$, program with statements labelled, and for each label $b$, a transfer function $F_b : L \rightarrow L$.

The goal is to find, for each label $b$, a fix-point $x$ such that $F_b(x)=x$. This is a common approach used in dataflow analysis,

In "Principles of Program Analysis" by Nielson, Nielson and Hankin, they reference that "Some formulation of monotone frameworks associate transfer functions with edges (or flows) rather than nodes (or labels)." However, in the textbook, they simply reference an exercise where the reader is asked to implement such a framework.

I'm wondering if anyone has a reference to either a book or paper where such a formulation is given. In particular, I'm wondering how a typical worklist algorithm for finding a fixed-point would be formulated.

Your formulation is not stated in the way I typically think of it.  Traditionally rather than thinking of looking for a fixed point at each node, we're looking for a solution to a system of simultaneous equations:

$$ x_b = F_b \left( \bigsqcup_{p \in \mathtt{pred}[b]}x_p \right) \; \mathrm{for\:all\:nodes}\:b $$

If $F_b$ has the distributive property over $\sqcup$ then you can simply rewrite this as

$$ x_b = \bigsqcup_{p \in \mathtt{pred}[b]} F_b(x_p) \; \mathrm{for\:all\:nodes}\:b $$

and since you have a function evaluation for every edge $p \rightarrow b$ you might as well just rewrite it as

$$ x_b = \bigsqcup_{p \in \mathtt{pred}[b]} F_{p \rightarrow b}(x_p) \; \mathrm{for\:all\:nodes}\:b $$

If you don't like that handwaving, then here's some more: think of it as taking $F_b$ for every node with one predecessor ($p$) and pushing $F_b$ onto the edge making it $F_{p \rightarrow b}$.  For nodes $b$ with more than one predecessor split them into two nodes, $b$ and $b'$.  The predecessors of $b$ are still the same, then there's an edge $b \rightarrow b'$ and then the successors of the original $b$ become the successors of $b$.  Now the original label $F_b$ becomes $F_{b\rightarrow b'}$.  The join operation still happens on the nodes.

Note that while transfer functions are associated with edges, data flow facts are still associated with nodes.  So the worklist algorithm doesn't really change.  Actually, with the normal (transfer functions on nodes) formulation, the worklist algorithm is really a worklist of edges, not nodes, so nothing changes.  (For an example of this take a look at these slides that came up when I googled for "dominance frontier".  http://www.seas.harvard.edu/courses/cs252/2011sp/slides/Lec04-SSA.pdf.  They give the worklist algorithm on page 7, and it's based on edges.)

A paper using the edge formulation is:

  G. Ramalingam: Data Flow Frequency Analysis. PLDI 1996: 267-277.

(I haven't read the paper beyond the first couple of pages to see that they were using the edge formulation, it's what came up after a bit of Googling.)

I wasn't familiar with the edge transfer function approach until you asked this question.  But I also know of at least two cases where it is important to take edges into account.

The first is when dealing with (post)dominance frontiers.  The natural definition of the dominance frontier of a node is a set of edges, but the original (more complicated) formulation was in terms of nodes.  See for example the (brief) discussion of this in

  Pingali, Keshav; Bilardi, Gianfranco: Optimal Control Dependence Computation and the Roman Chariots Problem, ACM ToPLaS, 19(3):462-491, 1997.

Another example is in the classic

  Knoop, J; Rüthing, O; Steffen, B: Lazy Code Motion, PLDI, 1992.

In Lazy Code Motion you sometimes need to move computations onto edges, but in the original formulation in the paper they were trying to move those computations to different nodes, which gave them trouble with branch nodes that target join nodes.  They called these critical edges and had to add a node along the edge.  This is explained in the following lecture notes by Cooper and Torczon:
https://www.cs.utexas.edu/~pingali/CS380C/2013/lectures/LazyCodeMotion.pdf


Silly question: what counts as a "unit of work" when computing big-Oh time complexity I am going through a fairly non-rigorous textbook called 'Cracking the code interview' and I am bothered by this terminology called "unit of work".
It says in the textbook that certain operations take constant work, where as others take variable amount of time.
For example, adding/subtracting/multiplying/dividing two numbers take constant work. Similarly, a comparison statement also takes constant work. Lookup are also constant.
Whereas other operations such as for-loop takes a variable amount of work. For example, if a FOR-loop is to be run from $i = 0$ to $i = n-1$, and assuming whatever inside of the FOR-loop takes constant amount of time, then the total amount of work is proportional to $n$. That is, FOR-loop takes $O(n)$ time.
Something that doesn't really make sense to me is the smallest unit that can be defined as "work" in big Oh runtime analysis. What is this unit based off of? Adding two bits together? Adding two integers together?
Stemming from it are two related concerns:

certainly multiplication takes more "work" than addition. Division takes more work than subtraction. So what is the smallest unit of work here? Is the time to add two numbers a smaller amount of work than multiplying two numbers? That is, is the work of multiplication proportional to the time of addition?, $\text{work}_{\times} = c \times  \text{work}_{+}, c > 0?$

For example, are things like multiplication truly independent of the input? $k \times n = n + n + \ldots + n$ ($k$ times). So why is it considered a constant amount of work? Doesn't the same logic also apply to other programs? Say if I have $n$ conditional statement checking if a value is smaller or greater than a number $n$. Then this "constant" operation can still depend on how large my $n$ is (depending on how i implement this comparison).

Thanks for your patience.

We assume an efficient implementation of standard arithmetic operations (since a stupid implementation could be replaced with a better one). Of course, if the numbers were of unlimited size, the amount of time wouldn't be constant. But it would still be constant per bit (at least for addition and comparison).
So if we pretend that all numbers are a constant size ("one unit of storage") and we pretend that all additions are constant time ("one unit of work"), we get the same relationship between input size and processing time as we would if we worked it out measuring space in bits and processing time in single-bit operations: time is linear in input size.
Complexity analysis is not about nanoseconds. You can't figure out how many nanoseconds an algorithm will take just by looking at the algorithm. What we can figure out is what happens to the time if you increase the problem size. Twice as long is twice as long regardless of what the measurement unit is. The measurement unit is irrelevant as long as we use the same one throughout.
Now, if we were really doing arbitrary precision arithmetic, multiplication and division would take polynomial time. But for most algorithms, taking that into account would massively complicate the analysis without adding much new information. So it's convenient to pretend multiplication and division are linear time.


Why aren't tries generally used? To store say integers (positive), we prefer to use red black BSTs. I have never seen a explicit use of a trie anywhere to store numbers.
I believe we can convert numbers to string and store them in tries for fast retrieval.
Is it a bad idea to use tries?
We don't use them because they are hard to code and there are libraries for BSTs or is there some other reason?

This is an interesting question. Certainly worth asking.

The choice of a data structure is very much dependent on what you want
to do with it. A more costly sophisticated structure, no matter how
smart, is a bad choice if you can meet your need with something
cheaper in space or time.

As I was writing this answer, I discovered that the wikipedia article
on tries does discuss to a significant extent comparison of tries with other
data structures.

One advantage of binary search trees (BST) is that they keep ordered
lists, for some arbitrary order that can be tested.  Actually the
order is often used only to help organization and retrieval, but there
are applications where you want to actually access the elements of your
ordered subset following the order of elements.  BST will provide you
with such an order.

I do not see any obvious way of doing it with
tries for an arbitrary order (but I did not try hard). However, tries
do work with lexicographic order, and can be used for lexicographic
enumeration of the keys, using simply a preorder traversal of the
tree implementing it.

Similarly, asking for the current rank of an element in the set
represented by a BST , or accessing an element by its current rank is
fairly easy to implement in $\log n$ time (by keeping track of the
weight of subtrees).  It seems not so tractable on a trie, except
again if one is interested in lexicographic order, in which case the
solution is similar to that used for BST.

Another point to consider is cost of basic operations (insertions,
deletions, search). With a balanced BST it is done in $\log n$ time,
where $n$ is the number of elements. For a trie, the cost is linear in
the size of the element representation. It is hard to compare the two
kinds of cost, and one would think the choice is very much problem
dependent.  This also applies to such operation as access by rank, or
rank retrieval.

The cost of number representation in a BST or in a trie may also be an
issue, as a trie will represent each digit separately (up to some
optimizations). It is possible that, for very large numbers, expressed
with a large base, the trie representation would be a better choice. I
am not sure.

There is probably more to say. The conclusion is that it is probably
worth thinking whether tries can be used, but it may be actually limited.


What will be the pictorial diagram of this transition table? I was doing my homework and I am confused on what I'm doing, it can't be that straightforward. I'm making a mistake somewhere. I tried looking for practice problems but they don't cover my issue either, I'm still confused. What will be the pictorial diagram for the following transition table?

You just create a super simple Graphviz document encoding the information:

$ cat foo.gv
digraph {
  q0 -> q0 [label = "input: a\noutput: 0"];
  q0 -> q2 [label = "input: b\noutput: 0"];
  q1 -> q1 [label = "input: a\noutput: 1"];
  q1 -> q0 [label = "input: b\noutput: 1"];
  q2 -> q2 [label = "input: a\noutput: 1"];
  q2 -> q1 [label = "input: b\noutput: 1"];
}
$ _

Process it:

$ dot foo.gv -T png -o foo.png
$ echo $?
0
$ _

Profit!


Sorted unsigned integer intervals tree structure The goal is to store sorted unsigned integer intervals that can overlap only in the boundaries, e.g., |0–10|10–50|100–110|110–200|. This structure will be created by some insert operations (the order matters) in the start and than queried by a lot of queries. The query is specified by interval and the result is all intervals from structure that has at least a partial overlap.

There is no need to delete inserted data (delete operation), but the new inserted interval can overwrite the existing ones. Please consider the following example.

|0–10|10–50|100–110|110–200|
insert: 40–70
|0–10|10–40|40–70|100–110|110–200|
insert: 105–115
|0–10|10–40|40–70|100–105|105–115|115–200|

What structure do you recommend?

Interval trees seem like a natural candidate. The Wikipedia page has links to implementations in various languages.
You can overwrite an existing interval by querying its endpoints, then removing the resulting intervals on the left and right, and then adding back the truncated intervals together with the new one.


Polynomial hierarchy intersection While familiarizing myself with polynomial hierarchy, I have come across a problem
of showing $NP^{\Sigma_{k}^{p} \cap \Pi_{k}^{p}} \subseteq \Sigma_{k}^{p}$. By looking at the proof for $NP^{SAT} \subseteq \Sigma_{2}^{p}$, I got the concept
where we can guess the choices of the NTM and answers to SAT call and then encode
the correctness of these answers. However, while I understand encoding correctness of answers for SAT calls, I have a problem of doing the same for the oracle $\Sigma_{k}^{p} \cap \Pi_{k}^{p}$, which has no known complete problems. It seems to me there is a cookbook way of proving this that I am missing?

I will assume the following definition for $\mathit{NP}^{\Sigma_k^p \cap \Pi_k^p}$: it is the class of languages decided by polytime non-deterministic Turing machines with oracle access to a language in $\Sigma_k^p \cap \Pi_k^p$. Consider now some $L \in \mathit{NP}^{\Sigma_k^p \cap \Pi_k^p}$ which is decided by some NP machine $M$ with oracle access to a language $K \in \Sigma_k^p \cap \Pi_k^p$.

Since $K \in \Sigma_k^p \cap \Pi_k^p$, there are $\Sigma_k^p$-witnesses to both $x \in K$ and $x \notin K$. Including all such witnesses, the NP machine $M$ becomes an absolute $\Sigma_k^p$ machine (we fold the first $\exists$ quantifier).

In more detail, we can write $L$ as $x \in L \leftrightarrow \exists |y|<|x|^C P(x,y)$ for some predicate $P$ which is polynomial time with oracle access to $K$. Since $P$ runs in polynomial time, it makes at most polynomially many queries to $O$. We construct a new predicate $P'$ which guesses the results $b_1,\ldots,b_T$ of these queries $q_1,\ldots,q_T$. Since $K \in \Sigma_k^p \cap \Pi_k^p$, if $b_i = T$ ($b_i = F$) then for some polytime $P_+$ ($P_-$) we have
$$\exists |w_{i,1}| < |x|^{C_1} \forall |w_{i,2}| < |x|^{C_2} \cdots Q |w_{i,k}| < |x|^{C_k} P_{\pm}(q_i,w_{i,1},\ldots,w_{i,k}).$$
By combining $P$ with the machines $P_+,P_-$ we can come up with a polytime predicate $P'$ such that
$$ x \in L \leftrightarrow \exists |y| < |x|^C \exists b_1,\ldots,b_T \exists |w_{1,1}|,\ldots,|w_{T,1}| < |x|^{C_1} \cdots Q |w_{1,k}|,\ldots,|w_{T,k}| < |x|^{C_k} \\ P'(x,y,\vec{b},\vec{w}). $$
Folding the first three existential quantifiers, we see that $L \in \Sigma^p_k$.


Insertion sort Pseudo code vs implementation? So I'm trying to implement an insertion sort algorithms based on page 18 Cormen psuedocode but I'm confused by for j = 2 to A:length. Specifically, what does the j=2 mean? I'm implementing it using the below python code and it only works when the range is the entire length of the array:
def insertion_sort(arr):
    # length of array
    n = len(arr)

    # traverse through array
    for i in range(n):
        key = arr[i]
        j = i - 1
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key

Could someone explain?

The following two points might clear your confusion.

The pseudocode in the book is following $1$ based indexing. Your code is following $0$ based indexing.

Your code is technically doing nothing in the first iteration of the while loop. In the first iteration $i = 0$, therefore $j = -1$. Since $j<0$, the inside while loop is not executed. And it keeps $A[0] = key$ to its original value. Effectively, your code starts executing from $i = 1$, which is equivalent to $j = 2$ in CLRS implementation.


Shortest walk through a given subset of edges Given an undirected weighted graph $G = (V, \{E,F\})$, how to find the shortest walk that passes through all edges $e \in E$ exactly once?

I'd like to know if there is a general approach to this problem. However, additional constraint may be added for my specific scenario.

The graph $G_0 = (V, E)$ initially has only edges that must be crossed, but it's disconnected:

Each connected component is formed by 2 vertices and 1 edge.
Each vertex $v$ is the endpoint of exactly one edge $\in E$. This means that any two edges $e_i, e_j \in E$ don't have a vertex $v$ in common.
The cost of each edge $e \in E$ is $0$.
The number of edges in $E$ is at most 1000, usually between 10 and 100.

Then other edges $f \in F$ are added with to link any two vertices (except the one already linked by $e$), so $G = (V, \{E,F\})$.

The cost of each edge $f \in F$ is $> 0$

Related questions

I found a few related questions, but they doesn't seem to help:

Shortest path from that passes through a set of edges once: edges $e \in E$ must be visited exactly once, not at most once.
Shortest directed path connecting given subset of vertices, Minimum path between two vertices passing through a given set exactly once, Find the shortest path in a graph which visits certain nodes : the constraint is on edges, not on the vertices.

Not working solutions

I tried a few approaches so far, but I'm unable to make them work properly. E.g.:

Convert $G$ to its line graph $L$. I can't figure out how to assign a proper weight to edges in $L$
If I can find a proper way to construct $L$, adding a dummy vertex $s$ on $L$ allows to solve this with TSP. Then I'll know the order of the edges $e$, but not the direction.
I really don't want to use brute-force. It may become impractical very soon.

Almost-Working solutions for the specific case

Since by construction every walk will be of the form: $e_1, f_1, e_2, ... f_n, e_n$:

Compute the weight of the path for each permutation of edges in $E$. The edge $f$ between two edges $e$ will be the mininmum weight one. Pick up the minimum weight path. This solution is brute-force, so not really practical for a large number of edges in E.
Start from an edge $e$. Follow the min-cost edge $f$ starting from the end-vertex in $e$. Repeat until all edges in $E$ are reached. This solution is not guaranteed to find the shortest path.

This is NP-hard, so it's very unlikely that a polynomial-time algorithm exists.

Given any instance $G=(V, E)$ of Hamiltonian Path, create a new graph $G'=(V', E')$ in which every vertex $v \in V$ becomes a pair of vertices $v_+, v_-$ connected by an edge in $G'$.  All of these edges should also be added to $F$.  Then for each $(u, v) \in E$, add the corresponding 4 edges $(u_-, v_-), (u_-, v_+), (u_+, v_-), (u_+, v_+)$ to $E'$ (but not to $F$).  All edges in $E'$ get weight 1.

Now if and only if there is a Hamiltonian Path in $G$, there is a path (and thus also a walk) of length $2|V|-1$ in $G'$ that passes through all the edges in $F$.  (Exercise: Prove that if a walk having length $2|V|-1$ and passing through all edges in $F$ exists in $G'$, then $G$ has a Hamiltonian Path; the other direction is easy.)  IOW, if your problem could be solved efficiently by some algorithm, then that algorithm could be used as a subroutine to solve Hamiltonian Path efficiently too, and people don't think that's very likely.


What are transitive successor and transitive predecessor in the graph? I'm reading a book on compilers, Engineering a Compiler, 2nd ed. by Keith D. Cooper & Linda Torczon and I came a across two new terms that I can't understand, they are:

  transitive successor and transitive predecessor of a node $i$

I tried to find definitions of those online, but I'm having hard time with it. Everything I find talks about transitive reduction.

Can someone give a clear definition of this? Any help is appreciated.

If you ask Google with "transitive successor" (including the double quotes) you get several book
references, and access to some pages (which I cannot read right now,
because of a local problem). Considering that successor is a
relation between the nodes of the directed graph, "transitive
successor" should naturally be its transitive closure. One book is
apparently using the term "direct successor" to be precise and avoid
confusion with "transitive successor" which could occur when using
"successor" alone.


How do I build a read/write 4-nibble RAM memory system using flip flops? Currently, I'm learning about flip flops and how it is used in RAM to store memory so I'm trying to recreate the circuitry in Logisim.  I know the components I need which are address register, 4-bit data register, 1 bit read/write register and the actual 4 nibble RAM with its own address space and data space.  How do I create each individual pieces and put them together?

You need to put multiplexers and selector/decoders around your flipflops.

The read path needs to multiplex each nibble using the 2 address line.

The write path is selecting with these two address lines with nibble should be modified.


Research on evaluating the performance of cache-obliviousness in practice Cache-oblivious algorithms and data structures are a rather new thing, introduced by Frigo et al. in Cache-oblivious algorithms, 1999. Prokop's thesis from the same year introduces the early ideas as well.

The paper by Frigo et al. present some experimental results showing the potential of the theory and of the cache-oblivious algorithms and data structures. Many cache-oblivious data structures are based on static search trees. Methods of storing and navigating these trees have been developed quite a bit, perhaps most notably by Bender et al. and also by Brodal et al. Demaine gives a nice overview.

The experimental work of investigating the cache behaviour in practice was done at least by Ladner et al. in A Comparison of Cache Aware and Cache Oblivious Static Search Trees Using Program Instrumentation, 2002. Ladner et al. benchmarked the cache behaviour of algorithms solving the binary search problem, using the classic algorithm, cache-oblivious algorithm and cache-aware algorithm. Each algorithm was benchmarked with both implicit and explicit navigation methods. In addition to this, the thesis by Rønn, 2003 analyzed the same algorithms to quite high detail and also performed even more thorough testing of the same algorithms as Ladner et al.

My question is

  Has there been any newer research on benchmarking the cache behaviour of cache-oblivious algorithms in practice since? I'm especially interested in the performance of the static search trees, but I would also be happy with any other cache-oblivious algorithms and data structures.

You've already covered background research on cache-oblivious algorithms quite well. In terms of benchmarking and practical results, I see this recent paper by Intel as an interesting read:

A Synergetic Approach to Throughput Computing on x86-based Multicore Desktops


What is the reason for writing parallel programs? Why do programmers write parallel programs instead of giving them the ability to automatically convert from serial to parallel?

Because the technology to extract paralellism automatically from sequential programs is still woeful... yes, some compilers/languages do take a stab at the problem, but for really demanding applications it still pays off to do the job manually.


Computational power of nondeterministic type-1 min-heap automata with multiple heaps I have asked a series of questions concerning capabilities of a certain class of exotic automata which I have called min-heap automata; the original question, and links to others, can be found here.

This question concerns the power of type-1 min-heap automata, which represent my initial idea for how these machines would operate. The class of languages which can be accepted by such automata is incomparable (i.e., neither a proper subset nor a proper superset) of the set of context-free languages.

Push down automata, which possess a single stack for data storage, accept the set of context-free languages, in the same way that min-heap automata, which possess a single heap for data storage, accept the set $HAL_1$ of languages accepted by nondeterministic type-1 min-heap automata. Push-down automata with two stacks are equivalent to Turing machines in computational power; they can simulate Turing machines, and vice versa; which leads me to my question:

  Does adding another heap to non-deterministic type-1 min-heap automata make them equivalent in terms of computing ability to Turing machines, in the sense that they are able to simulate Turing machines? If not, does it increase their computational power at all, in the sense that nondeterministic type-1 min-heap automata can accept a set of languages which is a proper subset of $HAL_1$? If so, does adding additional heaps increase computational power, i.e., can nondeterministic min-heap automata with $k+1$ heaps accept more languages than automata with $k$ heaps, for any $k$?

This is one of the last questions I plan to ask about these automata; if good answers can be had for these (and other) questions, my curiosity will be completely satisfied. Thanks in advance and for all the hard work so far.

Let $\mathrm{SDL}_k$ the shuffled Dyck language with $k$ types of parentheses, i.e.

$\qquad \displaystyle \mathrm{SDL}_k = \mathrm{DL}([_1,]_1) \, ш\, \dots \, ш\, \mathrm{DL}([_k,]_k)$

with $ш$ the shuffle of languages and $\mathrm{DL}(\_,\_)$ the Dyck language with matching parenthesis as specified. Intuitively, any word in $\mathrm{SDL}_k$ contains of $k$ properly nested words of parentheses interleaved arbitrarily; for instance, $[_3 [_1 [_1 [_3 [_2 ]_1 ]_3 ]_2 [_1 ]_1 [_2 ]_1 ]_3 ]_2\in \mathrm{SDL}_3$.

Fact 0: $\mathrm{HAL}_1^{(k)} \subseteq \mathrm{HAL}_1^{(k+1)}$ for $k\geq 1$

Claim 1: $\mathrm{SDL}_k \in \mathrm{HAL}_1^{(k)}$ for $k\geq 1$

Claim 2: $\mathrm{SDL}_{k+1} \notin \mathrm{HAL}_1^{(k)}$ for $k\geq 1$ (the claim is wrong; see below)

Together, fact and claims show that $\mathrm{HAL}_1^{(k)} \subset \mathrm{HAL}_1^{(k+1)}$ and $\mathrm{HAL}_1^{(k)} \subset \mathrm{RE}$ for for $k\geq 1$.

Ad Claim 1: It is clear that $\mathrm{DL}([,]) \in \mathrm{HAL}_1$; min-heaps can implement a counter that is increased by one on $[$ and decreased by one on $]$. A word is accepted if and only if the counter never becomes negative and is zero at the end.

The same principle is used for $\mathrm{SDL}_k$ on a $k$-heap automaton; we maintain one counter per parenthesis type on a dedicated heap each and accept if and only if no counter becomes negative and all counters are zero at the end.

Ad Claim 2: This is more a sketch. In order to accept $\mathrm{SDL}_{k+1}$ an automaton has to be able to check at any time wether $]_i$ is allowed next for any $i=1,\dots,k+1$. As nesting depth and "shuffle depth" are unbounded, finite control can not do this (not even for one parenthesis type). Since a $k$-heap automaton can only access $k$ bits of (heap) information at any time, it has no way of doing the necessary checks.

Claim 2 is in fact false. We have to be remember that type-1 heap automata can essentially store a finite amount of counters but can only access the top most. With two heaps, we can access all counters of the first heap: if we want to access counter $i$, move the symbols encoding counters $1,\dots,i-1$ to the second heap, access counter $i$ and move everything back. That leads us to the following claims:

Claim I: $\mathrm{HAL}_1 \subset \mathrm{HAL}_1^{(2)}$

Claim II: $\mathrm{HAL}_1^{(2)} = \mathrm{HAL}_1^{(3)} = \dots$

Claim I follows from above reasoning with $\mathrm{SDL}_2$. Claim II holds because $k$-heap automata can only manage finitely many counters, no matter the $k$, which can be simulated by a $2$-heap automata as outlined above.

This train of thought leads us to

Claim III: $\mathrm{HAL}_1^{(2)} \subset RE$

as Turing machines can handle unbounded numbers of counters, outclassing $2$-heap automata. As a concrete example, consider

$\qquad \displaystyle \mathrm{SDL} = \bigcup\limits_{k\geq 1} \mathrm{SDL}_k.$

Note that $\mathrm{SDL}$ can be expressed using a finite alphabet by encoding $[_i$ as e.g. $[\{\overline{i}\}$ with $\overline{i}$ the binary representation of $i$ and $]_i$ similarly.


Proof of bucket sort worst case being all elements in one bucket By bucket sort I mean on dividing numbers between 0 and 1 into $n$ buckets and performing insertion sort on all the buckets.

1| n ← length [A]
2| For i = 1 to n do
3|     Insert A[i] into list B[nA[i]]
4| For i = 0 to n-1 do
5|     Sort list B with Insertion sort
6| Concatenate the lists B[0], B[1], . . B[n-1] together in order.

The time taking task is lines 4 and 5, which on uniform distribution takes $\Theta(n)$ time. So the worst case, by intuition, I can say is $\Theta(n^2)$ when all the elements fall into one bucket (standard insertion sort on $n$ elements).

But how can I prove that the worst case for this algorithm is when I take all elements in one bucket? Bucket sort worst case stuff I've seen online directly say that the worst case is when we have all elements in that one bucket. But how can I prove this in the first place? Thanks!

For an upper bound on the worst-case cost, it's sufficient to show that it can't be worse. Assuming that insertion sort takes $\leq cn^2$ steps on $n$ elements, consider the sum

$\qquad\displaystyle \sum_{i=1}^n c |B_i|^2$;

it is an upper bound on the cost of sorting all the buckets. For an upper bound on the worst case for bucket sort, maximize this function subject to $\sum |B_i| = n$ (and add the remaining cost, which is $O(n)$ for all inputs).

For a lower bound on the worst-case cost, we have to find an infinite class of actual inputs and show that their cost behaves as claimed. $[0, \dots, 0]$ serves to show an $\Omega(n^2)$ lower bound, as you note.


Abstractions in call-by-push-value In "Call-by-push-value: A subsuming paradigm." (Levy, Paul Blain. Springer, Dordrecht, 2003. 27-47) terms of the lambda calculus get split in to values and computations, with the slogan "A value is, a computation does".

What I don't understand is: why are abstractions computations and not values? Intuitively a function does not do anything and can be used as data. It will only do something when applied to something.

thanks for your interest in call-by-push-value.  The fact that functions (all functions, not just lambda-abstractions) are computations is the main difference between call-by-push-value and call-by-value (where functions are values), and it does seem strange at first.  But the mystery is (somewhat) resolved when you see the CK-machine, which is a kind of operational semantics that uses a computation and a stack.  In terms of that machine, a function of type A -> B is a computation that aims to pop a value of type A and then behave as a computation of type B.  For example:

    print "hello".
    lambda x.
    print "hello again".
    return x

is a computation that first prints "hello", then pops x ("lambda" means "pop"), then prints "hello again", then returns x.  And actually, the same phenomenon of "lambda" as "pop" is present in call-by-name; that's why call-by-push-value manages to subsume call-by-name.

I hope that helps!  I should also say that the origin of call-by-push-value is that it was empirically observed within the models.  The slogan was designed to fit the language and not the other way round.  But that's just saying probably a less helpful answer, because it's just saying "the language is that way because the models say so".


Is every CPU instruction ultimately read and write? Is every instruction ultimately all read or write instructions? So, how I imagine this is that every place where something can be stored can be either in a read or write state, including the CPU registers.

How this is controlled is by the control unit. Every instruction goes through the control unit which is connected to the control bus and flips memory locations (computer memory addresses) to either read or write state.

I understand that there is much more too this depending on what information the control bus can carry, but is this general overview correct in how data is moved about?

Ultimately, the state of the machine must change after executing every single instruction: if it did not, then the machine would be stuck in an infinite loop of executing the same instruction again and again. So, in that sense,  some value in memory or in a register to be changed after each instruction is executed. At a minimum, this would be advancing the program counter.

If you want to count that as a "write" instruction then, yes, every instruction is a write instruction. However, then we would be in the situation that the phrase "write instruction" would mean exactly the same thing as "instruction", so it wouldn't be a useful piece of terminology. OK, so perhaps we want to define a write instruction to be one that directly alters a register or the main memory, where, by "directly alters", I'm excluding the automatic increment of the program counter.  Well, OK, but that's not very useful, either, since every instruction I can think of does that, apart from a no-op.  That wouldn't be a useful definition, either.

So, typically, "write instruction" is understood to mean an instruction that writes a value to some location in the main memory. Clearly not all instructions do that: for example, typical arithmetic instructions operate only on the registers.  Similar arguments can be made for reading.


Max flow not min cut? I understand the relation between max flow and min cut, however I made this (simplified) graph, and I cant figure out why max flow seems to be different from my min cut. Im probably overlooking something simple, but I've been staring at this for 10 minutes now...
Can anyone explain what Im missing?

The edge from $2$ to $3$ isn't part of the minimum cut. It's oriented in the wrong direction, from the sink side to the source side, so you can delete it from your cut and there's still no path from $s$ to $t$.