Hoare logic - total correctness of loops

They are equivalent, in the sense that every time you can apply the textbook rule you can also apply your own rule, and vice versa. The invariant for the two rules is similar, but not the same.

Converting a textbook rule instance into an instance of your rule

Suppose we have an application or your textbook rule. I.e., we have found some $\texttt{I}$ for which:

$\texttt{I} \Rightarrow \texttt{V} \geq 0$ together with $[\texttt{I} \land \texttt{C} \land \texttt{V} = v_0] \,\texttt{S} \, [\texttt{I} \land \texttt{V} < v_0]$

Then, thanks to the implication above, we also have $\texttt{I} \iff  \texttt{I} \land \texttt{V} \geq 0$. Using rule PrePost, we can rewrite the invariant into its equivalent, and we get an application of your rule:

$[\texttt{I} \land \texttt{C} \land \texttt{V} \geq 0 \land \texttt{V} = v_0] \, \texttt{S} \, [\texttt{I} \land \texttt{V} \geq 0 \land \texttt{V} < v_0]$

Here, we use the same invariant as in the textbook rule.

Converting an instance of your rule into a textbook rule instance

Now, for the converse direction. Suppose we have found $\texttt{I}$ for your rule:

$[\texttt{I} \land \texttt{C} \land \texttt{V} \geq 0 \land \texttt{V} = v_0] \, \texttt{S} \, [\texttt{I} \land \texttt{V} \geq 0 \land \texttt{V} < v_0]$

Now, we can't assume $\texttt{I} \Rightarrow \texttt{V} \geq 0$, so we can't use $\texttt{I}$ for the textbook rule. However, we can use as a new invariant $\texttt{I}' := \texttt{I} \land \texttt{V} \geq 0$. We trivially have $\texttt{I}' \Rightarrow \texttt{V} \geq 0$ by construction (*). Further, from the hypothesis

$[\texttt{I} \land \texttt{C} \land \texttt{V} \geq 0 \land \texttt{V} = v_0] \, \texttt{S} \, [\texttt{I} \land \texttt{V} \geq 0 \land \texttt{V} < v_0]$

we can obtain (by PrePost)

$[\texttt{I}' \land \texttt{C} \land \texttt{V} = v_0] \, \texttt{S} \, [\texttt{I}' \land \texttt{V} < v_0]$ (**)

Properties (*) and (**) are exactly what we need to apply the textbook rule.


Hanoi tower with forbidden direct move from source to destination

Notation
Let's denote least number of moves needed to move $n$ disks from column $i$ to column $j$ with $T_{ij}$. Let $A$ be the source and $C$ be the destination column.

Recurrence relations
We can say the followings about each $T$:
\begin{equation}
T_{AC}(n)=T_{AC}(n-1)+1+T_{CA}(n)+1+T_{AC}(n-1)
\end{equation}
To move $n$ disks from source to destination, we first have to move the top $n-1$ disks to column $C$ and then move the last one to Column $B$, Then return the $n-1$ disks to $A$ so as to free up destination column, then move the biggest disk to $C$ and once again move the $n-1$ disks to $C$. It's easy to see that this is the optimal set of operations. This equation can be written as:
\begin{equation}
T_{AC}(n)=2T_{AC}(n-1)+2+T_{CA}(n-1)
\end{equation}

For other $T$s we have a different situation:
\begin{equation}
T_{CA}(n)=T_{CB}(n-1)+1+T_{BA}(n-1)\\
T_{CB}(n)=T_{CA}(n-1)+1+T_{AB}(n-1)\\
T_{BA}(n)=T_{BC}(n-1)+1+T_{CA}(n-1)\\
T_{AB}(n)=T_{AC}(n-1)+1+T_{CB}(n-1)\\
T_{BC}(n)=T_{BA}(n-1)+1+T_{AC}(n-1)
\end{equation}

Solving the system of recurrence relations
Let's start with $T_{AB}$ or $T_{BC}$ . We already know:
\begin{equation}
T_{AB}(n)=T_{AC}(n-1)+1+T_{CB}(n-1)
\end{equation}
We try to rewrite $T_{CB}$'s equation by replacing $T_{AB}$ from the above equation.
\begin{align}
T_{CB}(n)&=T_{CA}(n-1)+1+(T_{AC}(n-2)+1+T_{CB}(n-2))\\
&=T_{CA}(n-1)+T_{AC}(n-2)+T_{CB}(n-2)+2
\end{align}
\begin{equation}
T_{CB}(n)-T_{CB}(n-2)=T_{CA}(n-1)+T_{AC}(n-2)+2
\end{equation}

By the same method we get:
\begin{equation}
T_{BA}(n)=T_{CA}(n-1)+T_{AC}(n-2)+T_{BA}(n-2)+2
\end{equation}

It can immediately be seen that $T_{BA}(n)=T_{CB}(n)$. Then we rewrite $T_{CA}$ as:
\begin{equation}
T_{CA}(n)=2T_{CB}(n-1)+1 \Rightarrow
\end{equation}
\begin{align}
T_{CA}(n)-T_{CA}(n-2)&=2(T_{CB}(n-1)-T_{CB}(n-3))\\
&=2(T_{CA}(n-2)+T_{AC}(n-3)+2)\\
&=2T_{CA}(n-2)+2T_{AC}(n-3)+4
\end{align}

Now let's go back to the main relation, to $T_{AC}$:
\begin{equation}
T_{AC}(n)=2T_{AC}(n-1)+2+T_{AC}(n-1) \Rightarrow\\
\end{equation}
\begin{align}
&T_{AC}(n)-3T_{AC}(n-2)\\
=&2(T_{AC}(n-1)-3T_{AC}(n-3))+(T_{CA}(n-1)-3T_{CA}(n-3))=\\
=&2(T_{AC}(n-1)-3T_{AC}(n-3))+(2T_{AC}(n-4)+4)\\
=&2T_{AC}(n-1)-6T_{AC}(n-3)+2T_{AC}(n-4)+4 \Rightarrow
\end{align}
\begin{equation}
T_{AC}(n)=2T_{AC}(n-1)+3T_{AC}(n-2)-6T_{AC}(n-3)+2T_{AC}(n-4)+4
\end{equation}

There! We have reduced the system of recurrence relations to a single relation, involving only the target series. Ok, the rest is easy from here on. I leave it as an exercise to the reader! $\ddot\smile$


In your second example, you allocate space for a PrimeSet object and initialise it, then you call the countPrimeNumbers function. The PrimeSet object still exists, it still occupies memory, it probably allocated more memory, and all that memory is still occupied but not accessible. That’s a memory leak: Memory that is occupied but unusable.


Lower-order term constraints and wrong guess

First of all, the way you state the induction hypothesis is a bit strange, and it definitely doesn't prove that $T(n) = O(n)$. Assuming that the induction is on $n$, what your induction hypothesis states (more or less) is that for every $n$ there exists $C$ such that $T(k) \leq Ck$ for all $k \leq n$. The function $T(n) = n^2$ satisfies this, with $C = n$.

What you really want to do is to fix the parameters $b,c,n_0$ in advance. In other words, you want to prove
$$
 \exists b,c,n_0 \, \forall n \, \forall n_0 \leq k \leq n\colon T(k) \leq ck - bn.
$$
You first instantiate $b,c,n_0$, and then you prove only the following part by induction:
$$
\forall n \, \forall n_0 \leq k \leq n\colon T(k) \leq ck - bn.
$$
At each step of the induction, you are proving
$$
\forall n_0 \leq k \leq n\colon T(k) \leq ck - bn
$$
for the current value of $n$.

Now for your mistake. Your induction hypothesis states that for all $k \leq n$,
$$ T(k) \leq ck - bn. $$
However, in the inductive step, you only prove
$$ T(k) \leq ck. $$
Also, you only prove it for $k = n$, despite the form of your actual induction hypothesis.

Indeed, it is very strange that your inductive hypothesis gives an upper bound on $T(k)$ which depends on $n$. This is quite unorthodox. Usually the upper bound only depends on $k$. Moreover, you are not really subtracting a lower-order term: $n \neq o(k)$!

Here is what an application of subtracting a lower-order term usually looks like. Suppose that we want to prove that $T(n) = O(n)$. Then you find $b,c,n_0$ and prove the following by induction:

$$ \forall n \geq n_0\colon T(n) \leq bn - c\log n.$$

Note that there is no $k$ here, and that $\log n = o(n)$ is indeed of lower order.


Why does this mergesort variant not do Θ(n) comparisons on average?

Since you don't do any reordering while splitting, the length of array after the while loop can not be larger than the length of the longest increasing subsequence in the input. Since that one is on average about $2\sqrt{n}$ elements long¹, you keep too many elements in unsorted.

In particular, there is no $b$ so that your ansatz describes the actual number of comparisions.

Assuming that the probability distribution of the length of the longest increasing subsequence survives your splitting, a proper ansatz would be of the form

$\qquad\displaystyle C(n) = C(n - 2\sqrt{n}) + \Theta(n)$

which does not seem to solve² to $C \in O(n)$.

In fact, it's even worse since you keep the "first" increasing subsequence, not the longest (in general); consider for instance $[1,n,2,3,4,\dots,n-1]$; you keep $[1,n]$ and recurse on $[2,3,\dots,n-1]$.

On the distribution of the length of the longest increasing subsequence of random permutations by J. Baik, P. Deift and K. Johansson (1999) [via Wikipedia]
I have not solved it explicitly, but plots suggest as much.


If there is an algorithm $A$ that guesses the entire message, given an encryption, with probability of $0.2$, then it's not $(O(A) +O(n), 0.1)$-secure

Let $m_1$ be an arbitrary message. We are guaranteed that $P(A(E(k,m_1)) = m_1) = 0.2$. Averaging over all other messages, there is some message $m_2$ such that $P(A(E(k,m_1)) = m_2) \leq 0.8/(2^n-1) \leq 2^{-n}$.
Consider the following algorithm $B$: on input $x$, if $A(x) = m_2$ then output $1$, else output $0$. By assumption, $P(B(E(k,m_1))=1) \leq 2^{-n}$, whereas $P(B(E(k,m_2))=1) = 0.2$. When $n \geq 4$, the difference between the two probabilities is larger than $0.1$.


Matrix Inversion in the complexity class $P$ seen as a decision problem

Gaussian elimination is an algorithm, you can’t frame it as a problem and thus it can’t be in $P$.

But matrix inversion itself is a problem and its decision version is as follows: “does matrix $M$ have an inverse?”

Gaussian elimination then is one possible way to prove that you can always answer that question in polynomial time, therefore matrix inversion is in $P$.


Consider for Al $f_{Al} \in O(n \log n) $:
$$f_{Al}(n)=\begin{cases}n\log n, & \text{ when }n\lt 100 & \\
n  , &\text{ when }n \geqslant 100\end{cases}$$
For Bob let's take $f_{Bob}(n) \in O(n^2)$
$$f_{Bob}(n)=\begin{cases}n, & \text{ when }n\lt 100 & \\
n\log n  , &\text{ when }n \geqslant 100\end{cases}$$
Note also, that since for asymptotic relations it is only important what happens from some number to infinity, then Bob and Al are arguing in vain.


Register Allocation and Definition of Interference

Your "reading" of the definition is a little unclear. In particular, it says nothing about the values of the variables. Here's a clearer reading:

  A variable $x$ interferes with a variable $y$ if 1) they are not the
  same variable, i.e. a variable never interferes with itself, and 2) there
  is some instruction other than $x := y$ where $x$ is overwritten while
  $y$ is live at the end of the instruction (and typically also
  during, but a multiple assignment instruction like $(x,y):=(a,b)$ would be an example where variables can interfere even though $y$ is not live during the instruction).

As the book points out immediately after that definition, if $x$ and $y$ have the same value (for some stretch of code), then there is no reason they can't be held in the same register (in that stretch of code). This is what makes ignoring $x := y$ instructions valid. The analysis does not calculate the values of anything however. $x$ and $y$ interfere in $\{x := k;y := k; f(x,y)\}$ and so will be assigned different registers. For this analysis to exploit the fact that they have the same value, a prior optimization pass would need to rewrite it to $\{x := k; y := x; f(x,y)\}$.

Your definition is also incorrect. The $gen$ set of $x := k$ is empty, but certainly two variables can't share a register if one is being mutated and the other isn't. Again, as the book points out immediately after the definition, the definition is close to saying that distinct variables $x$ and $y$ can't both be live at the same time. (Both being live at the same time would be formulated as $x,y \in out[i]$.) This is a more conservative condition than yours, but it is still incorrect for the same reason. If $x := k$ is the last occurrence of $x$, and thus isn't in the $out$ set of that instruction, it still interferes with $y$.


Trying to understand the question(well spaced points ?) better

What is the correct output if the sorted array as 1, 2, 3, 4 ,5 ,6 and C is 3?

Let us try. How about (1,2,3)? Too closely together. We should push away 3. (1,2,6) looks more far apart. Hmm, (1,2) is not good. (1, 3, 6) is the best.

  What about if the sorted array as 1, 10, 11, 12, 23, 24, 25 and C is 3 ?

We should include the smallest and biggest numbers, 1 and 25. Then we should choose a number as close to the middle as possible. (1,12,25).

...

Let us analyze $\min_{i,j  \in S,i\ne j} |i-j|$. Suppose $S=\{a_1, a_2, \cdots, a_C\}$, where $a_k\le a_{k+1}$. Then
$$\min_{i,j  \in S,i\ne j} |i-j|=\min_{1\le k\lt C}|a_{k+1}-a_k|$$
since the difference between two non-adjacent numbers $a_k$ and $a_{k+t}$ must be greater than the difference between $a_k$ and $a_{k+1}$.

So the minimum difference among numbers in $S$ seems in "reverse proportion" to the difference between the adjacent or nearby numbers of the given array.

I will leave the above as a hint. Hopefully it is enough for you to figure out the rest.


Difference between delayed branches and out-of-order execution

I suppose you could view branch delay slots as a very special sort of out-of-order execution, but this isn't usually what we mean when we talk about out-of-order execution: generally, we're referring to a CPU that has a more general mechanism to detect when instructions can be re-ordered.  In addition, usually out-of-order execution takes care to avoid changing the semantics/behavior of the instructions.  In contrast, a branch delay slot does change the behavior of the instructions (because it affects whether the instruction after the branch is executed or not).


Why do BNF specifications of C-like languages define expressions in terms of seemingly unrelated parent expressions?

Why are C-like language grammars so "polymorphic"?

Because that's the way algebra works :-).

The arguments to (for example) a relational expression could be shifts or sums or products (or, for that matter, variables or constants, to say nothing of a variety of unary operator expressions), and all combinations are possible. So you could write out all nine possibilities (and then sixteen possibilities for equality expressions, etc.) (not counting the unary/base possibilities) but the quadratic explosion gets annoying. It's easier to consider each precedence level to include all the more tightly-binding levels as well.

I wouldn't call this polymorphism, really, although you might implement the expression type from a base Expression and individual derived types for each operator. The semantic value of every *-expression production is then a derived type of Expression, and it is not semantically necessary to know which one; the production labels are no longer needed.


There is a simple algorithm whose complexity is $O(Kn)$. The algorithm computes, for each $m \leq n$, the $K$ largest sums of the first $m$ numbers. Given the list for $m$, the list for $m+1$ is computed by adding the $(m+1)$st element to the old list, merging the two lists, and keeping only the top half. Since merging sorted lists can be done in linear time, the resulting complexity is $O(Kn)$.


What are applications of alphabetic trees?

You use alphabetic trees when you need nodes to keep their input order in the resulting code. Huffman trees are used for coding purposes, and alphabetic trees for storing data and for allowing quick search and edit.

One example application is storing textual data in alphabetic order. The complete works of Shakespeare were stored in an OAT (optimal alphabetic tree), which was constructed using the Hu-Tucker algorithm. See here for another $O(n \log n)$ algorithm for constructing OATs.


how to prove that every finite language is context-free?

It's not hard to show that every finite language is regular. If you know that every regular language is also context-free, you're done.


Algorithm to find best combination of datasources (Quality and price)

What you're asking reminds me of some of the work I did a Linear Programming course and made me think of the Hungarian Algorithm. I hope this helps!


Number of iterations of the Euclidean algorithm

There's very little to deduce.

The number of iterations is linear in the size of the input because the size of the input is $2+\log_2 a + \log_2 b$ and the number of iterations is $2\log_2 a$, which is less than $2(2+\log_2 a + \log_2 b)$, so is less than twice the length of the input.  Hence, (2) holds.

Each iteration requires only a polynomial number of steps: all it does is tests and simple arithmetic operations, all of which can be done in time polynomial in the number of bits involved.  Therefore, the total required time is some linear function (the number of iterations) times some polynomial function (the cost of each iteration), which is another polynomial function. So (3) holds.


In theoretical computer science, in the context of operators or functions, "binary" usually means "taking two arguments", whereas "Boolean" means "taking one of two values", especially if those values are true and false or $0$ and $1$.

So, for example, the ordinary addition operator on the natural numbers is binary (it adds two things) but not Boolean (the arguments can take infinitely many different values).  Conversely, the function $f(x,y,z)=(x\lor y)\land z$ is Boolean (its arguments are true/false) but not binary (it takes three arguments, not two; it's ternary).

"Binary" is also used to denote the base-$2$ number system but that doesn't seem relevant, here: min and max operate on numbers as abstract quantities, and the representation of those numbers (binary, decimal, Egyptian hieroglyphs, ...) is irrelevant.


The thing to notice here is that your function sum is defined on lists, which are inductively defined. Theoretically, the inductive definition of a list defines for every type T a term
match_list :: T -> (a -> [a] -> T) -> ([a] -> T)

satisfying the property
match_list s t [] = s
match_list s t (x::xs) = (t x xs)

in addition, defining a recursive function requires an untypable fixed-point combinator fix satisfying the property
fix F = F (fix F)

so combining the two, we could write your definition by first defining
F :: ([a] -> a) -> ([a] -> a)
F := λ f -> match_list 0 (λ x -> (λ xs -> x + f xs))

and then
sum := λ x -> (fix F) x
     = λ x -> (fix (λ f -> match_list 0 (λ x -> (λ xs -> x + f xs)))) x

To convince oneself that this works, let's try this on the example
sum [1,2] = (fix F) [1,2]
          = (F (fix F)) [1,2]
          = (λ f -> match_list 0 (λ x -> (λ xs -> x + f xs))) (fix F) [1,2]
          = match_list 0 (λ x -> (λ xs -> x + ((fix F) xs))) [1,2]
          = 2 + ((fix F) [1])
          = 2 + ((F (fix F)) [1])
          = 2 + ((λ f -> match_list 0 (λ x -> (λ xs -> x + f xs))) (fix F) [1])
          = 2 + (match_list 0 (λ x -> (λ xs -> x + ((fix F) xs))) [1])
          = 2 + (1 + ((fix F) []))
          = 2 + 1 + ((F (fix F)) [])
          = 2 + 1 + ((λ f -> match_list 0 (λ x -> (λ xs -> x + f xs))) (fix F) [])
          = 2 + 1 + (match_list 0 (λ x -> (λ xs -> x + (fix F) xs)) [])
          = 2 + 1 + 0

This is theoretically what would go on in a purely functional language (for example the untyped lambda calculus), however in languages like haskell, lisp, or ocaml (I am unaware of inductive datatypes in python), the terms match_list and fix are "internal" constructs and are not explicit terms in the language.


Prove or disprove that the following language is context-free

You can use the pumping lemma in this way.

By closure properties, if $L$ is context free and it is intersected with the regular language $R = \{ 1^* 0^* 2 1^* 0^*$} the resulting langauge $L' = L \cap R$ is still context free.

We can apply the Pumping lemma to $L'$ and prove that it cannot be CF, so $L$ is not CF as well.

Let $p$ be the pumping length; pick

$$z = 1^p \, 0 \, 0^p \; 2 \; 1^{p} \, 1 \, 0 ^p$$

First note that if $vwx$ is entirely contained in the first half, then pumping it one time is enough to make the first half longer than the second half; making $[\alpha]_2 > [\beta]_2$ and pushing the string out of $L$

If $vwx$ is entirely contained in the second half, then pumping it zero times is again enough to make the first half longer than the second half; making $[\alpha]_2 > [\beta]_2$ and pushing the string out of $L$

So $vwx$ crosses the middle of $z$.

At least one, but at most $p$ positions are contained in $vwx$, so $v$ must be in the $0^p$ before the center and $x$ in the $1^p$ after the center.

If $|v| <> |x|$ then - as above - pumping them one (or zero times) would make the first half longer.

But if $|v| = |x| = k \geq 1$ we can still pump it zero times getting the string:

$$z^0 = 1^p \, 0 \, 0^{p-k} \; 2 \; 1^{p-k} \, 1 \, 0^p$$

but

$$ [ 1^p \, 0 \, 0^{p-k} ]_2 >= [ 1^{p-k} \, 1 \, 0^p ]_2$$

(for $k=1$ we have $1^p 0 0^{p-1} = 1^{p-1} 1 0^p$)


More exactly, a B tree has an $m$ value such that the number of children is between $\lceil\frac m2\rceil$ and $m$ children. That differs from your numbers for odd $m$. For $m=3$ the bounds are $2$ and $3$, which is the 2-3-tree you refer to.

As far as I know (I tried this several years ago) these numbers are the smallest interval for which the split and merge operations can work. You can try yourself. If a node has $m$ children, I can add $1$ and the node must be halved. Thus this satisfy the $\lceil\frac m2\rceil$ bound? Check for $m$ odd and even separately.


Understanding characterizations of Matching on Graphs

It is nice for OP to extract the essence of the proof for Berge's Lemma, which is described as the  "Theorem (I think it is due to Peterson)" to create the hypothesis.

"Is the hypothesis correct? If not, why is it wrong?" Yes, it is correct.

"What about the hypothesis with respect to non-bipartite graphs?" Yes, it is still correct with respect to non-bipartite graphs.

"If the hypothesis is correct, why is always Egervary's Theorem used?" Well, I cannot avow Egervary's Theorem is always used (when? and where?).
It is true, however, that in the case of bipartite graph, Egervary's Theorem is instrumental in creating a fast and easily-implementable algorithm to find the maximum weight matching. In comparison, I cannot find  a similarly good algorithm for which the hypothesis can be equally helpful. So it is no wonder that Egervary's Theorem is usually mentioned when we come to the maximum weight matching for bipartite graph.


Solving $T(n) = 2T(n/2) + T(n-1)/\log n$

By comparison to the recurrence $T(n) = 2T(n/2)$, we see that $T(n) = \Omega(n)$. By comparison to the recurrence $T(n) = 2T(n/2) + n$, we see that actually $T(n) = \Omega(n\log n)$.

Now let us prove by induction that the other direction holds as well. I will interpret $T(n/2)$ as $T(\lfloor n/2 \rfloor)$. Suppose that $T(m) \leq Cm\log m$ for all $m < n$. Then
$$
T(n) \leq 2C\frac{n}{2}\log \frac{n}{2} + \frac{n\log n}{\log n} = Cn\log n + (1-C)n.
$$
For $C \geq 1$, it follows that $T(n) \leq Cn\log n$.

It seems that we have proved that $T(n) = O(n\log n)$, but actually the base case of the induction doesn't hold. However, this shouldn't be too hard to fix (left to the reader).


Face recognition system with a sparse dataset

You can apply transfer learning.  Leverage one of the existing datasets and deep learning networks that can classify faces e.g. celebrities.

Add/remove layers on top of the feature extraction layers and use your small data set.  Provided that the base dataset / network is large and rich enough you should be able to apply it to your dataset.

See https://cs231n.github.io/transfer-learning/


applying CTL/LTL model-checking on some system

I'm pretty sure that you need your system to be designed in Promela, rather than Java. You then input the system in Promela, and the specification in LTL (or CTL) to SPIN, which outputs a C code for a model checker for the specific instance.


Is transitivity required for a sorting algorithm

You asked: Can we run a sorting algorithm, feeding it a non-transitive comparator?

The answer: Of course.  You can run any algorithm with any input.

However, you know the rule: Garbage In, Garbage Out.  If you run a sorting algorithm with a non-transitive comparator, you might get nonsense output.  In particular, there is no guarantee that the output will be "sorted" according to your comparator.  So, running a sorting algorithm with a non-transitive comparator is not likely to be useful in the way you were probably hoping for.

As a counterexample, running insertion sort on the input list $[3, 2, 1]$ using your comparator would leave the list unchanged -- yet the resulting output list is not in sorted order (according to your comparator).


Is there a simple argument why graph isomorphism is not NP-complete?

The type of argument you are looking for is as follows:

If graph isomorphism were NP-complete, then some widely believed complexity assumption fails.

There are at least two such arguments:

Schöning showed that if graph isomorphism is NP-complete then the polynomial hierarchy collapses to the second level (equivalently, $\Sigma_2^P = \Pi_2^P$).

Babai's quasipolynomial time algorithm implies that if graph isomorphism is NP-complete then the exponential time hypothesis fails.

Whether such arguments are "valid" or not is a sociological question, not a mathematical one.


Finding Hamiltonian cycles in polynomial space

Observe that a naive witness for $m$ cycles is a list of the cycles, which may be exponential (in case the value of $m$ is exponential in the size of $G$).

So perhaps you should work directly with PSPACE.

A possible approach is to order the vertices of $G$, and then try all sequences of $n$ (the number of vertices) vertices, in lexicographical order (one at a time, erasing the last one every time you proceed to the next, so as not to waste space), and for each sequence check whether it is a Hamiltonian cycle, and increment a counter if it is. If the counter passes $m$ then you have $m$ distinct cycles.

If by "distinct cycles" you mean that you do not count cyclic permutations, then after you complete the entire count, simply divide the number of cycles you found by $n$, giving you the number of cycles without cyclic permutations, and compare this number to $m$.


Subject S2 has read-write access to Object 1, which is something no other subject has. On the other hand, subject S2 has no rights to Objects 2 and 3, which is something no other subject has. So Subject S2 has incomparable rights to all other subjects.

Similarly S1 is incomparable to the others.

S4 clearly has more rights than S3.
S5 clearly has more rights than S3.

So the subjects' "security levels" can be shown like this:

$\,\,\,$S5 S4
   \ /     S1   S2
    S3

(I don't know this subject before your question so this is just my impression. This subject has been discussed in three questions at cs.stackexchange.com in the past.)


Sum of unique elements in all sub-arrays of an array

Hint: Use an extra $O(n)$-spaced array of pointer to the last (biggest) index of each distinct value. Then, this array is very helpful when you do your above algorithm.

Lastly, we should have an $O(n)$ algorithm.


The grammar you wrote can generate the word "aaa", which is not supposed to be generated, if the grammar generates exactly $L$.

ergo, the grammar is incorrect for $L$. (which is great, since $L$ is not CFL, and no grammar can generate it!)


Fast algorithm for interpolating data from polar coordinates to cartesian coordinates

I don't know if this has been studied by others.  Speculating off the top of my head, let me outline two possible approaches.

Applying standard rectangular methods to polar coordinates

Here's one way to adapt more familiar interpolation methods (that work with Cartesian coordinates) to your setting.  Let's start by looking at bilinear interpolation.

Let $P$ be the point on the Cartesian grid whose value you want to compute, using interpolation.  Find the smallest "rectangle" of four nodes that surround the point $P$.  A "rectangle" in polar coordinates is just like a rectangle in a Cartesian grid, except with up/down replaced with "inward"/"outward" and right/right replaced with "clockwise"/"counterclockwise".  For instance, here is an example of a "rectangle" in a polar-coordinate grid:

This gives you 4 nodes that surround $P$.  Finally, use these 4 nodes to interpolate and form the value for $P$.  For instance, you could do bilinear interpolation, in the same way we do bilinear interpolation on a Cartesian grid, but now working with polar coordinates / barycentric coordinates.

This also makes clear how to generalize to other interpolation schemes, such as bicubic interpolation.

Ad-hoc method: supplement from adjacent radials

One possible approach you could try would be to pick the 3 closest nodes, then supplement them with a few other nodes from adjacent radials.

Let $P$ be your point.  Start by picking the closest 3 nodes to $P$ (say).  Then, supplement them.  For instance, suppose all 3 nodes are on the radial $\theta$.  Look at the radial just to the left of it, $\theta-\epsilon$, and out of all nodes on that radial, pick the 1 or 2 nodes that are closest to $P$.  Similarly, look at the radial just to the right of it, $\theta+\epsilon$, and out of all nodes on that radial, pick the 1 or 2 nodes that are closest to $P$.

Now use those points to interpolate.  You might use weighted least-squares regression to fit a linear (or bilinear/bicubic/etc.) model, where the nodes that are closer to $P$ receive a higher weight.  If you experiment a bit with the number of points chosen, the type of model, and the weights, you might find a scheme that reduces the "striation" artifacts.

Maybe better schemes are known; I don't know.  I'm not expert in this area.


Chess violates all three conditions, so I don't really understand what there is to ask.

(1) The game is not finite. Although the 50-move and threefold repetition rules allow a player to end the game under certain circumstances, they do not oblige the player to do so.

(2) The game has draws.

(3) As you have observed, the game definition distinguishes between the players. Your "active player" trick doesn't work because you've turned chess into a one-player game: the "active" player makes every move and the "inactive" player is a spectator.


Terminology about the word Function : General vs Computable

A (mathematical) function $f$ with domain $X$ and range $Y$ is a set of pairs $(x,y) \in X \times Y$ such that for each $x \in X$ there is exactly one pair of the form $(x,y)$; we say that $f(x) = y$.

A computable function $f$ is a function computed by some program.

A function in a programming language is an entity whose exact definition depends on the programming language. For example, in Pascal a function is a subroutine returning a value, in C a function is any subroutine, and in functional languages a function is either a declared subroutine or an "anonymous" function arising as some lambda expression.

Summarizing, the meaning of function depends on context. In a mathematical context or in some parts of theoretical computer science (say, complexity theory), a function is an arbitrary mapping; this is also probably the case in programming language theory, but I'm not qualified to say. In software engineering the meaning might depend on context. Computable functions (also known as recursive functions) are always called that.


Determining properties of linear code from generator matrix

If the minimal distance is $d$, then

Up to $d-1$ errors can be detected. This means that if a sent codeword is modified by flipping at least one and up to $d-1$ bits, then the receiver can tell that some bits were flipped.

Indeed, suppose that $w$ is the codeword that was sent, and that $w'$ is obtained from $w$ by flipping at least one and up to $d-1$ bits. Since $1 \leq d_H(w,w') < d$ (where $d_H$ is Hamming distance), we see that $w'$ is not a codeword (since the distance between any two different codewords is always at least $d$), and so we can detect that errors have occurred.

Up to $\lfloor \frac{d-1}{2} \rfloor$ can be corrected. This means that if a sent codeword is modified by flipping at most $\lfloor \frac{d-1}{2} \rfloor$ bits, then the original codeword can be recovered.

Indeed, suppose that $w$ is the codeword that was sent, and that $w'$ is obtained from $w$ by flipping up to $\lfloor \frac{d-1}{2} \rfloor$ bits. I claim that $w$ is the unique codeword at distance at most $\lfloor \frac{d-1}{2} \rfloor$ from $w'$. Indeed, if $z$ were another such codeword then
$$
d_H(w,z) \leq d_H(w,w') + d_H(w',z) \leq 2 \lfloor \tfrac{d-1}{2} \rfloor < d,
$$
contrary to the definition of minimal distance.


Do we need recursion in programming language to solve any problem?

In short, to answer your questions:

(1) You can convert any recursive algorithm into its non-recursive form.

(2) As stated by the others, you have all the features you need.

Computational Power (Turing-completeness)

You probably know that you cannot solve any problem, for instance, the halting problem is undecidable. And so are many other problems, such as deciding whether an arbitrary formula in first order logic is provable. Thus, with today's knowledge on computability, even the most advanced computer/programming system imaginable won't be able to process every query even if all the data is available.

When assessing the computational power of languages, computer scientists often use the notion of Turing-completeness:
If you can describe (and run) any Turing machine in your programming language, then it is Turing complete and can solve any problem which can be solved by a Turing machine.

To get a feel for Turing machines, I strongly encourage you to use a Simulator and try to solve some simple problems.

In particular, have a look at the syntax of the sample program in the Simulator, which should give you an idea of your minimal language.

Expressive Power and Minimality

When it comes to language design, expressive power is more important to me than the ability to solve any computable problem. Many useful domain-specific languages are not Turing-complete, but address specific problems very well.

However, equally powerful computational models such as the Lambda Calculus (functional programming) or the Pi Calculus (concurrent programming) show that you can have a very small set of elegant, composable language elements to construct larger systems, to be able to reason about their composition while having the computational power of Turing machines at the same time. Beautiful.

So if it is minimality you are looking for, take a closer look at the Lambda Calculus.
Other noteworthy well designed minimal languages are:

LISP
Prolog
Smalltalk and in particular Self

Feel free to add more languages to your personal list (and please let me know ;)


How are Complex Numbers and Complex Analysis used in CS?

I haven't seen them pop up a lot in "Computer Science" per say but there are quite a few closely related fields where they are very present.

I can think of signal processing for example, where Fourier transforms and other complex transformations are fundamental tools. Designing filters for signals also often boils down to placing poles in the complex plane.

In  control theory and the analysis of complex systems you also sometimes analyse the stability of systems by looking at complex poles of algebraic fractions.

I imagine complex numbers must pup op a lot in quantum computing also, as a pure quantum state is represented as a complex vector in some basis.

I am only passingly familiar with the fields I mentioned so there might be a lot more ways complex numbers are used in them, and also a lot more fields I am not familiar with.


Is this language context free L=${a^mb^nc^pd^q: m+n=p+q}$?

You can create a word of this language symmetrically from outside to inside. Here is a context free grammar for that. It produces for every $a$ or $b$ a $c$ or $d$. If it has started producing $b$s or $c$s, it cannot produce $a$s or $d$s anymore.

Here are the production rules where $S$ is the start symbol:

\begin{align*}
S & \rightarrow aSd \tag{1} \\
S & \rightarrow T \\
S & \rightarrow V \\
S & \rightarrow U \\
S & \rightarrow \epsilon \\
T & \rightarrow aTc \tag{2} \\
T & \rightarrow V \\
T & \rightarrow \epsilon \\
U & \rightarrow bUd \tag{3} \\
U & \rightarrow V \\
U & \rightarrow \epsilon \\
V & \rightarrow bVc \tag{4} \\
V & \rightarrow \epsilon
\end{align*}
Edit: I've simplified the rules so that fewer terminal symbols appear in it, and adapted the proof.

Proof: All rules are symmetrical, and except for the $\epsilon$-rules they have one non terminal in the middle, which is preceeded and followed by a terminal. The preceding terminal is either an $a$ or $b$, and the following terminal is always a $c$ or $d$.

Obviously the rules produce for every $a$ or $b$ exactly one $c$ or $d$. Thus, the number of $a$s and $b$s must be equal to the number of $c$s and $d$s, and this is why $n + m = p + q$ is fulfilled. It also follows that in the left half of the word only $a$s and $b$s can be written, while in the right half only $c$s and $d$s are written.

In the rules $b$ is only followed by the non terminal $U$, which expand to $b\ldots{}$. Thus, an $b$ in the word can never be followed by an $a$. This shows that the left side of the word must have the form $a^nb^m$.

In the rules $c$ is only preceded by the non terminal $V$, which expand to $\ldots{}c$. Thus, an $c$ in the word can never be preceded by an $d$. This shows that the right side of the word must have the form $c^pd^q$.

A word $w = a^nb^mc^pd^q \in{} L$ can be constructed as follows:

Apply the rule (1) $\min(m, q) =: l$ times. You get $$\underbrace{a\ldots{}a}_{l}S\underbrace{d\ldots{}d}_l$$.
If $m \geq l$ apply rules $S \rightarrow T$ and then (2) $\min(p, m - l) =: k$ times, and you get $$\underbrace{a\ldots{}a}_{l + k }T\underbrace{c\ldots{}c}_k\underbrace{d\ldots{}d}_{l = q}$$ If $k = p$ than $n$ must be zero. You can apply $T \rightarrow \epsilon{}$ and you're finished. Otherwise $k = m -l$ and $a$ appears $l + k = m$ times. Apply rule $T \rightarrow V$, rule (4) $p - k$ times, and rule $V \rightarrow \epsilon{}$. You will get $$\underbrace{a\ldots{}a}_{m}\underbrace{b\ldots{}b}_{p - k}\underbrace{c\ldots{}c}_{k + p - k = p}\underbrace{d\ldots{}d}_{q}$$ Since $m + n = p + q$ proved already above, $p - k = n$ follows and you are finished.
Otherwise $q > l$, and you must apply rule $S \rightarrow U$, and rule (3) $\min(n, q - l) =: g$ times. You will get $$\underbrace{a\ldots{}a}_m\underbrace{b\ldots{}b}_gU\underbrace{d\ldots{}d}_{g + l}$$ If $g = n$ than $p$ must be zero. You can apply $T \rightarrow \epsilon{}$ and you're finished. Otherwise $g = q - l$ and $d$ appears $l + g = q$ times. Apply rule $U \rightarrow V$, rule (4) $n - g$ times, and rule $V \rightarrow \epsilon{}$. You will get $$\underbrace{a\ldots{}a}_{m}\underbrace{b\ldots{}b}_{g + n - g}\underbrace{c\ldots{}c}_{n - g = p}\underbrace{d\ldots{}d}_{q}$$ Since $m + n = p + q$ proved already above, $n - g = p$ follows and you are finished.


Compare-and-Swap in an RDBMS for custom locks and lock escalation

The Prevent race conditions across multiple rows on Stackoverflow seems to be relevant.

Also, I would urge you to use SQL server locks instead of your own lock column (which it sounds like you're doing).

And it looks like doing hierarchical locks is kind of clumsy in SQL, so if you're finding this to be a huge bottleneck you could try a locking service like zookeeper.


Relating indexes for parameters and variables

Yes.

This appears to be an instance of the assignment problem.  In the assignment problem, you construct a bipartite graph.  The vertices on the left represent referees.  The vertices on the right represent matches.  You draw an edge from a referee $r$ to a match $m$ if the referee $r$ is potentially available to officiate in that match.  You can use the time() and avail() parameters to work out which edges to draw.  Then, a solution to the assignment problem (a maximum matching in this bipartite graph) will represent a way to assign referees to matches.  Thus, this captures the restrictions you want to enforce in a simple and natural way.


I would like you to note that the selection cannot be fully random.. Assume there are 10 total images.

5 have the same tags
5 have a single but unique tag

Then the algorithm will Always choose the same 5 images (And will Always skip the other 5 images).

Luckily there's an algorithm that can help you easily. Note that this algorithm skips points 4/5 (which you claim are optional).

Foreach image => sort its tags alphabetically

Find the longest tag

Postfix the same letter to all the tags in order to make them the same lenght

In example if you have the tags cherry,optimization,google those tags are transformed into

cherryXXXXXX
optimization
googleXXXXXX

Foreach image, make a string that is made by concatenation of all its tags. Then sort those strings alphabetically.

In Example:

Image1 - tags: B, EE, A
Image2 - tags: A, C
Image2 - tags: Z

The final strings would be

AXBXEE
AXCX
ZX

Put your strings in a doubly linked, linkedlist, select a random element, then skip "some elements" (in example if you have 300 strings, you can select the first random and then skip 40-60 strings ) and take another element.

This algorithm is not complex, and not cheap, but is a good start point, note that your algorithm have to be a euristic-based (or greedy) algorithm because I fear your problem has a big computational complexity (still checking that, I'll update later this answer).

An alternative algorithm complexity (n number of images)

Assume the number of tags is limite to 10.

set all scores to 0
foreach img in images
    foreach img2 in images
       img.score -= TagsInCommon(img,img2)

for (int i = 0; i<5; i++)
{
    images.SortBy( x => x.score);
    img = images.RemoveFirst(); // pick image with highest score
    foreach img in images // (we have removed the first image here)
       foreach img2 in images
           img.score -= TagsInCommon(img,img2) //adapt score slightly
}

The above algorithm has a complexity of roughly

O(n^2 + nlogn + n)

where n is number of images (I did not check complexity ineherent in string lenghts, number of tags etc.).

This algorithm basically is another algorithm with a greedy approach, image with unique tags will be the first selected images, while images that are heavily tagged will be putted to the end of the list (and possibly are never sorted out). Plus we are adapting the score during execution to remove tags that we have already drawed.

A better alternative would be (instead of removing Always the first element) to select a random element with a distribution that favours the elements with higher score (but at same time do not forbid to draw elements with low score).

This algorithm will probably will take less of a second even with something like 100 thousand images.

A distribution like the following would suffice:


How does the MMU map multi-channel setups

ASLR has nothing to do with this. ASLR is a software technique to secure the applications where all executables are relocatable in that they keep information in the executable to relocate it to any address.
I would guess that the MMU doesn't see if there are several RAM DIMMs. It is the motherboard's job to make sure that if the memory controller of the CPU sets certain lines of the address bus, they are directed towards the right DIMM for decoding.
In hardware it could look like switches (transistors) activated by higher order bits of the address bus that will redirect all address lines to another DIMM. For example, if you have 2 DIMMs of 8GB each then the first DIMM needs 33 address lines for decoding because 2^33 bytes = 8GB. The second DIMM brings the computer to 16GB so, if you set any line of the address bus above 33, then the motherboard knows it needs to use the second DIMM.


What is the big-$\Omega$ complexity of Fermat's Little Theorem?

Modular exponents can be computed efficiently using repeated squaring. This is a recursive method (which can also be implemented iteratively) that relies on the following two identities:
$$
a^{2k} = (a^k)^2, \qquad a^{2k+1} = a(a^k)^2.
$$
This allows us to give a recurrence for $f(a,b,n) = a^b \bmod n$:
$$
f(a,b,n) =
\begin{cases}
1 & \text{if } b = 0, \\
f(a,b/2,n)^2 \bmod n & \text{if $b$ is even}, \\
af(a,(b-1)/2,n)^2 \bmod n & \text{if $b$ is odd}.
\end{cases}
$$
This shows that $a^b \bmod n$ can be computed using $O(\log b)$ many multiplications. Since we keep reducing modulo $n$ in each step, each of these multiplications takes time polynomial in $O(\log n)$ (naively, $O(\log^2 n)$, but this can be significantly improved using fast integer multiplication methods). In total, we obtain an algorithm running in polynomial time.


Language Classification + AWS ML: what am I doing wrong?

There are probably multiple things wrong here.

Features

First, you don't tell us what features you have provided.  If the only input you have provided is the word itself (e.g., the string craindre), then most likely the machine learning algorithm has no idea how to use that information: all it knows is that this string is different from all the others you've provided, so it has no ability to generalize.

So, you need to derive some suitable features, to enable this to generalize.  For instance, maybe you'll have a feature vector of length $26^2=676$, one for each possible pair of letters, counting the number of times that pair of letters appears consecutively in the word.  Then, instead of asking the machine learning algorithm to predict the language from the word itself, ask it to predict the language from the feature vector.

You can certainly come up with much more sophisticated and effective features; this is just an example.  For instance, maybe you might have a feature that counts the fraction of letters that were vowels, or the fraction of letters that were consonants, or a feature that indicates what the last letter was, or a feature that indicates how many consecutive vowel-pairs the word had.  Basically, you want to pick features values that you think might be helpful at predicting the language or might tend to take different values for different languages.  If you want to build something that will be very accurate at predicting language, you'll probably need to get fairly sophisticated in designing features.  There's lots of research literature on language detection; you could try reading it to get some ideas for better features.  But if you just want to play around with this, my advice is to start with a small number of simple features.

Typically, machine learning algorithms are very smart about finding patterns in the feature vectors you provide -- but they don't do anything to automatically select features.  So, the division of labor is: you come up with the features; the ML algorithm looks for patterns that enable it to use those features to predict the answer.

Class imbalance

I suggest you read about "the class imbalance problem".  You have 3 classes (English, French, and random).  Your training set is imbalanced: you have twice as many examples with English as French/random.  In other words, you don't have an equal number of examples for each class.

This is not necessarily a problem, but in some cases it can be.  For instance, some machine learning algorithms behave poorly when the training set is imbalanced.  And every machine learning algorithm will work sub-optimally when the frequency of the classes in the training set doesn't match what you expect to see in practice.

In your case, it's probably not any of those complicated explanations; it's probably a much simpler reason.  Because you haven't given the ML algorithm any useful features, it basically has no information whatsoever that it can use to generalize or spot patterns.  In other words, it's trying to guess the language of a given word given no information about that word.  So what is the poor ML algorithm to do?  All it can do is guess based on the relative frequency of different languages.  In your case, your training set has told it that any given word is more likely to be English than to be French or random (about 2x as likely), so if you're forced to make a guess and pick one language, the smartest one to pick is 'English'.

In conclusion: it is no surprise that the ML algorithm is always outputting 'English', in your situation.

Once you add a suitable feature vector, if it still works poorly, you can read about the class imbalance problem and see whether it applies to you.


Find MST on grid graph with only weight of 1 and 2 in $O(|V|+|E|)$

Let $n=|V|$ and $m=|E|$.
Intuitively you want the to return the union of the edges in 1) a maximal spanning forest $F$ of the graph induced by the edges of weight $1$, with 2) a maximal spanning forest $F'$ of the graph obtained by identifying the edges of each tree in $F$ into a single vertex (where each edge in $F'$ actually represents an edge of $G$).
Some care is required to attain a running time of $O(n)$. The details are as follows.

Let $G_1$ be subgraph of $G$ induced by the edges of weight $1$.
Let $C_1, \dots, C_k$ be the connected components of $G_1$.
For each $C_i$, compute any a spanning tree $T_i = (V_i, E_i)$ of $C_i$.
This requires $O(m)=O(n)$ time in total.
For each edge $e=(u,v)$ of weight $2$ in $G$ let $i$ and $j$ be such that $u \in C_i$ and $v \in C_j$. Let $k(e) = (\min\{i,j\}, \max\{i,j\})$.
Sort the edges of $G$ in nondecresing order of $k(\cdot)$, keep at most one edge for each value of $k(\cdot)$. Let $S$ the resulting ordered set of edges.
Notice that $S$ can be found in time $O(m)=O(n)$ using radix-sort.
Create a graph $G_2$ with vertex set $\{1, \dots, k\}$ and edge set $\{ k(e) : e \in S \}$. For an edge $(i,j)$ in $G_2$ let $\ell(i,j)$ be and edge $e$ in $G$ such that $k(e) = (i,j)$.
This label $\ell(i,j)$ can be stored along with the edge $(i,j)$ itself, so that given $(i,j)$ we can find $\ell(i,j)$ in $O(1)$ time.
This step also requires $O(n)$ time.
Finally, compute any spanning tree $T' = (V', E')$ of $G_2$.
An MST of $G$ is the tree induced by the edges in $\left( \bigcup_{i=1}^k E_i \right) \cup \{ \ell(i,j) \mid (i,j) \in E'\}$.
Overall, the whole algorithm takes $O(n)$ time.
The same algorithm extends naturally to any constant number of distinct edge weights.
Here is a visualization of the algorithm on the graph you proposed in the comments. Blue edges has weight $1$, red edges have weight $2$. The connected components of $G_1$ are highlighted in gray (and each connected component will be represented by a vertex in $G_2$). In this particular example $S$ contains all red edges of $G$ since each red edge connects a different (unordered) pair of connected components in $G_1$.


Is the halting problem claim true with the advent of AI

Even if we can design better AI solving problems we did not think possible even 10 years ago, they will always be computer programs. And as you said it yourself, "Alan Turing states that, there can't be a program that can decide if a program will ever stop." (he actually proved it and not only stated it...). Thus even the best AI you can think of will not be able to decide this problem, this is uncomputable.

This is a theorem, and unless we find a new device doing computation beyond the power of Turing machine (I am not talking about faster computation, but really a new kind of computing), this will remain impossible. Even if we have whole new kind of computer defining a new concept of computation, let's call them hypercomputers, it is very likely that those hypercomputers will not be able to decide
if a hypercomputer ever stops.

However, you are right in the sense that in every day life, many programs are simple enough to be analyzed and proven to terminate. Thus we can still hope to have better algorithm (using for example advances in AI), that can generate proof of terminations for a large class of programs. See for example Microsoft Terminator [1] which precisely address this problem in practice.

[1] https://en.wikipedia.org/wiki/Microsoft_Terminator


Coordinates of the center and the radius of the circle on the image

If you want to automate the process I would use Hough Circle Transform.  It is an algorithm used to detect circles in an image. This Wiki article will describe Hough Transform better than I can.

You can manually find the center of a circle using these methods.


Proving undecidability for a language which contains string with certain syntax

It can be thought of a semantic property of the language, and its ok to use Rice's theorem here.

Define $C=\{L|\text{there is a string with exactly 3 zeros in }L\}$

So, $L_1=\{<M>|M \text{ is a turing machine and } L(M)\in C\}$ and because $C\neq\emptyset$ and $C$ is not every language, then by Rice's theorem, $L_1\notin R$.


How and which component of an Operating System is responsible for the transition of a process from the blocked state to the ready queue?

When an I/O is started, it will typically have an I/O request structure associated with it that includes items like the process ID that the I/O belonged to.  When the I/O completes the device driver will typically fork into an OS level I/O subsystem in the OS which will queue the IO request packet notification to the process and move the process to a computable queue.  (this may vary a little from one OS to another).   The process then waits for it's turn to become computable.

And yes, anything that executes code requires CPU time... though this is considered "interrupt time" rather than user time.


CFG and PDA for the grammar that has perfectly nested parentheses and brackets

The language you study is a classic, the one-sided Dyck language (on two pairs of brackets). You can directly make a PDA by considering the following property of nested strings: every symbol closing bracket you read should match the last unmatched opening bracket. Keep the unmatched $[$ and $($ on the stack and you are ready to go.


Efficiently finding $k$ smallest elements of Cartesian product

If $k$ is known in advance, we can do the following. I will assume that each list $A_j$ is sorted according to cost. What we will do is a weighted form of breadth-first exploration of index tuples $(i_1,\dots,i_n)$, storing the current candidates in a (bounded length) priority queue $Q$ according to their cost $A_1[i_1]+\dots+A_n[i_n]$. Initially $Q$ contains just the initial tuple $(0,\dots,0)$.

In each iteration, pop the first tuple $t=(i_1,\dots,i_n)$ off $Q$; this is a cheapest previously unexplored solution. Then generate its successors of the form $t^{(j)}=(i_1,\dots,i_j+1,\dots,i_n)$, compute their cost, and insert them into $Q$ accordingly.

We can avoid creating duplicates by only creating the successors $t^{(j)}$ up to the first index $j$ for which $i_j>0$; e.g. for $t=(0,1,0,2)$ we would only create $(1,1,0,2)$ and $(0,2,0,2)$ (the other tuples $(0,1,1,2)$ and $(0,1,0,3)$ instead get created as successors of $(0,0,1,2)$ and $(0,0,0,3)$, respectively). This eliminates the need for a closed list of explored tuples. We still need to store the priority queue $Q$, but it can be bounded to length $k-j$, where $j$ is the current iteration, with any entries beyond that discarded.

For example, suppose we have $A_1=(1,5,7),A_2=(1,2,5),A_3=(1,3,4)$, and $k=4$.

Initially, $Q=[(0,0,0)]$.
Pop $(0,0,0)$, with cost $3$, and push $(1,0,0),(0,1,0),(0,0,1)$. Their costs are $7,4,5$, respectively, and $Q$ is now $[(0,1,0),(0,0,1),(1,0,0)]$.
Pop $(0,1,0)$ (cost $4$), and push $(1,1,0)$ (cost $8$) and $(0,2,0)$ (cost $7$). $Q$ is now $[(0,0,1),(1,0,0),(0,2,0),(1,1,0)]$; since we only need two more solutions, we can drop the last two, getting $[(0,0,1),(1,0,0)]$.
Pop $(0,0,1)$ (cost $5$), and push $(1,0,1)$ (cost $9$), $(0,1,1)$ (cost $6$), and $(0,0,2)$ (cost $6$). $Q$ is now $[(0,1,1),(0,0,2),(1,0,0),(1,0,1)]$; again, we can drop unneeded entries since we only want one more, getting $[(0,1,1)]$.
Pop $(0,1,1)$; done.

To see that this method is correct, we just need to prove the following:

Given the above restrictions, any index tuple $i=(i_1,\dots,i_k)$ (with $0\le i_j\le size(A_j)$) is reachable along the unique path $(0,\dots,0)\to\dots\to(0,\dots,0,i_k)\to\dots\to(0,\dots,0,i_{k-1},i_k)\to\dots\to i$.
The cost of the tuples along that path is nondecreasing, since the weights are nonnegative.
If there is another tuple $i'$ with a higher cost, and $i'$ is popped off $Q$ during the algorithm, then so are all tuples along the path to $i$ (using induction).
If a tuple $i'$ is discarded due to the length restriction, then there are at least $k$ tuples whose cost is no greater than that of $i'$.


Proof that language is not regular. $L=\{w\bar{w}|w\in \{0,1\}^* and\ \bar{w}\ is\ one's\ complement\ of\ w\}$

Just show that after processing $0^n$ and $0^{n’}$ with n != n’ you must have reached two different states. (Which is easy: In one state, processing $1^n$ leads to an accepting state, in the other state it doesn’t). Therefore there is no finite set of states.

Or you just take the pumping lemma, p arbitrary large, and w = $0^p 1^p$. Which makes y = $0^k$ for some k >= 1.


Big O of multiple variables in a logarithm: is $(2n+m)\log(2n+m) = O((n+m)\log(n+m))$?

Classical way is same as when we consider double limit $\lim\limits_{(n,m) \to \infty}f(n,m)=A$, which use intention to infinity by squares  i.e. for $\forall \varepsilon>0$ $\exists \delta>0$ such that for $\forall n > \delta$ and $\forall m > \delta$ holds $|f(n,m)-A|< \varepsilon$. Using maximum norm conception we can write $\left\Vert(m,n)\right\Vert = \max\{n,m \}> \delta$. It is also known Chebyshev norm and the infinity norm terms for this conception and notation $\left\Vert \cdot \right\Vert_\infty$. Let me say, that this is same as intention to infinity by rectangles i.e. when we require $\exists \delta_1>0, \exists \delta_2>0$ and consider $\forall n > \delta_1$ and $\forall m > \delta_2$.
Applying to big-$O$ we can write that $O(f(n,m)),(n,m) \to \infty$ is set of functions $g$, such, that $\exists C_g>0$ and $\exists M_g>0$ such that for $\forall \left\Vert  (n,m)\right\Vert_\infty > M_g$ holds $g(n,m) \leqslant C_g f(n,m)$.
In your case $(2n+m)\log(2n+m) \leqslant 2(n+m)\log [2(n+m)] \leqslant 4(n+m)\log (n+m)$ using $1+\frac{\log 2}{\log (n+m)} \leqslant 2$, when $n>1,m>1$.
For completeness let me also note, that definition from one variable can be expanded to two or multi  variables in different ways, for example, we can consider intention to infinity by circles i.e. when we consider $\sqrt{n^2+m^2} \to \infty$. Is known intention to infinity by triangles i.e. $n+m \to \infty $ etc.


What is the precise definition of pseudo-polynomial time (feat. Counting Sort)

Let us denote the input's length by $n$, and lets remember that $n=\Theta\left(N\log K\right)$. You won't be able to write the exact running time of counting sort as an expression of the form $2^{\Omega(n)}$, as this would mean that for large enough inputs, the running time is always exponential. However, in this case, if $K$ is not too large compared to $N$, then the running time is actually linear, this means that there exists an infinite series of inputs with increasing size on which the running time is not exponential.

With this is mind, recall that what you seek is the worst case complexity of your algorithm, i.e. you want to find a certain time bound that holds for all inputs of large enough size. This means that to lower bound the complexity, it suffices to find one series of inputs with increasing size on which the running time is exponential. This allows you to focus on inputs where $K=2^N$, in this case the input size is $n=\Theta\left(\log^2 K\right)$, and the running time is $O(K)=O\left(2^{\sqrt{n}}\right)$, which is definitely exponential.

In general, a pseudopolynomial time algorithm is an algorithm which runs in polynomial time in the numeric value of the input (which means it is not necessarily polynomial in the input's length). Wiki's definition is no different, except it adds the restriction that the running time is polynomial in both the numeric value and the input size, i.e. if the input size is $n$, and its associated numeric value is $v$, we want a time bound of the form $p(n,v)$ for some polynomial $p$. This excludes for example a $2^N+K$ time algorithm for sorting $N$ numbers in the range $[1,K]$, although this is polynomial in $K$.


Minimum cost subset of sensors covering targets

Your problem is equivalent to the weighted version of Set Cover, which is NP-complete (and delving into other complexity classifications, W[2]-complete and inapproximable within $O(\log n)$).

If you want a polynomial-time algorithm, you're going to have to impose restrictions on either your problem or the input.


Every DFS algorithm should also construct a DFS tree (or, in general, forest), which records how the search progresses. For the CLRS algorithm, the adjacent node in step 3 is made the child of the node in step 2. For the other algorithm you have to be more careful (I'll let you figure out the correct way). If the DFS tree is constructed properly, then it will satisfy the following property:

  If $(x,y)$ is an edge not belonging to the tree, then either $x$ is an ancestor of $y$ or $y$ is an ancestor of $x$.

This is the property of DFS used in actual algorithms. The actual sequence in which the nodes are traversed could also be important, but this is less common.

Corneil and Krueger suggest a generic "non-deterministic" version of DFS, and give a characterization in terms of the resulting DFS traversal order. They also suggest a canonical way of forming the DFS tree given the DFS order – each node is the child of its earliest neighbor, and show that the resulting DFS tree always satisfies the crucial property stated above.

If Method 1 satisfies the criterion of Corneil and Krueger, then it is worthy of the name DFS. If you are curious, you can read the paper and check whether the criterion listed there holds for that algorithm. Even if it doesn't, you can check whether there is a simple way to construct a DFS tree (not necessarily using the construction suggested by Corneil and Krueger) that satisfies the property above – that suffices in most cases.

You can use any algorithm which satisfies your needs (in some cases, you don't care about any property, only about traversing the entire connected component). A "correct" form of DFS, together with a method of constructing the DFS tree, should satisfy the DFS tree property, and preferably also the ordering characterization of Corneil and Krueger. Which one is preferable depends on many factors – usually the one using the least resources (time and memory).


Determining equivalence classes of $\{w \in \{0,1\}^*\mid$ the $k$-bit of $w$ from the right is 1$\}$

http://users.utu.fi/jkari/automata/fullnotes.pdf explains equivalence classes well (under section 2.8 "Myhill-Nerode theorem") whence the following notation and definition is borrowed.

Define $\text{Ext}(w,L) =\{x\mid wx\in L\}$ where $w$ is in $\Sigma^*$ and $L$ is the language, ie. the set contains of all suffixes that, when added to $w$, yields a word in $L$.

Two words $a$ and $b$ are in the same equivalence class if $\text{Ext}(a,L)=\text{Ext}(b,L)$.

For the language $L_k$ described, only the last $k$ letters of $w$ matter when figuring out $\text{Ext}(w,L_k)$ for any word $w$ because the other letters do not matter as they do not contribute to the condition "the $k$-th bit of $w$ from the right is $1$". Since there are only finitely many combinations for the last $k$ letters, specifically $2^k$, there are a finite number of equivalence classes in $L_k$.

As per your edit about suffixes of length less than $k$, sure, $\text{Ext}$ can contain such suffixes, but they do not matter in showing that there exist finitely many equivalence classes.


References on comparison between quantum computers and Turing machines

What is actually the case is that anything a quantum computer can compute, a Turing machine can also compute. (This is without commenting at all on how long it takes the Turing machine to compute the function compared to a quantum computer.)

This is actually not difficult to see, provided you understand quantum computation. For a quantum circuit over a typical gate set, for example, the outcome is governed by a probability distribution, which is determined by the coefficients of a unitary matrix. That unitary matrix is just a matrix product of those of the gates, and can be computed — if you're patient enough — by a classical computer. So for sheer computability (as opposed to efficiency), there is no advantage to using quantum computers.

The whole challenge arising from quantum mechanics is to determine whether such coefficients can be computed efficiently, which is a more demanding problem than whether they can be computed at all.


Floating point number fractions excercise

Actually, floating point arithmetic according to the IEEE 754 standard will calculate 1-x exactly, without any rounding error, if 0.5 ≤ x ≤ 2.0. So for x close to 1, 1-x is calculated exactly, 1 / (1-x) is calculated accurately, and 1 / (1 + x) and the sum will be calculated accurately as well.

What you are likely observing is the rounding error when 0.999999 for example is converted to a floating point number. x will not be equal to 0.999999, but a bit off. And the function itself as a function of real numbers is very sensitive to changes in the argument. That also explains why re-arranging the function can't help, because the function is sensitive to the arguments, and the arguments are not what you think.

The same applies for x close to -1, since f(x) = f(-x).

You will actually have a problem if x is close to 0. 1 / (1-x) and 1 / (1+x) can both be calculated with a very small absolute error, the difference is calculated exactly because both have about the same size, but because the result is close to zero, the small absolute errors turn into a rather large relative error.

When x is close to zero, 1 / (1 - x) = 1 + x + x^2 + x^3 ..., and a / (1 + x) = 1 - x + x^2 - x^3 ..., the mathematical difference is 2x + 2x^3 + 2x^5 ... ≈ 2x.

Let u be the value of the last bit in a number 1 ≤ x < 2, then IEEE arithmetic has rounding errors up to u/2. 1 / (1 - u) ≥ 1 is calculated with an error up to u/2, 1 / (1 + u) has an error up to u/4. If you pick x^2 slightly larger than u/4, then 1 / (1 - x) is rounded to 1+x, 1 / (1 + x) is rounded to 1 - x + u/4, and the difference that is calculated is 2x - u/4, instead of 2x + x^3 + 2x^5 ..., so the absolute error is > u/4, and the relative error about $(u/4)^{1/2}$.

You can fix this easily by subtracting 1 from both sides, giving $x / (1 - x) + x / (1 + x)$.


Where is the theory about "binary toggling games"?

"Binary toggling games" are generally just arithmetic problems over GF(2).

Your particular problem is equivalent to the following over GF(2):

$$\sum_i V_iS_i = 1 + A_M $$

If we write $\vec{S} = [S_1, S_2, \dots]^T$ and $V = [V_1, V_2, \dots]^T$ we find that your problem is actually a simple matrix equation over GF(2):
$$V\vec{S} = 1 + A_M$$

You can solve this problem using Gaussian elimination over GF(2). In your example:

$$\left(\begin{array}{ccc|c@}
 1 & 0 & 0 & 1\\
 1 & 0 & 1 & 0\\
 0 & 1 & 1 & 1\\
 1 & 1 & 1 & 0
\end{array}\right) \longrightarrow
\left(\begin{array}{ccc|c@}
 \color{red}1 & 0 & 0 & 1\\
 0 & 0 & 1 & 1\\
 0 & 1 & 1 & 1\\
 0 & 1 & 1 & 1
\end{array}\right)\longrightarrow
\left(\begin{array}{ccc|c@}
 1 & 0 & 0 & 1\\
 0 &\color{red}1 & 1 & 1\\
 0 & 0 & 1 & 1\\
 0 & 0 & 0 & 0
\end{array}\right)\longrightarrow
\left(\begin{array}{ccc|c@}
 1 & 0 & 0 & 1\\
 0 &1 & 0 & 0\\
 0 & 0 & \color{red}1 & 1\\
 0 & 0 & 0 & 0
\end{array}\right)
$$

From which we can read off that $S_1 = 1$, $S_2 = 0$ and $S_3 = 1$.


How to mathematically determine row, column, and sub-square of cell in nxn array where n is a perfect square?

Let the one-dimensional cells be $c_1, c_2, \cdots, c_{n^2}$.

Assume the top-left cell is at $(1,1)$, i.e., the first row and the first column. Assume the top right cell is at $(1,n)$, i.e., the first row and the $n$-th column. Then the $i$-th cell, $c_i$ is at $(i/n + 1, i \%n +1)$. Here $i/n$ is the integer division and $i\%n$ is the modulo operation in any popular programming language.  For example, let $n=9$. Then the $42$-th cell, $c_{42}$ is at $(42/9+1, 42\%9+1)=(5, 7)$.

Suppose the subsquares are lined up in the same order as the cells, so that we have subsquares $S1, S2, \cdots, Sn$. Consider each subsquare as a kind of "large cell". So that we would have the following coordinates for subsquares.

Note that $c_i$ belongs to the $(i/n+1)$-th subsquare, i.e. subsquare $S(i/n+1)$. For example, $c_{37}$ belongs to the $5$-th subsquare, i.e, subsquare $S5$. We are in the same situation as before, but with the $(i/n+1)$-th "large cell" and a $\sqrt n\times\sqrt n$ of "large cells". So similarly we see that the $(i/n+1)$-th subsquare is at $((i/n+1)/\sqrt n + 1,(i/n+1)\%\sqrt n + 1)$, using the coordinates for subsquares.

Suppose we want to traverse the subsquare at $(j,k)$ (where $(j,k)$ is in the coordinates for subsquares).

The first cell (the top-left cell) of that subsquare is $c_{(j-1)\sqrt n\cdot n + (k-1)\sqrt n +1}$
The first cell of the second row of that subsquare is $c_{(j-1)\sqrt n\cdot n + (k-1)\sqrt n +1 + n}$
$\cdots$
The first cell of the last row of that subsquare is $c_{(j-1)\sqrt n\cdot n + (k-1)\sqrt n + 1 + (\sqrt n -1 )n}$

So we can traverse all cells in that subsquare by the following pseudocode.

$\quad$ for $row$ in $1, 2, \cdots, \sqrt n$
$\quad\quad$ for $column$ in $1, 2, \cdots, \sqrt n$
$\quad\quad\quad$ visit the cell at $row$-th row and $column$-th column of the subsquare at $(j,k)$, which is $c_{(j-1)\sqrt n\cdot n + (k-1)\sqrt n + (row -1 )n + column}$

Note "$row$-th row and $column$-th column" are referring to cells in that subsquare.

For example, we will traverse the cells at subsquare (2,3) in the following order.

cells in its first row, $c_{34}$, $c_{35}$, $c_{36}$,
cells in its second row,  $c_{43}$, $c_{44}$, $c_{45}$,
cells in its third row,  $c_{52}$, $c_{53}$, $c_{54}$.


Assuming you refer to Myhill-Nerode equivalence classes:
First notice, that for a non-regular language $L$, the number of classes is necessarily infinite. This is one direction of the Myhill-Nerode theorem.
Since regular languages are closed under reversal, it follows that for a non-regular language $L$, both $L$ and $L^R$ have the same ``number'' (namely, infinitely) of equivalence classes.
For the case of regular languages, the Myhill-Nerode relation is very ``right-biased'', since it relates to the existence of a separating suffix. This is why reversing the language may change the number of classes. For example, consider the language
$$L_k=\{w\in \{a,b\}^*: w_k=a\}$$
i.e. the language of words whose $k$-th letter is $a$.
It's easy to show that the number of classes for $L_k$ is roughly $k$ (maybe $\pm 1$).
However, the language $L_k^R$ of words whose $k$-before last letter is $a$, is known not to have a DFA with less than $2^{k-1}$ states (and hence it has $\Omega(2^k)$ classes).
Interestingly, reversal and congruence classes do have an interplay: if you take a DFA, reverse it, determinize it, reverse it again, determinize again, and remove all unreachable states, you will obtain a minimal DFA for the original language, which is exactly what the equivalence classes characterize. This is Brzozowski's algorithm.


Is it decidable if a language described by number of occurences is regular?

Given two words $w_1$,$w_2$, is it decidable if the language $L$ of words containing equal number of $w_1$ and $w_2$ is regular?

First some definitions:
They could be made more concise, and the notations could be improved if they are to be used in proofs. This is only a first draft.

Given two words $w_1$ and $w_2$,
we say that:

$w_1$ always occurs with $w_2$, noted $w_1\triangleleft w_2$, iff

for any string $s$ such that
$s=xw_2y$ with $\mid x\mid,\, \mid y\mid\ \geq \mid w_1\mid +\mid
w_2\mid$ and $|x|_0,|x|_1|,|y|_0,|y|_1| \geq 1$ there is another decomposition $s=x'w_1y'$.
Note: The condition that $x$ and $y$ each contain at least a 0 and a 1 is required by a pathological case (found by @sdcvvc): $w_1=1^i0$, $w_2=v1^{i+j}$ and $y\in1^*$, and its symetrical variants.
there is a string $s=xw_2y$ with $\mid x\mid,\, \mid y\mid\ \geq \mid w_1\mid +\mid w_2\mid$ such that there is at most one decomposition $s=x'w_1y'$

$w_1$ always cooccurs with $w_2$, noted $w_1\triangleleft \triangleright\,w_2$, iff each always occur with the other,
$w_1$ and $w_2$ occur independently, noted $w_1\triangleright \triangleleft\,w_2$, iff neither one always occur with
the other,
$w_1$ always occurs $m$ times or more than $w_2$, noted $w_1\triangleleft_m w_2$, iff for any string $s$ such that
$s=xw_2y$ with $\mid x\mid,\ \mid y\mid|\ \geq \mid w_1\mid +\mid
w_2\mid$ there are $m$ other decompositions $s=x_iw_1y_i$ for
$i\in[1,m]$ such that $i\neq j$ implies $x_i\neq x_j$.

These definitions are constructed so that we can ignore what happens at
the ends of the string where $w_1$ and $w_2$ are supposed to occur.
Boundary effects at the end of the string have to be analyzed
separately, but they represent a finite number of cases (actually I think I forgot one or two such boundary sub-cases in my first analysis below, but it does not really matter).
The definitions are compatible with overlap of occurrences.

There are 4 main cases to consider (ignoring the symetry between $w_1$ and $w_2$):

$w_1\triangleleft
\triangleright\,w_2$
Both words come necessarily together, except possibly at the ends of the string. This concerns only pairs of the form $1^i0$ and $01^i$, or $0^i1$ and $10^i$. This is easily recognized by a finite automaton that only checks for lone occurences at both ends of the string to be recognized, to make sure there is a lone occurrence at both ends or at neither end. There is also the degenerate case when $w_1=w_2$: then the language L is obviously regular.
$w_1\triangleleft w_2$, but not $w_2\triangleleft w_1$
One of the 2 words cannot occur without the other, but the converse is not true (except possibly at the ends of the string). This happens when:

$w_1$ is a substring of $w_2$:then a finite automaton can just check that $w_1$ does not occur outside an instance of $w_2$.
$w_1=1^i0$ and $w_2=v1^j$ for some word $v\in\{0,1\}^*$, $v\neq01^i$: then a finite automaton check as in the previous case that $w_1$ does not occur separated from $w_2$. However, the automaton allows counting one extra instance of  $w_1$ that will allow acceptance if $w_2$ is a suffix of the string. There are three other symetrical cases (1-0 symmetry and left-right symetry).

$w_1\triangleleft_2 w_2$
One of the 2 words occurs twice in the other. That can be recognized by an a finite automation that checks that the smaller word never occurs in the string. The is also a slightly more complex variant that combines the two variations of case 2. In this case the automaton checks that the smaller string $1^i0$ never occurs, except possibly as part of $v$ in the larger one $v1^j$ coming as a suffix of the string (and 3 other cases by symetry).
$w_1\triangleright \triangleleft\,w_2$
The 2 words can occur independently of each other. We build
a generalized-sequential-machine (gsm) $G$ that output $a$ when it recognizes an occurrence of $w_1$ and
$b$ when recognizing an occurrence of $w_2$, and forgets everything
else. The language $L$ is regular only if the language $G(L)$ is
regular. But $G(L)=\{w\in\{a,b\}^*\mid\ \mid w\mid_a=\mid w\mid_b\}$ which is clearly context-free and not regular. Hence $L$ is not regular.
Actually we have $L=G^{-1}(G(L))$. Since regular languages and context-free languages are closed under gsm mapping and inverse gsm mapping, we know also that $L$ is context free.

One way to organize a formal proof could be the following. First build
a PDA that recognizes the language. Actually it can be done with a
1-counter machine, but it is easier to have two stack symbols to avoid duplicating the finite control. Then, for the cases where it should be a FA, show
that the counter can be bounded by a constant that depends only on the
two words. For the other cases show that the counter can reach any
arbitrary value. Of course, the PDA should be organized so that the
proofs are easy enough to carry.

Representing the FA as a 2-stack-symbols PDA is probably the simplest representation for it. In the non-regular case, the finite control part of the PDA is the same as that of the GSM in the proof sketch above. Instead of outputting $a$'s and $b$'s like the GSM, the PDA counts the difference in number with the stack.


Introduction to Algorithms (CLRS) Ex 5.2-5 solution

For a permutation $\pi$, let $\pi(i\;j)$ be the permutation obtained by switching the places of elements $i$ and $j$. Since $\pi(i\;j)(i\;j) = \pi$, we can partition the set of all permutations over the elements of $A$, into $n!/2$ pairs $\{\pi,\pi(i\;j)\}$.

Consider what happens to $A$ after permuting by $\pi$ and by $\pi(i\;j)$. In exactly one of these cases, the pair $(i,j)$ is an inversion. Therefore the pair $(i,j)$ is an inversion for exactly $n!/2$ of the permutations, i.e., with probability exactly $1/2$.


techniques for finding relevant words in a huge list of strings

This is still an open problem. You can use some techniques like Stemming the words of the strings and counting them called Bag of Words Approach. Most occurring words comes most of the time are in your relevant words list.

However, you would find that non-informative words like 'the', 'is' are coming most of the time in the answer. Simplest way would be to create a dictionary of stop words of english or of the language that would include words that can be discarded. It can contain prepositions, conjunctions, pronouns, articles or may be frequent verbs, as according to your requirements. You can use a Trie for creating this fast lookup dictionary.

However, there is another approach that would find the words that are most occuring. It is called TF/IDF. This is used when you have different documents/strings to compare to each other. It gives you a value for each word that would be proportional to how much it occurs in this document but not in other documents. So words like 'the', 'is' would have comparatively less value. However, if your strings have words like Aluminium in most of them, it would also be having low value. so use it with caution.

Another thing that i would like to point out about the use of TF/IDF is that you would have to divide your data into some parts, to compare to each other. TF/IDF would give result for each of these parts. Lets say if you take each of your string as one part, then it would give you a huge set of key-words since you have a huge set of strings. It would be better to randomly partition your huge-set-of-strings into say 2 or 4 or 8 parts and then find keywords for each part and then take either intersection or union.

The trick is to use different methods and use one that gives the best results.

For spelling mistake you can create a BKTree, that would allow you to find how much two words differ in their spelling mistakes. If you add this approach, it can give you better or worse results. For e.g. if you allow words with one difference acceptable, it would treat bat and cat the same. But it would also take care of Aluminium and Allminium.


Analysing worst-case time complexity of quick-sort in different cases

The usual rule here is only one question per post.

Link [2] doesn't say that random pivot and median pivot lead to $O(n^2)$ time complexity.

The median of first, middle, and last element is not the median of the whole array.  Writing "median pivot" is probably a bad idea, unless you have carefully specified what that's a median of.

Link [1] says that taking the median of all elements leads to $O(n \log n)$ time complexity.  That's different than taking the median of first, middle, and last.  Also, it's rare for practical implementations to take the median of all elements, as that link already states.


What is the difference between following two finite automata?

As many have pointed out in the comments, your automata is non-deterministic. There are two paths you could take from q0 when you read a 1. When running a non-deterministic automata, you need to keep track of all possible paths and see if any of them end up in an accepting state. If you don't keep track of all different possible states you could be in, your solution might never accept any string, if it choses the looping 1 all the time, never leaving q0.

Converting a non-deterministic finite automata (NFA) to a deterministic finite automata (DFA) can be done using a simple algorithm. It's quite slow, but for small examples, it's no problem doing it by hand. There are good videos explaining how to do this in slightly different ways.

The main idea is that you build a table of all possible states you could be in.
For your NFA, I'll label the nodes q0, q1 and q2 from left to right, starting at q0.

At q0 we can reach q0 or q1 when reading a 1.
At q0 we can reach q0 when reading a 0.

That's the first step. Now we have multiple states at the same time. We already did q0 so we have the (q0 or q1) state left.

When reading a 1 from (q0 or q1) we can end up in (q0 or q1). q0 can reach (q0 or q1), and q1 cannot reach anywhere.
When reading a 0 from (q0 or q1) we can end up in (q0 or q2). q0 can loop back to itself, and q1 can reach q2.

And lastly, the (q0 or q2) state.

When reading a 0 from (q0 or q2) we can end up in q0. q2 doesn't have any outgoing edges, and q0 can only reach itself.
When reading a 1 from (q0 or q2) we can end up in (q0 or q1). q2 doesn't have any outgoing edges, and q0 can reach (q0 or q2).

Those are all our possible state transitions in the NFA.

Our list of states used in the transitions above are:

q0
(q0 or q1)
(q0 or q2)

The edges are:

q0 + 0 -> q0
q0 + 1 -> (q0 or q1)
(q0 or q1) + 0 -> (q0 or q2)
(q0 or q1) + 1 -> (q0 or q1)
(q0 or q2) + 0 -> q0
(q0 or q2) + 1 -> (q0 or q1)

You can see that this is the bottom graph in your question, with the states renamed.

It's worth noting that in real life regex engines, NFA's are used because this conversion is very expensive for large automata. It's cheaper and safer to keep track of all states instead of doing the conversion. One notable example is the RE2 library. Most other implementations use backtracking, which is O(2^n) for an n-length string. RE2 is exponential in the expression length, but linear in input. Developers write the expressions, attackers write the input.


What mathematical guarantees gives alpha-beta pruning?

For a complete reference you can check An Analysis of Alpha-Beta Priming
If I am not misunderstanding eq 15 and 16 apply to your case.


Here's a sketch: you seem to be on the right track. Let $L\in BPP^{BPP}$ be decided by a BPP machine $M$ that makes queries to an oracle $A\in BPP$ decided by a $BPP$ machine $M'$. Let $E$ be the error for $M$, $E'$ the error for $M'$ (that is, the probability that the BPP machines fail is at most $E, E'$). We will choose $E, E'$ appropriately via error reduction.

Now, fix a string $z$ to use as randomness for all queries to $M'$. There are at most polynomially many queries to $M'$, say at most $|x|^k$, since $M$ is a ppt TM. Thus, $$\operatorname{Pr}[\text{an error occurs in some query to } M']\le |x|^k\cdot E'$$ So the overall probability of error by $M$ in deciding $L$ is at most $|x|^k\cdot E' + E$, so if we choose $E=\frac{1}{6}$ and $E'=\frac{1}{6|x|^k}$ (which we may do by the standard BPP error reduction), we get an overall probability of error $\le\frac{1}{3}$, so the procedure described is a $BPP^P\subseteq BPP$ procedure.

By the same proof we have the more general statement that $BPP^{BPP^A}\subseteq BPP^A$.


Since L is in P, you can answer the word problem in polynomial time. To show that L is in NP as well, we need to provide a polynomial checking relation $R$ such that

$$ w\in L \Leftrightarrow \exists y.(|y|\le |w^k| \text{ and } R(w,y))$$

Now Prof. Cook says to take a very simple $R$. For every $w$ in $L$, no matter what $y\in \Sigma^*$ you take, $R(w,y)$ is true and for every $w$ not in $L$, $R(w,y)$ is false, regardless of the $y$. This is a polynomial time relation, since we can decide whether $w\in L$ or not in polynomial time (since $L \in P$), without looking at $y$ at all. And as any $y$ works, there are also some $y$ that are short enough to satisfy the length restriction in the above definition.


Path in directed, weighted, cyclic graph with total distance closest to D?

The problem is NP-hard, by reduction from subset sum (given weights $w_1,\dots,w_n$, take a graph with $n$ vertices and two edges from vertex $i$ to vertex $i+1$, one of weight zero and one of weight $w_i$).

One algorithm is to simply enumerate all paths up to a certain length (say, up to length $2d$, if all edge weights are non-negative).  This can be done by enumerating all paths of length $i$; then enumerating all paths of length $i$ by concatenating any path of length $i$ followed by any edge out of the final vertex of that path; and so on, for $i=1,2,3,\dots$  Of course, the algorithm takes exponential time, but it is an algorithm.


Checking Divisibility Using Minimal Bits

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

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

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


Let $E = \{ZZ,WW,ZW,WZ\}$. A binary random variable is a mapping $X\colon E \rightarrow \{0,1\}$. The probability of an event, say $X=0$, is defined as
$$ \Pr[X = 0] =\frac{|\{e \in E : X(e) = 0\}|}{4}. $$
For example, let $C_1(ZZ)=C_1(ZW) = 0$, $C_1(WZ)=C_1(WW) = 1$. Then $\Pr[C_1=0]=1/2$.

Two (binary) random variables $X_1,X_2$ are independent if for every $b_1,b_2 \in \{0,1\}$,
$$\Pr[X_1 = b_1 \text{ and } X_2 = b_2] = \Pr[X_1 = b_1] \Pr[X_2 = b_2]. $$
For example, if $C_2(ZZ) = C_2(WZ) = 0$ and $C_2(ZW) = C_2(WW) = 1$, then you can check that $C_1$ and $C_2$ are independent, by checking that $\Pr[C_1 = b] = \Pr[C_2 = b] = 1/2$ and $\Pr[C_1 = b_1 \text{ and } C_2 = b_2] = 1/4$. On the other hand, $C_1$ and $C_1$ are not independent since $\Pr[C_1 = 0 \text{ and } C_1 = 0] = 1/2$.

Similarly you can define when more than two random variables are independent. It should be clear that there are no three binary random variables $X_1,X_2,X_3$ with $\Pr[X_1 = 0] = \Pr[X_2 = 0] = \Pr[X_3 = 0] = 1/2$ which are independent, since that would imply $\Pr[X_1 = X_2 = X_3 = 0] = 1/8$, which is impossible (the only values that $\Pr$ can obtain are $0,1/4,1/2,3/4,1$). On the other hand, any three constant random variables are independent.

A set of random variables is $k$-wise independent if any $k$ of them are independent. The question asks you to find three random variables $X_1,X_2,X_3$ so that any two are independent, but all three aren't. My hint is that there is a solution with $X_1 = C_1$ and $X_2 = C_2$.


Number of automorphism for clique of 6 vertices minus two non adjacent edges

It's not hard to check that $(1\; 2)$, $(1\;3)(2\;4)$, and $(5\;6)$ are all automorphisms of the graph. Considering the degrees of vertices, this shows that the orbits of the automorphism group $G$ are $\{1,2,3,4\}$ and $\{5,6\}$. According to the orbit stabilizer theorem, $|G| = 4|G_1|$. Once again, it's not hard to check that $(3\;4)$ and $(5\;6)$ are automorphisms in $G_1$, and consider degrees and the property of being connected to $1$ shows that the orbits of $G_1$ are $\{3,4\}$ and $\{5,6\}$. It is not hard to check that all 4 permutations respecting these orbits are in $G_1$, and so $|G_1| = 4$. We conclude that $|G| = 16$.

Informally, $1$ can get mapped to any of $1,2,3,4$. Assuming that $1$ gets mapped to itself (without loss of generality), we see that $2$ has to get mapped to itself, $3$ to one of $3,4$, and $5$ to one of $5,6$. These are the only constraints, so in total there are $4\cdot 2\cdot 2 = 16$ automorphisms.


Equality testing of arrays and integers in a procedural language

Integers are stored in one word of memory and there is a primitive machine code instruction for testing their equality. Most programming languages lift this instruction to the syntax, as with i == j in Java (where i and j are of type int).

Arrays are stored in multiple contiguous words in memory. In order to test the equality of two arrays, the program needs to iterate through each pair of  memory locations and test the equality of the elements stored in them.

Some programming languages hide the distinction between these to operations by allowing the syntax == to be used for testing the equality of two arrays (one can do this in C++, for instance, or Ruby). Other programming languages, such as Java, do not.


What learning algorithm is appropriate for predicting one time-series from another?

If I understand your question right, you want to model two stochastic processes, where the 'student' process is driven by the 'teacher' process.

A hidden Markov model can represent such a relationship, but is restricted to a discrete state space. This means that you can only model a finite set of points on your map rather than continuous (x/y) coordinates. A Linear Dynamical System might suit better to your problem.

You could also use recurrent neural networks to model your system.


Proving that an algorithm $A$ runs in $\Theta(f(n))$ time in the worst-case

Your observations are correct for the worst-case time complexity, which is the most common measure of time complexity, other than a small point – usually we prove an upper bound of $Cf(n)$ and a lower bound of $cf(n)$, where the constants $c,C$ need not match (and usually aren't explicit, being instead hidden in asymptotic notation).

There is a subtlety here – as you correctly mention, formally speaking we need a hard instance for every $n$. Usually this is not a problem since instances can be "padded" – if we have a construction that only works directly for even $n$, perhaps we can pad it to get a construction that also works for odd $n$. But in computational complexity we are sometimes considering more general and abstract cases in which this is not the case, and the only guarantee is that the running time is $f(n)$ for infinitely many $n$. We denote this by $\Omega^\infty(f(n))$ or $\Omega_\infty(f(n))$. This is the negation of $o(f(n))$, that is, all we can conclude if $o(f(n))$ doesn't hold.


Maximum waiting time between events such that k events are not missed

The solution was using a binary search on the time between laps and since every checking of the value is linear time, computing the solution is cheap. Thank you anyway.


Since the graph is complete, you can connect each vertex with any other vertex. Note that each vertex must be connected to the tree and hence has an incident edge in the tree.

Assuming all weights are positive, choose a vertex $v$ with the minimum weight and construct the tree from all incident edges with this vertex. The tree is hence a star graph with $v$ the center of the star.

Assuming the numbers can be negative (which is not specified in you question), then distinct two cases. the first one, all weights are negative. Hence, it turns into the case above, since  all products have to be positive.

The second case is where we have at least one negative weight and one positive weight. Let $u$ be a vertex with the maximum positive weight. Let $v$ be a vertex with negative weight with maximum absolute value among all negative weights. connect $u$ to all vertices with negative weights and $v$ to all vertices with positive weights. Be aware of not adding the edge between $u$ and $v$ twice.

Try to proof the correctness as an exercise. It should be clear using elementary math and an exchange argument.


I have tried this question to the best of my ability. Feel free to ask for any clarification or raise any doubts in the comments.

Apart from issues like nullifying the effect of some useful transitions, the problem in your solution is that you've started out at a rejecting state, but unless the string has encountered $bb$ and then $cba$ and subsequently $cc$, it should be accepted.
I've laid out the transitions in a step wise manner, jumping about the states to "reset" the logic that proceeds to rejecting state.
Update:
You can think about the automata as comprising of $3$ parts. q0,q1 check for first occurrence of $bb$. q2,q3,q4 detect the string $cba$. Finally, q5,q6,q7 test for the string $cc$.


Your induction hypothesis is insufficient. In the hypothesis, you are just proving that the last element of the array has the maximum value. However, you have to prove that the resulting array is sorted. Therefore, your induction hypothesis should be the following:
Hypothesis: At the end of 't' iterations of the outer "for" loop, the "n-t" highest elements of the array are in the sorted order and they occupy the indexes from 'n-t+1' to 'n'.
Base case: For 't = 1', the induction hypothesis says that at the end of the first iteration of the outer "for" loop, the algorithm gives the highest element at the index 'n'. And, you can easily prove this statement.
Induction Step: At the end of 't+1' iterations of the outer "for" loop, the "n-t+1" highest elements of the array are in the sorted order and they occupy the indexes from 'n-t' to 'n'. Again, you have to prove this step using the earlier mentioned hypothesis -- for 't' iterations.
This proves the induction hypothesis. And, now you can simply say that at the end of 'n' iterations of the outer "for" loop, all elements of the array are in the sorted order and they occupy the indexes from '1' to 'n'.


How to decide the scope of the following lambda expression?

The correct answer is:

  (λx.x (λuv.v) (λab.a) (λcd.c))

If I add in parethenese to disambiguate application, it becomes.

  (λx.((x (λuv.v)) (λab.a)) (λcd.c))


How to create a cellular automata rule to achieve a desired pattern?

One way to achieve what you describe would be to encode your problem as a SAT instance, with clauses decribing the desired initial and final pattern and the state transitions under the (fully or partly unknown) evolution rule, and then let a generic SAT solver look for a solution.

In fact, at least for certain classes of rules (specifically, two-state isotropic rules on the Moore neighborhood, a class that includes e.g. Conway's Game of Life), you won't even need to implement this yourself, since there is an existing program called LLS that can do exactly that.  While a full tutorial on how to use LLS is beyond the scope of this answer, one of the things it can do is take a partial rule string (i.e. a description of the state transition rule, with some transitions left unspecified) and a list of grids fully or partially describing the evolution of a pattern over several generations, and search for a solution that fills in the unspecified bits of the transition rule and/or the pattern.


How to read out a double negation in propositional logic

The answer by @D.W. is valid in classical logic, however if you are on the intuitionistic side, then you can't eliminate double negation (~~).

I'd read the formula as 'It is not true that my program is not correct'.


How to work out physical address corresponding to logical address?

You are correct in your reasoning that the pages are $256$ bytes and that the physical memory capacity is $4096$ bytes.

However, there are errors after that.

The offset is the distance (in bytes) relative to the start of the page.  I.e., logical_address mod page_size.  The bits for this portion of the logical address are not translated (given power of two page size).

The logical (virtual) page number is number of (virtual) page counting from zero.  I.e., $$\frac{logical\_address}{page\_size}$$

As you noted, the physical page is determined by the translation table, indexed using the logical (virtual) address.

Once the physical page number had been found, the physical address of the start of that page is found by multiplying the physical page number by the page size.  The offset is then added to determine the precise physical address.  I.e., $$(physical\_page\_number \times page\_size) + offset$$

So a logical address of, e.g., $508$, with $256$ byte pages would have an offset of
$$508 \mod 256 = 252$$
The logical/virtual page number would be
$$\frac{508}{256} = 1$$
With the given translation table, logical page $1$ translates to the physical page number $2$.  The physical address would then be
$$physical\_page\_number \times page\_size + offset = 2 \times 256 + 252 = 764$$


How many telescoping constructors will I have?

You'll need $2^n$ constructors.  You need one constructor for each possible subset of optional parameters.  There are $2^n$ such subsets.  You have $n$ things, and there are $2^n$ possible ways to choose a set containing some number of those things.

For each subset of optional parameters, you'll write down a constructor for that subset; the arguments to that constructor will be fully determined (they must include all of the required parameters, and all of the optional parameters in the chosen subset, in the specified order).

That said, in Java, the "create many constructors" pattern doesn't actually work, for reasons having nothing to do with combinatorics or the number of constructors.  You might notice that the type signature of the following two constructors is identical:

public Food(int id, String name, int calories, int servingSize) { ... }
public Food(int id, String name, int calories, int fat) { ... }

and that's not allowed in Java, because when the compiler sees an attempt to invoke the constructor (to instantiate the object) with a list of 4 parameters of type int, String, int, int, it won't know which of those two choices to choose.  The approach only works if all of the optional parameters have different, incompatible types.