does a non-terminated string count as a token in c?

No, in C unterminated strings are not tokens. The C language definition precisely describes what a token is; among other things, they include (complete) string literals and a fallback category of "single non-whitespace characters" which are not otherwise matched by the lexical grammar. This latter category does not, however, include " and ' characters; if these characters are not matched as part of a longer token, the result is specifically flagged as undefined behaviour.

So your text is invalid precisely because it cannot be divided into tokens. A conforming implementation must respond by providing at least one diagnostic message.

All of the above is specific to the C language standard. It is not a "principle of computation" and should not be applied to any other programming language.

For additional precision, the C standard defines two categories of tokens. Initial program text analysis (in phases 1 and 2) splits the text into preprocessing tokens and whitespace (whitespace includes comments, which are not tokens). The translation process then passes the stream of preprocessing tokens through phases 3 to 6, commonly known as "the preprocessor" although it is an integral part of program translation.

Preprocessing leaves most tokens intact but there are features which allow adjacent tokens to be fused or converted into a string literal token. Also, macros may ignore their arguments causing those tokens to vanish. It is not possible to split a token into multiple tokens.

In phase 7, the preprocessing tokens which survive preprocessing must be converted to tokens. Although this is described as a conversion, no textual modification is made; what is converted is the category of the token. Not every character sequence which qualified as a preprocessing token can be treated as a token; phase 7 conversion of such a token will fail and a diagnostic message will be produced.

So it can make sense to talk about an "illegal token" (@, for example) which is still a token. But unterminated string and character literals do not all into that category. They really are not tokens at all.

See §5.1.1.2 of the C standard for a precise description of the translation phases. Tokens are defined in §6.4, which includes the prohibition on unmatched " and ' in paragraph 3:

  A token is the minimal lexical element of the language in translation phases 7 and 8. The categories of tokens are: keywords, identifiers, constants, string literals, and punctuators. A preprocessing token is the minimal lexical element of the language in translation phases 3 through 6. The categories of preprocessing tokens are: header names, identifiers, preprocessing numbers, character constants, string literals, punctuators, and single non-white-space characters that do not lexically match the other preprocessing token categories. If a ' or a " character matches the last category, the behavior is undefined.


Two functions $g(n)$, $G(n)$ such that $g(n) = o(G(n))$ but $g(n+1) \neq o(G(n))$

One example is $g(n) = 2^{2^{n-1}}$, $G(n) =2^{2^{n}}$.

We have $g(n) = \sqrt{G(n)}$, so $g(n) = o(G(n))$.

Meanwhile, of course, $g(n+1) = G(n)$ so $g(n+1) = \Theta(G(n))$, so $g(n+1)\neq o(G(n))$

Why double exponential?  When we add one to $n$, we want the effect to be more than a multiplicative constant (because big $O$ notation hides multiplicative, and therefore additive constants).  Let's make it simple and say that we want adding 1 to $n$ to have a polynomial effect on the value of $g(n)$.  When you add a constant to $n$:

a linear function is increased by an additive constant
an exponential function is increased by a multiplicative constant
a double exponential function is increased polynomially (by a power of two in our example, hence $g(n)^2 = G(n)$)

We can also have $g(n) = n^n$, $g(n) = n!$, etc., where $G(n) = g(n-1)$.  In general we can let $g(n) = f(n)^n$, where $f(n) = \omega(1)$ and $f$ is nondecreasing.  Then we have:

$$\lim_{n\to\infty} \frac{g(n)}{G(n)} = \lim_{n\to\infty} \frac{g(n)}{g(n+1)} = \lim_{n\to\infty}\frac{f(n)^n}{f(n+1)^{n+1}} \leq \lim_{n\to\infty}\frac{f(n)^n}{f(n)^{n+1}} = \lim_{n\to\infty}\frac{1}{f(n)} = 0$$

So we've shown $g(n) = o(G(n))$ using the limit definition (the last step is because $f(n) = \omega(1)$).  Therefore, functions like $(\log\log n)^n$ and even $\alpha(n)^n$ where $\alpha$ is the inverse Ackermann function, will do the trick for us as well.


Prove or disprove those languages are regular

For number 1, you're entirely correct. Every string in $\Sigma *$ is in this language. Take an arbitrary string of zeroes, ones, and twos, then let $y$ be that string, and $w$ be empty.

For number 2, the standard way I learned to prove it's not regular is with "fooling sets". The Pumping Lemma also works here.

For number 3, consider that there are only finitely many possibilities for $w$. This means you could, in theory, write a regular expression that just listed all of them. So this one is actually regular, through "brute force".


(Possibly Easy) Formal Language Question

The reasoning you give is not formal enough. For the union case, you're just restating the theorem "the union of regular sets is regular since the union of regular sets is regular"; for the difference case, your assertion "a subset of a regular language is regular" is false ($\Sigma^*$ is regular and every language is a subset of $\Sigma^*$).

Regular languages are defined in terms of finite automata. The general approach to a proof is that you look at the definitions of what is given (L1 and L2 are regular, so there are automata...) and show a logical reasoning from that to the definition of what you want to prove (there is an automaton ... therefore L3 is regular).


Optimal Algorithm for checking if a number is a multiple of three

If an algorithm that takes less than $O(n)$ time, this means that the algorithm won't be able to look at all the digits of the number. Thus you can prove a lower bound of $O(n)$ by showing that you have to look at all (or almost all) digits of the number in order to decide divisibility.

To show the latter property, assume you had an algorithm that decides divisibility by 3 by looking at $n-2$ or fewer of the digits. This gives you 2 digits that you can set freely, since the algorithm has to give the same answer for any choice of these digits (it doesn't look at them) and it has to be always correct. However you can show that no matter where these digits are and what the value of the remaining digits is, you always have a choice for the digits that gives a number divisible by 3 and another choice that doesn't. Thus, the assumed algorithm can not exist. (I'll leave it to you to show the existance of such choices.)


Checking membership in DFA with fixed length using AC1 circuit?

Let $T$ by a balanced binary tree with $n$ leaves, and label each internal node $v$ by the interval $I_v$ consisting of the leaves below $v$. For each $v$ we will calculate the a two-place relation $R_v(s,t)$ which checks whether $I_v$ causes the automaton to move from $s$ to $t$. If $a,b$ are the two children of $v$, then
$$
R_v(s,t) = \bigvee_u (R_a(s,u) \land R_b(u,t)).
$$
For a leaf $f$, $R_f(s,t) = [\delta(s,x_f) = t]$, where $x_f$ is the $f$th input, and $\delta$ is the transition function. If $r$ is the root of the tree then the final answer is
$$
\bigvee_{q \in F} R_r(q_0,q),
$$
where $q_0$ is the initial state and $F$ is the set of accepting states.

Each node of the tree uses $O(1)$ gates. Since the tree has $O(n)$ nodes, the circuit has size $O(n)$. It's also not difficult to check that it has depth $O(\log n)$. Moreover, the fan-in of each gate is constant (since the number of states is constant), and so this circuit is actually in $\mathsf{NC}^1$.

Note also that the construction works directly for NFAs.


Amount of classes for a semantic segmentation neural network

It's hard to tell whether you are planning on doing image classification or object recognition/detection.

If you're doing image classification, you need each image to have only a single object, and the object needs to be in approximately the same position every time.  You train a neural network to output the label (which object it is).

If you're doing object recognition/detection, in the training set it's not enough to have a label for each image.  Rather, for each image you should have a list of the objects (labels) and the bounding box of each.  Then, you train a neural network to output the label (which object) and location (bounding box) of the object.  That requires a different architecture than object classification.

I suggest you spend some time reading up on object recognition/detection and how to do that with a neural network, since it sounds like you might not be familiar with that yet.

As far as the background class:  I'm assuming you mean a "none-of-the-above" class.  If you are doing image classification and you expect to have some images that aren't of any of the 12 labels, then yes, you should have a 13th label for "none of the above" (i.e., background), and your training set should contain examples of all 13 classes.  If you're doing object recognition/detection, that isn't necessary; instead, typically the training set needs to have realistic images that contain zero, one, or more objects, though that might depend on the specific architecture and approach for object recognition/detection you are using.


What does it mean when $A$ is a NP-Complete Problem but $\bar{A} = NP$?

If $A$ is ${\sf NP}$-complete and $\bar A$ is in $\sf NP$ then we can show that ${\sf NP = coNP}$. This would imply that the polynomial hierarchy collapses to the first level, which implies ${\sf NP = coNP = PH}$.

However, this implies not that all problems are in NP. Just an easy example. There are problems like the halting that are undecidable, and they will remain undecidable even if ${\sf NP = coNP}$, since the proof that the halting problem is undecidable does not use the concept of $\sf NP$ at all.


what is the need for valid/invalid bit in paged memory technique?

In a typical multilevel page table implementation on a typical modern operating system, any attempt to access memory for a page whose page table entry set to "invalid" (typically 0) causes a page fault. This is a hardware trap which transfers control to the operating system.

The most obvious use for this is to represent a region of address space for which there is genuinely nothing there. When a user-space application starts, it will have some of its virtual address space allocated (e.g. for program text, data, BSS, stack, etc). Additional memory (e.g. memory for heap storage or memory-mapped files) needs to be requested from the operating system. This means that a lot of the address space of the process is "blank", and any attempt to access those addresses should fail. The page table entries for these addresses are therefore marked as invalid.

(As an aside, most modern operating systems also use this to support the NULL pointer in C. The first few pages of the address space of a process are deliberately left invalid so that any attempt to access memory through a NULL pointer is trapped by the operating system. Even the first 1MB is not unknown.)

An alternative way to think of the validity bit is that if a program tries to access an invalid page, this causes a trap to the operating system. So the question you might want to ask is: Why would an operating system want that?

One use is to represent a page which is valid (in the sense that it is correct for the user program to access that address) but not currently backed by a physical page. For example:

Demand-paged memory, where the address represents part of a memory-mapped file (that might include the program that is running), or a page that has been swapped to secondary storage. In this case, attempting to access the memory causes the operating system to read in the data before the program continues.
Most modern operating systems support zero-fill memory. When an application allocates memory, the typical default is that this is not backed by physical memory until it is first used. The way this is supported by using the invalid bit.
A related idea is copy-on-write memory, which is used (for example) to implement fork() in Unix.

And there are a bunch of related operating system housekeeping-like tasks for which manipulating the valid bit is useful. For example:

Paging out memory requires detecting what pages have been recently used so that infrequently used pages can be paged out. One way to do this is to mark the page as invalid for a short time. If the page is used in that time, operating system knows that it was accessed because a page fault occurred. (Modern Intel CPUs have a more efficient mechanism for this, but the valid bit works if you're using a CPU where that isn't supported.)
An operating system will often mark a dirty page (e.g. a modified page which represents a memory-mapped file) as invalid while it is being flushed to secondary storage. Any program which tries to modify a page which is in the process of being flushed should wait until the write is complete, so that the data being written is in a known state.
Operating systems can use the validity bit to help debuggers. Many modern debuggers let you set a breakpoint which fires if a certain variable is read or modified. One way to implement this is through the page fault mechanism.

Basically, any time that it would be useful to handle a memory operation by trapping to the operating system is a time when it would be useful to mark a page as invalid.


What makes Bayesian Networks decomposable into joint trees?

I found the answer in valuation algebra more specifically in this paper .
They assume the set of functions (i.e. tables/relations/potentials/probability distributions) form a commutative semigroup. There are six axioms that the graphical model/representation should obey in order to use local computations (and thus joint trees). The valuation algebra has three operations:

Labeling: Mapping each potential $\phi$ to its scope $d(\phi)$ (variables that defined it).
Combination: Two potentials $\phi$ and $\psi$ are combined through combination operator $\phi \otimes \psi$ (in BNs $\otimes$ is the multiplication of CPTs).
Marginalization: The usual projection operator (this corresponds to summing up irrelevant variables in BNs).

where the axioms are:

Commutative Semigroup:
it is clear that the set of CPTs represent a commutative semigroup under the combination operator.
Labeling: for two potentials $\phi$ and $\psi$, $d(\phi \otimes \psi)=d(\phi) \cup d(\psi)$
Marginalization: $d(\phi^{\downarrow x})=x$ where $x\subseteq d(\phi)$
Transitivity: $(\phi^{{\downarrow y}})^{\downarrow x}=\phi^{\downarrow x}$ where $x\subseteq y\subseteq d(\phi)$
Combination: $(\phi \otimes \psi)^{\downarrow z}=\phi \otimes \psi^{\downarrow{z\cap y}}$ where $d(\phi)=x,d(\psi)=y$ and $x\subseteq z\subseteq x\cup y$
Domain: $\phi^{\downarrow x}=\phi$

The axioms are clearly satisfied by the nature of multiplication and marginalization over BN CPTs. Really do not know why axiom 6 is there. Sorry for abusing some of the notations.


When retrieving values from a hash table with linear probing, how do we know if the wanted value had not been shifted?

With linear probing, the appropriate bucket stores both the value and the literal key. So when retrieving, you start in the bucket determined by the hash code and check if the key is the same. If it's not, you move to the next one and check again, and repeat until you find what you're looking for.


Piecewise linear approximation for set of points

This can be solved with a straightforward dynamic programming algorithm.  If you have $n$ data points, it can be solved in $O(n^2)$ calls to BestFit plus $O(n^2 k)$ time.  See https://cs.stackexchange.com/tags/dynamic-programming/info for our resources on how to construct dynamic programming algorithms.


This is called rendezvous problem.

As the paper: Mobile Agent Rendezvous: A Survey mentioned, this problem is original proposed by Alpern: The Rendezvous Search Problem:

  Two astronauts land on a spherical body that is much larger than the
  detection radius (within which they can see each other). The body does
  not have fixed orientation in space, nor does it have an axis of rotation,
  so that no common notion of position or direction is available to
  the astronauts for coordination. Given unit walking speeds for both astronauts, how should they move about so as to minimize the expected
  meeting time T (before they come within the detection radius)?

In the survey paper above,

  Abstract: Recent results on the problem of mobile agent rendezvous on distributed networks are surveyed with an emphasis on outlining the various approaches taken by researchers in the theoretical computer science community.

It covers both "Asymmetric Rendezvous" (in Section 4) and "Symmetric Rendezvous" (in Section 5).

For symmetric rendezvous, the paper by Alpern shows:

  It is shown how symmetries in the search region may hinder the process by preventing coordination based on concepts such as north or clockwise.


How to efficiently sort and filter a large iterator

You can use a max-heap or min-heap. If you want to find the top $k$ elements, use a min-heap. Start by inserting the first $k$ elements. For every subsequent element, compare it to the root of the min-heap. If the new element is smaller, continue to the next element. Otherwise, remove the root and insert instead the new element, operations which can be done in $O(\log k)$. In total, this is an $O(n\log k)$ algorithm.


Algorithm to determine if a number is perfect on a Turing Machine

You need do do:

Factor the number given
Add up the factors, and check they add up to $n$

It should be something like:

sum = 0;
for(k = 1; k < n; k++) {
     if(n % k == 0)
         sum += k;
}
return sum == n;

To get n % k == 0 you can:

tmp = n;
while(tmp > 0)
    tmp -= k;
return tmp == 0;

Translating into TM-speak and splicing all this together isn't hard, just very tedious. Use a multitape TM to simplify your description.


Minimum expected cost through an unconventional graph with probabilities at which edges are selected

Once you know the expected success rate for room 3 (given a certain budget), you should be able to work out the expected success rate for room 2 (given a certain budget).

In other words, let $A[r,b]$ denote the probability of success when starting at room $r$ and starting with budget $b$, using the optimal strategy.  Given $A[r+1,\cdot]$, you can compute $A[r,\cdot]$ via a simple recurrence (consider all possible things you could buy, and the probability of beating room $r$, and how much that reduces your budget when starting at room $r+1$).  This immediately leads to a dynamic programming algorithm for your problem.

If charms persist from one room to the next, use $A[r,b,c]$ where $c$ is the set of charms you already have when you start at room $r$.


Prove that if you can derive w from α in n steps, it's possible with n left-derivations as well

Your method of proof can't work, since it implies that every derivation is a leftmost derivation. Indeed, here is a paraphrase of your proof:

  Let's prove by induction on the length of the proof that if a word $w$ can be derived from a sentential form $\alpha$ in $n$ steps, then $w$ can be derived from $\alpha$ in $n$ steps using a leftmost derivation.
  The case $n = 0$ is trivial.
  Now suppose that $n > 0$, and suppose that the first step of the derivation is $\alpha \Rightarrow \beta$. By induction, $\beta \Rightarrow^* w$ can be converted to a leftmost derivation of length $n-1$, so $\alpha \Rightarrow \beta \Rightarrow^* w$ would be a leftmost derivation of length $n$.

Unrolling the proof, your suggested derivation is actually the same as the original derivation (prove it by induction!), and since not all derivations are leftmost, since can't work.

Concretely, consider the derivation $AB \Rightarrow Ab \Rightarrow ab$. The first step $AB \Rightarrow Ab$ cannot belong to a leftmost derivation. Answering your question, you can't prove that $\alpha \stackrel{lm^1}{\Rightarrow} \beta$, simply because it isn't true.

Here is a different approach. Consider the derivation tree used to derive $\alpha$ from $w$. Try to use this tree to generate a leftmost derivation. Note that the length of the derivation is exactly the number of nonleaf nodes in the tree.


Easiest improvement on first-fit for bin packing algorithm

One "easy" option is to, after the first-fit algorithm has run, do a local search, i.e. checking if there are any k swaps / moves that you can do to improve the packing (i.e. removing a row or column) (for a relatively small value of k).

I also suspect, although this isn't rigorous by any stretch of the imagination, that you could, to a specified maximum depth, do a search-and-backtrack with the current element and next element every time you hit an element that is larger than the next element. In this case, for instance, you have the elements [1x1, 2x1, 1x1, 1x2, 1x3]. You specify a maximum depth, say 1. Then you start packing elements. In this case just packing [1x1] so far. When you hit the 2x1, you try packing [2x1, 1x1, 1x2, 1x3], , but you also branch and try packing [1x1, 2x1, 1x2, 1x3]. Ideally with an alpha-beta search, but you can also just try going to a specified lookahead and then seeing which is better.

Also, note that that particular packing library has... issues. In particular, when you tell it to pack [1x1, 1x1, 2x1, 1x2, 1x3] it does this:


If a function $f$ is convex and $f(0) = 0$ then $f$ is superadditive: $f(a+b) \geq f(a) + f(b)$ for $a,b \geq 0$. The function $f(n) = n\log n$ is convex (since $f''(n) = 1/n > 0$) and $f(0) = 0$ (in the limit), and so for all $k>0$,
$$
f(n) \geq k f(n/k).
$$
If $f$ were concave rather than convex, $f$ would be subadditive, and then $f(n) \leq kf(n/k)$ for all $k>0$.


Pumping Lemma Question: About the cases for y in the xy^iz criterion

Your proof doesn't work, since the pumping lemma only applies to large enough words. The pumping lemma states that if a language $L$ is regular, then there exists a constant $m$ such that all words in $L$ of length at least $m$ have a certain decomposition $xyz$ such that $|xy| \leq m$, $y \neq \epsilon$, and $xy^iz \in L$ for all $i \geq 0$. However, there is no guarantee for words of length smaller than $m$.

In your case, the word that you chose has size 8, which might conceivably be smaller than $m$, and so is not guaranteed to have the decomposition $xyz$ satisfying the properties stated above.

As an aside, if $L$ is finite than $m$ has to be larger than the size of all words in $L$ (why?), and in that case the pumping lemma cannot be applied to pump any word.


Is there a difference between "marking", "configuration" and "state" in Petri nets?

For standard Petri nets, configuration, state and marking are the same thing.
The term marking is standard. State is probably best avoided, as novices may confuse it with place.

For extended Petri nets (e.g. timed Petri nets), a configuration may contain more information than just a marking.


Where does the terminology of open addressing resp. closed hashing come from?

The short answer is that the terms were coined by different people for different purposes, and it's because hash tables historically had two different contexts: in-memory data structures (I believe that compiler symbol tables was one of the first "killer app" uses) and external-memory data structures (file-based databases).

According to Knuth, the first mention of hashing in the literature is from an internal IBM memo from 1953, and it describes hashing with separate chaining. I don't have a copy of the memo, so I don't know what it was used for. I also don't know (possibly nobody does) who coined the term "closed hashing", but it makes sense to me that with "closed hashing" everything is stored in the table itself, with no need for secondary data structures to do collision resolution. In that sense, the hash table is "closed". From the context, it seems that this was an in-memory use.

We do know who coined the term "open addressing scheme". It's from W.W. Peterson's 1957 paper Addressing for Random-Access Storage (IBM Journal of Research and Development 1.2), though the idea goes back a bit further. The context here is clearly searching in files. The addressing scheme that Peterson analysed was "open", as opposed to "structured" (e.g. sorting the data and using binary search).


Every simple undirected graph with more than $(n-1)(n-2)/2$ edges is connected

I am not sure what bothers you but as I see it you are confused about the following two facts

If a graph is connected then $e \geq n-1.$
If a graph has more than $e > \frac{(n-1)(n-2)}{2}$ then it is connected.

Notice that the implications in 1 and 2 are in opposite directions.

For a proof of 2. you can check out this link.


Traveling salesman problem with disconnected cities / infinite length edge

You're just trying to find Hamiltonian cycles in unweighted graphs. That's still NP-complete.

If you want to do it with a TSP solver, do it as follows. Suppose you have a graph on $n$ vertices. These are your $n$ cities. If there's an edge between two vertices, set the distance between the corresponding cities to $1$. If there's no edge, set the distance to $2$. If a minimum-weight TSP solution has total weight $n$, it's a Hamiltonian cycle of the original graph; if it has weight $n+1$ or more, then every cycle that visits all cities must include at least one non-edge of the graph, so the graph has no Hamiltonian cycle.


For every nonterminal $A$ it always holds that $A \Rightarrow^* A$. This is because $\Rightarrow^*$ is the reflexive transitive closure of $\Rightarrow$. In words, $A \Rightarrow^* \alpha$ is $\alpha$ can be obtained from $A$ by applying zero or more productions.

The similar notation $\Rightarrow^+$ is the transitive closure of $\Rightarrow$, and corresponds to one or more productions. In your grammar, it isn't the case that $T \Rightarrow^+ T$.


Is Post's Problem undecidable for fixed number of tiles i.e. $n\geq5$

It is the first version: $\forall n,\,n\geq 5\Rightarrow\,POST(n)$ is undecidable. The reason for the number $5$ is explained in the article of Turlough Neary cited in wikipedia page. The case $n=2$ is proven in

A. EHXENFEUCHT, J. KARHUMAKI, G. ROZENBERG, "THE (GENERALIZED) POST CORRESPONDENCE PROBLEM WITH LISTS CONSISTING OF TWO WORDS IS DECIDABLE",
Theoretical Computer Science 21 (1982) 119-144.


How to select a subset of columns in a given matrix to satisfy a condition?

The feasibility version of your problem is NP-complete, for any fixed $t > 1$, by reduction from SAT.

Suppose we are given a formula over the variables $x_1,\ldots,x_a$, having clauses $C_1,\ldots,C_b$. We will have $2a$ columns, one column per literal.

For each variable $x_i$ we will have the following row:

Positions $x_i,\lnot x_i$ have value $1$, and all other columns have the value $1/t$.

This row forces the solution $S$ not to be a singleton, and forces it to contain exactly one of $\{x_i,\lnot x_i\}$.

For each clause $C_j = \ell_1 \lor \cdots \lor \ell_c$ we will have the following row:

Positions $\ell_1,\ldots,\ell_c$ have values $1,1/t,\ldots,1/t^{c-1}$, and all other positions have value $1/t^c$.

This row forces the solution to contain at least one of the literals $\ell_1,\ldots,\ell_c$.

Conversely, any satisfying assignment corresponds to a set $S$, as can be easily checked. Hence a set $S$ exists iff the original formula is satisfiable.


You might use it to evaluate the performance of programming languages:

http://en.wikipedia.org/wiki/Tak_%28function%29

since recursive methods are pretty useful for benchmarking. In particular, deep recursion tests the speed with which a language can make method calls. This is important because modern applications have a tendency to spend much of their time calling various API functions.

You will also need it to solve ballot problems like this one:

Suppose A and B are candidates for office and there are 2n voters, n
voting for A and n for B. In how many ways can the ballots be counted
so that B is never ahead of A?

http://mathworld.wolfram.com/BallotProblem.html

or just to generate Takeuchi Numbers:

0, 1, 4, 14, 53, 223, 1034, 5221, 28437, ...


How to answer multiple queries for a tree?

For this problem I recommend to solve first for trees with simpler structures that can be generalized afterwards with data structures that run on top of trees (there are plenty of them).

Let's build an idea of what are the dynamics of the problem before jumping to the answer. We have the array A = [N0, N1, N2, N3]. An let's say after each second numbers at each position moves one step to the right. And in some place one number might change (in cases of queries). The initial array after the first second will look like A = [N0, N0, N1, N2]. If we are asked to change the value at position $2$ (indexed in base $0$) with value Q0 at the end of the first step, then the array will look like A = [N0, N0, Q0, N2]. After the following step the array will look like A = [N0, N0, N0, Q0]. We should be able to answer queries of the form: What is the value of position $i$ at this moment?

If there is a value at position $i$ at time $t$ we know this value will be at position $i+\delta$ at time $t+\delta$, unless it is overridden by some update. In the case it was overridden it must be the case that it happened on a position to the right of position $i$.

Supposed we are asked for the value at position $p$ at time $t$. Turning previous equations backwards, we are looking for the right-most position to the left of $p$ (let's call it $o$ from origin) such that an update originated there at time $t_o = t - (p - o)$. We say that for all positions in the array there was a simultaneous update at the beginning with initial values. Rewrite previous equation as: $t_o - o = t - p$. Notice that the problem is simpler now, for every update in position $o$ at time $t_o$ with value $v$ we store at this position the value $(t_o - o, v)$. For every query of the form ($p$, $t$) we should ask for the right-most position to the left of $p$ such that the first element is $t - p$ and return $v$ from such pair.

After every second add always an update in the root with current value, in order to always find the answer for every query. This idea can be implemented with a 2D Segment Tree. Complexity for every query an update will be $O(log^2 N)$.

To turn this idea into the tree case, just notice that:

right becomes the sub-trees.
left becomes the ancestor.
position becomes the height.

Decompose the tree in paths using Heavy Light Decomposition (HLD) and solve the same instance of the problem. Since HLD decompose every path from node $u$ to the root in $O(log N)$ paths each update/query complexity will be $O(log^3 N)$. Overall complexity will be $O((N + Q) log^3 (N+Q))$.


What are the basics of CS i should know,before I start my journey into machine learning

Computer science is a very broad subject area, and many of its sub-disciplines have little or no overlap with others. For example, knowing the basics of operating systems design, compiler design or microprocessor design are unlikely to help you make progress in machine learning (although each one is an interesting topic in its own right).

Machine learning is a sub-topic of artificial intelligence, so the most closely related disciplines are other sub-topics of artificial intelligence such as pattern recognition, data mining, knowledge representation and natural language processing. Some knowledge of the theory of data structures and algorithms would also be useful. Outside of computer science itself, you will also need some knowledge of mathematical topics such as probability, statistics and mathematical optimisation.


How many Turing Machines are there that run in time $t$ or in space $s$ on inputs of length $k$?

Given $k$, consider the set of $\mathcal{M}_k = \{ M_i \mid i \in \mathbb{N} \}$ with $M_i$ defined by

if |x| = k
  accept
else
  simulate TM i on x

The set $\mathcal{M}_k$ is a subset of the Turing machines you want to count for all $s,t$. Since it is infinite, the set you want to count is infinite, too.

As far as I can tell, this result is stable against all restrictions you impose as long as you don't restrict the set of all feasible Turing machines to be finite.


A problem is always claimed to be NP-hard, period.

Indeed, a problem's definition already contains a specification of its parameters. (See the entries in Richard Karp's seminal collection of NP-complete problems for several examples.) Usually, there is no need to make explicit reference to the parameters per se, as they are "automatically scaled" by the input length; for your two parameters $m$ and $n$, for instance, the input could simply be encoded as $0^m1^n$. Hence, for abstract problem instances, it usually suffices to refer strictly to the input length, which is indeed how time complexity is defined (i.e., as the number of computation steps as a function of the input length).

Studying how different requirements on the parameters impact the problem's complexity is the object of study of parameterized complexity theory. For example, the set of SAT formulas with $k$ many variables, $k$ being a fixed parameter (i.e., constant), is decidable in polynomial time (in the formula's length); in parameterized complexity terms, this means SAT is fixed-parameter tractable. It is only as the number of variables is also allowed to scale (in the input length) that SAT becomes NP-hard.


Your proof is correct, but you could elaborate your arguments if you wish.

We have $m\gt 0$ (typo in your question I think, you have used $\ge$) and $l+m\le p$. As $l\ge0$, $0\le p-m\implies m\le p$

$$m\gt0\implies p^2+m\gt p$$
$$\begin{align}m\le p&\implies p^2+m\le p^2+p\lt p^2+2p+1=(p+1)^2\\
&\implies p^2+m\lt (p+1)^2\end{align}$$

$p\lt 2p+1$ is true because $p\ge1$.

Thus, $p^2+m$ lies strictly between two consecutive squares, and hence cannot be a perfect square.


Algorithm for mapping objects of list without mapping to itself?

If you want a cyclic permutation with no trivial cycles (i.e., the only cycle involves all elements) see Sattolo's algorithm.

If you only want to avoid trivial cycles (but you are fine with cycles of length at least $2$), the mathematical object is called a derangement.

See: https://math.stackexchange.com/questions/302057/generating-a-random-derangement

Since the probability  $p_n$ that a random permutation on $n$ elements is a derangement approaches $\frac{1}{e}$ as $n \to \infty$, you can easily get a randomized algorithm by simply generating a random permutations (e.g., using Fisher-Yates shuffle) until you find a derangement.

The above bound is asymptotic but this works even for small values of $n$.
This is because the number of derangements on $n \ge 2$ elements is $!n = \left\lfloor \frac{n!}{e} + \frac{1}{2} \right\rfloor$ (see,e.g., here).
Since $p_n = \frac{!n}{n!}$, we can explicitly compute $p_2 = \frac{1}{2}$, $p_3 = \frac{2}{6} = \frac{1}{3}$, and for $n \ge 4$ we have:

$$
p_n = \frac{!n}{n!} = \frac{\left\lfloor \frac{n!}{e} + \frac{1}{2} \right\rfloor}{n!}
> \frac{\frac{n!}{e} - \frac{1}{2}}{n!}
= \frac{1}{e} -\frac{1}{2 \cdot n!}
\ge \frac{1}{e} -\frac{1}{2 \cdot 24}
> \frac{1}{3}.
$$

This shows that, on average, you will not reject more than $2$ permutations. In general, the probability that you will look at more than $2t$ permutations will always be at most $(2/3)^{2t} \le 2^{-t}$.


How to solve a polynomial of the form y = ax^3 + bx^2 + cx + d using the incremental algorithm in computer graphics

You have f(x). Let g(x) = f(x+1) - f(x). Let h(x) = g(x+1) - g(x). Let k(x) = h(x+1) - h(x). It turns out that k(x) is a constant.

Calculate f(x), g(x), h(x) and k(x) for x = 1. Then you calculate f(x+1) = f(x) + g(x), g(x+1) = g(x) + h(x), h(x+1) = h(x) + k(x), and k(x) is a constant.


How to understand equivalence of indexes of a family of types that are not definitionally equal

We can prove (x : Nat) (y : Nat) -> x + y = y + x (they are propositionally equal). I'm using Agda-ish notation here rather than the notation in the HoTT book because type setting is hard. Note that we can prove this in standard intensional type theory. This gives a function from Nat to Nat to a proof of equality.

In intensional type theory we don't distinguish between types up to judgmental equality. Almost as though there's a rule

     A ≡ B  a : A
     ------------
        a : B

Remember that FZ : Fin 1, Since 0 + 1 ≡ 1, this means that FZ : Fin (0 + 1). If we didn't have a rule like this, it'd be kinda pointless to have computation in our types because the minute we actually have some interesting expression in our type we couldn't witness it.

It's important to keep the different types of equality separate in type theory

Judgmental equality (a judgement) is something actually embedded in the system. You can't touch it when writing programs but it says that two terms are equal if they have the same value more or less
Proposition equality (a proposition) is what we can prove as a programmer. There is one way to prove A = B in standard ITT, with refl : A = A. This means that we can prove A = B if and only if A and B are judgmentally equal.

Whether Fin (x + y) or Fin (y + x) for some x and y have members is dependent on what x and y. If x and y are 0, then Fin (x + y) is judgmentally equal to Fin 0, which is unoccupied.

We can prove that Fin (x + y) = Fin (y + x) though in standard ITT, the proof in a system like Agda looks like

eq : (x y : ℕ) → Fin (x + y) ≡ Fin (y + x)
eq x y rewrite +-comm x y = refl

So in answer to your question, the two types are propositionally equal using an intensional notion of equality. This isn't enough to say if e : Fin (x + y) then e : Fin (y + x), for that we'd need judgmental equality. We can easily construct invertible maps between the two though by pattern matching on the result of eq for example.

Finally, in answer to your last question. In extensional type theory this is the case, in intensional type theory we need some extra tools. HoTT in particular provides us with univalence which is even more flexible: two types can be propositionally equivalent if they're isomorphic.


It's not a technical term with a precise meaning, it is just the English word "naive". In a computer science context, the word usually means something like "one of the things you would think of first, but without realizing a less obvious but important fact".

For instance, if one knows the definition of Fibonacci numbers is $\mathrm{Fib}(n) = \mathrm{Fib}(n-1) + \mathrm{Fib}(n-2)$, then a "naive" implementation would be

def Fib(n):
  if n <= 1:
    return 1
  else:
    return Fib(n-1) + Fib(n-2)

What's the problem? That if we call, say, Fib(7), then we end up making many of the same calls over and over, such as Fib(4) (because Fib(7) calls Fib(6) and Fib(5), and Fib(6) calls Fib(5) and Fib(4), and both times we call Fib(5) it calls Fib(4) and Fib(3), and so on).

So here a more a more "sophisticated", as opposed to naive, solution would be like dynamic programming and avoid all the extras computations.


What the definition is saying is: $f\in O(g)$ if there's a number $n_0$ such that $f(n)$ is less than some multiple of $g(n)$ (that's where the $c$ comes in) for all $n$ larger than $n_0$. In simple terms, it's saying that $f$ is eventually bounded by some fixed multiple of $g$.

Big-O notation is essentially a simplification describing the ultimate rate of growth of a function. Here we don't care at all if, say, $f(n)$ is bigger than $43\cdot g(n)$ for the first thousand values of $n$: if $f(n)<43\cdot g(n)$ for all the rest (the bigger values of $n$), we've established that a multiple of $g$ is an upper bound on the values of $f$.


Does big-Oh notation in optimization follow the same convention as in CS?

They are using the standard Landau notation.

In the theorem you stated, it is said that after $k$ steps your distance from the optimal value is smaller than $\frac{c}{k}$, where $c$ is a constant which depends on your initial distance from the point where optimum is achieved, and on the step size. In that case you can indeed say that the convergence rate is $O\left(\frac{1}{k}\right)$, which is interpreted as you quoted in the following line, to get $\epsilon$-close to the optimal value one needs $O\left(\frac{1}{\epsilon}\right)$ iterations.

Note that I wouldn't take this answer as "anywhere in optimization this notation means the Landau notation", and you are probably right to say that it needs to be mentioned. However, in this context, you can pretty safely assume that this was the authors intention.


Print the number of subarrays of an array having negative sums

An $O(n \log n)$ solution:

Find prefix sums $S[i] = \sum_{k=0}^{i} a[k]$

Set $S[-1] = 0$

Now count the number of inversion pairs in $S[-1], S[0], \dots, S[n-1]$


would complexity of constraint satisfaction problem bound the constrained optimization problem?

No, no optimization problem can be $\mathsf{NP}$-complete since all $\mathsf{NP}$-complete problems are in $\mathsf{NP}$ and $\mathsf{NP}$ only contains decision problems.


If there is one string x that can be parsed in two ways then repeating x n times can be parsed in at least $2^n$ ways. So the problem has either 0, 1, or an exponential number of solutions. Asking for all is likely pointless.

However, you could provide an answer with many solutions in a much more compact format. Say your input is "catsanddog" repeated 100 times with $2^{100}$ solution, clearly infeasible. Instead we present a solution like this: "word1 word2 word3" if a solution consists of these three words. [solution1 | solution2 | solution3] if there are say three alternatives. And everything concatenated. So the solution in the case above would be written as ["cats and dog" | "cat sand dog"] repeated 100 times.

In practice, this will usually give a solution with size cN for a not very large c, where N is the input size. You can still have extremes. Take the dictionary ["a", "aa"] and a string of n a's as input. The first few solutions are:

"a": "a"
"aa": ["a a" | "aa"]
"aaa": ["a aa" | ["a a" | "aa"] "a"]
"aaaa": [["a a" | "aa"] "aa" | ["a aa" | ["a a" | "aa"] "a"] "a"]


Community detection in weighted directed graphs for fixed number of communities

There are lots of community detection algorithms that need the number of communities as input. For example, Bigclam [1], a matrix factorization approach, needs the number of communities as input. Another example is the seed expansion [2] method that needs the number of communities as input. I'm sure there are many algorithms that take the number of communities as input, but you need to do some research and find the one that is best suitable for you. Looking at these algorithms may be a good start.

You may also think about your own community detection algorithm specific  to your problem. For example, you can use seed expansion and start with $k$ seeds (cities) and try to expand those seeds whenever appropriate (appropriate is a vague word, you need some calculations to see if an expansion is appropriate or not).

[1] Yang, Jaewon, and Jure Leskovec. "Overlapping community detection at scale: a nonnegative matrix factorization approach." Proceedings of the sixth ACM international conference on Web search and data mining. ACM, 2013.

[2] Whang, Joyce Jiyoung, David F. Gleich, and Inderjit S. Dhillon. "Overlapping community detection using seed set expansion." Proceedings of the 22nd ACM international conference on Conference on information & knowledge management. ACM, 2013.


Beginnings of multiptogramming and compilations for it

The early multiprogramming systems ran two or three programs simultaneously in a single computer. They did so by partitioning the memory amongst

operating system
one user-program
another user-program
...

The user programs shared a single copy of the operating system, which provided input/output and other services through system calls, which switched the processor into a special privileged mode that can access the external hardware. Programs had to be relocatable - able to run wherever in the memory they happened to end up.

Many advances were made in the Ferranti Atlas hardware and operating system:

virtual memory - both mapping and one-level store;
memory-addressed hardware;
three-level processing hierarchy: interrupt, supervisor, and user;
SPOOLing - buffering of slow input/output devices.

Time-sharing - time-division multiplexing of processor and sometimes of computer memory - dragged behind, and proved difficult to make a success of.

Multi-tasking within a single programming model is different and developed almost orthogonally.


Algorithm to find longest path in a tree that is smaller than x

Your dynamic program is a step in the right direction.
My idea would be to maintain two values for a node v:

$L_v$: The longest path starting from v going downwards (these corresponds to your dynamic program and the first two cases)
$U_v$: and the longest path in the subtree of v (i.e., case 3).

You already gave the formula for $L_v$.
For $U_v$ you take the maximum of $U_l$, $U_r$ and $L_l + w(lv) + w(rv) + L_r$ where $l$ and $r$ are the left and right children of v resp.
The last equation corresponds to the path which is formed by the longest paths to the left and to the right which are then joined.


This problem has been solved by Alon Efrat, Alon Itai and Matthew J. Katz in their paper Geometry Helps in Bottleneck Matching and Related Problems. The running time of the algorithm is $O(n^{1.5} \log n)$.


1. **What is Schema**-  In a relational database, the schema defines the tables, the fields in each table, and the relationships between fields and tables.

Yes, They are related to these 3 words,  "conceptual schema", "physical schema" and "external schema".

External schema for user views
Conceptual schema integrates external schemata
Internal schema that defines physical storage structures

No, It has no relation with "schema" in cognitive psychology

2. Yes, Schema used in other area also like in-

Programming & Algorithms -XML Schema , Schema (genetic algorithms)
Science- Body Schema, Image Schema
Mathematics- Axiom Schema (related to Mathematical Logic)

3.  Refer above point 1 & 2


Understanding Hamiltonian Path, NP vs Co-NP

A nondeterministic Turing machine is perhaps more clearly viewed as a Turing machine with two inputs: one is the actual input, in your case $\langle G,s,t \rangle$, and the other a polynomial size "witness", in your case a purported Hamiltonian path $p$. The machine checks, in polynomial time, that $p$ is indeed a Hamiltonian path from $s$ to $t$ in $G$, and if so, accepts; otherwise it rejects.

In what sense does this machine $M$ nondeterministically accept $\mathsf{HAMPATH}$?

If $\langle G,s,t \rangle \in \mathsf{HAMPATH}$ then there exists a witness $p$ such that $M(\langle G,s,t \rangle,p)$ accepts.
If $\langle G,s,t \rangle \notin \mathsf{HAMPATH}$ then $M(\langle G,s,t \rangle,p)$ rejects for all values of $p$.

Now consider the machine $!M$ which accepts when $M$ rejects and rejects when $M$ accepts.

If $\langle G,s,t \rangle \in \mathsf{!HAMPATH}$ then $!M(\langle G,s,t \rangle,p)$ accepts for all values of $p$.
If $\langle G,s,t \rangle \notin \mathsf{!HAMPATH}$ then there exists a witness $p$ such that $!M(\langle G,s,t \rangle,p)$ rejects.

As you can see, $!M$ doesn't have the same promises regarding $\mathsf{!HAMPATH}$ that $M$ has regarding $\mathsf{HAMPATH}$.


Genetic algorithm: What is the expected number of strings that are explored?

As I pointed out in the comments, the primary feature of interest for understanding how a genetic algorithm (or evolution, even) explores the fitness landscape is the fitness function. In this case, you specified an extremely simple fitness function with no epistasis. This was a standard assumption for analytical tractability when biology first started out (i.e. most analyses that have Fisher somewhere in the name probably assume no epistasis), but it is seen as less reasonable now. Hence, if your goal was to gain biological intuition, this question will not provide it. Since landscape with epistasis have qualitatively different dynamics.

Finally, you don't specify a selection function, so to give you a heuristic answer I will assume one that has strong selection.

First note, that at any given time, the number of genotypes you explore is bounded above by the trivial bound of $GN$. To start building a better bound, lets look at Wilf & Evans (2010) that analyzed a no-epistasis model under strong selection is a sexual population (i.e. with recombination). They showed, that it converges to equilibrium (the all $1$s string in your case) in $\Theta(\log l)$ (they actually showed a tighter characterization with a careful analysis of radix-sort, but I will leave that exploration upto you) generations (I think we have to assume that $N \in \omega(l)$). Thus, you will reach the peak very quickly.

On the way to the peak, you will explore $O(N \log l)$ genotypes. In fact, if the selection strength is very high, then we can assume that the population remains close-to monomorphic in terms of the phenotype specified as "number of ones in the genome" although polymorphic in terms of the genotype. This can give us a bound of about $O(l^2 \log l)$.

Once you reach the peak, strong selection will keep you there, and any mutants will go extinct after each generation. This means that from there on out, the population will just stay at the string $1^l$ with transient (single-generation) mutants of Hamming-distance one.

This gives us a pretty ridiculous bound $\min (O(GN), O(l^2 \log l))$. In other words, as long as you look at generations $G \in \Omega(\log l)$ you will only end up sampling an exponentially small fraction of the genome space $O(\frac{l^2 \log l}{2^l})$.


Quickly pruning edges below average weight for a membership-based weighting

Yes, we can make your idea work.  I'll show how below, and prove that it is correct (it does not miss any edges).

The first step will be to sort the groups by decreasing size.  Say their sizes are $s_1 \ge s_2 \ge s_3 \ge \dots$.  Say $t$ is your threshold.  Find the smallest $k$ such that

$$1/s_1 + 1/s_2 + \dots + 1/s_k \ge t.$$

Lemma. No edge can have weight above the threshold $t$ based only upon membership in groups $1,2,\dots,k-1$.  In other words, every edge with above-threshold weight must be in at least one of the groups $k,k+1,k+2,\dots$.

This observation lets you apply your idea, to optimize the performance of the algorithm.

Algorithm. Sort the groups by decreasing size and find $k$, as above.  For each of groups $k,k+1,k+2,\dots$, look at all pairs of points within the same group, and compute the edge weight of each such edge.  Output the ones whose edge weight is above the threshold $t$.

This algorithm can be proven to output all above-threshold edges, thanks to the lemma above.


Given N vertices and M edges find if two nodes are in the same connected component?

The problem is that you want to do a graph traversal every check : that is way too often.

Do a graph traversal to find the connected component of each vertex (e.g. give them a number). This takes $O(m+n)$ time. Store these numbers in an array indexed by the vertices, let's call it $A$. Then check if two vertices $i$ and $j$ are in the same connected component in $O(1)$ time by checking whether $A[i] = A[j]$.


How many different strongly connected graphs can be created given n nodes?

This is A003030. Everything known about this sequence is listed there.


Perfect Matching in Bipartite Graph with mutually exclusive edges

It is $NP$ as $SAT$ can be polynomially reduced to this problem.

Let clauses be the left part vertexes, and literals be the right part vertexes. Draw an edge $(x,y)$ iff clause $x$ contains literal $y$. Finally, a pair of edges $(x_1, y_1)$ and $(x_2, y_2)$ will be exclusive iff $y_1$ corresponds to literal $a$ and $y_2$ corresponds to literal $\overline{a}$.


How does $LL(n)$ languages compare with $LR(0)$, for $n>0$?

They are incomparable.

Every $LR(0)$ language has the prefix property (no sentence is a prefix of another sentence). But many $LL(k)$ languages don't have this property ($a^*$, for example).
The language $\{a^nb^mc\mid n\ge m\ge 0\}$ is $LR(0)$ but is not $LL(k)$ for any $k$.


Edit: This answer is for $k<n$. Without bounding $k$ in terms of $n$ the expression is unbounded.

If $k=n-1$ then your expression becomes
$O\left ({{2(n-1)}\choose{n-1}}\right)$. Notice that by Stirling's formula for any $0<\alpha<1$
$${m \choose {\alpha m}}= \Theta(m^{-{1/2}} 2^{H(\alpha)m}),$$
where $H(q)=-q \log q - (1-q) \log (1-q)$ is the binary entropy. In particular $H(1/2)=1$. Therefore we have for $k=n-1$
$$O\left ({{2(n-1)}\choose{n-1}}\right)=\Theta((2n-2)^{-{1/2}} 2^{2n-2})=\Theta\left(\frac{ 4^{n}}{\sqrt{n}}\right).$$

Since the upper bound $k=n-1$ is the worst case (
I leave it as an exercise to show this), your expression is $O\left(\frac{ 4^{n}}{\sqrt{n}}\right)$.


Slowdown when accessing data at page boundaries?

Go to Agner manuals page and download them all, you will find tons of interesting info there. In particular, microarchitecture.pdf says

  There is a false dependence between memory addresses with the same set and offset, i.e. with a distance that is a multiple of 4 Kbytes:

;Example 9.6. Sandy bridge false memory dependence
mov [rsi],eax
mov ebx,[rsi+1000H] ;False memory dependence

I.e. the access becomes slower because cpu thinks that it may be the same address, so the load in the second line may depend on the store in the first line and thus cpu serializes execution of these operations.

AFAIR, it wasn't changed in latest Intel cpus.


Propositional logic and connectives(translating to english)

The first thing to say is that in propositional logic every statement will have a truth value.

If (P or Q or R) evaluates to True (which it doesn't have to) then a natural English way to translate would be:

  Either you have the flu, you miss the final examination or you pass the course.

Note that this "or" is clearly inclusive - meaning that it is possible that more than one of those things happens but at least one must. To make that clear beyond doubt in natural English you might structure the sentence using "at least". This will be much more long winded but avoids the person you are communicating with thinking that you might mean exclusive "or" (e.g. the type of "or" used in "true or false" - it can be one or the other but not both). If you wanted to account for this you might say something like:

  At least one of the following is true: you have the flu, you miss the final examination or you pass the course.

For your second case what you said is not very natural. You would typically hear someone say:

  You won't pass the course if you have the flu or miss the final examination.

If you are supposed, for whatever reason, to structure the answer as you did, the commas should be removed after your "if" clauses. This would be better:

  If you have the flu then you do not pass the course, or if you miss the final examination then you do not pass the course.


Clustered Regions by Each Neuron in Self Organizing Map (SOM)

When clustering an input, one should calculate the Euclidean distance to all neurons, then the input is assign to the cluster of the nearest neuron.

In other words, for an input $v$ and a set of neurons $N$ (in your case $|N| = 16$ ) the cluster is:

$\text{Cluster}(v)=\arg \min_{i\in A}(||w_i-v||_2)$


You are asking two questions. The first is an enumeration question, and the second is about generation or encoding/decoding. The enumeration question is a standard combinatorial exercise, which can be solved using exponential generating functions (and algorithmically, using dynamic programming). For example, the number of strings of length $\ell$ in your example is $\ell!$ times the coefficient of $x^\ell$ in the exponential generating function
$$
\left(1 + x + \frac{x^2}{2!}\right)
\left(1 + x + \frac{x^2}{2!} + \frac{x^3}{3!}\right)^2
\left(1 + x + \frac{x^2}{2!} + \frac{x^3}{3!} + \frac{x^4}{4!}\right).
$$

For the generation problem, the idea is as follows. Suppose that we want the $k$th lexciographically smallest string of length $\ell$. We will uncover the letters one by one. To find the first letter, we count how many strings of length $\ell$ start with each letter—an instance of the enumeration problem mentioned above—and use this information to determine the first letter. We find the subsequent letters in a very similar way.


Confused about pumping lemma, What i'm missing?

you can't claim to know how $w$ distributes.

you know that some $w \geq n_0$ exists, in such a way it can be denoted as

$w=xyz$

$y \neq \epsilon $

$ |xy|\leq n_0 $

and for every $i>0: xy^iz \in L$

your error is that you claimed you know the distribution of $w$ to $x,y,z$. Namely, you fixed $y$ to be $10$

The language of course can be pumped, since it's regular. But for any $w = xyz, y$ must be a word of only $0$, since $1's$ cannot be pumped.


Are all NP-complete languages downward self-reducible?

Recall the (downward) self-reduciblity of a language.

A language $L \in \mathrm{NP}$ is self-reducible if for every verifer $V$ for $L$, there is a polynomial-time Turing machine $M$ such that for any oracle $O_{L}$ deciding $L$, and any $x \in L$, we have $V(x, M^{O_{L}}(x)) = 1$.

The book gives a proof of the self-reduciblity of SAT.
The idea for proving the self-reduciblity of all the $\mathrm{NP}$-complete language is similar.
Given an $\mathrm{NP}$-complete language $L$ and its verfer $V$, suppose that $L_{V}$ is the language of $V$.
For every string $w \in \Sigma^{*}$, we define $L_{w} = \{ z = x \Vert w : \exists u \in \Sigma^{*}, (x, w\Vert u) \in L_{V} \}$.
Clearly, $L_{w} \in \mathrm{NP}$.
Since $L \in \mathrm{NP}\text{-complete}$, there exists a Karp reduction $f$ such that
$$z \in L_{w} \Leftrightarrow f(z) \in L$$
Assume we have an oracle $O_{L}$ deciding $L$.
Now we design an algorithm that, given $x \in L$, finds $w$ with $(x, w) \in L_{V}$. Say the length of $w$ (given $x$) is $n = \mathrm{poly}(|x|)$. The algorithm proceeds as follows:
For i = 1 to n do:
    Set b[i] = 0;
    Set w = b[1]b[2]...b[i];
    If f(xw) is not in L (We run this step using our oracle for L)
        Set b[i] = 1;
    End if;
End for;
Return w;

Indeed, $w$ is a witness of $x$, i.e. $(w, x) \in L_{V}$.
And this algorithm runs in polynomial time.
Other languages in $\mathrm{NP}$ (that are not $\mathrm{NP}$-complete) may be self-reducible as well.
An example is given by graph isomorphism, a language that is not known (or believed) to be in $\mathrm{P}$ or $\mathrm{NP}$-complete.
On the other hand, it is believed that not all languages in $\mathrm{NP}$ are self-reducible.


How many different heaps are there of a given shape?

You can compute this recursively as follows. It will be convenient to denote (binary) trees using the following notation: a tree is either a leaf $\ast$ or is formed from two subtrees $(T_1,T_2)$. For a tree $T$, let $|T|$ denote the number of vertices in $T$, defined inductively by $|\ast|=1$ and $|(T_1,T_2)| = |T_1|+|T_2|+1$. Finally, let $N(T)$ denote the number of ways of allocating the integers $1,\ldots,|T|$ to $T$ so that the max-heap property is satisfied.

The base case is $N(\ast)=1$. Now consider a tree $T=(T_1,T_2)$. Clearly we must put $|T|$ at the root. Every filling out of the rest of the tree can be described as follows:

Choosing a set $S_1$ of integers as labels for $T_1$. The other elements $S_2$ function as labels for $T_2$.
Arranging $S_1$ in $T_1$ in a way satisfying the max-heap property.
Same for $S_2$ and $T_2$.

The number of ways of accomplishing the second bullet is $N(|T_1|)$, and the number of ways of accomplishing the third bullet is $N(|T_2|)$; in both cases, the exact contents of $S_1$ and $S_2$ are not important. The number of choices in the first bullet is $\binom{|T|-1}{|T_1|}$, and we conclude that $$ N((T_1,T_2)) = \binom{|T_1|+|T_2|}{|T_1|}N(T_1)N(T_2), $$
with initial case $N(\ast) = 1$.

Using this formula you can easily compute that for your tree the number of possibilities is $304128$ (I believe).

You can also "unroll" the formula:
$$
N(T) = \prod_{x=(x_1,x_2) \in T} \binom{|x_1|+|x_2|}{|x_1|},
$$
where $x$ goes over all internal nodes in $T$. For example, for your tree we get (top to bottom, left to right)
$$
\binom{12}{5} \binom{4}{3} \binom{6}{5} \binom{2}{1} \binom{4}{1} \binom{2}{1} = 304128.
$$


Use BFS to work backwards from v, flagging each vertex as 'visited' as you go.  If you ever hit a vertex you've previously visited, your graph doesn't have the uniqueness property.  Otherwise, it does.


Prove/disprove - reverse topological sort transpose graph

A topological sort of a graph $G$ is an order $\pi$ such that if there is a directed path from $x$ to $y$ in $G$, then $x$ precedes $y$ in $\pi$.

Let us now show that $\pi^R$ is a topological sort of $G^R$. If there is a path from $x$ to $y$ in $G^R$ then there is a path from $y$ to $x$ in $G$, and so $y$ precedes $x$ in $\pi$, and so $x$ precedes $y$ in $\pi^R$.


Using persistence on a constant database

Yes, you can do this in $O(\log n)$ time.  Use a sweep-line algorithm together with a persistent tree data structure.

Imagine the point $(d_1,d_2)$ as being on a grid, with $d_1$ as the value of the $x$-coordinate and $d_2$ as the value of the $y$-coordinate.  Your sweep line is a horizontal line, namely, at time $t$, the sweep line is the line $d_2=t$.

You will build a data structure that stores all the points $(d_1,d_t)$ such that $d_2 \le t$.  You can use a balanced binary search tree, keyed on the value of $d_1$.  This data structure will let you answer the query Query$(a,b,t)$ in $O(\log n)$ time.

Now you're going to gradually increase the value of $t$ (sweeping the line upward), and adjusting the data structure as you go.  You'll save a copy of the data structure for each value of $t$ that occurs in the $d_2$-database.

This sounds like it requires $O(n^2)$ space.  However, there's a clever trick.  Use a persistent data structure to store the trees.  As you move the sweep line upward, you insert more items into the tree.  A persistent data structure will let you pick any time $t$ and do a lookup into the state of the tree at time $t$.  This lets you answer Query$(a,b,t)$ in time $O(\lg n)$.


Dividing unequal parts as equaly as possible

The original number of frames you have is 4955 frames and every student should receive as close to equal amount of frames as possible, the following is a solution I would suggest:

4955 frames / 20 students = 247.75

we take 247 (floor) and 248 (ceiling) as the possible number of frames that each student can get, now to figure out how many of those students should get 248 (the rest will get 247):

4955 mod 20 = 15

15 students will receive 248 frames and 5 will receive 247 frames

This works because .75 is 15/20 which therefore means 15 out of 20 got the ceiling value of the original division and the rest got the floor to equalise to .75


Is a degree-$d$ pseudo distribution always a relaxation?

To see that this is a relaxation, all you have to check is that each feasible solution to the first problem gives rise to a feasible solution to the second problem. All you have to do is, given $x \in K$, take an actual distribution $D$ concentrated on $x$. (This only works if in the definition of $K$ you replace $\mathbb{R}^n$ with $\{0,1\}^n$; your formulation doesn't make too much sense.)

When $d = n$, the conditions guarantee that $D$ is an actual distribution. If the objective function $p$ is concave then the optimal distributions are singletons, and so both programs have the same value. Otherwise it could be that for some distribution $D$ supported on $K$ it holds that $\mathbb{E}_{X\sim D}[p(X)] < \min_x p(x)$.


Why isn't this undecidable problem in NP?

I think you misunderstood what it means to solve a diophantine equation, and Matiyasevich's indecidability theorem.

Matiyasevich proved that for every RE set $S$ there is a diophentine equation $f(n;x_1,...,x_k)$ such that $n \in S$ only if there exists integer coefficients $x_1$,..,$x_k$ such that $f(n;x_1,...,x_k) = 0$. In particular, the halting problem is a typical RE set, and so solving the above problem is undecidable.

Note that $x_1, ... x_k$ are not bounded in size, and in general can be arbitrarily large, so there is no "polynomial sized certificate" evident in this problem.

To expand: the integers $x_1, ... , x_k$ need to be written in binary to be a certificate. Since these integers can be arbitrarily large (regardless of $n$), we have that the certificate is not polynomial in $\log n$ or more importantly, not bounded by and computable function.

Every problem in $\mathsf{NP}$ however, has a certificate that is bounded by some polynomial $p(N)$ (where $N$ is size of input). So $\mathsf{NP}$ questions are trivially decidable, since you can enumerate every possible bit string upto length $p(N)$ and if none of them certify the input, return false. If some does then return true.


Longest palindrome substring in logarithmic runtime complexity

If a you are given a palindrome $p$ of size $N$ (as you say in the beginning of the question), then the longest palindrome is $p$ itself and you don't need to do any computation.

If your input is not a palindrome but an arbitrary string, then you need to at least read the input and therefore $\Omega(N)$ is a trivial lower bound.


Are there more partially recursive functions than and recursive functions?

No they have the same cardinality. They have the cardinality $\aleph_0$. Both sets are infinite in size so we have to compare them based on their level of infiniteness, since as we know there are infinite levels of infinity. Both sets are countably infinite so we say they have the same cardinality.

To expand on this and show why this is the case:

The set of partially recursive functions are infinite by design. Also they are computable, so by the Church-Turing thesis they are solvable by a Turing machine. Since there are only countably infinite Turing machines there can only be countably infinite partial recursive functions.

The same argument can be used on the set of recursive functions.


Does Bloom filter with false positive rate greater than 0.5 make sense?

A Bloom filter never gives a false negative. This is the property that makes them desirable in many situations. They are appropriate for any situation where the existence of false positives is a potential performance issue, but not a correctness issue.

One obvious example is where the filter is used to avoid a more expensive check. Let's try to quantify this a bit, to see what I mean.

Suppose that you are trying to represent some subset of a universe of $S \subseteq U$. We'll further assume that you are testing elements of $U$ for membership in $S$ with equal probability.

Let $p$ be the proportion of elements that are in the set (i.e. $p =
   \frac{|S|}{|U|}$).
Let $c_p$ be the cost of a precise test (measured in time, cycles,
disk accesses, or whatever seems appropriate).
Let $c_b$ be the cost of a Bloom filter test, and we hope that $c_b <
   c_p$.
Let $q$ be the false positive rate of the Bloom filter.

If we only performed precise tests, the cost of each test is $c_p$.

If we perform a Bloom filter test first, the cost of each test is $c_b$ plus $c_p$ times probability that we need to perform a precise test, whether due to true positives or false positives.

By the inclusion-exclusion principle, the average cost of this test is:

$$c_b + c_p(p + q - pq)$$

As long as $c_p > c_b + c_p(p + q - pq)$, the Bloom filter test gives you a net performance gain.

As you can see, the false positive rate $q$ is not the only important number here; Bloom filters with higher $q$ may, for example, have smaller $c_b$ because physically smaller data structures are more cache-friendly.

For completeness, I will note that having a backup precise test isn't the only use case for Bloom filters. There are other situations where false positives are tolerable.

Consider a network protocol where two systems on different machines need to be kept in sync. You would like to only transmit the changes, to save bandwidth. But occasionally transmitting some data that you don't need to transmit is not as bad as failing to transmit data that needs to be transmitted. It may be wasteful to over-transmit, but it's not incorrect to do so.


Section 2.3.3 in :

Codd, E.F. (1972). "Relational Completeness of Data Base Sublanguages" is what you need.


$UP^{\ O}\neq P^{\ O}$ for some oracle $O$

Here is the construction from Rackoff's paper Relativized questions involving probabilistic automata. We construct the oracle $O$ using diagonalization, in steps. At step $t$ we will construct the initial segment $O_t$ of $O$ which consists of $O \cap \bigcup_{i=0}^{n_t} \Sigma^i$ for some $n_t$, where $n_0 < n_1 < \cdots$ is an increasing sequence. We will maintain the following invariant: $O_t$ contains at most one string of each length. This will guarantee that the following language is in $UP^O$:
$$
L = \{ x : \exists y \in O \cap \Sigma^{|x|} \}.
$$

The construction will use an enumeration $M_i$ of all polynomial time Turing machines, with the guarantee that the running time of $M_i$ is at most $in^i$. It is a standard fact that such an enumeration exists.

Let $O_{t-1}$ be the initial segment constructed at step $t-1$ (or $\emptyset$ in the first step). We now show how to construct $O_t$. Choose the smallest $a_t > n_{t-1}$ such that $ta_t^t < 2^{a_t}$. Run $M_t$ on the string $0^{a_t}$, answering NO to all queries outside of $O_{t-1}$. Let $b_t$ be the length of the largest string queried, and let $n_t = \max(a_t,b_t)$. If $M_t$ accepts, set $O_t = O_{t-1}$, guaranteeing that $0^{a_t} \notin L$. Otherwise, set $O_t = O_{t-1} \cup \{x\}$, where $x$ is some string of length $a_t$ which $M_t$ didn't query (such a string must exist since $ta_t^t < 2^{a_t}$), guaranteeing that $0^{a_t} \in L$. You can check that $O_t$ satisfies the invariant stated above.

By construction, $L \in UP^O$ (the UP machine guesses $y$ of the same length as the input and verifies that $y \in O$), while $L \notin P^O$ since $M_t$ answers incorrectly on the string $0^{a_t}$, by construction.

Beigel, in the paper On the relativized power of additional accepting paths, shows that $P^O \neq UP^O$ for a random oracle, crediting this result to Rudich's PhD thesis. In fact he proves even stronger separations, showing that allowing more accepting paths increases the (relativized) power of polytime machines.


Similarities and differences in major process algebras

I only know CSP and CCS/pi-calculus (not ACP).

CSP was motivated by imperative programming processes communicating via messages.  Hoare then tried to abstract away a simple calculus out of it.  CCS, on the other hand, was an effort to create a foundational calculus like lambda calculus.  Given their original starting points, and given their final form, I would say that they have converged rather than diverged.

What I find common between CSP and CCS is that both of them are based on the notion of "process" (and, by that, I mean an abstract notion of events arranged in time).  The main difference between them is that CSP has two forms of choice (internal/external or nondeterministic/deterministic).  In CCS the two ideas are fused into one.  I think that is an irreconcilable difference.

The distinction between internal and external choice allows CSP to have a semantics in terms of linear traces.  The CCS semantics, on the other hand, has to be based on trees.

I think Hoare's current plan for "Unifying theories" is to put both of them into a single framework.  We have to wait and see what he comes up with!


Any suggestions about a known NP-complete problem that can be reduced to the following problem?

This problem is called Dominating Set, and as pointed out by Raphael in the comments it's a special case of Set Cover (for each vertex, create a set for it and its neighbours).  It's NP-hard.


How to deal with cost variation in a dynamic graph when applying Dijkstra

So if I get this right, you computed Dijkstra for your whole graph (that has no negative cycles) and then you are interested in the shortest path between two specific points. You used estimates, and after choosing the shortest (estimated) path, you compute the real path length (you don't do this before for performance reasons I guess).

Now here are my thoughts on this:

The real path length will very likely vary from the one you computed using estimates. That's why it is called estimates. So you first have to decide whether you are interested in the definitely shortest path or if it is sufficient to find a most likely or approximately shortest path.
For most applications the latter case is sufficient and hence your solution works.
If not, you have some possibilities. You could ignore the decreasing performance and just compute Dijkstra with the real values. This would be the easiest solution.
The best solution that comes to my mind is:

Estimate the length of all edges
Compute Dijkstra
Find shortest path between the desired nodes
If the shortest path contains one or more estimates: Compute the distances between all nodes along the shortest path and replace the corresponding estimates with your results. Go to 2.
Break; the computed path is indeed the shortest path


2D packing in fixed dimensions rectangle

This is equivalent to finding the enclosing square of minimum area for rectangles of size $(w_i/W, h_i/H)$.

You seem to have found algorithms for this problem already. There are many heuristics (here or here) and exact models (here), available when searching for "2D packing algorithm". The ones linked handle the case with variable W and H as well.


Chromatic number of a graph with $10$ vertices each of degree $8$?

Let $G = (V, E)$ be a simple graph like you described (which is unique up to isomorphism and known as the Turán graph $T(10, 5)$, by the way). Note that the maximal degree possible in a graph with $10$ vertices is $9$ and thus, for every vertex $v$ in $G$ there exists a unique vertex $w \ne v$ which is not connected to $v$ and the two vertices share a neighborhood, i.e. $N(v) = N(w)$. Therefore, $v$ and $w$ may be colored using the same color. This however implies that the chromatic number of $G$, denoted by $\chi(G)$, satisfies $\chi(G) \leq 5$ since we can take all such pairs $\{v, w\}$ as described above and assign every such pair a unique color (using 5 colors in total).

To see that $\chi(G)$ cannot be less than $5$ consider the (induced) subgraph $G'$ of $G$ that we get by removing one vertex of every such pair $\{v, w\}$ as described above (that means $vw \notin E$). We find that $G'$ consists of 5 vertices and is complete, therefore implying that $G$ contains a clique of size $5$ and giving us $\chi(G) \geq 5$.

Hence we have shown $\chi(G) = 5$.


Algorithm to find exactly two sets of numbers that have the same sum

This is called the Partition Problem, and it's NP-complete, meaning that it's very unlikely that any algorithm can solve every instance of the problem quickly. On the bright side, if there are $n$ numbers and their total sum is $t$, there is a fairly simple $O(nt)$-time dynamic programming algorithm (see section "Pseudo-polynomial time algorithm" on that webpage), and this is fast enough to solve many practical instances.


Image pattern detection - Finding similarities in same image

I'm no expert in image processing, but generally, repeating patterns can be identified relatively easily in the frequency domain. This is true for signal as well as image processing.

From what I understand of your question, you want to check that each image is composed almost completely of some repeating pattern, and reject those which are not (for example, photos).

You might want to try a Fast Fourier Transform of the image, and look for peaks in the frequency domain. Here is a similar question on SO, and this accepted answer gives good suggestions - try FFT, Wavelet analysis and auto-correlation, in that order of chance of working effectively. The other answers also give links to good references, especially this link.

A google search for "Detect repeating pattern in images" should give you good references, such as this, this, this and this.

Most of these references look for unknown repeating patterns in a given image, and locate those patterns. You would need to perform some post-processing on this that ensures that the repeating pattern (almost) completely covers your image, and not a small portion of the image. This should rule out repeating patterns in parts of the image, say the pattern on a person's shirt.


How rule 110 would be proven to be universal if the tag system did not exist?

More a bunch of references than an answer ....  :-)
As said by @vzn in its comment Cook's proof is very complex and required a lot of work; nevertheless the universality of rule 110 renewed the interest on small model of computations.

Among the most notable results was the proof that rule 110 can simulate a deterministic Turing machine efficiently, i.e. with only a polynomial-time slowdown:

Turlough Neary, Damien Woods: P-completeness of Cellular Automaton Rule 110. ICALP (1) 2006: 132-143
Damien Woods, Turlough Neary: On the time complexity of 2-tag systems and small universal Turing machines. FOCS 2006: 439-448

Along the direction of a simplified/different proof of the universality of rule 110, you can find some work, e.g.:

Richard G.:  Rule 110: universality and catenations. In: Durand B
(ed) Proceedings of the first symposium on cellular automata "Journees
Automates Cellulaires", pp 141-160 (2008)
Juan Carlos Seck Tuoh Mora, Genaro Juárez Martínez, Norberto Hernandez-Romero, Joselito Medina Marín: Elementary cellular automaton Rule 110 explained as a block substitution system. Computing 88(3-4): 193-205 (2010)

For a good survey on universality in cellular automata and other ideas for proving universality:

Nicolas Ollinger: Universalities in Cellular Automata*. Handbook of Natural Computing pp 189-229

Finally a *personal* idea on an alternative approach that could be investigated:

Proving universality of larger CAs (with larger neighbourhood or more states) is much easier and you can even get rid of the intermediate tag-system simulation, so you could investigate if using rule 110 gliders it is possible to simulate an arbitrary larger CA; a slightly similar approach has been used by Nicolas Ollinger and Gaétan Richard in A Particular Universal Cellular Automaton to prove the universality of colliding particles systems (they prove that a particular system can simulate an arbitrary CA)

And don't forget that instead of working on a different proof for rule 110 universality, you can work on the open problem  regarding rule 54 ... is it (weakly) universal ? :-)


Deriving the average depth for a randomly generated binary search tree

Suppose that $T$ is a random tree on $n$ vertices, according to the distribution you consider. Let $T_L,T_R$ be its two subtrees, and let their size be $N_L,N_R$. Let $P$ be the total path length of $T$. Let $P_L(i)$ be the total path length of $T_L$ if $N_L=i$, and zero otherwise, and define $P_R(i)$ similarly. We have
$$
P = \sum_{i=0}^{n-1} (P_L(i) + P_R(n-1-i)) + n-1.
$$
According to linearity expectation, we have
$$
\mathbb{E}[P] = \sum_{i=0}^{n-1} (\mathbb{E}[P_L(i)] + \mathbb{E}[P_R(n-1-i)]) + n-1.
$$
By definition, $\mathbb{E}[P] = D(n)$, where $D(n)$ is the expected internal path length of a random tree on $n$ vertices.

According to your probability distribution, the probability that $N_L=i$ is $1/n$. When that happens, $T_L$ is just a random tree on $i$ vertices. Therefore
$$
\mathbb{E}[P_L(i)] = \Pr[N_L=i] \mathbb{E}[P_L(i)|N_L=i] + \Pr[N_L\neq i] \mathbb{E}[P_L(i)|N_L\neq i] = \\ \frac{1}{n} \cdot D(i) + \left(1-\frac{1}{n}\right) \cdot 0 = \frac{D(i)}{n}.
$$
Therefore we obtain the recurrence
$$
D(n) = \frac{1}{n} \sum_{i=0}^{n-1} (D(i) + D(n-1-i)) + n-1 = \frac{2}{n} \sum_{i=0}^{n-1} D(i) + n-1.
$$
Equivalently,
$$
nD(n) = 2\sum_{i=0}^{n-1} D(i) + n(n-1).
$$
The initial condition is $D(0) = 0$.

We can solve this recurrence using generating functions. Let $P(x) = \sum_{n=0}^\infty D(n) x^n$. First,
$$
P'(n) = \sum_{n=1}^\infty nD(n) x^{n-1}.
$$
Second,
$$
\frac{P(n)}{1-x} = \sum_{n=0}^\infty [D(0) + \cdots + D(n)] x^n.
$$
Third,
$$
\sum_{n=0}^\infty n(n-1) x^{n-2} = \frac{d^2}{dx^2} \frac{1}{1-x} = \frac{2}{(1-x)^3}.
$$
Putting everything together, we obtain
$$
P'(x) = \sum_{n=1}^\infty nD(n) x^{n-1} =
2\sum_{n=1}^\infty (D(0) + \cdots + D(n-1)) x^{n-1} +
\sum_{n=1}^\infty n(n-1) x^{n-1} = \\
\frac{2P(x)}{1-x} + \frac{2x}{(1-x)^3}.
$$
The solution to this ODE is
$$
P(x) = \frac{-2\log (1-x)-2x}{(1-x)^2} = \frac{1}{(1-x)^2} \sum_{n=2}^\infty \frac{2}{n} x^n,
$$
which implies that
$$
D(n) = 2\sum_{m=2}^n \frac{n-m+1}{m} = 2(n+1)(H_n-1)-2(n-1) = 2(n+1)H_n-4n.
$$
Since $H_n = \ln n + \gamma + 1/2n + O(1/n^2)$, we deduce that
$$
D(n) = 2(n+1)(\ln n + \gamma + 1/2n + O(1/n^2)) - 4n = \\
2n\ln n + 2\ln n + (2\gamma-4) n + 2\gamma + 1 + O(1/n).
$$


Find the minimum set of intervals for given set of numbers

To show that the problem has a lower bound of $\Omega (n\log n)$, you can reduce the Element distinctness problem to your problem.


Show that for any natural number n, there is a regular language that is not recognized by any DFA with at most n final states

$\{\lambda, a, a^2, \dots, a^n\}$. All states in which these words are accepted must be different, in order to avoid loops (and stay finite).


Solve Max 3 color problem using 3 color decision problem

The problem "Can a given graph $G$ be 3-colored so that at least $m$ edges are bichromatic?" is in NP, and therefore can be reduced to 3-colorability (since 3-colorability is NP-hard). Using this, you can solve maximum 3 colorability, employing a simple binary search that invokes a 3-colorability oracle $O(\log n)$ times.

There might be a more direct reduction (which might have been the point of the question), but there is no real problem with this answer as well.


Proving a language comprised of 2 languages is regular(with suffix and prefix)

Your language is the concatenation $\Sigma^* L \Sigma^*$, where $L$ is the so-called perfect shuffle of $L_1$ and $L_2$. There are at least two proofs that the perfect shuffle of two regular languages is regular on this site: using automata and using closure operations.

If you are hell-bent on constructing an automaton for $\Sigma^* L \Sigma^*$, start with one for $L$, then follow the automata proof of closure under concatenation (which constructs an NFA).


Each eigenvector of the covariance corresponds to a new feature (which is a combination of the original features).

The principal eigenvector of the covariance matrix corresponds to the direction of maximum variance (not least as mentioned in the question).
Subsequent eigenvectors can be computed one by one under the constraint that they are orthogonal to the ones already computed. The fact that they are orthogonal makes the new features uncorrelated with each other.
In other words, a set of $k$ eigenvectors of the covariance corresponds to a set of $k$ new features that are uncorrelated with each other.

There are many different viewpoints on what exactly principal components are. In general, these seemingly different viewpoints have strong connections with each other. For example, the first $k$ eigenvectors (i.e., the eigenvectors corresponding to the $k$ largest eigenvalues of the covariance matrix) capture the maximum cumulative variance of the data. At the same time they form a basis for a $k$-dimensional subspace (the space of new features) such that if you project your original data (each datapoint individually) on that subspace (i.e., if you optimally approximate each datapoint using the new features), then the total euclidean distance between the original datapoints and their projections is the minimum possible; by minimum we mean in comparison to any other $k$-dimensional subspace.

This short article takes a look at what PCA is from a few different viewpoints.


Example of tree with > 6 vertices, tree would have depth = n after splay() deepest vertex

This is a good question whose answer can help us understand how splay tree tends to keep away from being imbalanced.

No, it is impossible for any rooted tree with more than 5 vertices to become a linear tree after operation splay() one of the deepest vertices, i.e. its depth is one less than the number of vertices.

Why?

For the sake of contradiction, let there be a rooted tree with more than 5 vertices which becomes a linear tree after splaying $x$, one of its deepest vertices. Consider the point of time just before the last splay step that moves $x$ to the root. There are three cases.

That last step is a zig-step (the following graph) or its mirroring zag-step.  Since the resulted tree is linear, part $A$ and $B$ are empty. That means, the left subtree of the root before that step contains node $x$ only. Since $x$ is the deepest node, the whole tree has at most 3 nodes, which is not true.

That last step is zig-zig step (the following graph) or its mirroring zag-zag.  Since the resulted tree is linear, part $A$, $B$ and $C$ are empty. That means, the left subtree of the root before that step contains node $P$ and $x$ only. Part $D$ can have at most two nodes; otherwise, either $x$ was not the deepest node or the resulted tree is not linear. So the whole tree has at most 5 nodes, which is not true.

That last step is a zig-zag step (the following graph) or its mirroring zag-zig. However, after that step, the root will alway has two children, which is not ture.

Exercise. Draw a tree with 5 vertices that becomes a linear tree after splaying one of its deepest vertices.


Maximum Independent Set of a Bipartite Graph

The complement of a maximum independent set is a minimum vertex cover.

To find a minimum vertex cover in a bipartite graph, see König's theorem.


Why is the probability used in the definition of RP complexity classes, arbitrary?

Yes, the constant is entirely arbitrary. Call an algorithm a $p$-algorithm if:

When the correct answer is NO, it always answers NO.
When the correct answer is YES, it answers YES with probability at least $p$.

Note that the probability in the YES case is only over the algorithm's coin tosses.

Given a $p$-algorithm and a constant parameter $m$, we construct a new algorithm which runs the original algorithm $m$ times (with independent coin tosses) and takes the OR of the result. This algorithm is a $1-(1-p)^m$-algorithm (exercise). For every constant $q < 1$ you can find a constant $m$ such that $1-(1-p)^m \geq q$. Hence if a problem admits a $p$-algorithm it also admits a $q$-algorithm, for every $0 < p,q < 1$.


At t=1, you just took action a = d at state s = S and ended in s' = S again with 0 reward. So:

$Q(S,d) = (1 - 1/2)(1) + 1/2[0 + (1)(1)] = 1$ ($maxQ(s',a')$ is the maximum value you can get from state S in this case, which is 1)

So nothing changes. At t=2, it is exactly the same as t=1, so nothing changes again.

At t=3, we just took action p at s = S and ended on state s' = P with reward +1. Thus:

$Q(S,p) = (1 - 1/2)(0) + 1/2[1 + (1)(1)] = 1$ ($maxQ(s',a')$ here refers to $maxQ(P,a')$, the maximum value we can get from state P, which is 1.

So, update $Q(S,p)$ to 1.

At t=4, we just took action a = p at state s = P, ending in state s' = S with reward 0. Thus:

$Q(P,p) = (1 - 1/2)(0) + 1/2[0 + (1)(1)] = 1/2$

So, update $Q(P,p)$ to 1/2.

I think you can do t=5 and t=6 by yourself now, just note that maxQ at a terminal state is 0 (because there is no future reward to accumulate). If you can't, just tell me and I'll update the answer.


Separation guarantee in Goemans Williamson algorithm

Feige and Schechtman, On the optimality of the random hyperplane rounding technique for max cut, constructed a graph on which all $r$ only give an $\alpha$-approximation, where $\alpha$ is the worst-case approximation ratio of the Goemans–Williamson algorithm.


When converting an arbitrary formula into a CNF, you are introducing extension variables. These are new variables that represent subformulas of your formula.

Let us take the following simple formula as an example:

$$ A \lor (B \land C). $$

In order to convert this into a CNF, we need to replace $B \land C$ with an extension variable $\alpha$ which has the same truth value of $B \land C$. We can easily express "$\alpha = B \land C$" as a CNF (or as a DNF). After replacing $B \land C$ with $\alpha$, we obtain the formula
$$
 (A \lor \alpha) \land \text{"$\alpha = B \land C$"}.
$$
(You need to replace "$\alpha = B \land C$" with a CNF.) This formula is equisatisfiable with the original formula: the original formula is satisfiable iff the new formula is satisfiable. Therefore if we are interested in knowing whether the original formula is satisfiable, we can instead ask whether the new one is.

In the transformation outlined above, we used the fact that the class of CNFs is closed under conjunction. That is, we could express add the condition "$\alpha = B \land C$" to our formula while retaining its CNF form. The same is not the case for DNFs, which are closed under disjunction but not under conjunction.

Indeed, consider the opposite situation, in which we want to convert $A \land (B \lor C)$ into an equisatisfiable DNF. We can easily express $\alpha = B \lor C$ as a DNF; the problem is that $(A \land \alpha) \land \text{"$\alpha = B \lor C$"}$ is not a DNF, since we joined $A \land \alpha$ and $\alpha = B \lor C$ with the wrong connective.


Finding a function f(n) which will bring T(n) runtime to O(log^4(n)) (Interview question)

I'm solving the case where $c=1$. Doing it for arbitrary $c$ is made in a similar fashion.

Let take $f(N) = 2^{2^{2^{\sqrt{\frac{\log^{[3]} N}{2}}}}}$.
so that for every integer $N$ we have :
$$T\left(2^{2^{2^N}}\right) = 2 T\left(f\left(2^{2^{2^N}}\right)\right)+1
= 2 T\left( 2^{2^{2^\sqrt{N/2}}} \right)+1.$$

I'm assuming in your question that you are only interested in functions $f$ that are increasing over $\mathbf{N}$.
Let prove that $T(N) = \Theta(\log^{[4]} N)$, that is proving that there exists two positive constants $A,B$ such that for sufficiently big $N$, $$ A\log N \leq T\left(2^{2^{2^{N}}}\right) \leq B\log N.$$

Let assume the last inequality holds up to some $\sqrt{N}>1$, with constant $A=1$ and some  $B > 1$.
Then
$$f\left(2^{2^{2^N}}\right) = 2 T\left( 2^{2^{2^\sqrt{N-1}}} \right)+1,$$
and so by hypothesis:
$$\log N = 2 \log\sqrt{N/2} +1 \leq  T\left(2^{2^{2^N}}\right) \leq 2 B\log\sqrt{N/2}+1 = B \log N +1-B \leq B\log N.$$

We can then conclude by induction, jumping by successive squaring, using the increasing property of $T$ to fill the gaps.


What is the best solution to find whether the sum of an array is even or odd

By a simple "adversary argument", you have to check each element (in some way): Suppose you have missed some element $x$ and get an answer "The sum is even": the adversary can modify $x$ (if it's odd, make it even; if it's even, make it odd), which will change the correct result but not your computation.

The adversary argument tells that in theory you have to check each element. By the way, it does not mean you have to sum them up. You can simply count the numbers of even numbers and odd numbers (or go through the array by +1 for even and -1 for odd).


A set of values that comes with an "add" operation that is associative is called a semigroup.  If it also comes with an element that plays the role of 0 (so that 0 + x = x and x + 0 = x for all x), it is a monoid.

In your case, you have a monoid, as $\{\epsilon\}$ plays the role of 0 (it is an identity).


Why add a +1 to the constant proving an O(n) bound?

We want to find a $c$ such that $4+4n\le cn$ for all $n$ greater than or equal to some bound $N$. So we need a $c$ such that $(4+4n)/n \le c$, or $(4/n)+4\le c$. Now while it's true that
$$
\lim_{n\rightarrow\infty}\frac{4}{n}+4=4
$$
we can't use $c=4$ since for all positive $n$ we have $(4/n)+4>4$. In other words, we need to pick $c$ to be some number larger than 4 and 5 is as good a choice as any in this case. There's nothing magical about picking a $c$ one greater than the limit; it's just one choice out of infinitely many.


What is wrong with this reasoning that finding the genus of a degree 3 bipartite graph is NP-complete?

You cannot reason in this way. Try proving it formally to see what goes wrong.

Also, consider the following example (which is admittedly slightly different than yours). Chromatic number is NP-complete, even for planar graphs. The 4-coloring problem (i.e., the chromatic number problem with the number of colors fixed at 4) is NP-complete. However, the 4-coloring problem for planar graphs is in P.


You're very close!

The key is the difference between recognizable and decidable.

A language $R$ is recognizable if we can build a TM $T$ such that $L(T) = R$. In other words, there's a Turing machine that accepts exactly those strings in the language—and for strings not in the language, it might halt in a non-accepting state (i.e. it might reject), or it might run forever without halting (i.e. it might diverge).

A language $D$ is decidable if we can build a TM $T$ such that $L(T) = D$, and $T$ rejects (halts in a non-accepting state) on strings not in $D$.

It turns out that a whole lot of languages are recognizable but not decidable. The language $H_0 = \{ \langle M \rangle | M \textrm{ halts on empty input} \}$ is undecidable (this is the Empty-Input Halting Problem), but $H_0$ can be recognized by the following procedure (call it $RH$):

  Simulate $M$ on empty input. If it ever halts, accept.

Now we have a Turing machine whose language, $L(RH) = H_0$, is undecidable! Which means the property in question is non-trivial, so by Rice's Theorem that property is undecidable.


You are asking two questions. The first question is about logic more generally. You are wondering whether a statement of the form
$$ \exists x \, \mathrm{True} $$
is valid, although $\mathrm{True}$ doesn't mention $x$. There is absolutely no requirement in the syntax of logical formulas that  you use all the variables you quantify over. This similar to functions which don't depend on all of their arguments. Do you object to the function $f(x) = 1$?

As for your second question, monadic refers to the fact that you are only allowed to quantify over unary predicates. The language itself can freely contain $k$-ary predicates for any $k$. Compare this to first-order logic, in which you are not allowed to quantify over any predicates. Would that mean that first-order logic only allows for 0-ary predicates?


When does Gaussian elimination solve exact 1-in-3 SAT?

Does this always work on larger matrices with 2*n rows and 2*n+1 columns where n is the number of variables? (I think it may need non-redundant (linearly independent?) rows.)

It works but since there are assignments other than -1 and 1, how will you use the row echelon form to make any conclusions about the 1-in-3 SAT instance?

Two cases:

Case 1: The 1-in-3SAT formula is unsatisfiable but the reduced row echelon matrix is satisfiable (because of the possible assignments other than -1/1)
Case 2: Both are satisfiable but assigning a 1 and -1 may bring you back to Case 1

Therefore you will have to try an exponential number of assignments in worst case. Assigning random -1 and 1 values will force you to assign undesirable values during the end of elimination and you will have to backtrack.

If you find an algorithm to find "only the solutions with -1 and 1" or count such solutions or prove there are 0 then it is NP-complete and even co-NP complete.


Can current quantum computers decide languages that Turing Machines cannot?

No. A state of $n$ qubits can be represented with a vector of size $2^n$, and quantum gates can be implemented as linear operations for those vectors. Therefore a quantum computer can be simulated with a Turing machine, although with an exponential overhead. It is also known that the class of problems solvable by a quantum computer in polynomial time, BQP, is contained in the class of problems solvable by a classical computer in polynomial space, PSPACE.

All this information is from the Wikipedia page https://en.wikipedia.org/wiki/Quantum_computing


Find the exactly correct separating hyperplane of SVM when the data is not perfectly linearly separable

I think you can create a "half-hard" SVM problem. It will be like the hard SVM for positive labels (without the error term) but for negative example it will be the like the soft SVM (with the error term).
This wil guarantee you get the line that labels correctly all positive examples, but still tries to label as many of the negative examples as it can (and also create the largest margin it can)
You can do this twice to get both lines $l_1$ and $l_2$.


Reducing from Hamiltonian Cycle problem to the Graph Wheel problem

We will add one extra vertex $v$ to the graph $G$ and we make new graph $G'$, such that $v$ is connected to the all other vertices of $G$. $G$ has a Hamiltonian cycle if and only if $G'$ has a $W_{n+1}$. It is easy to check that if $G$ has a Hamiltonian cycle then $G'$ has a $W_{n+1}$ wheel (just set $v$ as a center). On the other hand, if $G'$ has a $W_{n+1}$ then there are two possibility:

$v$ is the center of $W_{n+1} \rightarrow G $ has a Hamiltonian cycle.
Another vertex $u$ is the center of $W_{n+1}$ in $G'$. So both $deg(u) = deg(v) = n$. Then we can change the labeling of this two vertices (actually they are equivalence under isomorphic), now we have again first possibility.

P.S1: By $W_n$ I mean the wheel with $n$ vertex.

P.S2: In this proof we say if we fix $k=n+1$ (size of the artificial graph), then the problem is NP-Complete in this restricted version, So it's also NP-Complete in the case $k$ is as input parameter.


Boolean variable true iff equation is satisfied in ILP

You can do this by introducing the two inequalities

$$x_1 \le x_2 + M (1-y)$$

and

$$x_1 > x_2 - M y.$$

The former encodes the requirement $y=1 \implies x_1 \le x_2$ (you can see that if $y=1$, then the $M(1-y)$ term disappears; if $y=0$, then $M(1-y)$ becomes something huge and the inequality is automatically satisfied).  The latter encodes the requirement $y=0 \implies x_1 > x_2$ (for similar reasons).

Hopefully this gives you an idea how to handle other kinds of implications as well, should they arise.  Basically, multiply by something big, and add it/subtract it somewhere.


Time complexity of ArrayList Insertion : Calculating sum of X + X/2 + X/4 + X/8 + ... 1

Let's take main phrase from your book:
"If you read this sum left to right, it starts with 1 and doubles until it gets to $X$"
This means, that $X=2^k$, for some $k$. So, simply using geometrical progression, we have
$$1+2+4+\cdots+2^k=\frac{X}{2^k} +\frac{X}{2^{k-1}} + \cdots+\frac{X}{2^2}+\frac{X}{2}+ X = \frac{1-2^{k+1}}{1-2}=2^{k+1}-1=2X-1$$