Want to know the time complexity inner for loop which is partially iterating the array Question: Find out next increasing value of each element in this below array.

int[] array = { 5, 2, 7, 10, 4, 12}

e.g)
     5's nextIncreasingValue: 7
     2's nextIncreasingValue: 7
     7's nextIncreasingValue: 10
     ...
     12's nextIncreasingValue: -1

Implementation:

for(int i = 0; i < array.length; i++) {
        int nextIncreasingValue = -1;
    for (int j = i + 1; j < array.length; j++) {
        if(array[j] > array[i]) {
            nextIncreasingValue  = array[j];
            break;
        }
    }
    PRINT("For " + i + "th next increasing value is: " + j)
}

Now I want to know the time complexity of this program, since each time inner for loop is skipping some of the elements on iteration. So it cannot be O(n^2) even in the worst case.

Kindly explain me what will be the time complexity?

O(n) Solution using stack:

Stack s = new Stack();
for(int i = 0; i < array.length; i++) {
   while(!s.isEmpty() && array[i] > s.peek()) {
         PRINT  s.pop() NIV is array[i];
   }
   s.push(array[i]);
}
while(!s.isEmpty())
   PRINT  s.pop() NIV is -1;

It is $O(n^2)$. Consider array = [n, n-1, n-2, ..., 1].

BTW, you could implement this in $O(n)$ by scanning from the end of the array:

Suppose the next-increasing-value (NIV) of a[i+1] is x.
We want to find the NIV of a[i], which we observe that:

If a[i+1] > a[i], then the NIV is a[i+1]
If x > a[i], then the NIV is x
Otherwise, a[i] is already the maximum value, so the NIV = -1.

Using this we could work backward from a[n-1] to a[0] to find the NIV of each entry in $O(n)$ time.


Proof that $\{0|1\}^*0\{0|1\}^n$ requires at least $2^{n+1}$ states How can you prove that any DFA accepting the language generated by the regular expression $\{0|1\}^*0\{0|1\}^n$ requires at least $2^{n+1}$ states?
I first attempted induction on $n$.  But I don't even see how to prove the base-case, like if $n=1$.  You need the DFA to take any string and, when it encounters a 0, get set down a track of checking that $n$ characters follow.  If it's fewer than $n$ then fine you reject.  But if there are more characters, to sort of re-set it so that it looks for the first 0 after the earlier one was found.  But DFAs don't have that kind of memory.
And once you've established the base-case, the inductive case doesn't seem clear either.  If you know the result is true up to $n$, then if you consider the regex with $n+1$ then you get a DFA which accepts it.  You intuitively want to remove the accepting states and "move them back" one vertex in the graph.  Now you have a DFA with at least $2^n$ states.  But how do you know that you needed $2^n$ accepting states so that the net number of accepting states is then $2^{n+1}$?

This isn't about induction, it's about proving that the correct DFA must have enough memory to remember everything about the last $n+1$ characters. The very number $2^{n+1}$ should have been a clue to this.
Imagine that the DFA has just now read some prefix that's longer than $n+1$, but it doesn't yet know if there are any more characters left. Ask the question: what must the DFA currently remember?

Well, clearly, it must remember what it read $n$ characters ago, to decide whether to accept or reject if the string just ends right now
It also must remember what was $n-1$ characters ago, just in case the string ends 1 character later
And it must remember what was $n-2$ characters ago, just in case the string ends 2 characters later
And it must remember what was $n-3$ ...

As you can see, by that kind of logic it must be absolutely sure about each of $2^{n+1}$ bits. To formalize this deduction, try to prove the following:
LEMMA: If $a$ and $b$ are two different strings of length $n+1$, then they should lead the DFA in question to two different states.
The method for proving this lemma is to append things to $a$ and $b$, such that, for example, string $ac$ must be accepted and string $bc$ must be rejected. If the automaton knows the difference between $ac$ and $bc$, then it must have known the difference between $a$ and $b$. Look up "right invariant equivalence" if you don't already know that concept.
Once you prove the lemma, the rest is obvious. There are $2^{n+1}$ different strings which all lead to different states. Therefore, there are at least $2^{n+1}$ different states.


If x operations cost O(x) amortized then how much xy operations cost? True or False?

Say some data structure can perform $x$ operations in amortized $O(x)$ time.
Then for a big enough $y$ it can perform $xy$ operations in worst case $O(xy)$ time.

My attempt:

$x$ operations in $O(x)$ amortized means $O(1)$ expected time for $1$ operation.
Then for $xy$ operations it'd be $O(xy)$ amortized (and I think $O(x^2y)$ worst case). Therefore, the statement is incorrect.

But the answers sheet says i'm wrong. Why?

Amortized is not just probabilistic, it means that for some big enough $y$,  $xy$ operations can't take a long time and will guaranteed to be $O(x)$ in average in worst case (and therefore $O(xy)$ for all $xy$ operations), even through some of operations may take even $O(xy)$ time itself.

https://stackoverflow.com/questions/200384/constant-amortized-time


Determining whether a digital circuit is optimal Are there any techniques that can be used to determine whether a digital logic circuit is optimal, or if it has extraneous operations that don't contribute to the output?

I'm especially curious in the case where the circuit is defined in terms of XOR and AND gates.

I know I could make a karnaugh map and create a circuit from that, but that doesn't really tell me about the circuit I had, it just gives me another circuit.

Thanks for any info!

Use one of the standard techniques for circuit minimization.  As far as I know, verifying that a candidate circuit is minimal is as hard as finding the minimal circuit in the first place (I know of no faster algorithm for verifying minimality than finding a minimal circuit in the first place).

Circuit minimzation is NP-hard (in fact it's even harder than that, in some sense), so you shouldn't expect an efficient algorithm for it that handles all functions efficiently.


Why does existence of predecessor imply adequacy of a numeral system? I encountered this result when working with $\lambda$-calculus (so every element I mention here was a $\lambda$-expression there [1]), but I will express everything with, more understandable to broader audience, notions of functions.

Intro

Definition 1
A numeral system is a sequence $d = d_0,d_1,\ldots$ such that there exist functions $S$ (successor) and $isZ$ (test for zero) such that
$$S(d_n) = d_{n+1},$$
$$isZ(d_0) = T,\ \ isZ(d_{n+1}) = F.$$
where $T$ and $F$ are notions of true and false.

Definition 2
A numeric function $\varphi : \mathbb{N}^p \to \mathbb{N}$ is definable with respect to $d$ if there exists $f$ such that
$$\forall (n_1,\ldots,n_p)\in \mathbb{N}^p\ \ f(d_{n_1},\ldots,d_{n_p}) = d_{\varphi(n_1,\ldots,n_p)}.$$

Definition 3
A numeral system $d$ is adequate if and only if all partial recursive functions are definable with respect to $d$.

My question (intro)

Proposition 1 (Proposition 6.4.3 in [1])
Let $d$ be a numeral system. $d$ is adequate if and only if there exists $P$ (predecessor) such that
$$\forall n \in \mathbb{N}\ \ P(d_{n+1}) = d_n.$$

For the $\Rightarrow$ direction, it is sufficient to observe that predecessor is a partial recursive function. Specifically, it is a primitive recursion of zero function and first coordinate projection.

My question
How would one prove a $\Leftarrow$ direction? How is it even possible to have such a powerful result, that existence of one function leads to definability of all partial recursive functions?

[1] Hendrik Pieter Barendregt, The Lambda Calculus, 1984.

Recall that the set of partial recursive functions $\mathcal{R}$ is defined inductively by the following rules:

(zero) $\dfrac{}{\zeta : n \mapsto 0 \in \mathcal{R}}$
(successor) $\dfrac{}{\sigma : n \mapsto n + 1 \in \mathcal{R}}$
(projection) $\dfrac{}{\Pi_m^i : (n_1, \cdots n_m) \mapsto n_i \in \mathcal{R}}$
(composition) $\dfrac{\chi : \mathbb{N}^m \to \mathbb{N}, \psi_i : \mathbb{N}^k \to \mathbb{N} \in \mathcal{R} }{\phi : (n_1, \cdots n_k) \mapsto \chi(\psi_1(n_1, \cdots, n_k), \cdots \psi_m(n_1, \cdots, n_k)) \in \mathcal{R}}$
(primitive recursion) $\dfrac{\chi : \mathbb{N}^m \to \mathbb{N}, \psi : \mathbb{N}^{n+2} \to \mathbb{N} \in \mathcal{R} }{\phi : (k,n_1, \cdots n_m) \mapsto \begin{cases}
      \chi(n_1, \cdots n_m) & \text{ if } k=0 \\
       \psi(\phi(k-1, n_1, \cdots, n_m),k-1, n_1 \cdots n_m ) & \text{ if } k > 0\\
   \end{cases}  \in \mathcal{R}}$
(minimalization) $\dfrac{\chi : \mathbb{N}^{m+1} \to \mathbb{N} \in \mathcal{R} }{\phi : (n_1, \cdots n_m) \mapsto k \text{, the least integer with } \chi(k,n_1, \cdots n_m) =0
   \in \mathcal{R}}$

So we will prove the result by structural induction on $\mathcal{R}$.

Initial functions.

It is clear that $\zeta$ is defined by $\lambda x. d_0$, $\sigma$ by $S$, and $\Pi_m^i$ by $\lambda x_1 \cdots x_m . x_i$.

Composition

Suppose $\chi$ is defined by $f$ and $\psi_i$ by $g_i$.

Let $h$ be the term $\lambda x_1 \cdots x_k.f (g_1x_1 \cdots x_k) \cdots (g_mx_1 \cdots x_k)$. Then $h$ defines the function $\phi : (n_1, \cdots n_k) \mapsto \chi(\psi_1(\vec{n}), \cdots \psi_m(\vec{n}))$

Primitive recursion.

Suppose $\chi$ is defined by $f$ and $\psi$ by $g$.

Let's define the combinator $\textbf{r} = \lambda nfg.isZ\:n\:f\:(g \:(P\:n))$, with the property that:

$$
\textbf{r} \: d_n \:f \: g = \begin{cases} f & \text{ if } n = 0 \\
g \: (d_{n-1}) & \text{ if } n > 0
\end{cases}
$$

Now let $h$ be the term $\textbf{y} \: (\lambda s y x_1 \cdots x_m . \textbf{r} \: y(f x_1\cdots x_m)(\lambda z.g (s z x_1 \cdots x_m)z x_1 \cdots x_m )$. Then $h$ defines $\phi: (k,n_1, \cdots n_m) \mapsto \begin{cases}
      \chi(n_1, \cdots n_m) & \text{ if } k=0 \\
       \psi(\phi(k-1, n_1, \cdots, n_m),k-1, n_1 \cdots n_m ) & \text{ if } k > 0\\
   \end{cases}$.

Minimalization

Suppose $\chi$ is defined by $f.

Let $g$ be the term $\textbf{y} (\lambda syx_1 \cdots x_m.isZ \: (f\: y\: x_1\cdots x_m) \: y\:  (s\: (S \: y)\:  x_1 \cdots x_m))$. Then take $h$ to be the term $g \: d_0$, and $h$ defines the function $\phi : (n_1, \cdots n_m) \mapsto k \text{, the least integer with } \chi(k,n_1, \cdots n_m) =0$.

By induction, every function in $\mathcal{R}$ is definable.

(I leave the proving the fact that the terms $h$ define the stated functions as an exercise!)


Is the set of codes of Deterministic Finite-State Automata a regular language? Let $\Sigma$ be a given alphabet. Is there a way to code up Deterministic Finite state Automata (DFA) over $\Sigma$ as strings of $\Sigma$ in such a way that the corresponding subset of $\Sigma^*$ is a regular language?

For example for Turing machines, the set of codes of Turing machines over a fixed alphabet is decidable, and we can speak of decidable sets of Turing machines (through their codes).

Of course we can also speak of regular sets of DFA's (through their codes). Is the set of all DFA's regular in this sense?

This answer is, in a sense, a completely cheating approach, but it is indeed possible to encode all DFAs as strings.

We can write out a DFA by writing out its transition table.  We can write out the transition table using just 0s and 1s as follows: first, write out a number of 1s equal to the number of states, then a 0.  Then, write out a number of 1s equal to the number of symbols in the alphabet, then a zero.  Then, write out each row of the transition table by writing out each entry as a number of 1s indicating which state should be transitioned into, then a 1.

Now, this particular encoding of a DFA is not regular.  However, what we can do is the following.  Consider the set of all such encodings.  We can then order them in length-lex order, and then can number the DFAs produced this way 0, 1, 2, 3, 4, ..., etc. based on their ordering.  In this case, we now have a bijection between $\mathbb{N}$ and the set of all DFAs.  From there, we can then consider the regular language consisting of all natural numbers written out in binary.  This set is definitely regular; here's a regular expression for it:

  0 | 1(0|1)*

So we now have a regular language consisting of encodings of DFAs.  The encoding is not at all easy to work with - you'd have to start listing off all encodings of DFAs until you found the one you were looking for - but mathematically it is well-defined.


Why is there no two-bit data type? Why do most programming languages (if not all) lack a 2-bit data type?

A boolean is a single bit with the values being either true or false.

Why is there no native, corresponding type where the values can be either true, false, neither or both? This data type can of course be constructed inside the language, but I figure there would be lots of usages for a more fundamental language support for it.

This data type would be very handy in, for instance:

gene programming (values being: A, C, G or T)
GUI programming (a checkbox that is: not checkable, unchecked, checked, or both/unknown)
testing (test result can be: not run, pass, fail or inconclusive)
quantum programming (values being: true, false, neither or both)

Is there a scientific reason to why this data type (quad, qool, qit etc.) has been excluded?

Like Geier said, processors can't directly handle values smaller than a byte.  So a boolean type that was actually implemented as just a single bit would in most cases be inefficient.  The processor needs to do a bit of extra work to extract just that one bit.

The reason that the boolean type exists is more about semantics than anything else.  Logical true/false values is a very useful concept.  In many programming languages a conditional expression like "if x is 5" has a boolean value as the result.  And lets not forget that a boolean type corresponds nicely to a single bit, which is the building block of the binary numbers that computers work with.

There has been tri-state "booleans" in use, and there probably still is today.  But they are generally less useful and more complicated to deal with than the ordinary true/false ones.

What you are talking about would generally be implemented as bit flags (or bit fields), or simply by assigning different meanings to different numbers.


Context free grammar for $A \circ B$ If A and B are regular language, what is a context free grammar of the following language?
$$
A \circ B = \{ xy \mid x \in A \text{ and } y \in B \text{ and } |x|=|y| \}
$$

Suppose that DFA for $A$ and $B$ are $D_A$ and $D_B$ respectively.
We will construct a PushDown Automata (PDA) for the given language $A \cdot B$ by combining $D_A$ and $D_B$ in a particular manner.
Modify the transitions of $D_A$ such that on reading any letter it pushes a symbol $X$ on the stack. Join all the final states of $D_A$ to the initial state of $D_B$ with epsilon transitions. Modify all the transitions of $D_B$ to Pop $X$ from the stack. Accepting condition will be that on reading a word we should reach one of the final state of $D_B$ and the stack should be empty.
It will be quite easy for you to convince yourself that this will accept the language $A \cdot B$ as required. Now, we can apply the standard method to convert the PDA to grammar to get the required grammar.


Confused about constructing the "failure table" in Knuth-Morris-Pratt algorithm I'm trying to learn how the "failure table" is constructed in the Knuth-Morris-Pratt algorithm since it seemed nontrivial to me that you could do it in $O(k)$ time (where $k$ is the length of the pattern, $W$). To be clear, we let the failure table $T$ be a length $k$ array where $T[i]$ is the length of the longest proper prefix of $W$ which is also a suffix of $W[1]\cdots W[i]$.

I was trying to understand it better by reading the following code:

    vector<int> T(pattern.size());
    T[0] = 0;
    int j;
    for (int i = 1; i < pattern.size(); i++) {
        j = T[i - 1];
        // Find largest j s.t. T[:j+1] == T[i-j:i+1]
        while (j > 0 && pattern[j] != pattern[i]) {
            j = T[j - 1];
        }
        T[i] = (pattern[j] == pattern[i]) ? j + 1 : j;
    }
    return T;

The part I'm confused about is why pattern[j] == pattern[i] is enough to guarantee that $T[i] = j + 1$. I was trying to prove this inductively but have had no luck. I've phrased the problem as follows:

Suppose $W[1]\cdots W[T[i - 1]] = W[i - T[i - 1]]\cdots W[i - 1]$. If $W[i] == W[j]$, then is it true that $W[1]\cdots W[j] == W[i - j + 1]\cdots W[i]$?

I can't make any headway with this, nor can I see why it should be true. It still seems like we have to check $W[\ell] = W[i - j + \ell]$ for all $\ell = 1...j$. I can't figure out how to use the inductive hypothesis to prove this result. Do I have to use strong induction (where we assume all prior steps are true and not just the previous step) to prove this?

A proper prefix, which is also a suffix of the same string, is usually called border.

The condition you're asking about basically says this:

If $W[1..i-1]$ has a border of length $j$ and $W[j+1] = W[i]$, then $W[1..i]$ has a border of length $j+1$.
If $W[1..i-1]$ has no border of length $j$ such that $W[j+1] = W[i]$, then the length of the maximal border of $W[1..i]$ is $0$.

Both points follow directly from definition of string equality and definition of borders.

What you need to prove is that the while-loop indeed enumerates all possible borders in descending order.


How do you say when a language is Turing-complete only in a trivial way? I didn't know how to ask this question before but now that I'm reading about typed lambda calculus I think I've got a better idea.

There is this answer to a question asking whether CSS is Turing complete or not (note that this question is NOT about CSS at all), which I consider is not (at least in certain way, and this "certain" is what my question below is about), even if you can simulate Rule 110 with it, which is proven to be Turing complete. My intuition behind it is that only an insignificant subset of what CSS can output can be the result of a calculation. You cannot perform any calculation on colors or sizes to be set to element's styles.

Now I found an even simpler example while reading about typed lambda calculus. This article's overview describes a lambda calculus that can use booleans. I noticed that, in addition to the untyped lambda calculus operations, there is the conditional operation (if t1 then t2 else t3), which makes perfect sense. Without this, you wouldn't be able to do anything with booleans, and I would go ahead and say is really not Turing complete, or at least that is Turing complete but only in a trivial way.

So my question is, if this typed lambda calculus with booleans wouldn't have that conditional operator, would you say is Turing complete? If not, why not, and if yes, how would you express the fact that you cannot do any operation at all on it's main type of data which is what you'd expect from any Turing complete language in a categorical, technical way such that is clear that the Turing completeness of the language is really meaningless?

The reason why I'm giving so much importance to this is because I was recently trying to create a small Turing complete language myself and while doing it, got to a point in which my language was Turing complete but only in this trivial way (wasn't as obvious as the boolean lambda calculus without conditionals above, though). If I would have asked "Is this language Turing complete?" I would have probably got "Yes" as an answer and I would've think I'm done creating my language. But I really was not. And when asking myself why am I still working on my language, I'd like to be able to state exactly what is that my language is missing.

Untyped or simply-typed lambda-calculus is Turing-complete even with no booleans at all. Adding more stuff in the language, such as boolean constants and a boolean base types, cannot make the language less powerful, therefore it is still Turing-complete.

“Turing-complete” means that there is some “reasonable encoding” under which the language can express arbitrary computations. “Reasonable encoding” is not a formal notion; what it really means is that you must say what you consider to be computation, and how natural integers are to be encoded. For example, in the lambda-calculus, computation is beta reduction, and one possible encoding of natural integers is Church numerals.

In the simply-typed lambda calculs, there are no booleans as a built-in notion, but they can be encoded:
$$\begin{align}
  \mathsf{true}_\tau &:= \lambda x\colon\tau. \lambda y\colon\tau. x \\
  \mathsf{false}_\tau &:= \lambda x\colon\tau. \lambda y\colon\tau. x \\
  \mathsf{ifthenelse}_\tau &:= \lambda f\colon\tau. \lambda g\colon\tau. \lambda b\colon(\tau\rightarrow\tau\rightarrow\tau). b \, f \, g \\
\end{align}$$

The lambda calculus with boolean constants but no corresponding destructor¹ nor any way to encode it (such as a polymorphic equality construct) does lack expressive power in a sense, but only in that it is unable to distinguish between the two boolean values. It isn't the language's computational power which is at state, but the particular encoding of booleans as the boolean constants you picked: the boolean data structure is not implemented correctly. In fact, that language does not have any boolean data structures: it has constants that you chose to call “true” and “false”, but that doesn't make them booleans given the lack of a destructor.

Consider a variant where you define the following constructors and destructor:
$$
  \dfrac{}{\Gamma \vdash \mathsf{dog} : \mathsf{daisy}} \qquad
  \dfrac{}{\Gamma \vdash \mathsf{cat} : \mathsf{daisy}} \qquad
  \dfrac{\Gamma \vdash M : \mathsf{daisy} \quad \Gamma \vdash N_0 : \tau \quad \Gamma \vdash N_1 : \tau}{\Gamma \vdash \mathsf{cheese}(M, N_0, N_1) : \tau} \\
  \dfrac{}{\Gamma \vdash \mathsf{true} : \mathsf{boolean}} \qquad
  \dfrac{}{\Gamma \vdash \mathsf{false} : \mathsf{boolean}}
$$
and the following reduction rules:
$$\begin{align}
  \mathsf{cheese}(\mathsf{dog},M,N) &\to M \\
  \mathsf{cheese}(\mathsf{cat},M,N) &\to N \\
\end{align}$$

This language has an encoding of the booleans as the type $\mathsf{daisy}$, with $\mathsf{cat}$ and $\mathsf{dog}$ as the constructors and $\mathsf{cheese}$ as the destructor. The type $\mathsf{boolean}$ is not a boolean type: it's just some type that happens to have two values (which are undistinguishable).

A “typed lambda calculus with booleans [without] that conditional operator” is a Turing-complete language that doesn't have booleans.

¹  A destructor in a typed calculus is a term such that a type constructor appears in the premises of its typing rules but not in the type of its conclusion. If/then/else is a destructor for booleans.


Union of R.E. and Non R.E. language Let
\begin{align*}
    L_1 &=\{\langle M,w\rangle \mid M\text{ halts on }w\}\\
    L_2 &=\{\langle M,w\rangle \mid M\text{ does not halt on }w\}\,.
\end{align*}
Here $M$ represents encoding of a Turing machine (T.M.) and $w$ is the input string. What is the class of $L=L_1 \cup L_2$?

I read that the union would be a regular language as a string has to belong to either $L_1$ or $L_2$ (i.e., halt or not halt) so their union would be a regular language.

I have a doubt. Suppose we assume $L$ as a recursively enumerable (R.E.) language then there exists a T.M. which halts on all "yes" cases. Here yes cases means strings which belong to either $L_1$ or $L_2$.
So, if a string belongs to $L_2$, then the T.M. should halt which means that we are able to halt and say "yes" even if machine doesn't halt on this string (according to condition of $L_2$). This solves halting problem and hence assumption is not correct and so $L$ should be non recursively enumerable.

I know that there is some flaw in the explanation given above but I am not able to find it.

Can someone please help me?

The language $L = L_1 \cup L_2$ consists of all pairs $\langle M,w \rangle$ where $M$ is a description of a Turing machine and $w$ is a word. This language is not necessarily regular (it depends on the exact encoding), but it is certainly decidable. All you have to do, given an input, is to decide whether it is of the form $\langle M,w \rangle$.

Note that deciding $L$ bears no relation to the halting problem. My description of $L$ doesn't refer to whether $M$ halts on $w$ or not. Here is a similar example. Let $f$ be an uncomputable integer-valued function. The function $g := 1-f$ is uncomputable as well, yet $f + g$ is computable.


How does Gradient Descent treat multiple features? As far as I know, when you reach the step, in a gradient descent algorithm, to calculate step_size, you calculate learning_rate * slope
Now, slope is obtained by calculating the derivative of the cost_function with respect to the feature you want to find the optimal coefficient for.
Let's say that the cost function for the purposes of this question is the sum of squared residuals.
My question is, how are coefficients of other features treated in the differentiation of the equation? For instance, if I have the equation $y = b_0 + x_1 + x_2$, then by calculating the derivative of the cost function with respect to $x_1$, one gets:
$\frac{d}{d\left(x_1\right)}\left(\left(\hat{y}\:-\:\left(b_0\:+\:x_1+x_2\right)\right)^2\right) =$
$2\times\:\left(\hat{y}\:-\:b_{0\:}-x_1-x_2\right)\left(\frac{d}{d\left(x_1\right)}(x_2)\:+\:1\right)$
In this case, how is a value obtained by substituting a value for $x_1$ while $\frac{d}{d(x_1)}(x_2)$ is still in the formula?
I watched a YouTube video (it starts at the right point) that says that  $x_2$ is a constant (while it's a different feature) and, therefore, when differentiating, $\frac{d}{d(x_1)}(x_2)$ is omitted and we are left with $2\times \:\left(\hat{y}\:-\:b_{0\:}-x_1-x_2\right)(1)$. Is this the case or am I missing something?

That's correct.  The derivative of $x_2$ with respect to $x_1$ is 0.
A little context: with words like derivative and slope, you are describing how gradient descent works in one dimension (with only one feature / one value to optimize).  In multiple dimensions (multiple features / multiple variables you are trying to optimize), we use the gradient and update all of the variables in each step.  That said, yes, this is basically equivalent to separately updating each variable in the one-dimensional way that you describe.


Is my grammar correct and context free? I have this language

$L = \{a^{n}b^{3n}c^{2m} : m,n \ge 1\}$.

I have to determine a free context grammar that generates L.
Looks easy BUT i have a question about the grammar I found.
First things first, this is my grammar:

$S \Rightarrow BC$

$ B \Rightarrow aBbbb\ \backslash \ abbb $

$ C \Rightarrow Ccc \ \backslash \ cc$

Looks easy and clean to me. I already tested it with strings of different lengths and seems working just fine. Also it does indeed create only strings contained in L and no other strings.

My question is:

This is the first time I generate a grammar without any production containing $S$ itself (An example would be adding $S \Rightarrow B$ and I would solve my problem, because B generates only $a$'s and $b$'s and the number of this chars is dipendent between one another but indipendent with the number of $c$'s inside the string).

Recursively speaking, this works just fine but using $S$ would induce me to create a noncontracting language (because I'd be forced to invert some Non Terminals in order to produce both $a$'s and $b$'s correctly if something is wrong in my grammar).
Is this way of creating grammars correct? Can I describe what I wrote as an actual "grammar"? Is it context free?

Also, can I actually derivate $a$ through $B$ without a nonterminal $A$ and without generating it with the $S$ production?

Your context-free grammar is just fine.  It is not actually necessary for the grammar to have a production with $S$ in its right-hand side.  In fact, a context-free grammar need not have any recursive productions or mutually-recursive productions, though the generated language in that case may be quite limited.  It is also not necessary to use any particular names for your nonterminals (e.g there is no need for $A$ to appear anywhere).


Loop invariant condition IsPrime program I'm new to the concept of loop invariant and I'm trying to figure out the loop invariant for a program that returns if an integer is prime and, if not, one possible factorization.
My intuition is that as a loop invariant condition we need i in the range [2,floor(sqrt(n))] and then n mod i !=0 implies n is prime

bool IsPrime(int n)
{
    if (n == 1) return false;
    if (n == 2) return true;

    //if n (>2) is prime, it's prime factor is just n
    //if n (>2) is not prime, n=a*b, where both a,b<n and we have either a<sqrt(n) or b<sqrt(n)
    var bound = (int)Math.Floor(Math.Sqrt(n));

    //invariant: 2<=i<=bound and n mod i=0
    int i = 2;
    while (i<=bound)
    {
        //if n is divisible by some integer smaller than the upper bound it is not prime
        if (n % i == 0)
        {
            Console.WriteLine(" " + n/i);
            Console.WriteLine("x" + i);
            return false;
        }
        i+=1;
    }
    return true;
}

Could you please tell me if that is enough? I already made many attempts and that's the only statement that holds true for the whole loop until i=floor(sqrt(n)).

The condition $2 \leq i \leq \lfloor \sqrt{n} \rfloor$ is a reasonable part of the invariant you seek. As I think you realize, this is not enough.

You proposed to also require $n \!\!\!\mod i \neq 0 \implies n$ prime, but this can not realistically hold. For instance, take $n=3^2=9$: running the loop we would start from $i=2$ and have $n \!\!\!\mod i = 1 \neq 0$ but clearly $n=9$ is not prime, which makes the condition false. Hence, that is not really an invariant.

What we need is something expressing "we checked all the numbers from $2$ to $i-1$, and we did not find any divisors". This can be written as "for all the numbers $k$ such that $2\leq k < i$, we have $k\!\! \mod n \neq 0$".

That might be enough, but the loop seems to have a bug to me: for e.g. $n=5^2$ we never try to divide for $i=5$, consequently returning that $25$ is prime. Perhaps you should fix the bug first, and then adapt the first "range" invariant accordingly.


VC dimensions: Let ${x_1, \ldots, x_N}$ be $N$ labelled points on $\mathbb{R}$, then there exists a sinusoid that separates these points (Proposition, pg 26): Let ${x_1, \ldots, x_N}$ be $N$ points on $\mathbb{R}$, $N \in \mathbb{Z}$, labelled either $+1$ or $-1$ , then there exists a function from the set $\{t \mapsto \sin(\omega t)| \omega \in \mathbb{R}\}$ that separates these points into two sets, one with all labels ${+1}$, and one with all labels ${-1}$

Does anyone see how to prove this proposition?
Right now I am using induction, however, I cannot see how it can extend to the $N$ point case.
It is also difficult to picture how this works for the $N$ point case.

Here are some ideas. Denote by $\{x\}$ the fractional value of $x$, and consider the function $f_n(x) = \operatorname{sgn} (\sin 2\pi n x)$. Then:

$f_n(x) = +1$ iff $\{nx\} \in (0,1/2)$.
$f_n(x) = -1$ iff $\{nx\} \in (1/2,1)$.

Suppose first that the set of points is independent over the rationals. Weyl's equidistribution theorem shows that $\{nx_1\},\ldots,\{nx_N\}$ is equidistributed over $[0,1)^N$, and in particular we can find $n$ for which $\{nx_i\}$ matches the label of $i$.

Another case is $x_i = 2^{-i}$. This case is often used to show that the collection $\{ f_n : n \in \mathbb{N} \}$ has infinite VC dimension. In this case we choose $n$ so that its binary expansion corresponds to the labels of the set (details left to the reader, or see Example 3 on page 4 of these lecture notes). Using Weyl's equidistribution theorem, we can generalize this to the case $x_i = 2^{-i} x_0$ for arbitrary $x_0$.

I see two possible arguments for the general case:

Perturb the $x_i$s slightly to new values $y_i$ that they are rationally independent, and apply the argument above. Intuitively, if the perturbation is small enough then $\{nx_i\} \approx \{ny_i\}$ and by asking that $\{nx_i\}$ be in (say) $(1/6,1/3)$ or $(2/3,5/6)$, we can guarantee that $f_n(x_i) = f_n(y_i)$. The difficulty with this argument is that the perturbation needs to be small as a function of $n$, and we don't know $n$ in advance, barring some uniform version of the equidistribution theorem.
Choose a basis $r_1,\ldots,r_m$ for $x_1,\ldots,x_N$ over the rationals such that each $x_i$ is an integer combination of the $r_j$, and then try to apply an argument similar to that of the second case. If $m=1$ then this argument seems convincing (though details need to be checked), but the general case seems a bit more difficult.

For an interesting strengthening of the rationally independent case, see this nice paper.


Metagame Paradox: what is wrong with this explanation? Today I've heard about fascinating metagame paradox. I tried to come up with an explanation via Turing Machines formalization (below). Do you know what is the solution to the paradox? (the post content: definition - proposed solution - conclusion)

Something is a game iff:

G1. Two players
G2. Players alternate
G3. The game finally ends.

The metagame is:

M1. First player picks a game
M2. Second player starts the game
M3. The winner is the winner of the game at step 2.

Example of a metagame:

1) I pick tic-tac-toe
2) OK, I put X here ..
.. so they play ..
3) .. and let player 2 wins in the tic-tac-toe => player 2 wins the metagame.

Paradox: Is metagame a game?

If metagame is a game, then at point (M1) both players can always pick a metagame, so the metagame will never end => (G3) is violated => metagame is not a game => contradiction.

(also contradiction for case "metagame is not a game" -- metagame will satisfy the definition of a game)

(see also http://www.math.cornell.edu/~mec/2006-2007/Games/hypergame.html)

What is the solution to the paradox?

UPDATE: You may want to skip this explanation and go directly to D.W. answer.

I came up with the following explanation:

Lets formalize the problem using Turing Machines notations.
Let a game be a finite binary string that describes "somehow" game rules. Let a game simulator be a non-deterministic TM that reads a description from the input (without any sanity checks, so the TM doesn't know if the game finally ends), and then makes non-deterministic moves for the first and second player. Here we assume (A1) that the game-simulator can decide valid next moves.

Now have a look at the description of a meta-game:

M1. First player picks a game

This sentence means that we can "pick a game", i.e. in the definition we assume (A2) that whether an arbitrarily binary string is a game (satisfies G1,G2,G3) is decidable. (see also note (n1) )

M2 and M3 look decidable.

So, my suggestion is that metagame is not "defined properly", since its definition assumes the existence of a decider "if a given binary string is a game". And then we derive a contradiction, so this assumption is wrong.

Does it make sense? Is this related with other explanations of the paradox?
(intuitive answers would be great!)

Notes:

Assuming "whether an arbitrarily binary string is a game" may be too much. But we need some computable procedure "pick a game" and one that came into mind is "generate random string, check if it is a game".
I don't know what is a formal word for "not defined properly"
Assumption A1 may also be undecidable, but I believe it should not change the argument..

The flaw is that your definition of "game" is deficient and does not correspond to our intuition.  We also need a restriction on the number of moves that are possible at any position in the game.   It doesn't really have anything to do about computability, so much as about the notion of what it means for a game to be finite.

Usually we define a game as something where at each step there are only finitely many moves that can be played, and where the game is guaranteed to end after finitely many moves (there is no infinite sequence of moves in the game).  You forgot to specify the "at each position, there are only finitely many moves possible from that position" in your definition of a game.

If you add that to the definition, then you'll find that the metagame does not meet the definition: the metagame is not a game.  In particular, there are infinitely many possible games, so at the beginning of your metagame, there are infinitely many possible moves -- thus the metagame does not qualify as a game.  There is no paradox.

You could have an alternative definition of a game where you say that at each step the number of moves is either finite or countably infinite.  This is a bit different from what our intuition would suggest, but let's explore the consequences of defining a game this way.

In particular, the set of all games would now be uncountably infinite.

As a result, the metagame is still not a game: at the beginning of your metagame, there are uncountably infinitely many possible moves -- so does not qualify as a game.

In particular, "pick a game" is not meaningful: Player 1 has to select a game and describe it to Player 2, but there are uncountably infinitely many possible games, so Player 1 cannot describe his choice in any finite amount of time.  In particular, you cannot specify a game with a finite string (more precisely: no matter what candidate encoding of games you come up with, there will exist some games that cannot be specified by any finite string).  The description of the game is an infinite-length string.

If you like to think of it intuitively: in this case it wouldn't really be fair to think of the metagame as "finite" (even though it only lasts for a finite number of moves, if the first move takes infinitely long to complete, the metagame cannot be considered finite).

In any case, if you define a game this way, there is still no paradox.

(Why is the set of games uncountably infinite, if this is how we defined a game?  Well, I'll show an injective map $f$ that maps from a real number $x \in [0,1]$ to a game $G_x$.  In the first move of $G_x$, player 1 chooses a natural number $n \in \mathbb{N}$.  After that, there are $n$ more moves, then the game ends.  At the $i+1$th move (for $1 \le i \le n$), there are $x_i$ different moves available to the player whose turn it is to move, where $x_i$ denotes the $i$th digit after the decimal point in the decimal expansion of $x$.  Notice that $G_x$ qualifies as a game: there are two players, the players alternate, there are finitely or countably infinitely many moves at each possible position of the game, and the game is guaranteed to end after finitely many steps -- there is no infinite sequence of valid moves.  But the set $[0,1]$ of real numbers is uncountably infinite, and we have an injective map from an uncountably infinite set to a subset of the set of games.  Therefore, the set of all games is uncountably infinite, under this definition.)

Finally, the last alternative would be to define "game" so there is no restriction on the number of possible moves at each position.

However, this definition of a "game" would no longer correspond to our usual intuition for what a game should involve.  In particular, it may not be possible for a player to describe his/her move to the other player in any finite amount of time (since he/she may be choosing from among uncountably infinitely many possibilities).  That just ain't right.  In particular, such a process can't reasonably be considered finite: it would not complete in any finite amount of time.

Intuitively, why does it make sense that our definition of game ought to restrict the number of possible moves at each position to be finite, or at most countably infinite?  Because we need the player to be able to select a move and describe it to the other player.  If there is no finite encoding of the set of possible moves (at a given position), then the player whose turn it is to move has no way to describe the move he chose to his opponent.  If there is a finite encoding of the set of possible moves (at each possible position), then the number of possible moves must always be finite or countably infinite, by the definition of countability.


Number of levels in the recursion tree While solving Recurrences of type $T\left ( n \right ) = a\cdot T(\frac{n}{b})+c$ using the recursion tree method, number of levels in the recursion tree is equal to $\log_{b}n$ when $b$ is a constant.
But when $b$ is dependent on $n$, can we say that number of levels are still $\log_{b}n$?
For example, in
$T\left ( n \right ) = a\cdot T\left ( \frac{n}{\sqrt{n}} \right )+c$

Can we say that number of levels in the recursion tree are equal to $\log_{\sqrt{n}}n = 2$?
I guess this is wrong but I am unable to reason it properly, please explain me the reason "why this is wrong?"(If it really is).

If $b$ is not a constant, then no, you can't say the number of levels is still $\log_b n$.

In your example, we have $T(n) = a T(\sqrt{n}) + c$ (since $n/\sqrt{n} = \sqrt{n}$).  There are more than 2 levels in the recursion tree.  In fact, there are $\lg \lg n$ levels in the recursion tree.  So, no, you can't just compute $\lg_{\sqrt{n}} n = 2$ and conclude that there are 2 levels in the recursion tree -- that gives the wrong answer.

(Why $\lg n$?  Suppose $n=2^k$.  Then each level halves $k$, so we do a total of $\lg k$ levels we get down to a constant.  Since $k = \lg n$, we get a total of $\lg k = \lg \lg n$ levels.)

The Master theorem gives a formula for solving this kind of recurrence, but it's only valid when $b$ is a constant.


Graph searching: Breadth-first vs. depth-first When searching graphs, there are two easy algorithms: breadth-first and depth-first (Usually done by adding all adjactent graph nodes to a queue (breadth-first) or stack (depth-first)).

Now, are there any advantages of one over another?

The ones I could think of:

If you expect your data to be pretty far down inside the graph, depth-first might find it earlier, as you are going down into the deeper parts of the graph very fast.
Conversely, if you expect your data to be pretty far up in the graph, breadth-first might give the result earlier.

Is there anything I have missed or does it mostly come down to personal preference?

I'd like to quote an answer from Stack Overflow by hstoerr which covers the problem nicely:

  That heavily depends on the structure of the search tree and the number and location of solutions.
   If you know a solution is not far from the root of the tree, a breadth first search (BFS) might be better. If the tree is very deep and solutions are rare, depth first search (DFS) might rootle around forever, but BFS could be faster. If the tree is very wide, a BFS might need too much more memory, so it might be completely impractical. If solutions are frequent but located deep in the tree, BFS could be impractical. If the search tree is very deep you will need to restrict the search depth for depth first search (DFS), anyway (for example with iterative deepening).

  But these are just rules of thumb; you'll probably need to experiment.

Rafał Dowgird also remarks:

  Some algorithms depend on particular properties of DFS (or BFS) to work. For example the Hopcroft and Tarjan algorithm for finding 2-connected components takes advantage of the fact that each already visited node encountered by DFS is on the path from root to the currently explored node.


Merkle tree collision probability Say I use a perfect 128-bit hash function to construct a merkle tree.
By perfect I mean that any of the values in the $0$–$2^{128}$ range has an equal probability to be an outcome of the function, over a large enough domain of hashed entities.

Does the root have a higher collision probability than any of the leafs?

To elaborate, say that I have 1000 entities, each of which has a $p_1=1/2^{128}$ probability of colliding.
I construct the tree so that the lowest level spans the range of $2^8$ values, and upper levels span the range of two lower levels.

What is the probability of a single collision in such a tree?
What is the probability of two collisions in a single tree? $n$ collisions?

Yes, the root has a higher probability of collision.

Take, for example, simple trees with two leaves. Label tree 1's leaves $A$ and $B$, and tree 2's leaves $X$ and $Y$.

The probability that the tree hashes collide at the root is the probability that $\langle h(A),h(B) \rangle \neq \langle h(X),h(Y)\rangle \land h(h(A)||h(B)) = h(h(X)||h(Y))$ plus the probability that $\langle h(A),h(B) \rangle = \langle h(X),h(Y)\rangle$. The probability of the second part is $p^{-2}$ and the probability of the first is $p^{-1}(1-p^{-2})$, for a total of $p^{-1} + p^{-2} - p^{-3}$, which is slightly greater than $p^{-1}$, the probability of a single collision.

That assumes all of your leaves have different values. If the leaves are all the same but one, the probability of collision at the root is proportional to the logarithm (base 2) of the number of leaves times the collision probability of the underlying hash function.


Do any programming languages use general recursive functions as their basis? This is a naïve and, therefore, possibly malformed question, so apologies in advance!

My view is that a Turing Machine can be seen as the computational basis for procedural/imperative programming languages. Similarly, the lambda calculus is the foundation for functional programming languages.

I have recently learnt that the Church-Turing Thesis also shows mutual equivalence with a third model of computation: general recursive functions. Are there any programming languages that use this as their model of computation? If not, is there a technical reason why; i.e., besides "No one's tried yet"?

Direct answer to the question: yes, there are esoteric and highly impractical PLs based on $\mu$-recursive functions (think Whitespace), but no practical programming language is based on $\mu$-recursive functions due to valid reasons.

General recursive (i.e., $\mu$-recursive) functions are significantly less expressive than lambda calculi. Thus, they make a poor foundation for programming languages. You are also not correct that the TM is the basis of imperative PLs: in reality, good imperative programming languages are much closer to $\lambda$-calculus than they are to Turing machines.

In terms of computability, $\mu$-recursive functions, Turing machine, and the untyped $\lambda$-calculus are all equivalent. However, the untyped LC has good properties that none of the other two have. It is very simple (only 3 syntactic forms and 2 computational rules), is highly compositional, and can express programming constructs relatively easily. Moreover, equipped with a simple type system (e.g., System $F\omega$ extended with $\mathsf{fix}$), the $\lambda$-calculus can be extremely expressive in that it can express many complex programming constructs easily, correctly and compositionally. You can also extend the $\lambda$-calculus easily to include constructs that are not lambdas. None of the other computational models mentioned above give you those nice properties.

The Turing machine is neither compositional nor universal (you need to have a TM for each problem). There are no concepts of "functions", "variables" or "composition". It is also not exactly true that TMs are the basis of imperative PLs - FWIW, imperative PLs are much, much closer to lambda calculi with control operators than to Turing machines. See Peter J. Landin's "A Correspondence Between ALGOL 60 and Church's Lambda-Notation" for a detailed explanation. If you have programmed in Brainf**k (which actually implements a rather simple Turing machine), you will know that Turing machines are not a good idea for programming.

$\mu$-recursive functions are similar to TMs in this respect. They are compositional, but not nearly as compositional as the LC. You also just can't encode useful programming constructs in $\mu$-recursive functions. Moreover, the $\mu$-recursive functions only compute over $\mathbb{N}$, and to compute over anything else you'd need to encode your data into natural numbers using some sort of Gödel numbering, which is painful.

So, it is not a coincidence that most programming languages are somehow based off the $\lambda$-calculus! The $\lambda$-calculus has good properties: expressiveness, compositionality and extensibility, that other systems lack. However, Turing machines are good for studying computational complexity, and $\mu$-recursive functions are good for studying the logical notion of computability. They both have outstanding properties that the $\lambda$-calculus lacks, but in the field of programming $\lambda$-calculus clearly wins.

In fact, there are many, many more Turing complete systems out there, but they lack any outstanding property whatsoever. Conway's Game of Life, LaTeX macros, and even (some claim) DNA are all Turing complete, but no one programs (i.e. do serious programming) with Conway or studies computational complexity using LaTeX macros. They simply lack good properties. Turing complete per se is nearly meaningless when it comes to programming.

Also, many non-Turing complete computational systems are very useful when it comes to programming. Regular expressions and yacc are not Turing complete, but they are extremely powerful in solving a certain class of problems. Coq is also not Turing complete, but it is incredibly powerful (it's actually considered much more expressive than its Turing complete cousin, OCaml). When it comes to programming, Turing completeness is not the key, as many (close to) useless systems are uninterestingly Turing complete. You're not going to claim that Brainf**k or Whitespace are more powerful programming languages than Coq, are you? An expressive foundation is the key to powerful programming languages, and that's why modern programming languages are almost always based on the $\lambda$-calculus.


Performance impact due to time required for shuffling in Quicksort As a programmer with non CS background, I am learning algorithms.

When explaining the performance of quicksort in an Algorithm book and also elsewhere on the web, I do not see any reference to the time/space needed for shuffling. I do understand that shuffling is important to have the $O(n\log n)$ performance, but shuffling itself would have a complexity of $O(n)$. Why does this become irrelevant in the total performance?

The short answer is that the $O(n\log n)$ component dominates the $O(n)$ component, hence the $O(n)$ part can be ignored in the statement of complexity.


Converting non-deterministic algorithm to deterministic I was thinking about an non-deterministic algorithm to generate all the subsets of the $\{1..n\}$ set.

Subsets(n)
    S' = null
    for i = 1..n
        u = choice(1..n)
        if u in S'
           fail
        S' = S' + u
    for_each u in S'
         print u

How would I convert this algorithm into a deterministic form? I know that it is a lot more complicated to convert the choice statement in a deterministic manner but I want to get a general idea about maybe representing it in a deterministic manner.

Any finitely terminating non-deterministic algorithm can be made deterministic by using depth-first search on the tree of possible executions.

Or, to explain it another way: each time you have a non-deterministic choice, fork the program into multiple copies, one per possible choice.  Forking might be done by calling the operating system's fork() call (very expensive), or by capturing all the relevant state of the variables and storing it in a set of pending items to explore (potentially tedious to write the code), or by replacing the choice() with a recursive call that makes a copy of all of the relevant state (i, S') and iteratively tries each of the possible choices (easiest to implement in this case).

Here is an example of how to implement the latter transformation.  The state at the choice statement is the value of S' and i.  So, we do the following:

search(S', i, u):
    if u in S'
        return
    S' = S' + u   # this needs to copy the set, not update it destructively
    i = i + 1
    if i>n:
        for_each u in S'
            print u
    else:
        for u in [1,2,..,n]
            search(S', i, u)

Subsets(n):
    for u in [1,2,..,n]:
        search(emptyset, 1, u)

Notice how search contains all of the code after the choice statement, until the next choice statement.  We had to rip the for-loop over i apart to make this work, but the transformation was fairly mechanical.

This is a general method that can be used on any terminating non-deterministic algorithm -- not just this one.


Why register access bandwidth is higher then residing inside CPU cache? Access to registers claimed to be faster then cache. Why is it? Is it because cache has less wires or spatially further from functional units?

There are slower and faster technologies for memory. And there are technologies for creating bigger or smaller amounts of memory. Obviously a technology that creates slower and smaller memory is useless. So of the useful technologies, the fastest one will always provide the smallest amount of memory, and the ones providing the biggest amount of memory will be the smallest.

Register memory is smaller than cache, therefore it's faster. It has nothing to do with technology, it is a basic economic principle. If the technology used for cache was faster, it would be used for registers.


How does one find out whether $N = a^b$ for some $b$? I was trying to find out how to find whether $N$ is a perfect power or not for some $a$ and $b$ (so the algorithm should discover that its not a perfect power if its not expressable in the form  $a^b$).

My intuition tells me that for every value of the exponent $b$ we can binary search $a$ in the set $\{ 1,...,N-1 \}$. However, what I am not convinced yet is that this algorithm won't run forever, i.e. that we won't try new values of $b$ forever. Also, if someone has any comments on the correctness of the algorithm I suggested it would be greatly appreciated.

Yes, your approach is a good one.  The only thing you missed is that there's a simple upper bound $b \le \lg N$.

Do you see why?  It's easier to see why if you state more carefully the problem  you are trying to solve.  You are asking whether there exist $a,b \in \mathbb{N}$ such that $a \ge 2$, $b \ge 2$, and $a^b=N$.  Taking logs of both sides, we get $b \lg a = \lg N$.  From the fact that $a \ge 2$, we see $\lg a \ge 1$, so $b = (\lg N)/(\lg a) \le \lg N$.

Therefore, here is a simple algorithm:

For $b=2,3,\dots,\lg N$:

Use binary search to search for $a \in \mathbb{N}$ such that $a^b=N$.

Each iteration of the loop will take $O(\lg N)$ time (the time for a binary search over at most $N$ possibilities), and you do $\lg N$ iterations of the loop, so the total running time $O((\lg N)^2)$.

In particular, yes, this will always terminate.  You don't need to keep trying new values for $b$ forever, since we know that $b$ is an integer and is no larger than $\lg N$.

The running time of the algorithm can be improved a bit by replacing the binary search with a faster algorithm to compute $\sqrt[b]{N}$; for instance, you could use Newton's method.  But the basic method above is already very efficient.

You might be tempted to iterate over all possible values of $a$, and then do a binary search for $b$.  Don't do that; there are $\Theta(\sqrt{N})$ possible values of $a$, so this will be unavoidably slow.

Instead, a better approach is to iterate over all possible values of $b$, and then do a binary search for a matching $a$.  This is much faster, as it needs only $\Theta(\lg N)$ binary searches rather than $\Theta(\sqrt{N})$ of them.

One person mentioned factoring $N$.  This is much slower.  Our best algorithms for factoring run in subexponential time; they are much slower than the $\Theta((\lg N)^2)$ running time of the algorithm above.


Smallest possible DFA for a language over {0,1}* with third to last symbol 1 should have 4 states not 8. Where am I going wrong in my DFA? So I was reading Micheal Sipser's Introduction to TOC and when I stumbled upon this aforementioned question , he'd the following dfa :

Now, I came up with a much better DFA with only 4 states :

I read in another thread that the minimum number of states for a DFA for this language is 8. But , I came up with 4.

Where am I going wrong ?
(I tried testing this DFA with a plethora of input strings , seems ok to me)

Try inputting 1100 to your DFA. You get to $q_1$, a non-accepting state.

We can show that 8 states are needed using the Myhill–Nerode theorem. The following table gives words separating any two of $000,001,010,011,100,101,110,111$:
$$
\begin{array}{c|cccccccc}
& 000 & 001 & 010 & 011 & 100 & 101 & 110 & 111 \\\hline
000 & & 00 & 0 & 0 & \epsilon & \epsilon & \epsilon & \epsilon \\
001 & 00 & & 0 & 0 & \epsilon & \epsilon & \epsilon & \epsilon \\
010 & 0 & 0 & & 00 & \epsilon & \epsilon & \epsilon & \epsilon \\
011 & 0 & 0 & 00 & & \epsilon & \epsilon & \epsilon & \epsilon \\
100 & \epsilon & \epsilon & \epsilon & \epsilon & & 00 & 0 & 0 \\
101 & \epsilon & \epsilon & \epsilon & \epsilon & 00 & & 0 & 0 \\
110 & \epsilon & \epsilon & \epsilon & \epsilon & 0 & 0 & & 00 \\
111 & \epsilon & \epsilon & \epsilon & \epsilon & 0 & 0 & 00 &
\end{array}
$$


Simple path in a graph, within a given range of lengths Given an undirected graph $G(V,E)$ and two nodes $s$ and $t$, $s,t\in V$, find a path whose length $L$ is bounded by a lower bound $N$ and an upper bound $M$, $N\leq L\leq M$.

So, for example, $N=4, M=7$, I want to confirm that there is at least one simple path of 4,5,6 and 7 between two nodes in a graph? Nodes of the graph may appear in more than one path.

Typical problem size:

10,000 nodes
Mean of 20 edges per node
Cycles in graph
Unweighted edges

A special case of your problem is to determine whether there is a path of length between $n-1$ and $n-1$ (sic) in an $n$-vertex graph. This is the Hamiltonian path problem, which is well known to be NP-complete, so your problem is also NP-complete. More generally, it's also NP-complete to determine if a graph has a path of length at least $k$ (i.e., between $k$ and $n-1$) between two given vertices.


Can an artificial neural network convert from cartesian coordinates to polar coordinates? Given cartesian coordinates $x$ and $y$ as input, can a neural network output $r$ and $\theta$, the equivalent polar coordinates?

This would seem to require an approximation of the pythagorean theorem (which requires approximations of $x^2$ and $\sqrt{x}$) and $\sin$, $\cos$, or $\tan$ approximations. Is this possible?

If so, how many hidden layers would it take? I'm using an LSTM.

i dont know if this answers your question (or at least part of it)

According to the Universal approximation theorem for ANNs, it is possible (at least within a region of interest).

The question about how many hidden layers (and architecture) an ANN should have, is, AFAIK, an open problem, in the sense that there is no result to determine architecture and/or number of layers wrt specific final results (partly, this is due to the non-constructive proof of the above result), although you might want to see here and here.

Here is a review on methods to fix number of hidden layers in ANNs during the past 20 years: Review on Methods to Fix Number of Hidden Neurons in Neural Networks

Most ANNs are built by a trial and error process.

update (just an idea)

By modeling the transformations from cartesian to polar (and approximating square roots,..) as a discrete system, maybe one can transfer this design into ANN model (but i wont pursue this further right now)


Data Structure For Closest Pair Problem Suppose I have a list of distinct integers. I'm looking for a data structure that will support the operations search, insert, delete and closest_pair in $O(\log n)$ time.

I know that a sorted array supports search, insert and delete in $O(\log n)$ time. So, all we need to do is maintain information about the closest pair during the insert and delete operations.

The only problem is that the closest_pair would perform in better than $O(\log n)$ time since information about the closest pair would already be available. So, I'm stuck at this point.

Your confusion appears to arise from a misunderstanding: $O(\log n)$ means "proportional to $\log n$ or better". So being able to get the closest pair in constant time is not a problem.

While you seem to already have found a solution to the original problem, I'll still give hints towards a solution, in order to make this answer helpful for other people stuck with that problem.

Hint 1: Basic data structure to start from: (Contrary to the claim in the current version of the question, a sorted array does not work, since you can not insert or delete in an array in $O(\log n)$.)

   A height balanced binary search tree (e.g. AVL tree) works.

Hint 2: What additional information should be stored:

   Each node stores: the smallest and largest value in the subtree below this node and the  closest pair in that subtree.

Hint 3: How to update the information in a single node:

    The smallest value is the smallest value in the left subtree (or the value of the node itself, if no left subtree is present).
 The largest value is the largest value in the right subtree (or the value of the node itself, if no right subtree is present).
 There is no closest pair in a leaf.
 In an inner node there are at most 4 candidates for the closest pair:
 The closest pair in the left subtree,
 the closest pair in the right subtree,
 the pair (largest value in the left subtree, value of the node) and
 the pair (value of the node, smallest value in the right subtree).
 Simply compute minimum of these.

Finally: How to do the operations:

    $\text{search}$ just ignores the additional information.
  $\text{closest_pair}$ reads the required information from the root node.
  $\text{insert}$:
  1. perform a normal AVL-insert
  2. update all nodes on the path from the inserted leaf to the root and all nodes affected by rotations (starting at the leaf)
  $\text{delete}$:
  1. perform a normal AVL-delete
  2. update all nodes on the path from the deleted leaf to the root and all nodes affected by rotations (starting at the leaf)

 If the descent into the tree in insert and delete is done via recursion, the updates can --just as the rotations -- be done when returning from the recursive calls.
 Of course, once a node is unchanged, the nodes above it will remain unchanged as well (unless affected by a rotation).


Three City Scheduling I came across the following interview question

  There are 2N people a company is planning to interview. The cost of
  flying the i-th person to city A is costs[i][0], and the cost of
  flying the i-th person to city B is costs[i][1].

  Return the minimum cost to fly every person to a city such that
  exactly N people arrive in each city.

The solution to this involves greedy approach, where we sort the array based on the "profit" parameter. profit of choosing city A for a candidate i is defined as costs[i][1] - costs[i][0] and choose the top half elements from the sorted array to go to A and rest to B.

What if this question is modified to 3 cities and you have find optimal partition of n/3 chunks? Will greedy algorithm still work?

Generalizing with $kn$ people and $k$ cities we can see "move to city $j$" as a task. Furthermore, we have $n$ copies of each task. For all copies of a task $j$, the cost for person $i$ to move to that task is $c_{i, j}$.

But now the problem is a direct instance of the balanced assignment problem, with complexity $O((kn)^3)$.


Why octal and hexadecimal? Computers use binary and humans decimals Why do we use other bases which are neither binary (for computers) nor decimals (for humans)?

Computers end up representing them in binary, and humans strongly prefer getting their decimal representation. Why not stick to these two bases?

Octal (base-8) and hexadecimal (base-16) numbers are a reasonable compromise between the binary (base-2) system computers use and decimal (base-10) system most humans use.

Computers aren't good at multiple symbols, thus base 2 (where you only have 2 symbols) is suitable for them while longer strings ,numbers with more digits, are less of a problem. Humans are very good with multiple symbols, but aren't that good in remembering longer strings.

Octal and hex use the human advantage that they can work with lots of symbols while it is still easily convertible back and forth between binary, because every hex digit represents 4 binary digits ($16=2^4$) and every octal digit represents 3 ($8=2^3$). I think hex wins over octal because it can easily be used to represent bytes and 16/32/64-bit numbers.


Trying to understand CLRS bucket sort analysis I'm trying to understand the analysis of bucket sort in CLRS. Specifically, equation 8.2 that states:

$$ E[{n_i^2}] = 2 - \frac{1}{n} $$

To prove, CLRS:

Random variable denoting number of elements that fall into bucket i:

$$ {n_i} $$

An indicator random variable that a given element in the input falls into a particular bucket.

$$ X{_i}{_j} $$

so

$$ {n_i} = \sum_{j=1}^{n}X{_i}{_j} $$

Now, CLRS says to expand the square and regroup the terms:

$$ E[{n_i^2}] = E\left[\left(\sum_{j=1}^{n}X{_i}{_j}\right)^2\right] $$

I can see how the above goes to the next step:

$$ = E\left[\sum_{j=1}^{n}\sum_{k=1}^{n}X_{ij}X_{ik}\right]$$

I'm confused as to how the above turns into:

$$ = E\left[\sum_{j=1}^{n}X_{ij}^2 + \sum_{1 <= j <= n}\sum_{1 <= k <= n, k != j}X_{ij}X_{ik}\right] $$

For what it's worth, the Algorithms in a Nutshell books has a section on bucket sort that also analyzes why it's 2 - 1/n, and it helps me see things a bit more clearly, but still am unclear about the above. From the AiaN book:

$$ E[n_i^2] = Var[{n_i}]+ E^2[n_i]$$

where

$$ Var[{n_i}] = n * p * (1-p) = n * \frac{1}{n} * \left(1 - \frac{1}{n}\right) = 1 - \frac{1}{n} $$

and

$$ E[{n_i}] = n * p = n * \frac{1}{n} = 1$$

which equals 2 - 1/n

You are asking why

$\qquad\displaystyle \sum_{j=1}^{n}\sum_{k=1}^{n}X_{ij}X_{ik}
\quad=\quad \sum_{j=1}^{n}X_{ij}^2 + \sum_{j = 1}^{n}\sum_{1 \leq k \leq n,\\ k \neq j}X_{ij}X_{ik}$

holds (in expectation, but that's irrelevant for this; it might not always be, though!).

Note that the left-hand side and the second summand on the right-hand site are identical except for the $k \neq j$ constraint. That is, the difference between the two terms is exactly

$\qquad\displaystyle \sum_{j=1}^n \sum_{1 \leq k \leq n,\\k=j} X_{ij}X_{ik} \quad=\quad \sum_{j=1}^n X_{ij}X_{ij} \quad=\quad \sum_{j=1}^{n}X_{ij}^2$.

No deep insight here, just basic manipulation of sums.


Computing the number of bits of a large power of integer Given two integers $x$ and $n$ in binary representation, what is the complexity of computing the bit-size of $x^n$?

One way to do so is to compute $1+\lfloor \log_2(x^n)\rfloor=1+\lfloor n\log_2(x)\rfloor$ by computing an approximation of $\log_2(x)$ with sufficient precision. It appears that computing $\log_2(x)$ with $k$ bits of precisions can be done in $O(M(k)\log k)$ where $M(k)$ is the time needed to compute the product of two integers of length $k$. This yields a (not specially simple) algorithm of complexity approximately $O(s\log^2 s)$ if $s$ is a bound on the bitsize of both $x$ and $n$ (if I made no error).

Can we beat $O(s\log^2(s))$ where $s$ is the size of $x$ and $n$ (in the case where they have comparable sizes)? Is there a simple algorithm to get this complexity or better?

Note: I am interested in the complexity in a theoretical model such as Turing machines.

[edit] As suggested, I edit my answer to give more details.

The answer to my second question is no:

Proposition. Computing $\log(x)$ up to precision $k$ is at least as hard as computing the bit-size of $x^{2^k}$.

Proof. Let $|y|$ denote the bit-size of an integer $y$. First notice that for a nonnegative integer $y$, the bit-size of $y$ is $1+\lfloor \log y\rfloor$.

Thus, $\left|x^{2^k}\right| = 1+\lfloor 2^k\log x\rfloor$. Now $2^k\log(x)$  is $\log(x)$ shifted $k$ positions to the left. Thus one can compute $\log(x)$ to precision $k$ by simply subtracting $1$ to the bit-size of $x^{2^k}$ and shifting the result $k$ positions to the right.


How Babbage's Analytic engine made calculations of unlimited extent? Brian Randell, in his article The COLOSSUS, explains how computing ushered in the 20th Century, by the development of the Colossus computer. He cites a passage from the Passages from the Life of a Philosopher, illustrating how Charles Babbage described the Analytical Engine :

  That the whole of
  the conditions which enable a finite machine to make calculations of unlimited extent are fulfilled in the Analytical Engine.

I couldn't get how calculations of unlimited extent can be performed by the Analytical engine as described by Babbage. An example would be helpful too.

tl;dr-  The bit about "unlimited extent" is referring to being able to perform general-purpose computation rather than infinite computation.  They probably thought that it was trippy for a finite device to be able to pursue any sort of computation.

It seems that Brian Randell was referring to how the Analytical Engine was meant to be a general-computing device that could, in principle, perform any sort of computation.

The fuller quote discusses the notions of Turing completeness and "unlimited extent" as two different perspectives on this topic:

  Turing thus was the first to arrive at an understanding of the universal nature of a (conceptual) digital computer which matches and indeed surpasses the philosophic understanding that I believe Babbage had attained, a century earlier, of the universality of his planned (mechanical) Analytical Engine. Babbage’s phrasing was “that the whole of the conditions which enable a finite machine to make calculations of unlimited extent are fulfilled in the Analytical Engine” [2, p.28], where the term “extent” encompassed both the amount and accuracy of the data to be processed, and the length and logical complexity of the algorithm to be performed. Central to the Universal Turing Machine is the idea of having data, and input data in particular, represent a program (called a “table”
  in Turing’s paper). A hitherto little known manuscript by Babbage [1] which has recently been published for the first time makes it clear that Babbage had reached an almost similar level of understanding. In the manuscript he points out that a fully detailed sequence of “formula cards” might be prepared by the Analytical Engine from a more abstract sequence. However, this is not to say that Turing’s work was in any way derived from Babbage’s – indeed there is no evidence that Turing even knew of Babbage at this time, but this topic will be returned to later.

  -"The COLOSSUS", Brian Randell, page 4

This seems to be referring to the property of the Analytical Engine to perform general-purpose computation, which the above quote refers to as "universal nature" and "universality".


An efficient data structure supporting Insert, Delete, and MostFrequent Assume that we have a set $D$ and each member of $D$ is a data and key pair. We want a data structure that would support the following operations:

Insert $(d,k)$ into $D$,
Delete member $e$, (no need to search to find $e$, e.g. $e$ points to a member in $D$),
MostFrequent, which returns a member $e \in D$ such that $e.key$ is one of the most frequent keys in $D$ (note that the most frequent key doesn't need to be unique).

What would be an efficient implementation of this data structure?

My solution is a heap for the keys and their frequencies prioritized by the frequencies plus a hash table where the hash function maps members with the same key to the same slot in the hash table (with pointers from each part to the other).

This can give $\Theta(\lg n)$ for the first two operations and $\Theta(1)$ for the third (worst case running time).

I am wondering if there is more efficient solution? (or a simpler solution with the same efficiency?)

In the comparison-based model of computation, you may implement the priority queue using a Fibonacci heap instead of an ordinary heap. This will give you the following bounds: $\mathcal{O}(1)$  amortized time for insert and $\mathcal{O}(\log n)$ amortized time for deletion operations.

If you depart from the comparison-based model and adopt the RAM model where keys are regarded as binary strings, each one contained in one or more machine words, you may implement your priority queue in $o(\log n)$. Indeed, you can achieve for both insert and delete operations $\mathcal{O}(\sqrt{\log \log n}) $ and $\mathcal{O}(1) $ time for the findMin operation. Thorup proved that

If we can sort $n$ keys in time $S(n)$ per key, then we can implement a priority queue supporting find-min in constant time and updates (insert and delete) in $S(n)$ time.

See M. Thorup. Equivalence between priority queues and sorting, 2002. in Proc. FOCS 2002

Since we can sort in $\mathcal{O}(n \sqrt{\log \log n}) $ expected time and linear
space, as shown by

Y. Han and M. Thorup. Integer sorting in $\mathcal{O}(n \sqrt{\log \log n}) $ expected time and linear
space. in Proc. FOCS 2002

the bound is proved.


Proving that {0^{2^k}} is not regular with the Myhill-Nerode theorem My language is the repetition of 0 to a length that's a power of 2:

$L = \{ 0^k \ni k=2^n, n \geq 1 \}$

I want to know how to prove that this language is not regular. I have attempted the proof below, but think it may be incorrect due to my potentially wrong assumption that the Myhill-Nerode theorem allows me to break up a regular language in the following way:

$j, p = 2^h$ for 2 distinct values of $h$, $h \in \mathbb{N}$:

$a = 0^{j/2}$

$b = 0^{p/2}$

$c = 0^{j/2}$

$ac = 0^{j/2}0^{j/2} = 0^j$ is in my language since $j$ is of the form $2^n$

$bc = 0^{p/2}0^{j/2}$ is not guaranteed to be in my language for every $p$ and $j$, since $j \ne p$

Thus my language must not be regular since $ac$ is in it but $bc$ is not.

Did I apply the Myhill-Nerode correctly? If not, what do I need to change in my proof?

I'm not sure I follow your proof. To use Myhill-Nerode, you need to show that the number of equivalence classes under the indistinguishability relation $I_L$ is infinite. What follows is how I would approach this; you're probably best qualified to compare this to what you've done to see whether your proof is relying on the same assumptions, making the same points, and reaching the same conclusions for the same reasons.

Consider the string $w = 0^{2^n + 1}$. This is not a string in $L$. To create a string that is in $L$ by appending to this string, we can append $0^{2^n-1}$, of length $s = 2^n - 1$. There is no other string $s'$ shorter than $s$ such that $ws' \in L$.

Therefore, we immediately have that $w = 0^{2^n + 1}$ and $w' = 0^{2^m + 1}$, $n \neq m$, are distinguishable strings with respect to the indistinguishability relation $I_L$; they belong to different equivalence classes, since the set of strings we can append to $w$ to get a string in $L$ is different from the set of strings we can append to $w'$ to get a string in $L$ (recall that the shortest string in the first set is of length $2^n - 1$, whereas the shortest string in the second set has length $2^m - 1$).

Since $i$ and $j$ vary freely over the natural numbers, we must have an infinite number of equivalence classes over $I_L$. Since the Myhill-Nerode theorem tells us that regular languages must have only a finite number of such equivalence classes (remember, each of these equivalence classes corresponds to a single state in a minimized DFA for the language), this language must not be regular.


Build a context-free grammar for a context-free language A context-free language is defined by its description:

$L=(a^{2k} \space  b^n \space c^{2n} \mid k \geq 0, \space n > 0)$

For example:

$bcc, aabcc, aabbcccc, bbcccc$

How to build a context-free grammar for this context-free language?

I suppose that the order for generating any chain in this problem matters: 'b' will always stand after 'a' and 'c' - after 'b'. Is it so?

My attempts leaded to this solution:

$ S \rightarrow aaAbcc \mid bAcc \mid aabAcc $

$ A \rightarrow aa \mid bcc \mid λ $

Please correct me if I'm wrong or better offer your solution to this problem.

$ S \rightarrow EG $ ,
$ E \rightarrow aO \mid λ $ ,
$ O \rightarrow aE $ ,
$ F \rightarrow bFcc \mid λ $,
$ G \rightarrow bFcc $ .
I am assuming $λ$ stands for empty string.

Better one:

$ S \rightarrow EF $ ,
$ E \rightarrow aO \mid λ $ ,
$ O \rightarrow aE $ ,
$ F \rightarrow bFcc \mid bcc $.


Given tree with 0 or 1 assigned to each node, count paths with odd number of ones in it Let's say we have given tree of $N$ nodes and $N-1$ edges, each of the $N$ nodes is assigned one integer, either $0$ or $1$. We want to count all paths between two nodes $u$ and $v$ such that on the shortest path from node $u$ to node $v$ there are odd numbers of ones ( or in other words the sum of all integers on this path is odd number ).

I know that this can be solved easily by running a single DFS from each node, but this works in $O(N^2)$. I'm trying to find way to narrow it down to $O(N\log N)$ or $O(N)$. I was thinking about applying some dynamic programming, but I couldn't find the relations between the nodes.

You can solve in linear time this using dynamic programming on trees.

Scan the tree from the leaves up toward the root, for each vertex $v$ calculating, for $b \in \{0,1\}$, the number of vertices $u$ below $v$ such that the $(v,u)$ path has the same parity as $b$.


Proving P = NP without mathematical statements / computer program This is my first post after being a passive user for some time now.
I wish to ask some questions if I may.  I am not a mathematician but my question relates to the field of maths/computer science.  In particular, the P vs NP problem.  I am aware that this is a problem that elite professionals have not yet been able to solve ...

Regardless, I would like to ask:

If a person who is neither a mathematician nor a programmer were to come up with a flowchart or a series of steps written in basic English that allegedly provides a solution to one of the P vs NP problem, would that be counted as 'proving' that P = NP .. in order to claim the Clays Institute prize :) ? Or is it a must for one to write the solution as mathematical proofs / computer program?

Thank you.

A Turing machine, it must be remembered, is a kind of flowchart. So is the structure of a computer program generally. So turning "a flowchart" into a formal answer to the problem should be fairly easy, if it actually did work. Indeed, if one started with a terribly formal answer to P versus NP, most computer scientists would try to find a formulation of it which did come as close as possible to a plain english description in order to get as strong an understanding of the solution as possible.

But there is a fundamental problem with the sort of question that you're asking. What does it mean for someone who would be able to solve P versus NP — and by showing that they are equal, no less — to not actually be either a computer scientist or a mathematician? Perhaps they are not employed professionally as a computer scientist or mathematician, but this is beside the point if they have the skill to solve what some (Scott Aaronson, for example) describe as the most important mathematical problem we've ever considered. If someone has the training (or has even self-taught) to successfully tackle the problem, and also to clearly communicate the solution to others by identifying the major sub-routines and their roles in solving e.g. SAT or HAMPATH, then whether they are employed or even have degrees is an irrelevant detail; they are nevertheless in that case a mathematician or a computer scientist. Better still if they can describe how their solutions overcome classic obstacles such as oracle results, such as oracles A for which PA ≠ NPA (or the opposite) by showing specifically what sorts of structure in the problem the algorithm takes advantage of, which would not be accessible in the oracle model. The problem, however, is that most people who dream of solving P versus NP as amateurs or outsiders seem to lack the communication skills to actually describe their work adequately, or (by virtue of not having read enough) they are unaware of results which would make their approach to solving the problem doomed from the start.

As with all dreams of glory these days, there is a basic problem with the fantasy of being the one to resolve P versus NP. The problem is that it's bound to be nearly impossible. Not actually impossible, mind you, or at least not necessarily impossible; just nearly so. As someone bright with ambition, it is possible  for one to lose sight of the fact that there are many other bright people: many of whom have also thought about the problem; and many of whom are brighter than oneself, even by a couple of orders of magnitude. And that there have been such bright people for as long as the problem has been around; and yet it remains unsolved. Yes, it's possible in principle that everyone is thinking about it the wrong way, and have been for decades. But is that really particularly likely? Nobody should expect themselves to be the one person who can spot the one sign-error that everyone else is making, because if everyone else is making that error then there must be something about the problem that will lead one to make the same mistake. Or — in the more likely event that the reason why the problem remains unsolved is not that people keep making simple mistakes or haven't yet thought of the one simple trick that dissolves the whole thing — what makes the problem fundamentally difficult is essentially an objective difficulty of the problem, and no clever dancing steps will allow one to simply waltz gracefully past all obstacles; that what is required is an approach which is not merely novel, but quite profound, identifying subtle structures that there was good reason for nobody to have seen before. The sort of structure which one is most likely to spot by thinking continuously about the problem for years.

If you want to be realistic about what it would take to solve the P versus NP problem, you might compare it to similarly famous breakthroughs in the past few decades, such as the proofs of the four-colour theorem, Fermat's Last Theorem, or the Poincaré conjecture. They might have simpler proofs someday, but the original proofs take you far into the wilderness to get you to the end (or in the case of the Four Colour theorem, the route is very long and repetitive). There's no particular reason to suspect that P versus NP will be different; so that if in the end it is resolved by an amateur, chances are extremely strong that it would be by someone with similar background knowledge and awareness of techniques of someone who is academically trained. Any realistic amateur who dreams of solving P versus NP would do well to keep that in mind.


In a Binary Search Tree what is the base of the log in this Big O notation when discussing average time complexity as in this table.

O (log n)

I'm assuming it is 2 but wanted to verify.  Also is it always 2 for these data structures?

I'm in the opinion that the base of the log is not considered a constant so it should be included in the Big O notation.

Whether or not is should be included.  What is the actual value?

It doesn't matter what the base of the logarithm is.  $\log_a x = (\log_bx)/\log_b a$ so changing from one (constant) base to another just introduces a constant factor. Big-$O$ and related concepts don't care about constant factors.

The base of the log is absolutely a constant: the base used for the calculations might depend on the whim (or, more likely, convenience) of the person who did the analysis but it certainly doesn't depend on the input.


Showing that a problem in X is not X-Complete The Existential Theory of the Reals is in PSPACE, but I don't know whether it is  PSPACE-Complete. If I believe that it is not the case,  how could I prove it?

More generally, given a problem in some complexity class X, how can I show that it is not X-Complete? For example, X could be NP, PSPACE, EXPTIME.

Actually proving $X$ is not $PSPACE$-complete (under, say, polynomial-time reductions) would be extremely hard to do.

If $P=PSPACE$, then all non-trivial (i.e., not $\varnothing$ and not $\Sigma^{\star}$) and infinite problems in $PSPACE$ are $PSPACE$-complete under polynomial-time reductions. Since the existential theory of the reals has this non-trivial and infinite property, proving that it isn't $PSPACE$-complete would imply $P \neq PSPACE$. (See the answer to this question on CSTheory.SE for a sketch of the proof.)


Confusion about the Hiring Problem I'm confused about where the probability from the hiring problem comes from.
For background:

We interview one person everyday who has a quality characteristic, x, from 0 to 1(distributed uniformly). We interview for n days. If on the $i^{th}$ day, person i is more qualified then all the previous candidates, then we hire that person. Find the expected number of people we hire.

We can proceed to solve the problem using linearity of expectation and the method of indicator random variables.
Let X be the number of people we hire.
$$X = X_1 + X_2 + X_3 + ... + X_n$$
where $X_i = 1$ if we hire the with person and $X_i = 0$ if we don't.
According to online resources, the probability that we hire the with person is $\frac{1}{i}$ since each person is equally likely to be the highest so far.
However, this doesn't make sense to me. Why doesn't the probability that we hire the $i^{th}$ person depend on the quality characteristic we've seen so far?
Take, for example, the second person:
Shouldn't the
$(2^{nd} \text{person hired}) =1 - n_1$
where n_1 is the quality characteristic of the first person?
If we use what online resources say then $P (2^{nd} \text{person hired}) = \frac{1}{2}$. But what if person one had a quality characteristic of .9, then $P(2^{nd} \text{ person hired}) = .1$ and not half.
Can someone tell me where my logic is wrong?

Let us denote by $x_1,\ldots,x_n$ the qualities of the $n$ persons; so the $x_i$ are iid random variables distributed uniformly over $[0,1]$.
If you know $x_1,\ldots,x_i$, then $X_i$ becomes deterministic. For example, if $x_1 = 0.3$ and $x_2 = 0.5$ then $X_2 = 1$, whereas if $x_1 = x_2 = 0.4$ and $x_3 = 0.1$ then $X_3 = 0$. If you know only some of $x_1,\ldots,x_i$, then you can calculate the distribution of $X_i$, as your example demonstrates.
None of this is needed to calculate $\mathbb{E}[X]$, however. Using linearity of expectation, we know that
$$
\mathbb{E}[X] = \sum_{i=1}^n \mathbb{E}[X_i] = \sum_{i=1}^n \Pr[X_i = 1].
$$
In other words, in order to calculate the expected number of people hired, all we need to do is to calculate the probability that $X_i = 1$. This probability is $1/i$. You're right that the probability changes if we know more about the $x_j$, but so what? We are not interested in calculating $\mathbb{E}[X]$ given partial knowledge of the $x_j$. Instead, we want to calculate the expected value of $X$ when $x_1,\ldots,x_n$ are chosen uniformly at random from $[0,1]$, independently. This is the relevant distribution for calculating $\Pr[X_i = 1]$.
What might be throwing you off is the trick of using linearity of expectation. It allows us to treat the random variables $X_i$ completely independently, although the variables themselves are certainly dependent.


Quantum computing - Difference between a binary bit and a Q-bit I have recently watched this introductory video on quantum computing where the speaker talks about $n$ Q-bits and the representation of $2^n$ states.

What I didn't get is the word state.How is it different from a classical computer working with $1$'s and $0$s in which each bit can represent 2 states ($0$ or $1$) so that the $n$ bits can generate $2^n$ states.

I think something worth pointing out early on is the ambiguity of the word state. In quantum information most things have very strong (shall I say natural?) physical interpretations / origins.
In classical information we represent information as bits. A bit might correspond to the state of some classical system, such as an electric sign in a circuit, etc. Evolution of classical bit vectors is arbitrary in the sense that its enforced by us humans.

In quantum computing information is represented using states of a quantum system (for example polarization of a photon).
The states of a quantum system can be identified with vectors of a Hilbert space. Qubits $|0\rangle, |1\rangle$ are just an arbitrary choice bases of a two dimensional space. A two-qubit state represents a quantum system which is a composite of two two-dimensional subsystems. Evolution of quantum state vectors are governed by the laws of physics.

For a classical two-bit vector, the permissible values are $00,01,10,11$, whereas for a two-qubit system you can have any $a|00\rangle+b|01\rangle+c|10\rangle+d|11\rangle$ for $a,b,c,d\in\mathbb{C}$ provided that $|a|^2+|b|^2+|c|^2+|d|^2=1$. This, together with the postulates of quantum mechanics, permits a completely different range of behaviors of quantum systems (and qubit vectors), behaviors that are unseen in classical systems. This gives the above representation of information a lot more power compared to classical information representation. A number of physical phenomena allow various interesting information theoretic operations (such as teleportation, superdense coding, etc), which are not admissible using classical systems.

The emphasis here really is on the fact that in quantum computing you can exploit a range of physical phenomena that is not typical in classical information theory.


Simulating DFA operations on non-regular languages with finite final state set A language I'm investigating is not regular since the minimal DFA for the language grows depending on input string size. However, while the number of non-final states increases, the final states are the same small strictly finite core which include the initial state.

Another question looks superficially similar, hinting that what I'm looking for might be an interpretation of this language as a generalization of a prefix-code in order to ignore the infinite non-final states.

Are there methods to treat this 'pseudo-regular' language as regular (or any other language class with efficient algorithms) for purposes of intersection and path finding from the small final state set back to the inital state, thus sidestepping the issue that the complete DFA is not finite in size?

Your question is missing quite a few definition, but here is my interpretation.

  A language $L \subseteq \Sigma^*$ is finite-regular if there exists $C$ such that for all $n$, $L \cap \Sigma^n$ is accepted by some DFA with at most $C$ final states.

Note that if the minimal DFA for a language has $m$ accepting states, then every DFA for the language has at least $m$ accepting states (this follows from Myhill–Nerode theory). Therefore we obtain an equivalent definition if we replace "some DFA" with "the minimal DFA".

Using the product construction, you can easily show that the class of finite-regular languages is closed under union and intersection, and more generally under monotone set operations.


Subset sum algorithm in O(n³ log n)? I think that I have found an algorithm which resolve exactly the subset sum problem in $O(N^3)$ in the worst case, only for positive numbers.

After my research, I'm lost between all the algorithms for this problem.

$O(2^N*N)$ for the naive algorithm (I understand)
$O(2^{N/2})$ for advanced algorithm (I understand)
$O(N * C)$ for pseudo-polynomial time algorithm (only positive numbers)

Reference : Wikipedia

$O(N^3 * log(N))$ for an exact resolution but I don't understand the whole process

Reference : Andrea Bianchini paper

I would like to know if my resolution is in polynomial time ?

If it is, the paper of Andrea Bianchini is too.
So it should proove that P=NP, but it's not the case. Why ?

This is a common misconception many have. Subset sum, among others, is NP-complete only if the input is encoded in binary (or ternary etc). In unary encoding it's polynomial-time solvable by a simple dynamic programming approach. These problems are sometimes referred as weakly NP-complete.
If you're not quite sure what I mean by unary encoding: Unary encoding means we encode a number by a sequence of $1$'s of appropriate length.
All in all, I fear you haven't settled P/NP (unless, of course, your runtime refers to binary-encoded problems). But good luck!
As an example, suppose your input consists of $10$ numbers, each between $128$ and $256$. Then your input size is, in unary, about $10 \times 256=2560$, whereas your input size is, in binary, $10 \times \log_2 (256) =80$.
That's quite a difference!

Wikipedia describes an algorithm that works in polynomial time for unary encoding. Wikipedia's solution was taken from the book Computers and Intractability: A Guide to the Theory of NP-Completeness, by M. Garey and D. Johnson.


Minimum spanning tree formulation as integer program The minimum spanning tree problem can be solved in polynomial time via Kruskal's or Prim's algorithm. However, every integer program I have seen that corresponds to the MST problem require a constraint for every subset of vertices, so the number of constraints would be exponential.

That makes me wonder, is it is possible to write down the constraints for a IP corresponding to MST such that the number of constraints is polynomial in the number of vertices? Furthermore, if it is possible, does it hold that every problem in P can be written as a LP with at most polynomial number of constraints?

Thank you very much!

Yes, it's possible.

It's trivially possible that every problem in P can be reduced to LP in polynomial time, for uninteresting reasons: given an instance of the decision problem, the reduction solves the decision problem (in polynomial time), then either outputs a feasible LP instance or an infeasible LP instance (where these instances are hardcoded).  I realize that's pretty uninteresting and probably not what you wanted.


How do you read the regular expression (0^∗10^+)^+? Give an example of a string in the language of $(0^*10^+)^+$.

I've been asked to give an example of a string in this language but I'm confused on how to read this notation. I'm guessing the acceptable strings are supposed to start with 0, but that's about all I can infer.

This regular expression describes the language of all words over $\{0,1\}$ which do not consist entirely of $0$-s, and in which every $1$ is followed by $0$.


When are adjacency lists or matrices the better choice? I was told that we would use a list if the graph is sparse and a matrix if the graph is dense. For me, it's just a raw definition. I don't see much beyond it. Can you clarify when would it be the natural choice to make?

Thanks in advance!

First of all note that sparse means that you have very few edges, and dense means many edges, or almost complete graph.
In a complete graph you have $n(n-1)/2$ edges, where $n$ is the number of nodes.

Now, when we use matrix representation we allocate $n\times n$ matrix to store node-connectivity information, e.g., $M[i][j] = 1$ if there is edge between nodes $i$ and $j$, otherwise $M[i][j] = 0$.
But if we use adjacency list then we have an array of nodes and each node points to its adjacency list containing ONLY its neighboring nodes.

Now if a graph is sparse and we use matrix representation then most of the matrix cells remain unused which leads to the waste of memory. Thus we usually don't use matrix representation for sparse graphs. We prefer adjacency list.

But if the graph is dense then the number of edges is close to (the complete) $n(n-1)/2$, or to $n^2$ if the graph is directed with self-loops. Then there is no advantage of using adjacency list over matrix.

In terms of space complexity
Adjacency matrix: $O(n^2)$
Adjacency list: $O(n + m)$
where $n$ is the number nodes, $m$ is the number of edges.

When the graph is undirected tree then
Adjacency matrix: $O(n^2)$
Adjacency list: $O(n + n)$ is $O(n)$ (better than $n^2$)

When the graph is directed, complete, with self-loops then
Adjacency matrix: $O(n^2)$
Adjacency list: $O(n + n^2)$ is $O(n^2)$ (no difference)

And finally, when you implement using matrix, checking if there is an edge between two nodes takes $O(1)$ times, while with an adjacency list, it may take linear time in $n$.


What to infer about maximum height of AVL tree from these three different formulae I have came across following problem:

  What is the maximum height of any AVL-tree with 7 nodes?

The recurrence giving number of nodes $n$ in the AVL tree for given height $h$ is as follows:

  $n(h)=n(h-1)+n(h-2)+1$

  $n(0)=1$

  $n(1)=2$

So if we follow this recurrence, we get the height of the AVL tree with 7 nodes = 3 as follows

$n(2)=n(1)+n(0)+1=2+1+1=4$

$n(\color{red}{3})=n(2)+n(1)+1=4+2+1=7$

However I find two formulae, both listed on this page:

The first one is stricter one:

  $h < 1.475 \times log_2(n(h)) - 1.475$

According to this formula, I get

$h < 1.475 \times log_2(7)-1.475$

$h<\color{red}{2.665}$
The second one is rough estimate and it is taken from Goodrich's book:

  $h < 2 \times log_2(n(h)) + 2$

According to this formula, I get

$h < 2 \times log_2(7) + 2$

$h<\color{red}{7.61}$

So with these different answers, I don't get what should I infer. Am I doing any miscalculations? Or should I just stick to what is yielded by recurrence and ignore formulae as they are mere estimates? Or should the first formula have ceil function to give perfect answer rather than the estimates as follows?

$h \color{red}{=} \color{red}{\lceil} 1.475 \times log_2(n(h)) - 1.475 \color{red}{\rceil}$

Perhaps the simplest way out is to solve the recurrence explicitly. Let $m(h) = n(h) + 1$. Then $m(h)$ satisfies the recurrence
$$
m(h) = n(h) + 1 = n(h-1) + n(h-2) + 2 = m(h-1) + m(h-2).
$$
The initial conditions are $m(0) = 2$ and $m(1) = 3$. Define $F(h) = m(h-3)$, so that $F(3) = 2$, $F(4) = 3$, and $F(h) = F(h-1) + F(h-2)$ for $h > 4$. It is well-known that
$$
F(n) = \frac{1}{\sqrt{5}} \left[\left(\frac{1+\sqrt{5}}{2}\right)^n - \left(\frac{1-\sqrt{5}}{2}\right)^n\right].
$$
Since $m(h) = F(h+3)$ and $n(h) = m(h)-1$, we see that $n(h) = F(h+3)-1$ and so
$$
\begin{align*}
n(h) &= \frac{1}{\sqrt{5}} \left[\left(\frac{1+\sqrt{5}}{2}\right)^{h+3} - \left(\frac{1-\sqrt{5}}{2}\right)^{h+3}\right] - 1 \\ &=
\frac{2+\sqrt{5}}{\sqrt{5}} \left(\frac{1+\sqrt{5}}{2}\right)^h -
\frac{2-\sqrt{5}}{\sqrt{5}} \left(\frac{1-\sqrt{5}}{2}\right)^h - 1.
\end{align*}
$$
The second term is very small, and in particular
$$
\frac{2+\sqrt{5}}{\sqrt{5}} \left(\frac{1+\sqrt{5}}{2}\right)^h - 2 < n(h) < \frac{2+\sqrt{5}}{\sqrt{5}} \left(\frac{1+\sqrt{5}}{2}\right)^h.
$$
This shows that
$$
\log_{(1+\sqrt{5}))/2} n(h) < h + \log_{(1+\sqrt{5}))/2} < \log_{(1+\sqrt{5}))/2} [n(h)+2],
$$
from which you can deduce whichever excellent bounds you want.