Why does substitution terminate? I'm formalizing some properties of lambda calculus in Coq and I have some problems proving termination of substitution. My terms are defined as:

Inductive Term :=
  TVar: nat -> Term
| TAbs: nat -> Term -> Term
| TApp: Term -> Term -> Term.

and I have a way of generating fresh variables using a function

fresh: Term -> nat

satisfying:

Lemma fresh_is_fresh:
  forall t,
    ~ FV t (fresh t).

and similarly a function fresh2: Term -> Term -> nat for obtaining a fresh identifier wrt. two terms.

I now want to define a standard notion of capture avoiding substitution:

Fixpoint substitute (t1:Term) (t2:Term) (x:nat): Term :=
  match t1 with
  | TVar y =>
    if beq_nat x y then t2 else TVar y
  | TApp t11 t12 =>
    TApp (substitute t11 t2 x) (substitute t12 t2 x)
  | TAbs y t =>
    if beq_nat x y then
      TAbs x t
    else TAbs (fresh2 t t1) (substitute (substitute t (TVar y) (fresh2 t t1)) t2 x)
  end.

Obviously, Coq cannot see that this definition is terminating, so I need to provide a custom measure, so that the code is something like the following:

Program Fixpoint substitute (t1:Term) (t2:Term) (x:nat) {measure ???}: Term :=
  match t1 with
  | TVar y =>
    if beq_nat x y then t2 else TVar y
  | TApp t11 t12 =>
    TApp (substitute t11 t2 x) (substitute t12 t2 x)
  | TAbs y t =>
    if beq_nat x y then
      TAbs x t
    else TAbs (fresh2 t t1) (substitute (substitute t (TVar y) (fresh2 t t1)) t2 x)
  end.

Now my question is: What is the correct measure to use here? And how I do use it to prove the obligations which arise using this measure?

Derek Elkins' comment solved my problem! Here's the solution I came up with:

We create a seperate renaming function rename: Term -> nat -> nat -> Term, which assumes that the name to rename with is fresh. This makes it trivially terminating.

Fixpoint rename (t:Term) (x y : nat): Term :=
  match t with
  | TVar z =>
    if beq_nat y z then TVar x
    else TVar z
  | TApp t1 t2 =>
    TApp (rename t1 x y) (rename t2 x y)
  | TAbs z t =>
    if beq_nat y z then
      TAbs z t
    else
      TAbs z (rename t x y)
  end.

we then define a (somewhat arbitrary) measure of a term:

Fixpoint size (t:Term): nat :=
  match t with
    TVar _ => 1
  | TApp t1 t2 => size t1 + size t2
  | TAbs x t => 2 + size t
  end.

and we can easily prove that renaming preserves this measure:

Lemma rename_preserves_size:
  forall t x y,
    size t = size (rename t x y).

this lemma is used in the final case of substitition in order to prove that the term rename t y' y has the same size as t and thus the call substitute (rename t y' y) t2 x happens on a strictly smaller term.

Now all I need to prove that this is correct.


Box and triangle intersection I am looking for geometry algorithm.

I have an axis-aligned box $B$ and a triangle $T$ in 3D space. I want to compute an axis-aligned bounding box of their intersection.

Both $B$ and $T$ are convex polytopes and $B\cap T$ is also convex polytope. I don't need general algorithm, I need something fast and simple.

Have you heard about such an algorithm? Or is it trivial and I can't see it?

I got an idea to "crop" the triangle with each of 6 box's faces. Cropping triangle with each plane can add 1 new vertex, so the resulting object may have up to 9 vertices. Then I compute the bounding box of that object. Am I right? Can it be simplified to get only bounding box output?

The following answer is incorrect.

Suppose the triangle has vertices $(x_1,y_1,z_1), (x_2,y_2,z_2), (x_3,y_3,z_3)$ and the box has coordinates $[x_\min, x_\max] \times [y_\min,y_\max] \times [z_\min, z_\max]$.  Then the bounding box of their intersection is $[x'_\min, x'_\max] \times [y'_\min,y'_\max] \times [z'_\min, z'_\max]$, where
\begin{align*}
    x'_\min &= \max\{\min\{x_1,x_2,x_3\}, x_\min\}, \\
    x'_\max &= \min\{\max\{x_1,x_2,x_3\}, x_\max\}, \\[1ex]
    y'_\min &= \max\{\min\{y_1,y_2,y_3\}, y_\min\}, \\
    y'_\max &= \min\{\max\{y_1,y_2,y_3\}, y_\max\}, \\[1ex]
    z'_\min &= \max\{\min\{z_1,z_2,z_3\}, z_\min\}, \\
    z'_\max &= \min\{\max\{z_1,z_2,z_3\}, z_\max\}. \\[1ex]
\end{align*}


Pumping Lemma for Regular Languages with 3 variables (a^nb^mc^m) I've been trying to understand the pumping lemma, and how to apply it to a language such as a^nb^mc^m where n >= 0 and m >= 0. The pumping lemma states that:

For any regular language L, there exists an integer n, such that for all x ∈ L with |x| ≥ n, there exists u, v, w ∈ Σ∗, such that x = uvw, and

(1) |uv| ≤ n

(2) |v| ≥ 1

(3) for all i ≥ 0: uviw ∈ L

It states that there exists some n such that this holds true. In the language a^nb^mc^m if I were to replace m with the pumping length, and choose a pumping length, for example 3, such that a^nb^pc^p I could get the string:

aabbbccc

If I chose:

x = aa

y = b

z = bbccc

then xy or aab <= p and y > 0. Then if I pump up y by 2 for example, I would get the string aabbbbccc. But this is not in the language as there are more b's then c's. The problem i'm having is if I instead split my string as such:

x = a

y = a

z = bbbccc

then xy or aa <= p and y > 0. If I pump this string by 2 for example, I would get the string aaabbbccc, which is in the language. So in this case the pumping lemma is passed.

So my question is, for the pumping lemma does my second example passing mean that the language a^nb^mc^m passes the pumping lemma, or does the fact that I found a case where splitting x and y with this pumping length makes it false, mean that the language does not pass the pumping lemma. And if that is the case then if I had the language:

a^nb^m  where n >=0 and m >=0 and I choose m to be p, and made the pumping length 3 for example, I could end up with the string:

aabbb, where x = a, y = ab, z = bb, which when pumped would produce aababbb which is not in the language, but I know that a^nb^m is a regular language.

Hopefully you can see where my confusion lies. I been researching for a while and I just can't find a clear cut answer on this. Any help would be extremely appreciated.

Thank you.

Apply the pumping lemma on the word $b^nc^n$.


Fitting a feedback loop to data points If you want to fit a polynomial to a set of data points, there are many options available including least squares fitting, gradient descent, and lagrange interpolation.

However, thinking in more programmer / computer science terms, let's say that I had something more like a pseudo random number generator where it had some internal state, and when you ran a function, it would do an operation, update the internal state and spit out a new value.
 (Note, I'm not trying to make a prng, just using it as an example of the type of function I'd like to fit to my data)

Are there any methods other than brute force for creating (or iteratively training, ala gradient descent) a system like that to give something close to a specific sequence of desired output values?

For example, a simple feedback function may look something like this in C++:

float SequenceGenerator()
{
    // internal storage
    static float internalState = 16.371f;

    // adjust the internal storage
    internalState += internalState * 83.12f;

    // keep the internal storage <= 100
    while(internalState > 100.0f)
        internalState -= 100.0f;

    // return the next value in the sequence
    return internalState;
}

I definitely see how i could choose some random value for the initial values for the starting state, and the multiplication amount.  I can also see how I could compare the values that come out to my sequence and come up with something like a mean squared error.

I'm not sure however, how I might be able to do something like calculate a gradient to adjust those values to iteratively minimize the mean squared error.

Is there a way to do something like this?

(I can't seem to find appropriate tags other than PRNG, please let me know if there are better tags or feel free to edit)

This is probably an awful approach to fitting points and prediction.

There's no reason to expect that a PRNG will do a good job at fitting points.  Interpolation is effective because we think that not all curves are equally likely.  Some kind of Occam's razor applies: all else being equal, the "simpler" the curve, the more likely that it is as a plausible model.

Thus, linear regression is useful precisely because not all curve shapes are possible; only straight lines.  Empirically, straight lines occur more often than crazy-wiggly shapes.  Similarly, polynomial regression is useful because a low-order polynomial is more likely than a high-order polynomial.

Now consider the following approach: try to fit the data you already have to an arbitrary function (with no restrictions on the function or the shape of the curve; all functions are valid/legal models).  Well, that'll be an absolutely terrible approach at prediction.  You'll be able to find a function that exactly fits all of the data you already have, but (most likely) it will be absolutely useless at predicting values you haven't seen -- it'll be absolutely useless at generalization / prediction.  Essentially, you'll have massively overfitted the data set.

Now a PRNG is designed to behave like a true-random generator.  In other words, all sequences of outputs are supposed to be equally likely (or, at least, you can't tell the difference).  Fitting your data to a true-random generator will be useless at prediction/generalization.  For the same reason, fitting your data to a PRNG is likely to be useless at prediction/generalization.

You should probably read about the "no free lunch" theorems for machine learning and prediction: https://en.wikipedia.org/wiki/No_free_lunch_theorem, http://www.aihorizon.com/essays/generalai/no_free_lunch_machine_learning.htm, http://no-free-lunch.org/.  To be effective at prediction, the learning technique must embed some bias about what hypotheses/models are more likely.  A true-random generator has no bias and thus is useless.  A PRNG behaves like a true-random generator and thus will probably be useless (or, to the extent it has bias, its bias is towards distributions that are very unlikely to appear in nature).


Does this program have a runtime of O(N) or O(n*m) This question is similar to, but distinct from this one, in that I am considering a specific case that demonstrates an apparent inconsistency in how I see Big-O notation used. I would like to be sure I am properly evaluating the run time of this algorithm.

Imagine we have a list of strings, such as this:

words = ["eat", "tea", "tan", "nat", "bat", "cat", "act"]

We want to visit each character of each word in this list (The above example comes from an anagram grouping prompt). What would the runtime of visiting each character be? Assume that neither the number of words or the length of the words are constants. They are both variables.

in python, that could be done as so

for w in words:
    for c in w:
        print(c)

I have seen the run time of visiting every element in this list as being:

O(n*m): where n is the number of words in the list and m is the number of characters

O(N): where N is the total number of characters in the list

O(N) is clearly linear, but O(n*m) is not (according to the answers in the aforementioned question)

How can the same algorithm be both linear and not linear, simply depending on how you describe the inputs.

In the example case I am considering, all words have the same number of characters, but how might our answer change if this was not the case? Does m then represent the average character length? the length of the longest word?

Big $O$ is merely a function that describes an upper bound of another function, so it can be used in different ways.  You can describe the big $O$ of the memory usage of a function, or the big $O$ of the number of operations a function performs.

What you've encountered is simply that, by using different descriptors of the inputs, you wind up with different descriptors of the function itself.  The function you have described is, in fact, linear to the total number of characters in the input.  That statement is not wrong, but $O(nm)$, where $m$ is the average number of characters of the words in a set, is clearly a more useful description of the behavior of the function.


How to show all false outputs in a circuit? I have 3 input variables and the output for all 8 possible combinations is 0 (false). When making a circuit, how would I show this using gates or no gates at all? Thanks!

First you can write down the truth table of your circuit, in this case it will be entirely composed of $0$s.
Then you will build up a Boolean expression in the form you prefer (if you have no limitations) which reproduces the behavior (relation input/output) observed in the truth table.

Note that every operator of your boolean expression correspond to a logic gate:

$\land$ = AND

$\lor$ = OR

$\neg$ = NOT

$\oplus$ = XOR


Can you always prove the asymptotic bound of a recurrence of the form aT(n/b) + f(n) using the substitution method? To make my question more concrete, here is an example I am stuck on.

I want to prove that $T(n) = 8T(\frac{n}{2}) + n^3$ is asymptotic bound by $n^3\log(n)$ using the substution method. That is $T(n)$ is $\Theta(n^3\log(n))$, so both $O(n^3\log(n))$ and $\Omega(n^3 \log(n))$.

We know $T(n) = \Theta(n^3 \log(n)) \Leftrightarrow \exists c_1, c_2, n_0 > 0: \forall n > n_0 . c_1 n^3 \log(n) \leq T(n) \leq c_2 n^3 \log(n)$.

Given that I assume the proof should go somewhat as follows:

To show: $\exists c_1, c_2, n_0 > 0: \forall n > n_0 . c_1 n^3 \log(n) \leq T(n) \leq c_2 n^3 \log(n)$

To do this we can use strong induction.

Let $P(n)$ be $c_1 n^3 \log(n) \leq T(n) \leq c_2 n^3 \log(n)$.

Take $n$ to be an arbitrary natural number.

Induction hypothesis: $P(1),P(2),...,P(n-1)$. And notably, $P(\frac{n}{2})$.

It seems fairly straight forward to show the right-hand side of $P(n)$, that is that $\forall n > n_0 . T(n) \leq c_2 n^3 \log(n)$.

It follows that (taking $\log$ to be in base $2$):

$$
\begin{align*}
  P(\frac{n}{2}) &\Leftrightarrow T(\frac{n}{2}) \leq c_2 (\frac{n}{2})^3\log(\frac{n}{2}) \\
  &\Leftrightarrow 8T(\frac{n}{2}) + n^3 \leq 8c_2 (\frac{n}{2})^3 \log(\frac{n}{2}) + n^3 \\
  & \Leftrightarrow T(n) \leq 8c_2\frac{n^3}{8}(\log(n) - log(2)) + n^3 \\
  & \Leftrightarrow T(n) \leq c_2n^3\log(n) + n^3 - c_2n^3log(2) \\
  & \Leftrightarrow T(n) \leq c_2n^3\log(n) + n^3 - c_2n^3 \leq c_2n^3\log(n) \ \text{ (if $c_2 \geq 1$)}
\end{align*}
$$

So we have $P(n)$.

And as such $\exists c_2, n_0 > 0: \forall n > n_0 . T(n) \leq c_2 n^3 \log(n)$.

My problem:

So we have shown that $T(n) = O(n^3 \log (n))$ but not yet that $T(n) = \Omega(n^3 \log (n))$ which is also required to have $T(n) = \Theta(n^3 \log(n))$.

And that is what I am not sure how to go about showing — the left-hand side of $P(n)$, that is that given $P(\frac{n}{2})$, we have $c_2 n^3 \log(n) \leq T(n)$.

Can someone provide some insight into how to approach this?

You can prove precise equality for your recurrence. I'm going to assume the base case:

$$T(n) = \begin{cases}
  8 & n = 2\\
  8T\left(\tfrac{n}{2}\right) + n^3 & n > 2\\
\end{cases}$$

Claim: $T(n) = n^3 \log_2 n$

Base Case ($n = 2$): $T(2) = 8 = 2^3 \log_2 2 = 8$

Inductive Case ($n > 2$):

$$\begin{align*}
T(n) & = 8T\left(\tfrac{n}{2}\right) + n^3\\
     & = 8\left(\tfrac{n^3}{8} \log_2 \tfrac{n}{2}\right) + n^3\\
     & = n^3 \log_2 \tfrac{n}{2} + n^3\\
     & = n^3 \log_2 n - n^3 \log_2 2 + n^3\\
     & = n^3 \log_2 n - n^3 + n^3\\
     & = n^3 \log_2 n & \square
\end{align*}$$

Thus $T(n) = n^3 \log_2 n \implies T(n) = O(n^3 \log n)$. No need to mess with lower or upper bounds.

However, in general this equality might not be the correct solution. Sometimes you will need to add lower order terms to get the equality or inequality to hold. A general approach to determine the lower order terms is as follows:

If we have:

$$T(n) = \begin{cases}
f(b) & n = b\\
aT(n/b) + f(n) & n > b
\end{cases}$$

We first assume $n = b^k$ for some $k$. Next we can turn this into a summation:

$$\begin{align*}
T(n) & = aT(n/b) + f(n)\\
     & = a(aT(n/b^2) + f(n/b)) + f(n)\\
     & = a^2T(n/b^2) + af(n/b) + f(n)\\
     & \vdots\\
     & = \sum_{i = 0}^{\log_b n - 1} a^{i} f\left( \frac{n}{b^i}\right)
\end{align*}$$

Then if you can find a closed form for this sum, we can easily prove equality by induction (e.g. substitution method) with proper constants. Here is your example again:

$$\begin{align*}
T(n) & = 8T\left(\tfrac{n}{2}\right) + n^3\\
     & = \sum_{i = 0}^{\log_2 n - 1} 8^{i} \left( \frac{n}{2^i}\right)^3\\
     & = \sum_{i = 0}^{\log_2 n - 1} 8^{i} \frac{n^3}{2^{3i}}\\
     & = \sum_{i = 0}^{\log_2 n - 1} n^3\\
     & = n^3 \log_2 n\\
\end{align*}$$

Now you can go ahead and use this in your substitution method and you should not have any issues.

Feel free to try the same method with a trickier example:

$$T(n) = \begin{cases}
  12 & n = 3\\
  5T\left(\tfrac{n}{3}\right) + n^2 + n & n > 3\\
\end{cases}$$


Largest reported speedup for a parallel computation? A parallel implementation of a computation is usually compared to a sequential version of the same computation.  The ratio of the time taken by the sequential version to the time taken by the parallel version is called the speedup.  So if 8 cores run their smaller parts of the computation in 2 time units, and one core runs the whole computation in 8 time units, then the speedup is 4.

  What is the largest speedup reported for a real computation?

It is possible to reach essentially infinite speedup in a search problem, since one of the parallel pieces of the search space may lead to a fast solution by that parallel instance, while the sequential solution has to work through the entire search space to get to that point.  More generally, I want to exclude any problem where one of the parallel processes can reach a shortcut.  So I am only interested in computations where the amount of work done by the parallel processes is the same as done by the sequential process.  This is common in solving PDEs by grid methods, or in discrete event simulation.
So with $n$ processors, one should never get more than $n$ speedup for these kinds of problems.

I would also like to exclude embarrassingly parallel problems like parallel rendering, since there one really has a vast number of independent tiny problems.  I am interested in problems where it is not possible to partition the computation into strictly disjoint pieces.

For a large speedup, one has to have many processors.  Given the restrictions on scope that I have conveniently labelled as "real computations", this question is then essentially about how efficiently the very large processor arrays that exist have been programmed.

I am aware of reported speedups of ~500 using arrays of GPUs, but surely larger speedups exist.

Edit: To address some of the comments, I dug up some further motivation, which will hopefully be precise enough for the tastes of those more mathematically inclined.  This is quite different in style from the above, so I append it here as a postscript.

For $n$ iid random variables $X_1, X_2,\dots, X_n$ with mean $\mu$,
denote their maximum by $X_{(n)}$ and their sum by $S_n$.
O'Brien has shown that $X_{(n)}/S_n \to 0$ almost surely as $n \to \infty$ iff $\mu < \infty$.

Letting $X_i$ be the time taken by the $i$-th processor to complete its task, and assuming that there is a timeout/recompute mechanism to ensure that $\mu$ is finite, this hints that the inverse of the speedup should be essentially unbounded.  (This is not necessarily the case: the techniques used may not carry over to the inverse, so I have to leave this a bit vague.)

This is a nice theoretical prediction, and the question arises: is this prediction borne out in practice?  Or do implicit dependencies or diverging behaviours of the different processors (i.e. a breakdown in the iid assumption) tend to curtail this supposedly unbounded increase?

The iid case corresponds to the embarrassingly parallel case.  Where the processors have to synchronize, independence breaks down.

My question can therefore also be rephrased as: how badly does non-negligible dependence between parts of a computation as seen in practice affect the large-scale speedups that have been demonstrated?  Given that the bounds for expectation of the maximum in the non-independent case are quite weak, some pointers to empirical data would be useful.

G. L. O'Brien, A Limit Theorem for Sample Maxima and Heavy Branches in Galton-Watson Trees, Journal of Applied Probability 17 539–545, 1980.

John Gustafson observed and reported speedups in excess of 1024 on early 80's supercomputers; this led him to the concept of scaled speedup (Gustafson-Barsis law), in contrast to the pessimistic Amdahl-Ware law.

Right now, in the era of multicore parallel supercomputers equipped with hundreds of thousands or millions of cores, performances are more commonly reported in terms of petaflops and efficiency. For instance, the winners of the last Gordon Bell prize at the Supercomputing 2012 conference, established the current world record for an astrophysical N-body simulation of one trillion particles performed on the full K computer, which appears to be number 4 in the June 2013 top 500 list. They reported 4.45 petaflops on 663,552 cores (the K computer was equipped with 82944 8-core processors in November 2012), and an efficiency (the ratio speedup/cores) of 42%. Translated in terms of speedup, that means a speedup of about 278,691.


There are n numbers. Find the maximal set of pairwise NON coprime numbers I have to take input in an array(no. of elements in array <=10^5).
For ex:- Let the array be {2,3,4,16,9,45,81,27}
Now I need to find the order of the maximal set such that any pair of elements in the set have gcd > 1.
In the example:- {3,9,45,27,81} is such a set.It's order is=5, hence 5 is my ans.
Note that {2,4,16} also has pairwise gcd's >1 but it is not maximal (5>3).

What I did:-
I tried to find every possible set which meets the condition and then see the maximum order but that doesn't seem to work(works in some cases, but fails in majority).

The input numbers are <=10^7 so this needs to be fast.

Your problem is NP-complete, I will show a reduction from maximum independent set to your problem. Let $G = (V, E)$ be an undirected graph, and let $G'$ be the complement graph of $G$. Label each edge $uv$ of $G'$ with a prime number $p_{uv}$ such that for each pair of edges $uv, wx \in E$ it holds that $p_{uv} \neq p_{wx}$
Now, label each $v \in V$ with $$ \prod_{u \in Adj(v)} p_{uv}\,.$$

Now, take the set of the labels. A subset of it is the maximum set of non-parwise coprime numbers if and only if it is a maximum clique in $G'$, if and only if it is the maximum independent set of $G$.


Multiple FPT Parameters The class $FPT$ (fixed-parameter tractable) is defined here. However, there is only one "parameter" that is studied from the given problem/language.

Is there an equivalently defined class that can take $O(1)$ parameters? It may be useful for defining this for problems that are not driven by a single parameter. Unfortunately, there does not seem to be any material on extra parameters, including in the book Parameterized Complexity Theory.

Yes, it's exactly the same class. You can take any constant size list of parameters and combine them just using addition. This is particularly obvious in Flum and Grohe's formulation of $FPT$ where problems are equipped with a parameterization $\kappa : x \rightarrow \mathbb{N}$.

So for example, you can take a problem with two parameters $k$ and $r$, and produce a combined parameter $k+r$ (or indeed using any moderately sane function), as if the running time is bounded by some function $f(k,r)$ (we can ignore the $|x|^{O*(1)}$ part for the moment)), then it is bounded by the function $f(g(k+r),h(k+r)) = f'(k+r)$, where $g$ and $h$ do whatever is necessary to turn $k+r$ into a sufficiently usable form (in most cases, this is nothing).

Note that this produces the intuition you expect. If $(\Pi,\kappa) \in FPT$, then it is still in $FPT$ when you add a new parameter, however it is not necessarily true that if $(\Pi,\kappa_{1} + \kappa_{2}) \in FPT$ then either $(\Pi,\kappa_{1}) \in FPT$ or $(\Pi,\kappa_{2}) \in FPT$.

As an example, deleting $k$ vertices to obtain an $r$-regular graph is $W[1]$-hard with parameter $k$, $paraNP$-complete with parameter $r$ but in $FPT$ with parameter $k+r$.


What is the correct representation of Master Theorem? What I'm taught in my class -

  $T(n)=aT(\frac{n}{b})+\theta(n^k\log^pn)$
  where $a\geq1$, $b>1$, $k\geq1$ and $p$ is a real number.

  if $a>b^k$ then, $T(n)=\theta(n^{\log_ab})$
  if $a=b^k$ then,

  if $p>-1$, then $T(n)=\theta(n^{\log_ab}\log^{p+1}n)$
  if $p = -1$, then $T(n)=\theta(n^{\log_ab}\log\log n)$
  if $p<-1$, then $T(n)=\theta(n^{\log_ab})$

  if $a<b^k$, then

  if $p\geq 0$, then $T(n)=\theta(n^k\log^pn)$
  if $p<0$, then $T(n)=O(n^k)$

On certain websites, the above representation for Master Theorem is slightly different as follows -

  $T(n)=aT(\frac{n}{b})+\theta(n^k(\log n)^p)$

This ambiguity creates a great confusion while solving problems such as :

  What is the value of the recurrence : $T(n)=T(\sqrt{n})+\theta(\log\log n)$

Substituting $n=2^m$, we get a new expression :

  $S(m)=S(\frac{m}{2})+\theta(\log m)$
  Here  $a=1$, $b=2$, $k=0$ and $p=1$

If I apply Master Theorem as per the way I am taught in class, the result I get is :

  $T(n)=\theta(\log\log\log n)$

and if I solve using the other formula, I get the result as :

  $T(n)=\theta((\log\log n)^2)$

Which is the correct one? This confusion is making me question every problem that I've solved.

By convention, the notation $log^p(x)$ is defined to be $(log(x))^p$, not $p$ iterations of the $log$ function. This is similar to the trigonometric functions, which gives us identities like $sin^2(x)+cos^2(x)=1$.


Give an NL-algorithm for complement of 2-SAT Question1: What is the difference between 2SAT and the complement of 2SAT?

Question2: It is known that NL is contained in P, but what we know about P over NL? can be said that an algorithm that runs in P, uses NL space?

Information That I gather

I follow the Papadimitriou algorithm to solve 2-SAT with
Let give 2-SAT a graph of connected nodes according to the specifications contained literal and clauses where the information of the nodes and connections is a container in a CNF of 2 literals per clause, because of the problem need to be contained in NL we assume that we are only working to solve this in 1 writing tape and 1 only input tape to run the algorithm

    for i=0 repeat log2(n times)
      Choose Random initial assignment for every literal
         Repeat 2n^2
           -If
             The assignment satisfies all the paths in the sequence
             of clauses, Halt and report
           -else
             Pick arbitrary unsatisfied clauses and flip the value of its literals
     Report unsatisfiable

According to 2-SAT reachability one condition for the possibility of no reach, if one path of the graph where there are connected nodes with the same literal and one of them is a negation, then the graph doesn't have a satisfiable result, and that would be the case in the algorithm. This is the same case for a complement of 2SAT.

In the non-deterministic solution, the algorithm could give only a correct answer or a false negative depending on the condition of the arrangement of the clauses, but never retrieve a false positive because of the condition establish in the conditional operator.

With the else clause the algorithms cover different possible clauses fliping the literal where the condition was unsatisfied and trying new options.

The algorithm uses only memory to keep the counter running because the counter corresponds to the size of the input in Log2(n)*2n^2 space on the writing tape.

Also is prove that 2SAT correspond to NL and NL-complete and we know that NL=coNL

Question1: What is the difference between 2SAT and the complement of 2SAT?

The set of all strings that do not describe satisfiable 2CNF formulas.

  Question2: It is known that NL is contained in P, but what we know about P over NL? can be said that an algorithm that runs in P, uses NL space?

We don't know anything significant beyond that $\mathrm{NL}\subseteq\mathrm{P}$.

It doesn't really make sense to ask if "an algorithm... uses NL space". You can ask if an algorithm uses logarithmic space and if it's nondeterministic, but there's no such thing as "nondeterministic space" per se. By that, I mean that the storage space itself isn't nondeterministic: nondeterminism is a property of the algorithm that uses the space.

It's certainly not true that an algorithm that runs in polynomial time necessarily uses logarithmic space: it could use polynomial space. It's possible that every deterministic algorithm that runs in polynomial time could be rewritten as a nondeterministic algorithm that uses only logarithmic space but we don't know if that's true or not. If it were true, we would have $\mathrm{P}=\mathrm{NL}$.

Note that, formally speaking, $\mathrm{NL}$ and $\mathrm{P}$ are classes of problems, not algorithms.


Serializable schedules but not view serializable I know that to check if a given schedule is serializable we can test for either view serializability or conflict serializability. But do serializable schedules exist which are not view serializable?

No.
There doesn't exist any serializable schedule which is not view serializable.


Understanding this answer: A CFG defines a language as a the smallest solution to a system of language equations Statement comes from this answer. A blanket statement that this is a well-known fact is made in this other question.

I have never heard of a language equation. But I am just a student. Given the syntax, is this equating the derivations of a CFG grammar to equations?

In other words, is this bit from the answer $A=ABa$ meant to be considered equivalent to a BNF derivation $A \rightarrow ABa$? (where $A$ and $B$ mean the same as in the original answer -- variables that decompose to terminals containing $a$)

Or is there some other meaning being expressed here? From the second question that I found after I typed this question it seems to mean something different. Can someone "ELIStudent"?

A good way to think about these equations is to imagine them as sets over valid words. Say I have an alphabet $\Sigma = \{a, b\}$, then the rule
$$
A \leftarrow A a \mid b
$$

says that there's some set $A$ that is isomorphic to the set $(A * \{a\}) \cup \{b\}$. Here the $*$ operation is the product/concatenation operation lifted over sets, that is
$$
\{a, b, c\} * \{d, e, f\} = \{ad, ae, af, bd, be, bf, cd, ce, cf\}
$$

Going back to our grammar rule, it is basically declaring the existence of a set $A$ of words that satisfies the equation
$$
A = (A * \{a\}) \cup \{b\}.
$$

Now, there's a huge class of sets of words that satisfies this equation. For example, the set $A_\bot = \{b, ba, baa, baaa, baaaa, \dots\}$ is a valid solution since a $b$ or appending any element of $A_\bot$ with another $a$ will result in a word that is already in $A_\bot$. However, you should check that
$$
A_{bb} = \{b, bb, ba, bba, baa, bbaa, baaa, bbaaa, \dots\}
$$
is also a valid solution to this equation. In particular, $b$ is already in $A_{bb}$, and for any element $ba^k$ or $bba^k$ in $A_{bb}$, its concatenation with $a$ results in $ba^{k+1}$ and $bba^{k+1}$, which are also already in $A_{bb}$. Therefore, $A_{bb}$ is also a valid fixed point.

In fact, for any given ground set of words $S = \{w_1, w_2, w_3, \dots\}$, we can construct a closure $A_S$ which contains every word in $S$ and similarly satisfies the above equation. In particular, the closure operator is the same isomorphism:

\begin{align*}
A_S^{k + 1} &= (A_S^k * \{a\}) \cup \{b\} \\
A_S &= \bigcup_k^\infty A_S^k
\end{align*}

So now we get to the real question. If there are an infinite supply of solutions for this equation, then what good is it as a characterization of some grammar? Well, intuitively, we hope to just characterize those words that are generated from this rule "from scratch". In effect, we wish to treat these rules as free objects. That is, we care about the case where the underlying generator $S = \{\}$. Let
$$
A(S) = (S * \{a\}) \cup \{b\}
$$
then we want
$$
A_* = \bigcup_k A^{(k)}(\{\})
$$
to be the set generated by our grammar rule, where $A^{(k)} = A(A(\stackrel{k}{\dots} A(\cdot)))$.

This then gives some intuition of what we mean by the "least solution." $A(S)$ is monotone in the sense that $S \subseteq S' \implies A(S) \subseteq A(S')$; in fact, this holds over all grammar rules. Since the least element over the class of possible sets that $S$ can take (ordered on set inclusion) is the empty set, then effectively the "freely generated" language that we desire also turns out to be the smallest (ordered on set inclusion) fixed point, that is, $A(\{\}) \subseteq A(S')$ for any set $S'$.

In general, you'll see a lot of these "smallest solution" clauses all around the landscape of computer science. For example, any recursive program is the smallest solution to some program equation; any constructable inductive datatype is the smallest solution to some inductive datatype equation; any valid program semantic is the smallest solution to some logical equation; etc. It turns out that these classes of topological closures corresponds elegantly to a notion of finiteness. For example, the set of all finitary words $\Sigma^*$ is itself a least fixed-point. Since computations themselves can be seen as some enumeration process of finite objects, the analogy holds quite naturally; least fixed-points typically gives some assurance of some form of computability.

In conclusion, if you see the phrase "least solution" or "the least fix-point," it often means that the problem concerns finite objects that are freely-generated in the sense that only things that can be derived "from scratch" are considered.


How to model and solve this problem? I have a matrix $P \in M_n(\mathbb N)$, where

$$ P =
\begin{bmatrix}
0 &  P_{12}  & \ldots & P_{1n}\\
P_{21}  &  0 & \ldots & P_{2n}\\
\vdots & \vdots & \ddots & \vdots\\
P_{n1}  &   P_{n2}    & \ldots & 0
\end{bmatrix}$$

with $P_{ii} = 0$ for all $i \in \{1,2,\dots,n\}$. I need to find matrices $A, B \in M_n(\mathbb N)$ that satisfy $A + B = P$ and that satisfy the following constraints

$$\forall i\in [\![ 1,n]\!] \sum_{k=1}^{n} A_{ik} = \sum_{k=1}^{n} A_{ki}$$

such that $\sum_{i=1}^{n} \sum_{k=1}^{n} A_{ik}$ is maximized.

I need to implement an algorithm to solve this problem. On my input data I have approximately: $ n = 16 $  and  $ \sum_{i=1}^{n}\sum_{k=1}^{n} P_{ik} = 60000 $  so the brute-force approach is out of question.
I don't know what could be a good approximation algorithm so my current approach is to reduce the problem to a binary integer programming problem and then apply Branch-and-Cut but I have serious doubt on it effectiveness for this specific problem.

Finding the optimal solution in polynomial time would be perfect (not sure if it's possible), but I can satisfy myself with a good approximation algorithm. Not having a strong background in CS I'm a bit confused, help would be greatly appreciated !

Choose a modelling language, like JuMP, and solve it as a MILP.

An attempt I made with CPLEX solves a random instance ( $n=16$, $max(P)=60000$ ) to optimality almost instantly.

I've implemented the following

$$ max(z)$$
$$ z = \sum_{i=1}^n\sum_{k=1}^n A(i,k) $$

$$   \sum_{k=1}^n A(i,k) =\sum_{k=1}^n A(k,i)\quad \forall i \in [1,n]$$
$$ A(i,k) + B(i,k) = P(i,k)\quad \forall (i,k) \in [1,n] \times [1,n]$$

$$A\in[0,max(P)-1]^{n\times n}\subset\mathbb{Z}^{n\times n}$$
$$B\in[0,max(P)-1]^{n\times n}\subset\mathbb{Z}^{n\times n}$$


Is there a name for complement of recursively enumerable set? If there is a recursive function
$$
f(x) =
\begin{cases}
1 & \text{if $x \notin A$}\\
\text{undefined} & \text{if $x \in A$}\\
\end{cases}
$$

Is there a special name for the class of sets like $A$?

The complement of a recursively enumerable (RE) language is called co-recursively enumerable (co-RE).

As RE and co-RE form the first level of the arithmetic hierarchy, they are also known by aliases $\Sigma_1^0$ and $\Pi_1^0$.


How does Lamport imply anomalous behavior is impossible given these constraints? Lamport's paper: Time, Clocks, and the ordering of Events in a Distributed System
Anomalous behavior occurs because Lamport's logical clocks are not enough to guarantee that the total ordering of events derived from the unique partial ordering and a non-unique total ordering is not enough to guarantee that the ordering is correct with respect to physical time.
He gives two conditions PC1 and PC2:
PC1: There exists a constant $ \kappa $ << 1 such that for all i:
$ |\frac{dC_{i}}{dt} - 1| < \kappa $
PC2: For all i, j:
$ |C_{i}(t) - C_{j}(t)| < \epsilon $
PC1 says that individual clock drift in the system must be less than some constant $ \kappa $. PC2 says that clocks must be synchronized so that the difference in time between any 2 clocks does not exceed $ \epsilon $.
This is what I do not understand. He says that anomalous behavior is impossible if this proposition holds, deduced from PC2.
proposition:
PC2 implies $|C_{i}(t + \mu) - C_{j}(t)| > 0$ if $\frac{\epsilon}{1 - \kappa} \leq \mu$.
I have no idea where he comes up with this, maybe my math isn't too great.
Note: $\mu$ is a constant that must be less than the shortest transmission time for interprocess messages.
PC1 implies $|C_{i}(t + \mu) - C_{i}(t)| > (1 - \kappa)\mu$. This is apparent because (1 - $\kappa$) is less than 1. But apparently he combines this with PC2 to deduce the proposition.
How does he arrive at this??

The constraint as written by Lamport is $C_i(t+\mu)-C_j(t)\gt0$ or $C_i(t+\mu)\gt C_j(t)$ which can be re-written  $$C_i(t+\mu) - C_i(t)\gt C_j(t) - C_i(t) \tag{*}\label{*}$$
Given Lamport's previous deductions, we recognise the boundary conditions each side must satisfy namely:
$$(1-\kappa)\mu \lt C_i(t+\mu) - C_i(t)$$
$$ \epsilon \gt C_j(t) - C_i(t)$$
Now, Lamport wants to find out the range of values for 'variables' $\epsilon,\kappa$ ($\mu$ is fixed) that will ensure the strict inequality $\eqref{*}$.
Obviously, for real numbers (Lamport's starting assumption) if $x \lt A$ and $y \gt B$, then as long as $y \leq x$ we know $A\gt B$.
In other words, as long as $\epsilon \leq (1-\kappa)\mu$ then $\eqref{*}$ is true and so $$C_i(t+\mu)-C_j(t)\gt0$$


Infeasible linear programming reduce errors to find solution Most normal linear programming problems look like this:

We choose some point in the double shaded area that solves our optimizer and we're good to go.
However, I've come across a problem where it's fairly common to get a lp problem like this (infeasible):

I'd like to employ some metric such that the solution given reduces the errors between the closest possible solutions in any equation it does not fulfill such that it would be on the line right between the 2 solutions (something like reduce OLS or LAD).
Is there any formal algorithm for this or common way this is done?

One approach: replace each inequality $a_1 x_1 + \dots + a_n x_n \le b$ by $a_1 x_1 + \dots + a_n x_n \le b + t$, replace each inequality $a_1 x_1 + \dots + a_n x_n \ge b$ by $a_1 x_1 + \dots + a_n x_n \ge b - t$ (using the same $t$ for all of them), and then minimize $t$.


Difference between a skiplist and an Indexable skiplist Can someone please help me understand the main differences between a simple skiplist and an indexable skiplist? How does an indexable skiplist work in comparison to a normal skiplist (maybe a little example?), I can only find so little about it online.
Thanks.

An Indexable Skiplist is a skiplist with the added property that it can quickly lookup the $m$th entry (in order) in a skiplist in $O(\log n)$ time in a skiplist of $n$ entries.  In other words, it takes a skiplist that is not an indexable skiplist $O(n)$ time, on average, to find the $m$th element in order in a skiplist, while an ordered skiplist can do this in logarithmic time.

It does this by keeping track of the width of the links in the skiplist.


Is it decidable if a language described by number of occurences is regular? It is known that the language of words containing equal number of 0 and 1 is not regular, while the language of words containing equal number of 001 and 100 is regular (see here).

Given two words $w_1,w_2$, is it decidable if the language of words containing equal number of $w_1$ and $w_2$ is regular?

Given two words $w_1$,$w_2$, is it decidable if the language $L$ of words containing equal number of $w_1$ and $w_2$ is regular?

First some definitions:
They could be made more concise, and the notations could be improved if they are to be used in proofs. This is only a first draft.

Given two words $w_1$ and $w_2$,
we say that:

$w_1$ always occurs with $w_2$, noted $w_1\triangleleft w_2$, iff

for any string $s$ such that
$s=xw_2y$ with $\mid x\mid,\, \mid y\mid\ \geq \mid w_1\mid +\mid
w_2\mid$ and $|x|_0,|x|_1|,|y|_0,|y|_1| \geq 1$ there is another decomposition $s=x'w_1y'$.
Note: The condition that $x$ and $y$ each contain at least a 0 and a 1 is required by a pathological case (found by @sdcvvc): $w_1=1^i0$, $w_2=v1^{i+j}$ and $y\in1^*$, and its symetrical variants.
there is a string $s=xw_2y$ with $\mid x\mid,\, \mid y\mid\ \geq \mid w_1\mid +\mid w_2\mid$ such that there is at most one decomposition $s=x'w_1y'$

$w_1$ always cooccurs with $w_2$, noted $w_1\triangleleft \triangleright\,w_2$, iff each always occur with the other,
$w_1$ and $w_2$ occur independently, noted $w_1\triangleright \triangleleft\,w_2$, iff neither one always occur with
the other,
$w_1$ always occurs $m$ times or more than $w_2$, noted $w_1\triangleleft_m w_2$, iff for any string $s$ such that
$s=xw_2y$ with $\mid x\mid,\ \mid y\mid|\ \geq \mid w_1\mid +\mid
w_2\mid$ there are $m$ other decompositions $s=x_iw_1y_i$ for
$i\in[1,m]$ such that $i\neq j$ implies $x_i\neq x_j$.

These definitions are constructed so that we can ignore what happens at
the ends of the string where $w_1$ and $w_2$ are supposed to occur.
Boundary effects at the end of the string have to be analyzed
separately, but they represent a finite number of cases (actually I think I forgot one or two such boundary sub-cases in my first analysis below, but it does not really matter).
The definitions are compatible with overlap of occurrences.

There are 4 main cases to consider (ignoring the symetry between $w_1$ and $w_2$):

$w_1\triangleleft
\triangleright\,w_2$
Both words come necessarily together, except possibly at the ends of the string. This concerns only pairs of the form $1^i0$ and $01^i$, or $0^i1$ and $10^i$. This is easily recognized by a finite automaton that only checks for lone occurences at both ends of the string to be recognized, to make sure there is a lone occurrence at both ends or at neither end. There is also the degenerate case when $w_1=w_2$: then the language L is obviously regular.
$w_1\triangleleft w_2$, but not $w_2\triangleleft w_1$
One of the 2 words cannot occur without the other, but the converse is not true (except possibly at the ends of the string). This happens when:

$w_1$ is a substring of $w_2$:then a finite automaton can just check that $w_1$ does not occur outside an instance of $w_2$.
$w_1=1^i0$ and $w_2=v1^j$ for some word $v\in\{0,1\}^*$, $v\neq01^i$: then a finite automaton check as in the previous case that $w_1$ does not occur separated from $w_2$. However, the automaton allows counting one extra instance of  $w_1$ that will allow acceptance if $w_2$ is a suffix of the string. There are three other symetrical cases (1-0 symmetry and left-right symetry).

$w_1\triangleleft_2 w_2$
One of the 2 words occurs twice in the other. That can be recognized by an a finite automation that checks that the smaller word never occurs in the string. The is also a slightly more complex variant that combines the two variations of case 2. In this case the automaton checks that the smaller string $1^i0$ never occurs, except possibly as part of $v$ in the larger one $v1^j$ coming as a suffix of the string (and 3 other cases by symetry).
$w_1\triangleright \triangleleft\,w_2$
The 2 words can occur independently of each other. We build
a generalized-sequential-machine (gsm) $G$ that output $a$ when it recognizes an occurrence of $w_1$ and
$b$ when recognizing an occurrence of $w_2$, and forgets everything
else. The language $L$ is regular only if the language $G(L)$ is
regular. But $G(L)=\{w\in\{a,b\}^*\mid\ \mid w\mid_a=\mid w\mid_b\}$ which is clearly context-free and not regular. Hence $L$ is not regular.
Actually we have $L=G^{-1}(G(L))$. Since regular languages and context-free languages are closed under gsm mapping and inverse gsm mapping, we know also that $L$ is context free.

One way to organize a formal proof could be the following. First build
a PDA that recognizes the language. Actually it can be done with a
1-counter machine, but it is easier to have two stack symbols to avoid duplicating the finite control. Then, for the cases where it should be a FA, show
that the counter can be bounded by a constant that depends only on the
two words. For the other cases show that the counter can reach any
arbitrary value. Of course, the PDA should be organized so that the
proofs are easy enough to carry.

Representing the FA as a 2-stack-symbols PDA is probably the simplest representation for it. In the non-regular case, the finite control part of the PDA is the same as that of the GSM in the proof sketch above. Instead of outputting $a$'s and $b$'s like the GSM, the PDA counts the difference in number with the stack.


Calculate the number of trailing zeros in equation f(n) = f(n-1) * f(n-2) where f(0) and f(1) are any given arbitary numbers This question is doable if you can calculate the number by multiplying f(n-1) and f(n-2).

Is it possible to do this question if we entirely want to skip multiplying these 2 numbers and still be able to calculate say the number of trailing zeros in f(20).

Why do I want to skip multiplying these two numbers?
Because as this function grows exponentially, so does the value. We might get an integer overflow on some languages. Hence.
Also, our aim is to calculate the number of trailing zeros and not calculate the number itself.

What I tried. To try and calculate trailing zeros and f(n-1) and f(n-2), So that I deduce the number of trailing zeros in f(n) and go on from there.

But to calculate trailing zeros in f(n-1), I need to know what f(n-1) is? Which is where my whole approach fails.

Assuming f(0) and f(1) are integers, find which powers of two and of five are factors of f(0) and f(1). The powers in f(n) can be calculated like a Fibonacci sequence and the number of trailing zeroes is the smaller of both sequences.

The Fibonacci series is defined by $fib(0)=0$, $fib(1)=1$, and for $n≥2$ we have $fib(n) = fib(n-2)+fib(n-1)$, so the series starts (0, 1, 1, 2, 3, 5, 8, 13 ...). If we start with different values and use the same recursion formula, we get for example the sequence (1, 0, 1, 1, 2, 3, 5, 8, 13...). If we define $fib(-1)=1$, then the n-th element of this sequence equals $fib(n-1)$.

The sequence starting with (x, y) and the same recursion formula (x, y, x+y, x+2y, 2x + 3y ...) equals $x \cdot fib(n-1) + y \cdot fib (n)$.

Let $f(0)$ have the factor $2^x$ and $f(1)$ the factor $2^y$ and no higher power of two, then $f(n)$ has the factor $2^z$, where $z = x \cdot fib(n-1) + y \cdot fib (n)$.

Likewise, let $f(0)$ have the factor $5^a$ and $f(1)$ the factor $5^b$ and no higher power of five, then $f(n)$ has the factor $5^c$, where $c = a \cdot fib(n-1) + b \cdot fib (n)$.

The number of trailing zeroes in $f(n)$ is

    $min(z_n, c_n)$ where

    $z_n = x \cdot fib(n-1) + y \cdot fib (n)$
    $c_n = a \cdot fib(n-1) + b \cdot fib (n)$


Dividing bins into segments This may be a question with a well known answer, but I've been thinking on it for two days, and can't quite come up with a satisfactory answer.

Consider the problem of dividing $p n$ bins numbered $1$ through $pn$ into $p m + 1$ segments by placing $pm$ balls.  If we let $k =  pn - pm \bmod pm+1$, then we can show that we may attain a placement of the $pm$ balls such that there are exactly $(pm+1) - k$ segments of empty bins of length $\lfloor \frac{pn-pm}{pm+1} \rfloor$ and $k$ segments of empty bins of length $\lceil \frac{pn-pm}{pm + 1} \rceil$.

Here's the tricky question: can we accomplish this task while ensuring that there are exactly $m$ balls in each interval $[(j-1)n + 1, jn]$, for $j \in \{1, 2, \dots, p\}$?

Every concrete example I work through answers in the affirmative, but I can't seem to get an algorithmic way of doing it, or mathematical proof that one such arrangement exists.

For particular examples, it always seems to work.  See an  example below with $p = 2,$ $n = 7,$ $m = 2.$

1| |X| | |X|1|X| | |X| | |

where 1 denotes the beginning of a new 'period', and | denotes the 'wall' of a bin, and X denotes a ball.  Note that 1 and | both denote 'walls' of bins.

For $0 \leq i \leq pm+1$, define
$$
x_i = \left\lfloor i \frac{pn+1}{pm+1} \right\rfloor.
$$
We put ball $i$ in bin $i$ for $1 \leq i \leq pm$. The length of the $i$th space (for $1 \leq i \leq pm+1$) is
$$
x_i - x_{i-1} = \left\lfloor i \frac{pn+1}{pm+1} \right\rfloor - \left\lfloor (i-1) \frac{pn+1}{pm+1} \right\rfloor \in \left\{ \left\lfloor \frac{pn+1}{pm+1} \right\rfloor, \left\lceil \frac{pn+1}{pm+1} \right\rceil \right\},
$$
so your first condition is satisfied (the spaces are as equal to each other as possible).

For your second condition, we need to verify that $1 \leq x_1,\ldots,x_m \leq n$, $n+1 \leq x_{m+1},\ldots,x_{2m} \leq 2n$, and so on. It's clearly enough to verify that $x_{Cm} \leq Cn$ for $1 \leq C \leq p$ and that $x_{Cm+1} > Cn$ for $0 \leq C < p$. For the first condition, we have
$$
x_{Cm} = \left\lfloor Cm \frac{pn+1}{pm+1} \right\rfloor < Cm \frac{pn+1}{pm+1} + 1 = \frac{Cpmn + Cm + pm + 1}{pm+1} \\ < \frac{Cpmn + Cn + pm + 1}{pm+1} = Cn+1,
$$
using your implicit assumption $m < n$. For the second condition,
$$
x_{Cm+1} = \left\lfloor (Cm+1) \frac{pn+1}{pm+1} \right\rfloor \geq (Cm+1) \frac{pn+1}{pm+1} = \frac{Cpmn + Cm + pn + 1}{pm+1} \\
\geq \frac{Cpmn + Cn + pm + 1}{pm+1} = Cn+1,
$$
using $Cm + pn \geq Cn + pm$, which follows from $(p-C)(n-m) \geq 0$.


How to find time complexity of this pseudocode Recently, I came across a question about finding sum of all values in range $[low, high]$ in BST $T$.

Then I formulated following algorithm to carry out that task:

  We do inorder traversal of BST ($sum = 0$ in start)
  But whenever we encounter any node having value strictly less than $low$ than we don't visit it's left subtree. We only traverse it's right subtree recursively in same manner.
  In same manner if we find any node having value strictly greater than $high$ than we don't traverse it's right subtree.
  If value of node falls in given range then we increment $sum$ by 1.

I think this algorithm correctly solve above problem in time complexity $O(m+lg(n))$ where $m$ is number of nodes having value in given range.

My reasoning for that time complexity is that we traverse at most $O(lg(n))$ nodes(This statement I'm not able to prove) which don't get added and we traverse $m$ nodes that gets added into $sum$. Which gives above time complexity.

At least any hint regarding how to prove this time complexity would be great.

Thanks.

It sounds like your pseudocode is equivalent to the following:

Do search for low in the BST. Find this value or the next largest value. (assuming that the BST is somewhat balanced, this is $O(lg(n))$)
In-order traverse until we reach an element that is greater than high, adding all values that we traverse to some running sum. (in order traversal of $m$ elements in a BST is time $O(m)$ since each element is visited at most twice.)
The running sum gives us our answer. The total runtime of this is $O(lg(n) + m)$

This is equivalent to what you write in your psuedocode I believe. The ignoring of subtrees that are not in the range of interest is what is done in a search.

Hope this helps!

For a proof:
First you should show that this algorithm is complete, i.e. show that it gets you the answer you want.

Then all you need to do is argue the asymptotic bounds. These arguments should be based on the fact that this is a BST, e.g. a search in a BST is in the worst case $O(h)$ where $h = O(lg(n))$ is the height of the tree because at each step in the search, you go up one level in the tree.


Transform unstructured flow charts into structured ones Has anyone studied the problem of converting a generic flowchart to a semantically equivalent "structured flowchart" (i.e. one that only uses the 'if' and 'while' block structure)?

I can see this may be relevant to code generation and optimization but I've not been able to find anything on the topic.

Intuitively, I would say that the graph corresponding to a structured flowchart must have no intersecting cycle, if this is not the case some sort of auxiliary variable must be introduced.

In the picture below, for example, the graph for the unstructured flowchart has the two cycle that intersect. In case of nested loops, one would have had one of the two cycle completely contained in the other.

I'm pretty sure that there's much more than this.

Could anyone point me in the right direction?

Yes.  This has been studied in the research literature under the name "goto removal" or "goto elimination": it is the problem of taking a program with gotos, and removing the gotos.

This became of interest after structured programming became more popular; one simplistic interpretation of structured programming was that you shouldn't use gotos.  See also the structured program theorem.

If you search for "goto elimination" on Google Scholar, you will find a number of papers that discuss this topic, and from there you should be able to find many more.


Finding a good loop invariant I want to prove that the following program is correct. The code takes an array i of length N and a number x. At the end, the value of found should be true if the array contains x and false otherwise.

found := false;
i := 0 ;
while i < N do {
    found := found || (a[i]=x);
    i:=i+1
}

The given preconditions are that N >= 0 and that the array is sorted in ascending order (however, I don't know how the fact that it is sorted can help).

As postcondition, I think the following would suffice: the value of found equals the value of the predicate “there exists an i in the range [0, N) such that a[i] == x”

However, I am stuck at this point and don't know how to continue. I cannot think of any loop invariant that has any relation to the postcondition. What would you suggest as a loop invariant?

You have an intended postcondition for a loop, and you're looking for an interesting invariant. In this scenario, try taking the intended postcondition, and replacing the total number of iterations (here N) by the number of iterations so far (here i). There's no guarantee that this is an invariant: that's only the case if the way the postcondition is somehow related to the structure of the loop. But if it is an invariant, it's definitely interesting, because it lets you prove the postcondition.

So we're interested in the following property: “the value of found equals the value of the predicate there exists a $k$ in the range $[0, i)$ such that $a[k] = x$”. Note that I use a name other than i for the existential variable, since i is now used in the context. The quantifier pile-up is:
for any value of N set before calling this snippet,
for any value of the variable i,
there exists an index $k$ such that …

It is easy to verify that this is indeed an invariant of the loop.

Intuitively, this property states that found reflects whether the element is in the array up to the point that has been traversed. At the end of the loop that traverses the whole array, found reflects whether the element is in the whole array.


Are all subsets of NP-complete languages also NP-complete? Is the following assertion true or false?

  If the language $L$ is NP-complete and $Q ⊆ L$, then $Q$ is NP-complete.

I know for example that $k$-coloring is NP-complete if I take $k$ as input, but 2-coloring is an infinite subset of this which is in P (see link). Therefore, for me, the assertion is false. However, I'm working through languages, and I cannot figure out an example (with language) useful to show false the assertion.

Take any infinite NP-complete language $L$. The language $L$ has uncountably many subsets, and particular there is some uncomputable subset $Q \subseteq L$. Since $Q$ is uncomputable, in particular it is not in NP, and so not NP-complete.

You can also try your example. Let $L$ consist of all pairs $(G,k)$ such that $G$ can be colored using at most $k$ colors, and let $Q$ consist of all pairs $(G,2)$ such that $G$ is bipartite; note that $Q \subseteq L$. It is known that $L$ is NP-complete, whereas $Q$ is in P. Therefore $Q$ is not NP-complete unless P=NP.


Do "Type-2" Turing machines with infinite length inputs have more computational power? Certain idealizations of a Turing machine yield an increase in computational power, such as an inductive Turing machine, which can (trivially) solve the halting problem if it has an infinite amount of time to run.

A related variation is the "type-2 Turing machine" defined by Weihrauch, which (if I understand correctly) is basically a Turing machine with an infinite-length input, and a write-only output tape for which previous outputs cannot be changed. Such models are useful for describing real computation.

Does this model of computation have more computational power than a standard Turing machine, similar to the inductive one?

I would naively guess yes, since the theory of "type-2 computability" and "type-2 recursion" seems to be distinct from the ordinary theory of computability, and it seems intuitive that anything which is "type-1 computable" should also be "type-2 computable" (but not the other way around). However, I am unsure of all this.

Burgin (2004) seems to suggest this as a model of hypercomputation in his book on "super-recursive algorithms," but as he does not offer a proof of such, I may be misinterpreting.

Type-2 Turing machines are not more powerful than ordinary Turing machines in the sense that any map $\mathbb{N} \to \mathbb{N}$ that can be computed by a type-2 machine can also be computed by an ordinary machine. To see this, suppose a type-2 Turing machine $T$ computes a function $f : \mathbb{N} \to \mathbb{N}$. We can convert $T$ to an ordinary machine by modifying it so that it stops as soon as it writes $f(n)$ on the output (and we can tell when this happens because the output is a single finite number, so it cannot take forever for the machine to produce it).

It is far more interesting to go up one level and compare computability of functionals, which are maps
$$F : \mathbb{N}^\mathbb{N} \to \mathbb{N}$$
that take an infinite sequence of numbers as an input and output a number. Now there is a difference between type 1 and type 2.

Say that a functional $F$ is type-2 computable if there exists a type-2 Turing machine $T$ such that, for any sequence $\alpha \in \mathbb{N}^\mathbb{N}$, when $\alpha$ is written on the input tape and machine $T$ is run, it writes $F(\alpha)$ on the output tape (and terminates).

Say that a functional $F$ is type-1 computable if there exists a type-1 Turing machine $T$ (i.e., an ordinary one), such that, for any computable sequence $\alpha \in \mathbb{N}^\mathbb{N}$, if we write onto the input tape the encoding $n$ of a machine that computes $\alpha$, then $T(n)$ writes $F(\alpha)$ on the output tape (and terminates).

Notice that a type-1 computable functional only accepts computable inputs, whereas a type-2 computable functional accepts all inputs. If we write $\mathcal{R}$ for the set of all computable sequences of numbers (i.e., the total computable functions), then a type-1 computable functional is a map $F : \mathcal{R} \to \mathbb{N}$ computed by some type-1 machine, whereas a type-2 computable functional is a map $F : \mathbb{N}^\mathbb{N} \to \mathbb{N}$ computed by some type-2 machine.

Because $\mathcal{R} \subseteq \mathbb{N}^\mathbb{N}$, we can convert any type-2 functional to a type-1 functional by simply feeding it only computable inputs. We have:

  Theorem: When a type-2 computable functional is restricted to computable inputs, it becomes a type-1 computable functional.

Proof. The theorem is not a complete triviality. The input is presented to a type-2 functional as a sequence, whereas to a type-1 functional it is presented as a description of a Turing machine computing the sequence. So, suppose $F$ is a type-2 functional computed by a type-2 machine~$T$. We convert $T$ to a type-1 machine as follows: when given an input $n$ which described a machine $M$ that computes some $\alpha \in \mathcal{R}$, we simulate an input type for $T$ so that whenever $T$ wants the $k$-th cell of the input, we run $M(k)$ to compute $\alpha(k)$ and give $T$ the answer. $\Box$

Can we go in the other direction? Suppose $F : \mathcal{R} \to \mathbb{N}$ is computed by a type-1 machine $T$. Perhaps we can extend $F$ to all of $\mathbb{N}^\mathbb{N}$ to get a computable $\overline{F} : \mathbb{N}^\mathbb{N} \to \mathbb{N}$ which agrees with $F$ on $\mathcal{R}$? The anwser is negative! (See Exercise 15-40 in H. Rogers Jr. "Theory of Recursive Functions and Effective Computability".)

The moral of the story is this (as I have often repeated on these forums): all known notions of computability of functions from numbers to numbers agree, but notions of computability of functionals do not, and they are incomparable in general.


How is type safety handled differently between reference and value types? I'm trying to understand how type safety is preserved for value types and for reference types, specifically in languages with managed memory (such as C#).  I understand that reference types (i.e. classes) have data allocated onto a managed heap, with a reference to that data allocated on the stack.  Is there metadata about the type of the data passed around with the pointer?  Is there a new 'pointer type' created along with the class itself?

I've been looking at this SO question and this blog post but neither discuss typing itself as it relates to these topics.

There usually is metadata about the runtime class of an object contained within the object itself, regardless of what language you're working in. This metadata is essential in languages like C# that have automatic memory management. In order to clean up an object that is no longer referred to by any other objects, you need to clean up all of its members too, which means deciphering exactly what class it is.

Just how that metadata is stored is up to the individual language implementation. Some languages make classes themselves into objects, and the metadata will consist of a pointer to the class. For example, this approach is used in some Common Lisp implementations (for reasons that we don't need to get into).

Other languages are a little more subtle about it. For example, in many object-oriented languages, an object stores a reference to a virtual function table or vtable. The vtable is a struct consisting of pointers to all of the implementations of that class's methods; the language runtime is responsible for setting up all of the vtables. Every instance of a class will store a reference to the same copy of that class's vtable, so you can figure out what class an object belongs to by asking which vtable it points to. This is exactly how object-oriented programming was mimicked in plain old C (see this article) and how it works under the hood in C++.

These kinds of complications are necessary because of inheritance. If I have an object x and I know it's of class A, x could really be an instance of any subclass B of A, and the language runtime needs to ascertain what the real class is in order to do method dispatch or garbage collection properly. In C#, struct types don't have inheritance at all, unlike class types. So a struct might have no metadata -- if the type of x is S and S is a struct type, it can't possibly be anything else.

I hope this at least addresses your narrow question about metadata. As for the much broader issue of type safety, have a look at Pierce's Types and Programming Languages, especially the chapters on subtyping.


Number of double wedges containing a point We have a set of $n$ double wedges on a plane. (By double wedge, I mean two lines intersecting at a point, with opposite sides of the point considered as "inside" the double wedge.) Now these $n$ double wedges can intersect each other.
Our query is as follows: given a point, we want to find how many double wedges it's contained in. We want to be able to make this query in $O(\log n)$ time, using a data structure that can be constructed (preprocessed) in $O(n^2\log n)$ time and $O(n^2)$ space.
This exercise is from the de Berg's computational geometry book in the chapter about arrangement of lines, so I was thinking we can do some kind of incremental construction by adding the double wedges one by one, but I can't seem to think of the data structure.

The set of $2n$ lines on the plane form a well studied Arrangement of lines, which is a type of planar subdivision, composed of vertices, edges and faces. This planar subdivision used to be represented by DCEL. There are two types of algorithms, which can convert a bare set of lines into the DCEL - plane sweeping algorithm with time complexity $O(n^2log(n))$, and incremental one with time complexity $O(n^2)$. Both these types are described in this book (Item 8.3). The resulting subdivision will have $O(n^2)$ faces.
Given a planar subdivision with $O(n^2)$ faces we can convert it further into a hierarchical data structure, which can be used to locate a face, containing any query point, in $O(log(n))$ time. This is a topic with long history - please see the Point location page for more information.
So, if we assign a number of double wedges, containing a point, to each face of the planar subdivision - we'll solve the exercise. Let's find out how we can do just that.
Each double wedge defines four parts of the plane, and we need to define clearly, what parts are inside the wedge. In order to do that we'll split each boundary line into two rays - one pair of "incoming" rays and one pair of "outcoming" rays. We'll consider a part of the plane, lying to the left of each such ray, to be inside the double wedge.

The direction of these rays can be used to calculate the number of intersecting double wedges (called below an intersection number), corresponding to each face of the planar subdivision. It's easy to see, that these numbers for adjacent faces differ by one. Even more, if we jump from some face to another face over a boundary edge, directed from the left to the right, we'll need to increment this number. If the boundary edge is directed from the right to the left, then this number needs to be decremented. An example of two double wedges $w1$ and $w2$ with assigned intersection numbers (in red) is below.

So, the algorithm to assign intersection numbers to faces comprises of two steps:
Step 1. Take an arbitrary initial face and calculate its intersection number, using all the $n$ double wedges - it can be done in $O(n)$ time.
Step 2. Traverse all the faces of the planar subdivision, starting from the initial face and assigning the intersection number using boundary edges direction as described above - it can be done by the DFS in $O(n^2)$ time.


Finding examples of languages that are "anti-palindromic" Let $\Sigma = \{ 0, 1 \}$. A language $L \subseteq \Sigma^* $ is said to have the "anti-palindrome" property if for every string $w$ that is a palindrome, $w\notin L$. In addition, for every string $u$ that is not a palindrome either $u\in L$ or $\mathrm{Reverse}(u) \in L$, but not both(!) (exclusive or).

I understand the anti-palindrome property, but I could not find any languages that have this property. The closest one I could find is $\Sigma^* \setminus L$, but it does not have the exclusive or part... that is, for example, both $01$ and $10$ are in $L$.

Could anyone give me an example of a language that has this propery? Or possibly even more than a single example, because I fail to see what kind of limitations this puts on a language. (Must it be non-regular? Context Free? Or not even in $R$? and etc.)

One example will be $L = \{ x\ \ |\ \   binary(x) < binary(x^R), x\in [0,1]^*\}$.

And yet another example $L' = \{ x\ \ |\ \   binary(x) > binary(x^R), x\in [0,1]^*\}$.

The idea is, if $x \neq x^R$ you make  a rule to choose only one of them. You need to choose the rule such that palindromes should be rejected ($f(x) < f(x^R)$, for palindromes you must have $f(x)= f(x^R)$).You can also change the alphabet, I took binary alphabet just to get a quick answer.

$L$ and $L'$ above are not regular. And every anti-palindromic language will be non-regular and can be as bad as a non-RE language. Examble of an undecidable language: $L=\{x\ \ |\ \ $such that $ binary(x)<binary(x^R)$ if both $x$ and $x^R$ $\not\in$ Halt or both $x$ and $x^R$ $\in$ Halt, otherwise if $x \in$ Halt$\}$

Klaus Draeger explained in the comment below that anti-palindromic language given at the beginning of the answer is context-free: $L=\{x0y1x^R\ |\ x,y\in\{0,1\}^*\}$


Finding which functions are bounded by $O(n^2)$ I am asked to select the functions that are bounded by the Big-Oh function O(n^2): $f(n) \in O(n^2)$.

$f(n) = \sum_{i=1}^{n} n$
$f(n) = \sum_{i=1}^{n} i$
$f(n) = n + n^2$
$f(n) = 1$

I choose the answers 1, 2, and 4:

Simplifies to $n \cdot n = n^2$, which is bounded by $O(n^2)$
Simplifies to $\frac{n(n + 1)}{2} = n^2/2 + 1/2$, which is bounded by $O(n^2)$
$n^2 + n$ is obviously not bounded by $O(n^2)$
$1$ is obviously bounded by $O(n^2)$

However, it was alerted to me that one of my answers is incorrect. That seems strange, considering that after expanding all the expressions mathematically, I believe that I have chosen whether they are bounded by $n^2$ correctly.

We have $n^2 + n = O(n^2)$. Indeed, if $n \geq 1$ then $n^2 \geq n$ and so
$$
n^2 + n \leq 2n^2.
$$


Complexity of $O(\log(n^n))$ vs $O(\log(n!))$ Is $O(\log(n^n)) < O(\log(n!))$? Is there any good/practical algorithm with this kind of complexity?

And also, to check my understanding of algorithmic complexity, are these two $> O(n\log(n))$?

I'm just starting with this topic and not really sure if I'm getting it right.

Thanks and stay safe.

$O(\log n^n)$ and $O(\log n!)$ both describe the same set of functions.

Notice that $( \frac{n}{e} )^n \le n! \le n^n$ and hence:

$O(n \log n)  = O(n \log \frac{n}{e}) = O( \log ( \frac{n}{e} )^n) \subseteq O(\log n!) \subseteq O(\log n^n) = O(n \log n)$.

This shows that all the above sets coincide.


Why whenever a caller or client modifies a library collection class, all iterators are made invalid? Whenever a caller or client modifies a library collection class, all iterators are made invalid (with the exception of the iterator through which the change was made, in the case of remove). Give a reason for this rule in the case of an array list (using a dynamically sized array, in which an iterator has a pointer to the array) and in the case of list (using linked list nodes, in which case the iterator points to one or more list nodes).

The question is "why".

There are two problems: First, you would have to define how an iterator that doesn't become invalid would change if the underlying container changes. That will be an interesting problem. Some languages have iterators that can iterate through hash tables, enumerating all (key, value) pairs in some order. Now imagine you insert an item into the hash table, the number of items becomes too large, and the whole hash table is re-hashed, and you need to define how the iterator is modified in a meaningful way.

Second, if the iterators need to stay valid, you need to keep track somehow which iterators are involved with which underlying container. That's not too difficult, but costs time and space. Together with the first problem, it's much easier to just declare any iterator as undefined after a change.

PS. If you copy / paste this as an answer to a homework question, your teacher will most likely trace it back to this post.


How to properly calculate dependent nested loops for big-O I am revising for my algorithms exam and I have come across one topic in particular that I do not quite understand; which is how to analyse dependent nested loops. I know if we have a 2-nested loop, both of which iterate $n$ times, the order will be of $n^2$; but if we have a dependent nested loop such as:

input = an n-dimensional array
For i = 0; i < n; i++:
        For j = 0; j < i; j++:
            ...

Am I correct in thinking this would always be $O(n^2)$ as in the worst case, this loop will always be $n^2$?

The lecturer gave us the forumla $\frac{1}{2}n(n+1)$ but has not explained in what context this is to be used for calculating the running time of a 2-nested loop with dependency. Is there a general way to calculate the running time of a dependent nested loop, like there is with standard nested loops?

We can write the for loop as the sums;

$$\sum_{i=1}^{n} \sum_{j = 1}^{i} 1 = \sum_{i=1}^{n}i = \frac{n(n+1)}{2} \in\mathcal{O}(n^2) \, .$$

Note: set the starting values from $i = 1$ and $j = 1$, and increment the upper boundaries also. The calculation in the inner function is assumed as a constant operation and it will not change the calculation.


Information loss of a 9-input majority gate According to information theory, the logic gates AND, NAND, OR, NOR all lose 1.189 bits of information each with two bits of information at their inputs and with all inputs being independently and uniformly distributed.

When gates are used in combination with other gates in a circuit, to calculate the entropy loss for the entire circuit you have to use what are called "mixture probabilities" or "mixing distributions" to calculate the entropy loss, the loss for each gate being dependent on the entropy loss history of the preceding gates.

Can anyone calculate the entropy loss of a majority gate with 9 inputs, all equally likely $\{1,0\}$?

Let me first explain what the entropy loss is for a gate like AND. The input entropy is $2h(1/2) = 2$ (where $h(p) = -p\log_2p-(1-p)\log_2(1-p)$), while the output entropy is $h(1/4)$ (since the probability that the output is $1$ is $1/4$). Therefore the entropy loss is $2 - h(1/4) \approx 1.189$.

In the case of recursive majority, the output is uniform, so the output entropy is $1$. The input entropy, in contrast, is $9$, and so the entropy loss is $9-1=8$.


Is there an existing protocol where a sender does not know who he is sending data to? I was thinking about how the BitTorrent protocol automatically gives every peer a list of IPs of every other user who is currently seeding / leeching off the torrent in question. Is there an existing protocol where, somehow, the destination address is vague enough or unknown to the sender (and perhaps becomes more known as the packet is sent through the routers ?) Or is there research in implementing something like this that could be interesting to read ?

If you want strong protections for the identity/anonymity of the participants, you might be interested in systems for anonymous communication, such as Tor.

If you're just interested in systems where the destination's address isn't necessarily known under normal operating conditions (but it's not a critical security goal to ensure it can never be known), you might be interested in peer-to-peer overlay networks, such as Chord and many others.


What exactly is a "binary file"? I suspect this may be more of a concept / theory question, but, I haven't been able to wrap my brain around what exactly a binary file is.

I've read links such as the below:

https://en.wikipedia.org/wiki/Binary_file

https://betterexplained.com/articles/a-little-diddy-about-binary-file-formats/

But, the piece of the puzzle that's confusing me, is that ALL files are stored as 1's and 0's on a hard-disk, or, in RAM, etc.
(i.e. there's no physical engraving of the hex characters "6F" onto a disk platter for example; it's still a binary format that the data is stored in).

So, if all files are stored as binary, then, presumably it's an operating-system, (& filesystem) concept to refer to something as "binary" file?

A binary file is a file that is simply not a text file. It means that a bin file has a specific format (mp3, exe, jpg...) and can not be interpreted only as a character sequence. There are many ways data can be formatted and read.


Bucket sort with gaussian distribution Bucket sort algorithm lets you sort an array of $n$ elements in expected $O(n)$ time, supposing the elements are equally distributed in the $\lbrack 0,1 )$ interval.

Is there a way to modify the bucket sort in order to sort in expected $O(n)$ time an array of $n$ elements distributed in $\lbrack 0,1)$ according to the Gaussian distribution?

The algorithm works by choosing the number of buckets and the boundaries of the buckets such that in expectation the number of elements that land in a bucket is constant. The analysis is particularly simple for a uniform distribution, because uniformly sized buckets work.

For more complicated distributions you have to choose your bucket size more cleverly, but there is nothing stopping you from looking hard at the probability density function and creating more buckets in regions where you'd expect many elements to occur.


Practical applications of disjoint set datastructure I know that the disjoint set datastructure is used   to keep track of the connected components of an undirected graph when the edges are added to the graph dynamically . I also know that is is used in Kruskal's  algorithm for minimum spanning trees . What are the other possible applications of this datastructure ?

Maze generation (using a modified Kruskal's algorithm)
Tarjan's off-line least common ancestors algorithm
Connected component labeling
Online maintenance of biconnected components
Validation Hindley–Milner rules
Computing the winner of Havannah board game (see Efficient Playouts for the
Havannah Abstract Board Game)
Alias analysis
Used in construction of contour trees (see Laying the Foundations for an Advanced
Visualization System in O'Caml and Multi-Resolution computation and presentation of Contour Trees)


polynomial time reducibility - $L_{2} \notin \textbf{P}$ and $L_{1} \leq_{p} L_{2} \implies L_{1} \notin \textbf{P}$ If we have two languages $L_{1} \subseteq \Sigma^{\ast}_{1}$ and $L_{2} \subseteq \Sigma^{\ast}_{2}$

I proved that when $L_{2} \in \textbf{P}$ and $L_{1}  \leq_{p} L_{2}$ then $L_{1} \in \textbf{P}$

Is it also true that when $L_{2} \notin \textbf{P}$ and $L_{1}  \leq_{p} L_{2}$ then $L_{1} \notin \textbf{P}$? I don't think it's, but I can't find a counter-example.

Let $L_1=\emptyset$ and $L_2=\{\langle M\rangle\mid M\text{ halts on empty string}\}$. Let $s$ be a string that does not belong to $L_2$, for example, the empty string, which is a string that does not even represent a Turing machine. The reduction $f$ is $\forall x, f(x)=s$.

Now you can see $L_1\in\mathbf{P}$ and $L_2\notin\mathbf{P}$ (in fact, $L_2$ is undecidable), and $f$ is a polynomial-time reduction (it just ignores the input and outputs $s$ directly). Also, $x\in L_1\Leftrightarrow f(x)\in L_2$ (note $x$ always $\notin$ $L_1$ and $f(x)=s$ always $\notin$ $L_2$).

This is a counter-example.


Origin of the terms "safety" and "liveness" for concurrent algorithm properties? Properties of concurrent algorithms are usually divided into two categories:

Safety - something must not happen.

Properties in this category are for example partial correctness and sometimes deadlock-freedom (the latter depending on the author).
Liveness - something that must happen eventually.

Properties in this category are for example termination and starvation-freedom.

Which publication introduced these terms?

The oldest reference I was able to find is "Proving the Correctness of Multiprocess Programs" by Leslie Lamport, dated March 1977:

  To prove the correctness of a program, one must prove two essentially different types of properties about it, which we call safety and liveness properties. [...]

It does, however, not claim to introduce these terms.

Lamport commented on his paper "Proving the Correctness of Multiprocess Programs" as follows:

  This paper introduced the concepts of safety and liveness as the proper generalizations of partial correctness and termination to concurrent programs. It also introduced the terms "safety" and "liveness" for those classes of properties. I stole those terms from Petri nets, where they have similar but formally very different meanings. (Safety of a Petri net is a particular safety property; liveness of a Petri net is not a liveness property.)

This can be seen as a claim that he (Lamport) has introduced the terms.


Is Ω(f+g) = Ω(min(f,g))? We know that $O(f(n)+g(n))=O(max(f(n),g(n)))$.

So can we say that $\Omega(f(n)+g(n)) = \Omega(min(f(n),g(n))$?
Then what is $\Theta(f(n)+g(n))$ equal to?

Assuming $f,g > 0$, we have
$$\max(f(x),g(x)) < f(x) + g(x) \leq 2\max(f(x),g(x)).$$
Therefore $\Theta(f(x) + g(x)) = \Theta(\max(f(x),g(x)))$, in the sense that both sets of functions are equal.

Still assuming that $f,g > 0$, it is also true that $\Omega(f(x)+g(x)) = \Omega(\min(f(x),g(x)))$, in the sense that if $h(x) \in \Omega(f(x)+g(x))$ then also $h(x) \in \Omega(\min(f(x),g(x))$. The stronger bound $\Omega(f(x)+g(x)) = \Omega(\max(f(x),g(x)))$ also holds.

I have mentioned two interpretations of equality. In fact the second one (which really corresponds to $\subseteq$ in this case) is actually the standard one – equality is not symmetric! However, in the case of big $\Theta$ both notions fortunately coincide.


Reference/book recommendations for search data structure I am interested in data structures that support efficient searching of various kinds.

When I read the Wikipedia page of "search data structure", it says "Useful search data structures allow faster retrieval; however, they are limited to queries of some specific kind". So, obviously, there exists a correlation of one specific data structure and the searching operations it supports. For example, k-d tree supports efficient query of multiple-dimensional data.

Of course, the data structures I am thinking about are not limited to arrays or trees. They can also be graphs or more advanced structures.

I am new to this field. So I am wondering if anyone can recommend some books or review papers that summarize different search/query data structures.

Thanks in advance.

I highly recommend MIT course on Advanced Data Structures, I was watching  Eric Demaines lectures, he shows multiple examples, here are some of them:

Van Emde Boas tree
Y-fast trie

Here some suggested reading from their website:

Data Structures and Network Algorithms by Robert E. Tarjan (covers
BSTs, splay trees, link-cut trees)
Open Data Structures by Pat Morin (covers BSTs, B-trees, hashing, and
some integer data structures)

MIT course

YouTube lectures


Every AVL tree may be red black tree I proved by induction that every AVL tree may be colored such that it will be red black tree. The problem is that I can't see an error in my proof.  Look at my proof.

Induction for height.
Let's assume that it is truth for each AVL tree of height at most $h$.
Let's consider AVL tree $T$ of height $h+1$.  Now, let's consider two subtree of $T$ - $L$ and $R$. We know that $height(R)\le h$ and $height(L)\le h$.   Hence using induction hypothesis we conclude that $L$ and $R$ may be colored such that $L$ and $R$ will be red black tree.  Then we may paint root - of course black color.   Now $T$ is AVL and black tree.

Your proof produces a tree in which all nodes are colored black. It doesn't necessarily satisfy the "black height" rule:

  Every path from a given node to any of its descendant NIL nodes contains the same number of black nodes.

Not every AVL tree satisfies this condition, for example the Wikipedia example doesn't.


Relative succinctness of NFAs and regular expressions What is known about the succintness of NFAs, relative to regular expressions?

In order to clarify the question, let me explain what I know. The regular languages can be characterized by any of the following:

A language is regular iff it can be recognized by an NFA.
A language is regular iff it can be recognized by a DFA.
A language is regular iff it can be defined by an MSO formula.
A language is regular iff it can be described by a regular expression.

The family of languages $(\{w\in\{0,1\}^* \mid |w|>n, w_{|w|-1-n}=0\})_{n\in\omega}$ has NFAs with $n+1$ states. For DFAs, there is a lower bound of $2^n$ states. This family exemplifies that the translation from NFAs to DFAs necessarily incurs a worst-case exponential explosion of size.

In the other direction, there is no explosion, because each DFA is an NFA. Together, we can say that NFAs are exponentially more succinct than DFAs.

A similar result holds for the comparison of automata (either NFAs or DFAs) to MSO formulae: The formulae are non-elementarily more succinct.

I am aware that the translation from regular expressions to NFAs is linear and that there is an exponential translation in the other direction. Now to the actual question: Is it known that an exponential blowup cannot be avoided? What NFAs (or even DFAs) witness this? What techniques are used to prove non-existence of short regular expressions?

This question leads me to assume that divisibility languages are witnesses. That was what prompted the present question.

DFAs can be exponentially more succinct than regular expressions. A simple example is the language of all words over $\{a,b\}$ in which the number of $a$s and the number of $b$s are each divisible by $n$. This is accepted by a DFA of size $n^2$, but requires a regular expression of length $2^{\Omega(n)}$. For proof, see Example 23 in the survey From finite automata to regular expressions and back by Gruber and Holzer.

Gruber and Holzer improved this in their paper Tight bounds on the descriptional complexity of regular expressions, also mentioned in their survey (Theorem 24 of the survey). In fact, they prove an even stronger result (Theorem 8 of the paper): there is a language described by a regular expression of length $O(n)$ whose complement requires a regular expression of length $2^{2^{\Omega(n)}}$. (A regular expression of length $O(n)$ corresponds to an NFA having $O(n)$ states and so to a DFA having $2^{O(n)}$ states, whose complement has the same number of states.) The regular expression with this wondrous properties, over the alphabet $\{0,1,\$\}$, is
$$
(0+1)^{\geq 1} + (\epsilon + \Sigma^*\$)\bigl((0+1)^{\leq 4n-1}\$ + (0+1)^{\geq 4n+1}\bigr)\Sigma^* \\
+ \Sigma^*\$(0+1)^{3n}(0+1)^*0\Sigma^{n+1}1\Sigma^* \\
+ \Sigma^*\$(0+1)^{3n}(0+1)^*1\Sigma^{n+1}0\Sigma^* \\
+ \Sigma^*\$(0+1)^*0\Sigma^{2n}1\Sigma^* \\
+ \Sigma^*\$(0+1)^*1\Sigma^{2n}0\Sigma^*
$$
We can even obtain an example over the binary alphabet $\{a,b\}$ using the homomorphism
$$
0 \mapsto abbb, \quad 1 \mapsto aabb, \quad \$ \mapsto aaab.
$$

The way all of these results are proved is via the concept of star height: a language of star height $h$ requires a regular expression of length $2^{\Omega(h)}$. Unfortunately lower bounds on the star height are rather difficult to establish, so instead one uses the more manageable cycle rank, a theorem of McNaughton identifying the two for a class of languages known as bideterministic. (For more details, consult either of the sources cited above.)


textbook on the human brain for computer scientists/machine learning professionals? The human brain as studied by neuroscientists, or neurobiologists, generally focus on what I would call

implementation details (how specifically does information transport between synaptic channels, i.e. what are the chemical processes)
vague generalities (e.g. about "memory" as a psychological concept and in very vague terms what types of memory there are without studying them mathematically)

There is nothing intrinsically wrong with this.

But I am interested in the brain as a computational system. Of course we don't yet understand the brain very well, but is there a book on the brain that a computer scientist or machine learning professional could read to get a computational/systematic understanding of what we know about the brain? e.g. what is the computational role of various neurotransmitters (without going into chemistry), etc.

There is no "textbook" on this. However, there is a book! It is How to Create a Mind by Raymond Kurzweil, the director of engineering at Google. Excellent book that explains the brain from a computer-science perspective. It goes into a lot of detail.

Check out the intro sound bytes on Audible.

For a closer to the metal (i.e. actual implementations of models of the brain), check out Cognitive Architectures, such as ACT-R, Soar, CLARION, ICARUS, EPIC, LIDA, etc. Here is a survey.


Is it possible to build short proofs of arbitrary folds over a huge list? With the use of Merkle Trees, you can prove the presence of an element of a very big list, with an amount of information close to just logarithm of the size of the whole tree. Merkle proofs, thus, probabilistically confirm the result of this specific fold:

isMember :: ∀ t . List t -> Bool
isMember e = foldr (\ h t -> h == e || t) False

My question is if the same result can be extended to arbitrary folds; or, in other words, is it possible to prove arbitrary computations over a big list using some clever trick similar to Merkle Trees?

Formally

Given those 5 values:

H :: String -> Uint256, a fingerprint function
H(X) :: Uint256, the fingerprint of a dataset
F :: String -> String, an arbitrary computation
Y :: String, the claimed result of F(X)
A short proof

I need a verify function that returns true iff F(X) == Y, without having to run F(X); perhaps not even having the whole original dataset X.

Specific example

Suppose that you have a huge dataset (20 GB) distributed through a network of 100 computers that don't trust each-other. Is there any way for a computer to generate a claim such as the sum of this dataset is 1650874919052809!, so that other nodes are able to probabilistically verify that claim is correct, without actually running sum dataset?

Yes, there is a generalization of the construction you mentioned.  However, it's utility depends on the function F.  The guarantees you get are meaningful only if F is robust, in the sense that you have to change a large fraction of the dataset to make any (meaningful) change to the output of the computation.

Suppose we have an untrusted agent Agatha who is going to do the computation for us and try to prove that she did it correctly.  She'll build a Merkle tree in the same way, with one leaf per prefix of the list, and the leaf holding (the hash of) the intermediate state of the fold after processing that prefix.  Thus, a list with $n$ items will involve construction of a Merkle tree with $n$ leaves.  Agatha will send the hash at the root of the Merkle tree.  She will also send the value at the rightmost leaf and a witness to its value.  $\newcommand{\pl}{\operatorname{polylog}}$

Agatha will do $O(n)$ work to compute the fold and build the Merkle tree.  We want the verifier to be able to verify the correctness of the result, using only $o(n)$ time and $o(n)$ communication with Agatha.

How will the verifier check Agatha's claimed result?  The verifier can pick two adjacent leafs at random, ask Agatha to send a witness to the values at those two leaves, and re-apply F to check that the second was correctly obtained from the first.  The verifier can repeat this many times.  In each round, Agatha sends $O(\lg n)$ bits, and the verifier does $O(\lg n)$ work.

Now suppose Agatha cheats on at least a $p$ fraction of the F applications.  Will this be detected?  Well, each round has at least a  $p$ chance of detecting Agatha's malfeasance.  Thus, after $100/p$ rounds, there is a $(1-p)^{100/p} \approx e^{-100} < 2^{-128}$ chance that Agatha's malfeasance goes undetected.  In other words, $O(1/p)$ rounds suffice to detect Agatha if she cheats on at least a $p$ fraction of the applications of F.

On the other hand, if Agatha cheats on only a single application of F (say), she has a good chance of getting away with it; the verifier has no good way to detect this.

So, this construction is only useful if F is such that cheating on a small number of applications of F is harmless.  This is closely related to the notion of a robust function, from robust statistics, which is about functions where changing a small number of inputs makes only a negligible change to the final output.  For instance, since the sum, max, and min are not robust, this construction is not useful for computing the sum, max, and min.  However, the median is robust, and the median can be computed securely via such a tree.  As a simpler example, consider counting the number of entries in the database that match some pattern; this can be done securely via such a tree.  In particular, Agatha can cheat on at most a $p$ fraction of nodes, and we can arrange that this changes the final count by at most $pn$.  If that bound on the (additive, absolute) error is good enough, then we can achieve acceptable security.

In practice you probably typically don't want to use this kind of general construction.  You can often do better by building a protocol that is specialized or customized for the particular function F you are dealing with.  You can find many papers on this topic in the research literature, under names like "secure aggregation" or "outsourced computation" or "resilient aggregation".  I've seen papers in the database literature, the cryptography literature, and the sensor network literature.

For example, if F is associative and commutative, and if the fold is robust, then we can obtain a secure Merkle tree scheme, where each internal node in the tree holds the result of the fold on a sublist corresponding to the subtree rooted at that internal node.  (This is a bit different than the prefix construction mentioned earlier, and offers better security when F satisfies this property.  The verifier needs to pick a random node and check that it was constructed correctly, rather than picking a random leaf.)

The preceding paragraph immediately lets you compute the "count" operator securely, up to an additive error of $\pm pn$.  If we want to compute the median, Agatha can first compute the median offline, say $m$, then report $m$, and use a count query to count the number of data items that are $\le m$.  The verifier can verify this count query up to an additive error of $\pm pn$, which proves that $m$ isn't "too far" from the true median (its rank differs from the rank of the true median by at most $\pm pn$, which in practice means it'll be quite close to the true median).

There's lots more one can say, and I've probably made oversimplifications at multiple points in this exposition, but hopefully this gives you some ideas and an entry point to the research literature on this subject.


Solving unusual recurrence with two variables I have the following recurrence relation:
$$T(n,k) = T(n-1,k)+T(n-1,k+1)$$
With the following base cases (for some given constant $C$):
For all $x \leq C$ and for any $k$: $T(x,k)=1$
For all $y \geq C$ and for any $n$: $T(n,y)=1$
I want to get a formula for $T(n,0)$. I think that it can be seen that after $i$ iterations we get the following relation:
$T(n,0) = \sum_{j=0}^i {n\choose{j}}\cdot T(n-i,j)$
But I don't know if it helps and can't proceed much further than that.
My question is $-$ what are the right techniques for dealing with recurrence with 2 variables, and in particular with this recurrence (where the second variable is increasing)?

In the cases $C\leq0$ and $C\geq n$ you have $T(n,0)=1$.
Assume that $0<C<n$. Show that
$$T(n,0)=\sum_{i=0}^{\color{red}{k}}\binom{\color{red}{k}}{i}T(n-\color{red}{k},i)$$
for $0\leq k\leq n-C$ and $n\leq 2C$. It looks like this is the formula that you mentioned in the question, except that the binomial coefficient should have the same amount that is being subtracted from the first entry of $T$.
Apply it for $k=n-C$.
We get $$T(n,0)=\sum_{i=0}^{n-C}\binom{n-C}{i}T(C,i)=\sum_{i=0}^{n-C}\binom{n-C}{i}=2^{n-C}$$
If $n>2C$ the formula that we get is
$$T(n,0)=\sum_{i=0}^{\color{red}{C}}\binom{\color{red}{k}}{i}T(n-\color{red}{k},i)$$
Putting $k=n-C$ we get
$$T(n,0)=\sum_{i=0}^{C}\binom{n-C}{i}T(C,i)=\sum_{i=0}^{C}\binom{n-C}{i}\in O(n^C)$$
since it is a polynomial of degree $C$.

We didn't need it this time, but a technique that could be useful to work with recurrences is generating functions.


For data-path cycles in MIPS, what determines wheter a control signal gets the "don't-care" value? For example for the  sw command in MIPs, the control signal values are

ALUOp1: 0

ALUOp: 0

RegWrite: 0

MemRead: x

MemWrite: 1

Branch: 0

ALUsrc: 1

RegDest: x

MemToReg: x

Why do memRead, RegDest and MemToReg have the values of x? Why not just 0?

A control signal controls a single component in the architecture. When the command that is now active is not using the component this control signal controls, the control signal gets the "don't care" value.

The principle is that you don't want to restrict yourself for not using this component (=0 value), because any constraint will create a more complex logic inside the cycle. Instead you are freeing yourself from this choice by assigning the control signal with a "don't care" value, which means you can minimize the logic in the cycle and allowing the irrelevant component to work in the background (with no obvious bad consequences).

As you mentioned in your example, while using the sw command, you don't need to read anything from the memory. You could assign MemRead with the value 0, but why overkill it? It's easier to don't care if it reads data from the memory or not (it will read gibberish though), and RegWrite=0 (which in turn controls the writing of what was read from the memory) won't allow the use of this read anyway.