Does the inverse of a one-way function $f$ being reducible to a predicate $b$ imply that $b$ is a hard-core bit for $f$?

Before addressing your question, we should note that there are some subtleties when defining "inverting $f(x)$ reduces to finding $h(x)$". Suppose we aim towards something along the lines of a standard Turing reduction, then what does our oracle do? When feeding the oracle some string $y\in\{0,1\}^*$, where the only promise about $y$ is that it lies in the image of $f$, then what do you expect it to return? If $f$ is a permutation, then this is easy. However, when $f$ is not one to one, it isn't clear what to expect. One possibility is to require that the oracle returns $h(x)$ for some $x\in f^{-1}(y)$, though it might make the oracle pretty much useless (I'd guess that there exists a one way function $f$ and a hardcore predicate $h$ for $f$ such that any function in $2^{\{0,1\}^*}$ is an $h$-oracle for $f$ under this definition).

Back to your original question. Suppose $f$ is a one way permutation and define $g(x,i,j)=(f(x),i,j,x_i)$. Inverting $f$ reduces to (under the above definition) evaluating $h(x,i,j)=x_j$, since you can feed the oracle different values of $j$. However, $h$ is not hardcore for $g$, since for a uniformly chosen triplet $(x,i,j)$ where $x\in\{0,1\}^n$ and $i,j\in [n]$, with probability $\frac{1}{n}$ it holds that $i=j$ and you can recover $x_j$.


Is it true that all languages which have polynomial circuits are in PSPACE?

Some languages in P/poly are undecidable. For example, any language over the alphabet {a} is in P/poly because for any string length n, either an is in the language or it is not, so the advice string for length n can just be whether or not to accept the string. However, there are uncountably many languages over this alphabet and only countably many Turing machines, so infinitely many of these languages are undecidable.

Every language in PSPACE is, by definition, decidable. Therefore, PSPACE ≠ P/poly.

Hope this helps!


Find a weighted median for unsorted array in linear time

Let $A$ be an input array containing $n$ elements, $a_i$ the $i$-th element and $w_i$ its corresponding weight. You can determine the weighted median in worst case linear time as follows. If the array length is $\leq 2$, find the weighted median by exhaustive search. Otherwise, find the (lower) median element $a_x$ using the worst case $O(n)$ selection algorithm and then partition the array around it (using the worst case $O(n)$ partition algorithm from QuickSort). Now determine the weight of each partition. If weight of the left partition is $< \frac{1}{2}$ and weight of the right partition is $\leq \frac{1}{2}$ then the weighted (lower) median is $a_x$. If not, then the weighted (lower) median must necessarily lie in the partition with the larger weight. So, you add the weight of the "lighter" partition to the weight of $a_x$ and recursively continue searching into the "heavier" partition. Here is the algorithm's pseudocode (written in Latex).

FIND-WEIGHTED_LOWER_MEDIAN(A)
    if $n$ == 1
       return $a_1$
    elseif $n$ == 2
       if $w_1 \geq w_2$
          return $a_1$
       else
          return $a_2$
    else
       determine $a_x$, the (lower) median of A
       partition A around $a_x$
       $W_{low}$ = $\sum\limits_{{a_i} < {a_x}} {{w_i}}$
       $W_{high}$ = $\sum\limits_{{a_i} > {a_x}} {{w_i}}$
       if $W_{low} < \frac{1}{2}$ AND $W_{high} \leq \frac{1}{2}$
          return $a_x$
       else if $W_{low} \geq \frac{1}{2}$
               $w_x = w_x + W_{high}$
               B = \{ a_i \in A: a_i \leq a_x \}
               FIND-WEIGHTED_LOWER_MEDIAN(B)
            else
               $w_x = w_x + W_{low}$
               B = \{ a_i \in A: a_i \geq a_x \}
               FIND-WEIGHTED_LOWER_MEDIAN(B)

Now let's analyze the algorithm and derive its complexity in the worst-case. The recurrence of this recursive algorithm is $T(n) = T(\frac{n}{2} + 1) + \Theta(n)$. Indeed, we have no more than a recursive call on half the elements plus the (lower) median. The initial exhaustive search on up to 2 elements costs $O(1)$, determining the (lower) median using the select algorithm requires $O(n)$, and partitioning around the (lower) median requires $O(n)$ as well. Computing $W_{low}$ or $W_{high}$ is again $O(n)$. Solving the recurrence, we get the complexity of the algorithm in the worst case, which is $O(n)$.

Of course, a real implementation should not use the worst case $O(n)$ selection algorithm, since it is well known that the algorithm is not practical (it is of theoretical interest only). However, the randomized $O(n)$ selection algorithm works pretty well in practice and can be used since it's really fast.


Async Distributed Algorithm Time Complexity

In a distributed system, messages can be sent in parallel.  Vertex #1 can send a message at the same time as vertex #2 is sending a message.  So, the total amount of time to complete the algorithm might be much less than the total number of messages sent.


You are thinking correctly but a small error is there in writing the regular expression. The regular expression is $r = ((00+11)(0+1)^*)+((0+1)^*(00+11))$.


Optimal algorithm for signaling for help?

Your problem is very similar to the well-known cow-path problem, though the details are a bit different. When talking about optimal algorithms, we are usually concerned with minimizing the competitive ratio (a concept from the field of online algorithms), which is the worst ratio between the solution produced by your algorithm and the one produced by the optimal algorithm (in this case, $n$). If your algorithm searches the sequence $a_1 < a_2 < \ldots$ then the competitive ratio is
$$ \sup_n \frac{\sum_{i\colon a_{i-1} < n} a_i}{n}. $$
(Here $a_0 = 0$.)

Suppose we're aiming for a competitive ratio of $C$ (your algorithm gives $C = 4$). Considering $n=1,a_1+1,a_2+1,\ldots$, we must have
$$
\begin{align*}
a_1 &\leq C, \\
a_1 + a_2 &\leq C(a_1 + 1), \\
a_1 + a_2 + a_3 &\leq C(a_2 + 1), \\
&\ldots
\end{align*}
$$
The classical solution to the cow-path problem (Searching in the plane) shows that $C \geq 4$, and so your algorithm achieves the optimal competitive ratio.


Given that at least N "operations" are needed since each array element is affected, you can't get the number of operations down by much. It's not clear what your complexity measure exactly is – why is sum += array[i] a single operation? What about the loop? The actual CPU needs to increment i and compare it to array.size(), there are jumps involved and so on. The operation sum += array[i] is probably more than one instruction. Not to mention things you actually forgot to count, like sum = 0.

That said, I can't see how to improve on your algorithm, and I don't think it's possible, though as mentioned above, the notion of complexity is very shaky here, so perhaps there is a "trick" which will work under your complexity measure, whatever it is.


A type is a property of computations. It's what you write on the right-hand side of a colon.

Let me elaborate on that. Note that the terminology isn't completely standard: some articles or books may use different words for certain concepts.

A term is an element of an abstract syntax that is intended to represent computation. Intuitively, it's a parse tree. Formally, it's a finite tree where the nodes belong to some alphabet. An untyped calculus defines a syntax for terms. For example, the (untyped) lambda calculus contains terms (written $M$, $N$, etc.) built from three types of nodes:

variables, of arity 0 (a denumerable collection thereof), written $x$, $y$, etc.;
application of a variable, of arity 1 (a denumerable collection thereof, with a bijection to variables), written $\lambda x. M$, etc.;
application, of arity 2, written $M \, N$.

A term is a syntactic construction. A semantics relates terms to computations. There are many types of semantics, the most common being operational (describing how terms can be transformed into other terms) or denotational (describing terms by a transformation into another space, usually built from set theory).

A type is a property of terms. A type system for an untyped calculus describes which terms have which types. Mathematically, at the core, a type system is a relation between terms and types. More accurately, a type system is a family of such relations, indexed by contexts — typically, a context provides at least types for variables (i.e. a context is a partial function from variables to types), such that a term may only have a type in contexts that provide a type for all its free variables. What kind of mathematical object a type is depends on the type system.

Some type systems are described with types as sets, using notions of set theory such as intersection, union and comprehension. This has the advantage of resting upon familiar mathematical foundations. A limitation of this approach is that it doesn't allow reasoning about equivalent types.

Many type systems describe types themselves as terms in a calculus of types. Depending on the type system, these may be the same terms or different terms. I'll use the phrase base term to refer to a term of the calculus that describes computation. For example, the simply typed lambda calculus uses the following calculus of types (written $\tau$, etc.):

base types, of arity 0 (a finite or denumerable collection thereof), written $A$, $B$, etc.;
function, of arity 2, written $\tau_0 \rightarrow \tau_1$.

The relation between terms and types that defines the simply typed lambda calculus is usually defined by typing rules. Typing rules are not the only way to define a type system, but they are common. They work well for compositional type systems, i.e. type systems where the type(s) of a term is built from the types of subterms. Typing rules define a type system inductively: each typing rule is an axiom that states that for any instantiation of the formulas above the horizontal rule, the formula below the rule is also true. See How to read typing rules? for more details. Does there exist a Turing complete typed lambda calculus? may also be of interest.

For the simply typed lambda calculus, the typing judgement $\Gamma \vdash M : \tau$ means that $M$ has the type $\tau$ in the context $\Gamma$. I've omitted the formal definition of contexts.
$$
\dfrac{x:\tau \in \Gamma}{\Gamma \vdash x : \tau}(\Gamma)
\qquad
\dfrac{\Gamma, x:\tau_0 \vdash M : \tau_1}{\Gamma \vdash \lambda x.M : \tau_0 \rightarrow \tau_1}(\mathord{\rightarrow}I)
\qquad
\dfrac{\Gamma \vdash M : \tau_0 \rightarrow \tau_1 \quad \Gamma \vdash N : \tau_0}{\Gamma \vdash M\,N : \tau_1}(\mathord{\rightarrow}E)
$$

For example, if $A$ and $B$ are based types, then $\lambda x. \lambda y. x\,y$ has the type $(A \rightarrow B) \rightarrow A \rightarrow B$ in any context (from bottom to top, apply $(\mathord{\rightarrow}I)$ twice, then $(\mathord{\rightarrow}E)$, and finally $(\Gamma)$ on each branch).

It is possible to interpret the types of the simply typed lambda calculus as sets. This amounts to giving a denotational semantics for the types. A good denotational semantics for the base terms would assign to each base term a member of the denotation of all of its types.

Intuitionistic type theory (also known as Martin-Löf type theory) is more complex that simply typed lambda calculus, as it has many more elements in the calculus of types (and also adds a few constants to the base terms). But the core principles are the same. An important feature of Martin-Löf type theory is that types can contain base terms (they are dependent types): the universe of base terms and the universe of types are the same, though they can be distinguished by simple syntactic rules (usually known as sorting, i.e. assigning sorts to terms, in rewriting theory).

There are type systems that go further and completely mix types and base terms, so that there is no distinction between the two. Such type systems are said to be higher-order. In such calculi, types have types — a type can appear on the left-hand side of the $:$. The calculus of construction is the paradigm of higher-order dependent types. The lambda cube (also known as Barendregt cube) classifies type systems in terms of whether they allow terms to depend on types (polymorphism — some base terms contain types as subterms), types to depend on terms (dependent types), or types to depend on types (type operators — the calculus of types has a notion of computation).

Most type systems have been given set-theoretical semantics, to tie them with the usual foundations of mathematics.
How are programming languages and foundations of mathematics related? and
What is the difference between the semantic and syntactic views of function types? may be of interest here. There has also been work on using type theory as a foundation of mathematics — set theory is the historic foundation, but it is not the only possible choice. Homotopy type theory is an important milestone in this direction: it describes the semantics of intentional intuitionistic type theory in terms of homotopy theory and constructs set theory in this framework.

I recommend Benjamin Pierce's books Types and Programming Languages and Advances Topics in Types and Programming Languages. They are accessible to any undergraduate with no prerequisite other than basic familiarity with formal mathematical reasoning. TAPL describes many type systems; dependent types are the subject of chapter 2 of ATTAPL.


Concise example of exponential cost of ML type inference

In this answer, I'll stick to a core ML fragment of the language, with just lambda-calculus and polymorphic let following Hindley-Milner. The full OCaml language has additional features such as row polymorphism (which if I recall correctly doesn't change the theoretical complexity, but with which real programs tend to have larger types) and a module system (which if you poke hard enough can be non-terminating in pathological cases involving abstract signatures).

The worst-case time complexity for deciding whether a core ML program has a type is a simple exponential in the size of the program. The classical references for this result are [KTU90] and [M90]. A more elementary but less complete treatment is given in [S95].

The maximum size of the type of the type of a core ML program is in fact doubly exponential in the size of the program. If the type checker must print the type of the program, the time may therefore be doubly exponential; it can be brought back to a simple exponential by defining abbreviations for repeated parts of the tree. This can correspond to sharing parts of the type tree in an implementation.

Your example shows exponential growth of the type. Note, however, that it is possible to give a linear-size representation of the type by using abbreviations for repeated parts of the type. This can correspond to sharing parts of the type tree in an implementation. For example:

# fun d c b a -> d c b (c b (b a));;
t2 -> t2
where t2 = (t1 -> 'b -> 'c) -> t1 -> 'a -> 'd
where t1 = 'a -> 'b

Here is a conceptually simpler example: the size of the type of the pair (x,x) is twice the size of the size of the type of x, so if you compose the pair function $N$ times, you get a type of size $\Theta(2^N)$.

# let pair x f = f x x;;
# let pairN x = pair (pair (pair … (pair x)…));;
'a -> tN
where tN = (tN-1 -> tN-1 -> 'bN) -> 'bN
…
where t2 = (t1 -> t1 -> 'b2) -> 'b2
where t1 = ('a -> 'a -> 'b1) -> 'b1

By introducing nested polymorphic let definitions, the size of the type increases again exponentially; this time, no amount of sharing can shave off the exponential growth.

# let pair x f = f x x;;
# let f1 x = pair x in
  let f2 x = f1 (f1 x) in
  let f3 x = f2 (f2 x) in
  fun z -> f3 (fun x -> x) z;;

References

[KTU90] Kfoury, J.; Tiuryn; Urzyczyn, P. (1990). "ML typability is dexptime-complete". Lecture Notes in Computer Science. CAAP '90 431: 206-220. [Springer] [Google]

[M90] Mairson, Harry G. (1990). "Deciding ML typability is complete for deterministic exponential time". Proceedings of the 17th ACM SIGPLAN-SIGACT symposium on Principles of programming languages. POPL '90 (ACM): 382–401. [ACM]

[P04] Benjamin C. Pierce. Advanced Topics in Types and Programming Languages. MIT Press, 2004. [Amazon]

[PR04] François Pottier and Didier Rémy. "The Essence of ML Type Inference". Chapter 10 in [P04]. [pdf]

[S95] Michael I. Schwartzbach. Polymorphic Type Inference. BRICS LS-95-3, June 1995. ps


(Criterion of no-op Kleene star) Let $V$ be a language such that $\epsilon\in V$. Then $V=V^*$ if and only if $V=VV$, where $V^*$ is the Kleene star.

Proof: "$\Longrightarrow$":  $V=V\epsilon\subseteq VV$ while $VV\subseteq V^*=V$.

"$\Longleftarrow$". $V\subseteq V^*$ by definition. Let $V_i$ as defined in Wikipedia. Since $V_0\subseteq V$ and assuming $V_n\subseteq V$, $V_{n+1}=V_nV\subseteq VV=V$, we know $V_i\subseteq V$ for all $i\ge0$ by induction. Hence $$V^*=\bigcup_{i=0}^\infty V_{i+1}\subseteq \bigcup_{i=0}^\infty V=V\,.$$

Exercise 1. Show that $\epsilon\in B$ and $B=BB$.

Exercise 2. Let $V$ be a non-empty language such that $V=VV$. Show that $\epsilon\in V$. (Hence for a non-empty language $V$, $V=V^*$ if and only if $V=VV$.)

Exercise 3. Show that $V^*=(V^*)^*$.


Is $\{w~|~\forall x \in T(M_v):|w|>|x|~\}$ decidable?

Yes, you are missing something.
The first argument that this language is co-semi-decidable is correct. However, the second one is wrong (and not formally written. A formal proof could not consist of such arguments, they are only for intuition usually).
Now to show why it is fully decidable:
We know that $|T(M_v)|=c<\infty$. Now, since this is a constant smaller than infinity, there must be an $x_0\in T(M_v)$ for which $|x_0|$ is the longest from the words in $T(M_v).$
Now, build the turing machine that accepts $w$ iff $|w|>|x_0|$.
Since $x_0$ is the longest, then if $|w|>|x_0|$ we will have that $\forall x\in T(M_v):|w|>|x_0|\ge|x|$ and thus $w$ is in your language. Now, if $|w| \le |x_0|$, then obviously $w$ is not in your language.
Thus $w$ is in your language iff $w$ is accepted by the turing machine we built.


Use the Sipser-Lautemann theorem: $\mathrm{BPP} \subseteq \Sigma_2^p \cap \Pi_2^p$.


What's the usage of $S$ in Dijkstra shortest path algorithm in the book Introduction to Algorithms?

Yes, the set $S$ is not needed in the Dijkstra’s algorithm, which is at the beginning of section 24.3, Dijkstra’s algorithm of the book introduction to algorithms by CLRS, third edition. That is, line 2 and line 6 in procedure DIJKSTRA($G,w,s$) can be removed without affecting the algorithm.

One immediate purpose of $S$ is to facilitate the proof of theorem 24.6 (Correctness of Dijkstra’s algorithm) of the book. Also, other implementations of Dijktra's might use that set more visibly such as the set of visited nodes in Wikipedia's entry. It is indeed a cornerstone concept to understand Dijktra's algorithm.

By the way, your observation that the line 7 of line 7 could be improved to "for each vertex $v \in G.Adj[u]\setminus S$" is very nice. In fact, that is done in the Wikipedia' entry mentioned above. Should that be done, $S$ could not be removed  any more as you have emphasized.


Defining decision-problem complexity classes by counting branches of a polynomial-time NTM

In the abstract of Counting classes: thresholds, parity,
mods, and fewness”, by Beigel and Gill, any class of languages whose membership of some input $x$ can be determined by some function of $\#M(x)$ (the number of accepting paths of the NTM $M$ on input $x$) is considered a counting class.

In regards to your "counting description" of some known classes, your characterization of $\mathsf{ZPP}$ is actually a description of $\mathsf{P}$ (there is no mentioning of the power of expected polynomial time over worst case polynomial time). Additionally, your description of $\mathsf{P}$ is not very clear, a Turing machine can be either deterministic or non deterministic (those are different models of computation), so there is no NTM which is "actually deterministic". It is not clear how to give a counting characterization of $\mathsf{ZPP}$, since it differs from the rest of the classes by relaxing the polynomial time property.

Additionally, note that in the NP/coNP case you have an equivalence, i.e. $x\in L$ iff there exists some accepting path/ iff all paths are accepting. Requiring only one implication results in a stronger class.


Algorithm: Finding median in a sorted array with duplicates

Yes. Even with duplicates, the process of finding median is same. See  this link - https://math.stackexchange.com/questions/1191119/how-to-find-the-median-of-three-numbers-if-one-of-them-appears-twice


Any algorithm better that O(N*logN) for a problem of finding student with largest average score in a list of N scores of the form StudentID, score

You are on a good path, but seem to be confused for no reason. After step 2 you have created an array with average scores. This is a worst case O(N) size array. What is the complexity of finding the highest average score now? Do you need to sort the array?


Find the point with minimum max distance to any point in a set

This is the smallest enclosing circle problem, and can be solved in linear time. Also, these slides describe a randomized algorithm that runs in expected linear time.


Have I got the right understanding of the mu operator?

Hint: $h(x)$ is always a non-negative integer (whenever it's defined).

As a side note, usually primitive recursive functions are assumed to be non-negative, and so $\max(xy-5,0)$ is more usual than what you wrote.


The term "polynomial delay", in this case, appears to refer to the time complexity of generating (or enumerating) subsequent solutions. This is a bit different than our standard notion of runtime, since we usually only consider single executions of a machine or algorithm on an input. The delay complexity measure deals with time spent between enumerations through a set (e.g. a set of solutions).

Suppose you are working with a large dataset or database. You might want to step through or enumerate solutions to some problem using that data as an input. There are at least two steps involved here:

Initialization (perhaps generating your first solution)
Computing the next solution for the purpose of enumeration.

For example, you might use a polynomial space or exponential time algorithm to initialize and preprocess your data. To find or generate multiple solutions to a problem, you may only need to do a little bit of extra work. The time complexity with generating that next solution is the time delay complexity measure that you encountered in that paper. In particular, the time delay between enumerations is polynomial in respect to the input.

Jan Ramon mentions this and other time complexity measures in his talk on "General Graph Refinement with Polynomial Delay":
http://videolectures.net/mlg07_ramon_ggr/


Finding median weights in all paths of an AVL tree with weighted nodes

Your main AVL tree has $n$ nodes. On each you build a small AVL tree with a nomber of nodes bounded by $\log n$, so that the insertion of each node on the small AVL tree has a cost $\log\log n$ steps. Overall that makes $O(n\log n\log\log n)$ steps, not $O(n\log\log n)$ as stated in your step 2.


Database Theory - Does the dependency preservation and lossless join properties hold for every decomposition of a relation into 3NF?

Is it possible to have multiple (different) decompositions of a relation into 3NF, as the claim seems to imply?

Yes, consider for instance the relation schema R(A, B, C, D), with F, a cover of the functional dependencies holding in R, equal to:

A → B
C A → D
D → A

Both the decomposition:

R1(A B)
R2(A D)
R3(C D)

and

R1(A B)
R2(A C D)

are in 3NF (actually the first is also in BCNF).

  Is it the case that every decomposition (assuming the answer to first is Yes) of a relation into 3NF is dependency preserving?

No, in the first decomposition the functional dependency AC → D is not preserved.
Note that both decompositions are lossless (in general, there is no interest in lossy decompositions).

Final note: since there are different possible decompositions, these and their properties depends on the algorithm used to find them. For instance, the classical “analysis” algorithm for BCNF is guaranteed to produce a lossless decomposition, but it is not guaranteed to preserve the dependencies, while the classical “synthesis” algorithm to produce the 3NF is guaranteed to be lossless and preserve the dependencies, as well (but it could find a decomposition in which not all the anomalies are eliminated).


You can generate any distribution by using a standard PRNG to choose $X$ uniformly from the interval $[0,1]$ and then returning $F^{-1}(X)$, where $F$ is the cumulative distribution function of the distribution you're interested in.

For the Gaussian distribution, though, it's usually better to use Box–Muller or ziggurat.


How to view Graph Reduction/Graph Representation for a Haskell program?

Welcome to CS.SE!
I cannot present the underlying algorithms themselves, just the concepts they use.
The normal form (NF) of some expression is basically its result, like 42, Just 1, \ x -> 1 + x.
The weak head normal form (WHNF) is some expression which is one of three:

A lambda: \ x -> x + 5 * 6. The NF is \ x -> x + 30.
Data constructor: (3, 2 + 5). The NF is (3, 7). It could be partially applied: (,) (2 * 5). The NF is \ x -> (10, x).
Partially applied built-in function: (+) (2 * 8). The NF is \ x -> 16 + x.

As one can see, WHNF generalizes NF.
So, what have graphs got to do with this? Well, one can understand f e1 e2 ... en as a graph with a node f which is connected with n other nodes: e1, e2, ..., en. Evaluation is the reduction of the nodes1. To show why this is actually very cool I am going to use a picture which I stumbled upon on Wikipedia and HaskellWiki not so long ago:

So, what is going on in this picture? The idea is simple: when working with lists, we have a binary operation (:) and some initial value []. When we are folding, we have a binary operation f and some initial value z. The data structure does not change - only the nodes of our graph. To get the complete result (NF, that is), we reduce the graph.
(Please note that the initial 1 : 2 : 3 : 4 : 5 : [] could not have been reduced any further; in (pseudo-)haskell the lists are: data [a] = a : [a] | [].)

1Some technical details on evaluation (the basic tools to manipulate graphs, just as you have asked). The programmer might force the reduction. seq x y forces its first argument to the WHNF and returns the second (being basically flip const magically strict in the first argument). More formally:

...seq x y means that whenever y is evaluated to weak head normal form, x is also evaluated to weak head normal form.

If the programmer wants to do the same for the NF, they should take a look at Control.DeepSeq.deepseq.


Worst-case expected running time for Randomized Permutation Algorithm

Firstly I would revise the inner for loop so that checking whether $r$ has been used already, is $O(1)$. As stated, it is $O(n)$.  You could do this by initializing a (1-indexed) boolean array $used[\cdot]$ of length $n$, and setting $used[x]$ equals true whenever you set some $A[i]=x$.

Now the question is how many times may $rand()$ be called in the worst case. Actually, the way the algorithm is set up right now, the worst case is $+\infty$; this is because it's not learning from any of its bad choices of $r$. For instance, if it selects $5$, when $5$ was already in $A$, then the smart thing to do would be never to guess $5$ again. There are ways to achieve this; so if you had some method that never repeated guesses, then you can get $O(n^2)$ worst case runtime.

If you are interested in expected runtime, then you can calculate the expected number of times $r$ is recalculated in any given step: at step $i$, there are $n-i$ good choices, for a success probability of $\frac{n-i}{n}$. The expectation for number of tries to get a first success in a bernoulli variable with probability $p$, is $\frac{1}{p}$. Then if you sum $\frac{n}{n}+\frac{n}{n-1}+\frac{n}{n-2}+\cdots \frac{n}{1}$ you have asymptotic $O(n\log n)$.  This is basically the coupon collector's problem.


How to Implement a reversible OR operator with a Fredkin gate (controlled swap)?

As also stated in the relevant Wikipedia page, you can do it by using the first two inputs (the control-bit and one of the target bits) as input for the reversible OR, and the third input bit fixed with the value 1.
Then, the second output is what you want.

To better see this, write the general action of a Fredkin on an input as following:
$$\begin{pmatrix}a\\b\\ c\end{pmatrix}\mapsto
\begin{pmatrix}
a \\
(a c)\oplus[(1\oplus a)b] \\
(a b)\oplus[(1\oplus a)c]
\end{pmatrix}.$$
Note that this is just rewriting the action of the Fredkin algebraically.

Then, if you use as input $(a,b,1)$, you get

$$\begin{pmatrix}a\\b\\ 1\end{pmatrix}\mapsto
\begin{pmatrix}
a \\
a\oplus[(1\oplus a)b] \\
(a b)\oplus(1\oplus a)
\end{pmatrix},$$
which is what you want as soon as you notice that $a \oplus b\oplus ab=a\,\operatorname{OR}\, b$.


Finding three factors of a number with minimal sum

The problem does not require exponential time. It can be solved in subexponential, but superpolynomial time.

The first step is to find the prime factorization of $x$, which can be done with the general number field sieve.

Next, enumerate all possible values of $a,b$ and for each tuple $(a,b)$ compute $c$ to find the triple with the minumum sum. A number $x$ has at most $\exp(O(\log x / \log \log x))$ divisors, so there are also at most $\exp(O(\log x / \log \log x))$ such tuples.


We can solve this problem just by doing DFS from each vertex.

For each vertex $u \in G$, start the DFS from each vertex $v$ such that $v$ is the direct descendant of $u$, ie. $(u,v)$ is an edge.
For each vertex $v'$ reachable by the DFS from $v$, remove the edge $(u, v')$.

The overall complexity of the above is the complexity of running $N$ DFS', which is $O(N(N+M))$.


Let $L=\{\langle M \rangle \mid M \text{ is a TM such }L(M)\in R\}$, where $\langle M\rangle$ is the encoding of a TM $M$, and $R$ is the set of all decidable languages. This is the language in question.
Notice that $R\neq \emptyset$ and also since there are languages not in $R$ (like the halting problem), then $R\neq RE$. Simply put, $R$ is not trivial (obviously).
Apply Rice's theorem on the property $"R"$, to directly get that $L$ is not decidable.


What is the best way to compress a string with only numbers and commas in it?

Treat this as a base-11 number (the comma is treated like the digit "10").  Convert the base-11 number to binary, and use the resulting binary string as the compressed version of your data.

This will be close to optimal.  It falls short of optimal only in that it does not take into account the guarantee that every number in the list will have at most 3 digits -- but even taking that into account would not improve the compression ratio much.

The absolute best method will depend on the distribution of data that you will be compressing; but I expect this will be close to optimal for most real-world distributions.


To answer your first question, see: Burkhard Monien,
Two-way multihead automata over a one-letter alphabet.
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (1980) https://eudml.org/doc/92118

".. we show that for languages over a one-letter alphabet two-way automata with $k+1$ heads are more powerful than two way automata with $k$ heads."

This improves over a similar result of the same author and others for two-letter alphabets, one-way automata, or stepping from $k$ to $k+4$-heads, see the paper.

Also an interesting quote "It is wellknown that SPACE(log n), the class of languages acceptable within space bound log n, is identical with the class of  languages acceptable by two-way multihead automata".


Ant colony optimization for continuous functions

No, discretizing solution space is not necessary

I read page 14 of paper you provided and then went googling.

I found this 2014 paper: A unified ant colony optimization algorithm for continuous optimization that mentioned a bit of history of ACO on continuous function.

Tracing from that, I think the best paper to begin is this 2008 paper Ant colony optimization for continuous domains coauthored by the original creator of ACO, Marco Dorigo, himself.

Quote from page 76 this paper:

  The fundamental idea underlying $ACO_R$ is the shift from using a
  discrete probability distribution to using a continuous one...

That is instead of remembering pheromone value in discrete boxes, you remember in a form of probability distribution function (PDF) that is parameterized for updates. The moving of the ants (solution points) is also continuous.
The ants move random directions across the dimensions of solution space (as opposed to moving from box to box as in the first paper you gave.)

I hope I have answered some of your question and provide some references for further reading without digging too deep in myself.


distinguishing between CTL* formulas $A[FG p]$ and $AFAG p$ using transition system

(This is the "standard" example which proves that CTL is not a superset of LTL, in terms of expressiveness)

Consider this system:

state $q0$, transitions to $q0$ and $q1$
state $q1$, transition to $q2$
state $q2$, transition to $q2$

Let $p$ be true in $q0,q2$ but not in $q1$.

(p)     (not p)    (p)
 q0 ----> q1 ----> q2
| ^               | ^
\-/               \-/

State $q0$ does not satisfy formula $AF[AGp]$. Take the infinite path $q0,q0,q0,\ldots$. There is no state in the path satisfying $AGp$ since we can only pick $q0$ and from there the path $q0,q1,q2,q2,q2,\ldots$ does not satisfy $Gp$ since $q1$ does not satisfy $p$.

State $q0$ however satisfies $A[FGp]$. Take any infinite path starting from $q0$. Either it is of the form $q0,q0,q0,\ldots$ or of the form $q0,q0,q0,\ldots,q0,q1,q2,q2,q2,\ldots$. Both forms satisfy $FGp$.


If A is reducible to B and B is reducible to A, and A is NPC, is B also NPC?

First, note that there are two problems frequently called the "Maximum Clique Problem".

One of them is the Clique Decision Problem: given an undirected graph $G$ and a number $k$, does $G$ contain a clique with at least $k$ vertices? This is one of Karp's 21 Problems, the original list that made NP-completeness famous. The proof involved reducing to it from the Boolean Satisfiability Problem, the very first original NP-complete problem. And a verifier for this is easy to make: check whether the set given as a solution actually does contain $k$ or more vertices, and is actually a clique.

The other is the Maximum Clique Size Problem: given an undirected graph $G$, what is the size of the largest clique in $G$? This can be shown to be NP-hard by reduction from the Clique Decision Problem, by simply comparing the size of the largest clique with $k$. And as you mentioned, it can apparently be shown to be in NP by reduction to the Clique Decision Problem: for every integer from the number of vertices down to 1, check if there's a clique of that size, and if so return that number.

So it would seem that both versions of the problem are NP-complete. But be careful about the definition of NP. NP is defined as a class of decision problems, and the Maximum Clique Size Problem is not a decision problem.

Specifically, NP is the class of decision problems where, if the answer is yes, you can be given extra information of polynomial size that lets you verify that the answer is yes in polynomial time. (If the answer is no, you can't necessarily verify it, unless NP = co-NP.) So for problems which aren't answered with yes or no, trying to put them in NP just doesn't make sense.

So while the Maximum Clique Size Problem is indeed NP-hard, and can be reduced to an NP-complete problem in polynomial time, it is not in fact in NP. And thus it cannot be NP-complete. This is why you can't make a verifier for it (unless NP = co-NP, which is an open question).


Which one should I report as total network I/O bytes among Sum(InBound) or Sum(InBound + OutBound)?

I would suggest reporting the sum of both.

As a general principle, the best solution is to define your metrics in the report or paper where you write up your results.  You should describe what you measured and how you measured it.  This includes clarifying whether "total network I/O" includes both inbound+outbound traffic or only inbound traffic.


How to "properly" handle incorrect values in a random walk?

A random walk $(X_i)$ can't become negative if there are no positive-probability transitions to negative values. One condition that causes it to stay finite with probability $1$ is that, for all large enough $n$, $\mathbb{E}(X_{i+1}|X_i=n)<n$.


Forming red-black tree from binary tree conserving in-order traversal

Iterative insertion gives a time complexity of $O(n \log n)$ for $n$ keys, but it's possible to do it in linear time.

The input tree gives you the in-order traversal, so you can begin by traversing the input tree and storing the keys in an array. Now, notice that if $n = 2^m - 1$ for some $m$, it's actually trivial to create a new binary tree which is perfectly balanced: split the array in half, choose the middle element as the root, and recursively build the left and right children from the two halves of the array. To make it a red-black tree, you have to assign colors. For a perfectly balanced tree, this is simple: you can actually make every node black.

But how do you handle the general case, when $n$ is not one less than a power of 2? You won't be able to make a perfectly balanced tree, but you can get pretty darn close!

This smells like a homework assignment, so I'll leave the specifics of assigning colors to you, but here's something to get started. Notice that, when you split the array of keys in half, the two halves have either exactly the same number of keys, or they differ by one. When they have exactly the same number of keys, assigning colors is easy. When they don't, you might need to use some red nodes...


Time complexity of a backtrack algorithm

The running time of your algorithm is at most $N (N-1) (N-2) \cdots (N-K+1)$, i.e., $N!/(N-K)!$.  This is $O(N^K)$, i.e., exponential in $K$.

Justification: There are $N$ possible choices for what you put into the first blank, and in the worst case you might have to explore each.  There are $N-1$ choices for the second blank, and so on.  You can draw a tree of the choices made: the first level shows the choice of what to put in the first blank, the second level shows the choice of what to put in the second blank, and so on.  The degree of the root is $N$; the degree of the nodes at the second level is $N-1$; and so on.  The number of leaves is the product of the degrees at each level, i.e., $N (N-1) (N-2) \cdots (N-K+1)$.  In the worst case, your algorithm might have to explore every possible node in this tree (if it is not able to stop early before reaching the $K$th level and backtrack from a higher-up node).  Therefore, this is a valid upper bound for the running time of your algorithm.

If you want a tighter analysis, here is the exact worst-case running time (not an upper bound).  The number of leaves in your search tree, in the worst case, is the number of strictly increasing sequences of length $K$ over $\{1,\dots,N\}$ that start with 0.  (We can assume without loss of generality that the first blank contains a 0, as you point out, which is why we can restrict to sequences that start with a 0.)  That number is exactly $C(N-1,K-1) = (N-1)!/((K-1)!(N-K)!)$.

This is a tighter analysis, but it doesn't save us from exponential running time.  When $N\gg K$, $C(N-1,K-1)$ is still $O(N^K)$, i.e., exponential in $K$.

That said, evaluating your algorithm experimentally (by testing it on some real data sets) would probably be a better way to evaluate your algorithm than trying to derive a worst-case running time.  You might want to compare it to the performance of translating your problem into a SAT instance and using an off-the-shelf SAT solver.  Depending upon the value of $N$ and $K$, there might be other better alternatives as well.

See also the following question for a closely related problem, and for algorithms to solve it:

How to obtain the unknown values ai,bj given an unordered list of ai−bjmodN?


NP-hard or not: partition with irrational input or parameter

The problem you have stated probably contains an error:

  Given a set $N$ with $n+2$ numbers, such that the first $n$ numbers are positive and rational with sum $1$, the $(n+1)$st number is $\sqrt{2}$, and the $(n+2)$nd number is $2 - \sqrt{2}$, determine whether there is a subset of $N$ such that the sum of the subset is $3/2$.

The answer is that there is never any such subset. Either the subset includes $\sqrt{2}$ and $2 - \sqrt{2}$, or neither. If it includes neither, then the sum is less than or equal to $1$. If it includes both, then the sum is greater than or equal to $2$. So the sum of the subset will never be $3/2$.


We have
$$
\frac{n!}{(n/2)!(n/4)!\cdots 2!} =
\frac{n!}{(n/2)!(n/2)!} \frac{(n/2)!}{(n/4)!(n/4)!} \cdots \frac{4!}{2!2!} \frac{2!}{1!1!} = \\
\binom{n}{n/2} \binom{n/2}{n/4} \cdots \binom{4}{2} \binom{2}{1} \leq 2^n 2^{n/2} \cdots 2^4 2^2 = 2^{n+n/2+\cdots+2+1} <2^{2n} = 4^n.
$$
Using Stirling's approximation we can get more refined asymptotics, but we leave this to the interested reader.


Min-Max number of shifts and reductions in bottom-up parser

The number of shifts is always precisely the number of symbols in the input stream, since every symbol is shifted exactly once. The number of reductions depends on the grammar; it is impossible to answer that question without knowing something about the grammar.

For example, if the grammar were in Chomsky Normal Form, you could easily count the number of reductions because for CNF grammars, the concrete syntax tree must be a complete binary tree and each node in the tree corresponds to a single reduction.


I have both good news, and bad news.  Not only is there a way to do it; there are many candidate ways to do it.  For instance, you could use IRV, Condorcet voting, Borda count, or many other schemes.  See https://en.wikipedia.org/wiki/Ranked_voting and https://en.wikipedia.org/wiki/Social_choice_theory.

Unfortunately, there are also negative results showing that no scheme provides all of the properties that we might desire.   See Arrow's theorem: https://en.wikipedia.org/wiki/Arrow%27s_impossibility_theorem and https://en.wikipedia.org/wiki/Condorcet_paradox.


Approximation algorithm to visit all nodes in an undirected, weighted, complete graph, with shortest sum of edge weights

Suppose $G$ is a weighted graph, and $T_{OPT}$ is the optimal route you seek.

For clarity: $T_{OPT}$ is a path that connects all vertices, such that for any other path $P$ that connects all vertices, it holds that $w(T_{OPT}) \leq w(P)$.

Denote $M$ for the MST of $G$. Since $T_{OPT}$ is a subgraph of $G$ that connects all its vertices, we can say:

$w(M) \leq w(T_{OPT})$ - by definition of MST.

Denote $M^*$ An euler tour of $M$. Since $M^*$ visits each edge of $M$ exactly twice, it holds that:

$w(M^*) = 2w(M)$
$M^*$ is some path that visits all vertices of $G$, hence a path that solves your problem (although we cannot say $w(M^*) = w(T_{OPT})$)

Following from 1. 2. and 3. we get:

$$w(M) \leq w(T_{OPT})$$
$$2w(M) \leq 2w(T_{OPT})$$
And, since $w(M^*) = 2w(M)$
$$w(M^*) \leq 2w(T_{OPT})$$


Is there an undecidable decision problem that computable algorithm for it leads to an algorithm for halting problem?

Let me rephrase your question. Suppose $O$ is undecidable; can Turing machines with an $O$-oracle solve the halting problem? There are some undecidable $O$ for which this is false. Constructing such $O$ is known as Post's problem, solved using the priority method; Wikipedia has some details.


Data structure used to implement recursion

Let me restate your question: Which data structure does the CPU use to implement recursion? This data structure is knows as the call stack. As you can imagine, it's a stack. I strongly suggest that you consult the Wikipedia page (or any other source) and try to understand why a stack is used and how it works. This is much more important than answering a multiple-choice question.


Matching elements of two lists to identify the missing ones

The two questions are rather different. If $A$ and $B$ are given as unsorted lists, then one thing you could do is to sort $A$ and $B$ together, putting elements of $A$ before those of $B$ in case of ties, and then do a simple linear scan. This runs in $O(n\log n)$ time, where $n$ is the length of both arrays.

If the arrays are sorted then you can just merge them, in $O(n)$, and continue as before.

If the "arrays" (really sets) are given as bit-vectors, then you can use bitwise operations; details left to you.


Difference between time complexity and computational complexity

Computational complexity is the general subject of using complexity measures to compare programs or algorithms. Time complexity and space complexity are two measures that are commonly used when talking about computational complexity, but there are others.

For example, it's common to look at the number of comparisons performed in a sorting algorithm.


From in-order representation to binary tree

The in-order traversal is not unique. The above trees have the same sequence 1,2,3,4,5. (They are isomorphic, but I assumed you consider ordered binary trees.)


Binary string satisfying several constraints

There are 4 types of intervals:

Intervals containing both $0$ and $1$ (e.g. 00?11?). Such intervals are already satisfied, and we simply ignore them.

Intervals which can't be satisfied: either of length 1 (e.g. 0, ?), or contain only 0's or 1's (e.g. 000, 111). If such an interval exists, report "no solutions".

Intervals which consist only of 0's or only of 1's and have a single ? (e.g. 00?0, 1?). For such intervals, we know what ? must be - so we just set ?, satisfying the interval, and ignore the interval from now on.

Intervals which have more than one ?. We'll talk about them later.

The first phase of the algorithm is to get rid of Types 1, 2, 3. Note that when we satisfy an interval of Type 3, other intervals can change their Type.
while (true) {
    Remove all intervals of Type 1
    Check that there are no intervals of Type 2
    if (there exists an interval of Type 3) {
        Satisfy and remove this interval
    } else {
        break
    }
}

As a result, only intervals of Type 4 remain. Each such interval has two ?. In particular, it covers two consecutive remaining ?'s. Therefore, it suffices to assign to the remaining ?'s values 0, 1, 0, 1, 0, 1, ..., from left to right.

Now, the efficient algorithm for the first phase. We process all intervals in increasing order of their right ends.
We maintain a set of intervals $T_4$ (initially empty) of currently encountered Type 4 intervals, sorted by their left ends.
For each new interval, depending on their type, we do the following:

Type 1: Ignore it

Type 2: Return "no solutions"

Type 4: Add an interval into $T_4$.

Type 3: Satisfy it. Now we look into the rightmost interval $I$ in $T_4$ (i.e. with the largest left end). If it changed its type, remove it from $T_4$ and process it again (i.e. check its type and apply the corresponding action from this list). Otherwise do nothing: since $I$ didn't change its type, other intervals in $T_4$ also won't change their type.
Indeed, let $I'$ be another interval from $T_4$. If $I \subseteq I'$, we are fine (if $I$ has two ?, then $I'$, which contains $I$, also has them). Let $i$ be the position of the fixed ?. If $i > right(I')$, then we are fine. Otherwise, we have $i \le right(I') < right(I)$. But note that there are no ? between $right(I')$ and $right(I)$: otherwise, the currently processed interval wouldn't be Type 3, since it has at least two ?'s. Therefore, $I \cap I'$ has at least two ?'s, and therefore, $I'$ too.

While processing Type 3, we find the rightmost interval $I$ in $T_4$ until $T_4$ is empty or $I$ didn't change its type. Simply put, we remove intervals from $S$ while there are intervals which change their type.


Which word could I use for the Pumping Lemma proof?

If we want to use the usual pumping lemma for regular languages as introduced in most textbooks to prove a given language is not regular, the way to avoid or reduce case distinction in showing a word cannot be pumped
is to

select that word so that its front part is in a very restricted form and at least at long as the pumping length.
combine all cases into very few or only one case conceptually.

Let me take the language in the question as an example.

To show $A_{1} \triangleq\left\{a w c^{l} d^{m}\mid l \in \mathbb{N} \wedge m \in \mathbb{N}^{+} \wedge w \in\{a, b\}^{*} \wedge |\left.w\right|_{a}=l+m\right\}$ is not regular, let us suppose our adversary Adriana claims $A$ is regular with pumping length $p$. In order to beat Adriana, we select word $w=aa^pd^p\in A_1$. Adriana claims that $w=xyz$ for some $x,y,z$ such that $|xy|\le p$, $|y|\ge1$ and for all $n\ge0$, $xy^nz\in A$.

It looks like we have to make a case distinction, because Adriana could decompose the word in many ways. For example, Adriana could have any one of the following decompositions.

$ x=\epsilon, y=a^{j}$ and $  z=a^{p+1-j} d^{p}.$
$ x=a, y=a^{j}$ and $  z=d^{p-j} d^{p}.$
$x=aa^i, y=a^{j}$ and $  z=d^{p-i-j} d^{p}.$
$\cdots$.

We have to prove Adriana is wrong in every possible case. There is no way around that, as Adrianna is free to choose any one of them.

However, a little dose of abstraction and intelligence will enable us to treat all cases simultaneously.

Since $|xy|\le p$ and all $p$ letters at the front of $w$ are $a$'s, $y$ must contain $a$ only. Suppose $y=a^i$ for some $i>0$. Then $xz=xy^0z$ contains less number of $a$'s than $w$ but the same number of $c$ and $d$ as $w$. That means $xz\not=A_1$. We beat Adriana as if she has only one case.

Hopefully this strategy answers your question. Indeed, it should be applicable to almost all similar problems in the course of your study where you want to prove a language is not regular.

Here are a few exercises about the languages you have encountered.

Exercise 1. Prove the language $C \triangleq\left\{a^{m} b^{n} c d^{n} d^{m} \mid n, m \in \mathbb{N} \wedge m \leq 3\right\}$ is not regular "without case distinction".

Exercise 2. Prove the language $B \triangleq\left\{w \in \Sigma^{*} \mid |\left.w\right|_{b} \neq|w|_{c} \right\}$ is not regular "without case distinction".

Exercise 3. Prove the language $A \triangleq\left\{(a b)^{n} c^{n} | n \in \mathbb{N}\right\}$ is not regular using two combined cases.


You try all 26 possibilities, and check which of them results in an English-looking test. In principle you can do the latter statistically, but in this case there are only 26 possibilities, so you might as well just look at all of them manually.


Are all finitely recursive context free languages parseable with a regexp?

We can take it even further: if we put a limit on the size of the HTML/XML, say 1PB, then there is only a finite number of them, so we can trivially parse them in $O(1)$ using a giant look-up table. However, that doesn't seem to tell us much about the complexity of parsing HTML/XML in practice.

The issue at stake here is modeling. A good model abstracts away the salient points of a real world situation in a way that makes the situation amenable to mathematical inquiry. Modeling HTML/XMLs as instances of arbitrarily recursing language forms a better model in practice than your suggestion or my suggestion.


how to prove that a language is regular?

Both mentioned languages are irregular
This can be easily shown for both languages using the pumping lemma
First consider L = {w | w has more as than bs}
Let p be the pumping length then clearly  b^p a^(p+1) is in L and it cannot be pumped
We know that |xy| ≤ p ,and thus x and y will have only bs , then pumping the string for i > 1 , xy^i z will give you a string with bs equal to (for i=2) or more than ( for i >2)  as, since this string cannot be pumped L is irregular
In a similar manner the language with the number of as equal to bs can be shown to be non-regular , consider a^p b^p clearly it has equal number of as and bs , using the same argument as above x and y will have only as and thus pumping the string gives more as than bs and thus this language is also non-regular
Intuitively we know both are irregular since we need to keep count of the number of as and bs to compare them something , and the number of as and bs is not a finite specified number .


How do you determine the number of errors in the Welch-Berlekamp algorithm?

The same procedure actually works to correct any number of errors up to $e$.

The requirement is that the error polynomial $E(x)$ has to be zero at every point $a_i$ where there was an error.  Nothing says it has to be zero at only those points; you can have an $E(x)$ that is zero at other points too, and that's OK, as long as its degree is $e$.

So, if $e$ is an upper bound on the number of errors, there will exist a polynomial $E(x)$ with all the desired properties (i.e., has degree exactly $e$ and is zero at every point where there is an error).  For instance, if there are fewer than $e$ errors, then there exists a polynomial $E(x)$ that's zero at every error, and zero at a few more points to get the number of zeros up to exactly $e$.

Finally, the correctness theorem says that if such a polynomial $E(x)$ exists, then the Berlekamp-Welch algorithm will be able to find it.   So, even if there are fewer than  $e$ errors, the procedure will still work correctly to identify $E(x)$.  Once you have $E(x)$, you can identify $n-e$ positions that are error-free, and then you can decode in a straightforward way.

To document the result of the conversation about the "counterexample" in the question:

That's actually not a valid counterexample.  The flaw was in the calculation of how many errors you should expect Berlekamp-Welch to be able to correct.  The distance is $n-k+1$, so you should expect it to be able to correct up to $(n-k)/2$ errors (as Ran G. points out).  In your counterexample $n=5$ and $k=3$, so $(n-k)/2=1$, so you should only expect this procedure to be able to correct one error, i.e., $e=1$.  So, when you ran the procedure on an example with $e=2$, there's no reason to expect the procedure to work correctly.

So, the counterexample isn't actually a counterexample, and it doesn't contradict my answer above.


Number of submatrices with a particular sum

Here is an O(N3) algorithm (it is valid only for matrices of non-negative values).

Compute prefix sums for each column: B[k][j] = Sum(A[0..k][j]).
For each pair of row indices (p, q):
Apply a two-pointers algorithm for implicit array of values B[q][j]-B[p][j].

Where a two-pointers algorithm advances first pointer while sum of values between pointers is less than desired and advances second one when this sum is greater than desired. When the desired sum is found, advance first pointer (x times) while sum does not change and advance second pointer (y times) while sum does not change (we might need to advance pointers more then once in case of sub-matrix column summing to zero), then add x*y to counter of found sub-matrices and continue.


Assuming the TCS-variant of regex, the problem is indeed NP-complete.

We assume that our regexes contain

letters from $\Sigma$, matching themselves,
$+$, denoting union,
$\cdot$, denoting concatenation,
$*$, denoting Kleene-Star,
$\lambda$, matching the empty string

and nothing else. Length of a regex is defined as the number of characters from $\Sigma$. As in the comic strip, we consider a regex to match a word, if it matches a substring of the word. (Changing any of these assumptions should only influence the complexity of the construction below, but not the general result.)

That it is in NP is straightforward, as explained in the comments (verify a candidate-RE by translating it into an NFA and running that on all words from $A$ and $B$).

In order to show NP-hardness, we reduce Set cover:

  Given a universe $U$ and a collection $C$ of subsets of $U$, is there a set $C' \subseteq C$ of size $\leq k$ so that $\bigcup_{S \in C'} S = U$?

We translate an input for Set cover into one for regex golf as follows:

$\Sigma$ contains one character for each subset in $C$ and one additional character (denoted $x$ in the following).
$A$ contains one word for each element $e$ of $U$. The word consists of exactly the characters representing subsets in $C$ that contain $e$ (in arbitrary order).
$B$ contains the single word $x$.
$k$ is simply carried over.

This reduction is obviously in P and equivalence is also quite simple to see:

If $c_1, \ldots, c_k$ is a solution for the set cover instance, the regex $c_1 + \cdots + c_k$ is a solution to regex golf.
A regex matching the empty subword would match $x$. Thus, any regex solving the golf problem has to contain at least one letter from each of the words in $A$. Hence, if the golf instance is solvable, there is a set of at most $k$ letters from $\Sigma$ so that each word in $A$ is covered by this set of letters. By construction, the corresponding set of subsets from $C$ is a solution to the set cover instance.


Shortest paths among two subsets of nodes

Note: The first version of my problem is to find all $d(s,t)$ for each $s \in S$ and $t \in T$. As @D.W. argues, it is not likely to do this in $O(m \log n)$ time because taking $S, T = V$ requires all pairs shortest paths. For $\min\{d(s,t): s \in S, t \in T\}$, however, the following method of "adding extra nodes" works:

Add an extra node $s_0$ and add edges of weights 0 from $s_0$ to each node in $S$
Add an extra node $t_0$ and add edges of weights 0 from each node in $T$ to $t_0$
Find the shortest path from $s_0$ to $t_0$.


Why does the explanation of auxiliary carry flag differ from the article to article?

The two definitions are exactly the same. Don't forget that in computer science, we often start counting things at zero rather than at one.


Conditional probability in Expectation Maximization (EM)

I think I found the solution.
In general we have:
$$p(\theta,x,j=1) = p(j = 1 | x, \theta) \cdot p(x,\theta) \\
\Leftrightarrow \frac{p(\theta, x, j=1)}{p(x, \theta)} = p(j=1| x,\theta)$$
By using this, we get:
$$p(j = 1 | x, \theta) = \frac{p(\theta, x, j=1)}{p(x,\theta)} = \frac{p(j=1,x|\theta) \cdot p(\theta)}{p(x|\theta) \cdot p(\theta)} = \frac{p(j=1,x | \theta)}{p(x|\theta)}$$


Is this path finding problem in a 01-matrix NP-complete?

Your problem is to determine if there is a Hamiltonian path in a grid graph (an induced subgraph of a rectangular grid). This is NP-complete: see Itai, Papadimitriou and Szwarcfiter, Hamilton Paths in Grid Graphs (SIAM J. Comput., 11(4):676–686, 1982) PDF.


Why is discrete mathematics required for data structures?

A course on data structures will not be about "creating data structures". You can expect to analyse data structures, prove various properties of them, and create your own to solve some highly nontrivial problems.

Every single data structure you intend to build must be rigorously defined. Each method on a data structure must be proven rigorously to be correct. The time and space complexity of each method must be rigorously proven to follow a particular asymptotic bound. This all involves some nontrivial discrete mathematics. You'd also need to have a solid handle on probability when randomized inputs and data structures start being used, which you should expect for a decent course on data structures. If you're still unconvinced, look up Cuckoo Hashing and show that the insert time is, on average, $O(1)$, or take a look at a van Emde Boes tree and just attempt to figure out how the hell it works in the first place. You'll quickly realise that there's far more to it than just writing code to build obvious structures.

However, if you go into this course believing it to be beneath you, I can guarantee that you'll get nothing out of it. I would be very surprised indeed if an Ivy League university is "trying to cram useless info into your head and make more money".


Expressing partial decidability using existential quantification

The predicate $R(x,y,z)$ states that "$M$ accepts the input $x,y$ within $z$ steps". It is computable since we can simulate a given machine on a given input for a bounded number of steps.


Why is there readonly (const) in C++, but not writeonly (sink)?

I can only hypothesize, so maybe this should only be a comment, but it's too long for the comment box.

In general Stroustrup tries extremely hard to avoid adding new keywords to the language, so if he discovered that there was another way to get whatever "expressivity" writeonly might provide he would remove the keyword.

My guess is that he actually couldn't find much use for writeonly.  Stroustrup came from an Operating Systems background, and (according to [1]) a lot of the stuff about const and friend originally derived from analogies to O.S. access rights.  (For const, think read/write/execute permissions on files in Unix, and for friend think of one program granting access permissions to another program.)

The analogy apparently only goes so far though.  The usefulness of a writeonly parameter would seem to be that it allows you to return more than one value (but you can return a pair or a struct in C++, and you can "return" an error code by throwing an exception, and perhaps one return value plus an error code is the common case.)  Declaring a non-parameter variable as writeonly makes no sense, because then you would need to do a cast in order to do anything with the value.  A writeonly function is a constructor, and C++ already has those using a different syntax (that doesn't require a new keyword.)  An append operation for vectors most certainly can not be writeonly, because it must increment the length of the vector (i.e., length = length+1.)

[1] Bjarne Stroustrup, The Design and Evolution of C++, Addison-Wesley, 1994.


Applying a permutation on a sequence with multiplication

The problem is NP-complete. Here is a reduction from 3SAT.

Given an instance of 3SAT with variables $v_1,\ldots,v_n$ and clauses $c_1,\ldots, c_m$, construct numbers as follows. We represent a number as the form $\lambda_1p^{\mu_1}+\lambda_2p^{\mu_2}+\cdots$ where $p$ is a very large number (we will estimate $p$ later) so that we can assume there is no carry when performing addition of numbers.

Construct $2n-1$ numbers $u_1,\ldots,u_{2n-1}$: $p^0, p^1, \ldots, p^{2n-2}$.
For each variable $v_i$, if $v_i$ shows up in clauses $c_{j_1},c_{j_2},\ldots$ and $\bar{v}_i$ shows up in $c_{k_1},c_{k_2},\ldots$, construct two numbers $y_i=p^{2n-2+i}+mp^{3n-2+j_1}+mp^{3n-2+j_2}+\cdots$ and $\bar{y}_i=p^{2n-2+i}+mp^{3n-2+k_1}+mp^{3n-2+k_2}+\cdots$.
For each clause $c_j$, construct numbers $z_j=p^{3n-2+j}$.
Add $0$s to make there are $(13n+1)m$ numbers in total.
The target
$$
\begin{align}
x=\;&(n+1)p^0+(n+2)p^1+\cdots+(3n-1)p^{2n-2}\\
&+4np^{2n-1}+4np^{2n}+\cdots+4np^{3n-2}\\
&+16nmp^{3n-1}+(16nm+1)p^{3n}+\cdots+(16nm+m-1)p^{3n-2+m}.
\end{align}
$$

Since there are $(13n+1)m$ numbers and the coefficient of $p^{\mu}$ is at most $m$, we can choose $p=(13n+1)m^2+1$. The construction is in polynomial time.

Now we can see in a valid permutation, the first $2n-1$ numbers must occupy the positions from $n+1$ to $3n-1$, and the next $2n$ numbers $y_1,\bar{y}_1,\ldots$ must occupy the positions $1,\ldots, n$ (say low positions) and $3n,\ldots, 4n-1$ (say high positions), where for each $i$, one of $y_i,\bar{y}_i$ occupies a low position and the other occupies a high position.

Suppose the instance of 3SAT is satisfiable. If $v_i$ is assigned $1$, we arrange $y_i$ at a high position and $\bar{y}_i$ at a low position; otherwise we arrange $y_i$ at a low position and $\bar{y}_i$ at a high position. Now the numbers constructed in steps 1 and 2 are arranged. Consider $\sum\alpha_i\pi_i=\cdots+\lambda_1p^{3n-2+1}+\cdots+\lambda_m p^{3n-2+m}$ for these numbers. We can arrange $z_j$ at position $16nm+j-\lambda_j$ to satisfy the sum goal. Note at least one literal in a clause must be assigned $1$, i.e. its corresponding number ($y_i$ or $\bar{y}_i$) must be at a high position, hence we have

$$m\cdot 3n < \lambda_j\le m\cdot (4n-1+4n-2+4n-3)<12nm,$$

i.e. $4nm+j<16nm+j-\lambda_j<13nm+j\le (13n+1)m$, thus the positions for $z_j$'s are valid. Also note $\lambda_j$ is a multiple of $m$, then $16nm+j-\lambda_j \equiv j \pmod m$, which means these positions do not conflict with each other. As a result, we have arranged these numbers such that $\sum\alpha_i\pi_i=x$.

On the other hand, if there is a permutation satisfying $\sum\alpha_i\pi_i=x$, then for each $i$, if $y_i$ is arranged at a high position, we assign $v_i=1$; otherwise we assign $v_i=0$. Consider $\sum\alpha_i\pi_i=\cdots+\lambda_1p^{3n-2+1}+\cdots+\lambda_m p^{3n-2+m}$ for numbers constructed in steps 1 and 2, then the position of $z_j$ must be $16nm+j-\lambda_j$, which is a valid position, meaning $16nm+j-\lambda_j\le (13n+1)m$, i.e. $\lambda_j>(3n-1)m$. This means at least one number ($y_i$ or $\bar{y}_i$) related to clause $c_j$ is arranged a high position, which means the clause is satisfied.

For example, consider an instance with two clauses $\bar{v}_1\vee v_2\vee v_3$ and $v_1\vee \bar{v}_2\vee v_3$, the numbers are:

           p^0  p^1  p^2  p^3  p^4  p^5  p^6  p^7  p^8  p^9
                                    v_1  v_2  v_3  c_1  c_2
u_1        1
u_2             1
u_3                  1
u_4                       1
u_5                            1
y_1                                 1                   2
\bar{y}_1                           1              2
y_2                                      1         2
\bar{y}_2                                1              2
y_3                                           1    2    2
\bar{y}_3                                     1
z_1                                                1
z_2                                                     1
0
0
...
-----------------------------------------------------------
x          4    5    6    7    8    12   12   12   96   97

There are $80$ numbers in total. (One of) the permutation(s) corresponding to the solution $v_1=v_2=v_3=1$ is $\bar{y}_1\bar{y}_2\bar{y}_3u_1u_2u_3u_4u_5y_1y_2y_30\cdots 0z_1z_20\cdots$ where $z_1$ is at position $73$ and $z_2$ is at position $74$.

If the numbers are upper-bounded by a constant, say $100$, then the problem can be solved in polynomial time.

Let $f(\alpha, x)$ denote whether such permutation exists. Note for any permutation $\pi$, suppose $\alpha_k$ is placed at the first position (i.e. $\pi_k=1$), we have
$$\sum \alpha_i\pi_i=\alpha_k+\sum_{i\neq k}\alpha_i\pi_i=\sum \alpha_i+\sum_{i\neq k}\alpha_i(\pi_i-1),$$
which means the primary problem has a valid solution iff there exists $k$ such that the subproblem for sequence $\alpha-\alpha_k$ (meaning the sequence $\alpha_1,\ldots,\alpha_{k-1},\alpha_{k+1},\ldots$) and target $x-\sum \alpha_i$ has a valid solution, so we have

$$f(\alpha,x)=\bigvee_{i=1}^n f\left(\alpha-\alpha_i,x-\sum_{j=1}^n \alpha_j\right).$$

Note we do not care the order of the sequence, so every subsequence of $\alpha$ can be expressed as "$n_1$ $1$s, ..., $n_{100}$ $100$s", which means there are up to $n^{100}$ different subsequences of $\alpha$. Therefore, we can compute $f(\alpha,x)$ using the recursion formula above in $O(n\cdot xn^{100})=O(n^{103})$ time.


Should we not reuse constants in tableaux proofs?

On the contrary, you never want to reuse constants. Each time you witness an existential quantifier, you should use a different constant. For example, consider the following two sentences:

Some integer is even.
Some integer is odd.

You wouldn't want to instantiate them with the same variable.


KNN is a memory intensive algorithm and it is already classified as instance-based or memory-based algorithm. The reason behind this is KNN is a lazy classifier which memorizes all the training set O(n) without learning time (running time is constant O(1)).

Inversely, When it comes to querying new points to find the nearest K, the query time will be  expensive O(n) in terms of the running time.


What is the best way to index lookups on a 2D array of integers that is boundless in x and y?

Hash map / Hash table (depending on the language used)

Per comments, Some reasoning why:
According to Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, the big O of hash tables is O(1) to O(N) for insert, size, and time.

So best case is O(1) solution. If you are able to control the upper and lower bounds, then you have a 'max' number that you could add and can create a table with that in mind.

If you have a 2 by 2, then you can have a table with 4 rows, where the index is the grid coordinate and the value is then the place in memory. Again, language dependent ( this may be hard to do in JS, where C would be easy)


Calculating traversal position of a node in a full binary tree, given its path

Essentially the algorithm is:

Each time you go left, you add one.
Each time you go right, you add the size of the left sub-tree, and you add one.

The size of a full binary tree can be calculated as $2^{h+1}-1$. Thus, the height of the left sub-tree can be calculated by $2^{h_{\text {subtree}}+1}-1=2^{h-l+1}-1$ where $l$ is the level of the left sub-tree.

#WARNING: non tested, python-ish

def calc_tree_size(tree_height):
  return (1<<(tree_height+1)) - 1

def inorder_traversal_position(tree_height,path):

  result = 0

  for level in range(len(path)):
    if path[level] == 0:
      #If we go left,

      #Preorder goes left after visiting a node.
      #Add one for the node we just visited.
      result += 1
    elif path[level] == 1:
      #If we go right,

      #Preorder normally goes left, visiting all the nodes
      # in the left sub-tree before going right.
      #Add the number of nodes in the left sub-tree.

      left_subtree_level = level + 1
      left_subtree_height = tree_height - left_subtree_level
      left_subtree_size = calc_tree_size(left_subtree_height)

      result += left_subtree_size

      #Add one for the node we just visited.
      result += 1

    return result


The subformula $s(y) = \exists z V(x,y,z)$ is a Boolean function which depends on $x$ and $y$. In this context we can assume that $x$ is fixed, so we only show the dependence on $s(y)$. Here $\exists z V(x,y,z)$ is the definition of the function: the value of $s$ on an input $y$ equals the truth value of the formula $\exists z V(x,y,z)$ (recall we're assuming that $x$ is fixed).

Since $V$ runs in polynomial time, as in Cook's theorem we can encode $V(x,y,z)$ is a polynomial size formula in the variables $x,y,z$. Given the fixed input $x$ and an input $y$, we can substitute $x$ and $y$ in the formula for $V(x,y,z)$ to get a formula $\varphi_{x,y}$ depending only on $z$. We can also convert this formula to CNF. The new formula is satisfiable, i.e. $s(y)$ is true, iff $\varphi_{x,y} \in SAT$.

If we have a circuit $C$ solving SAT we can use it to check whether $\varphi_{x,y}$ is satisfiable. That's what Wikipedia means when it writes $C(s(y))$: write $s(y)$ as an instance $\varphi_{x,y}$ of SAT, and then run $C$ on the instance to get the truth value of $s(y)$. Since $C$ solves SAT, $C(s(y)) = s(y)$, that is, on input $\varphi_{x,y}$ the circuit $C$ will output the truth value of $s(y)$.


Why is the class NP-Complete important compared to NP-hard?

There are at least a few reasons that NPC is interesting:

The class NP contains many problems that are interesting (both practically and theoretically), moreover many of these problems turn out to be NP-hard (and hence NP-complete), but many problems outside of NP are almost certainly too hard to be of more than theoretical interest, so NPC provides a (rough) group of problems that are apparently hard, but not so hard that we can't try to do something with them.
In other words, NPC is probably the limit of what we can hope might be polynomial-time solvable, it would seem a stretch to try for PSPACE = P (for example).
The class is NP is structurally interesting. It's the basic example of "do we get any more computational 'speed' from nondeterminism". So we're interested whether P=NP or not, and NPC is (probably) an important component of working that out.
NP-hard (as a class) is really too big and varied to deal with as a single thing, it's everything that can be reduced to from an NP-complete problem, including a huge swathe of stuff outside NP, so from the point of view of trying to develop general results and techniques, there's nothing to grab on to.


Why is it seemingly easier to resume torrent downloads than browser downloads?

The bittorrent protocol was designed to transfer large files out-of-order. It divides files in chunks (pieces in bittorrent terminology), and maintains a map of which participant holds which chunks. One of the elementary commands is for one participant to request a chunk from another participant. If a client crashes or disconnects, it can check which chunks it has already downloaded (the base data includes a cryptographic checksum for each chunk) and request only chunks that it does not already have. I think bittorrent includes a command to request part of a chunk, too, but if worst comes to worst only chunks that have not been fully downloaded need to be re-requested.

The HTTP protocol was designed to transfer mainly small files and to be simple to implement. Its most basic command is to download one file with a minimum of fuss. A simple server may only understand one command, to download a file in full. Hence, if the download is interrupted, there is no choice but to download the whole file again. There is a way for a client to request only part of a file (with the Range: header). Not all servers implement it (because it is not a fundamental feature of HTTP). Web browsers typically don't bother with it (because they are primarily designed to download small files: web pages), but all download managers support it (because they are designed to load large files) and will use it if the server accepts.


How can I efficiently generate the shortest list of arguments for the range() function that will generate a given list of integers?

I'm assuming the input does not have duplicates, e.g. not [1, 2, 2, 5].

No, an efficient (polynomial time) algorithm does not exist to our best knowledge, as per "Covering a set with arithmetic progressions is NP-complete" by Lenwood S.Health.

But we can make a recursive algorithm regardless, it will just be exponential time as our input grows.

Note that the first element not covered by previous ranges must be the start of the next range. Furthermore, you can always cover at least two elements with each range. And even better, the second element you choose to cover with a range also fully determines that range. The stop condition doesn't really matter - you'd just stop when the next element generated wouldn't be in the set.

With this information you can write a recursive algorithm (which assumes l is given sorted):

def cover_ap(l):
    if not l: return []
    if len(l) == 1: return [(l[0], l[0])]

    candidates = []
    a = l[0]
    for b in l[1:]:
        ap = [a, b]
        step = b - a
        k = b + step
        while step > 0 and k in l:
            ap.append(k)
            k += step
        stop = ap[-1] + 1

        remain = sorted(set(l) - set(ap))
        candidates.append([(a, stop, step)] + cover_ap(remain))

    return min(candidates, key=len)


does not yet seem to be a duplicate on this very site:
cycle detection, see also where hares catch up with turtles
(would-be comment: the question first states repetition every N iterations, next every N bytes.)
(If it didn't carry over: for each PRNG to check, have a clone. For each change in state of the original one, trigger two in the clone. If the states get identical, you detected a cycle. No deterministic PRNG with limited state can avoid it. The states need not be as small as the results; they rarely are, nowadays, and the cycle lengths are huge.)


What order of growth does a ratio of Bigh-Ohs have?


Confused by proof of correctness of Majority

At each step,

if $c == 0$, set $c=1$.
Otherwise, if $c>0$, either increment $c$ or decrement $c$.

Since $c$ is 0 initially, it is always true that $c\ge0$. That means, $-c\le0$ all the time.

Suppose, at some moment, $c'$ is positive. The definition of $c'$ says $c'=c$ when $a^*=v$ and $c'=-c$ otherwise. Since $-c\le0$, $c'\not=-c$. So, the situation cannot be "otherwise". The situation must be other than "otherwise", i.e, $a^*=v$ and, hence, $c'=c$.
We just proved that for any moment, if $c'$ is positive, then $a^*=v$ and $c=c'$ is also positive.
Now just apply the above conclusion to the very last moment.


BCNF Decomposition: Confusion regarding given answer

For the relation R(A, B, C, D) with the following functional dependencies:

1.A -> B
2.C -> D
3.B -> C

candidate key = A

The correct way to decompose a relation such that it satisfies BCNF property is following.

The FD 2 and 3 are violating the BCNF property(LHS should be key) i.e to convert the relation into BCNF it is needed to be decomposed.

To decompose this find the FD which violates the BCNF property in our case FD 2 and 3 violates.

Seprate out this FD into a different relation i.e our new relation is

R1 = (A,B) with FD A-> B
R2 = (B,C,D) with FD B->C and C->D

Again for the R2 the key is B and FD C->D violates the BCNF property we further split R2 into R12 and R22

R12  = (B,C) with FD B->C
R22  = (C,D) with FD C->D

Now the final obtained relation after decomposition is

R1 = (A,B) with FD A-> B
R12  = (B,C) with FD B->C
R22  = (C,D) with FD C->D

The above relations are the only decomposition of R that satisfies BCNF property.

For more insights refer this http://www.cs.toronto.edu/~faye/343/f07/lectures/wk12/moreBCNF.pdf


Checking for intersection of $d$-dimensional spheres

This is an instance of the smallest enclosing ball problem.

An equivalent statement of your problem is: Given points $x_1,\dots,x_n$, we want to determine whether there exists a point $p$ such that every point $x_i$ is at distance at most $R$ from $p$, i.e., we want to find a sphere of radius $R$ that encloses all of the points $x_1,\dots,x_n$.

So, find the smallest enclosing ball that contains all of $x_1,\dots,x_n$; then check whether the radius of that ball is at most $R$ or not.  The smallest enclosing ball problem is well-studied and you can find references and algorithms in the Wikipedia page I linked to.


Is language equality for linear context-free grammars decidable?

Quoting from Amiram Yehudai, The Decidability of Equivalence for a
Family of Linear Grammars, Information and Control 47, 122-136 (1980), page 1:

  The equivalence problem for various families of languages is of great
  interest in the theory of formal languages. This problem is decidable
  for regular languages (Rabin and Scott, 1959) and undecidable for
  context-free languages (Bar-Hillel et al., 1961). It is also
  undecidable for the family of linear context-free languages, as
  follows from Lemma 1 in (Baker and Book, 1974). The family of uniform
  linear languages is a natural and nontrivial subfamily of the linear
  languages for which equivalence is decidable.

This refers to Baker, B. S. and Book, R. V. (1974), Reversal-bounded multipushdown machines, J. Comput. System Sci. 8, 315-332, which, in the proof of that Lemma 1, presents a subset of linear context-free languages such that deciding whether a member of the set is equal to $\Sigma^*$ is equivalent to deciding the Post Correspondence Problem.


What is meant by NFA size is linear in the number of characters in the patternset is that there exists constants $A,B$ such that every pattern of length $n$ is accepted by some NFA of size at most $An+B$. This is proved by structural induction on the patternset, and is a rather straightforward exercise.

Without knowing the constants $A,B$, you can't predict what the general claim gives you for any particular pattern. If you work out the proof, you will get values for $A,B$, and then you will be able to obtain a bound on the NFA size for your sample pattern; that bound probably would be worse than $4$. DFA size could be much bigger. For example, for an alphabet of size $n$, the set of all words not containing all characters has a description of size $O(n^2)$, but has DFA size $2^n$ (NFA size is $n$ or $n+1$, depending on the definition).


Complexity of minimizing the maximum inter-cluster distance?

Because you are working in one dimension, there's a polynomial-time algorithm, using dynamic programming.  Assume $x_1,\dots,x_n$ are sorted in increasing order.  Notice that each cluster must contain a contiguous sequence of $x$'s, say $x_i,x_{i+1},\dots,x_j$.  Let $f(n_0,k_0)$ denote the minimum of the maximum inter cluster distance for dividing the points $x_1,\dots,x_{n_0}$ into $k_0$ clusters.  Then you can express $f(n_0,k_0)$ in terms of $f(m,k_0-1)$ for $m<n_0$:

$$f(n_0,k_0) = \min_m \max(f(m,k_0-1), \text{variance}(x_{m+1},x_{m+2},\dots,x_{n_0})),$$

where $m$ ranges over $m=1,2,\dots,n_0-1$.

Consequently, you can evaluate $f(\cdot,\cdot)$ at all $O(nk)$ inputs in $O(n^2k)$ time.  You can improve this to $O(nk)$ time by setting $g(n_0,k_0)=\min(f(1,k_0),\dots,f(n_0,k_0))$ and noting

$$\begin{align*}
f(n_0,k_0) &= \max(g(m,k_0-1), \text{variance}(x_{m+1},x_{m+2},\dots,x_{n_0}))\\
g(n_0,k_0) &= \min(g(n_0,k_0-1), f(n_0,k_0)).
\end{align*}$$

You will need to use the fact that you can compute the mean and variance of $x_{m+1},\dots,x_{n_0}$ from the mean and variance of $x_1,\dots,x_m$ and the mean and variance of $x_1,\dots,x_{n_0}$.  You can compute the mean and variance of $x_1,\dots,x_{n_0}$ for all $n_0$ in $O(n)$ time by maintaining a running sum and running sum of squares.


Closure under intersection of context free binary trees

If I correctly read your question there are two types of terminal symbols, disjoint sets for internal labels and leaf labels. In that way the structure of the tree is uniquely determined by the string.

Then your formalism is known as regular tree grammars. A production $A \to a BC$ seems to label a tree node by $a$ while attaching children $B$ and $C$. This formalism is closed under intersection. This can be proved precisely as for finite state automata or right-linear grammars. Simulate the two in parallel, as a product construction. With productions $A \to_1 a BC$ and $P\to_2 a QR$ we join them to $(A,P) \to a (B,Q)(C,R)$ and $A \to_1 a$ and $P\to_2 a$ are joined to $(A,P)\to a$.


Using Loop Dependence analysis for vectorization

I found a few resources which helped me to understand the more complex algorithms for use of loop dependence analysis.

The basic way in which the result from Loop Dependence Analysis is utilized is through various tests such as

Dependence Test of various types such as GCD Test, Conservative Test etc. help in determining if the dependency exists and they can further be utilized to test if the
Loop Transformation is safe or not.

Following are a few references which helped:

1) http://www.cs.cmu.edu/afs/cs/academic/class/15745-s09/www/lectures/lect6-deps.pdf

2) http://www.cs.utsa.edu/~qingyi/cs6363/slides/Ch02Dependence.pdf

3) http://www.cs.arizona.edu/~collberg/Teaching/553/2011/Handouts/Handout-33.pdf


Is there a formal name for this graph operation?

Your attempt is like subdivision. Actually you used two subdivision and finally you add extra edge between center of subdivision nodes.


Deterministic and randomized communication complexity of set equality

For the first point, try a counting argument. How many different messages $m(a)$ can $B$ receive, if $|m(a)|<n$? How many different strings can $A$ have?

For the second point, try first analyzing the trivial randomized protocol (randomly fixing $\log(n)$ positions of the string and sending these bits of $a$). Clearly, this protocol always accepts if $a=b$. Assume $a\neq b$, what is the probability that $\log(n)$ randomly picked bits are the same? Does that suffice?


Push two symbols to stack at once in a push down automata

There are some options (from comments):

By some definition of PDA, you can push a string $w \in \Gamma^\ast$, where $\Gamma$ is the stack alphabet. (from abc's comment)
Even if you could push only one symbol per transition, you could modify your PDA to push the first -> move to a new state -> push the second -> continue as usual. (from chi's comment)
The third option is to use multiple stack symbols encoding different things. (from Raphael's comment)


Can we find k shortest paths between all pairs faster than solving the pairwise problem repeatedly?

First of all, a crucial difference in computing $k$-shortest paths is if the paths need to be simple or not. A path is called simple, if it does not contain nodes repeatedly. A path with a loop, for example, is not simple. Note that on the Wikipedia page you linked, the articles are concerned with not necessarily simple paths. The case of simple paths seems to be harder than the case with not necessarily simple paths.

The all-pairs $k$-shortest simple paths problem

This seems to be a quite young area of research. A recent paper by Agarwal and Ramachandran can be found on the ArXiv [1]. The previous-work section will also give you some insight into the history of the problem.

The all-pairs $k$-shortest paths problem

Here, indeed, it is the best choice to just repeatedly apply Eppsteins algorithm [2]. The general observation that a repeated application of an algorithm for the single-source version of the problem is the fastest approach was already made in 1977 by E. L. Lawler [3]; Eppstein provides the fastest algorithm to date for this subproblem.

References

[1] Agarwal, U. and Ramachandran, V. Finding $k$ Simple Shortest Paths and Cycles. arXiv:1512.02157 [cs.DS] https://arxiv.org/pdf/1512.02157.pdf

[2] Eppstein, D. Finding the k shortest paths. SIAM Journal on Computing 28, 2 (1999), 652–673.

[3] Lawler, E. L. Comment on a computing the k shortest paths in a graph. Communications of the ACM, 20(8):603–605, 1977.


Can a Turing machine have infinite states?

No.  The definition of Turing machines requires that the finite-state control unit have a finite number of states.  It's not allowed to have an infinite number of states.

A machine that could have infinitely many states in its control could accept any language (unlike a Turing machine).  However such a machine could not be implemented in practice.  For these two reasons, it would not be a good model of the computational power of real computers.

In addition, once you allow an infinite-state automaton, there's no need to have any tape -- the tape doesn't add any computational power, because an infinite-state automaton can already do "everything".  For these reasons, while it would be possible to construct machines that look like Turing machines but have infinite state, there would be little point: their power would be equivalent to an infinite-state automaton on their own, i.e., every language can be accepted by such a machine.


You have described an optimization problem, namely, find the arrangement that minimizes the average deviation from the mean. The decision version of this problem is, given an input to your problem and a value $T$, whether there exists an arrangement whose average deviation is at most $T$. This problem is in NP.

Whether it is NP-hard or not is for you to ponder. Combinatorial problems in NP tend to be either NP-hard or in P, so you should simultaneously try to prove that your problem is NP-hard via reduction from a known NP-hard problem, or to find an efficient algorithm for your problem.


If $L$ is CFL and $\overline{L}$ is CFL, then is L regular?

As Shaull noted in the comments, $\{a^n b^n\}$ works. The language is trivially context-free but not regular, so I'll show the complement is context-free. A word which is not of the form $a^n b^n$ is either $a^n b^m$ where $n\neq m$, or not of the form $a^n b^m$ at all. So

$(a+b)^{\ast}-{a^n b^n}=\{a^i b^j: i \neq j\} \cup ((a+b)^{\ast}-a^{\ast} b^{\ast})$

which is a sum of context-free language $\{a^i b^j: i \neq j\}$ and the complement of $a^{\ast} b^{\ast}$ which is a regular language.

Another way to see it is that $\{a^n b^n\}$ is a deterministic context-free language, which is a class closed under complement. In other words any nonregular DCFL is a counterexample to the question.

I'll leave the following question to the reader:

  Suppose $L$ and $\overline L$ are CFLs, is $L$ a DCFL?


Finding a target vector through applications of a binary operator

Here is a simple solution that I suspect will be fast enough.  Use breadth-first search on a graph where the vertex set is $X^3$.  In other words, each possible vector $w \in X^3$ is a vertex.  The vertex $w$ has 6 edges out of it going to $w \oplus v_1$, $w \oplus v_2$, $w \oplus v_3$, $v_1 \oplus w$, $v_2 \oplus w$, $v_3 \oplus w$.  Now use BFS to find the shortest path from $v_1$ or $v_2$ or $v_3$ to $t$.  This can be done by initially marking $v_1,v_2,v_3$ as visited and having distance 0, initializing the queue to contain $v_1,v_2,v_3$, and then running BFS until you reach the goal vertex $t$.

Why does this work?  Define $d(v,w)$ to be the distance from $v$ to $w$, i.e., the length of the shortest path from $v$ to $w$ in this graph.  Define $d(w) = \min(d(v_1,w),d(v_2,w),d(v_3,w))$.  Note that any path of length $d$ corresponds to an expression that uses $d$ applications of the $\oplus$ operator, and vice versa.  Therefore, $d(t)$ -- the distance to the goal vertex $t$ -- represents the minimum number of applications needed to reach $t$, and the corresponding path yields an expression that evaluates to $t$ using the minimal number of applications of $\oplus$.

How efficient is this?  BFS run in time linear in the number of vertices plus the number of edges.  Here we have $2^{24}$ vertices and $6 \times 2^{24}$ vertices.  Therefore, in the worst case we perform something like $c \times 6 \times 2^{24}$ basic operations, where $c$ is a small constant.  The performance in practice might be better than that, as there might not be any need to visit all possible vertices.  The memory requirements are relatively limited.  You can store the set of visited vertices in a 2MB bitmap; thus, checking whether a vertex has been visited before can be done by a single random-access lookup in this bitmap.  You can store the queue in a single array of maximum size $3 \times 2^{24}$ bytes, i.e., 48MB; this is not very large large, and locality of access will be excellent.  So I expect this algorithm to complete within seconds.

If this is not fast enough, it is probably possible to optimize it further using various techniques.  For example, here is one candidate.  Define $x-v = \{w \in X^3 : v \oplus w = x\}$ and $P(x) = \{v \in X^3 : \exists w \in X^3 . v \oplus w = x\}$.  Define $S_j = \{w \in X^3 : d(w)=j\}$ and $T_k = \{w \in X^3 : d(w,t)=k\}$.  Now you could consider an optimized iterative deepening algorithm, as follows:

For $d=1,2,3,\dots$:

For $k=\lfloor d/2 \rfloor, \lfloor d/2 \rfloor + 1, \lfloor d/2 \rfloor -1,\lfloor d/2 \rfloor +2,\dots,d,1$:

Set $j=d-k$.  For each $v \in S_j$:

If $v \in P(t)$ and $t-v \cap T_k \ne \emptyset$, then choose any $w \in t-v \cap T_k$ and output $v \oplus w$ and halt.

We can compute the $S_j,T_k$'s using the technique above (BFS).  The trick here is to use a clever data structure to store $T_k$.  If we store $T_k$ in an octree or k-d tree, then testing whether $t-v$ has any intersection with $T_k$ is a stabbing query: we are given a $10 \times 10 \times 10$ cube and want to know if there's any point of $T_k$ that falls within the cube.  This lookup can be done efficiently when $T_k$ is stored in an octree or k-d tree or similar data structure (basically in $O(\log |T_k|)$ time or so).

This requires more complex data structures, so I'm not sure that it will be worth it to implement.  It's not clear whether the resulting solution will be faster or slower than simple BFS, but if simple BFS is too slow, this is another approach you could try.

This finds the sequence that evaluates to $t$ and uses the minimal possible number of applications of $\oplus$.  If you just want any sequence (not necessarily minimal), it might be possible to find it faster.  For example, you could use best-first search, where the "goodness" of a vertex is measured by its $L_{\infty}$ distance to $t$.

An aside: your operator $\oplus$ is not associative, but it is "almost so".  In particular, $(u \oplus v) \oplus w$ is in general not equal to $u \oplus (v \oplus w)$ (due to the rounding), but it will be "close".  Ignoring rounding,
$$\begin{align*}(u \oplus v) \oplus w &= 0.81 u + 0.09v + 0.10w\\
u \oplus (v \oplus w) &=0.90 u + 0.09 v + 0.01 w,\end{align*}$$
so (again ignoring rounding) their difference is $0.09 u - 0.09 w$, which is in $[-23,23]^3$.  Rounding might make it a bit larger, but not too much.

It might be possible to use this property to gain some additional speedup -- though I have not identified a specific way yet.


Does exponentiation reduce to multiplication or the other way around?

Both statements are accurate, assuming $\le_p$ refers to polynomial-time Turing reductions (i.e., Cook reductions), and assuming that in the exponentiation problem, the exponent is specified in unary (otherwise you can't exponentiate in polynomial time).  Given an algorithm to multiply in polynomial time, you can use it to exponentiate in polynomial-time via a Turing reduction, since $a^k = a \times a \times \cdots \times a$.  Also, given an algorithm to exponentiate in polynomial time, you can use it to multiply in polynomial time via a Turing reduction, since $ab = [(a+b)^2 - a^2 - b^2]/2$.  That said, since both multiplication and exponentiation can be computed in polynomial time directly, there's really no need for such a fancy reduction: it's immediate from the definitions that any problem in P reduces to any other problem in P.

You might want to refresh your understanding of the definition of the reductions.

Note that we usually apply reductions to languages, i.e., to decision problems.  So, to really understand how to apply the formal theory to your question, you'd first need to re-cast it as a question about a formal language or about a decision problem.  "Multiplication" is not a decision problem.  Re-casting as a decision problem will complicate things a little bit, and change the nature of the reductions (for instance, the reductions I hinted at above might no longer work), but the bottom line will still remain true: since you can reduce any problem in P to any other problem in P, there will be a reduction in both directions.

See also What is the definition of P, NP, NP-complete and NP-hard?, What are common techniques for reducing problems to each other?, What is the difference between an algorithm, a language and a problem?, and NP-completeness: Reduce to or reduce from?


How to change the algorithm implication by changing the invariant?

Well, the new invariant does not hold in the code you posted, so I guess you are asked to change the code accordingly.

  What I firstly supposed is that the summation must be done in reverse order.

That might be a wise choice. You could try something like this:

$$
\begin{array}{l}
sum,i:=0,n;
\\
\{\text{Invariant}\ P: 0\leqslant i \leqslant n\ \wedge sum=\sum_{j=i}^{n-1} b[j]\}
\\
\{T:i\}
\\
do\ i\neq 0 \rightarrow\ sum, i:=sum+b[i-1],i-1;\ od
\\
\{R: sum=\sum_{j=0}^{n-1} b[j]\}
\end{array}
$$

I have not checked that this Hoare triple is valid, but it should be, possibly with some minor changes.


There is no standard definition since it is uncommon to use the details of the definition of Turing machine. In contrast to other definitions in mathematics, Turing machines are complicated objects whose definition is unwieldy to use directly. Instead, we invoke the Church–Turing hypothesis and describe Turing machines by giving algorithms rather than listing tuples. At this point, the exact definition of Turing machine is unimportant.

A similar situation occurs in other cases, of which I will describe two: number systems and forcing.

Number systems, especially the real numbers, have several different constructions. If you look at books containing a construction of the real numbers, you are likely to see different constructions, in some cases vastly different ones (for example, Dedekind cuts versus Cauchy sequences). However, from the point of view of the user, all we care about is that the real numbers we construct satisfy the field axioms as well as being complete and Archimedean (the exact meaning of these terms is unimportant). We almost never get to use the actual underlying definitions.

Forcing is an important proof technique in set theory. Forcing can be defined in several different ways, the most popular being forcing relations and Boolean-valued models. (A less popular one is modal logic.) These methods are all equivalent, but the formal development can be somewhat different. All of these methods lead to the same proofs in set theory, but there is no "official" one. Which one you choose to present in a set theory textbook or course depends on your personal taste.

The exact definition of Turing machine does matter if you're interested in exact resource consumption, say, how many steps does it take to solve a certain problem. Since all reasonable definitions of Turing machines result in the same running times up to constant factors, and since we don't usually care about constant factors per se, the exact definition doesn't matter and yields the same results.

The same situation occurs when proving other theorems in which the Church–Turing hypothesis cannot be used. For example, when proving Cook's theorem that SAT is NP-complete, we really need to refer to the definition of Turing machine; but the construction will work for many different definitions, in much the same way. We pick one definition arbitrarily and stick to it, knowing that using any other variant will result in a slightly different yet still valid proof.