Classification and complexity of generating all possible combinations: P, NP, NP-Complete or NP-Hard The algorithm needs to generate all possible combinations from a given list (empty set excluded).
list          =>         [1, 2, 3]
combinations  =>         [{1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}]

This algorithm would take O(2n) time complexity to generate all combinations. However, I'm not sure if an improved algorithm can bring this time complexity down. If an improved algorithm exists, please do share your knowledge!
In the case that it takes O(2n) which is exponential, I would like some insight regarding which class this algorithm belongs to P, NP, NP-Complete, NP-Hard, or whether it does not belong to any of them. Thanks in advance :)

If you want to explicitly list all subsets of list, then the size of the output will be $\Omega( n \cdot 2^n )$.
Notice indeed at least half of these subsets have at least $\lfloor n/2 \rfloor$ elements, and just writing them out requires  $\Omega( n \cdot 2^n )$ space (and time).
If you want to iterate over each of these subsets but you don't necessarily need to explicitly list them, then you still need $\Omega(2^n)$ time since there are $2^n - 1$ subsets of interest.
An easy algorithm is as follows: maintain a binary counter $c$ of $n$ bits.
Intuitively, the counter represent the indicator vector of a subset $X$ of list (i.e., the $i$-th bit is $1$ iff the $i$-th element of list is included in $X$). Initially $c=0$. Increment $c$ until it overflows. Each time that a bit flips from $0$ to $1$ (resp. $1$ to $0$) you interpret this as adding (resp. removing) the corresponding element to $X$. The set resulting after each increment is the next set to consider.
This algorithm requires $O(2^n)$ time, plus whatever time you need to process these implicitly generated sets. To see this you can take a look at the amortized analysis of incrementing a binary counter (see, e.g., the section "Incrementing a binary counter" in Chapter 17 of CLRS). Essentially, the least significant bit flips at every increment, the second least significant bit only flips every other increment, and so on. The number of bit flips is then $\sum_{i=0}^{n-1} \frac{2^n}{2^i} < 2^n \cdot \sum_{i=0}^{+\infty} 2^{-i} = 2^{n+1} = O(2^n)$.
An application of this algorithm is generating all possible subset-sums of a set $S$ of integers (which is used used, e.g., in the split-and-list algorithm for the subset-sum problem), assuming that $\sum_{x \in S} x$ still fits into a constant number of memory words (and hence arithmetic operations can be carried out in constant time).
In this case adding (resp. removing) an element $x$ to the subset simply means increment the previous sum by $x$ (resp. $-x$).
Asking whether this problem belongs to $\textsf{P}$ or $\textsf{NP}$ or is $\textsf{NP}$-complete makes no sense, since these complexity classes are only defined for decision problems (and yours is not).


Can the mind be a finite automata and still invent the Turing machine? The Turing machine was invented by a human mind.  Presumably, nothing less powerful than a Turing machine can invent a Turing machine.

However, a Turing machine has infinite tape, whereas the mind is situated in a finite universe, and thus can only be a TM with finite tape.  A TM with finite tape can be simulated by a finite automata, which is strictly less powerful than a Turing Machine.  This seems to imply that a Turing machine was invented by an automata that is less powerful than a Turing machine, contradicting the initial premise.

Is this a problem?  Or, is the initial premise false?  Is it possible for a finite automata to somehow "invent" a machine that is more powerful, a kind of bootstrapping, if you will?

While it is difficult to formally define "invent," it does not seem a finite automata can even represent finite TMs effectively.  For example, on the wikipedia page, it states a DFA will require quadrillions of states to represent a TM with a few hundred states.  So, to even just represent the useful subset of halting TMs, my impression is that a DFA representation will probably exceed any computational capacity we have.  There appears a big disconnect between DFAs and TMs, such that it is hard to imagine a plausible bootstrapping to go from one to the other.

There is also the related issue of how a finite automata can prove the halting problem for TMs.

Some Turing Machine Details

A Turing Machine does not have infinite tape, it has unbounded tape. There is no limit to how many symbols can be stored on it, but at any given time, only a finite number of symbols are ever on the tape. So while we cannot conceive of all runs of a machine, we can always conceive at least some states of the machine.
In a sense, Turing Machines carve out the "finite" portion of all languages, in the sense that it carves out the portion that can be finitely represented (by a Turing Machine). There are uncountably many languages, but countably many Turing Machines, so there's a bunch of stuff we will never understand because it is truly infinite, in too big of an infinity.
Most problems that we can conceive of don't actually require the power of a Turing Machine. Many can be written using primitive recursion or other well-founded recursion schemes. So most algorithms don't actually require the infinite-ness of Turing Machines.
For a Turing Machine that halts, there is always a function describing the max amount of memory used in relation to the input size. So we don't need to understand infinity, we simply need to understand the relationship.

Can a weak system invent a stronger one?

The answer here, I think, is yes, depending on your definition. For example, the language of all valid Turing Machines can be described using a context-free grammar, a computationally weaker formalization. You can even describe a regular language that describes what a valid Turing Machine looks like, and they're finite. (Spoiler alert, this doesn't say much, because you can map each integer onto a Turing Machine, so the regular language $\{0,1\}^*$ can be the set of all valid Turing Machines).

And, it's important to distinguish recognizing a thing, or inventing a description of something, and inventing all the things. We can recognize what a Turing machine is, but we can't see all of them, and because of things like the Halting problem, we certainly can't even understand all of them.

Other Infinite Things

This question is ultimately no different than asking how a finite mind could understand the natural numbers, or the function $y=x$ in $\mathbb{R}^2$. Both are infinite, but can be described in finite ways.

But, there are functions and sets and real number and such that are truly infinite, that can never be described by any possible spoken or written formula (because there are uncountably many reals, but countably many finite sentences in any human language.) And there are more true theorems than there are proofs, a la Gödel.

So we can describe infinity, and speak of its properties, perhaps without truly understanding it, at least without understanding every facet of it.


Understanding an upper bound in the analysis of Karger's algorithm I'm reading the wiki page of Karger's algorithm for a self-study of CLRS to get some and I'm confused by one of the bounds they have.

Here, under the section about finding all min cuts, they have this line $$(1-P(n))^{O(\log^{2} n)} \le (1-\frac{c}{\ln n})^{\frac{3}{c} \ln^{2} n}$$. I get that they are using the definition of big O to insert these constants, but what feels fishy to me is the choice for the constant in the exponent of $\log^{2} n$ of $\frac{3}{c}$. Why can't I just choose the coefficient to just be, $\frac{2}{c}$ and get a tighter bound? How do they know here that $\frac{3}{c}$ is the smallest coefficient that may be chosen?

I understand the rest of the argument, for the record (They're using $e^{x} \ge 1+x$)

$$(1-P(n))^{O(\log^{2} n)} \le (1-\frac{c}{\ln n})^{\frac{3}{c} \ln^{2} n}$$

First, to get a tighter bound, you should choose $\frac{4}{c}$ or larger, instead of $\frac{2}{c}$ or smaller.

In particular, the probability for $\frac{2}{c}$ is
$$\textrm{Pr}[\textrm{miss any min-cut}] \le O(1).$$
This does not make sense for a probability value.

Second, the larger the chosen coefficient is, the higher the time complexity of the algorithm is (to achieve a tighter bound). That is, there is a trade-off.


Context-free string that satisfies constraint? I'm not sure on how to come up with a string that is in terms of $p$ for

$ a^ib^jc^k$  where $ i+j = k^2$

Where $p$ is the pumping length. I can't seem to find anything in terms of $p$ that satisifies the constraint. Any ideas or sugeestions are appreciated!

It is not necessary to define a string that has exactly length $p$. It only has to have length at least $p$. So $(i,j,k) = (2p^2,2p^2,2p)$ so that $2p^2+2p^2 = (2p)^2$ for a string of length $4p^2+2p$ would be OK.


How do I prove that a Turing Machine that accepts a string w in an even number of steps is not decidable? Let a language A =  {(M,w) : M is a TM and w is a string such that w is accepted by M in an even number of steps}.

How can I prove that this is undecidable? I have considered trying to build the ATM proof assuming this language. Language A can cover acceptance under even steps but how would I cover acceptance under uneven steps? Language A would reject in that case. How would you go about trying to build the proof via this path?

Another thing I wonder is if Rice's theorem covers this language. Would this be considered a functional property? Could I use it to prove the undecidability of this language?

Thanks

This is a bit of a nit-picky question, since you really need to pay attention to the parity of the number of steps you TM does.

We'll show that the problem is undecidable by a reduction from $A_{TM}$. There are many ways to construct such a reduction. In my opinion, the following is the least technical.

Given input $(M,w)$ for $A_{TM}$, we will construct a new output $(M',\epsilon)$, such that $M$ accepts $w$ iff $M'$ accepts $\epsilon$ within an even number of steps.

We construct $M'$ as follows: given input $x$, if $x\neq \epsilon$, then $M'$ rejects.

Otherwise, if $x=\epsilon$, $M'$ works as follows: simulates the run of $M$ on $w$. If $M$ accepts, it clears the tape by going to the rightmost non-blank cell, and then writes blanks all the way to the left. It then simulates $M$ again, erases the tape again in exactly the same manner, and accepts.

If $M$ rejects, then $M'$ rejects as well.

The idea here is that if $M$ accepts $w$, then the operation of $M'$ on $\epsilon$ is to simulate $M$ on $w$ twice. Therefore, it will take an even number of steps.

Proving the correctness and computability of this procedure is not hard.


Does every problem in NP have an exponential time algorithm? I am not sure that every problem in NP have an exponential time algorithm. Since NP does not mean "not polynomial.", I think the answer is false. But I have no concrete reason about that.

Yes, every NP problem has an exponential-time algorithm. One definition of NP is the "succinct certificates" definition: a language $L$ is in NP if, and only if, there is a relation $R$ on strings such that:

there is a polynomial $p$ such that, whenever $(x,y)\in R$, $|y|\leq p(|y|)$,
$x\in L$ if, and only if, $(x,y)\in R$ for some $y$, and
there is a deterministic Turing machine that decides if $(x,y)\in R$ in polynomial time.

So, to decide if $x\in L$, all you need to do is try all possible $y$s of length at most $p(|x|)$ to see if $(x,y)\in R$ for some $y$.  There are exponentially many possible values of $y$ to try.

To see the intuition behind succinct certificates, consider 3-colourability. There, a certificate is a 3-colouring of the graph. To describe a 3-colouring needs just a constant number of bits to say what colour each vertex of the graph has, so the length of the certificate is bounded by a polynomial. Obviously, a graph is 3-colourable if, and only if, it has a 3-colouring. And if I claim to have a 3-colouring of a graph, you can check that in deterministic polynomial time: just make sure I didn't give the same colour to two adjacent vertices.

To get a succinct certificate for any NP-problem, use the definition that a problem is in NP if it's decided by a nondeterministic Turing machine in polynomial time. Use a description of an accepting run of that machine as the certificate.


Why it converts to T The AND function in the lambda is:

and = (λ a. λ b. a b F)

I have following expression:

and T T

then the result will become T and I am asking me why?

When I do the beta reduction, then I understand, why I've got T:

(λ a . λ b . a b (λ x . λ y . y)) (λ x . λ y . x) (λ x . λ y . x)
(λ b . a b (λ x . λ y . y))[a →(λ x . λ y . x)] (λ x . λ y . x)
(λ b . (λ x . λ y . x) b (λ x . λ y . y)) (λ x . λ y . x)
((λ x . λ y . x) b (λ x . λ y . y))[b→(λ x . λ y . x)]
(λ x . λ y . x) (λ x . λ y . x) (λ x . λ y . y)
(λ y . x)[x →(λ x . λ y . x)] (λ x . λ y . y)
(λ y . (λ x . λ y . x)) (λ x . λ y . y)
(λ x . λ y . x)[y→(λ x . λ y . y)]
(λ x . λ y . x)
T

But when I shortened it like:

T T F

then I've got F, because:

T T F
T F
F

What am I interpreting wrong?

$T \equiv \lambda x. \lambda y. x$, which means it is a $\lambda$-function of two arguments, returning the first one, so $(T\ T\ F)$ $\beta$-reduces to $T$, which can be shown more formally as follows.

$$T\ T\ F \equiv (\lambda x. \lambda y. x)\ T\ F \to_\beta
(\lambda y. T)\ F \to_\beta
T$$


What kind of bigram probability smoothing is this? I hope it isn't off topic but I need to understand this example. Given the corpus 12 1 13 12 15 234 2526 and smoothing factor of k=1. The example does the following operations:

Considers OOV(out of vocabulary) words and assigns them a zero times value, after that k=1 is added to the times every words appears, to avoid zero probabilities. So the result of smoothing the bigrams probability will be:

$P(1|12)=(1+k)/(2+2+6*k)=0.2$
$P(15|12)=(1+k)/(2+2+6*k)=0.2$
$P(13|1)=(1+k)/(2+6*k)=0.25$
$P(12|13)=(1+k)/(2+6*k)=0.25$
$P(234|15)=(1+k)/(2+6*k)=0.25$
$P(2526|234)=(1+k)/(2+6*k)=0.25$

My question is, What kind of smoothing is this? shouldn't be for example like this?; $P(1|12)=(1+k)/(2+6*k)=0.25$Besides it also says "If OOV words appear, you need to use smoothing to return a value; $P(234|12)=1/((2/7)*6+6)=0.1296$"

PS: I take this example from a small section of the translated version of this chinese webpage, it is just explaining a code implementation.

This looks like it might be implementing Laplace smoothing (though I can't explain the extra +2 in the first two calculations).

There are many smoothing methods, e.g., Lidstone, Good-Turing, Kneser-Tey,  Witten-Bell.  You can also use interpolation and backoff to handle rare or low-probability events when computing conditional probabilities like this.


Find the longest possible path in full binary tree Given the depth of the tree, I need to calculate the longest possible path in the full binary tree (also known as the diameter).

When attempting this problem, I experimented with what the depth has to do with the path length. However, the solutions I came up with depended on going through the root, while the longest path could obviously exist outside of the root.

What's an equation I can use to find the diameter of the full binary tree using the depth?

If it is a full binary tree, that is defined as:

  Full binary tree is a tree in which every node other than the leaves has two children.

Then you know the depth $D$ will be half of the total possible diameter. This is because we can take a maximum possible path of length $D$ from root to any leaf in the subtree rooted at the left-child of the root, and we can also take a maximum possible path of length $D$ from root to any leaf in the subtree rooted at the right-child of the root. Thus, adding these up would be a path of length $2D$.

Thus, we get that the maximum possible diameter would be equal to twice the depth (i.e. $\mathrm{diameter} = 2\cdot \mathrm{depth}$).


If I can efficiently uniformly sample both $A$ and $B\subset A$, can I efficiently uniformly sample $A-B$? As posed in the question; the statement naively seems like it should be self-evident but there are no algorithms that come immediately to mind. Suppose I have some domain $A$ (in my case a subset of $\mathbb{Z}^n$ for some $n$, but I would expect any answer to be independent of that structure), and a domain $B\subset A$. If I have an efficient algorithm for uniformly sampling from $A$, and an efficient algorithm for uniformly sampling from $B$, is there any way of 'combining' these to get an efficient algorithm for uniformly sampling $A-B$? I can certainly rejection-sample, but if $|A-B|\ll|A|$ then there's no guarantee that that will be efficient.

Theorem: For any given $A$, either there are good algorithms to sample every subset of $A$, or what you're describing is impossible.
Proof (perhaps slightly informal): Suppose there are some "problematic" subsets of $A$ (those which cannot be efficiently sampled). Let $C$ be one of those subsets. From the fact that $C$ is problematic, it follows that $|C| \ll |A|$ (otherwise $C$ could be dealt with by rejection-sampling). Now let $B = A \setminus C$. Clearly, rejection-sampling does work on $B$, because $B$ is almost the entirety of $A$. So now we have algorithms for both $A$ and $B$, but no algorithm for $C$. Q.E.D.
Here's a ridiculous example: $A = \{(x_1, x_2, x_3, x_4) \mid x_i \in \mathbb{Z},\; 2 < x_i < 10^{10^{10^{1000}}}\}$ and $B$ contains only those quadruplets of numbers which are not counterexamples to Fermat's Last Theorem (i.e. such that $x_1^{x_4} + x_2^{x_4} \neq x_3^{x_4}$). It's trivially easy to sample $B$, but that gives us no clue whatsoever about how to do $A \setminus B$.


Which permutations can not be obtained by moving elements through two stacks? I have a Stack1 which  has the entries a,b,c ( with a on the Top) and  Stack2 which is empty.The condition is.

  An entry pooped out of the stack1 can be printed immediatly or pushed to stack2. An Entry popped out of the stack2 can only be printed.

In this Arrangement, which of the permutation of a,b,c is not possible.

I tried diagrammatically by popping out the initial stack and found the first arrangement as c,a,b...Then i mind a formula taught in Permutation's course as (n-1)! possibilites so came up with answer of 5.

so, which arrangement will be not possible.??

This process is called stack sorting. Wikipedia has a page on the subject.

Here you read that the number of possible sequences when the input is $1,2,\dots,n$ equals the Catalan number $C_n = \frac{1}{n+1} {2n\choose n}$, which differs from your guess.

In fact there is a nice characterization of the orders which are possible, they avoid the permutation pattern $231$. However your problem is "backwards", not the strings that can be sorted using a single stack, but the strings that can be obtained that way.


Does Multitape reduction to a one tape machine preserve space complexity? Suppose a Turing machine $M$ has a read-only input-tape and $k$ read-write work-tapes whose non-blank cells are each bounded by $f(|x|)$ where $|x|$ is the length of the input.

Is there some constant $C(k)$ and Turing machine $M^{'}$ with a read-only input tape such that $M^{'}$ accepts exactly when $M$ accepts, $M^{'}$ has only one read-write work tape, and the blank cells of that tape are bounded by $C f(|x|)$?

If there doesn't exist such a constant $C(k)$ that is independent of $M$, does there exist a constant $C(k, M)$?  In other words does reducing the number of tapes preserve space complexity?

You can take $C(k)=1$.

Simulate the $(k+2)$-tape machine (input, output, $k$ work tapes) by storing the $i$th character of all the simulated tapes in the $i$th character of the single tape. This is a standard construction, which also requires you to store the head positions using the characters on the tape. Now, you can do the whole computation without using any extra space.

In a little more detail, suppose you're simulating a Turing machine with tape alphabet $\Sigma$. Let $\Sigma'$ be the alphabet containing a character $a'$ for each character $a\in\Sigma$. We'll simulate using alphabet $(\Sigma\cup\Sigma')^{k+2}$, so each character on the simulating tape is a tuple $(c_1, \dots, c_{k+2})$. If $c_j\in\Sigma$, that means that the corresponding cell on the $j$th tape of the simulated machine contains that character; if $c_j=a'\in\Sigma'$, that means the cell contains character $a$ and that tape's head is in this position.

Note that it only makes to talk about space $\Omega(n)$ on single-tape Turing machines, since you now have to count the space used by the input.


Need solution for infinite right recursive grammar in Predictive parsing? i am new to compiler design, currently studying Ullmans book on this.He says:

Problem with predictive parsing (both recursive and non recursive) is that Left recursive productions can go infinite loop.Thus, to make grammar suitable for predictive parsing we need to eliminate the left recursion by immediately or indirectly.

 E -> E+T|t

My problem is, same can happen with right recursion also.What is the solution for it?

 T -> E+T|t

Please correct me if i am wrong! thanks.

You don't get infinite recursion with right recursive rules if the prediction sets for the rules are different.

In the example T -> E + T | t, if the first set of E does not contain t (I am presuming t is a terminal), you are fine. The parsing procedure will be:

def T
  if look_ahead is in first(E)
    E
    match ('+')
    T
  else if look_ahead == t
    advance_lookahead
  else syntax_error

With this, the recursion will stop when the look ahead contains t.

With left recursion T -> T + E | t, you are in trouble because first(T) always contains t.

Conversion of left- to right recursion solves one problem but creates another. Right-recursive rules have the disadvantage that parsing lists requires stack space proportional to list length.  Ideally you'd like the space a parser takes to be limited by a constant.  So what to do?

The practical way to prevent many cases of right-recursion is to extend grammars to allow for iteration.  In your case

T -> E + T | t

would become

T -> E + { E + } t

The curly braces denote "0 or more".

When the parser is implemented, the curly braces would become a while loop that uses the look ahead to decide whether to parse another instance of what's in the braces.  With your example, you'd need first(E) not to contain terminal t.

A more common example is the standard expression grammar:

Expr -> Term { '+' Term }
Term -> Factor { '*' Factor }
Factor -> '0' | '(' Expr ')'

In this case, the recursive descent procedure for Expr would be

def Expr
  Term
  while look_ahead == '+'
    advance_lookahead
    Term

If we didn't have the curly braces, the grammar would have to be:

Expr -> Term ExprTail
ExprTail -> '+' Term ExprTail | \eps
Term -> Factor TermTail
TermTail -> '*' Factor TermTail | \eps
Factor -> '0' | '(' Expr ')'

To parse Exprs we now need two procedures:

def Expr
  Term
  ExprTail

def ExprTail
  if look_ahead == '+'
    advance_lookahead
    Term
    ExprTail

Interestingly, if you use a good compiler to compile both versions with optimizations turned on, it will detect tail recursion in ExprTail, convert it into a loop, and then in-line the loop in Expr.  The resulting compiled codes will be exactly the same.


Finding out if languages involving counting and modulo operations are regular I am having trouble with the regularity of the two following languages:

i) $\{0^{n}1^{m}|n,m>0,n-m=0\,mod\,3\}$

ii) $\{0^{n}1^{m}|n,m>0,n+m=0\,mod\,3\}$

To clarify this is stating that the (#(0's) - #(1's)) mod 3 = 0.

I know how to prove that the first language is regular without the n,m > 0 restriction but with it I am inclined to think that the language is not regular because we'd need to make sure there is at least one 1 and 0 b and in doing so would also have to "remember" the previous numbers of 0's and/or 1's. Which is not possible with a DFA.

My logic is similar with the second statement.

Is my logic right?

This is essentially @Yuval's hint, expressed in a slightly different way. You've said that you can prove
$$
L_u = \{0^n1^m\mid n, m \ge 0, n - m \equiv 0\pmod{3}\}
$$
is regular. If so, then its intersection with the regular language denoted by $00^*11^*$ will be regular. Show that this intersection is equal to
$$
L_r = \{0^n1^m\mid n, m > 0, n - m \equiv 0\pmod{3}\}
$$
and you're done. Notice that a similar construction shows that
$$
\{0^n1^m\mid n > k, m > j, n - m \equiv 0\pmod{3}\}
$$
is also regular for any $k, j > 0$.

The same idea can be used on your second question.


Decidability of the language of DFAs accepting only odd-length strings Let $L$ be the language $\{\langle M \rangle : M\text{ is a DFA that accepts only odd-length strings}\}$.
Prove that $L$ is decidable.

How wrong is my answer?
Create a TM $T$ that decides $L$:

Create an equivalent input string $v$ that is in the language $L(M)$.

Give encoding to $T = \langle M, v \rangle$.

TM $T$ simulates $M$ on input $v$.

If TM $T$ halts and accepts, accept. Otherwise, reject.

I would like to know how off I am with my answer.

Every DFA can be simplified by a Turing Machine, so you can simplify the DFA you receive as input and compare it to the simplified DFA that accepts odd-length strings.

On input $M$:

Simplify $M$. Remove every unreachable state and transition from $M$ (disjoint from start state)
If the start state of $M$ is reject, and the only other state in $M$ is accept, and for every $w \in \Gamma, \exists$ a $w-arrow$ from accept to reject and from reject to accept, then accept. Otherwise reject.


Semantic information collections on the web. (Semantic Wikipedia) There are lots of technologies supporting semantic information markup even as wiki software.

I am wondering if there is any kind of broad information collection project like Wikipedia which features semantic markup of those information.

Google didn't bring up a project like this (only for very specific topics like software) or i just didn't find the right keyword.

Does anyone know about something like this?

DBpedia provides structured information from Wikipedia.

It uses RDF, and is one of the most known Linked Data datasets.

Also of interest (but not using information from Wikipedia) may be Freebase and OpenCyc.


Is the knapsack problem NP-hard when $v_i=i$? The knapsack problem is NP-hard and can be formulated as:
$$\begin{align}&\text{maximize } \sum_{i=1}^n v_i x_i,\tag{P1}\\&
\text{subject to } \sum_{i=1}^n w_i x_i \leq W,\\&\text{and } x_i \in \{0,1\}.\end{align}$$

What if $v_i=i$? Is it still NP-hard?

$$\begin{align}&\text{maximize } \sum_{i=1}^n ix_i,\tag{P2}\\&
\text{subject to } \sum_{i=1}^n w_i x_i \leq W,\\&\text{and } x_i \in \{0,1\}.\end{align}$$

I am trying to reduce (P1) to (P2). Given an instance of (P1), I create the same number of items, same weights. Now, I have to relate the solutions to (P1) and (P2).

No, this problem is in $\mathbf{P}$. The main point being that the sum of all the values is $1 + 2 \ldots + n = \frac{n(n+1)}{2} = \mathcal{O}(n^2)$, which is polynomial in the input size. Without the extra restriction of $v_i = i$, the sum of all the values could be exponential in the input size, as the values are represented in binary in the input.

So we can define $DP[i][v]$, where $1 \leq i \leq n$ and $0 \leq v \leq \frac{n(n+1)}{2}$, to be the minimum weight needed to get a value of at least $v$, using only the first $i$ items. If it cannot be achieved, we'll set $DP[i][v] = INF$. The final answer is the maximum $v$ such that $DP[n][v] \leq W$.

The DP values can be calculated as follows:

$DP[i][v] = \min(DP[i-1][v], w_i + DP[i-1][v - v_i])$.

The first term considers the possibility of the $i^{th}$ item not being chosen, and the second term is the possibility that it is chosen.

So the entire problem can be solved in $\mathcal{O}(n^3)$ time and $\mathcal{O}(n^3)$ space, which can be reduced to $\mathcal{O}(n^2)$ space by just reusing two arrays of size $\frac{n(n+1)}{2} + 1$.


How to prove the optimality of the "patience sort" algorithm? I was trying to understand how we can solve the Longest Increasing Subsequence (LIS) problem in O(N log N) time. I came across a sorting algorithm called the patience sort algorithm. To learn it I was going through this document:
https://www.cs.princeton.edu/courses/archive/spring13/cos423/lectures/LongestIncreasingSubsequence.pdf
I couldn't understand how the optimality was proved - i.e. why this algorithm leads to a minimum number of piles and correspondingly why it leads to the maximum length increasing subsequence.
In the above document from the weak duality principle (see pg. 5) we can understand that the number of piles ≥ length of any increasing subsequence.
Weak duality principle:

How can we use the above principle to prove the strong duality principle (see pg. 6)? If we can prove this, we will have proved the optimality.
Strong duality principle:

Thanks for the help.

The weak duality principle says that given any play of patience solitaire, the number of piles (at the end) is no less than the length of any Increasing Subsequence (IS) of the initial sequence of cards.
In particular, the min number of piles is no less than the length of the longest IS of the initial sequence of cards. That is, the weak duality implies the following direction of the strong duality:
$\quad$  Min number of piles $\ge$ max length of an IS.

Claim: We have
$\quad$  Min number of piles $\le$ max length of an IS.
Proof. Instead of proving using variables that represent general situations, I will use proving by illustration, which should convince a reasonable human.
Look at this picture, which is also embedded in the question. It shows the situation at the end of patience solitaire using greedy algorithm, starting with sequence 6,3,5,10,J,2,9,A,K,7,4,8,Q of spades.
Consider the queen of spades. At the time when it was to be placed on the last pile, it must appear later than all cards in the previous piles in the initial sequence (since cards were dealt in order). We must also have verified that it was larger than all uncovered cards in the piles before the last pile. In particular, it must be larger than the uncovered card in the second last pile, which was the 8 of spades. So, we have
$\quad$ $8,$ Q
as an IS of the initial sequence.
Consider the 8 of spades. At the time when it was to be placed on second to last pile, it must appear later than all existing cards in the piles to its left in the initial sequence (since cards were dealt in order). We must also have verified that it was larger than all uncovered cards to its left. In particular, it must be larger than the uncovered card immediately to its left, which was the 7 of spades. So, we have
$\quad$ $7, 8$
as an IS of the initial sequence.
Consider the 7 of spades. At the time when it was to be placed on third to last pile, it must appear later than all existing cards in the piles to its left in the initial sequence (since cards were dealt in order). We must also have verified that it was larger than all uncovered cards to its left. In particular, it must be larger than the uncovered card immediately to its left, which was the 5 of spades. So, we have
$\quad$ $5, 7$
as an IS of the initial sequence.
And so on.
In the end, combining all ISs obtained, we will have,
$\quad$ $3,5, 7, 8,$ Q,
as an IS of the initial sequence.
We can see that every pile contributes exactly one item to the IS. Hence, the number of piles is the same as the length of that IS. So, the number of piles (at the end of greedy algorithm) is at most the length of the longest IS of the initial sequence.
So, the min number of piles for all playing strategies, including the greedy algorithm, is at most the length of the longest IS of the initial sequence. $\quad \checkmark$.
The proof above is basically an expansion of the instruction, "follow pointers to obtain IS whose length equals the number of piles" in the lecture note from Princeton quoted in the question. By the way, we can also use the subsequence $3,5,10,$ J, A or one of many other subsequences to the same effect.

Combining both "$\ge$" and "$\le$", we should obtain the equality in the strong duality. Moreover, the proof above shows the greedy algorithm finds both numbers (or, that one number).

Exercise (easy):
Let $P_1, P_2, \cdots, P_k$ denote the piles we have obtained at the end of the greedy algorithm in its natural order. Show that card $c$ is in $P_i$ iff the longest IS of the initial sequence that ends at $c$ is of length $i$.


Efficiently enumerating all paths from i to j of given length in a graph I've been trying to efficiently solve this problem : given a integer p > 0 and a directed graph whose nodes are 0, ..., N-1, enumerate (not simply count) all the paths (not necessarily elementary) from a node i to a node j of length p. For instance, i->j is of length 2 if the edge i->j exists, i->k->j is of length 3, etc...). The graph is either given as an adjacency matrix or adjacency lists.
In my very special case, I'm searching for cycles 0->...->0 of given length, but I'm pretty sure I'm gonna need the more general case i->...->j.

Right now, I'm dynamically storing paths from k to j of length q in a matrix Z[k][q], and since I need Z[i][p], I first compute all the Z[j][p-1] for i->j, then append i to them.

The problem is that this approach uses an awful lot of memory and doesn't scale very nicely for large graphs. Any advice on this ?

It's not possible to solve this problem "efficiently". There can be exponentially many paths of a given length, so enumerating all of them is not feasible in large graphs.

Your dynamic programming approach is a pretty good one, though you might be able to improve it by not storing the paths explicitly but instead storing the paths as linked lists or using pointers, so that you only use $O(1)$ storage per path, letting paths share their common suffixes (if you do not do this already).


How to find infinite set $X$, which satisfies $T(n)=Ω(n)$ when $n∈X$ Consider the following recurrence relationship.
\begin{eqnarray}
T(n) &=&
\begin{cases}
    T\left(\displaystyle\frac{n}{2}\right) + 1, &n \ \mbox{is even number}& \\
    2T\left(\displaystyle\frac{n-1}{2}\right),　&n \ \mbox{is odd number}&
\end{cases} \nonumber \\
T(1) &=& 1
\end{eqnarray}
How to prove there exists an infinite set $X$, that when $n∈X$, $T(n)=Ω(n)$?

Here is the idea. When $n$ is even,
$$ \frac{T(n)}{n} \approx \frac{1}{2} \frac{T(n/2)}{n/2}. $$
In contrast, when $n$ is odd,
$$ \frac{T(n)}{n} \approx \frac{T(\lfloor n/2 \rfloor)}{\lfloor n/2 \rfloor}, $$
due to the factor 2 in the recurrence.
This suggests that in order to find your set $X$, you want to hit the "odd" case all the way. If $m = \frac{n-1}{2}$ then $n = 2m+1$, so if $m$ is a good choice, so is $n$. This suggests considering the sequence defined by $n_0 = 1$ and $n_{t+1} = 2n_t+1$, which is $1,3,7,15,\ldots$. As you can see, $n_t = 2^{t+1}-1$. The value of $T$ on this sequence is $1,2,4,8,\ldots$, that is, $T(n_t) = 2^t$.
We can now prove by induction that $T(2^{t+1}-1) = 2^t$. When $t = 0$, this just states the base case $T(1) = 1$. When $t > 0$,
$$
T(2^{t+1}-1) = 2T\left(\frac{2^{t+1}-2}{2}\right) = 2T(2^t-1) = 2\cdot 2^{t-1} = 2^t.
$$
Finally, note that
$$
T(2^{t+1}-1) = 2^t \geq \frac{1}{2} (2^{t+1}-1),
$$
and so you can take $X = \{ 2^{t+1}-1 : t \in \mathbb N \}$ as your infinite set.


FFT for expanded form of equation multiplication I know how to use the FFT for multiplying two equations in $O(n\,log\,n)$ time, but is there a way to use FFT to compute the expanded equation before simplifying?

For example, if you are multiplying $A(x) = 1 + 2x + 6x^2$ and $B(x) = 4 + 5x + 3x^2$ such that you get $C(x) = A(x) \cdot B(x) = 4 + 5x + 3x^2 + 8x + 10x^2 + 6x^3 + 24x^2 + 30x^3 + 18x^4$ without going directly to the simplified answer?

Furthermore, is it possible to use FFT to do this expanded form multiplication in $O(n\,log\,n)$ time? If so, can you show me how to apply FFT to this scenario?

The trivial algorithm that multiplies every monomial in $A$ by every monomial in $B$ takes time $O(|A| \cdot |B|)$ (where $|A|$ is the number of monomials in $A$ or $\deg A + 1$, depending on the representation), which is the same order of magnitude as the size of the output, and so optimal. You only need FFT if you want to actually compute the product $AB$. In particular, there is no way to compute your function in time $O(n\log n)$, simply because the length of the output is $\Omega(n^2)$.


Similarity of two monochromatic shapes I need to find out to what extent two shapes are similar. I mean I've got two vectors of points - and just that, no shadows, color or whatever - simplest case. Two triangles are the perfect example. Of course this has to work regardless of what the angle shift is and regardless of their scale (only aspect ratio matters).

I know there is SIFT method but this seems too complicated for this simple use case. Is there more suitable method?

Updated question

The problem is I don't know the optimal measure too. I mean I have to check if the two shapes are similar not in terms of size or angle but shape. So in terms of those triangles what matters is angle. Of course these shapes not need to be so trivial - they can consist of curves where no angles are present. So far I have found that I can use Procrustes algorithm to eliminate the offset, size and angle but what then? There is Fréchet distance but it seems it won't work for any composite shapes - a square with both diagonals is a good example. I mean this isn't going to work when there are several ways of drawing a figure, is it?

I was also wondering if those shapes can be represented by graphs (so finite number of points) and then I could see what is the length of minimal path going through both points (hamiltonian cycle?) - but I'm not sure if it would work in all scenarios.

While Procrutes algorithm will work with any shape I can think of, Frechet distance is more problematic.

It works well for any shape which can be drawn in one stroke so there are no two ways of doing this. A good example is a triangle

the problem is visible here

as there are more than 1 way of ordering the pixels to get the desired shape. Is there a way to handle this as well with Frechet algorithm? If not, what algorithm should be used?

One approach is to apply Procrustes analysis to superimpose the shapes, then use the sum of the squares distances between each pair of corresponding points (i.e., a L2 norm).  This is apparently sometimes called Procrustes distance.  Here you will use the set of "corners" of the shape as your set of points.

One disadvantage of this approach is that it is not robust in case one or a few points are deleted: maybe shape $S_2$ is the same as shape $S_1$ except that it is missing a single point.  If you want to be robust to this kind of situation, you could combine RANSAC with Procrustes distance.  Pick a random sample of 3 consecutive points from $S_1$, and 3 consecutive points from $S_2$; use Procrustes analysis to find the best map $M$ to superimpose those points; apply $M$ to $S_1$ to get $M(S_1)$, and use some kind of edit distance to measure the similarity between the vector of points of $M(S_1)$ and vector of points of $S_2$ (you might assign a large cost $c_\text{del}$ to deleting a point, a large cost $c_\text{ins}$ to inserting a point, and make the cost of matching a point $p$ to a point $q$ be the squared distance $||p-q||^2$ between the two points, then apply standard dynamic programming algorithms to compute the edit distance).  Now repeatedly apply this sampling procedure.  Keep the best map $M$ you find, where you can determine what you consider best (e.g., the lowest edit distance; or some other metric).

There are probably many other possible distances.  For instance, instead of the sum of squared distances, another possibility is to compute $\theta_i$ (the angle between $p_i,p_{i+1},p_{i+2}$ from the first shape) and $\theta'_i$ (the angle between $q_i,q_{i+1},q_{i+2}$ from the second shape), then some norm on these angles: e.g., $\sum_i (\theta_i - \theta'_i)^2$.  This too could be made robust to a few mismatched points using RANSAC.  There isn't enough information in the question to select between these, so without more knowledge, the best I can suggest is to simply try these on a set of examples and see which one seems to give results that most closely match what you are looking for.

None of this will work if your shapes $S_1$ and $S_2$ look "similar" but they have a very different number of points.  For instance, you mention the case where $S_1$ is a perfect square (with crisp edges where the angle between all 4 pairs of 3 points is exactly 90 degrees) made out of 20 points total and $S_2$ is a user-drawn square consisting of 300 points without crisp corners and no 3 consecutive points which align at 90 degree angle.  The methods above will not work at all for that kind of situation.

Incidentally, you mention the issue of shapes that can be drawn in one vs those that cannot.  I think your representation of a shape as a vector of points implicitly assumes that the shape can be drawn in one stroke (since the points appear in the vector in the order that they're visited by the stroke, and each point is assumed to be connected to the one after it), so if you want to deal with shapes that cannot be drawn in a single stroke, you'll probably need to find a different representation of the shape.


Proving building a balanced BST out of sorted array is $\Theta(n)$ I'm having hard time proving building a balanced BST out of sorted array is $\Theta(n)$

I got the following formula: $$T(n)=2T(\frac{n}{2})+\Theta(1)$$

I tried to prove it by induction but got stuck with the case in which $n$ is an odd number.

Is there a better way to prove it? Substitution wouldn't be considered a valid proof (I reached the closed formula using substitution of-course).

If you are allowed to use the master theorem then you can immediately conclude that $T(n)=\Theta(n)$ (since $n^{\log_2 2} = n = \omega(1)$).

If you are not allowed to use the master theorem then you can write this recurrence instead:
$$
T(n) \le 2T(\lfloor n/2 \rfloor) + c,
$$
where $c > 0$ is an absolute constant and $T(1) \le c$.

Then you can prove by induction that $T(n) \le 2cn - c$.
The base case is $n=1$ and is trivial since $T(1) \le c = 2cn - c$.
Consider now $n>1$ and suppose that the claim holds up to $n-1$, we will prove that it also holds for $n$:
$$
T(n) = 2T(\lfloor n/2 \rfloor) + c \le 2(2c\lfloor n/2 \rfloor-c) + c \le
2cn - 2c +c=2cn-c.
$$


Scheduling to minimize the truncated gaps I have a single job of unit length, a set of $n$ slots, and a budget of $B$ units. If the job is scheduled at slot $t$, then it will consume $c(t)$ units of the budget $B$. If the job is not scheduled for a period of $x$ consecutive slots, then a penalty of $\lfloor x/2\rfloor$ occurs. The objective is to schedule the job in order to minimize the sum of penalties.

For example, for $n=12$, if the job is scheduled at slot 1, at slot 3, at slot 6, and at slot $12$, then the sum of penalties is $\lfloor 1/2\rfloor + \lfloor 2/2\rfloor + \lfloor 5/2\rfloor = 0+1+2=3$.

Is this problem NP-hard?

I am trying to reduce the knapsack problem to it. Transforming the values in the knapsack problem to the penalties is somehow difficult, because once the job is scheduled at $t$, the penalty is initialized.

The problem is polynomial-time solvable.
To avoid edge cases it is better to think that the job needs to be scheduled at time $0$ and that $c(0)=0$.

Let $OPT[t,p]$ be the minimum amount of budget that needs to be spent in order to schedule the job in the first $t$ slots with an overall penalty of at most $p$ and with the additional constraint that the job must be scheduled at time $t$.

Let $P(t', t) = \Big\lfloor \frac{t-t'-1}{2} \Big\rfloor$ be the penalty incurred if the job is scheduled at times $t'$ and $t > t'$ and is not scheduled at any time in-between.

Then $OPT[0,p] = 0$ and, for $t>0$:
$$
OPT[t,p] = c(t) + \min_{\substack{t'=0,\dots,t-1 \\ P(t',t) \le p}} OPT\left[t', p - P(t',t) \right]
$$

The minimum attainable penalty up to time $t$, with the constraint that the job is scheduled at time $t$, is then:
$$
\mu(t) = \min \{p \in \{1,\dots,\lfloor t/2 \rfloor\} \mid  OPT[t,p] \le B \}
$$

And the minimum attainable penalty for your problem is:
$$
\min_{t=0,\dots,n}  \left\{ \mu(t) + P(t,n+1) \right\}.
$$

Notice that there are at most $n \cdot (P(0,n)+1) = O(n^2)$ values $OPT[p,t]$ to compute.


Is it compulsory that every infinite set be non regular? I am confused regarding the statements provided by one of our faculty regarding
   "Is it compulsory that every infinite set is non regular
    though every finite set is a regular set".
Providing this  example:

  $$L= \{ 0^n 1^n | n>=0 \} $$     its  formal as $\Sigma=\{0,1\}$ and
  thus we've a formal meaning as $\{\epsilon,01,0011,000111,....\}$

                               no. of 0's = no. of 1's

The above language should be a non-regular as we need to keep track the value of 'n' in order to make it a equal no, of 0's & 1's and FA has no memory.

or am i mistaken.

Please, provide some oxygen regarding this confusion.thank you.

You must have misunderstood the comment, since the set $\Sigma^*$ is infinite and regular. The correct notion of "infinite" is given by the Myhill–Nerode theorem. Every language is associated with a set of states, and a language is regular iff the set of states is finite.

A state in a language $L$ is a set of strings $S$ that are interchangeable with respect to $L$ in the sense that for all words $x$, either all words of the form $sx$ (where $s \in S$) are in $L$, or all are not in $L$. In the example $L = \{0^n 1^n : n \geq 0\}$, the states are $\{ 0^{m+n} 1^n : n \geq 0  \}$ for each $m \geq 0$, all other words forming another state. You can see that there are infinitely many states, and so the language is not regular.

Every regular language has a DFA whose states correspond to the states described above. This DFA is known as the minimal DFA. A "minimal DFA" for $\{ 0^n 1^n : n \geq 0 \}$ would need to have infinitely many states, since the DFA would have to remember how many zeroes it has seen so far, or more generally how many ones it expects at this point (if the next symbol is a one). No finite automaton can remember that much information, so the language isn't regular.


Algoritm to sample an even subgraph of a graph In some problems related to the Ising model in physics and mathematics the following problem comes up:
Suppose I have a graph $G$. Then an even spanning subgraph of $G$ is a subgraph where you keep all the vertices and some of the edges such that each vertex has even degree.There is always at least one since the empty spanning subgraph is always even. Now, among all the even spanning subgraphs of $G$ I want to sample one uniformly at random.
Is there an fast and preferably easy to implement algoritm to do that?
Is this a well studied problem? If yes: could you point me to some references?
Some background: The space of even spanning subgraphs of a graph has some nice structure since if you have two of them then you can take their symmetric difference and it will still be an even spanning subgraph. This means that it is a vector space of the field $\mathbb{F}_2$ and you can pick a basis of that space - in particular this shows that the number of even spanning subgraphs is always a power of 2.
I wonder how difficult it is to find the basis elements since if you have some you just flip coins for each and take the symmetric difference of all the graphs where you get head.
Another point is that there might be a smart low-tech randomized way to do this.

Based on this answer from Math.SE you can construct a simple algorithm for uniformly sampling an even spanning subgraph.
Assume without loss of generality that $G$ is connected (otherwise you can apply the sampling algorithm to each connected component and return the union). Let us denote $G$'s vertices by $v_1,...,v_n$, and given $i>1$ let $P_i$ be some simple path from $v_1$ to $v_i$ (such path exists since $G$ is connected).
Given $A\subseteq\{2,..,n\}$ and some spanning subgraph $H$, define $H^A$ to be the graph obtained from $H$ by flipping the edges in each $P_i$ for $i\in A$, i.e. if $H$ is represented by $x_H\in\mathbb{F}_2^{|E|}$, and $P_2,...,P_n$ are represented by $x_2,...,x_n\in \mathbb{F}_2^{|E|}$, then $H^A=x_H\oplus\left(\bigoplus\limits_{i\in A} x_i\right)$. Note that for $A\neq B$ we have $H^A\neq H^B$. $H^A=H^B$ for some $A\neq B$ iff there exists nonempty $A\subseteq\{2,...,n-1\}$ such that $\bigoplus\limits_{i\in A}x_i=0$ (i.e. the vectors $x_i$ are dependent). Suppose $i\in A$, and let $G_A$ denote the spanning graph represented by $\bigoplus\limits_{j\in A}P_i$. Flipping the edges of any path $P_j$ only changes the parity of the degrees of $v_1$ and $v_j$. Thus, as $G_A$ is obtained by starting with the empty graph and flipping the edges of every $P_j$ with $j\in A$, $deg_{G_A}(v_i)$ is odd, which means $G_A$ is not the empty graph.
Now we can define the following equivalence relation on subgraphs of $G$, $H_1\sim H_2\iff\exists A\subseteq\{2,..,n\}:H_2=H_1^A$. Based on the previous observation, each equivalence class contains $2^{n-1}$ different elements.
The second key observation is that each equivalence class contains a unique even subgraph of $G$. Given a subgraph $H$, for any vertex $v_{i>2}$ with odd $deg_H(v_i)$ flip the edges in $P_i$. This only changes the parity of the degrees of $v_1,v_i$ in $H$. Proceed in this manner until $deg_H(v_2),...,deg_H(v_n)$ are all even. Since the sum of the degrees is always even, $deg_H(v_1)$ must now be even too, which means that the newly obtained equivalent graph $H'$ is an even spanning subgraph. For uniqueness, suppose for the purpose of contradiction that $H\sim H'$ are two different equivalent even spanning subgraphs of $G$, i.e. $H'=H^A$ for some non empty $A\subseteq\{2,..,n\}$. Let $i\in A$ be some path index in $A$, then clearly $deg_{H'}(v_i)$ is odd, since $deg_{H}(v_i)$ is even and its parity is only changed while flipping the edges of $P_i$.
This was covered in the linked answered by Yly. Now you have a simple sampling algorithm that requires $O(|V|+|E|)$ preprocessing time. Execute BFS from $v_1$ to obtain the paths $P_2,...,P_n$. Sample uniformly a spanning subgraph $H$, now for each $v_i$ with odd $deg_H(v_i)$ flip the edges of $P_i$. In this manner you find the unique even spanning subgraph in $[H]$, using $O(n^2)$ time. Uniformity follows from the fact that all equivalence classes have the same size, and each contains a unique even spanning subgraph.


Dijkstra's Algorithm Invariant I am trying to prove the first assertion in the following code, taken from notes of Damon Wischik:
def dijkstra(g, s):
    for v in g.vertices:
        v.distance = ∞
    s.distance = 0
    toexplore =  PriorityQueue([s], sortkey = lambda  v: v.distance)

    while not toexplore.isempty():
        v = toexplore.popmin()
        # Assert: v.distance is the true shortest path distance between s and v
        # Assert: v is never put back into toexplore
        for (w, edgecost) in v.neighbours:
            dist_w = v.distance + edgecost
            if dist_w < w.distance:
                w.distance = dist_w
                if w in toexplore:
                    toexplore.decreasekey(w)
                else:
                    toexplore.push(w)

Base case: The estimate of the source node is correct when it is popped.
Inductive step: Consider the shortest path from the source node $s$ to some destination node $d$,
$$ s \to v_1 \to v_2 \to \cdots \to v_k \to d. $$
Assume that the estimates for $s,v_1,v_2,\ldots,v_k$ are correct when they are popped.
When $d$ is popped, we can be sure that $s, v_1, v_2, \dots, v_k$ were popped prior to that as their true shortest distances from the source $s$ are lower than that of $d$. In particular, when $v_k$ is popped, we are sure that the edge $(v_k, d)$ will be relaxed since relaxing the edge $(v_k, d)$ gives us the true shortest distance from the source to the destination, which is definitely an improvement on any prior estimate of D. Hence D's estimate is the true shortest distance from the source when it is popped.
Hence the assertion is true.
Is there a flaw in my proof?

I believe your proof is a bit incomplete, since you do not guarantee the shortest path to $d$ is a path which only traverses the popped nodes. You can add this part to make you proof complete :
Assume the shortest path to our vertex $d$ is the path $s \to u_1 \to u_ 2 \to \cdots \to u_l \to x \to \cdots \to  d$
Where nodes $s, u_1, u_2, \cdots, u_l$ are popped earlier, therefore their distances are correctly determined, and $x$ as the first vertex which is not popped yet. Since the edges are nonnegative, therefore $dist_x \le dist_d$ (let $dist_v$ be the actual distance of the vertex $v$). Since $x$ is the first vertex which is not popped yet, it's distance should now have been determined by relaxing $(u_l, x)$. We assumed $d$ has the smallest estimate, let it be $est_d$, so $est_d \le est_x = dist_x$, and thus $est_d \le dist_x \le dist_d \implies est_d \le dist_d$, and since estimate can never be less than actual distance, $est_d = dist_d$.
I hope my answer was helpful.


List of all possible reasoning tasks - satisfiability and theorem proving only? What is the exhaustive list of reasoning tasks? As far as I can understand, then any logical reasoning reduces to 2 tasks only: 1) satisfiability problem (finding the assignment of the variables) and 2) theorem proving (deducing general statement from the other statements).

https://en.wikipedia.org/wiki/Logical_reasoning lists 3 types of reasoning: 1) deductive; 2) inductive; 3) analogical. But, as far as I understand, then each of those types reduces to some methods/heuristics of forming some statements and again - in the final step one of two reasoning tasks is applied - SAT or theorem proving.

Logic programming in essence if SAT problem as well (at least for stable model semantics/fixed poing semantics): one compiles the list of implicational statements and then tries to find the assignment of variables under which no internal dynamics happen further.

So - are there only those 2 reasoning tasks - SAT and theorem proving? Of course, there are many logics in which those tasks can be completed, but that is other problem, see, e.g. https://kwarc.info/people/frabe/Research/rabe_howto_14.pdf and https://uniformal.github.io/

The question is important when one tries to implement cognitive architecture (https://en.wikipedia.org/wiki/Cognitive_architecture and http://bicasociety.org/cogarch/architectures.php) - one should be sure about the exhaustive list or reasoning tasks to certify that some implementation achieves some generality.

My question is of even more important when one considers neural networks. One can ask - what is the exhaustive list of reasoning tasks that neural networks should be able to do? Of course, generally there are evidence about Turing completeness of neural networks, but my question concerns the cognitive/reasoning subset of general computations.

There is no exhaustive list of reasoning tasks, as the phrase "reasoning task" does not have a precise definition.

Don't put too much weight on categorizations.  They're a descriptive tool that might help you get a high-level overview of a field, but they're inherently subjective, incomplete, and imperfect.  There's tons of work on artificial reasoning, and there are many ways one could potentially put a mental framework around it -- there's no one right answer about how to do that.


Computing theory: can a single node be a subgraph? Can a single node be considered a subgraph?

For example, if I had this graph, G:

X-----Y

and I deleted Y, leaving me with the graph

X

is this a subgraph (induced) of G?

What about the following argument?

Assume a single node can be considered a graph. Any graph is an induced subgraph of itself. Therefore, a single node graph has a single-node induced subgraph.

Though this is only valid if a single node can be considered a graph.

In computing theory, what is the generally accepted norm?

What about the following argument?

  Assume a single node can be considered a graph. Any graph is an induced subgraph of itself. Therefore, a single node graph has a single-node induced subgraph.

  Though this is only valid if a single node can be considered a graph.

That's completely circular. If a single node can be a graph, you can ask about its subgraphs and, sure, every graph is a subgraph of itself. But if a single node can't be a graph, it doesn't make sense to ask about subgraphs of something that isn't a graph.

In general, a single vertex is considered to be a graph, referred to as the "trivial graph".  However, it's something of a special case in that it's often an exception to statements one might wish to make when proving things.  For example, every connected graph contains at least one edge... except for the trivial graph; every graph has a proper subgraph... except for the trivial graph; etc. Because of this, writers often exclude the trivial graph from consideration. So, for example, in the "notation" section of a graph theory paper, you often see a statement such as "Except where stated otherwise, we assume that every graph contains at least one edge".

In this respect, asking whether the trivial graph is a graph is a bit like asking whether zero is a natural number. Some people will jump up and down and insist that it is; some people will jump up and down and insist that it isn't; the best plan is to say that it is or isn't according to what makes your life easiest in any particular situation.


Build Automatic Speech Recognition (ASR) from scratch I want to build a Automatic Speech Recognition (ASR) engine for myself, but I've no idea from where to start.

I've read that most ASR's are build upon Hidden Markov Models, but also I've read that HMM is limited somehow and a better approach is to build a ASR upon Machine Learning features.

Overall I am confused.

Can someone recommend me books on topics from which I can start?

Thanks (:

I want to build a Automatic Speech Recognition (ASR) engine for myself, but I've no idea from where to start.

Start with trying existing open source speech recognition system, learn how they work, play with them. Check http://cmusphinx.sourceforge.net.

  I've read that most ASR's are build upon Hidden Markov Models, but also I've read that HMM is limited somehow and a better approach is to build a ASR upon Machine Learning features.

HMM which provide time variance is still a reasonable model for speech, most of the system use it in one form or another. Limitations of HMM exist, but you do not need to care about them on that level.

You can implement a basic speech recognition system without HMM. For example check

http://de.mathworks.com/company/newsletters/articles/developing-an-isolated-word-recognition-system-in-matlab.html

That would be enough for "yes" and "no" discrimination. For any more serious use you will need HMM.

  Can someone recommend me books on topics from which I can start?

There are two good books on topic:

A basic guide to start:

http://www.amazon.com/Spoken-Language-Processing-Algorithm-Development/dp/0130226165

A modern state of the art

http://www.amazon.com/Automatic-Speech-Recognition-Communication-Technology/dp/1447157788/


Monte Carlo: what is a seed? I have reached a chapter in the notes I am following where a program written in C++ is using a Monte Carlo method to estimate $\pi$. It mentions a 'seed', but does not say what this is. I have tried finding out what a seed is online, but I only seem to get results about 'why you should/shouldn't use a fixed seed', and unfortunately they have left me none the wiser as to what a seed actually is.

What is seed in this context?

The seed is an initial number of the pseudorandom number generator(PRNG) which is in fact fully deterministic. It returns a sequence of numbers that looks random enough for many purposes, but always generates the same sequence for given value.

In order to make simulation non-repeatable (returning always the same value) they advice different initial value for every simulation (this is what non-fixed seed means).

Image taken from here


Is MAX-averageSAT a well-known problem? Is there any variant of the Boolean SAT or Max-SAT problem that has a flavor of maximizing or minimizing the average of the weights of the satisfied clauses of a WCNF formula? Any literature on an optimization problem of similar flavor would be appreciated. Thanks.

This problem is new to me.  It has similar hardness to weighted MaxSAT; there is a polynomial-time Turing reduction in both directions.  Here is a key fact:

Let $\varphi,(w_1,\dots,w_n)$ denote a weighted CNF formula, where $w_1,\dots,w_n$ are the weights on the clauses.  Then the following two conditions are equivalent:

There is an assignment to $\varphi,(w_1,\dots,w_n)$ so that the average of the weights of the satisfied clauses is at least $a$.
There is an assignment to $\varphi,(w_1-a,\dots,w_n-a)$ so that the sum of the weights of the satisfied clauses is at least $0$.

This lemma yields an equivalence between weighted MaxSAT and weighted MaxAverageSAT.
For instance, if you have an instance of weighted MaxAverageSAT that you want to solve, here is how you can solve it using an off-the-shelf solver for weighted MaxSAT.  Basically, use binary search on the average $a$.  Given $a$, you can test whether it is possible to achieve an average at least $a$, by using the solver on $\varphi,(w_1-a,\dots,w_n-a)$ and checking whether it gives you an assignment where the sum of the weights is at least $0$; you can then use this to determine whether to increase $a$ or decrease $a$ in the binary search.  After polynomially many iterations of binary search, you'll narrow it down to a small enough range that you can uniquely determine the maximum achievable average.


Is it standard for VMs to run *= computationallyHeavyFunction() if the left hand side is 0? What is the standard way for VMs to deal with 0 *= computationallyHeavyFunction()? Given that once the VM sees that left hand factor is 0, it would know that the result of computationallyHeavyFunction() would not matter, is it standard for VMs to still compute computationallyHeavyFunction() or do they tend to omit that computation and just evaluate as 0?

Edit: After answer, I think I misphrased the question. I'll rephrase a bit and replace computationallyHeavyFunction() that has unknown factors. If VMs see 0 * (1-1/veryLargeNumber)^anotherVeryLargeNumber, do they tend to not compute right factor? Assuming they rely on squaring algorithm, quite computation heavy with O(log2(anotherVeryLargeNumber)).

Optimizing 0 * f(…) is correct only if f has no side effect and its result is known to be finite. If f has side effects, they must be executed even if the result does not matter. If f might return a result such as NaN or infinity then the result of the calculation might be NaN and not 0.

A VM that is optimized for numerical or symbolic calculations and that has access to enough type information to know that f has no side effects and has a finite result would presumably optimize the call away. Any other type of VM would not do this optimization.


Is #P closed under exponentiation? modulo? The complexity class $\newcommand{\sharpp}{\mathsf{\#P}}\sharpp$ is defined as

$\qquad \displaystyle \sharpp = \{f \mid \exists \text{ polynomial-time NTM } M\ \forall x.\, f(x) = \#\operatorname{accept}_{M}(x)\}$.

It is known that $\sharpp$ is closed under addition, multiplication and binomial coefficient. I was wondering if it is closed under power. For example, we are given a $\sharpp$ function $f$ and another $\sharpp$ function $g$. Is it true that $f^{g}$ or $g^{f}$ are $\sharpp$ functions as well?

This is edit after the question has been answered.

Is ($f$ modulo $g$) a $\sharpp$ function? How about when we are given a $\newcommand{\FP}{\mathsf{FP}}\FP$ function $h$. Then is ($f$ modulo $h$) a $\sharpp$ function?

No.  Take $f(n)=g(n)=2^n$ for a counterexample.


Efficient algorithm to find subgraph I have a really nasty problem (for me) at hand and I was wishing some of you may know an efficient algorithm to solve it. Thanks to all of you in advance.

My problem

I have a set of elements (that I would describe as a graph) that may be of three categories:

Provider nodes
Consumer nodes
Interconnections between nodes

Each node can have one or more interconnections tied to it.

My goal is to correlate each consumer to a set of providers to whom is connected, both directly through an interconnection or indirectly through multiple hops from one consumer to the other. Indirect interconnections can't go through a provider, only a consumer.

Our current approach is to analyze this graph starting with providers, hopping through interconnections recursively until a all unvisited consumers are hit. We then take this "island" of consumers bordered by a set of producers and assign these producers to each consumer we visited.

The approach gave us the right results but at a very high cost, in terms of time spent analyzing the graph.

Do you have any suggestion for an algorithm that can come in handy to solve this problem? I would also consider alternative data structures to hold our input (right now they are a set of tuples in a relational database describing the correlation between nodes and interconnections).

OK, it sounds like your problem is the following:

  You have an undirected graph.  Each vertex is either a consumer or a producer.  Say that a consumer $c$ is connected to a producer $p$ if there is a path from $c$ to $p$ where all intermediate nodes are consumer nodes.  You want to output a list of pairs $(c,p)$ where $c$ is connected to $p$.

This problem can be solved in a straightforward, clean, and efficient manner, using an algorithm for connected components.  Here is the algorithm:

Remove all of the producer nodes, keeping only the consumer nodes and the edges from a consumer node to a consumer node.
Compute connected components on this smaller graph.  Let the connected components be $C_1,\dots,C_k$.
Now, back in the original graph, shrink all of the consumer nodes in the same connected component into a single node.  Thus, we get an edge from connected component $C_i$ to producer $p$ if there is any consumer $c$ in $C_i$ that has an edge to $p$.
This resulting graph now describes the connectivity relationship.  In particular, for each consumer $c$ and each producer $p$, $c$ is connected to $p$ if and only $C_i$ has an edge to $p$, where $C_i$ is the connected component containing $c$.

For instance, to output the list of all pairs $(c,p)$ that are connected, you can do the following:

For each connected component $C_i$, for each provider $p$ that has an edge from $C_i$ to $p$, for each consumer $c$ in $C_i$, output the pair $(c,p)$.

This algorithm runs in linear time.  The running time to compute the connectivity graph (produced in steps 1-3) is $O(m+n)$, where $n$ is the number of nodes and $m$ is the number of edges (interconnections) in the original graph.  The running time in step 4 could be as large as $\Theta(n^2)$, since there might be as many as $\Theta(n^2)$ such pairs.  However, here's what we can say.  If the correct output has length $\ell$ (i.e., there are $\ell$ pairs $(p,c)$ that are connected), then step 4 will have running time $O(\ell)$.

Therefore, the total running time is $O(m+n+\ell)$, i.e., linear in the sum of the size of the input and the size of the output.  This is as fast as you could possibly hope for.

If you don't need to output the set of all pairs $(c,p)$ explicitly, but you just want a compact representation of this connectivity information, you can use the graph computed in steps 1-3 as that compact representation.  Then the running time is $O(m+n)$.


How does the CPU receive, process and output information? I was studying the I/O process of a PC...and I think I understood it..but not very much so I will type what I understood giving an example..and I hope that I got it right

e.g. typing with a keyboard

First: The Input, and that is done simply by the keyboard..

Second: The information gets to the CPU in binary, but the logic unit doesn't understand it so the Control Unit gets the Instructions saved in the RAM by the CU it self..
then the instructions is sent to the Logic Unit through the CU

Finally:The Logic Unit understands it that time and do some operations that produces some Outputs.
The outputs are saved in the RAM, and viewed on the screen

So, please tell me if that's right or if I missed the whole thing..
Thank you very much in advance.

From what I know, and I might be slightly wrong here,
each device (Mouse, keyboard, screen etc') has a device driver.

The device driver is the one handling the communications with the CPU.
Where usually, each device has its own Data register, Status register and Command register (Where the register are basically mapped areas in memory for the device itself).

What happens is when any action is made (i.e pressing a key on the keyboard) the device "updates its status" to ready to send and stores the data it needs to send in some area of memory specifically saved for it, and then interrupts the CPU to perform the action needed.

The CPU sends "Ack" as acknowledgement and accepts the interrupt, executes it, and goes back to what it did before. (Only if the status is ready, otherwise does nothing).

(There are other methods such as busy wait that the device can notify and interact with the CPU).


Maximizing quantities/length in buckets to match each other I have a use case, real one, and I'm trying to come up with an efficient maximization algorithm to solve it.

I'll try to simplify, with a simple analogue, and after will explain the real world use case:

Analogue:

Imagine you have 2 buckets of springs.
Each spring has 2 properties: resting length, and maximum stretching length.
Some springs are basically just rods, and resting length = maximum stretch length.

Your job is to maximize length of joined springs (& rods) in each bucket, such that the length of the 2 joined springs in the 2 buckets match exactly.

Example:

A bucket of springs $S_k$ is a non-empty multiset of intervals $[i,j]$, where $i$ denotes the "resting length", and $j$ denotes the "maximal stretch length".  For example, if the two buckets are

$$\begin{align*}
S_1&=\{[2,4],[2,4],[4,4]\} \\
S_2&=\{[1,1],[2,4],[13,15]\}
\end{align*}$$
then the maximum achievable length is 5, since $2 + 3 = 1 + 4$ and $2 \in [2,4]$ and $3 \in [2,4]$ and $1 \in [1,1]$ and $4 \in [2,4]$.

Note that if the last spring in $S_2$ would have been $[12,15]$ instead of $[13,15]$, the maximum length would have been $12$ (by the choice $4+4+4=12$).  But since lengths in each bucket must match exactly, we end up with only $5$.

Real (boring) problem:

My use case is from the finance world. I'm trying to match buy orders & sell orders for different amounts. Some of the orders can be partially accepted, whilst other must be strictly accepted or rejected. The orders I can partially accept, also specify the minimum amount it must be accepted with.
Each order is a "spring" in the analogy, where "resting length" is minimum accepting amount, and "maximum stretching length" is the full amount. The 2 buckets are the buy orders & sell orders.
Also, note that for now I've been asked to maximize amounts, but a further complication of the algorithm would be to maximize both amount & price. Either by preferring amount over price, and when there's a choice, to prefer the better price (lower for buy, higher for sell), or by maximizing total revenue (sell price * amount - buy price * amount).

Just for fun

Try to generalize to any number of $n>1$ buckets.  In a valid solution, all buckets must end up with the same total length.

P.S. To be clear, I haven't solved it efficiently myself. And I am still looking for an efficient way to do the matching.
I'm interested in the subset of orders, and not just the maximal amount that can be matched.
Also, this kind of reminds me of bean packing problem (NP complete), because of the strict orders (rods), but not quite. Even if it is NP complete, I'm still gonna implement it (inefficiently), since mostly it'll work on a small number of orders (pretty sure it's gonna be OK). But I have a hunch there's a dynamic algorithm somewhere that can be more efficient.

I would solve this problem with an SMT solver like z3. Example in Python:

import z3

buckets = [
    [(2, 4), (2, 4), (4, 4)],
    [(1, 1), (2, 4), (13, 15)],
]

solver = z3.Optimize()

m = z3.Int("m")

for bnr, bucket in enumerate(buckets):
    springs = []
    for b, (lo, hi) in enumerate(bucket):
        include_spring = z3.Bool(f"is{bnr},{b}")
        spring = z3.Real(f"s{bnr},{b}")
        solver.add(lo <= spring)
        solver.add(spring <= hi)
        springs.append(include_spring * spring)

    solver.add(z3.Sum(springs) == m)

solver.maximize(m)
solver.check()

model = solver.model()
print(solver.model())

The constraints are easy to express and SMT solvers are really quite powerful nowadays.


Where are back edges in a DFS tree? As I understand it when doing a DFS run when every new node is discovered and edge is added to the DFS tree from the parent of the new node to the new node. If that's the case how are back edges are created?

The terms forward, back and cross edges classify edges in the original graph with respect to the depth-first search, so they don't appear in the DFS tree itself. Different DFS runs may yield different classifications. They are useful in some algorithmic contexts.

You can read more on Wikipedia.


Checking Divisibility Using Minimal Bits Suppose we're given an infinite stream of integers, $x_1, x_2, \dots$.

  a) Show that we can compute whether the sum of all integers seen so far is divisible by some fixed integer $N$ using $O(\log N)$ bits of memory.

  b) Let $N$ be an arbitrary number, and suppose we're given $N$'s prime factorization: $N = p_1 ^{k_1} p_2 ^{k_2} \dots p_r ^{k_r}$. How would you check whether $N$ divides the product of all integers $x_i$ seen so far, using as few bits of memory as possible? Write down the number of bits used in terms of $k_1, ..., k_r$.

For part a), we know that for any prime $p \ne 2, 5$, there is an integer
$r$ such that in order to see if $p$ divides a decimal number $n$, we break $n$ into $r$-tuples of decimal digits, add up these $r$-tuples, and check if the sum is divisible by $p$. But $N$ is a fixed integer, and not necessarily a prime. Is there some way to connect the theorem above to any arbitrary integer?

For part b), for the product of $x_i$ (call it $y$) is divisible by $N$, then $y$ must be divisible by each $p_i ^{k_i}$ (call it $a_i$. Since we're given the prime factorization, we can just check if $y$ is divisible by $N$ by dividing $y$ by each $a_i$ and halting when it fails, right? Would this result in using $k_1 \times \dots \times k_r$ bits?

Am I at least on the right track, or am I completely wrong? Any help understanding this problem would be tremendously helpful.

For part (a), the idea is that it suffices to store the sum of all integers seen so far modulo $N$. Since this is an integer between $0$ and $N-1$, storing it requires only $\lceil \log_2 N \rceil$ bits.

For part (b), let $x_i = p_1^{a_1(i)} \cdots p_r^{a_r(i)} q$, where $q$ is relatively prime to $p_1,\ldots,p_r$. Then $x_1 \cdots x_m$ is divisible by $N$ iff $a_j(1) + \cdots + a_j(m)\geq k_j$ for $j=1,\ldots,r$. Hence it suffices to store $\min(a_j(1)+\cdots+a_j(m),k_j)$ for $j=1,\ldots,r$. The $j$th number is between $0$ to $k_j+1$, and so requires $\lceil \log_2 (k_j+1) \rceil$ bits, for a total of
$$
\sum_{j=1}^r \lceil \log_2(k_j+1) \rceil \text{ bits}.
$$
(In fact, we can be a little bit smarter and use only $\left\lceil \sum_{j=1}^r \log_2(k_j+1)\right\rceil$ bits, but it's not such a big difference.)

In both cases, it is possible to show that the amount of bits stated is also required. For example, in part (a), at any given point in time you need to distinguish between $N$ different states, correspond to the current sum modulo $N$. Indeed, all sequences $0;1;\cdots;N-1$ must lead to different memory states, since if $i$ and $j$ led to the same state, then we would not be able to distinguish between the sequences $i,N-i$ and $j,N-i$, although one of them satisfies the divisibility property and the other doesn't.


Smallest set of balls under hamming distance that covers all $n$-bit strings Suppose we defined a set $S = \{x\mid0 \leq x \leq 2^n-1\}$. Notice that all element in $S$ can be represented with a $n$-bit binary string. Now consider subset $S_i$ such that,

$$S_{y_i} = \{y \in S\mid d(y,y_i) \leq t\},$$

where $y_i$ is the $i$th element of $S$ and $d(y_j,y_i)$ is the hamming distance between the binary representation of $y_j$ and $y_i$ and $t < n$.  Obviously, $S_{y_i} \subset S$.

Consider the family ${\Phi = \{S_0, S_1, \ldots, S_{2^n-1}\}}$. Find ${\phi \subset \Phi}$ with smallest cardinality, so that the union of the all elements in $\phi$ is equal to original set $S$ (notice that, each element of $\phi$ is a subset of $S$).

I was not be able to solve. However, I believe it is possible to find $\phi$ with an efficient algorithm rather than using an exhaustive search.

Edit: An example-

Assume $n =3$ and $t = 1$

Then $S = \{0, 1, 2, 3, 4, 5, 6, 7\}$

So, $S_0 = \{y \in S\ |\ d(y,0) \leq 1;\} = \{0, 1, 2, 4\}$

Similarly, $S_1 = \{0, 1, 3, 5\}$; $S_2 = \{0, 2, 3, 6\}$; $S_3 = \{1, 2, 3, 7\}$; $S_4 = \{0, 4, 5, 6\}$; $S_5 = \{1, 4, 5, 7\}$; $S_6 = \{3, 4, 6, 7\}$; $S_7 = \{3, 5, 6, 7\}$;

So, $\Phi = \{S_0, S_1, S_2, S_3, S_4, S_5, S_6, S_7\}$;
Now, for this case the $\phi = \{S_2, S_5\}$ as $S_2 \cup S_5 = S$

The object you are looking for is known as a covering code. Finding the smallest covering code for a given radius is generally a difficult problem, just like its more well-known dual problem, error-correcting codes.


How to enumerate a product set? I am coding a procedure that takes an integer $d$, and generates $d$ finite lists $X_1 \ldots, X_d$ of elements. I would then like for it to output a list of the elements in the product set $X_1 \times \cdots \times X_d$.

I can't use nested for-loops because $d$ can vary so I wouldn't know how many to nest. I'm sure there's a totally standard solution to this problem, but I don't know enough to search for it successfully either here on online.

For what it's worth, here's one dumb solution I came up with. Let $b$ be the maximum cardinality of the sets $X_i$. Then run a single loop for $n$ running from $0$ to $b^d$; for each $n$, write it in base $b$ and use the $i^{\rm th}$ digit to read off the element of $X_i$ corresponding to that digit (and ignore if any of those digits are too big for the cardinality of the corresponding set). This will work, but feels like a pretty stupid solution.

What's the standard way of doing this?

There is a legitimate mathematical question here: find an encoding or $X_1\times X_2\times\cdots\times X_d$. The idea is to use mixed base. As you note, if all sets have cardinality $b$, then you can use base $d$ encoding. If the sets have different cardinalities, then you use a mixed base approach. Suppose $|X_i| = b_i$. The choice of elements $c_i \in X_i$ (say $0 \leq c_i < b_i$) can be encoded as follows:
$$ c_1 + b_1 c_2 + b_1 b_2 c_3 + \cdots + b_1 b_2 \cdots b_{d-1} c_d. $$
Every number in the range $0$ to $b_1 b_2 \cdots b_d - 1$ encodes a unique choice of element from $X_1\times X_2\times\cdots\times X_d$.

There is also a programming question here: how to generate the list. The idea is to use a generalization of a binary counter, familiar for students of amortized complexity. There is an array $c$ of length $d$, where $c_i$ is going to encode a choice of element in $X_i$. At each step, we update this "counter" by increasing it by 1. We start by increasing $c_1$ by 1. If $c_1 < b_1$, everything is fine. Otherwise, there is carry: we set $c_1 = 0$, and increase $c_2$ by 1. And so on. The resulting sequence is a lexicographically ordered list of elements in $X_1\times X_2\times\cdots\times X_d$. The amortized complexity per step (assuming $b_i > 1$ for all $i$) is $O(1)$.

Notice the similarity between the encoding in the first half and the algorithm in the second half.


prove that in binary heap buildheap function does at most 2N-2 comparison prove that in binary heap buildheap function does at most 2N-2 comparison
I don't know how should I prove it I need some hint thanks.
buildheap procedure: we have n element and we build a heap at first and then we start from the first node which is not leaf(floor of n/2) and for each step we have 2 comparison(each node should be compared with min of children and to find min also there is 1 comparison)
so we compare this node and we go back until we get to root(and all of these steps are recursive and keeps continuing till we reach the node or right place of node)
buildheap():
    for i ← size / 2 till i > 0
        Max-Heapify(i)
        i ← i-1

Max-Heapify(A, i):
    left ← 2×i
    right ← 2×i + 1
    largest ← i

    if left ≤ length(A) and A[left] > A[largest] then:
        largest ← left

    if right ≤ length(A) and A[right] > A[largest] then:
        largest ← right

    if largest ≠ i then:
        swap A[i] and A[largest]
        Max-Heapify(A, largest)

I wrote number of comparisons:
node          comparison
 1                 0
 2                 1
 3                 2
 4                 3
 5                 6
 6                 7
 7                 8
 8                 11
 9                 14

I think the worst case is when we have new level with one node(3,5,9,.. node because it has 2 less than the most we have)
but I have another idea:
we have n/2 node which don't move down
n/4 moves one level down
n/8 moves 3 level down
and each moving from level to level needs 2 comparison
so we have
$\frac{n}{2} \times 0 + \frac{n}{4} \times 1 + \frac{n}{8} \times 2 + .... = n \times (\frac{1}{4} + \frac{2}{8} + \frac{3}{{16}} + \frac{4}{{32}} + ...)$
sum of $(\frac{1}{4} + \frac{2}{8} + \frac{3}{{16}} + \frac{4}{{32}} + ...)$ is $1$ and it will be multiplied by 2(because of 2 comparison for each move) but we have 2n here not 2n-2
did I make a mistake or the idea is wrong?

Floyd's method of constructing a heap consists of applying heapify on all non-leaf nodes. Running heapify on a node $v$ costs twice the height of the subtree rooted at $v$ (where the height of a leaf is 0), with only one exception: if the unique deepest path terminates at an only child, then the cost is twice the height minus 1.
Consider now a heap on $n$ elements, and suppose that $2^h \leq n < 2^{h+1}$. Let us first compute the total number of comparison when ignoring the very last level. In other words, we are considering the case of a complete binary tree with $h$ levels, containing $2^h-1$ nodes in total. The total sum of heights is
$$
(h-1)2^0 + (h-2)2^1 + (h-3)2^2 + \cdots + 1\cdot 2^{h-2} + 0\cdot 2^{h-1} = \\
(2^0 + 2^1 + \cdots + 2^{h-2}) + (2^0 + \cdots + 2^{h-3}) + \cdots + (2^0) = \\
(2^{h-1} - 1) + (2^{h-2} - 1) + \cdots + (2^1 - 1) = \\
2^h - h - 1.
$$
The total number of comparisons is twice that.
The actual heap contains $m = n - 2^h + 1$ nodes at level $h+1$. These increase the sum of heights by 1 for each node which contains one of these $m$ nodes as a descendant. At depth $d$ (where the root is depth zero), there are $\lceil m/2^{h-d} \rceil$ such nodes. This shows that if $n$ is odd, the number of comparisons is exactly
$$
2(2^h-h-1) + 2\sum_{d=0}^{h-1} \left\lceil \frac{n-2^h+1}{2^{h-d}} \right\rceil.
$$
If $n$ is even, then there are some nodes in which the unique deepest path terminates at an only child. To determine how many, let us denote by $x$ the odd leaf. The node $x$ is always the unique child of its parent. Going one level up, $x$ is the unique node at depth 2 iff $n$ is divisible by 4. Continuing in this way, it is not hard to check that if $2^r$ is the largest power of 2 dividing $n$, then the number of such nodes is $r$, and so we have to subtract $r$ from the above formula:
$$
2(2^h-h-1) + 2\sum_{d=0}^{h-1} \left\lceil \frac{n-2^h+1}{2^{h-d}} \right\rceil - r.
$$
We can simplify this formula using $2^h/2^{h-d} = 2^d$, to get
$$
2\sum_{d=0}^{h-1} \left\lceil \frac{n+1}{2^{h-d}} \right\rceil - 2h - r.
$$
Replacing the ceiling with a floor and changing the order of summation, this simplifies to
$$
2\sum_{d=1}^h \left\lfloor \frac{n}{2^d} \right\rfloor - r.
$$
This is always at most
$$
2\sum_{d=1}^h \frac{n}{2^d} < 2n,
$$
and so at most $2n-1$. In fact, the same argument shows that the sum itself is less than $n$, and so at most $n-1$, hence the number of comparisons is at most $2n-2$.
We can also get a more explicit expression for this quantity. Let the binary expansion of $n$ be $b_h b_{h-1} \ldots b_0$, where $b_h = 1$. The sum equals
$$
(b_h \ldots b_1)_2 + (b_h \ldots b_2)_2 + \ldots + (b_h)_2 = \\
b_h (2^{h-1} + \cdots + 1) + b_{h-1} (2^{h-2} + \cdots + 1) + b^0 (0) = \\
b_h (2^h - 1) + b_{h-1} (2^{h-1} - 1) + \cdots + b_0 (1 - 1) = \\
n - (b_h + \cdots + b_0).
$$
Thus, if we denote by $\sigma$ the sum of all digits in the binary representation of $n$, then we get
$$
2n - 2\sigma - r,
$$
a formula also appearing on Wikipedia.
Since $\sigma \geq 1$, this is always at most $2n - 2$.


Can the pumping lemma for context free languages be extended to any subword? It is known that in the case of a Regular Language $L$ , the pumping lemma can be extended to apply to any sufficiently long subword of the language, ie, if $uwv \in L$ and $|w| \ge p$ then we can perform the usual breakup of $w$ as $w=xyz$ such that $uxy^izv \in L$.

Can we similarly extend the pumping lemma for context-free languages such that it is applicable to any sufficiently long subword? Intuitively I think it should generalize, since the pumping lemma is basically stems from the existence of a repeating non-terminal on some path given a sufficiently deep parse tree, and that should not change if we consider a subword instead of the entire word. But I'm having trouble with formalizing an argument.

If anyone could provide an idea for a formal argument or proof, it would be really appreciated.

The extended form of pumping lemma for regular languages you mentioned is called "the general version of pumping lemma for regular languages".

It is indeed natural to suspect that a similar general version of the usual pumping lemma for context-free languages as said in the title should hold. Unfortunately, it does not. For example, take context-free language $L=\{a^nb^n\}$. The initial subword $a^n$ of $a^nb^n$ can be arbitrarily long. However, no part of that subword can be pumped.

There are, however, a few valid generalizations of the usual pumping lemma for context-free languages. You may want to take a close look at them.

Ogden's lemma.
Interchange lemma.


Example algorithms for first class in programming for EE students I am professor of Electrical Engineering who will teach, for my first time, a class to first-year EE students about programming. This will be their first contact in an academic setting with programming, algorithms, data structures, etc.

When introducing the subject of algorithms, I'd like to present a few problems, give a naïve algorithm that might be the first thing that comes to mind to solve it, and then show an efficient algorithm that is clearly more efficient than the naïve one. Ideally, something that none of the students might come up with on their own. Obviously, being their first class in programming, I can't use overly complicated algorithms or I'll run the risk of confusing rather than illuminating them.

Right now I've collected a few examples:

Naïve modular exponentiation vs. left-to-right modular exponentiation
Linear search vs. binary search
Trial division vs. sieve of Erathosthenes (for creating a list of primes from, say, 1 to 100)
Naïve polynomial evaluation vs. Horner's rule
GCD by factoring vs. Euclid's GCD
Schoolbook multiplication vs. Karatsuba multiplication

Of these, (1) and (2) I believe students could come up on their own, and maybe (3) and (4) as well. (5) and (6), I'd risk saying most wouldn't come up with on their own.

What other algorithms could I use to demonstrate the importance of efficient algorithms? Also, would anyone advise against using one of the examples I've listed above, and for what reason?

My favorite example of the value of efficiency is Fibonacci number computation.
A naive programmer could use the recursive top-down solution, which takes exponential time. A bottom-up iterative solution, on the other hand, runs in linear time.


How to find min or max in constant time using infinite # processors? Given $ n $ numbers and an infinite number of processors can the min or max be found in constant time? Assume a shared memory architecture (all processors can write to a common shared memory) and the ability to perform concurrent writes

I have tried dividing up the numbers into groups of 2 each and then using $n/2$ processors at the first step and then $n/4$ processors on the output of the first step etc. I can't see how to make use of more than $n/2$ processors given that I have $\infty$ of them

I managed to solve this so hoping it's alright to answer your own question.
Initialize to all elements off, an $n$ bit vector $A$ having a 1:1 mapping with the $n $ numbers. Compare each number against every other number on $n \choose 2$ processors. Each processor switches the bit corresponding to the smaller of its two elements to 1. Assumption is that the processors can do concurrent writes to $A$. The bit in $A$ remaining off denotes the maximum element.

This is $\Theta(1)$ (constant time) as the depth of the computational graph is independent of the number of elements. The work required is however $\mathcal {O(n^{2})}$.


Neural Network Normalization and de-Normalisation of data I am developing a simple backprop neural network with n inputs and 1 output. I am using a sigmoid activation function. [Aforge.Net]

I have read that it is good to normalise the input and output data prior to training, which I have done using a simple linear relation (max/min mapping) to normalise between [0, 1].

My question is, what happens when upon using the NN after training, I get inputs that are larger/smaller than the max/min of the training sets (used for normalisation)? Should I be storing new max/mins and using these to re-normalise my new inputs? or do I just normalise the data with the parameters used in the training set and simply give the network inputs that may be greater than 1 or less than 0?

You should definitely not be storing new max/mins after training is finished since that will mess up the values for the values that are within the old max and min.

You're network might not do very well on any of these new values anyway since they are more extreme than anything it saw during training. You should scale everything using the max/min you found during training. You could cap anything more extreme than that to be either 0 or 1.


Looking for a formal grammar for $\{ a^{2^n} \mid n \in N\}$ The title says it all. The language $\{ a^{2^n} \mid n \in N\}$ looks quite simple. Yet I could not find a grammar that generates this language.

(Answer adapted from an almost identical question on StackOverflow, because it really belongs here.)

It's certainly possible to write a grammar for this language, but it won't be a context-free grammar. That's easy to demonstrate using the pumping lemma.

The pumping lemma states that for any context-free language, there is some integer $p$ such that any string $S$ in the language whose length is at least $p$ can be written as $uvxyz$, where $u$, $v$, $x$, $y$ and $z$ are strings and $vy$ is not empty, and for all integers $k$, the string $uv^kxy^kz$ is also in the language.

It's clear that the lengths of the strings "pumped" by using successively larger values of $k$ form an arithmetic sequence. So we can assert that for any string $S$ in the language whose length is greater than $p$, there is there some $n$ such that for any integer $k$ there is a string in the language whose length is $|S| +nk$. That is not the case for the language $\{ a^{2^n} \mid n \in N\}$, since the lengths of the strings in that language form an exponential sequence. So the language cannot be context-free.

In fact, since the alphabet of the language has only one symbol, Parikh's theorem demonstrates that if the language were context-free, it would also be regular. It's even easier to demonstrate that the set of lengths of strings recognised by a regular language must be eventually periodic (unless the set is finite). A regular language corresponds to a Deterministic Finite State Automaton (DFA), and any DFA which can accept an infinite number of strings must include a cycle in its transition diagram. The cycle cannot have more steps than the automaton has states, so the lengths of the strings accepted must be ultimately periodic.

Constructing a non-context-free grammar for the language is not that difficult, but I don't know how useful it is.

The following is a Type 0 grammar (i.e. it's not context-sensitive either), but only because of the productions used to get rid of the metacharacters. The basic idea here is that there we put start and end markers around the string (${\boldsymbol \langle}$ and ${\boldsymbol \rangle}$) and we have a "duplicator" ($\blacktriangleright$) which moves from left to right doubling the $a$'s; when it hits the end marker, it either turns into a back-shuttle ($\blacktriangleleft$) or it eats the end-marker and turns into a start-marker-destroyer ($\star$)

\begin{align*}
\mathrm{Start}\Rightarrow  &\ {\boldsymbol \langle} {\blacktriangleright} a{\boldsymbol \rangle}\\
{\blacktriangleright} a\Rightarrow &\ aa{\blacktriangleright}\\
{\blacktriangleright}{\boldsymbol \rangle}\Rightarrow  &\ {\blacktriangleleft}{\boldsymbol \rangle}\\
{\blacktriangleright}{\boldsymbol \rangle}\Rightarrow  &\ \star\\
a{\blacktriangleleft}\Rightarrow  &\ {\blacktriangleleft} a\\
a\star\Rightarrow          &\ \star a\\
{\boldsymbol \langle}{\blacktriangleleft}\Rightarrow   &\ {\boldsymbol \langle}{\blacktriangleright}\\
{\boldsymbol \langle}\star\Rightarrow          &\ \varepsilon
\end{align*}


color adjustment algorithm Got a problem I'm not sure how to approach.
I'm being given a string of text with indeterminate length, around typical "body text" size. The text is a solid color, and the background can be a solid OR a gradient of one or more colors of varying luminance. The goal is to make the text readable across the entire background while adjusting the color channels as little as possible.
How could I find the SMALLEST possible color adjustments to the foreground and/or background that would make the text readable, according to WCA standards or others?

The text has a luminance value $t_0$ and the background occupies a luminance interval $[L_0,H_0]$, $L_0 \le H_0$. I think what you want is to ensure a separation of at least some $s$ between them. There are many degrees of freedom here; one way to capture most of them is to decide beforehand on a way to penalise changes in these variables, as well as the penalty for changing the background interval width $H-L$, and then look for a solution that minimises this penalty cost.
We could use a linear cost model, where the absolute value of the change in each variable is penalised, but this has the disadvantage that optimal solutions are not always unique. So let's use a quadratic cost model (least squares), with penalty weights $c_t, c_L$ and $c_H$ for changes to the main variables, and also a weight $c_d$ for the penalty for changing $H-L$ (i.e., stretching or squashing the background luminance range). Then you want to choose $t, L$ and $H$ to minimise $$p = c_t(t-t_0)^2 + c_L(L-L_0)^2 + c_H(H-H_0)^2 + c_d(H-L-H_0+L_0)^2$$ such that $L \le H$ and either $t \ge H + s$ or $t \le L - s$. This gives a lot of flexibility: Set any of the $c$-parameters to zero to express that you don't care about changes in the corresponding quantity; set it extremely high to try hard to avoid changing it. A sensible first choice might be to set them all equal to 1, and if that yields solutions that "look wrong", increase the weights of whichever values moved around too much.
If $t_0$ is already separated from $[L_0, H_0]$ by $s$, then leaving it unchanged is the optimal solution. Otherwise, intuitively, an optimal solution must have a tight gap, i.e., either $t = H+s$ or $t = L-s$. This can be solved by solving for each of the two cases separately and choosing the better one.
To solve for the first case, substitute $t = H+s$, find the partial derivatives of $p$ w.r.t. the two remaining variables $H$ and $L$, set these to zero:
$$\begin{align}
p & = c_t(H+s-t_0)^2 + c_L(L-L_0)^2 + c_H(H-H_0)^2 + c_d(H-L-H_0+L_0)^2\\
\frac{\partial p}{\partial L} & = 2c_L(L-L_0) + 2c_d(H-L-H_0+L_0) = 0\\
\frac{\partial p}{\partial H} & = 2c_t(H+s-t_0) + 2c_H(H-H_0) + 2c_d(H-L-H_0+L_0) = 0
\end{align}$$, and solve the resulting set of simultaneous equations for these variables to find the minimum:
$$\begin{align}
L & = \frac{c_LL_0 + c_d(H_0-H-L_0)}{c_L - c_d}\\
H & = \frac{c_t(t_0-s) + c_HH_0 + c_d(L+H_0-L_0)}{c_t + c_H + c_d}\\
& = \frac{c_t(t_0-s) + c_HH_0 + c_d(\frac{c_LL_0 + c_d(H_0-H-L_0)}{c_L - c_d}+H_0-L_0)}{c_t + c_H + c_d}
\end{align}$$
Having computed the optimal value of $H$, you can substitute this back into the expressions for $L$ and $t$, and then calculate $p$ for this case. The derivation for the $t=L-s$ case is very similar. Finally, pick whichever gives the lower $p$ value.