Grammer Class/Production Rules of Programming Languages

The issue is where you want to draw the line for what is considered "syntax". Sure, variable scoping typically requires context-sensitivity, but that doesn't need to be handled by the parser. The parser could just parse the syntax allowing out-of-scope variables, and a follow-on pass could check for out-of-scope errors. In practice, many real implementations of parser for real languages are context-sensitive, but this is handled in an ad-hoc manner by sharing state between productions and allowing "actions" to be attached to context-free productions. In particular, few (no?) languages use general-purpose context-sensitive parsing approaches. In fact, few uses general-purpose context-free parsing approaches. Instead, tooling for potentially limited classes of context-free grammars is used and, as mentioned, ad-hoc "semantic actions" lead to the parser actually being context-sensitive but this done in a way that is not captured by the context-free grammars that putatively describe the language.

In other words, a context-free grammar for a language often describes a larger language than what is actually accepted. But rejecting a program after parsing it for out-of-scope variables, say, is no different than rejecting it for having a type error. Type checking is almost never done while parsing. So what checks are done while parsing or later is usually done as a matter of convenience, and many aren't nicely described by a grammar.

The grammar complexity of the syntax has little to do with the computational complexity.  For example, every bit string is a syntactically (and semantically!) valid Jot program, and Jot is Turing-complete.


What is the difference between bounding and pruning in branch-and-bound algorithms?

In branch and bound algorithms, you essentially partition the original problem to be solved in a number of subproblems whose union is equivalent to the original problem you started with. The process of deriving new subproblems is called branching and leads to the so-called branch decision tree. Now, when you need to solve a subproblem, you can either determine its optimal solution, show that the subproblem is infeasible (so that you can discard it), or you can show that the subproblem solution is no better than the best known solution for the original problem. If you are not able to solve a subproblem, you branch again, partitioning it into sub-subproblems. Now, for each subproblem you can derive a lower bound for its solution and, if the lower bound is greater than or equal to the best known solution for the original problem, you can discard the subproblem since the best solution you can obtain for the subproblem is certainly worst with regard to the feasible solution of the original problem.
In order to get a lower bound you must relax the problem. The relaxation may be continuous, lagrangian etc.

Therefore, the word bound in branch and bound refers to the process of determining lower bounds for subproblems. Pruning refers instead to the process of discarding subtrees in the branch decision tree rooted at subproblems whose solution is impossible or worst with regard to the feasible solution of the original problem.


Consider the coding $a \to 0$, $b \to 1010$, $c \to 100$, $d \to 1011$, $r \to 11$.$\ \ $  I let you guess what represents $010101101000101101010110$ in this coding, but this can be easily computed by a sequential machine, as illustrated
here, slides 9-10.

What is the theory behind this? A subset $P$ of $A^+$ is a prefix code if no element of $P$ is a proper prefix of another element in $P$. For instance, the sets $\{0, 1010, 100, 1011, 11\}$, $0^*1$ and $\{0^n1^n \mid n > 0\}$ are prefix codes, with $A = \{0, 1\}$. Prefix codes are conveniently represented by the leaves of a tree. In particular, variable-length Huffman codes, the UTF-8 code and the Morse code are of this type.

Now if $B$ is another alphabet and $f:B \to P$ is an injective function, then $f$ extends uniquely to an injective monod morphism (coding) from $B^*$ to $A^*$. Further, if $P$ is a finite subset of $A^+$, the decoding function $f^{-1}$ can be computed by a sequential machine. This machine is essentially the minimal automaton of $P^*$, equipped with appropriate outputs (see the example).

Variable-length codes (whose prefix codes are a special case of) form the topic a rather advanced theory. The main reference is:
J. Berstel, D. Perrin, C. Reutenauer, Codes and automata. Encyclopedia of Mathematics and its Applications 129. Cambridge: Cambridge University Press (2010). ISBN 978-0-521-88831-8.


Sum of k smallest values of affine functions

I recently found out that my problem is known as the k-th level problem, which itself is equivalent to the k-set problem in the dual plane. Since almost 50 years, it is an open problem how many sets there are exactly. At present, the best upper bound is given by $O(n k ^{1/3})$: https://en.wikipedia.org/wiki/K-set_(geometry)


Find all group of neighbors with a constraint weight

Your problem is the same as listing all cliques in a graph.

Given your weight matrix, construct a graph in which two vertices are connected if the weight between them is below the threshold. A clique in this graph is the same as the sets of vertices you are interested in.

A graph could contain exponentially many cliques - even exponentially many maximum cliques (consider for example $n/3$ paths of edge-length 2). So in general you will need exponential time to list all cliques.


does every graph have a complete, preferred, stable and grounded extension?

As a complete extension is an admissible set containing exactly these arguments it defends, there is always at least one complete extension, that may be the empty set and nothing else.

Grounded extension is a minimal complete extension, hence there is always one, and it also has the property to be a unique fixed point.

Perferred extension are maximal complete ones, hence starting from the same principle (there is at least one complete extension) there should always be at least one.

As far as I know, the notion of stable extension is not so well-defined and their existence therefore depends on the chosen definition.

You can probably work out additional properties from the paper

Baroni, P., Caminada, M., & Giacomin, M. (2011). An introduction to argumentation semantics. The Knowledge Engineering Review, 26(04), 365-410.


Are there any optimization problems in P whose decision version is hard?

No. The optimization problem is "How big is the biggest $X$?" and the decision problem is "Is there an $X$ that is bigger than $y$?" Solving the decision problem simply involves comparing $y$ with the size of the biggest $X$.  You can certainly compare two numbers in polynomial time so, if you can solve the optimization problem (compute the size of the biggest $X$) in polynomial time, you can solve the decision problem.


Reduction function from A to its complement

This is true for any recursive language $A$ different from $\emptyset$ and $\Sigma^*$ for some finite alphabet $\Sigma$. Your definition is correct. In general you could define $f$ as following. Let $a\in A$ and $\overline{a} \in \overline{A}$.

$$f(x)=
\begin{cases}
      \overline{a} & x\in A \\
      a & x\notin A
\end{cases}
$$
From this definition it follows $x \in A \iff f(x) \in \overline{A}$. Moreover, since $A$ is recursive $f$ is computable for any $x$ and hence $A \leq_T \overline{A}$.

The whole point is to decide $x \in A$ by using $f(x)$ and $\overline{A}$. So, given $x$ you can effectively say whether or not $x \in A$ only by looking at if $f(x) \in \overline{A}$. If $f(x) =\overline{a} \in \overline{A}$ then $x$ is in $A$, otherwise $x$ is not in $A$. Hence $A \leq_T \overline{A}$.


What is the time complexity of this "reverse words" algorithm?

This algorithm runs in linear time in the size of the input $O(n)$.

To see why try to count how many times you read/write to a position in the string. Note that asymptotically this is equal to the total running time.


There is a serious typo/mistake in the OP's (original) question. The title say "Two criteria for an edge to belong to all MSTs". However, the lemma 1 talks about "appears in any MST". To be consistent with the title and with lemma 2, let us modify the lemma 1 as:

An edge $e$ appears in all MSTs iff $e$ is the unique lightest edge in the cut-set of some cut which $e$ crosses.

According to the title of the question, we may assume the OP's intention is to prove the two criteria for an edge to belong to all MSTs is equivalent without any reference to MST. (If reference to MST is allowed, both criteria are equivalent to the statement, the edge belongs to all MSTs. Hence both criteria are equivalent to each other as well.)
Let us state the equivalence of the two criteria clearly.

Let $G$ be a weighted connected undirected graph and $e$ an edge in $G$. The following two properties of $e$ are equivalent.

(unique-cut-lightest) there is a cut of $G$ such that $e$ is the unique lightest edge that crosses the cut.
(non-cycle-heaviest) every cycle containing $e$ contains an edge heavier than $e$.

It turns out we do have a simple proof of the above equivalence.
Unique-cut-lightest $\Rightarrow$ non-cycle-heaviest: Let $c$ be a cycle that contains $e$. As a cycle, $c$ must contains another edge in that cut-set. Name that edge $e'$. Since $e$ is the unique lightest edge in that cut-set, $e'$ is heavier than $e$.
Unique-cut-lightest $\Leftarrow$ non-cycle-heaviest: Let the vertices of $e$ be $u$ and $v$. Let us remove $e$ and all edges that is heavier than $e$ in all cycles that contains $e$ from $G$ (keeping all the vertices, however), obtaining a new graph $G'$ that share the same vertices as $G$ but with less edges. There is no path from $u$ and $v$ in $G'$; otherwise, any such path together with $e$ is a cycle in $G$ that contains no edge that is heavier than $e$, which contradicts the assumption. So $u$ and $v$ are in different connected components of $G'$. Divide the vertices of $G'$ into two sets, the vertices in the connected component of $u$ and all the other vertices. These two sets of vertices is a cut of $G$ as well. $e$ crosses that cut since $u$ is in the connected component of $u$ and $v$ is not. Since all edges other than $e$ crossing that cut is one of the removed edges, $e$ is the unique lightest edge crossing that cut.


You are asking several related questions. I will only answer the first one. The heapify procedure gets an almost-heap $A$ and a node $i$. The heap property is satisfied for all nodes except for $i$. Heapify proceeds as follows:

Determine the largest child $j$ of $i$.
If $A[i] \geq A[j]$, the heap property is already satisfied.
Otherwise, exchange $A[i]$ and $A[j]$, and run heapify on $A$ and $j$.

After the exchange, the heap property is no longer violated for $i$, but might be violated for $j$. For this reason we have to call heapify recursively on the node $j$.

I suggest you try a few examples and see for yourself that sometimes the recursive call is necessary.


Show that a language consisting of strings of a prime number of 1s is irregular using pumping lemma

Your attempt doesn't work, since you need the word you pick to belong to the language. Therefore I suggest picking $w = 1^p$, where $p$ is a prime which is larger than the pumping constant. The pumping lemma shows that there is a decomposition $w=xyz$, where $y \neq \epsilon$, such that $xy^iz \in L$ for all $i \geq 0$. Let $x=1^r$, $y=1^s$, and $z=1^t$, so that $r+s+t=p$. Then $xy^iz = 1^r 1^{si} 1^t = 1^{r+si+t} = 1^{p+(i-1)s}$. Thus, $p+(i-1)s$ has to be prime for all $i \geq 0$. However, when $i = p+1$, we get $p+(i-1)s = p+ps = p(1+s)$, which isn't prime.


monotone min-3-sat polynomial algorithm?

3SAT is NP-complete.  Positive 3SAT (where all literals are positive) is in P, and thus presumably not NP-complete.  There is an even simpler algorithm for Positive 3SAT: set all variables to true.  That will always provide a satisfying assignment.

I can't comment on your algorithm  because it doesn't seem fully specified: you describe what order to make assignments to variables, but you don't describe how to choose a truth assignment for each variable.  (Should it be set to true?  to  false?  The question doesn't say.)


Arden's rule expressed as matrix algebra

The notation is probably defined in the paper or in some standard reference, but one can guess that
$$
A^* = (I - A)^{-1}.
$$
This definition satisfies the identity $A^* = I+AA^*$, since
$$
I+AA^* = I-((I-A)-I)A^* = I-(I-A)A^*+A^* = I-I+A^* = A^*.
$$
Presumably a quasiregular matrix $A$ is one for which $I-A$ is invertible, perhaps with some additional assumptions.


How can we get small test error reducing only train error?

Yes, if you are classifying images, each example would be an image.  There is some distribution on images that are likely to arise in practice.

We need independence and identical distributions because without it we can't learn.  If we practice five times, but then are tested on something entirely different, our practice might not be useful.

The distribution refers to the distribution of each single image.  That has nothing to do with how many images you draw from that distribution.  Imagine flipping a biased coin.  I could flip the coin 100 times; each outcome would be a sample from that (biased) distribution, and that's true whether we have 10 coin flips or 1000 coin flips.


How to do high performance string matching when comparing unordered sets of tokens

So you want to use the Jaccard index as your metric of similarity.  Well, the Wikipedia page for the Jaccard index (and which I linked to in the comments above) already has some hints on methods for finding close matches, more efficiently than comparing all pairs.  For instance, you can use locality-sensitive hashing.  Hint for the future: you might want to do more research in the future based on feedback from folks, as locality-sensitive hashing was already suggested in the comments and a relevant Wikipedia page was also mentioned in the comments.

If tokens are not too common, there's another alternative method you could also try.  You could build an inverted index: an index that, for each token, lists all of the strings that contain it.  Now given a new string S, it's easy to enumerate over all of the tokens in it, look each one up in the inverted index, find all other strings that share at least one token in common with S, compute the similarity between that string and S, and keep the best one.  As long as no string contains too many tokens and no token is present in too large a fraction of strings, this will perform better than all-pairs comparison.

Your "extended" problem is different in nature and would probably be better asked as a separate question.  It might be a much harder problem.


Let $B[i] = A[i] + i$ and let $C[j] = A[j] - j$. You are looking for
$$
\max_{i \geq j} B[i] + C[j] = \max_j (C[j] + \max_{i \geq j} B[i]).
$$

This gives a linear time in-place algorithm for your problem:

maxB = A[n] + n
maxSum = A[n] - n + maxB
for j=n-1 downto 1:

maxB = max(maxB, A[j] + j)
candidate = A[j] - j + maxB
maxSum = max(candidate, maxSum)

return maxSum


No, you can't do this. A single LBA can process inputs of any possible finite length. For any individual input, there are only finitely many possible tape configurations but, over all possible inputs or all possible lengths, there are there are infinitely many possible tape configurations. A finite automaton can't have one state for each of these configurations.

In particular, LBAs can accept non-regular languages, such as $\{a^nb^n\mid n\geq 0\}$ so there are LBAs that can't be converted to a single DFA.

What you could do is produce an infinite family of DFAs, one for each possible input length. Each of these would have a finite number of states. However, such an infinite family could recognize any language – even undecidable ones! – because every language contains only finitely many strings of each length and every finite language is regular.


Finding least number of line segments with length $L$ that cover $N$ points

Point indexes are just a way of naming them. What matters in the
algorithm is only their positions.

The first thing you need is the management of your points. You need a
structure that sorts them according to position when given the initial
list of positions (ascending or descending order, it does not
matter). This structure must allow you to remove a point, and add it
somewhere else at low cost to keep the list sorted when you operate a
change. You will find many such structures in any course on data
structures and algorithms.

Then you need a structure for representing segments that will group
your points into a collection of buckets of points covered by the same
segment. This collection of buckets is a covering. The construction of
an optimal covering is easy. You can show easily that, given any
covering, you can always replace the lefmost segment by a
segment that start rightward at the leftmost point, to get another
covering. From that you can show by induction that you can get an
optimal covering by placing a segment so that its leftmost end is on
the leftmost point, and then reapeat recursively starting at the
lefftmost point not yet covered.

A symetric proof shows that you can alternatively start from the
right. Actually, combining the two proofs, you can show that you can
always chose your next segment either rightward from the leftmost
point or leftward from the rightmost point, computing from both end towards the middle until the two computations "meet" somewhere in the middle (you can choose that "somewhere"). In all versions of the algorithm, the last segment added may cover points that are already covered (though it can be avoided for the unidirectionnal versions of the algorithm - it does not matter anyway).

We assume first you build your covering from the left only.

Each change is composed of two "half-changes", removal of the point from its former position followed by addition of the point in the sorting structure at its new position. After performing them, you have recompute your segments.
You try to limit the new computation to an incremental change to the previous one, and you must have kept your collection of buckets.
You start at the leftmost segment affected by the leftmost
"half-change" (either addition or removal), and you recompute segments until you find a segment
that is the same as for the previous covering (which ends a first incremental update), and you do some
accounting to know whether and how that changes the number of
segments. If the rightmost "half-change" has been passed in the
process, you are also done for that change. Else you do the same for that
second half-change, still recomputing from left to right as in the
first computation of a minimal covering of segments.

The algorithm could alternatively compute coverings from right to left. It is the same in reversal.

Starting from both
ends may make the algorithm a bit more complicated (you have to work out the changes for yourself), On the other hand
it may improve it somewhat as it can avoid having to recompute all
segments up to the right end in pathological cases of incremental recomputation: you are sure an incremental update will not exceed half the collection of points ( actually it is not exactly half, depending on how the "meeting point in the middle" is chosen). But I guess it is
a minor improvement. You might be even more subtle in choosing the
"middle place"  and in possibly changing it when you move your points,
 to account for
changes of the algorithm behavior according to point density. But this
is marginal and requires a bit of analysis.

Note: the above works for addition and removal of points, without necessarily keeping a constant number of points, provided it is allowed by the structures  that I left unspecified and up to your own choice. The fact that the number of points remains constant in the statement of your problem could be an indication that a specific method is expected that would make use of that fact.

P.S. What do you mean by best approach ?  What is the criterion.


Detecting face like patterns using CNN based face detector

You probably need a training set that contains examples of abstract faces and minimalistic face patterns.  There's no reason to expect a neural network trained on real faces to detect abstract face patterns; neural networks don't necessarily generalize that way.


Can I apply Rice's theorem to decide decidability status of these languages?

You're right that both of these are non-trivial properties. The key is, Rice's theorem applies only to non-trivial semantic properties.

So what defines a semantic property?

Intuitively, a "semantic" property is a property of what the machine does, rather than how the machine works. If you treat the machine as a black box that takes input and gives output, with all the internal mechanisms hidden, semantic properties are the ones you can still measure.

Applying this rule of thumb, we see that printing letters and multiplying numbers are both semantic actions (they're things a program does rather than mechanisms by which the program does it), so yes, Rice's Theorem applies, and these properties are undecidable.


A recursively enumerable language and a recursively enumerable set

No they do not have exactly the same meaning. A language is a set of strings, whereas a set can be virtually anything. Usually such a set is a set of (natural) numbers, but we also can consider sets of graphs.

However, when the sets are accepted or generated by Turing machines, then they have to be represented on a tape (for input or output). This means they have to be represented as strings anyhow. Hence for the Turing machine itself there is no difference. Only for the human beholder there is an interpretation of the string as number or graph.


NFA state complexity for the complement of EPAL restricted to a fixed length

Hint: further break up the difficult case $\{ww' : |w|=|w'|=n,w\neq w'\}$ as a sum $$\bigcup_{i=1}^n \{ \Sigma^{i-1} \alpha \Sigma^{n-i} \Sigma^{i-1} \alpha' \Sigma^{n-i} : \alpha \neq \alpha' \in \Sigma \}. $$
In total there are $n+1$ cases (including $\{w : |w| \neq 2n\}$), so if you can implement each one in $O(n)$ states, you're done.


The complexity of checking the correctness of the problem solution on the Turing machine

What you might be looking for is an application of probabilistically checkable proofs (PCPs) for verifying computation. People have been working lately on making this practical, see for example Computational integrity with a public random string from quasi-linear PCPs, and other works by Eli Ben-Sasson and Alessandro Chiesa. At the moment this is unfortunately still a mostly theoretical concept.


Your question is rather unclear but I think it's something like this:

  I have a Turing machine and I want to figure out if it runs in polynomial time.  That means that its running time must be bounded by a polynomial function of the input's length. I've figured out an expression for its running time but this expression is in terms of, e.g., some of the numbers represented in the input, and not just the input's length.  How do I proceed from here?

So you've computed a running time that's something like $f(n, x_1, x_2, ...)$ where the $n$ is the input length and the $x_i$ are other quantities associated with the input.  What you need to do is bound how big those quantities in terms of $n$ and then substitute those bounds into&nbsp:$f$, to obtain a function whose only input is $n$.

For example, your input includes a list of numbers. That list could have as many as roughly $n/2$ entries, since it could be $0\#0\#0\#\ldots$.  If the list has just one entry, that number has roughly $n$ bits, so the biggest number in the list could be as big as $2^n$ or so.

In other situations, you might know more about the input.  Perhaps the entries in the list all have to be different.  Then the input can't be $0\#0\#0\#\dots$ and the entries themselves have to get longer than just one bit.  If you had $k$ entries in the list, they'd need about $\log k$ bits each, at a minimum, so you'd have $k\log k\leq n$, which you can try to solve and use.

Then, substitute everything you get into $f$ and see what you get.  For the example you have in your question, it's something like $|m|=\Theta(n)$, $k=\Theta(2^n)$, so $|m|(\log n)(\log k)$ is about $n(\log n)(\log 2^n) = n^2\log n$.


Boolean logic: why is the "opposite" of and equal to or?

This is called DeMorgan's law, and let us think about it like this... By the way, let

$\land$ be &&
$\lor$ be ||
$\neg$ be !

You have a door, and the door has two locks. To open the door you therefore need keys $A$ and $B$, written $A \land B$.
Well, suppose that someone is not able to open the door. Well, then that must be because they don't have both keys, or, $\neg (A \land B)$.
But analysing this situation, if you do not have two keys, you either lack $A$ or you lack $B$, or in other words, you either $\neg A$ or you $\neg B$.
Hence, $\neg (A \land B) = \neg A \lor \neg B$.
You can go through the exercise with a door where you need 1 of 2 keys to open for the reverse case.


Find the minimal number of runs to visit every edge of a directed graph

This looks like a minimum-cost flow problem, but with demands instead of capacities.

A flow in a directed graph $G = (V,E)$ is a function $\phi: E\to \mathbb{R}_{\ge 0}$ that assigns a non-negative real value to every edge, such that for every vertex $v$ except $s$ and $t$, the total flow into $v$ is equal to the total flow out of $v$, or more formally,
$
    \sum_u \phi(u\mathord\to v) = \sum_w \phi(v\mathord\to w).
$
(This equality is usually called the conservation constraint.)

It's useful to think of a flow as a weighted sum of paths from $s$ to $t$.  In particular, suppose $P$ is a set of simple $(s,t)$-paths, and for any edge $e$, let $\#P(e)$ denote the number of paths in $P$ that use edge $e$.  Then the function $\#P$ is a flow.

In most traditional flow problems, each edge $e$ also has a capacity $c(e)$, and a flow is feasible if and only if $\phi(e) \le c(e)$ for every edge.  However, in your case, you want to force the flow to use every edge; so instead, you have a demand constraint $\phi(e) \ge 1$ at each edge.

Finally, we can define the cost of a flow $\phi$ to be the sum of the flow values: $\$(\phi) = \sum_{e\in E} \phi(e)$.  Possibly up to some off-by-one errors, your goal is to find a flow $\phi$ of minimum cost that satisfies all the conservation and demand constraints.

This problem can be solved in polynomial time using textbook flow algorithms.  Your specific problem is unlikely to appear in any textbook, but all the necessary components are described in Kleinberg and Tardos' Algorithm Design.  You may also find my lecture notes on flow algorithms (groundwork, basic algorithms, and extensions) helpful.


Find and prove a linear algorithm that identifies all cycles and the length in a graph where each vertex has exactly one outgoing edge

Unfortunately, your algorithm is not correct.
Let us call a directed graph where each vertex has exactly one outgoing edge a unique-outgoing graph.
What does a unique-outgoing graph look like?
It consists of some directed tree and some directed cycles, all of which are disjoint except that every root of the trees is also a vertex of some cycle. Or, it looks like a collection of directed cycles with some directed trees attached to them.

Here is an illustration,  which corresponds to the array $[5, 12, 3, 10, 9, 2, 3, 14, 14, 7, 2, 14, 5, 11, 4]$. There are two connected components in that graph. One component has the cycle of vertices 2, 3, 10 with two attached trees, the tree with vertices 2, 5, 0, 12, 1 and the tree with vertices 3, 6. The other component has the cycle of vertices 4, 9, 7, 14 with one attached tree, which has vertices 14, 8, 11, 13.
A simple algorithm
Here is the pseudocode, which is about as simple as possible.
Input: Array $arr[0], arr[1], \cdots, arr[n-1]$, such that the graph has the edge $(i, arr[i])$.
Procedure:

$round\leftarrow 0$.
Create array $first\_visited$ of $n$ zeros, where $first\_visited[i]$ will record the round at which $arr[i]$ is first visited. No element is visited at round 0.
Loop $i$ from 0 to $n-1$:
If $first\_visited[i]$ is 0:

Increase $round$ by 1.
$index\leftarrow i$
Loop the following as long as $first\_visited[index]$ is zero, i.e., $arr[index]$ is not visited.

$first\_visited[index]\leftarrow round$
$index \leftarrow arr[index]$

Now $first\_visited[index]$ must be non-zero.
If $first\_visited[index]$ is equal to $round$, a new cycle has been found! Record (or output) the cycle as well as its length by chasing the elements starting from $index$. Otherwise, do nothing.

When we run the algorithm on the aforementioned array, we will visit

0, 5, 2, 3, 10, 2 in round 1. The cycle 2, 3, 10 of length 3 will be recorded.

1, 12, 5 in round 2.

4, 9, 7, 14, 4 in round 3. The cycle 4, 9, 7, 14 of length 4 will be recorded.

6, 3 in round 4.

8, 14 in round 5.

11, 14 in round 6.

13, 11 in round 7.

Basically, the algorithm loops over all elements from index 0 to $n-1$. From each unvisited element, it makes an inner loop where it chases the next element via its outgoing edge, until it reaches a visited element. Each inner loop constitutes a round of chasing, during which each newly-visited element will be associated with the number of rounds happened so far.
The algorithm runs in $O(n)$ time with $O(n)$ space.
On your algorithm

I'm thinking of marking the vertices I have traversed, and every time a vertex points back to the ones that I've traversed I count one cycle and move on to the next unvisited vertex

You have got the basic idea. However, a new cycle might not be found when a vertex points back to a vertex that has been traversed, even if it is not part of any confirmed cycles. For example, consider the moment when your algorithm have visited 0, 5, 2, 3, 10, 2, 1, 12 and then 5 again. Vertex 5, although revisited, is not part of any cycle.
To ensure that a new cycle will be found when you revisited a vertex, the first visit to that revisited vertex must happen after the visit to the vertex i in your algorithm. That is why the variable $round$ is introduced in the above algorithm, which is, in fact, the only critical difference between the two algorithms.

Exercises
Here are a couple of exercises that help prove the above algorithm is correct.
Exercise 1. Show that there is exactly one cycle in each connected component.
Exercise 2. Prove the following invariant of the above algorithm. At the start of step 3.1, all visited vertices and edges so far form a unique-outgoing graph.


(Leetcode) Combinatorial Sum - How to generate solution set from number of solution sets?

Suppose that the candidates are $x_1,\ldots,x_n$ and the target is $T$. I'm assuming all candidates are positive. If $T < 0$ then there are no solutions. If $T = 0$ then the only solution is the empty solution. Otherwise, there are two kinds of solutions:

$x_1$ together with a solution for $T - x_1$ using all candidates.
A solution for $T$ using the candidates $x_2,\ldots,x_n$.

Using this, you can easily write a recursive procedure that generates all solutions.


Collection of meta-reductions in theory of $\mathrm{NP}$-completeness

NODE- & EDGE- DELETION

Here, I start with some links on meta-result on the hardness of node- and edge- deletion to satisfy $\pi$ property for various classes of property $\pi$.

https://dl.acm.org/citation.cfm?id=804355
https://www.cs.umd.edu/~gasarch/TOPICS/ramsey/hered.pdf
https://www.sciencedirect.com/science/article/pii/0166218X83901014


Constructing a NFA that accept complement of language L of another NFA

Is there a general way to do it? The answer is yes: one way to do it is to find a DFA that accepts $L$ (for example with the powerset construction), make it complete (by adding a sink state), and swap final states and non-final states. The automaton is deterministic, but it is a special case of non deterministic.
Is there a polynomial time way to do it? I don't know, since the construction above can be exponential time in the number of states (because of the powerset construction).


Augmenting AVL tree to calculate sum of subtree

Your solution is traversing the whole subtree on each call to subSubtree so it is actually $O(|T|) \neq O(\log n)$ where $|T|$ is the length of the subtree. If I query the root of the tree it will go over every node, so complexity is $O(n)$.
If you keep the sum of the subtree while modifying it (insertions/deletions) then the pseudo-code will look like:
calculateSum(key):
    node = Search(key) // assuming I have a search function in O(log n)
    return node->size

Search can be implemented in $O(\log n)$ and getting the size is $O(1)$ since it is stored on the node itself, hence the overall complexity will be $O(\log n)$.


Maximal difference of height between two leaves in an AVL tree

We consider Fibonacci tree ([TAOCP3, Knuth98, Sect. 6.2.1]) and compute the maximal height difference in it.

A Fibonacci tree of order $k$ which is constructed recursively (see an Fibonacci tree of order 6 in the figure below; also from TAOCP):

  If $k = 0$ or $k = 1$, the tree is simply a single node.
  If $k \ge 2$, the tree has a left subtree of order $k-1$ and a right subtree of order $k-2$.

It is easy to verify that a Fibonacci tree is also an AVL tree.

From the figure above, we observe that the two leaves at the leftmost $l$ and at the rightmost $r$ differ most by heights ($H_l, H_r$ among all pairs of leaves. We can compute the height difference as follows.

A Fibonacci tree of order $k$ has $n = F(k+2)-1 \sim \Phi^{k+2}$ nodes in total, where $\Phi$ is the golden ratio.

$$H_l - H_r = k \text{ (leftmost path; decrease by 1}) - k/2 \text{ (rightmost path; decrease by 2}) = k/2 \text{ (maybe floor or ceiling functions here; I omit the details)}.$$

Because $n = \Phi^{k+2}$, we have $k/2 = \log_{\Phi} \sqrt{n} - 1$.


Algorithm to find all 2-hop neighbors lists in a graph

The question really depends on what is the precise definition of a 2-hop. If by a 2-hop you mean the set $$hp(v) = \{ u \mid \mbox{there is a path of length 2 between u and v}\},$$ then the current answer is no, you cannot do it faster than $O(n^{\omega})$ where $\omega$ is the usual constant associated with the complexity of performing the matrix product.

Why? For every vertex $v$ check if $v$ is adjacent to vertex in $hp(v).$ If this is the case then you have found a triangle in your graph. Moreover the graph is triangle free if you do not find a vertex $v$ with this property.

The currently best known algorithm for testing if a graph is triangle-free has time complexity $O(n^{\omega}).$


Why does Min-Max algorithm delays a good move indefinitely?

In a game-theoretical sense, both of the moves you describe are equally good in the scenarios you describe, so the algorithm is "correct" in that it doesn't matter which move it picks -- you do not explicitly encode a preference for faster wins (or faster gains of $+100$) over slower scores.

Introducing a discount factor to explicitly encode such a preference, as described in ryan's answer, can be a solution... but it's not very common in game AI / minimax / alphabeta search literature, and it can also be detrimental in slightly different scenarios. For example, if we can get a score of $+100$ in one ply, or a score of $+101$ in the second ply, we would generally prefer the path leading to that delayed $+101$... but a common choice of a discount factor $\gamma = 0.9$ would lead us to prefer the suboptimal path. Note that this does not just hold for the example of $\gamma = 0.9$; we can come up with such a counterexample for any value $0 \leq \gamma < 1$ that will cause the solution with discount factor to break down and lead to suboptimal behaviour.

A more robust solution is a combination of iterative deepening with move ordering. In practice, we rarely use a plain minimax search with a predetermined depth limit. In practice, we usually do something like:

Start out with a $1$-ply search
Proceed to run a $2$-ply search afterwards if we still have time
Proceed to run a $3$-ply search if we still have time
etc.

This is referred to as iterative deepening. Now, when we start a new search (with an increased depth limit), a common trick is to first re-order the moves at the root node based on the scores found in the previous search (with the lower depth limit).

Now, imagine that we apply this process to the scenario described in your question. The Qxb8 line of play will first be discovered to give a $+100$ score in one of the first iterations (shallow searches). Based on this, we will sort that Qxb8 line to be searched before the Qa1+ line when moving on to the next iteration with a deeper search. Both lines will then be discovered to have the same $+100$ score, but now, due to clever move ordering (not specific to this case, but clever move ordering in general thanks to iterative deepening!), the shorter line will have been searched first and be the preferred line of play.

Note that the "trick" with iterative deepening + move ordering is not just useful to solve the issue highlighted in this question, but in general can also significantly increase the number of prunings that can be achieved when we extend the basic minimax algorithms with techniques like alpha-beta pruning.


Is there a way to calculate exactly how many binary trees are possible if only one of the preorder, inorder and postorder traversals is given?

Your question probably assumes that the nodes of the tree all contain different values. If we have a tree with $n$ nodes all of whose have the same label $x$, then we can't tell what tree we're looking at by observing the traversals, as we always get just a series of $x$'s, independent of what the tree shape is or what traversal we use. So I assume the labels are all different.

Use the traversal to generate a list of all the elements of the tree $[x_1, \ldots, x_n]$. Now, which trees are possible with this particular traversal? Pick any tree with $n$ elements and place the labels $x_i$ into the nodes so that for that tree you'll get them back in the order $[x_1, \ldots, x_n]$. This shows that, if we only have one of the traversals available, any tree shape is possible, as long as it has the correct number of nodes $n$. So the answer is that there are $C_n$ such trees, where
$$C_n = \frac{1}{n+ 1}{2 n \choose n}$$
is the $n$-th Catalan number.


Natural candidates for the hierarchy inside NPI

I've found a nice problem called ModularFactorial. Take as input two $n$-digit integers $x$ and $y$, and output $x! \mod y$. This problem is at least as hard as Factoring and not know to be hard for FNP. The reference is the recent (and beautiful) book by Cristopher Moore and Stephan Mertens The Nature of Computation, page 79.


Yes, this is absolutely still considered a genetic algorithm. In fact, it is quite common to experiment with various strategies of obtaining an initial population. As you say, it is reasonable to start with a completely random population unless you have a reason to try something else.

Whether this is a good way to go is anybody's guess, really. It depends heavily on your problem and problem instances. Give it a try and see how it compares to a random initial population. Further, whether this is a modification that is considered fine, trust your advisor more than random people on the internet.


Decide whether an $n$-bit positive integer is composite

NP doesn’t look at how hard it is to find a certificate (in this case a factor), just at how hard it is to test a certificate that claims to prove the answer is “yes”.

So it doesn’t matter how hard it is to find a factor, just that given a factor of an n-bit number, you can easily verify that it is a factor in $O(n^2)$. Or a bit faster with more effort. So “is x composite” is quite obviously in NP.

The opposite, “is x a prime”, has been shown to be in NP, but that is absolutely not easy to show. Basically you have to show that for any n-bit prime p, there is a certificate that allows us to verify in polynomial time time that p is prime.


The language of non-extendable strings of a regular language is regular

The definition does not ask for a maximal length string in $L$ but it looks for the strings that cannot be extended into a longer string in the language: $x\in L$, but no $xy \in L$ for nonempty $y$.

This means that repetitions are no problem. For $L = a^*b$ in fact $\mathrm{Max}(L) = L$ as no string can be extended to a longer string in $L$. But for $L = ba^*$ we have $\mathrm{Max}(L) = \varnothing$,as every string can be extended.

If you start with a (deterministic!) FSA, you can easily see which strings can be extended, and which not. How?


There are about $2^{\log^2n}$ possible configurations, and $2^{\log^2n} = n^{\log n}$, which is not polynomial (it's "quasipolynomial"). So, no, you can't claim that $\mathrm{DSPACE}[\log^2 n]\subseteq \mathrm{P}$.


I have a problem understanding a solution for number theory problem from SPOJ

A number is prime if it has no non-trivial factors. In order to check whether a number $n$ is prime, it suffices to check that it has no factors in the range $2,\ldots,\sqrt{n}$. In order to find all primes in $[a,b]$, we go over all primes in $2,\ldots,\sqrt{b}$ (using a list prepared ahead of time), and for each such prime $p$, we mark off all multiples of $p$ in $[a,b]$. After going over all such primes, the unmarked numbers in $[a,b]$ are prime.

How do we mark off all multiples of $p$ in $[a,b]$? We mark off the first multiple $p \lceil a/p \rceil$ (computed in a funny way in the code), if it happens to fall inside the interval (but not if this multiple happens to be $p$ itself!), and then we mark off the remaining multiples, by jumping in steps of $p$ until we fall off the interval $[a,b]$.


Why the Goemans-Williamson's MAX-CUT algorithm relax the variables to vectors of $n-$dimension on unit sphere?

The MAX-CUT algorithm relies on semidefinite programming, a convex optimization problem which can be solved in polynomial time. What you solve directly is the semidefinite program

$$
\begin{align*}
& \max \sum_{ij} w_{ij} \frac{1-a_{ij}}{2} \\
s.t. \quad& (a_{ij})_{i,j=1}^n \text{ is positive semidefinite} \\
& a_{ii} = 1 \text{ for all $i$}
\end{align*}
$$

Given a solution for this program, you can extract the vectors using Cholesky decomposition.

The problem you are interested in is different:

$$
\begin{align*}
& \max \sum_{ij} w_{ij} \frac{1-\langle v_i, v_j \rangle}{2} \\
s.t. \quad& v_i \in \mathbb{R}^d \\
& \|v_i\|^2 = 1
\end{align*}
$$

When $d = 1$, this is just MAX-CUT. When $d$ is constant, optimizing over $\{v_i \in \mathbb{R}^d : \|v_i\| = 1 \}$ is likely NP-hard. When $d = n$, this can be solved using the semidefinite program described above. This is why we allow the dimension to be unbounded.

If you could force the dimension to be small, then you could improve the approximation ratio of the algorithm, see for example Rounding Two and Three Dimensional Solutions of the SDP Relaxation of MAX CUT by Avidor and Zwick. Assuming the unique games conjecture, however, the approximation guarantee of the Goemans–Williamson algorithm is tight. This shows that even in the particular case of MAX-CUT, it is likely that finding a low-dimensional solution cannot be done efficiently.


show that in every infinite computably enumerable set, there exists an infinite decidable set

Here is one possible approach. Since $L$ is c.e., there is some enumerator that outputs a list of the word in $L$: $w_1,w_2,\ldots$.

Let $D$ consist of all words $w_i$ which are longer than all words appearing before them. I claim that $D$ is infinite. If not, let $w_m$ be the last word in $D$. Then all other words have length at most $|w_m|$. However, this contradicts the infinitude of $L$.

Furthermore, $D$ is decidable. Given a word $w$, run the enumerator for $L$, and halt whenever one of the following events happen:

If $w_i = w$, output Yes.
If $|w_i| > |w|$, output No.

Since $L$ is infinite, this algorithm will eventually stop.


Is the $k$P$k$N-3SAT problem NP-complete?

1) 2P2N-3SAT is NP-complete

(Edit to take into account all comments below)

Take a 2P1N-SAT instance, check the all-1 vector is not a model, then add the clause with all variables negated to the formula to transform it into a 2P2N-SAT instance.

For each 1-clause $(a)$ in the new 2P2N formula, replace it by the three following 3-clauses : $(a \lor x \lor x)(\lnot x \lor y \lor y)(\lnot x \lor \lnot y \lor \lnot y)$ where $x,y$ are fresh 2P2N variables (i.e. appearing twice as positive literals and twice as negative literals).
For each 2-clause $(a \lor b)$ in the formula, replace it by the six following 3-clauses : $(a \lor b \lor x)(\lnot x \lor y \lor y)(\lnot x \lor \lnot y \lor \lnot y)(x \lor z \lor \lnot z)(z \lor t \lor  \lnot t)(\lnot z \lor t \lor \lnot t)$ where $x,y,z,t$ are fresh 2P2N variables.
Keep all 3-clauses in the formula.
For each $k$-clause ($k>3$) in the formula, transform it into a set of 3-clauses by the usual way, which does not change the number of occurences of positive (negative) literals of the taken $k$-clause, but add only extra variables which appear once as a positive literal and once as a negative literal. For each such new variable $x$, add the two following clauses to the 3-CNF formula :  $(x\lor y \lor \lnot y)$ and  $(\lnot x \lor \ y\lor  \lnot y)$ where $y$ is a fresh 2P2N variable.

All these transformations can obviously be done in polynomial time and transform the 2P1N-SAT instance into a 2P2N-3SAT instance. The NP-complete 2P1N-SAT problem is then reducible to the 2P2N-3SAT problem.

2) The extension to $k$P$k$N-3SAT can be done in the same spirit (a bit longer) to prove it is NP-complete as well.


Considering the above condition, should α derive a string beginning with a terminal in FOLLOW(A), then it becomes impossible to determine which derivation will be used to produce this symbol with lookahead limited to one symbol.

For instance, should $\mathrm{s}$ be the symbol that is both on FIRST(α) and FOLLOW(A), and $x$ the leftmost substring already parsed, then the following sequences are both possible:

$xA$ω $ \Rightarrow x$βω $ \Rightarrow^* x$ω $ \Rightarrow^* x\mathrm{s}$…

$xA$ω $ \Rightarrow x$αω $ \Rightarrow^* x\mathrm{s}$…ω

Even if the grammar is not ambiguous, you can't decide which path to take by reading just $\mathrm{s}$.


Reducing time complexity for finding all possible triplets in an array?

Finding all the triplets is in fact useless. Let $|A| = n$. Observe that each $a \in A$ appears in exactly $\binom{n-1}{2}$ triplets.

Therefore, the requested sum is just:

$$
\sum_{a \in A} \binom{n-1}{2}a = \binom{n-1}{2} \sum_{a \in A} a
$$


Weighted interval set scheduling problem

Sure, you can define any problem you want.  Effectively you would no longer seek a cover of intervals, but a cover of sets, where each set is a union of intervals.  Over a discrete set, any set can be expressed as a union of intervals.  Thus, this is equivalent to the maximum set packing problem.  Consequently, it is NP-hard.


There is a mutual recursion in two variables $f(n)$  for the $n\times 2$ grid and $g(n)$ for the $n\times 2$ grid with a single square sticking out. It does not matter where the square sticks out (first or second row) because their number of tilings is the same.

Note the trominos indeed come in pairs, but they do not need to form a $3\times 2$ block. You can place horizontal dominoes in between. Now that I look at it, it seems there is a recursion with one $f(n)$ if you look at a tromino and its matching partner. This picture suggests $f(7) = f(6)+f(5)+2f(4)+2f(3)+ \dots +2f(1)+2f(0)$. Sounds like a promising recursion to me.

If my initial computations are right, this suggests 1,1,2,5,11,24,53,117, ... which is OEISA052980. This lists another recurrence however. Would be fun if they match.

PS. Yes! Recursions are the same.
$f(n) = f(n-1) + f(n-2) + 2\sum_{k=0}^{n-3} f(k)$. Then subtract $f(n)-f(n-1) = f(n-1)+f(n-3)$. Thus $f(n) = 2f(n-1)+f(n-3)$, which is in the OEIS.


All problems about Turing machines that involve only the language that the TM accepts are undecidable

There are a few keywords in the excerpt from the said text book - non-trivial, problem, property.

Now what is a problem, assuming we are not dealing with combinatorial optimization problems,i.e. we are dealing with only questions which have an YES or NO answer to them.
When you ask a YES or NO question to an input string if the answer is YES you place it in a set $L$ and if the answer is NO you just discard it. Now this set $L$ is the language or the problem. It contains all those strings which which satisfy our YES or NO question.

  All non-trival problems about Turing machines that involve only the language that the TM accepts are undecidable

Here the author is talking about YES or NO questions (with respect to Turing machines) only involing the language that the Turing machine accepts,i.e. the Recursively Enumerable language(RE), which means that our "problem" set shall contain only RE languages. Now a trivial problem is one in which the our YES or NO question is either satisfied by all input or satisfied by none of the input. So a non-trivial problem is one which is neither empty nor it has all possible inputs.

  Rice Theorem: "Every nontrivial property of the RE languages is undecidable."

Property of RE languages is a set of RE languages having the said property.

Non-trivial property: The property is either satisfied by all concerned languages or by none.

So "nontrivial property of the RE languages" becomes the set of RE languages and it is neither empty nor it has all possible RE languages.

By the above argument we can say that the two statements are equivalent.

(In fact property and problem are the same thing, they both are set of strings after all. Now we might think that property is a set of languages, although while it is true, it is inconvenient to represent languages in a set(as languages can be infinitely long), rather what is done is instead of the language , we represent the corresponding Turing Machine with a suitable encoding)


a program discovering himself how to solve propositional calculus

If there are no quantifiers, testing validity of such formulas is equivalent to testing satisfiability of the complement of the formula.  That can be done with a SAT solver.  SAT solvers and the satisfiability problem are well-studied.  So, the minimal set of concepts needed would be: enough to solve SAT.

Statements with quantifiers are harder (QBF).  Higher-order logics are harder still.


Single pair shortest path algorithm with time a constraint

Your problem is NP-hard: The partition problem reduces to it as follows:

Let $ S = \{s_0, ... , s_{n-1} \} $ be a multiset of non-negative integers.

Construct cities $ \{ c_0, ... , c_n \} $, with each city $ c_i $ having 2 roads to $ c_{i+1} $, one with duration $ 0 $ and cost $ s_i $, the other with duration $ s_i $ and cost $ 0 $.

Then find the minimum-distance path from $ c_0 $ to $ c_n $ with total duration at most $ \frac 1 2 \sum S $.  This path has equal cost and duration iff $ S $ can be partitioned into subsets of equal sum.


Simple operations are anything that takes constant time to achieve.
The confusion is that division does not seem to take constant time, and in fact, in general, it does not. BUT!

Division and addition both take constant time if, say, you are adding two 32-bit integers together, which is usually how it goes. However, if you are adding arbitrarily large numbers, they won't really be constant-time, though sometimes I think people will treat it as if it is because the numbers are kind of assumed to not get super big.


Some questions regarding an approximation algorithm for Cardinality Maximum Cut Problem in Vazirani's textbook!

An $\alpha$-approximation algorithm $A$ for a maximization problem is an algorithm which on instance $x$ produces a solution $y = A(x)$ of value $V(y) \geq \alpha OPT(x)$, where $V(y)$ is the value of $y$ and $OPT(x)$ is the value of the optimal solution.

A tight instance for such an algorithm is an instance $x$ such that $V(A(x)) = \alpha OPT(x)$. This instance shows that $A$ isn't a $\beta$-approximation algorithm for any $\beta < \alpha$.

In some cases it is impossible to find a single tight instance, yet it is still possible to show that the algorithm isn't a $\beta$-approximation algorithm for any $\beta < \alpha$ using a sequence of solutions $x_i$ satisfying $V(A(x_i))/OPT(x_i) \longrightarrow \alpha$. Such a sequence is sometimes also called a tight instance, even though in reality it is a sequence of instances rather than a single instance.

You are also wondering what is the correct answer to the question about which upper bound you are using. Your algorithm presumably uses the trivial upper bound, which is the total number of edges. If you find an "integrality gap" instance in which the ratio between this upper bound and the maximum cut is $\alpha$, then this means that any algorithm using this upper bound cannot have an approximation ratio better than $\alpha$. In your case you can take a large clique, for example (this is actually a sequence of bad instances).

The famous Goemans–Williamson algorithm uses a better upper bound, namely the value of a semidefinite relaxation of maximum cut. Using this better upper bound, it manages to increase the approximation ratio from 1/2 to roughly 0.878, which is conjectured to be optimal.


Can a self-learning appliance be developed?

You may be thinking of some combination of online and offline learning.

Online learning only use new examples to base its learning on, and modifies the model at each step.

Offline learning looks at all available data, then fixes its model and uses that model on new data.

There is some use in creating new examples from existing ones, but this is typically done by hand, as to emulate possible variations expected to appear in actual data (and typically only if you don't have enough data). There isn't much use in automating this, as any conclusions it draws from the data will already be reflected in the model - if we add entries based on these conclusions, and in turn use these to draw new conclusions, either the conclusions will remain exactly the same (i.e. there's no point in adding them), or we'll start to lean towards conclusions not corresponding to the original data, which is not a good idea.

The only way AI can build its own personality, is if you program the potential to do so into it. There's no way AI can suddenly become sentient after playing 1000000000000 games of chess if it's only been taught to play chess and only knows about chess.


Estimating probability from generative model

Think of this as estimating a probability of some outcome, based on observations of many trials.  Suppose we flip a coin 1000 times, and it comes up heads 327 times.  What is your best estimate for the probability that the next flip will come up heads?  $0.327$, right?  You get that by dividing the number of heads by the number of trials.

What if you rolled a six-sized die 1000 times, and it came up a "one" 327 times?  What is your best estimate for the probability that it comes up "one"?  The same thing -- $0.327$, right?

It's the same here.  Each time that you generate $(s',o)$ and find that $s'=s'_0$, think of that as a trial -- the outcome of the trial is the observed value of $o$.  (Ignore all iterations where $s' \ne s'_0$; they're not even a trial.)  So, if you have a particular bin, say the bin corresponding to $o=1$, then you count the number of trials where you observed that $o$ was $1$, and divide by the total number of trials.  That's your estimate for the desired probability.


Idea: Count explicitly how many factors $2$ the numbers in $[1..n]$ contribute to $n!$.

Observe that every other number adds one (the even numbers), every fourth adds another (those divisible by four), every eighth another, and so on.
Hence, the number $\#_2(n!)$ of factors $2$ in $n!$ fulfills

$\qquad\displaystyle\begin{align*}
  \#_2(n!) &\leq \sum_{i=1}^{\log_2(n)} \frac{n}{2^i} \\
           &= n \cdot \sum_{i=1}^{\log_2(n)} \frac{1}{2^i} \\
           &= n \cdot \frac{n-1}{n} \\
           &= n-1 \;.
\end{align*}$

Therefore, $2^n$ can not be a divisor of $n!$.


Data structure for finding max, inserting and deleting in O(1) and O(n) space

Suppose we have such data structure. We can find in $O(1)$ the max, delete the max in $O(1)$ and repeat it $n$ times. Hence, we can sort $n$ numbers in $O(n)$. Therefore, constructing such data structure must take $\Omega(n\log(n))$ (like sorting, in general, can't be done better than $n\log(n)$. Hence, you might have some constraint on data).
Also, as deleting is in $O(1)$, means it must be found. Hence, Searching and Finding is in $O(1)$.

Therefore, you must know the position of each value (something like counting sort, but with this constraint that $max <= n$ to take the $O(n)$ space!). Hence, you can act like a counting sort by saving the max value in a variable besides the array, by accepting some constraint on data (not in general).


Proving Big Omega of a polynomial without limits

Define $M = \max(|a_0|/a_m, |a_1|/a_m, \ldots, |a_{m-1}|/a_m)$, and take $c = a_m/2$ and $n_0 = 2mM$. Then for $n \geq n_0$,
$$
\begin{align*}
f(n) &= a_m n^m \left(1 + \frac{a_{m-1}}{a_m} \cdot \frac{1}{n} + \cdots + \frac{a_1}{a_m} \cdot \frac{1}{n^{m-1}} + \frac{a_0}{a_m} \cdot \frac{1}{n^m}\right) \\ &\geq
a_m n^m \left(1 - \frac{M}{n_0} - \cdots - \frac{M}{n_0^{m-1}} - \frac{M}{n_0^M}\right) \\ &\geq
a_m n^m \left(1 - \frac{mM}{n_0}\right) \\ &=
c n^m.
\end{align*}
$$


$R(h)$ is not necessarily a number, it is a deterministic function of $h$. So, it would be a number if $h$ is deterministic, but if $h$ is a random variable, then $R(h)$ is also a random variable.
We consider $S \sim D^m$, a dataset that consists of $m$ i.i.d. samples, assumed to be drawn with respect to $D$. Accordingly, $h_S$ denotes the function that we end up with when we observed this fixed dataset $S$ (hence the subscript $S$).
Like you said, $R(h)$ is just a number for a given fixed $h$. However, in the case of $Pr_{S\sim D^m}(R(h_S))$, $h_S$ is NOT fixed and hence, neither is $R(h_S)$. Notice that it depends on the random dataset $S$ and as a function of a random variable, it is also a random variable.
Here is an example I just made up to demonstrate what these concepts correspond to:

Suppose you have a system that keeps spitting out pictures of animals and you want to classify them. Let's say, $\mathcal{Y} = \{\text{cat, dog, rat}\}$ and $\mathcal{X}$ is the set of all pictures that this picture generator can spit out that shows one of these three animals. Then, $D$ is defined over $\mathcal{X}$ because it describes the probability of observing a specific picture, for all possible pictures. Then, $S$ is $m$ observed pictures from this picture generator, sampled in i.i.d. fashion. These are concepts that are independent from your learning system, but only related to the nature of the problem you're dealing with.
Suppose you believe the best way to classify which animal is in a picture is to use a convolutional neural network (CNN) of a specific size and architecture and is trained using a certain algorithm. Then, you are restricting your hypothesis set $H$ as the set of all CNNs of that architecture and size that can be obtained via your specified training approach. If you instead decided to use SVMs, you would have ended up with a different $H$. Since $S$ is random, the CNN you'll obtain (i.e. $h_S$) is also random.

Notice there is an inherent randomness in $h_S$ due to the randomness in $S$, but there can be even more randomness if your training algorithm is non-deterministic. So, depending on the training approach that takes you from $S$ to $h_S$, $h_S$ can be a random variable even for a fixed $S$ (think about stochastic gradient descent).
Long story short, due to these random factors at play, $R(h_S)$ is not just a number, but a random variable.


Finding maximum subgraph with vertices of degree at most k

Let $G$ be any graph and let $k = 0$.
This problem is, as you correctly pointed out in a comment, better known as Independent Set and is famously NP-complete.
It is therefore unlikely that there is an algorithm solving your problem (which is slightly more general) in polynomial time.


Nope.  A counting PDA is more powerful than a PDA... even more powerful than a Turing machine.  It can recognize undecidable languages.

Proof: Let $L \subseteq \{1\}^*$ be an undecidable unary language.  It's easy to build a PDA that pushes one symbol on its stack per symbol on the input tape.  Then the height of the stack fully encodes the input word.  Thus its final transition can in one step decide whether the input word is in $L$, by "encoding" $L$ fully into the transition relation $\Delta$.

In retrospect, this is perhaps not too surprising.  A counting PDA is not physically realizable.  A PDA has a finite description.  A Turing machine has a finite description.  A counting PDA does not.  Thus, it's not too surprising that it might be more powerful.

Or, to put it another way, because they have a finite description, there are only countably many PDA's and only countably many Turing machines; but there are uncountably many counting PDA's.  As a result, it's not surprising that there exists a language accepted by a counting PDA that isn't accepted by any PDA (or any Turing machine) -- for this not to be the case, there would have to be some enormous equivalence among counting PDAs that map the uncountably many counting PDAs to only countably many languages.

How do we know there exists an undecidable unary language?  Well, let $L_2 \subset \{0,1\}^*$ be any ordinary undecidable language in binary.  Now map each word $x \in L_2$ to its unary encoding; this gives you a unary language $L_1$.  Then $L_1$ must be undecidable too (because the mapping is computable).  For instance, the binary word $110$ maps to the unary word $1^6$, since $110$ is the binary representation of 6.  (Strictly speaking, we must adjust the encoding slightly, to make sure that $110$ and $0110$ don't map to the same thing, but that's easy to fix up.)


Prove the following claim on Hamilton Path?

Try to prove instead (without induction) that if the algorithm returned false, there is no hamilton path.
Hint: there must be two parallel nodes. Can we reach one from the other?


How to reduce INDEPENDENT SET to INDEPENDENT SET SIZE?

There's a couple of issues to address, first is what definition of INDEPENDENT SET you are using, the "standard" definition is

INDEPENDENT SET (Decision)
Input: A graph $G$ and a number $k \in \mathbb{N}$.
Question: Does $G$ have an independent set of size at least $k$?

This is the decision version of the problem, and it should be pretty obvious how to use INDEPENDENT SET VALUE to solve it.
If you however mean the search (or optimization) version of the problem:

INDEPENDENT SET (Search / almost Optimization)
Input: A graph $G$ and a number $k \in \mathbb{N}$.
Output: An independent set $I\subseteq V$ where $|I| \geq k$.

If we're looking at the optimization version, then we have the optimization criterion "maximise $k$".
In these cases we can still use INDEPENDENT SET VALUE to solve the problem in polynomial time. What we want is an algorithm that makes a polynomial number of calls to our INDEPENDENT SET VALUE sub-routine, and at each step decides what to do with some element of the graph.
Further hints in spoilers (don't cheat! ;) ):

 Say you have a graph $G$ where the size of the largest independent set is $\alpha(G)$ Consider what happens if you delete a vertex from $G$ to get $G'$, then run the INDEPENDENT SET VALUE algorithm on $G'$ - what possible values can you get for $\alpha(G')$, and what does that mean for the vertex you deleted?


Creating a Deterministic Push Down Automata

Just like any automaton, a PDA is nondeterministic if (and only if) the transition relation is not a function, that is there are configurations that have multiple possible succeeding configurations. If this is the case for reachable configurations, this means that a non-deterministic automaton has inputs for which there are multiple computations.

Here, the transition $(\varepsilon, Z0/Z0)$ to state three may be taken even though the word has not been completely read, that is in configurations of the form

$\qquad (\alpha 1 \beta, Z0)$

you can either take transition $(\beta_1, Z0/\beta_1Z0)$ or $(\varepsilon, Z0/Z0)$ -- the automaton is non-deterministic. Of course, taking the latter always leads to rejecting the input unless $\beta = \varepsilon$, Since there is no other nondeterminism, this implies that the automaton is unambiguous.

Converting an NPDA to a DPDA is not always possible; NPDA define a properly larger language class than DPDA. Given an NPDA, checking if an equivalent DPDA exists is undecidable. And even if there is one (and you know that) there is no algorithm to find it. That is to say, there is no general, algorithmic technique for that part of your question.


What is a logical approach to developing an algorithm which can find the optimal parameters for a function which make it best fit a given data set?

The answer depends on what is your notion of "optimal parameters", and on the specific model you have in mind.

Suppose your model is $f(x,\overline{p})$, where $p$ is the parameters vector, and you wish to find the vector $\overline{p}$ which minimizes $
\sum\limits_{i=1}^n\left( y_i-f(x_i,\overline{p})\right)^2$. This problem is known as least squares fitting, and if your model $f(x,\overline{p})$ is linear, then the optimal value of $\overline{p}$ is given by ${(x^Tx)^{-1}x^Ty}$. For more complicated models, the solution might not be so easy to find analytically, and one might need to settle for approximations. One option is to use iterative methods, such as the Gauss-Newton algorithm.

There is no general way to deal with any type of error function. If for example your cost function does not allow any mistake, and your model $f$ is polynomial in the parameters, then the task reduces to solving a system of polynomial equations. Different types of error functions can take you to different areas in optimization, or even in mathematics in general.


What is the difference between an embedded system and dedicated system?

An embedded system is embedded in some larger device/system. For example, a computer used to control a car is embedded, or the microprocessor controlling e.g. a washing machine.

A dedicated system is one which is used for one task only, like file serving or running a database.

Most embedded systems are dedicated (to their specific task(s)). There isn't a clear cut definition.


Finding Regular expression for FSM with more than one final state

If we get more than one different regular expression for the same finite state machine with more than one final state, is it correct?

Rather than push the buttons mechanically, you have to understand what you're doing. Your task is to find a regular expression equivalent to a given FSM. This means that the language accepted by your regular expression has to be the same as the language accepted by the given FSM.

For every state $\sigma$ in the FSM, you can computer a regular expression $r_\sigma$ for the language $L_\sigma$ of all words upon reading of which the FSM ends up at the state $\sigma$ (this definition is valid in the deterministic case; for non-deterministic automata, it has to be slightly modified). The language $L$ accepted by the FSM consists of all words upon reading of which the FSM ends up at an accepting state. Given this data, you should be able to come up with a regular expression for $L$ using the regular expressions $r_\sigma$ for all accepting states — you just have to combine them in the correct way.


You do not need anything as fancy as Stirling. It is easy to see that $n!\cdot n < n^n$ for all $n>2$ (just compare the first two terms of $n!=1\cdot 2\cdot\ldots$ witht those of $n^n=n\cdot n\cdot\ldots$).


how to generate all spanning trees from one spanning tree

The solution is greatly presented in Knuth's book at 7.2.1.6 (see page 23)


Suppose $A[i] + A[j] + A[k] + A[\ell] = X$. If there is a way to break this sum into two non-equal parts, then the problem you mention does not occur. Otherwise, we have
\begin{align}
A[i] + A[j] &= A[k] + A[\ell] \\
A[i] + A[k] &= A[j] + A[\ell] \\
A[i] + A[\ell] &= A[j] + A[k]
\end{align}
In fact, all of these are equal to $X/2$, and this implies that $A[i] = A[j] = A[k] = A[\ell]$.
The hashtable entry for $X/2$ can only contain two of the indices $i,j,k,\ell$, say $i,j$ (it might contain fewer). The algorithm then finds the correct solution when it reaches $k,\ell$ in the second stage.


Algorithm to find slope of line with a modulus

As I understand it, the best way should just be to take the known maximum - minimum as your change in y, and the period length as the change in x (assuming the function you've described is periodic, with its domain as ℝ), and their ratio is the slope.  Since you're dealing with discrete points, you'd just need enough data to estimate the shape of two periods to solve for the period length, but more is obviously better.


Is it true that if L* is recursive, L is also recursive?

No.
Take any language $L$ over $\Sigma = \{0, 1\}$ that contains 0 and 1. Then $L^* = \Sigma^*$ (this is recursive, even regular), regardless of what $L$ might be. It could be a not even recursively enumerable language.


Explanation of O(n2^n) time complexity for powerset generation

Observe that:
$T(N) = 2T(N-1) + 2^{N-1}$
$T(1) = 2$
Note that the entire runtime, our algorithm only spends time generating more data. Therefore, our function T represents both the amount of time that the function spends running on an input of size N, and also the amount of data it generates from an input of size N.
We have $2T(N-1)$ because we first make the recursive call, and the following line makes a copy of all that data again in preparation to tack on the element we left out in the recursive call. We tack on exactly $2^{N-1}$ copies of the element we intentionally left out so that's where the last term comes from. Finally, T(1)=2 because with 1 element, we return 2 possible subsets (the entire set and the empty set).
Unrolling this recurrence we have:
$T(N)=2T(N-1)+2^{N-1}$
$\quad \quad =2(2(T(N-2)+2^{N-2})+2^{N-1}$
$\quad \quad =2(2(2(T(N-3)+2^{N-3})+2^{N-2})+2^{N-1}$
$...$
$\quad \quad = 2^N + (N-1)*2^{N-1}$
$\quad \quad = O(N*2^N)$


Just like Wojciech said, there is a bijection between calculating Huffman Code and your problem. As you can see, we can treat your problem as:

  Find binary rooted tree with $n$ weighted (weights $a_1,...,a_n$) leafs, such that sum of
  distances from leafs to root multiplied by their weight would be
  minimal.

This problem can be solved by calculating Huffman Code. Now let's see why we can use that algorithm to solve our problem. We will treat each deck as a leaf and each shuffling as an inner verticle. If all inner vertices have exactly 2 kids then such tree is a result of some shuffling procedures. We can easily prove that every Huffman Code Tree don't have inner verticles with only one child (because we could reduce that tree otherwise).

For further reading:

In this lecture note you can read prove that you can use your algorithm to build Huffman Code.


Complement of equality problem of Turing machine is recognisable or not

Let's start with the definition of recognizable:

A language $L$ is recognizable if there exists a Turing machine $T$ such that if $x \in L$ then $T$ halts on $x$, and if $x \notin L$ then $T$ does not halt on $x$.

You haven't specified what you mean by "complement of equality problem of Turing machines", so let me assume that you mean the language $L$ consisting of pairs $(T_1,T_2)$ of Turing machines which do not recognize the same language, that is, there exists $x$ such that $T_1$ halts on $x$ and $T_2$ doesn't, or vice versa.
You could try recognizing $L$ by going over all words $x$, and for which one, checking whether $T_1$ halts on $x$ and $T_2$ doesn't, or vice versa. While you can recognize that $T_1$ halts on $x$, you cannot recognize that $T_2$ doesn't halt on $x$, so this strategy fails.
To show that this language is unrecognizable, you can use a reduction from the non-halting problem. Suppose that $T$ is a Turing machine, and we want to determine whether it doesn't halt on the empty input. Construct a new Turing machine $T_1$ which erases its input and transfers control to $T$, and let $T_2$ be a fixed Turing machine which immediately halts. Then $(T_1,T_2) \in L$ iff $T$ does not halt on the empty input.


Label the four statements
$$\begin{align}
x &: C=B-1\\
y &: B=2C\\
z &: D=2B\\
w &: B=D-1
\end{align}$$
The only constraint is that $x$ must be executed before $y$ and $z$ must be executed before $w$, giving us six possible orders: $xyzw,xzyw,xzwy,zxyw,zxwy,xwzy$. Trace the execution of each of these possible orders and you'll find that $B$ can have a final value of $2$ (twice), $3$ (three cases), and $4$ (in one case).

For what it's worth, if P1 consists of $n$ assignments and P2 has $m$ assignments, the total possible orders is given by the binomial coefficient $\binom{n+m}{n}$, though that won't necessarily be the same as the number of possible final values of the shared variable $B$.


Understanding the Sipser-Gacs-Lautemann theorem

First of all, it's not clear to me that every language of the form given by your last formula is in BPP. Fortunately, we only need the reverse direction: every language in BPP can be written in this form. This will show that BPP is contained in $\Sigma_2$. Since BPP is closed under complementation, this will complete the proof.

Start with a BPP machine with some small error probability. For appropriate $k$ (depending on the error probability), a union bound shows that the formula doesn't hold. The other direction looks more complicated, and this is probably where the other results they prove come in. Basically, you have a set of good random strings covering almost all strings, and you want to cover all of them by finitely many translates of the set. Perhaps that's what these lemmas show.


The line-covering step in the Hungarian algorithm

OK, after reading this much more complicated explanation of the same algorithm, using bipartite graphs instead of matrices, I realized how to find the smallest number of rows/cols.

Given the matrix, create the "graph of zeros" - a bipartite graph where the rows are on one side and the cols are on the other side, and there is an edge between row and column iff there is a zero in their intersection. Then, our problem becomes finding a smallest vertex covering of this graph.

Based on Koenig's theorem, a smallest vertex covering in a bipartite graph can be found using any algorithm for finding a largest matching in the graph, in polynomial time.


BosonSampling: $\# P \subseteq FBPP^{{NP}^{\mathcal{O}}}$ implies $P^{\#P}\subseteq BPP^{{NP}^{\mathcal{O}}}$

I'm not an expert, and I have one blank space in my answer, hope someone might fill it in.

  $FBPP$ is the class of search problems $R = (B_x)_{x\in\{0,1\}^*}$ for
  which there exists a probabilistic polynomial-time algorithm $A$ that, given $\langle x, 0^ {1/\varepsilon}\rangle$ as input, produces an output $y$ such that $Pr [y \in B_x] ≥ 1 − \varepsilon$, where the probability is over $A$’s internal randomness.

Suppose that $L$ is a $\# P-$hard problem, and $L \in FBPP^{NP^{\mathcal{O}}}$. Then, $$P^{\# P} \subseteq P^{L} \subseteq P^{FBPP^{NP^{\mathcal{O}}}} \subseteq BPP^{NP^{\mathcal{O}}}$$

The second inclusion is clear. The first inclusion: suppose $L_1 \in P^{\# P}$. It means that there exists some polynomial algorithm $\mathcal{A}$ which makes queries to some functions $f_1, f_2, \ldots$ from $\#P$. By the definition of $\#P-$hard problems, $f_i \in FP^{L}$, where $FP$ is the class of polynomially computed functions $f:\{0,1\}^*\rightarrow \{0,1\}^*$. It means that every $\mathcal{A}$'s query to $f_1, f_2, \ldots$ can be replaced by a polynomial program with (at most polynomial) number of queries to $L$, or simply speaking  $\mathcal{A}$ is equivalent to some polynomial program $\mathcal{B}$ with queries to $L$. We've shown
$$P^{\#P} \subseteq P^{FP^{L}} = P^L$$
We see that $P^{FP}$ can be replaced by $P$.

The third inclusion: again, the same trick: here $P^{FBPP}$ turns to $BPP$. Suppose $L_2 \in P^{FBPP^{NP^{\mathcal{O}}}}$ and $\mathcal{A}$ is the corresponding algorithm for $L_2$. $\mathcal{A}$ makes at most $p(n)$ queries to the probabilistic polynomial programs $A_1, A_2, \ldots$ which solve some search problems. $\mathcal{A}$ uses randomness, but always gives the right answer. One can supposedly make $A_1, A_2\ldots $ a part of $\mathcal{A}$; the resulting probabilistic polynomial algorithm $B$ with queries to $NP^{\mathcal{O}}$ never errs and belongs to $BPP^{NP^{\mathcal{O}}}$.

The only doubt that I have here is that there might be a polynomial number of queries to different functions $FBPP$, and $\mathcal{B}$ is supposed to know all the algorithms for them. It is widely known that if $\mathcal{C}$ is a complexity class with a complete problem $\mathcal{L}$, then $A^{\mathcal{L}} = A^{C}$ for class $P$. However, $BPP$ doesn't have complete problems, and I'm not sure about $FBPP$.


Find longest path between two disjoint sub-sets of vertices $V_1, V_2 \subset V$ of a Graph

Hopefully not giving too much away: You need to add only two nodes.


Algorithms and machines are not defined in your question and I don't think they are needed to ask what you want to ask.

Complexity classes are defined using Turing machines. That is their definition. If you want to prove anything you have to use these definitions. Anything about any other model is unrelated unless you prove some correspondence between that model and Turing machines.

Let me add that there is a hypothesis that says that "efficient" "computation" in any "reasonable" "machine" will capture the same number theoretic functions. However it is not a provable statement unless one defines the quoted terms. We can prove it for many machines but not all machines. Being Turing machine equivalent is not sufficient, we want them to be Strongly so, i.e. we should be able to simulate those machines with Turing machines and vice versa efficiently. The nice thing about $\mathsf{P}$ and $\mathsf{NP}$ is that they are very robust classes, i.e. small and big differences in machine models does not change the class. However it is true all the time. For example, I can define a simple new model of computation where I have an basic operation that in constant time solves a problem that is unsolvable in $\mathsf{P}$. Then it is obvious that this model will not be strongly equivalent to Turing machines.

The example above was an artificial one. However right now we have a model of computation that seems closer to efficient computation in practice than polynomial-time Turing machines: bounded-error probabilistic/randomized Turing machines, efficient algorithms in that model are referred to as $\mathsf{BPP}$.

Many experts believe that $\mathsf{BPP}=\mathsf{P}$ but we are far from proving it.

We have another model of computation which some experts expect to become practicable in future: quantum Turing machines, efficient algorithms in that model are referred to  as $\mathsf{BQP}$. We don't know if it is different from $\mathsf{P}$ but some experts conjecture that it is different and more powerful than $\mathsf{P}$.

In short, if you want to prove a complexity theory result about $\mathsf{P}$ and $\mathsf{NP}$, you have to use either the original definitions using Turing machines, or first prove a correspondence between them and the classes you are using based on some other model of computation. As I mentioned above it is quite easy to create machine models where polynomial "time" in them can solve an $\mathsf{NP}$ (or even arbitrarily more difficult) problem: just add a basic operation to your machine model that solves that problem and let the "time" that operation takes to be one unit of time.


Classify an algorithm to maximize number of tips used by liquid handlers concurrently

If we focus solely on the dispensing operation, we can formulate this as a Set Cover Problem. Namely, we are given a set of tips that have already aspirated some source liquids and we are asked to minimze the number of dispense operations to fill up a given column of target vials. In this simplified set up, we aren't allowed to go back and aspirate new source liquids and we assume that the target volumes are less than the tip capacities.
To set this up as a Set Cover Problem, we treat each target vial as its own element in the universe. We associate with each configuration of the tips (e.g.: position and tip spacing) a set corresponding to the target vials that may be covered by this configuration, taking into account the aspirated fluids in each tip (i.e.: a target vial is "covered" by a tip configuration, if there is a tip that has aspirated the appropriate fluid and positioned over that vial).


use of unconditional transfer of control instruction

To implement if-then-else, when you get to the end of the "then" branch, you need to jump unconditionally past the "else" branch. The breaks in a C switch statement are also unconditional jumps.

You could probably also implement tail recursion by replacing "call" instructions with jumps.


Proof of Simple Properties About Terms, Position of Subterms and Replacement of Subterms

Item 2. If $p \in Pos(s)$ and $q \in Pos(t)$:
2.1 $(s[t]_{p})|_{pq} = t|_{q}$.
We prove by induction on the length of $p$:
Case $p = \epsilon$:
$(s[t]_{\epsilon})|_{\epsilon q} = t|_{\epsilon q} = t|_{q}$.
Case $p = ip'$:
$(s[t]_{ip'})|_{ip'q} = f(s_1, \ldots, s_i[t]_{p'}, \ldots, s_n)|_{ip'q} = (s_{i}[t]_{p'})|_{p'q}$. By induction hypothesis, $(s_{i}[t]_{p'})|_{p'q} = t|_{q}$.
2.2 $(s[t]_{p})[r]_{pq} = s[t[r]_{q}]_{p}$.
We prove by induction on the length of $p$:
Case $p = \epsilon$:
Notice that $(s[t]_{\epsilon})[r]_{\epsilon q} = t[r]_{q}$ and also that: $s[t[r]_{q}]_{\epsilon} = t[r]_{q}$.
Case $p = ip'$:
$(s[t]_{ip'})[r]_{ip'q} = f(s_1, \ldots, s_{i}[t]_{p'}, \ldots, s_n)[r]_{ip'q} = f(s_1, \ldots, (s_{i}[t]_{p'})[r]_{p'q}, \ldots, s_n)$. By induction hypothesis,
$$(s_{i}[t]_{p'})[r]_{p'q} = s_i[t[r]_{q}]_{p'}$$
and hence $f(s_1, \ldots, (s_{i}[t]_{p'})[r]_{p'q}, \ldots, s_n) = f(s_1, \ldots, s_i[t[r]_{q}]_{p'}, \ldots, s_n) = s[t[r]_{q}]_{ip'}$.
Item 3. If $pq \in Pos(s)$, then :
3.1 $(s[t]_{pq})|_{p} = (s|_{p})[t]_{q}$.
We prove by induction on the length of $p$:
Case $p = \epsilon$:
notice that $(s[t]_{\epsilon q})|_{\epsilon} = s[t]_{q}$ and also that $(s|_{\epsilon})[t]_{q} = s[t]_{q}$.
Case $p = ip'$:
$(s[t]_{ip'q})|_{ip'} = f(s_1, \ldots, s_{i}[t]_{p'q}, \ldots, s_n)|_{ip'} = (s_{i}[t]_{p'q})|_{p'}$. By induction hypothesis:
$$(s_{i}[t]_{p'q})|_{p'} = (s_{i}|_{p'})[t]_{q}$$
But $(s|_{ip'})[t]_{q} = (s_{i}|_{p'})[t]_{q}$ and thus the result holds.
3.2 $(s[t]_{pq})[r]_{p} = s[r]_{p}$.
We prove by induction on the length of $p$:
Case $p = \epsilon$:
$(s[t]_{\epsilon q})[r]_{\epsilon} = r = s[r]_{\epsilon}$.
Case $p = ip'$:
$(s[t]_{ip'q})[r]_{ip'} = f(s_1, \ldots, s_{i}[t]_{p'q}, \ldots, s_n)[r]_{ip'q} = f(s_1, \ldots, (s_{i}[t]_{p'q})[r]_{p'}, \ldots, s_n)$. By induction hypothesis:
$$(s_{i}[t]_{p'q})[r]_{p'} = s_{i}[r]_{p'} $$
and therefore we have $f(s_1, \ldots, (s_{i}[t]_{p'q})[r]_{p'}, \ldots, s_n) = f(s_1, \ldots, s_{i}[r]_{p'}, \ldots, s_n) = s[r]_{ip'}$.
Item 4. If $p$ and $q$ are parallel positions in $s$ (i.e. $p || q$), then
4.1 $(s[t]_{p})|_{q} = s|_{q}$
We prove by induction on the length of $p$:
Case $p = \epsilon$: This case can't happen, as $p$ and $q$ would not be parallel positions.
Case $ p  = ip'$:
We now prove this by induction on the length of $q$.
If $q = \epsilon$:

This can't happen, as $p$ and $q$ would not be parallel positions.

If $q = jq'$:

There are two possibilities, according to whether $i = j$ or not.
Case $i = j$:

$(s[t]_{ip'})|_{iq'} = f(s_1, \ldots, s_{i}[t]_{p'}, \ldots, s_{n})|_{iq'} = (s_{i}[t]_{p'})|_{q'}$. We have that $p'$ and $q'$ are parallel positions and thus, by induction hypothesis:
$$(s_{i}[t]_{p'})|_{q'} = s_{i}|_{q'}.$$
Since we also have $s|_{iq'} = s_{i}|_{q'}$ the result holds.

Case $i \neq j$:

Let's suppose without loss of generality that $i > j$. Then:
$$(s[t]_{ip'})|_{jq'} = f(s_1, \ldots, s_{j}, \ldots, s_{i}[t]_{p'}, \ldots, s_{n})|_{jq'} = s_{j}|_{q'}.$$
Since we also have $s|_{jq'} = s_{j}|_{q'}$ the result holds.

4.2 $(s[t]_{p})[r]_{q} = (s[r]_{q})[t]_{p}$:
Case $p = \epsilon$: This case can't happen, as $p$ and $q$ would not be parallel positions.
Case $ p  = ip'$:
We now prove this by induction on the length of $q$.
If $q = \epsilon$:

This can't happen, as $p$ and $q$ would not be parallel positions.

If $q = jq'$:

There are two possibilities, according to whether $i = j$ or not.
Case $i = j$:

$(s[t]_{ip'})[r]_{iq'} = f(s_1, \ldots, s_{i}[t]_{p'}, \ldots, s_n)[r]_{iq'} =
f(s_1, \ldots, (s_{i}[t]_{p'})[r]_{q'}, \ldots, s_n)$.
We have that $p'$ and $q'$ are parallel positions and thus, by induction hypothesis:
$$ (s_{i}[t]_{p'})[r]_{q'} = (s_{i}[r]_{q'})[t]_{p'} $$
and hence $$f(s_1, \ldots, (s_{i}[t]_{p'})[r]_{q'}, \ldots, s_n) = f(s_1, \ldots, (s_{i}[r]_{q'})[t]_{p'} , \ldots, s_n)= f(s_1, \ldots, s_{i}[r]_{q'}, \ldots, s_n)[t]_{ip'} = (s[r]_{q})[t]_{p}.$$

Case $i \neq j$:

Let's suppose without loss of generality that $i > j$. Then:
$$(s[t]_{ip'})[r]_{jq'} = f(s_1, \ldots, s_{j}, \ldots, s_{i}[t]_{p'}, \ldots, s_n)[r]_{jq'} = f(s_1, \ldots, s_{j}[r]_{q'}, \ldots, s_{i}[t]_{p'}, \ldots, s_n) = f(s_1, \ldots, s_{j}[r]_{q'}, \ldots, s_{i}, \ldots, s_n)[t]_{ip'} = (s[r]_{jq'})[t]_{ip'}.$$


$n^a = \exp(a \ln n) = \exp(a \ln n \frac{\ln 2}{\ln 2}) = 2^{\frac{a \ln n}{\ln 2}}$. Can you prove that if $h(n) = O(k(n))$ then $2^{h(n)} = O(2^{k(n)})$ ?


1/3-CNFSAT is very much similar to HALF-SAT, where instead of satisfying exactly half of the total number of clauses you are satisfying exactly one third of it. So the reduction from 3SAT is also quite similar. We reduce 3SAT instance, $\phi$, to a 1/3-CNFSAT instance as follows.

Let $z$ be a new variable not in $\phi$. Let there be $m$ clauses in $\phi$. We add $(z \lor \lnot z)$ and $2m+2$ copies of $(z)$ to $\phi$. In every exactly 1/3-satisfying assignment $z$ must be false.

Let $\phi \land (z \lor \lnot z) \land (z) \land (z) \land ... (2m+2) $ copies $...\land (z) = \phi'$. The following claim is easy to prove.

Claim: $\phi$ is satisfiable iff $\phi'$ has exactly 1/3rd satisfiable clauses.

Therfore 3SAT $\leq_P$ 1/3-CNFSAT, and hence 1/3-CNFSAT is NP-complete.


You would pick some number a, run the code, and see if you can find a pattern. There will be an obvious pattern. Then you think how you can use that pattern to find long ranges of numbers i where r ends up being 1, and long ranges where r does not end up being 1.

When you've done that, all you do is add up the number of values in those ranges of values i that end up being 1.

The best way unless you are a super genius (in which case you wouldn't be asking here) is to play around with the code, figure out its behaviour, and think about ways to take shortcuts.


can we do binary search to solve quadratic equation?

Consider the value of fx on line 6.

def solve():
    low, high=-1000,0
    while (high-low)>10e-5:
        x = (low+high)/2
        fx = 2*(x**2)-4*x-5
        if fx<0:
            high=x
        else:
            low=x

    return low

print(solve())

or

def solve():
    low, high=-1000,0
    while (high-low)>10e-5:
        x = (low+high)/2
        fx = 2*(x**2)-4*x-5
        if fx>0:
            low=x
        else:
            high=x

    return low

print(solve())


Find all sets of nodes that can be connected with a single path

Just use depth-first search. Each node you encounter in the search tree corresponds to a path from the source vertex.


Converting If-else integer equation to Linear Programming

Your condition is effectively excluding $(0,1,1)$ and $(1,0,1)$ corners of the unit cube. Thinking of it pictorially gives you a quick formulation: (i) construct the cube, (ii) chop those corners off and (iii) ensure integrality.
In (ii), the corners we want to get rid of are on the $BC$ and $AC$ planes. We can cut from the correctly aligned diagonals on those planes. However, moving in $+A$ direction, the cut should shrink and vanish at $A=1$ to include $(1,1,1)$.
\begin{align*}
&\text{(i) } 0 \leq A,B,C \leq 1  \\
&\text{(ii) }-A+B+C \leq 1, A-B+C \leq 1 \\
&\text{(iii) }A,B,C \in \{0,1\}
\end{align*}


No, the kernel does not check the page permissions on every execute. If the CPU supports the NX bit, it checks that bit.

Exactly what the CPU does with it and when probably varies between CPU manufacturers and vendors.

Modern CPUs implement a split TLB, one for instructions and one for data. The Core i7, for example, has (ignoring 2MB and 1GB pages for the moment):

L1 data TLB: 4-way set associative, 64 entries
L1 instruction TLB: 8-way set associative, 64 entries
L2 unified TLB: 6-way associative, 1536 entries

I'm not a CPU designer, so this could be wrong, but if it were me, I would check the NX bit when inserting the page table entry into the L1 instruction TLB.

There are a few things you need to consider; for example, the TLB load might be caused by speculative execution, so an exception shouldn't be raised unless instructions on that page are actually executed. But this is nothing special; it's exactly the same behaviour as you would expect if the instruction execution would cause a page fault.

There are architectures which manage TLBs in software or which allow for that possibility, most notably MIPS, Itanium, and some variants of SPARC V9. On such a platform, it is perfectly feasible for the kernel to perform the equivalent of the NX check on every instruction TLB miss.


Can a language have $\Sigma^{*}$ as its syntactic monoid?

It seems to work to take $L=\{ww: w\in\Sigma^* \text{and $|ww|$ is a power of $2$}\}$.

First, we can show that if $|u|>|v|$ then they are not equivalent.
Indeed, there is $x$ such that $|uxux|$ is a big power of $2$, say $2^{|u|+|v|}$.
Therefore, $uxux\in L$.

But then the length of $vxux$ cannot be power of $2$, because its difference to $2^{|u|+|v|}$ is only $|u|-|v|$. Therefore, if we take $y=xux$, we have $uy\in L$ and $vy\notin L$.

Now it suffices to show that words of the same length are not equivalent.
Let $u\neq v$ with $|u|=|v|$, and let $x$ such that $|ux|$ is a power of $2$ (and then so is $|uxux|$). Then you can see that $(u,v)\notin\sigma_L$ because $uxux\in L$ and $uxvx\notin L$.


What is the difference between radix trees and Patricia tries?

I found this post very helpful.

To see the difference between Patricia tries and radix trees, it is important to understand:

The notion of radix, since Patricia tries are radix trees with radix equal to 2.
The way keys are treated: as streams of bits. Keys are compared $r$ bits at a time, where $2^r$ is the radix of the trie.

Suppose that we insert the keys smile, smiled, and smiles (in this order) in a Patricia trie. The binary representation of these keys is the following:

Note that smile is a prefix of smiled, and, analyzing the binary representation, we can see that the first bit that differs (from left to right) is 0 (highlighted in red in the second row); for this reason, smiled will be the left child of smile. Similarly, smiles will be the right child of smiled because they share the same prefix up to a bit whose value is 1 (highlighted in red in the third row). The resulting Patricia trie after inserting the three keys is the following:

If the radix was, for example, 4, then internal nodes could have, at most, four children (with their edges labeled 00, 01, 10, and 11, respectively). In this case, keys would be compared by chunks of 2 bits, and not 1 (as in Patricia tries).

  In what ways are the two data structures different?

To my understanding, the only difference is the radix, which is equal to 2 in the case of Patricia tries. This value can be any power of 2 in regular radix trees.

  Is the difference only in the way comparisons are made when doing look-ups?

In both data structures, the comparison operation is bitwise. However, the number of bits that are checked atomically varies according to the radix. In the case of Patricia tries, bits are compared individually (since radix = 2). This is not necessarily the case in radix trees. In general, bits are checked in chunks of size $\log_2{R}$, where $R$ is the radix of the trie.

  How can each node be a "two-way branch"? Shouldn't there be at most ALPHABET_SIZE possible branches for a given node?

The radix establishes the maximum number of children that the nodes of a radix tree can have. For example, when radix = 2, each node can have at most two children. This is the case of Patricia tries (also known as binary radix trees).

  Are radix tries typically implemented as Patricia tries (and, hence, often considered the same)? Or can no such generalizations be made?

To be honest, I do not have an answer for this question. It seems that both data structures were proposed around the same time by different authors. For historical reasons that I am unaware of, both terms still live today.


Is the unsolvability of the N-Body Problem equivalent to the Halting Problem

There is some (somewhat scattered) research into the undecidability of the N-body problem from physics (in line with general study of undecidable phenomena in classical and quantum physics), which asks about calculating future trajectories or orbits of objects all subject to $n^2$ gravitational interactions; it has been studied for centuries including by e.g. Newton and Gauss. It basically reduces to a large array of differential equations and such systems have been proven to contain undecidability scenarios. However, this is a somewhat unusual crosscutting area of physics and mathematics that is not widely cited in either field and there do not seem to be widely cited single references either.

See e.g.

Church’s thesis meets the N-body problem / Smith
On an Undecidable Problem Related
to Difference Equations with Parameters / Abramov
Decidability and Undecidability in Dynamical Systems 2.2.2 n-body problem / Hainry


Efficiently convert an NFA with multiple $\varepsilon$ edges and accepting states into a regular expression

State elimination method is a good technique, if used properly.

Solving $f_2$ can be done directly from the given automaton.
$$ f_2 = ( s \rightarrow q_1 \rightarrow f_2 + s \rightarrow q_2 \rightarrow f_2 + s \rightarrow f_1 \rightarrow f_2)^+ $$
( Overall Kleene + due to $(f_2,\epsilon) \rightarrow s$)
$$ f_2 = (a\cdot a^*\cdot a + a\cdot b^*\cdot a + (a\cdot c^*)^+\cdot c)^+ $$
This can be rearranged as
$$ f_2 = (a\cdot a^+ + a\cdot b^*\cdot a + (a\cdot c^*)\cdot (a\cdot c^*)^*\cdot c )^+$$
$$ = ( a \cdot ( a^+ + b^*\cdot a + c^*\cdot (a\cdot c^*)^*\cdot c) )^+ $$

Similarly, $f_1$ can be solved directly from the given automaton as follows
$$ f_1 = ( s \rightarrow q_1 \rightarrow f_2 \rightarrow s  + s \rightarrow q_2 \rightarrow f_2 \rightarrow s)^* \cdot s \rightarrow f_1 \cdot (\epsilon + c \cdot \epsilon \cdot f_1) $$
$$ = ( a \cdot a^+ + a\cdot b^* \cdot a )^* \cdot (a\cdot c^*)^+ \cdot ( \epsilon + c \cdot \epsilon \cdot f_1) $$

$( \epsilon + c \cdot \epsilon \cdot f_1)$ represent the two possible transitions from $f_1$. If the input has been completed scanned, stop at $f_1$. If not, move to $f_2$ using $c$, then move to $s$ using $\epsilon$. Then start scanning for $f_1$ again.

This recursive relationship can be solved by taking
$$ r = ( a \cdot a^+ + a\cdot b^* \cdot a )^* \cdot (a\cdot c^*)^+$$
Then $f_1$ becomes,

$$ f_1 = r \cdot ( \epsilon + c \cdot f_1)$$
$$ = r \cdot ( \epsilon + c \cdot ( r \cdot ( \epsilon + c \cdot f_1) ) )$$
Unravelling this recursion gives us,
$$ f_1 = r + r \cdot c \cdot r + r \cdot c \cdot r \cdot c \cdot r + \space... $$
$$ = r \cdot ( c \cdot r )^*$$


How does worst-fit memory allocation react when encountering contiguous empty memory blocks?

You have to assume that the blocks are what they are; if they can be coalesced into larger blocks, then this has already happened (ergo, perhaps the blocks that you have before you are not in fact adjacent in memory; they are an abstract list!) So, in short, there is no cumulative hole which spans multiple blocks.

So worst fit just walks the list of free blocks that it knows about and finds the largest block and takes from there.


When did polynomial-time algorithm become of interest?

Since this question was reopened and made more explicit, I would like to convert my comment into an answer. Now the OP wants to understand

  why and when polynomial algorithms became of interest.

I especially focus on the sub-question:

  When did people realize the role and importance of efficient versus non-efficient algorithms?

Because algorithms, in its general terms, have existed since ancient times, it is hard to identify the person who is the first to highly praise the polynomial algorithms(, and when and why). However, there is a famous person who has explicitly advocated the polynomial algorithms. It is Jack Edmonds, in the paper Paths, Trees, and Flowers; 1965.

In Introduction, the author claims

  We describe an efficient algorithm for finding in a given graph a matching of maximum cardinality.

Then in the second section titled "Digression", the author

  An explanation is due on the use of the words "efficient algorithm".

Then come the explanations:

  There is an obvious finite algorithm, but that algorithm increases in difficulty exponentially with the size of the graph. It is by no means obvious whether or not there exists an algorithm whose difficulty increases only algebraically with the size of the graph.

  When the measure of problem-size is reasonable and when the sizes assume values
  arbitrarily large, an asymptotic estimate of $\ldots$ the order of difficulty of an algorithm is theoretically important.

  For practical purposes the difference between algebraic and exponential order is often more crucial than the difference between finite and non-finite.

  However, if only to motivate the search for good, practical algorithms, it is important to realize that it is mathematically sensible even to question their existence. For one thing the task can then be described in terms of concrete conjectures.

ADDED: I have just happened to found a third-party confirmation that it was Jack Edmonds who originally advocated the polynomial algorithms.

The following is quoted from Section 2.18.1 of the book "Applied Combinatorics (second edition)" by Fred Roberts and Barry Tesman.

  A generally accepted principle is that an algorithm is good if it is polynomial. This idea is originally due to Edmonds [1965].