Formal definition of the Dynamic Array - what is the Dynamic Array

I'm not sure what you mean by this:

  I have never seen, in any programming language ever, any specialized Data Structure called Dynamic Array, nor can I find any ADT which is implemented by Dynamic Array.

There are many examples of dynamic arrays in mainstream programming languages:

Python: list
C++: std::vector
Java: ArrayList
Rust: Vec
OCaml (Batteries included): BatDynArray
Javascript: array (when dense)
and many others...

To answer your question about whether or not dynamic arrays are data structures or ADTs: why not both? Clearly, there is a well-known implementation technique known as a "dynamic array" which is characterized by random-access arrays and exponential resizing. So in this sense, there is an agreed upon notion of a "dynamic array data structure". But also, in many of the examples I gave above, the library interface exposes functionality for explicit resizing (e.g. trimming to size). This suggests that dynamic arrays could be considered as an ADT, because the library interface includes details of performance semantics. And presumably, the "dynamic array data structure" is not the only possible implementation of the "dynamic array ADT".


Is there any problem that is R-complete and RE-complete

Wikipedia hints at the definition of RE-complete. A language $A$ is RE-complete if for every r.e. language $L$ there is a computable reduction $f$ such that $x \in L$ iff $f(x) \in A$. There are two features of this definition:

We consider many-one reductions. This allows us to distinguish RE-complete problems from coRE-complete problems.
We allow any computable reduction. This is the strongest canonical class of reductions that still makes sense, since R is a proper subset of RE.

Both of these features are shared by the definition of NP-completeness.

As for R-completeness, I am not aware of any such definition, and I don't expect one. Indeed, the class of reductions allowed has to be smaller than all computable functions, since otherwise the definition trivializes (all nontrivial computable languages would be R-complete). Suppose for definiteness that we consider reductions running in time $t_1(n)$, and let $L$ be some R-complete problem with respect to such many-one reductions. Then $L$ runs in time $t_2(n)$, and so we would get that all languages in $R$ can be computed in time $t_1(n) + t_2(t_1(n))$, which clearly isn't the case. The same kind of argument rules out oracle reductions and space-bounded reductions.


How to denote the space complexity in terms of output

If your algorithm/TM is called $A$ and the input $x$, it is customary to denote the size of the output by using function and string notation, that is $|A(x)|$.


Why is the syntax of some programming languages very much not according to earlier conventions?

Today, most people who learn a programming language know very little mathematical notation and are more familiar with other programming languages, and with symbols that are available on their computer keyboard. Of course, this wasn't the case in the 1950s and 1960s when some of the major programming language families that exist today appeared.

A lot of programming languages use a C-like syntax today because this has become the earlier convention. C established conventions such as braces {…} to delimit code blocks, semicolons ; to delimit instructions, dot . to access an element of a compound structure by name, the equal sign = as the assignment operator, double-equal == as the equality operator and != as inequality, && and || as logical-and and logical-or, square brackets […] for array indices, etc. C also participated in some conventions inherited from mathematics, such as the decimal notation for numbers, infix binary operators with parentheses for precedence, and the function call syntax with parentheses around the argument lists and commas to separate arguments function(argument1, argument2, …).

The conceptors of C, like Wirth, followed some conventions already established in ALGOL. I think (but I'm not sure) that's where brackets for array access comes from.

Syntax choices are of course very strongly influenced by technical reasons: most languages use syntax that programmers will be able to type on their keyboard. To start with, most languages represent their source code as a sequence of lines, each line being itself a sequence of printable characters. This rules out some aspects of mathematical notation such as subscripts, superscripts, superposition (like the fraction notation), etc.

The set of available characters is usually limited to what typical computers of the time allow people to type easily. This self-perpetuates because operating system and keyboard manufacturers keep making these characters easily available. The basic standard set of characters today is ASCII: computer systems that don't support ASCII are extremely rare. Some of the characters in ASCII today weren't commonly available in the 1950s and 1960s, which explains why some languages that trace their roots to this time period don't use all of them.

An example of characters that are used by mathematicians, but weren't commonly available on computers at the time, is the logical operators $\wedge$, $\vee$ and $\neg$. FORTRAN and ALGOL 58 spelled them out AND, OR and NOT. C (following some of its ancestors) used &&, || and !. Mathematicians never used & for conjunction, as far as I know¹: that came from Latin (& started out as a ligature for “et”, which is how the Latin word for ”and“ is spelled). Later versions of ALGOL added ∧ and ∨ as syntax for boolean operators, but since most computers didn't have them, they allowed other spellings, including /\ and \/, which contributed to the imposition of the backslash as a standard character.

Some languages stray further from classical mathematical notations than C. A major example is Lisp, where the syntax for a function call is (function argument1 argument2 …) and there are no infix operators. Lisp made this choice in the interest of uniformity: there is only one syntax for function calls and not many ($2+3$, $2^3$, $2x$, $\sin x$ are some examples of mathematical notations for function calls that don't follow the usual $f(x,y,\ldots)$ syntax). This uniformity has some theoretical advantages (Lisp was heavily inspired from the mathematical work on the lambda calculus), technical advantages (Lisp makes it easy to manipulate code as data objects), and sociological advantages (it makes the language easier to learn: for example you don't need to learn operator precedence).

A (basically the) notable language that baked in more classical mathematical notations is APL. It's still limited by the line syntax, but uses a special character set that includes characters such as $\leftarrow$, $\rightarrow$, $\neq$, $\neg$, $\subset$, $\supset$, etc. The special character set was a strong barrier to adoption because it required special software and made it harder to learn to type programs. The syntax of APL makes it very terse, and is a reasonably good fit for numerical programming, but it isn't particularly readable.

Beyond symbol availability, another reason for programming languages to depart from mathematical notation is the need for new concepts. Most programming languages incorporate syntax for imperative programming, with major concepts that mathematics doesn't have: operations done in sequence, assignment. For sequencing, the most logical character would have been . following the typography of most languages, but that character was also used in mathematics for decimal numbers. ;, which is not used in mathematics, was the next logical candidate. For assignment, some languages tried to introduce $\leftarrow$, but since it wasn't available in typical character sets, it never really took on. The symbol = was a logical candidate for both equality testing (“are these things equal?”) and assignment (“make this equal to that”). C uses = for assignment and == for equality testing. Other languages made different choices. ALGOL used the arguably more fitting := for assignment (more fitting because it's asymmetric, leaving the symmetric symbol = free for the symmetric concept of equality). PL/1 uses = for both and distinguishes the meaning from context, but this requires the language to distinguish between contexts that allow an assignment and contexts that allow a predicate and not to have any context that allows both. Some languages go closer to mathematical notation and use syntax like set x = … or let x = …; I think the designers of B and C considered this too verbose. I think FORTRAN was the heaviest original influence on imposing = for assignment.

¹  Linear logic uses $\&$ but that's not the ordinary conjunction and that came later.


Consensus problem of distributed systems

The FLP theorem [1] says that

  It is impossible for a set of processors in an asynchronous distributed system to agree on a binary value, even if only a single processor is subject to an unannounced crash.

There are several ways to circumvent this impossibility results, by, according to Jennifer Welch; I suggest you to read the linked webpage

changing the system assumptions

Assuming a synchronous system such as in the "Byzantine Generals" problem [2]
Assuming a partial synchronous system in which failure detectors [3] are used

or changing the problem statement

No guarantee for termination (progress) such as Paxos [4]
Randomized protocol [5]
No need to agree on a single value such as in $k$-set agreement problem
No need to agree on exact values in approximate agreement

[1] Impossibility of Distributed Consensus with One Faulty
Process) JACM, 1985.

[2] Reaching Agreement in the Presence of Faults JACM, 1980.

[3] Unreliable Failure Detectors for Reliable Distributed Systems JACM, 1996.

[4] Paxos Made Simple TR. By Lamport

[5] Another Advantage of Free Choice (Extended Abstract): Completely Asynchronous Agreement Protocols PODC, 1983. It has just received the 2015 Edsger W. Dijkstra Prize.


Why is this problem listed as "Dynamic Programming"

How do you choose which partition is best (there could be several partitions if you allow negative numbers or zeroes), and which side of the partition to choose? You have to examine all partitions and both sides of each partition, and then choose the best one. Naively, the complexity of this algorithm is exponential. With dynamic programming you can find the solution in polynomial time – I'll let you figure out how.


The language has star-height 2. Note that the language includes
$R_0=(ba^+ba^+)^*$, but is disjoint from $R_1=(ba^+ba^+)^*ba^+$. Therefore, it suffices to show:

Claim: If $L$ has star-height 1 and $R_0\subseteq L$, then $L\cap R_1\ne\emptyset$.

Suppose $L$ has star-height 1. Then we can write $L=\bigcup_{i=1}^m F_{i,0}^* w_{i,1} F_{i,1}^* \cdots w_{i,n} F_{i,n}^*$ for words $w_{i,j}$ and finite sets $F_{i,j}$.

We have $(ba^kba^k)^k\in R_0\subseteq L$ for every $k$. For $k$ large enough,
there is some $F_{i,j}^*$ that contributes at least three $b$'s. Let us
choose $k$ so large that also $k>|w|$ for any $w\in \bigcup_{i,j} F_{i,j}$.

Let $u$ be the factor with at least three $b$'s contributed by $F_{i,j}^*$. Then $u$ decomposes into factors $u_1,\ldots,u_m$ from $F_{i,j}$. Now we can
clearly pick one or two consecutive $u_\ell$'s that together form a word $f\in a^+ba^+$. We can therefore repeat $f$ and obtain a word in $R_1$.

Update: Tried to be clearer.


When true is returned I can output the cycle by taking the nodes from the stack.

The stack contains the nodes you still have to visit, so they can not be part of the cycle.

There are at least two options to actually obtain data from a DFS.

Create the DFS tree explicitly; this gives you full information.
If you only want one cycle, you can store a pointer to the visited node's parent (the tree edge) instead of labelling it gray.


First, your definition of reducibility needs to include some sort of restriction on the power of $f$: typically, for example, we require the function to be computable.

Without this restriction, any two decision problems (except the trivial problems "always yes" and "always no") are reducible to each other.  Since there are always $y$ and $n$ such that $Q_2(y)=1$ and $Q_2(n)=0$, there is always a function $f$ that reduces $Q_1$ to $Q_2$: just take
\begin{equation*}
  f(x) = \begin{cases}
         \ y &\text{if }Q_1(x)=1\\
         \ n &\text{if }Q_1(x)=0\,.
         \end{cases}
\end{equation*}

So, we typically restrict to computable functions $f$ as reductions.  Your question is, essentially, is a computable reduction always reversible? The answer to this is no and the reduction $f$ above gives a big hint why: that function is not invertible and there's no reason, in general, to expect that even a computable reduction should be invertible.

For example, consider any decidable problem $Q_1$, and let $Q_2$ be the halting problem.  In this case, we can take $y$ to be the description of any Turing machine that halts immediately, and let $n$ be any Turing machine that just moves the head right forever.  Since $Q_1$ is decidable, the reduction $f$ above is computable.  It tells you how to translate questions about $Q_1$ to questions about the halting problem.  It also kind of tells you how to translate questions about whether or not $y$ and $n$ halt into questions about $Q_1$.  But it doesn't help you determine whether any other Turing machine halts – and it can't, because that problem is undecidable.


Is it possible for a graph to have two different minimum spanning tree

It is possible to have different minimum spanning trees for a graph.
Consider a simple example: a cycle graph with all weights equal. Removing any edge from the graph produces a minimum spanning tree for the cycle graph.


What is the formalism to prove statements about uniqueness of functions with certain signatures

I'm sure there is a connection to category theory, but you can actually do it with (what I consider to be ) a simpler tool: parametricity.

They basic idea is that, when a language has the property that polymorphic types do the exact same thing for each type they're instantiated to (i.e. there's no typecase construct), we can prove very powerful properties about the language, in the form of a logical relation.

This prevents exactly the "special case" implementation that you describe in your question. It's also worth mentioning that these implementations are all extensionally equal: they might look different but produce equal results for equal inputs. e.g. you can replace any term $t$ with $(\lambda x \ldotp x) t $ and get an equivalent function.

The statements about functions only from their type are generally called free theorem, named after the paper that introduced the idea: Theorems for Free by Phil Wadler. If you're interested in this area, I highly recommend the paper, since it's a good introduction to the subject.

The idea behind this actually goes much further back than that paper, to John Reynolds work with System F and the "abstraction theorem" but it took a while before the idea became popular.

You can actually generate free theorems at http://free-theorems.nomeata.de/, although it might take a bit of massaging to get useful information from the theorems they give there.

If you're interested in parametricity used to prove things other than free theorems, like type safe, then Amal Ahmed's thesis is the best introduction I've seen. She really does a good job of describing semantic types: the type of a program is actually a property of how it runs and what it produces, and what we call "types" are a syntactic approximation of these more general semantic types.


Is there an asymptotically optimal algorithm for unbounded search?

The basic observation is:

  Lemma. Suppose $a_s$ is a nondecreasing sequence of integers. There exists a strategy which uses $a_s$ queries when the answer is $s$ if and only if
  $$ \sum_{s=1}^\infty 2^{-a_s} \leq 1. $$

In one direction, consider any strategy. For each $s$, let $w_s$ be the sequence of answers to queries made by the strategy. No word in the collection $\{w_s\}$ is a prefix of another, and so the collection forms a prefix code. The lengths $a_s = |w_s|$ therefore satisfy Kraft's inequality, $\sum_{s=1}^\infty 2^{-a_s} \leq 1$.

In the other direction, let us suppose that $\sum_{s=1}^\infty 2^{-a_s} \leq 1$. Decrease the $a_s$ if need be (while keeping them nondecreasing) so that $\sum_{s=1}^\infty 2^{-a_s} = 1$ (this is always possible); we can restore the original values later by asking dummy questions. Since the $a_s$ are nondecreasing, there is an index $S$ such that
$$ \sum_{s=1}^S 2^{-a_s} = \sum_{s=S+1}^\infty 2^{-a_s} = \frac{1}{2}. $$
The first question asked by the strategy is "$s \leq S$?". If the answer is affirmative, recurse on $a_1-1,\ldots,a_S-1$; otherwise, recurse on $a_{S+1}-1,\ldots$. The left recursion is different from the right recursion, since $a_1-1,\ldots,a_S-1$ is finite; but a similar argument works, with a base case of $a_1 = 0$, in which case no more questions need be asked. $\quad \square$

Given the lemma, we have reduced the question to the topic of the paper universal codes of the natural numbers, in which it is shown that no optimal strategy exists (in a certain reasonable sense formalized in the paper).


The class $\mathsf{D^p}$ was originally introduced in the context of studying the facets of the traveling salesman polytope. It contains all languages that can be considered as the intersection of a language in $\sf NP$ and one in $\sf co\text{-}NP$. Formally, $\mathsf{D^p} = \{ L_1 \cap \overline{L_2} \mid L_1,L_2 \in \mathsf{NP} \}$. It first appeared in [1].

[1] Papadimitriou, Christos H., and Mihalis Yannakakis. "The complexity of facets (and some facets of complexity)." Journal of Computer and System Sciences 28.2 (1984): 244-259.


Does every large enough string have repeats?

No, unfortunately not. There are even infinite square-free words if your alphabet has at least three symbols.

This apparently natural border (two-element alphabets have only finitely many square-free words) is observed in many places, for instance:

$\{xyyz \mid x,y,z\in \Sigma^+\}$ is co-finite for $|\Sigma|\leq 2$ but not context-free for $\Sigma>2$.
The class of languages generated by terminal-free patterns can be learned in the limit if $|\Sigma|>3$ but not so if $|\Sigma|=2$ [Reid2004].


The Communication Complexity of Majority, What does Bob send to Alice? Can Bob just wait for Alice's input?

Yes it's perfectly fine for one player to send multiple bits while the other waits. In fact, "the" trivial upper bound on communication complexity is having one party send its input to the other one, who can then compute the output locally (although note that there are some very nice and non-trivial probabilistic algorithms -- e.g. for EQ -- even for one-way communication, where Alice can talk to Bob but not the reverse). A deterministic communication protocol specifies, as a function of the transcript so far, if Alice or Bob should speak next. Additionally it always specifies when the communication has ended.
Ryan Williams' notes, which you linked, deals at first with the simplified setting:

In general, Alice and Bob will speak one bit each, in rounds. Alice will always start the communication, and speak one bit in odd-numbered rounds.  Bob will always speak a bit in even-numbered rounds.

If you only care about communication complexity and not round complexity, you can replace the above with "Alice and Bob will speak at most one bit each, in rounds [...]" to capture the more general case.


The book is counting the number of times each line is executed throughout the entire execution of a call of DFS, rather than the number of times it is executed in each call of the subroutine DFS-VISIT. Perhaps the following simpler example will make this clear:

PROCEDURE A(n)
1  global = 0
2  for i from 1 to n:
3      B(i)
4  return global

PROCEDURE B(i)
1  global = global + 1

In each execution of A, line 1 of B is executed $n$ times, and B itself is executed $n$ times. Nevertheless, the running time is $O(n)$ rather than $O(n^2)$.

Here is another example, in which an array $T[1\ldots n]$ is involved.

PROCEDURE COUNT(n, T[1...n]):
1  count = 0
2  index = 1
3  while index <= n:
4    ADVANCE()
5    count = count + 1
6    index = index + 1
7  return count - 1

PROCEDURE ADVANCE():
1  while index <= n and T[index] == 0:
2    index = index + 1

The procedure COUNT counts the number of 1s in the input array T. Even though ADVANCE could be called up to $n$ times by COUNT and the worst-case running time of ADVANCE is $O(n)$, lines 1–2 of ADVANCE run at most $n$ times, and so the overall running time is $O(n)$ rather than $O(n^2)$.


Digraph without circuits with negative cost

Sum up the value of $a(uv)+\pi(u)-\pi(v)$ over all the edges in some circuit.  What can you say about the result?  What does this imply about whether that circuit was a negative circuit?


machine learning classification with financial instrument/time series data

Consider that:

a "sliding window" approach can be used with any standard regression / classification algorithm. E.g. given the following time series

Time High Low Open Close Volume
  1   H1   L1  O1   C1     V1
  2   H2   L2  O2   C2     V2
  ...
  i   Hi   Li  Oi   Ci     Vi

you can feed the ML algorithm with these examples:

  O0, H1, L1, O1, C1, V1, H2, L2, O2, C2, V2, H3, L3, O3, C3, V3
  O1, H2, L2, O2, C2, V2, H3, L3, O3, C3, V3, H4, V4, O4, C4, V4
  O2, H3, L3, O3, C3, V3, H4, V4, O4, C4, V4, H5, V5, O5, C5, V5
  ...

(the first value is the target)

The size of the window (s) is an important limitation: the algorithm cannot correlate "candles" that lie more than s timesteps apart.

On the other end, with a large s, all examples appear to be sparse and dissimilar in many ways (see Curse of dimensionality).

You may use other features (e.g. averages, multiple timeframes, Japanese candlestick patterns...) but not without a good knowledge of the specific domain.
ML has tools that, in theory, can deal with timeseries. E.g. Recurrent neural networks can take advantage of their internal memory to process arbitrary sequences of inputs and exhibit dynamic temporal behavior. See Which machine learning algorithms can be used for time series forecasts? for references.


First of all, I will assume that by

  Additionally, the state $f_S$ of $f$ is set to a value $f_S' = f_S \pm k$, where $k$ is selected uniformly at random from $$\{0, 1, 2, ..., \lfloor n/2 \rfloor - ((f_S - x) \mod n)\} $$

you actually mean

  Additionally, the state $f_S$ of $f$ is set to a value $f_S' = f_S + k \mod n$, where $k$ is selected uniformly at random from $$\left\{- \left| \left\lfloor \frac{n}{2} \right\rfloor - ((f_S - x) \mod n) \right|, \ldots, -1, 0, 1, 2, \ldots, \left| \left\lfloor \frac{n}{2} \right\rfloor - ((f_S - x) \mod n) \right|\right\} $$

Otherwise, it is not entirely clear that $f_S \in \{ 0, ..., n-1\}$ always holds and how exactly $f_S \pm k$ behaves.

Using this, the problem basically comes down to "missing as much as possible". Observe that the closer we shoot the rabbit, the larger hops he makes; in the extreme case we have $f_S - x = \pm 1 \mod n$. This results in a uniform hop between $ -(\lfloor n/2 \rfloor \pm 1)$ and $ (\lfloor n/2 \rfloor \pm 1)$, which basically completely randomizes the position of the rabbit again. On the other hand, if we miss as badly as possible - by an offset of $f_S - x \mod n = \lfloor n/2 \rfloor$, the rabbit actually does not move at all (!) and the black box actually updates us on this fact. Therefore, we can just turn around and shoot the rabbit.

We are left with finding a procedure for missing increasingly in each shot. I propose a simple "binary search". (I will conveniently omit the rounding.) It proceeds roughly as follows:

Reset and shoot at an arbitrary position until you get from the blackbox the answer $(f_S - x \mod n) \in \{ \frac{1}{4}n, ..., \frac{3}{4}n\}.$ This takes a constant amount of steps in expectation.
Now, we know that the rabbit's past position $f_S$, and that it did not move more than $\frac{1}{4}n$ steps in either direction. This basically halves our search space in the next iteration, since the rabbit has to be at a position $f_S' \in \{ (f_S - \frac{1}{4}n) \mod n, ..., f_S, ..., (f_S + \frac{1}{4}n) \mod n \}$
Recurse: Shoot at position $f_S - n/2 \mod n$. With probability $1/2$, the position $f_S'$ the rabbit jumped onto in step 1&2  lies the range $\{ f_S - \frac{1}{8}n, ..., f_S, ..., f_S + \frac{1}{8}n \}$. In that case we halved the search space once more. With probability $1/2$, the rabbit did not jump in that range, but since we know that $f_S' - x \mod n = f_S' - f_S + n/2 \mod n \in \{ \frac{1}{2}n - \frac{1}{4}n, ..., \frac{1}{2}n + \frac{1}{4}n \}$, we have the same assumptions as in step (2) and therefore lose nothing.

Each step needs $2 = \mathcal{O}(1)$ expected time to succeed and halves the search space, yielding an overall of $\mathcal{O}(\log n)$ expected number of steps.


Knapsack-type problem where the objective function is a ratio

I can't refer you to literature on this subject, but I did come up with a strategy to solve it.

Do the regular dynamic programming approach to solve simply maximizing $\sum v_ix_i$. In that approach you end up with an array $m[i, c]$ which is the maximum value you can reach with cost less than or equal to $c$ using items up to $i$.

Then simply do a $O(C)$ loop to find the best possible $\frac{m[n, c]}c$ for each $c$ where $n$ is the number of items.


What are the simplest examples of programs that we do not know whether they terminate?

A pretty simple example could be a program testing the Collatz conjecture:
$$
f(n) =
\begin{cases}
\text{HALT}, &\text{if $n$ is 1} \\
f(n/2),  & \text{if $n$ is even} \\
f(3n+1), & \text{if $n$ is odd}
\end{cases}
$$
It's known to halt for $n$ up to at least $5 × 2^{60} ≈ 5.764 × 10^{18}$, but in general it's an open problem.


Analyzing programs with multiple for-loops

From your comments, it seems that you are incorrectly calculating the number of loops. And since I do not where to start from for you, I will start from a basic level - please ignore whatever you know or find obvious. I am also going to assume that the semi-colons after each for loop are not present - otherwise in many programming languages, the variable x will be incremented only twice, once after each apparently nested loops.

Counting how many times each loop executes can be written as a discrete summation. For example, a simple for loop from $1$ to $n$, where $1$ operation takes place, can be seen as $\sum\limits_{i = 1}^{n}1 = n$. That is, the loop will execute $n$ times (or the increment statement will be executed $n$ times). Nested loops can be counted as nested summations. When evaluating any summation, consider the iterating variable as the variable, and treat everything else as a constant.

Consider the first set of nested loops. The number of executions/number of times x is incremented can be written as:
$$T_1(n) = \sum\limits_{i = 1}^{n}\sum\limits_{j = i}^{n}\sum\limits_{k = 1}^{in}1$$
Notice the upper and lower limits on each summation, and compare with your loop variables and ranges. We start evaluation from the innermost loop as follows:
$$\begin{align*}
T_1(n) & = \sum\limits_{i = 1}^{n}\sum\limits_{j = i}^{n}\sum\limits_{k = 1}^{in}1 = \sum\limits_{i = 1}^{n}\sum\limits_{j = i}^{n}in \\
&= \sum\limits_{i = 1}^{n}\left(in \sum\limits_{j = i}^{n}1\right)  \ \ \ \ \ \ \text{(considering $j$ as the only variable)} \\
&= \sum\limits_{i = 1}^{n} \left(in(n - i + 1) \right) = \sum\limits_{i = 1}^{n}((n^2 + n)i - ni^2) \\
&= \sum\limits_{i = 1}^{n}\left((n^2 + n)i\right) - \sum\limits_{i = 1}^{n}\left(ni^2\right) \\
&= (n^2 + n)\sum\limits_{i = 1}^{n}i - n\sum\limits_{i = 1}^{n}i^2 \\
&= n(n+1)\cdot \frac{n(n+1)}{2} - n \cdot \frac{n(n+1)(2n+1)}{6} \\
&= \frac{n^2(n+1)(n+2)}{6}
\end{align*}
$$

You can verify that if x is initially 0, this will be its value after the first set of nested loops. For the second set, I will provide the the summation and answer, leaving the actual work up to you.

$$T_2(n) = \sum\limits_{i = 1}^{n-1}\sum\limits_{j = i+1}^{n}\sum\limits_{k = 1}^{j}1 = \frac{n(n-1)(n+1)}{3}$$

As others have pointed out, since the two blocks of nested loops are serial, you can just add the number of times each has executed to get the final count as $T(n) = T_1(n) + T_2(n)$. This will give you the number of times x has been incremented. This simple mechanical process should help you out in most instances of nested loops.


Regular expression for language that does not accept x string (3 letters, |x|=3)

You can create a complete DFA (with all transitions populated) and then just invert the set of start and end states. In your case, using grammar notation, this accepts all strings with the sequence $cab$:

$$\begin{align*}
S & \rightarrow Q_0 \\
Q_0 & \rightarrow a Q_0\,|\,b Q_0\,|\,c Q_1\\
Q_1 & \rightarrow a Q_2\,|\,b Q_0\,|\,c Q_1\\
Q_2 & \rightarrow a Q_0\,|\,b Q_3\,|\,c Q_1\\
Q_3 & \rightarrow a Q_3\,|\,b Q_3\,|\,c Q_3\,|\,\epsilon
\end{align*}$$

So this accepts all strings without the sequence $cab$:

$$\begin{align*}
S & \rightarrow Q_0 \\
Q_0 & \rightarrow a Q_0\,|\,b Q_0\,|\,c Q_1\,|\,\epsilon\\
Q_1 & \rightarrow a Q_2\,|\,b Q_0\,|\,c Q_1\,|\,\epsilon\\
Q_2 & \rightarrow a Q_0\,|\,b Q_3\,|\,c Q_1\,|\,\epsilon\\
Q_3 & \rightarrow a Q_3\,|\,b Q_3\,|\,c Q_3
\end{align*}$$

Now you just have to convert that into a regular expression. Whether or not that's easier is up to you.

You can also directly construct a DFA which accepts $(a|b|c)^*bac(a|b|c)^* \setminus (a|b|c)^*cab(a|b|c)^*$ using Brzozowski's method, but that's a bit tricky to do by hand for this example.


How to show independence and uniform distribution of hash codes from k-wise independent hash functions?

Throughout, we assume that $|D| \geq k$.
Suppose that $H$ satisfies, for all distinct $x_1,\dots,x_k \in D$ and all $y_1,\ldots,y_k \in R$,
$$
\Pr_{h \in H}[h(x_1)=y_1,\ldots,h(x_k)=y_k] = \frac{1}{|R|^k}.
$$
Now let $x \in D$ be arbitrary. Since $|D| \geq k$, we can find $x_2,\ldots,x_k \in D$ such that $x,x_2,\ldots,x_k$ are distinct. For each $y \in R$,
$$
\Pr_{h \in H}[h(x)=y] =
\sum_{y_2,\ldots,y_k \in R} \Pr_{h \in H}[h(x)=y,h(x_2)=y_2,\ldots,h(x_k)=y_k] = \\
\sum_{y_2,\ldots,y_k \in R} \frac{1}{|R|^k} = \frac{|R|^{k-1}}{|R|^k} = \frac{1}{|R|}.
$$
This proves (i). To see (ii), let $x_1,\ldots,x_k \in D$ be distinct. Then for all $y_1,\ldots,y_k$,
$$
\Pr_{h \in H}[h(x_1)=y_1,\ldots,h(x_k)=y_k] = \frac{1}{|R|^k} = \prod_{i=1}^k \frac{1}{|R|} = \prod_{i=1}^k \Pr_{h \in H}[h(x_i) = y_i].
$$
In the other direction, suppose that (i) and (ii) hold. Then for all distinct $x_1,\ldots,x_k \in D$ and $y_1,\ldots,y_k \in R$,
$$
\Pr_{h \in H}[h(x_1)=y_1,\ldots,h(x_k)=y_k] = \prod_{i=1}^k \Pr_{h \in H}[h(x_i) = y_i] = \prod_{i=1}^k \frac{1}{|R|} = \frac{1}{|R|^k} .
$$


The problem that $LL$ variants have with left recursion is inherent to the way $LL$ works: it is a top-down type parser, which means it replaces nonterminals by their productions.

An $LL$-style parser works as follows. It traverses the input from left to right in one go. If we are at some point in the input, then we know that everything to the left of this point is OK. For everything to the right of this point, the parser has constructed an 'approximation' of what it expects to see next. Consider for example this grammar:

  1: $E \to E + E$
  2: $E \to x$

Note that the grammar is not $LL$, but we can still parse inputs in $LL$-style. On input $x+x+x$, an $LL$-style parser may end up at position $x+\bullet x+x$. Let's assume it has decided that the left part, $x+$, is fine, and for the rest of the input it expects to see $x+E$. It will then find out that $x+x+$ is fine, with $E$ remaining. It may then replace this $E$ by a production, in particular production 2 above. With $x$ remaining, the parser will accept the input.

The trick is then to correctly decide the replacing production for a given nonterminal. A grammar is $LL(k)$ if we can do this by just looking at the next $k$ input symbols, and other techniques are known that are more powerful.

Now consider the following grammar:

  1: $A \to A a$
  2: $A \to \varepsilon$

If an $LL$ parser tries to replace $A$ by a production, it has to decide between production 1 and 2.

Let's consider what the proper course of action would be if our parser was omniscient. Every time it replaces the $A$ by production 1, it 'adds' an $a$ to what it expects for the remaining input (the expected remainder goes from $A$ to $Aa$ to $Aaa$...), but the $A$ at the start does not go away. Eventually, it must pick production 2, after which the $A$ disappears and it can never again add $a$s to the expectation.

As there is no chance to match a few more input symbols, the parser must decide at exactly that input position how many times production 1 must be matched. This means it must know exactly how many times in our case the $a$ will appear in the remainder of the input at this moment.

However, $LL(k)$ can see only $k$ symbols ahead. This means that if production 1 must be chosen more than $k$ times, the parser cannot 'see' this and so is doomed to fail. $LL(*)$ is better at parsing than $LL(k)$, because it can see arbitrarily far ahead in the input, but the crucial detail (which is not always mentioned) is that this lookahead is regular.

To imagine what happens, you can view the algorithm as follows: when it has to decide which production to take, it starts up a finite state machine (a DFA, which is equivalent in power to regular expressions) and lets this machine look at the rest of the input. This machine can then report 'use this production'. However, this machine is severely limited in what it can do. Although it is strictly better than looking at only the next $k$ symbols, it cannot for instance 'count', which means that it cannot help in the above situation.

Even if you were to 'hack' in some counting function in this finite automaton, then there are still left-recursive grammars for which you really need more power. For instance, for this grammar:

  $A \to A B$
  $A \to \varepsilon$
  $B \to ( B )$
  $B \to \varepsilon$

you would have to match 'towers' of matching braces, which is something a finite automaton cannot do. Worse still:

  $A \to B C A D E$
  $A \to A'$
  $A' \to A' D E$
  $A' \to \varepsilon$
  $B \to a B a \mid b B b \mid a a \mid bb$
  $C \to c C c \mid d C d \mid c c \mid d d$
  $D \to e D e \mid f D f \mid e e \mid f f$
  $E \to g E g \mid h E h \mid g g \mid h h$

is a totally awful grammar, for which I'm pretty sure no known linear time parsing algorithm works and all known general parsing algorithms take quadratic time. Worse still, any grammar describing this language is necessarily left-recursive. The grammar is still unambiguous however. You need a hand-crafted parser to parse these monsters in linear time.


Graph coloring decision problem NP-complete

A simpler reduction is from MAX-CUT. The idea is to represent each edge as a gadget which is a complete bipartite graph having $N$ vertices on each side. By choosing $N$ large enough, we can force any potential coloring to color all vertices on one side using color 1, and all vertices on the other side using color 2. You can now connect these gadgets in such a way that the maximum number of bichromatic edges is closely related to the maximum cut in the original graph.

I'll let you work out the details.


How can I multiply a binary representation by ten using logic gates?

I assume that the task is to compute $mul(10, a)= 10a$. You don't need to do multiplication. A single binary adder is enough since $$10a = 2^3a + 2a$$
meaning you add one-time left-shifted $a$ to 3-time left-shifted $a$.
For general multiplication $mul(x,y)$ please see this article.


Multi-point evaluations of a polynomial mod p

No, $O(n \lg q)$ running time is not achievable.  It takes $\Omega(q)$ space even just to write out the answer, so any algorithm will necessarily have running time at least $\Omega(q)$.

However, you can find algorithms that are more efficient than the naive solution.  The naive solution for evaluating a polynomial of degree $n$ at $q$ points takes $O(nq)$ time, by using Horner's rule $q$ times.  It turns out there are faster algorithms to do this, namely, in $O(\max(n,q) \log^2 \max(n,q))$ time.  For simplicity of exposition, let me assume $q=n$, so the goal is to evaluate the polynomial $f(x)$ at points $x_1,\dots,x_n$.

We're going to use divide-and-conquer.  Define

$$\begin{align*}
f_0(x) &= f(x) \bmod (x-x_1)(x-x_2)\cdots(x-x_{n/2})\\
f_1(x) &= f(x) \bmod (x-x_{n/2+1})\cdots(x-x_n)
\end{align*}$$

Now we have

$$f(x_i) = \begin{cases}
f_0(x_i) &\text{if }i\le n/2\\
f_1(x_i) &\text{otherwise.}\end{cases}$$

Thus, it suffices to evaluate $f_0(x)$ at the points $x_1,\dots,x_{n/2}$ and evaluate $f_1(x)$ at the points $x_{n/2+1},\dots,x_n$.  We can do this by a recursive invocation of the same procedure.  Since both $f_0(x)$ and $f_1(x)$ have degree at most $n/2$, we're invoking the procedure recursively on two subproblems of size $n/2$.

This requires us compute $f_0(x)$ and $f_1(x)$ from $f(x)$.  This can be done in $O(n \log n)$ time, using FFT-based polynomial division, which works similar to FFT-based polynomial multiplication (see here, here, and these slides).

The running time of this divide-and-conquer algorithm is

$$T(n) = 2 T(n/2) + O(n \log n),$$

which has the solution $T(n) = O(n \log^2 n)$.  Thus, you can evaluate a polynomial of degree $n$ at $n$ arbitrary points in $O(n \log^2 n)$ time.

Since you are working modulo $p$, you want to use a Discrete Fourier Transform designed for mod $p$ arithmetic.

Thanks to Niklas B. for pointing me to http://www.dis.uniroma1.it/~sankowski/lecture4.pdf.


Computing snapshot of Turing machine from previous snapshots in logarithmic space?

What you seem to be asking is what is the complexity of computing each bit in the sequence of snapshots. The complexity depends on the way you encode the snapshots. Here are a few options:

Encode the state of the machine, the position of the head, and the tape. Computing a bit of the tape requires knowing whether the head is currently at that position or at a neighboring position. Since in general a polytime machine has a polysize tape, this requires circuits accessing $\Theta(\log n)$ inputs.
Encode the state of the machine and the tape, where the tape alphabet is enlarged to include another bit, signifying whether the head is at that position or not. Now each tape bit only depends on a constant number of bits. However, determining the next state is (still) very costly, since we need to know the value under the head.
Encode the state of the machine and the tape, where the tape alphabet is enlarged to include the "head bit" as well as the symbol currently under the head. Now each bit indeed depends only on a constant number of bits.

Of course, given any formula, we can always convert it to a 3CNF using auxiliary variables without blowing it up by too much. What I outline above is a particular way of doing this transformation in the case at hand.


Different characterization of $\Delta_2^P$

That set is BH2, and BH is a subset of PNP.    If  BH ⊆ BH2  "then the polynomial hierarchy collapses to" BH3(2), where BH3(2) is the 2nd "level of the Boolean hierarchy over $\Sigma_2^P$."

(So, to answer your question:  No, I can't give such a description.)


Can a graph with more than |V| - 1 edges have the maximum weighted edge as part of its MST?

Consider the following example:

You can clearly see that the heaviest edge (connecting vertices 3 and 4) is in any MST of this graph. In general, the heaviest edge (assuming it is unique) will be part of the MST of a graph if and only if it is a bridge (meaning that if we remove that edge the graph gets disconnected). The condition $|E| \geq |V| - 1$ doesn't really change anything. However, in order for MST to make sense, we need the graph to be connected. Note that $|E| \geq |V| - 1$ does not guarantee that.


Showing that u#v with u a substring of v is not context-free

Okay I got confused when developing my ideas, and a simple example using Pumping Lemma would be: $a^nb^n\#a^nb^n$. Consider this: clearly $v$ and $x$ cannot contain $\#$, otherwise when pumping more or less $\#$ appear and the new string is not in the language. Now suppose $vwx$ are in the left $a^nb^n$, then $v^2$ and $x^2$ will make it longer than the R.H.S.; then if $vwx$ are in the right $a^nb^n$, then $v^0x^0$ will make the R.H.S. shorter than the left. This gives us the only possibility that $v$ in the first $b^n$ and $x$ in the second $a^n$, and clearly no matter how you pump it the new string cannot be in the same language, and this solves the problem.


Yes, there is.  Test whether the 3SAT formula is satisfiable or not.  If it is, convert it to the formula True.  If it is not, convert it to the formula False.  This can be done in exponential time, e.g., by trying all possible assignments, or by your favorite method for testing satisfiability of a 3SAT formula.

Under the strong exponential-time hypothesis, this is optimal: there is nothing faster.

In particular, any procedure for converting into an equisatisfiable 2SAT formula can be used to test satisfiability of 3SAT: first convert into an equisatisfiable 2SAT formula, then test the satisfiability of the corresponding 2SAT formula (can be done in linear time. This gives a method for testing the satisfiability of a 3SAT formula, whose running time is essentially the same as the running time of the conversion procedure.  Now the strong exponential-time hypothesis says that any method for testing satisfiability of 3SAT formulas requires exponential time.  It follows that any method for conversion also requires exponential time.


Find maximal clique consisting of at least half of the vertices

Each time you remove a vertex $v$ with degree $<c−1$, the degree of all its neighbours will be reduced by 1, so if any neighbor $u$ gets a degree $<c−1$ after removing $v$, remove $u$ as well; don't stop on $v$. Once you are done you will get what is called the ($c−1$)-core of the graph, which is the induced subgraph where all of its vertices has a degree $\geq c−1$. The maximum clique will be a subset of such core.
Besides that, $c$ is just a lower bound on the maximum clique size, which doesn't change the fact your problem is NP-hard but over a much tinier graph (if you are minimally lucky).
Also, given the maximal $d$ such as the $d$-core exists (the degeneracy of the graph), $d+1$ is an upper bound to the maximum clique size.
With $c$ and $d+1$ as bounds, your maximal clique will probably be found very efficiently by the algoritm introduced in this paper, where all of the above is explained very well (there are a link to github with the implementation in C++): http://www.optimization-online.org/DB_FILE/2018/07/6710.pdf
If you have remove enough vertices, maybe your $c$, which is at least a 50% in the original graph, becomes even higher after the previous erosion of the graph, so you could start looking for algorithm variants specialized for dense graphs.


Is the language of Turing Machines that halt on every input recognizable?

Preliminary

Let $H$ be the usual halting language:
$$
H=\{(\langle M\rangle, w)\mid M(w) \text{ halts}\}
$$
Its complement is
$$
\overline{H}=\{(\langle M\rangle, w)\mid M(w) \text{ doesn't halt}\}
$$
We know that $H$ is recognizable (just run $M$ on $w$ and do what it does), so $\overline{H}$ must be unrecognizable (otherwise $H$ would be decidable, which we know isn't true).

The Reduction

As you suggested, we'll produce a reduction from $\overline{H}$ to
$$
AH = \{\langle N\rangle\mid N \text{ halts on all }x\}
$$
thus showing that $AH$ is unrecognizable. As you suggested, what we want is to map $(\langle M\rangle, w)$ to a description of a TM $M_w$ where

Mw(x) =
   run M on w
   if M(W) halts
      loop
   if M(w) doesn't halt
      halt

That would do it, except for the fact that if $M$ didn't halt on $w$, we'd never get to the $\texttt{halt}$ instruction. What we need is a finite way of testing for non-halting. A standard way to deal with this kind of difficulty is to limit the number of steps our simulation will perform, like this:

N(x) =
   run M on w for |x| steps
   if M has halted
      loop
   if M(w) hasn't halted yet
      halt

How does this modification help us?

If $(\langle M\rangle, w)\in\overline{H}$, then $M(w)$ will never halt, so $N(x)$ will halt after $|\,x\,|$ steps and thus $\langle N\rangle\in AH$
If $(\langle M\rangle, w)\notin\overline{H}$ then $M(w)$ will eventually halt, say after $s$ steps. This means that $N$ will halt on all inputs, $x$ of length less than $s$, and will loop on all longer inputs, so $\langle N\rangle\notin AH$.

This establishes the reduction we needed, and so we can conclude that $AH$ is non-recognizable.


This is not a proof for the statement (since the statement is incorrect if the tree is not balanced), but rather another way to think and solve the problem.
Notice that in any path from the root to a leaf, say $v_1,\dots, v_k$ we must have that the number of green nodes is at most $1$ (by the first property). Also, notice that the number of blue nodes in the path, is the depth of the leaf $v_k$ minus either one or zero, depending on whether there was a green node in that path.
So, in order to count the number of blue nodes in a path you have to do the following two things:

Write at every leaf its depth (can be done in $O(n)$)
Write at every leaf whether there was a green node in the path from the root to it (think about it, it also can be done in $O(n)$)

Then finally you go through all leaves, calculate the number of blue nodes using this information, and make sure all leaves have the same value of it.


The proofs can be found in the literature. I'll try to explain the intuition.

The short version is that parameterized independend set is typical for both $W[1]$ and $A[1]$.

The general intuition about the $W$- and the $A$-hierarchy is that they are about amounts of nondeterminism. In particular, at the first levels, both hierarchies allow existential nondeterminism with $n^k$ possibilities to choose from, followed by universal nondeterminism with $n$ possibilities, followed by existential nondeterminism with a constant number of possibilities. Let us see that for each of the three problems.

Independend set is the question:

Is there a set of $k$ vertices,
such that for all edges
there is an endpoint not in the set?

The first bullet point is existential ("is there?") with $\binom nk$ possibilities. Up to parameterized reductions there is no difference between $\binom nk$ and $n^k$. The second point is universal ("for all") with as many possibilities as there are edges. Which is bounded by the input size $n$. The last part is existential ("there is") with $2$ possibilities ($2$ endpoints per edge).
In the case of $W[1]$, that is of parameterized weighted $c$-CNF-SAT, the first existential nondeterminism concern the set of variables to set to true, much like the vertex set above. The universal nondeterminism ranges over the clauses, all of which have to be satisfied. Their number is bounded by $n$. The last part is existential, namely finding an atom in the clause that is satisfied. That part has at most $c$ possibilities.
For model checking of $\Sigma_1$, it is not obvious at first that the above nondeterminism suffices. We will have to do some normalization of $\Sigma_1$ formulae. First, let us assume that the quantifier-free part is in DNF. Achieving DNF may bring an exponential blow-up, but as the formula is the parameter, any blow-up is fine. Second, let there be a bound $r$ on the arity of relations (I will not go into the details of how to do that). Last, let all atoms be negative (that can be achieved by adding complements for all relations with an $n^r$ blowup.

Now the quantifiers incur existential nondeterminism with $n$ possibilites each, for a total of $n^k$. The disjunctive part of the DNF brings another existential $n$. The resulting $n^{k+1}$ is as well as $n^k$ under parameterized reductions. Then comes a conjunctive clause for universal nontederminism with $k$ possibilities. Then comes a negated relational atom: For all tuples in the relation ($n$ (universal) possibilities, because the relation is part of the input) there is some position ($r$ existential possibilities) at which the tuple differs from the values chosen for the quantifiers. Again, think of independent set, where $r=2$. The universal part totals to $k\cdot n$, which is as well as $n$ under reductions.


What machine learning algorithm to use and how to implement it?

I would suggest that you try to apply reinforcement learning, maybe deep Q-learning or some other form of RL.

I don't know if those are going to be the best set of features (the best way to represent the input).


Show that the Pumping Lemma for CFLs is not powerful enough to prove that the language L = {aibjck |i ≠j ≠ k ≠ i } is not context free

The Pumping Lemma states: "... there exists a constant $p$ such that for each word $w\in L$ with $|w|\ge p$ there exists a decomposition $w = uvxyz$ such that ...", where $p$ is the pumping constant.

You have chosen your own decomposition, and shown it not fit the pumping property. Perhaps there is another decomposition that will work?

And even in the case your example would work, I can claim that the pumping is larger than 6.


Need clear explanation to Range updates and Range queries in Binary Indexed trees?

Consider an array $A[0, \cdots, n-1]$ and its cumulative sum array $A'$.
Suppose we want to make a range update of $v$ to $A[i, \cdots, j]$. Then $A'$ is changed in the following way:

For $0 \le x < i$: $A'[x]$ does not change;
For $i \le x \le j$: $A'[x]$ is added by $v \ast \left( x-(i-1) \right)$;
For $j < x < n$: $A'[x]$ is added by $v \ast \left( j-(i-1) \right)$.

For your question, why is $v \ast \left( x-(i-1) \right)$?

First, the specification of range update of BIT Range-Update(v,i,j) means adding value $v$ to each element of $A[i, \cdots, j]$.

Secondly, $A'$ stores the cumulative sums of $A$. For $A'[x], i \le x \le j$, its increment consists of the cumulatively added values preceding it, which is, along with $v$ of itself, $v \ast \left( x-(i-1) \right)$. The increment of $A'[x], j < x < n$ is the same as that of $A'[j]$, which is $v \ast \left( j-(i-1) \right)$.

An example from the post you mentioned is as follows (thanks @JS1; the indices starts from 1 for consistency):

Suppose you had an empty array:

0  0  0  0  0  0  0  0  0  0  (array)
0  0  0  0  0  0  0  0  0  0  (cumulative sums)

And you wanted to make a range update of +5 to [4..8]:

0  0  0  5  5  5  5  5  0  0  (array)
0  0  0  5 10 15 20 25 25 25  (desired cumulative sums)


Actually I think I have spotted this property in a book. It uses the "extended" transition relation $\delta^*$, i.e., for strings rather than single letters.

  Other properties you would expect $\delta^*$ to satisfy can be derived from
  our definition. For example, a natural generalization of the recursive
  statement in the definition is the formula
  $$\delta^*(q,xy) = \delta^*(\delta^*(q,x),y))$$
  which is true for every state $q$ and every two strings $x$ and $y$ in $\Sigma^*$.
  The proof is by
  structural induction on $y$ and is similar to the proof [...] in Example 1.27.

  John C. Martin, Introduction to Languages and the Theory of Computation, McGraw-Hill, 4th edition, c2011. Page 54.

I hope you agree with me that this matches the "machine" terminology you use in your question.


Can the complement of a context-free language be regular?

Since regular languages are all context-free and REG is closed against complement, every regular language is such an example.

As for non-regular context-free languages, the same closure property with a sprinkle of proof by contradiction easily shows that none of them can have a regular complement.


Vertex-disjoint cycles passing through a collection of vertices

If $U$=$V$ it reduces to a matching problem by splitting all of the vertices into a left-vertex and a right-vertex to create a corresponding bipartite graph.  All existing edges in the original graph translate to the bipartite graph as low-cost edges directed left-to-right (from the origin's left-vertex to the destination's right-vertex).  For each left/right pair, you add a high cost edge connecting the left to the right.  (Unless it already had an edge due to a loop, in which case the edge remains low cost.)  The minimum cost matching will use as few of those high cost edges as possible.  The resulting matching corresponds to a set of vertex-disjoint cycles with the maximum number of total vertices because for each vertex not in a cycle, the high-cost edge is used.

Now assume $U$ is instead a strict subset of $V$.  For each vertex not in $U$, consider the high cost edge connecting its left-vertex and right-vertex.  Lower the cost of those edges so that the only remaining high-cost edges are the ones connecting left/right vertices in $U$.  (Again, if a vertex in $U$ has a loop, the edge is instead low cost.)  The minimum cost matching will use as few of those high cost edges as possible, thus maximizing the number of vertices in $U$ that are in cycles.


Satisfying assignments, twice-3SAT NP complete

Hints:

Showing that the problem is NP is easy.
To show that it is NP-hard, show first that TWICE-SAT is NP-hard (see next step).
In order to show that TWICE-SAT is NP-hard, reduce from SAT. The idea is to add a "dummy" satisfying assignment, which is always going to be satisfying; any satisfying assignment of the original SAT instance will translate to a (different) satisfying assignment of the new instance.
Either reduce TWICE-SAT to TWICE-3SAT, or use insights from your proof in step 3 to prove that TWICE-3SAT is NP-hard.


What is the most efficient algorithm for creating a list of unique values from a list of pairs of value?

Question 1: How to solve the finding uniques problem
If your data is consistently formatted in this way:
[
  ['somestring', 'someotherstring'],
  ['anotherstring', 'anotherotherstring'],
]

And so on, you can actually just call dict directly on it and it will reduce all of the first items to keys, and keep the last of the second items as the values, and this runs extremely quickly. You can then retrieve the keys from the dictionary to get your unique list.
Here is an example:
a = [
  ['somestring', 'someotherstring'],
  ['anotherstring', 'anotherotherstring'],
]
b = dict(a)
print(list(b.keys()))

I tested this with a data set resembling the one you describe, with 50 million entries and 10 million unique values. On a single core in my laptop it took only about 15 seconds to run and used about 5.5 GB of memory. It actually took 10 times as long to make the data as it did to reduce it to a unique list. I have included the code I used to test below:
import random
import string
import time

def make_data(n, min_len, max_len, repeat_chance=0.0):
    dataset = []
    for i in range(n):
        if random.random() < repeat_chance and len(dataset) > 1:
            dataset.append([random.choice(dataset)[0], ''])
        else:
            key = ''.join(random.choices(string.printable, k=random.randint(min_len, max_len)))
            dataset.append([key, ''])
    return dataset

def main():
    random.seed(42) # For reproducibility
    start_time = time.time()
    x = make_data(50000000, 10, 100, 0.8) # 50 M with 80% repeats for ~10 M unique
    mid_time = time.time()
    y = dict(x) # Reduce to unique keys
    end_time = time.time()

    print('Make data:  {0:.2f} s'.format(mid_time - start_time))
    print('Make dict:  {0:.2f} s'.format(end_time - mid_time))
    print('Total time: {0:.2f} s'.format(end_time - start_time))
    print('Total items:  ', len(x))
    print('Unique items: ', len(y))

if __name__ == '__main__':
    main()

And got the following output which is consistent with the specifications of 50 million entries and 10 million unique values
Make data:  169.61 s
Make dict:  15.47 s
Total time: 185.08 s
Total items:   50000000
Unique items:  10000776

Question 2: What is the complexity of that algorithm?
Is adding p unique values to a list and then searching the list for each new value from a list of n values to determine if its unique a O(np) problem?
Intuitively, I expect this to be a O(np2) problem. As n goes up, we must go through each one only once, so linear in n. As p goes up, we must go through more uniques to tell if the new value coming in is unique, so p2. This wiki page has almost exactly this situation, and shows how to derive the O(n2) complexity. But let's not let intuition guess for us, lets do the work.
Here is a plot of n with constant-ish p of 5000 and the time it takes to process it using your algorithm on the vertical axis.

Here is a plot of p with constant n of 1 million and the time it takes to process on the vertical axis.

These plots suggest that the list algorithm offers the complexity we expected of O(np2).
Bonus Question: How does the dict method compare to the list method?
Just for the intrigue, I also compared the dict method to your list algorithm and plotted them together. Blue is the list algorithm, and orange is the dict method.

Since the orange line is a little difficult to see, here is a rerun with only the dict method.

As you can see, the dict method maintains linear performance with respect to p, offering an overall performance of O(np) while the list algorithm offers the complexity we expected of O(np2). The dict method also outperformed the list algorithm at every test point.
If anyone is so inclined, here is the code used to generate that data.
import random
import string
import time
import matplotlib.pyplot as plot

def make_data(n, min_len, max_len, repeat_chance=0.0):
    dataset = []
    for i in range(n):
        if random.random() < repeat_chance and len(dataset) > 1:
            dataset.append([random.choice(dataset)[0], ''])
        else:
            key = ''.join(random.choices(string.printable, k=random.randint(min_len, max_len)))
            dataset.append([key, ''])
    return dataset

def get_uniques_listwise(dataset):
    uniqueset = []
    for datapoint in dataset:
        if not datapoint[0] in uniqueset:
            uniqueset.append(datapoint[0])
    return uniqueset

def get_uniques_dict(dataset):
    return list(dict(dataset).keys())

def makechart(testpoints, index, xlabel, ylabel, title, f0, f1=None):
    n_times0 = []
    n_times1 = []
    for testpoint in testpoints:
        dataset = make_data(testpoint[0], 10, 100, 1 - testpoint[1] / testpoint[0])
        start_time = time.time()
        f0(dataset)
        end_time = time.time()
        n_times0.append(end_time - start_time)
        if not f1 is None:
            start_time = time.time()
            f1(dataset)
            end_time = time.time()
            n_times1.append(end_time - start_time)

    plot.plot([x[index] for x in testpoints], n_times0)
    if not f1 is None:
        plot.plot([x[index] for x in testpoints], n_times1)
    plot.xlabel(xlabel)
    plot.ylabel(ylabel)
    plot.title(title)
    plot.show()

def main():
    random.seed(42) # For reproducibility
    n_p_testpoints_n = [
        [100000, 5000],
        [500000, 5000],
        [1000000, 5000],
        [2000000, 5000],
        [5000000, 5000],
        [7000000, 5000],
        [8000000, 5000],
        [9000000, 5000],
        [10000000, 5000]
    ]
    makechart(
        n_p_testpoints_n,
        0,
        'n',
        'time to find uniques',
        'varying n with near constant p=5000',
        get_uniques_listwise,
        get_uniques_dict
    )

    random.seed(42) # For reproducibility
    n_p_testpoints_p = [
        [1000000, 10000],
        [1000000, 15000],
        [1000000, 20000],
        [1000000, 25000],
        [1000000, 30000],
        [1000000, 35000],
        [1000000, 40000],
        [1000000, 45000],
        [1000000, 50000],
    ]
    makechart(
        n_p_testpoints_p,
        1,
        'p',
        'time to find uniques',
        'varying p with constant n=1000000',
        get_uniques_listwise,
        get_uniques_dict
    )

if __name__ == '__main__':
    main()


Just two pointers:

If you want to actually combine the ideas of priority queues and binary search trees, think about combining heap and BST in one structure.
There is the concept of self-organising lists. The idea is to move recently accessed element to (or towards the) front in order to speed up future accesses to the same element, thusly "learning" the element distribution over time (with quality depending on the particular implementation). Maybe you can adapt this to trees?

Spoiler: Follow below links only if you have not been able to come up with something yourself.

   1. This is called a treap.
 2. Splay trees implement this idea.


Why is the common explanation to the halting problem an oversimplification?

It's basically correct, but it can be viewed as an oversimplification because that one sentence doesn't explain the details of how to feed it back into itself or why "feeding it back into itself" creates a paradox -- that requires additional explanation or justification.


Given a list of strings, find every pair $(x,y)$ where $x$ is a subsequence of $y$. Possible to do better than $O(n^2)$?

No, it is not possible to do better unless the Strong Exponential Time Hypothesis (SETH) fails. If we could solve this problem substantially faster than $O(n^2)$ we would immediately obtain a much faster algorithm for solving the NP-complete problem Satisfiability. This is true even for $m$ slightly more than $\log(n)$ and the case in which we want to decide whether such a pair $(x,y)$ exists at all.

See, e.g., these lecture notes under section 3 "Tight Lower Bounds for Orthogonal Vectors". The proof is analogous to the proof of Theorem 2 in these lecture notes.

First, we consider the more general problem of given two sets of strings $X,Y$, finding whether some string in $X$ is a subsequence of a string in $Y$.

Given a SAT formula, we split its $n$ variables into two equal sets of $n/2$ variables. In $\Sigma$ we take a character corresponding to every clause. In $X$ we add a string for every possible assignment to the first half of the variables, with a character corresponding to every clause not satisfied by those variables. Meanwhile, in $Y$, we add a string for every assignment to the second half of the variables, with a character for every clause that is satisfied by those variables. Clearly, the formula is satisfiable if and only if some string in $X$ is a subsequence of some string in $Y$.

If this problem can be solved substantially faster than $O(n^2)$, then this gives a substantially faster algorithm for Satisfiability than $2^n$. Suppose the problem could be solved in $O(n^{1.99})$ time, then Satisfiability could be solved in $(2^{n/2})^{1.99}=O(2^{0.996n})$ which contradicts SETH.

In your problem, there is only a single set of strings, all of which may be a subsequence of each other. This is however not a problem, as we can simply modify the strings in our instance such that no string $Y$ is a subsequence of any other string (for instance by padding all strings in $Y$ to have the same length), and similarly padding every string in $X$ to the same length as other strings in $X$ (but substantially shorter than strings in $Y$).

This can probably also be done with a constant-size (likely even binary) alphabet but this requires more clever encoding.


Preorder traversal:

This traversals always yield unique binary trees. (proof for this remains. To me it seems that it is correct due to procedure to construct tree that follows. However it might not be the case.)

For instance consider traversal sequence $6,5,N,N,5,3,N,N,2,N,N$.

We can proceed as follow to construct binary tree.

  First symbol is always root of tree.

Root will always be identified uniquely.

  Try to parse remaining part of input recursively(This will be our left sub-tree). When one sub-tree is parsed  return.

Here this left sub-tree parsing will start with input $5,N,N,5,3,N,N,2,N,N$ and will return after input $5,3,N,N,2,N,N$ left to be processed.

  Try to parse yet remaining part of input recursively(This will be our right sub-tree).

Post-order traversal: This is similar to pre-order.

inorder traversal: This does not always yield unique binary tree. Here is counterexample.

Consider preorder traversal $N,5,N,6,N,3,N,5,N,2,N$. And following two binary trees.

        6                    5
       /  \                /  \
      5    5              6    2
     / \  /  \           / \  / \
    N  N 3    2         5   3 N  N
        / \  / \       / \ / \
       N   N N  N     N  N N  N


What is the purpose of a single input, single output, bidirectional shift register?

a) if during left shift the output signal immediately followed the input, output changes were no longer synchronous. (And the circuit would just act as a "buffer".)
b) when you shift it left, all you're really doing is sending the data input straight to the output no:
it shifts the FFlops' data right to left, capturing Input data in the rightmost one (the one driving Output data, clocking Input data straight to the output ). All but the latest capture become observable again when you switch to shifting right and shift, only.


Change the structure from 3SAT to 1in3 3SAT

A 1-in-3 SAT clause (A,B,C) can be expressed with the following 5 clauses in 3SAT.

$(A ∨ B ∨ C) $

$(A ∨ \overline{B} ∨ \overline{C}) $

$(\overline{A} ∨ B ∨ \overline{C}) $

$(\overline{A} ∨ \overline{B} ∨ C) $

$(\overline{A} ∨ \overline{B} ∨ \overline{C}) $

Why? Consider the truth table over A,B,C.

| A | B | C |   | A | B | C |
| 0 | 0 | 0 |   | --------- |
| 0 | 0 | 1 |   | 0 | 0 | 1 |
| 0 | 1 | 0 |   | 0 | 1 | 0 |
| 0 | 1 | 1 |   | --------- |
| 1 | 0 | 0 |   | 1 | 0 | 0 |
| 1 | 0 | 1 |   | --------- |
| 1 | 1 | 0 |   | --------- |
| 1 | 1 | 1 |   | --------- |

There are 8 lines. Each clause eliminates 1 line. We only want to allow (0,0,1), (0,1,0), (1,0,0) and eliminate the others.


A BST can be broken by accessing one of its nodes, how can I always make sure this happens?

Hint: In a BST, an inorder traversal produces the keys in sorted order. If we had N.key = $20$ and the inorder traversal was $2, 4, 10, 11, 17, 20, 28, 31, 40$, what $x$ values would break the sorted order when put in the place of $20$?


Proving that context-free languages are closed under inserting symbols

Using closure under GSM mappings

Whenever possible, it may be faster to prove closure properties from
other known closure properties, That is why there has been a
systematic study of closure properties (see AFL, full AFL, trios,
...). This is somewhat developed in the Hopcroft-Ullman textbook,
ed. 1978).

For this problem, the insertion of a single character from the alphabet in the strings of a
language can be trivially performed by application of a
GSM-mapping. Since CF languages (and many others) are closed under
GSM-mapping, they are closed under the $+$ operator.

If you do not know about GSM mappings, you can do it with closure
under intersection with regular sets, homomorphism and inverse
homomorphism. That is actually how closure under GSM mapping is
proved.

Assuming your original alphabet is called $\Sigma$, you create a new
alphabet $\hat\Sigma=\{\hat a \mid a\in \Sigma\}$, i.e. a new set of
symbols in 1-1 correspondance with $\Sigma$.  Using the inverse of a
homomorphism (that simply erases $\hat\Sigma$), you insert an arbitrary
number of $\hat\Sigma$ symbols in the string.  Then you intersect the
result with the regular set $\{w\in (\Sigma\cup\hat\Sigma)^*\mid
|w|_{\hat\Sigma}=1\}$, so as to allow the insertion of only one
symbol from $\hat\Sigma$. Then you remove the hat with a homomorphism $\phi$ such
that $\forall \hat a \in \hat\Sigma,\, \phi(\hat a)= a$.


Comparative study between Deep neural nets and Bayesian Networks

They're not directly comparable.  They do different things.  They solve different problems.

A Bayesian network is a probabilistic model of the relationship between multiple random variables.  It is a generative model.  It builds a model of the joint probability distribution between multiple random variables.  It typically requires some priors or assumptions about the structure of the joint distribution.  While it could be used for classification, it normally isn't.

Deep learning is typically used for classification: supervised learning.  It is a discriminative model.  It does not try to model/estimate the joint probability distribution between multiple random variables.  It typically does not require you to specify priors or assumptions about the structure of the joint distribution.


Setting a cutoff for string distance filtering with different length strings

You can use normalized edit distance, where you divide the edit distance by the length of the larger of the two strings.  Whether this is better will depend on what you are trying to achieve.

There are many other techniques for fuzzy matching, which you might want to investigate.  The Levenshtein edit distance is only a starting point.


Compression algorithm for statistical data with a desired outcome size

Does something like that exists? Could you maybe throw me into the right direction?

The basic idea is to become independent from time (like store the accel value every XX seconds) and instead store all data changes. Then being able to set the "resolution" by time say if I then get this compressed data only every 10 minutes the data is less accurate (but still close enough) to then saying I get the compressed data every 1 minute.

When talking about signals that change over time with a fixed sample rate your question actually has a proper mathematical answer. It can be beaten for very specific kinds of signals that have patterns in them you already know beforehand, but if it's a generalized signal over time without any further information, it's essentially as good as it gets.
And that answer is found in the Fourier transform. By first transforming your data from the time domain into the frequency domain you get all the power you desire. You become time-independent, and you can drop the coefficients that are above frequencies you care about. You can also downsample, using more/less bits for coefficients that are important/not important.


Are there unary languages that are in RE but not R?

There are undecidable unary languages.

You can consider the set of words in $\{0,1\}^*$ as essentially encoding natural numbers in binary.*  Similarly, the set of words in $\{1\}^*$ encodes natural numbers in unary. Intuitively, if a set of natural numbers is undecidable, that doesn't depend on the base in which the numbers are represented, since we can easily write algorithms to convert between bases.

Another way to see this is to observe that any decidable language (over any alphabet) is, by definition, decided by some Turing machine.  There are only countably many Turing machines, but there are uncountably many unary languages.  Therefore some (almost all!) unary languages must be undecidable.

* This isn't quite true because of the empty string and because, e.g., the strings $1$ and $01$ are clearly different but both encode the number one in binary. To get around this, say that the string $w$ encodes the number whose binary representation is $1w$.


5 - Horizontal attacks
9 - Diagonal attacks of slope -1
3 - Diagonal attacks of slope +1
-
Total 17 pairs of queens attacking each other.

And yes, the numbers in each square correspond to number of attacking pairs of the queen if the queen in the corresponding column is moves to that location.


Optimal flow in a network with non-constant edges' weights

Your problem is a generalization of the Longest Path problem, which is NP-hard.  If the functions are constant and every conversion increases the amount of money, then there's no reason not to convert all of the money at once.  At that point, you are just looking for the longest path.

Your generalization, allowing partial conversions, non-constant functions, etc. cannot be easier than that.


How are "Problem Complexity" and "Solution Complexity" different?

Problem complexity is the best we can achieve for a given problem (sometimes under given restrictions). We usually talk about problem complexity when dealing with lower-bounds and it means there is probably no algorithm with lower time/place complexity than the proved ones.

Algorithm complexity is on the other hand the resources needed for a specific algorithm to run. When some algorithm solves a given problem in time $t$, we know that this problem has at most time complexity $t$ and hence, the complexity of an algorithm is an upper-bound for the complexity of the problem it solves.


Depending on your acceptance definition, you might be able to get away with only a single state. The basic idea is to keep the state information on the stack. The first thing you'd try is for each symbol on the stack to contain the "current state", i.e. each symbol is a tuple $(s,X)$, where $s$ is a state of the original PDA and $X$ is a stack symbol in the original stack alphabet. That way, the state information is stored on the stack. There is a problem here, however: if we pop $(s,X)$, we don't know what state the PDA should be in. For the solution, see these lecture notes. The construction heavily relies on non-determinism.


Valid bit incoherence between TLB and Page Table

The typical scenario where this kind of incoherence can occur is when the page table has been changed. In this case, an invalid PTE has become valid; perhaps the area of address space has been allocated, or a page has been swapped in.

"But", I hear you say, "why wasn't the TLB entry flushed when the PTE changed?" Well, it probably was, but the change may have happened on a different core.

The way this is typically handled in a multiprocessing operating system is to perform a "TLB shootdown". The core which changed the PTE issues an inter-processor interrupt (also known as a "crosscall") to any other CPU which may have a copy in its TLB to instruct it to flush.

An inter-processor interrupt is an expensive operation. But, of course, it doesn't need to happen a lot of the time. For example, if the other CPU is not currently using an address space which uses the TLB entry, it can't possibly access the entry until it performs a context switch, so the flush can be delayed until the next time the CPU enters the kernel (say).

But even if the other CPU is using the address space right now, you still don't need to perform a shootdown in this specific case, because the stale TLB entry is invalid. Attempting to access it will cause a page fault, so any attempt to use the stale TLB entry will be resolved by the page fault handler. And if that never happens, you've saved yourself a costly inter-processor interrupt.


Is there an algorithm for reducing CNFs further

CNF minimization is hard; see https://cstheory.stackexchange.com/q/9839/5038.  It is certainly NP-hard, and there is a sense in which it is "even harder".
One way to get some intuition why it is hard is that if the CNF is not satisfiable, then its reduced form is "False", whereas if it is satisfiable, its reduced form is something else.  So, if you had an efficient way to find a reduced form, that would immediately give you a way to tell whether the CNF is satisfiable -- a task that we know is NP-hard.
See https://cstheory.stackexchange.com/q/9839/5038 and https://en.wikipedia.org/wiki/Logic_optimization#Circuit_minimization_in_Boolean_algebra for some points into the literature on algorithms for this task.


Can an LL(k) parser parse any grammar without left recursion or common prefixes?

A 'top down parser' is usually understood to be a hand-written $LL(1)$ parser, or $LL(k)$ for some low $k$, which would explain the use of this terminology. These two concepts are therefore essentially the same.

I'm unsure what you mean exactly by 'common prefixes' - I guess you are talking about common lookaheads. If you ensure that you can always uniquely distinguish which production you need to expand by looking at the next letter, then your language is $LL(1)$ (and also contains no left recursion). Doing that usually means you change your grammar structure a bit so your parser is never confused by 'k letter prefixes' of the part of the input that you haven't looked at yet.

If you are really talking about common prefixes in the language-theoretic sense, then all your words would have to start with a unique letter, which means your language is finite and therefore $LL(1)$.


Relation between Hoare Type Theory and pointers

A pointer to a variable creates an alias. When the alias is modified, the corresponding variable is modified as well. Therefore, the rule for an assignment in Hoare's logic is not just update the value, but update the value for all associated aliases. Let's apply it to the example:

{True}        int i=0;  {i = 0}
{i = 0}       int*p=&i; {i = 0; [*p, i]}  /* *p and i are now aliases */
                                          /* The postcondition can be written as: */
                        {[*p, i] = 0}     /* In particular, *p = 0 */
{[*p, i] = 0} *p=1;     {[*p, i] = 1}     /* In particular, i = 1 */
{[*p, i] = 1} return i; {i = 1}

The general rules to reason about programs with pointers are given by Separation logic. The information whether two expressions reference the same memory location is obtained by pointer analysis and alias analysis.


Weaker, but similar conditions to Turing completeness?

The automaton as represented by a combinational logic circuit (CLC) is called combinational logic. Its model of computation is given an input, a CLC is used to compute the output. The name of that model of computation can also be called combinational logic. (This is similar to Turing machine, which is a kind of computing machine and also the name of the model of computation associate to it.)

The question has been answered. However, you might suspect there is no actual information in the answer so far. You may ask further, what is exactly that model of computation? How to understand it?

Firstly let us be clear, a combinational logic is the digital logic where the output is a pure function of the present input only. This is in contrast to sequential logic, in which the output depends not only on the present input but also on the history of the input and which can be used to build finite automatons.

Define a Turing machine (TM) as bounded-computing if there is a natural number $n$ such that it always halts before $n$ transitions. Define bounded computation as the following model of computation: given an input, a bounded-computing TM is used to compute the output.

A finite language is a language in which the number of words is finite. What are the languages that are accepted by the bounded-computing TMs? The answer is finite languages.

What is the computation done by a CLC?  For any given $n$ and $m$, and a function $f:\{0,1\}^n\to\{0,1\}^m$, there is a combinational logic circuit (CLC) that outputs $f(s)$ given $s\in\{0,1\}^n$ as input. That is all a CLC can do. Note that the input are limited to strings of same length, which is, however, not a limitation of its computing capability since a CLC can pad shorter inputs to longer inputs of the same longer length. Another apparent limitation is that the input can only be words made up from two symbols, 0 and 1. That is not an actual limitation, either, since we can encode any finitely many symbols by two symbols. For example, the $i^{\text{th}}$ symbol can be encoded as $011\cdots1$ where the number of $1$s is $i$.

As it might have become intuitively clear by now, the computation by a CLC and computation by a bounded-computing TM are weakly computational equivalent. (Weak computational equivalence of two models of computation means the set of functions computed by one of them is "the same" as the set of functions computed by the other. Strong computational equivalence means there exists a simulation between the two How to show two models of computation are equivalent?). The detail of a demonstration of the weak computational equivalence is not shown here. However, the ideas are pretty simple. Now we know that combinational logic is computational equivalent to bounding computing. Hopefully, that provides a bit of insight into what is combinational logic as a model of computation.

There is a model of computation called combinatory logic, which is weakly computational equivalent to Turing machine but is not relevant here.


How do you find an infinite regular language that is a subset of a non-regular language?

Note that any non-regular language is infinite, since any finite language is regular.

Instead of searching for infinite regular subset in some given non-regular language, why don't we try to construct a non-regular language that contains an infinite regular language?

To do that we can take some context-free language, which is not regular, e.g. classical $a^nb^n, n \ge 0$, and "add" some infinite regular language to it. By "add" I mean the union operation on sets.

I should notice that one has to be careful while "adding" an infinite regular language to a non-regular one, since $L(a^nb^n) \cup \Sigma^* = \Sigma^*$, which is obviously regular.

So let's take a regular language $L(a^*)$, which has only one string in common (the empty string) with $L(a^nb^n), n \ge 0$ as our candidate "addition".

It's easy to prove the language $L(a^*) \cup L(a^nb^n), n \ge 0$ is non-regular (context-free). And its regular subset $L(a^*)$ is infinite.


Convergence of Simulated Annealing Based Algorithms

I copied this answer from computational science

There is a theorem that syas that a black box algorithm is guaranteed to find the global minimum of an arbitrary smooth (i.e., twice continuously differentiable) function if and only if it samples points densely in the search space.

Here dense is meant in the topological sense, i.e., it must sample points in arbirarily small neighborhoods of every point.

In this case, the worst case complexity is O((dδ)−n), [the Latex parser chokes with nested big brackets] where d is the diameter of the search space and δ the guaranteed error in x

Edit: While this looks like being the worst case complexity for locating an δ-accurate x rather than for locating a point for a ϵ-accurate f, the complexity for the latter is as bad (even for the rather big value of ϵ=(ffirst−fglobal)/2), as one can easily construct a smooth function which interpolates all data points so far but takes much smaller values in the center of the largest open ball not containing one of the points evaluated.

Thus guaranteed convergence to a global minimum is worthless in practice. (For example, uniformly random search has a convergence guarantee to the global minimizer, whereas most practically fast algorithms don't have one.)

Note that simulated annealing usually performs much worse than modern methods. Rather use code recommended in:

Comparison of derivative-free optimization algorithms (2012, by Nick Sahinidis)

Black-Box Optimization Benchmarking (BBOB) 2012 (by Auger, Hansen, et al.)


Given an array $a$, we have to find product of $a_{j}$-$a_{i}$ modulo $998244353$ over all $i$ and $j$ given $j>i$

The product $$V=\prod_{i<j}(a_j-a_i)$$ is the determinant of the Vandermonde matrix of the numbers $a_1,a_2,...,a_n$.
The square of this number is the discriminant  $D$ of the polynomial $$p(x)=\prod_i(x-a_i)$$
This in turn is equal to $$V^2=D=(-1)^{n(n-1)/2}\prod_ip'(a_i)$$
You can quickly compute the coefficients of $p(x)$ and thus $p'(x)$, evaluate it at the $n$ points $a_1,a_2,...,a_n$ and their product. Then compute square root. The sign of $V$ you determine by sorting and counting the parity of the number of switches.
You can do all this in $O(n\log^2(n))$.
See the relevant algorithms here.
For the modular square root, you can use Tonelli-Shanks for efficiency. Although the theoretic order of this step is constant since the prime $998244353$ is fixed.


Does the Bondy-Chvátal theorem have algorithmic applications beyond Ore's theorem?

Other way than Bondy-Chvátal theorem is brute force search. However brute force search isn't an efficient way of solving this problem - there can be an exponential number of possibilities to test.

You won't have to test so many possibilities, if you will try following algorithm:

http://arxiv.org/pdf/1405.6347.pdf

The main principle of algorithm is "to think over" which paths(possibilities) should be checked than check many wrong paths.

Algorithm can remove unnecessary edges from graph and test when Hamiltonian cycle can't exist in graph.

Algorithms implementation:

http://findinghamiltoniancycle.codeplex.com/


It seems very likely that it is $NP$-complete.

A good "trick" to tackle a problem like this would be to create an instance where there are $X$ very big numbers in the grid and you're allowed to choose $X$ items. Choose the goal amount so that you need all of these big numbers, and this constrains you to "use" all of the $X$ items to cover the $X$ big numbers. The only freedom is in where exactly you pick the position of the rectangles relative to the big numbers.

A good candidate for a reduction would be Vertex Cover, which is $NP$-complete even for planar, 3-regular graphs. You could fix some embedding of the graph in the plane, and then place large numbers on the edges, so that you need to collect these numbers to win. You'd make $K$ so large that you can cover almost all of the big numbers in each edge, but not quite. Placing a rectangle at the position of a vertex would cover numbers in all of the incident edges.

I'll leave it to you to figure out the details (since you only asked for a "way" to prove it) but I'm pretty sure this is a feasible approach.


Depth first or breadth first ordering in binary search trees?

Think about what happens when you move from one layer in the tree to the next. When you start getting to layers with progressively more nodes, you'll eventually get to a spot where the layers are so big that they can't fit into memory caches. When that happens, if you've laid out the memory in a BFS order, then going from one layer to the next will almost always cause a cache miss because the memory fetched for the first layer won't include the node from the next layer in it. In other words, every link followed will cause a cache miss. On the other hand, if you use DFS order, then the memory for the nodes will have the nodes broken apart into smaller chains of nodes corresponding to the paths taken by DFS. If you do lookups in a way that follows those chains, it's possible that you'll have no cache misses at all when going from one node to the next, which can dramatically speed up lookups.

The ordering I've actually heard most for making cache-friendly BSTs is the van Emde Boas layout, which is formed as follows:

If the tree has height two or less, lay it out in DFS or BFS order (they're the same here).
Otherwise, split the tree at the middle level into a "top tree" of the first half of the nodes and up to $\sqrt{n}$ "bottom trees" formed from the lower levels. Recursively compute the van Emde Boas layouts of each of these trees, then concatenate them together in order.

You can prove that this layout is optimal assuming that you don't know anything about the particular sizes of the caches of the machines in the computer (it's known as a cache-oblivious data structure).

If you do know the cache size, though, the "best" choice is probably to use a B-tree instead of a BST, since B-trees are specifically designed to play nicely with caches. Although they were designed for on-disk storage, they work really well in main memory, as some recent work has shown.


Count number of ways in which atomic operation(s) of n different processes can be interleaved


Locate all locations in a sorted array where arr[i]<arr[i+1]

Here is a fairly simple fix. Anytime you "overshoot" in your search (I.e. $A[i]=A[i+2^j]$ but $A[i] \neq A[i+2^{j+1}]$ when you backtrack to find the correct index, also keep track of elements in that range that satisfy the inequality (may as well if your scanning over them anyway). You can pick back up at $A[i+2^{j+1}]$. This way, your running time is $O(n)$ worst case.


Hint: use $0^n1^n$ for large enough $n$.

Another approach is to use the Myhill-Nerode criterion, say with the words $0^n$.


Reference request: optimizing procedures on lists in dynamic languages by performing safety checks in advance

I'm not aware of anything exactly like this, but there are some things that are arguably related.

For specifically sorting this is related to the Schwartzian transform, though with a very different goal.  In the Schwartzian transform, you run through the input applying an expensive function and pairing the input and output together, then sorting on the output.  This is in contrast to performing that expensive function on each operation.  In your case, your "expensive function" would be the type checks and the dynamic dispatches.  A bit differently you would be checking a property for the whole list as well and then choosing which comparison operation to use based on that.

In a totally different vein, there's a general technique called polymorphic inline caching (pioneered by the Self team and covered, among many other things, in Craig Chamber's thesis) and more generally adaptive optimization that is used in some virtual machines.  Polymorphic inline caching solves the problem that if we do a dynamic dispatch, then we are jumping to some completely unknown code, and thus we can't inline it and optimize it and the current function.  The solution is simple: just do an if to test if we are in some specific case, and if so, we can inline that code, else we do the dynamic dispatch.  The problem is there is an unbounded, unknown number of possible cases.  This isn't a problem, though, for a Just-In-Time (JIT) compiler which can just do this for the cases actually seen at runtime.

This doesn't solve your problem since dynamic dispatch is based on the runtime class of an object, not on some arbitrary predicate like "all the elements of this array have the same type".  This is where adaptive optimization comes in and things like tracing JIT compilers.  It's quite conceivable that unrolling a loop a few times or inlining a couple levels of recursion can lead to many type checks being eliminated with simple constant propagation style optimizations, and possibly entirely eliminated by more sophisticated optimizations in some cases.  Nevertheless, it will often not do the same thing as you are suggesting and would need to see a trace first for each use of the sort function.  On the other hand, if it knows all the elements are numbers, say, from earlier code, it can eliminate checking entirely.


Undirected graph whose BFS and DFS trees have roots of degree 2

The degree of the root in a BFS tree equals the degree of the vertex in the original graph. Hence condition 2 states that your graph is 2-regular. Since it is connected, it must be a 5-cycle. Running DFS on the 5-cycle results in a path, and in particular, the root has degree 1.
This argument shows that there's nothing special about the number 5: the result remains true for any number of vertices.


Why is the complexity of the following code $O(n^4)$?

There are two things that could be measured here. First, the time complexity of the code, which is to say the number of steps it takes to execute. In that case we have two possible metrics: (1) count each arithmetic operation as taking 1 unit of time. That's the one you're likely used to. In (2) we count the time an arithmetic operation takes as a function of the number of bits needed to express the operands.

The second possibility is to measure the magnitude of the result, $r$, as a function of $n$. It appears that your professor is looking for the second measure: express $r$ in terms of $n$. That, though, is a bit problematic, since $s$ is reset to zero at each iteration of the outer loop, so the final value of $r$ is just the result when $i=n$ which will be $O(n^6)$.

The upshot is that your calculation of the running time, $O(n^2)$ is the only one that makes any sense here. Ask your professor for clarification.


"Term Rewriting and All That" - Exercise 3.10

If we can find $(z_1, z_2)$ such that $a z_1 + b z_2 = 1$ then we can take $(k z_1, k z_2)$ to obtain an arbitrary number $k (a z_1 + b z_2) = k \in \mathbb{Z}$ and then it is proved that $g_{(a, b)}$ is onto. However, every linear combination of two numbers $(a, b)$ is a multiple of their $gcd$. So, $g_{(a, b)}$ is onto if and only if $gcd(a, b) = 1$.


Methods of turning a decision problem into finding the certificate?

The main method is self-reducibility. Suppose that your problem is of the form "there exists an object $x$ such that $P(x)$". Consider some partition of the set of all possible objects $O$, say $O = O_1 \cup \cdots \cup O_m$ (here $m$ should be "small", i.e. polynomial in the size of $x$). If the problem "there exists an object $x \in O_i$ such that $P(x)$" can be reduced to your original problem, then you can use a recursive approach for finding some certificate. The reduction should have the property that a witness for the reduced problem implies a witness for the original problem.

SAT, the example in the question, has exactly this property. In this case, $x$ is a truth assignment, and $P(x)$ states that $x$ satisfies some formula. For each variable $x_i$ we can partition the set $O$ of all truth assignments into $O = O_{i,true} \cup O_{i,false}$ according to the value of $x_i$. The problem "there exists a truth assignment $x \in O_{i,val}$ such that $P(x)$" (where $val$ is either $true$ or $false$) is also a SAT problem. We can use this to figure out a truth assignment satisfying $P$.

A more interesting example is 3-colorability. In this case $x$ is a 3-coloring and $P(x)$ states that $x$ is a valid coloring for the input graph. For any two unconnected vertices $v,w$, we can consider the partition $O = O_{v=w} \cup O_{v\neq w}$, according to whether $x(v) = x(w)$ or not. We can reduce the problem "there exists $x \in O_{v=w}$ such that $P(x)$" into an instance of 3-coloring by merging $v$ and $w$. We can reduce the problem "there exists $x \in O_{v\neq w}$ such that $P(x)$" into an instance of 3-coloring by adding the edge $(v,w)$.


Common name for inverse of beta reduction

Yes, it's called beta expansion. Usage examples: Horwitz, Miller, Galbiati and Talcott, Coq manual, …

Similarly $M \to (\lambda x. M \, x)$ (the converse of eta reduction) is called eta expansion, and so on.


Subtyping and subkinding, are they relevant?

There will be no inconsistency. Those arise from shady postulates which state that some subkind is an element of itself, or that "too large" a kind/type is an element of a "too small" one (the most famous example is $\mathrm{Type} : \mathrm{Type}$), but that is not what we are dealing with here.

To give an example of what you're looking for, take $\mathrm{Type}$ to be the class of all sets. For the subtype and subkind relations we simply use subset and subclass inclusion. Take $a$ to be the class of all finite sets, and $b$ the class of all countable sets. Let $A = \{23, 42\}$ and $B = \mathbb{N}$. Then we have $A : a$, $B : b$, $A \subseteq B$, $a \subseteq b$, and both $a$ and $b$ are subkinds of $\mathrm{Type}$. And it would not be difficult to arrange $A \subseteq B$ and $b \subseteq a$, if we so wished.

Or you could take $\mathrm{Type} = a = b$ and $A = B$, but that's not a very informative answer, even though it has its virtues.


how to mapping reduce any r.e. language to the diagonal language K?

For any r.e. language $L$, it is the domain of some M_l.

Consider the machine $M_n(x,y)=M_l(x)$, and now let $f(x)=s_1^1(n,x)$ (obtained from snm theorem). Hence for any $y$, $M_{f(x)}(y)=M_l(x)$

Then $L$ can be reduced to $K$ by $f$ :

if $x\in L$ iff M_l(x) halts iff $M_{f(x)}(f(x))$ halts iff $f(x)\in K$.


Polynomial time is not too difficult.

A "cluster" contains a sequence of 1 or more consecutive numbers from your list. The "badness" of a cluster is defined as the sum of absolute differences between the numbers, and the average of the numbers in the cluster. A sequence of clusters is a list of clusters, containing consecutive numbers from the list starting with the first one. And the "badness" of a sequence of clusters is the sum of badnesses of the individual clusters.

First get a reasonable upper bound for the best clustering to avoid unnecessary work: Just cluster the n numbers into m buckets of equal or almost equal size, then calculate the badness of this sequence of clusters. Call the result B. You might also calculate the badness of a sequence of clusters created by splitting where the largest gaps between consecutive numbers are.

Now for 1 ≤ m' ≤ m, and for 1 ≤ n' ≤ n - (m - m'), calculate the best sequence of m' clusters covering exactly the first n' numbers, and its badness. For m' = 1 that's trivial, because the cluster consists of the numbers 1 to n'. For m' > 1 it is more difficult: The best clustering using m' clusters to cover 1 to n' consists of the best clustering using m'-1 clusters covering 1 to n'' for some n'' < n', plus the cluster n''+1 .. n'. You calculate the badness of this for n'' = n'-1 down to m'-1. All these badnesses can be calculated in O (n), so the best badness for m' and n' can be found in O (n).

In total, you find the optimal badness for m clusters covering 1 to n in $O (n^3)$. If you take advantage of the upper bound B found earlier, and consider that any result that leads to a badness > B can be ignored, you can probably save significant amount of time.

PS. How to find the badness for different clusters each in constant time: Let's say you want to find the badness of a cluster covering the numbers from l to r, for l = r, r-1, r-2, ..., 1. Start with l = r. The sum of items in the cluster is $C = a_l$. The badness is 0. Let s = l. Then the sum of items at indices < s is $S = 0$.

Now replace l with l-1. Increase C and S by $a_l$. The average A of items in the cluster is C / (r - l + 1). As long as $a_{s-1} ≥ A$ replace s with s-1, and subtract $a_s$ from S. The badness in the cluster is C - 2S + ((2s - l - n - 1)A (unless I made some mistake).