Largest weight-limited connected subgraph: NP-complete?

The decision version is NP-complete so the problem is NP-hard. The following is a reduction from 3SAT.

For an instance of 3SAT with $n$ variables $x_1,\ldots, x_n$ and $m$ clauses, create a graph as follows:

For each variable $x_i$ create two vertices $v_i^0, v_i^1$ with cost $1$. Create an edge between each two vertices of these $2n$ vertices, i.e. the $2n$ vertices induce a clique.
For each variable $x_i$ create a vertex $v_i$ with cost $0$, and two edges $(v_i, v_i^0)$ and $(v_i,v_i^1)$.
For each clause $c_l$ with variables $x_i,x_j,x_k$, create a vertex $u_l$ with cost $0$, and three edges $(u_l, v_i^{b_i})$ (if the literal is positive, $b_i=1$, otherwise $b_i=0$, and the same below), $(u_l, v_j^{b_j})$ and $(u_l, v_k^{b_k})$.

Then we ask if there is a connected vertex set $T$ with size at least $2n+m$ and the sum of cost is no more than $n$.

Now if the instance of 3SAT has a feasible solution where $x_i=b_i$, we can make $T$ consist of all $v_i$s, $u_l$s and $v_i^{b_i}$s.

On the other hand, if $T$ exists, because you can afford at most $n$, at most $n$ vertices among $v_i^0, v_i^1$s are chosen, thus all $n+m$ vertices with cost $0$ must be chosen. This means:

Since $v_i$ is chosen, at least one vertex of $v_i^0$ and $v_i^1$ is chosen. Because at most $n$ vertices among $v_i^0, v_i^1$s are chosen, exactly one of $v_i^0$ and $v_i^1$ is chosen. We assign $x_i$ accordingly.
Since $u_l$ is chosen, at least one corresponding literal has value $1$, thus the clause is satisfied.

So the instance of 3SAT has a feasible solution.


Time complexity described by recurrence relation

If we draw recurrence tree for this relation than it would be something like following:

         T(n)            -> Cost: n
    /     |    \
T(n/2)  T(n/3)  T(n/6)   -> total cost: n/2 + n/3 + n/6 = n
   .
   .
  T(1) --------------->  highest depth which is about lg(n).

So, there are $lg(n)$ levels and every level has at least cost $n$ so $T(n) = \mathcal{O}(n\lg{n})$.

Now let's conjecture that $T(n) = \Omega(n\lg{n})$ and try to prove it.

We will prove this by induction.

Let's assume that $T(n) \ge c.n\lg{n}$ for some $c > 0$.

$T(n+1) = T(\frac{n+1}{2}) + T(\frac{n+1}{3}) + T(\frac{n+1}{6}) + n+1$

$\therefore T(n+1) \ge c.\frac{n+1}{2}.\lg{\frac{n+1}{2}} + c.\frac{n+1}{3}.\lg{\frac{n+1}{3}} + c.\frac{n+1}{6}.\lg{\frac{n+1}{6}} + n+1$

$\therefore T(n+1) \ge c.(n+1)\lg{(n+1)} + (n+1 - c.(n+1)(\frac{\lg{2}}{2} + \frac{\lg{3}}{3} + \frac{\lg{6}}{6})$

$\therefore T(n+1) \ge c.(n+1)\lg{(n+1)} + (n+1 - c.(n+1)(\frac{\lg{432}}{6}))$

$\therefore T(n+1) \ge c.(n+1)\lg{(n+1)}  \space \space \space  $

$[\because (n+1 - c.(n+1)(\frac{\lg{432}}{6}) < 0, \space \text{for } c\ge 1]$

Hence, we have proved that $T(n) = \Omega(n\lg{n})$ but we also have $T(n) = \mathcal{O}(n\lg(n))$.

So, that implies $T(n) = \Theta(n\lg{n})$.


Superset of another language and recognizability of turing machines

If a machine halts on all strings then it halts on some string. Therefore $L_2 \subseteq L_1$.

If a machine halts on some string but not on all strings then it is in $L_1 \setminus L_2$. Since there are such machines, $L_1 \subsetneq L_2$.

The language $L_2$, usual known as TOT, is well known to be $\Pi_2$-complete. In particular, it is neither r.e. nor co-r.e. This can also be proved directly by reducing both the halting problem and its negation to $L_2$:

Given a Turing machine $M$ and an input $x$, construct a Turing machine $M'$ which erases its input and then runs $M$ on input $x$. Then $M$ halts on $x$ iff $M' \in L_2$.
Given a Turing machine $M$ and an input $x$, construct a Turing machine $M'$ which on input $n$ simulates $M$ on $x$ for $n$ steps, and loops if $M$ halted within $n$ steps. Then $M$ doesn't halt on $x$ iff $M' \in L_2$.


Quadratic probing maximum load factor with $c_1 = c_2 = 0.5$ to guarantee successful insertion

For the case you describe ($c_1=c_2=1/2$, $m=2^k$), you can reach a load factor of 1. The probe sequence touches all the cells in the table.

As a practical matter, you probably don't want to get really close to a load factor of 1, as the probing can take $O(n)$ time.


how to formally arrive at a correct EBNF grammar of a language

Your informal description of your language could certainly be made more precise, in the same way as you could make the description of any (mathematical) set more precise until you've written the description out in mathematical notation. In that sense, EBNF is similar to what you get when you recast an informal description of a language into a mathematical formalism. (EBNF doesn't quite qualify, but the BNF formalism which inspired EBNF is a precise formalism.)

In between the formal description of a language and the practical question of building a parser for the language, a number of practical issues need to be dealt with, many of them having to do with the way a string of characters is grouped into meaningful tokens in the concrete representation of the language. In other words, questions like "where can spaces and newline characters be placed?" "Can I insert comments into an expression?" and so on. It's possible to write these into a formal description of a language, but the end result is often not particularly useful for the casual reader because the high-level structure of the language is overwhelmed by pesky details.

I note in passing that your grammar requires that AND and NOT appear with precisely one space preceding and following, while no spaces are allowed around the >= operator (and friends). That means that several of your examples don't match the EBNF. For example, time >= 2020-01-09 would have to be written as time>=2020-01-09 and response:success AND NOT os:windows as response:success AND  NOT os:windows (with two spaces between AND and NOT). I doubt that was your intent, and I don't say this to criticise; just to point out how tricky it can be to get the details right, so that it can actually be used to construct a concrete parser, and still make the grammar usable for human readers. The usual approach is to separately formalise the division of the text into lexemes ("tokens") and the syntactic structure of the language, which treats the inputs as a stream of tokens rather than as a stream of undifferentiated characters. That's by no means formally necessary, and a lot of the applications of EBNF do in fact attempt to be precise to the character level, but a close examination of these EBNF applications might reveal the practical limitations of this strategy.

As I said in a comment, for any language for which a context-free grammar exists, there are an unlimited number of other context-free grammars which derive the same language. However, the question of whether two context-free grammars derive the same language is undecidable; no algorithm exists which can always correctly make that determination. Consequently, it is also impossible to enumerate all the grammars which could derive a given language (however that language is given).

In addition, there are competing mathematical formalisms which could be used to describe a language. After all, a language is a set, and any mathematical expression which precisely defines a set is a possible formal language description. (Some of these will be more practically usable than others.) So there's no way to say whether a procedure exists to generate a description in one formalism from a description in another formalism without know what, exactly, the nature of the two formal systems is. Sometimes it will be possible, other times not.

If you only want to know if a given text is in a language, then any of the unknowable infinitude of possible grammars for that language will suffice, although it's better if the grammar formalism used is computationally tractable. But most of the time, you don't just want to know that a text is in a language. (A C "compiler" whose only possible output is one of the messages "yes, that is a well-formed C program" and "no, that is not a well-formed C program" is unlikely to attract many paying customers, even if its judgement is 100% correct.) In most applications, you want to parse the language in order to reveal the syntactic structure of a valid text. To do that, your grammar should reflect the syntactic structuring you have in mind, and not all of the possible grammars for the language do.


Solve Integer Factoring in randomized polynomial time with an oracle for square root modulo $n$

Where in the analysis of the algorithm does the number of squares ("quadratic residues") come in? As to their number, you know that $a^2 \pmod{n}$ is always a square, and every number has up to $4$ square roots. That should help you show that there are a lot of squares.
Try to prove that your algorithm works, and see if anything is missing.
Suppose $n = pq$ ($p,q$ different primes) and $(x,n)=1$. Then if $x$ is a square, then $x$ has two square roots modulo $p$ and two square roots modulo $q$, and so four square roots in total by the Chinese remainder theorem. We know that a number $x$ such that $(x,p)=1$ has at most two square roots since the polynomial $t^2-x$ can have at most two roots modulo $p$. If it has one square root $y$ then $-y$ is another one.


Convolutional Neural Network Feature Engineering?

Your questions phrasing is a bit confusing. I'll try to answer my interpretation of your confusion.

I think the base of your confusion relays on the assumption that 2D convolution receives a 2 dimensional array as input.
This is not true - The input of a 2D convolution layer is a 3 dimensional array.
At the beginning you have an image which can be greyscale/RGB, let's consider an RGB image of 28x28, this image is represented as a tensor of 3x28x28 (greyscale will be 1x28x28), generally - colors x width x height as the colors can exceed 3 for opacity etc.
A 2D convolutional layer with patch size 5x5 will be a applied over each patch of size 5x5 of the images over all colors.
To sum it up, slice the image to cubes of patch size (which overlap according to the stride parameter) each of these patch is taken with all it's colors as the input to the filter.

The process I've described above is the application of a single filter over the input. The result of "running" the filter over the input is a matrix (as the dot product of each patch of the image with the filter is a scalar).
Now, take 32 such filters stacked on top of the other, the output will be 32 matrices where each matrix is the application of a different filter over the input.

As far as dimensions go, let's assume you apply 5x5x32 over a 1x28x28 image (without padding & stride=1) you'll have: $\frac{input\ size-patch\ size}{stride}+1$, where I assumed everything is symmetrical for both axises.
So you have output of $\frac{28-5}{1}+1=24$, which means the second layer is of size 32x24x24.

You can either think of the second layer as an "image" of size 24x24 with 32 "colors" which is weird but some people do it, or you can think about everything in terms of 3 dimensional arrays and understand exactly how a filter is applied over each 3 dimensional array.

Why is this referred to as filters?

Let's consider the case where you apply a 2D convolutional layer with parameters 5x5x1. What does this layer actually do? How does it look?
(consider the case where your images are greyscale for simplicity), The layer is actually a dot product of each patch of size 5x5 with a 2D weight matrix of size 5x5. Organized to form a 2 dimensional array of results (which is the output layer).
The 5x5 weights matrix is called "filter". You can think of it as a gaussian for a moment, the 5x5 weight matrix is applied over each patch of the image thus blurring the image. This is applying a gaussian filter over the image.
Now instead of a gaussian filter, you learn the weights and have a general filter.
Now consider a layer of 5x5x32, it is the same, but with 32 different filters.


Overfitting in Machine Learning Algorithms

Yes, they can overfit too.  Overfitting is especially a risk when the number of features is much larger than the number of samples in the training set.


How to build a TM which decides $L_k := \{(\langle M \rangle ,x)\in HP : |(\langle M \rangle ,x)| \le k \}$

You cannot construct an explicit algorithm/TM which will decide the language $L_k$. Regarding your attempt at the proof: you are right that there is no guarantee that the configuration will repeat because these machines are not given to be space bounded.

The TM $M_k$ to decide $L_k$ will have all the tuples (which are finite in number) which are accepted hard coded in it. The TM will basically perform a search in a look up table: if that tuple is found then accept it, else reject.
We don't care how these tuples are actually obtained.

We can perhaps even prove that a general method to construct such TM $M_k$ for each $L_k$ cannot exists: Suppse there exists, then for a given input $<M,x>$, find the length of input, let it be $k$ and construct the TM $M_k$. Simulate $M_k$ over $<M,x>$. This will act as a decider for Halting Problem: which we know is undecidable. Hence, the assumption that we can have such a method is false.


Is an inﬁnite union of context-free languages always context-free?

The union of infinitely many context-free languages may not be context free. In fact, the union of infinitely many languages can be just about anything: let $L$ be a language, and define for every $l \in L$ the (finite) language $L_l = \{ l \}$. The union over all these languages is $L$. Finite languages are regular, but $L$ may not even be decidable (and thereby definitely not context-free).

The closure properties of context-free languages can be found on Wikipedia.


Name for sorting algorithm "while not sorted, swap the FIRST unordered pair"

In more detail, this variant of bubble sort finds the leftmost pair of adjacent items that are in the wrong order. Then it swaps those two items. This operation of "find and swap" is repeated until the given list is sorted. In other words, this variant of bubble sort swaps the items in the leftmost inversion of the given list repeatedly until the given list is sorted. (Note the two items in the leftmost inversion must be adjacent).

There is no standard or popular name for this variant of bubble sort, or so I believe.

I would call it left-bubble sort, a name that captures its conceptual intention. We could also have right-bubble sort, which swaps the items in the rightmost inversion repeatedly until sorted. We could also have random-bubble sort, which swaps two randomly-selected adjacent items that are in the wrong order repeatedly until sorted. If we do not even require the two items to be adjacent, we can have random-swap sort. Depending on how the inversion is selected randomly, "random-swap sort" can become bogo-sortopt, bozo-sortopt, and bozo-sort+opt that  appear in this article.

The above description of left-bubble sort does not specify how to find the leftmost inversion in each iteration. A naive implementation may always comparing the first two items, then the next two items and so on until it finds the first inversion or stops. We can observe that the initial part of the list during the left-bubble sort is sorted. Since there cannot be any inversion in the initial part of the list, we can optimize the implementation by just comparing the item that was just moved to the left with the item right before it without comparing the initial adjacent items.

Whether we use the naive implementation or the optimized implementation above, left-bubble sort behaves exactly the same as the simplest insertion sort, in terms of the states the given list goes through until sorted. The simplest insert sort here corresponds to the first pseudocode at this Wikipedia page, which is implemented in Programming Pearls (2000) by Jon Bentley.

Here is an illustration of the states produced by left-bubble sort.

4, 3, 2, 1    <- 4 is considered inserted into the expected place.
3, 4, 2, 1    <- 3 is inserted into the expected place
3, 2, 4, 1
2, 3, 4, 1    <- 2 is inserted into the expected place
2, 3, 1, 4
2, 1, 3, 4
1, 2, 3, 4    <- 1 is inserted into the expected place

In particular, left-bubble sort builds the final sorted array (or list) one item at a time, which is the defining characteristic of "insertion sort" according to that Wikipedia page. We can thus treat (the optimized version of) left-bubble sort as another name for the simplest insertion sort.


Job Shop Problem: How do you get an ordered sequence of operations from the disjunctive acyclic graph?

The graph consisting of all vertices corresponding to a particular machine and the induced chosen edges form a directed path. This path tells you exactly which jobs to run on that machine and in what order.
The length of the longest weighted path from u to a job tells you exactly when you can start processing that job.


Does Google's PageRank count as a sorting algorithm?

The answer depends on what you mean by a sorting algorithm. The usual meaning is:

  A sorting algorithm is an algorithm that gets a list $L$ of comparable objects, and sorts them in (say) nondecreasing order. The algorithm could only work for a certain class of objects.

If you use this definition, then PageRank isn't a sorting algorithm. But it's up to you.


Why pointer dereference was once called "decrement"?

OK, I found a lead.  Just needed to know what to search for: https://en.wikipedia.org/wiki/CAR_and_CDR

  The 704 and its successors has a 36-bit word length and a 15-bit address space. These computers had two instruction formats, one of which, the Type A, had a short, 3-bit, operation code prefix and two 15-bit fields separated by a 3-bit tag. The first 15-bit field was the operand address and the second held a decrement or count. The tag specified one of three index registers. Indexing was a subtractive process on the 704, hence the value to be loaded into an index register was called a "decrement".[2]:p. 8 The 704 hardware had special instructions for accessing the address and decrement fields in a word.[2]:p. 26 As a result it was efficient to use those two fields to store within a single word the two pointers needed for a list.[3]:Intro.

Still, this memory model is very foreign to me, so I wouldn't mind if anyone explained how this would work.


Bubble sort: how to calculate amount of comparisons and swaps

Number of swaps: The number of swaps in Bubble sort is exactly the number of inverted pairs, i.e. the number of pairs $(i,j):i < j\wedge s[i]>s[j]$. This number of pairs should be $(n/2-1)+(n/2-2) + ... + 1$ which is of the order of $n^2$.

Number of comparisons: This is of the order of $n$ times the number of passes through the list, which is of the order of $n$, as the element N needs to get to the end.

Therefore you have $\Theta(n^2)$ comparisons and swaps.


Are regular languages closed against an intersection that keeps words with the same number of ones?

Let
$$
  L = \{ x \in L_1 \mid \text{there exists }y \in L_2 \text{ such that } |x|_1 = |y|_1\}
$$
Let $\pi: \Sigma^* \to a^*$ be the homomorphism defined by $\pi(u) = a^{|u|_1}$.
I claim that
$$
  L = L_1 \cap \pi^{-1}(\pi(L_2))
$$
Since regular languages are closed under homomorphisms, inverses of homomorphisms and intersection, it will follow that $L$ is regular.

Proof of the claim.
\begin{align}
  L_1 \cap \pi^{-1}(\pi(L_2)) &= \{ x \in L_1 \mid \pi(x) \in  \pi(L_2) \} \\
  &= \{ x \in L_1 \mid \text{there exists }y \in L_2 \text{ such that } \pi(x) = \pi(y)\}\\
  &= \{ x \in L_1 \mid \text{there exists }y \in L_2 \text{ such that } |x|_1 = |y|_1\} \\
  &= L
\end{align}


What is the big-$O$ notation of a summation of a log?

Recall that the sum of $\log$'s is equivalent to the $\log$ of products.

That is:

$$\log(xy) = \log x + \log y$$

Thus we can change your function:

$$
\begin{align}
\sum_{i=n}^{n+m} \log i &= \log \prod_{i = n}^{n + m} i\\
&= \log (n \cdot (n+1) \cdot (n+2) \cdot \ldots \cdot (m-1) \cdot m )\\
&= \log (m!\ /\ (n-1)! )\\
\end{align}
$$

Then we can similarly use the division rule to get these back out:

$$
\log (m!\ /\ (n-1)! ) = \log (m!) - \log((n-1)!)
$$

Then using Stirling's Approximation we can immediately see:

$$
\log (m!) - \log((n-1)!) = O(m \log m)
$$

You might be able to do better though by taking more precise bounds to get:

$$
\begin{align}
\log (m!) - \log((n-1)!) &\leq em^{m + \frac{1}{2}}e^{-m} - \sqrt{2\pi}(n-1)^{n- \frac{1}{2}}e^{1-n}\\
&= \vdots
\end{align}
$$


Are there other ways to describe formal languages other than grammars?

There are plenty of possibilities. Others have already mentioned automata which offer a rich selection. Consider the following frameworks, too:

Some languages can be defined directly by (co)inductive definitions. For instance, the smallest fixpoint of
$\qquad \begin{align*}
  \phantom{a} \\
  &\phantom{\Rightarrow}\ \varepsilon \in L \\
  w \in L &\Rightarrow aw \in L \\
  aw \in L &\Rightarrow baw \in L \\
  \phantom{a}
\end{align*}$
is the same language as the one described by $(ba\mid a)^*$, the largest fixpoint is $(ba\mid a)^\omega$. Note that such a definition can also be written in calculus or inference rule form:
$ \qquad \begin{align*} \phantom{a}\\
  \frac{}{\varepsilon}, \quad \frac{w}{aw}, \quad \frac{aw}{baw} \\
  \phantom{a}
\end{align*}$
Words define word structures that can be used as models of logical formula. Essentially, every word defines the domain of its positions $D_w = \{1, \dots, n\}$, predicates $P_a : D \to \{0,1\}$ so that $P_a(i) \Longleftrightarrow w_i = a$ for all $a \in \Sigma$, a predicate $<$ that is $<$ from $\mathbb{N}$ restricted to $D_w$ and a predicate $\operatorname{suc} : D_w \times D_w \to \{0,1\}$ that is true if and only if the second parameter is the direct successor of the fist.
So for instance, if $w = aababaab$ then
$ \qquad \begin{align*} \phantom{a}\\
  S_w \models \forall\, i. \forall\, j.\ (P_b(i)\ \land\ \operatorname{suc}(i,j)) \to \lnot P_b(j); \\
  \phantom{a}
\end{align*}$
in fact, this first-order formula defines---via the set of all word structures that fulfill it---the same language as $(ba\mid a)^*$. The corresponding $\omega$-language $(ba\mid a)^\omega$ is described by the LTL formula
$ \qquad \begin{align*} \phantom{a}\\
  \square\,(P_b \to\bigcirc(\lnot P_b)) \\
  \phantom{a}
\end{align*}$
Several equivalences between classic language classes and certain logics are known. For example, FO corresponds to star-free languages, weak MSO to regular languages and MSO to $\omega$-regular languages. See here for references.
Something orthogonal to classic classes are pattern languages. Assume a terminal alphabet $\Sigma$ and a variable alphabet $X=\{x_1, x_2,\dots\}$. A string $p \in (\Sigma \cup X)^+$ is called a pattern. Let $\mathcal{H}= \{\sigma \mid \sigma : X \to \Sigma^*\}$ the set of substitutions. We define the language of a pattern $p$ as
$ \qquad \begin{align*} \phantom{a}\\
  \mathcal{L}(p) = \{\sigma(p) \mid \sigma \in \mathcal{H}\}. \\
  \phantom{a}
\end{align*}$
Note that $\sigma$ is extended to work on patterns; terminal symbols are left unchanged.
As an example, consider $\mathcal{L}(x_1abbax_1)= \{wabbaw\mid w \in \{a,b\}^*\}$.
Note that we allow substitutions to delete variables; some properties of the class of pattern languages are hugely different for deleting vs. non-deleting substitutions. Pattern languages are of particular interest in Gold-style learning.


Difference between Row Major Order and Column Major order

The only difference between Row Major Order and Column Major Order in the case of ANSI C is that the memory access patterns are different.

Suppose we have an array $a[i][j]$ which is stored in Row Major Order and we decide to iterate by columns, then the CPU would take more time to process this set of instruction as compared to the case where we decide to iterate by rows. Using the correct access pattern helps the Operating System use caches more effectively.

However this has no bearing on the running time complexity of the code and for all arrays which occupy space below a certain threshold, the difference would be hardly noticeable.

One final note:

If Row Major Order is taken, then we have $2$ arrays of $a[3][4]$ so each array has $12$ elements. Total no.of elements $= 2*12 = 24$ elements.
If Column Major Order is taken, then we have $4$ arrays of $a[2][3]$ so each array has $6$ elements. Total no.of elements $= 4*6 = 24$ elements.


Why the negative reward function in linear quadratic regulation encourage to be at original state?

Minimizing $s^TUs=s^Ts=\|s\|^2$ minimizes the distance from the origin, because the norm of a vector is its Euclidean distance (https://en.wikipedia.org/wiki/Euclidean_distance) from the origin:

$$\|s\|= \sqrt{s_1^2+s_2^2+\dots+s_n^2} = \sqrt{(s_1-0)^2+(s_2-0)^2+\dots+(s_n-0)^2}$$


Proof for This Greedy Strategy for Equalizing An Array

Actually I am not sure the greedy solution will always give the best solution?

Recall that the change making problem does not work for certain denominations in a greedy way. For example with denominations $1,3,4$ and a goal of $6$ the greedy solution will give $4,1,1$ whereas the optimal solution is $3,3$.

This can be translated into your problem. Start with array $A=[0,6]$ and steps $D=\{1,3,4\}$. Now your greedy solution seems to behave like change making. I am not certain about this, however, as your description does not precisely say by which amount the numbers are incremented. Perhaps your algorithm chooses $[0,6] \to [4,6] \to [7,6] \to [7,7]$ (which is also wrong, anyway).


What is the usage of a decision problem for an optimization problem like the longest path problem?

In complexity theory, we tend to focus on decision problems. They're conceptually simpler and the corresponding function and optimization problems can be reduced to them with only a polynomial loss of efficiency. From a theoretical point of view, polynomial factors are considered "efficient".

Let's take your example of Longest Path.  We know that the longest path has length between 1 and $n$ (where $n$ is the number of vertices), so we can find the actual length of the longest path by doing binary search using a series of queries of the form "Is there a path of length at least $n/2$?", "... $3n/4$?", ... That tells us that the longest path has some length $\ell$.  Now, we can loop through the edges one by one.  Delete the $i$th edge and ask, "Is there still a path of length at least $\ell$?" If there is, go on to the next edge; if there isn't, undelete edge $i$ and go on to the next one.  When this algorithm terminates, we'll be left with a graph that is exactly a path of length $\ell$. We used $\Theta(\log n$) calls to Longest Path to find the length of the longest path, and $O(n^2)$ calls to find the actual path.

The decision problem isn't necessarily "useful" per se: as you observe, the function problem ("Give me a solution", rather than "Is there a solution?") is the one we usually want to solve, practically speaking.


Understanding an upper bound in the analysis of Karger's algorithm

$$(1-P(n))^{O(\log^{2} n)} \le (1-\frac{c}{\ln n})^{\frac{3}{c} \ln^{2} n}$$

First, to get a tighter bound, you should choose $\frac{4}{c}$ or larger, instead of $\frac{2}{c}$ or smaller.

In particular, the probability for $\frac{2}{c}$ is
$$\textrm{Pr}[\textrm{miss any min-cut}] \le O(1).$$
This does not make sense for a probability value.

Second, the larger the chosen coefficient is, the higher the time complexity of the algorithm is (to achieve a tighter bound). That is, there is a trade-off.


What is the rationale behind implicitly widening integer types in numeric operations?

First of all, when you write 200 + 100 the compiler deduces the type for both numbers. It's assigning int which has a width of 32bits on most languages and target architectures, so your 200 was never just 0xC8, it always were 0x000000C8 (on little endian).

Why are we still using 32bits?
My guess is that 32bits is still the sweet spot for avoiding overflows while not using too much memory.

Moving from 32bits to 64bits requires twice the memory, that is trivial, but has some details.

Twice the memory will have to be moved, and the memory copying speed won't increase.
Twice the memory will not only reside on your ram, but also on the cache of your CPU, and while your system may have a lot of ram it still has quite limited cache. Take for example the i7-4790K, quite more powerful and expensive than your average CPU. It says it has 8MB of cache, but that is Level-3 cache, it has 4x32kB data Level-1 cache to use across it's 4 cores, now memory seems expensive.
When I mentioned the Level-1 cache I was only bringing you closer to the real thing. Your CPU operates on it's registers and they are even more limited.

This may seem interesting now: Memory hierarchy

"Most modern CPUs are so fast that for most program workloads, the bottleneck is the locality of reference of memory accesses and the efficiency of the caching and memory transfer between different levels of the hierarchy"

Edit: I forgot to mention that because of the no-overhead backwards compatibility of the amd64 (x86-64) architecture, 32bits operations are done just as fast as 64bits operations, but probably that also applies to 16bits.


$\to_\beta$ is the one-step relation between terms in the $\lambda$-calculus. This relation is neither reflexive, symmetric, or transitive. The equivalence relation $\equiv_\beta$ is the reflexive, symmetric, transitive closure of $\to_\beta$. This means

If $M\to_\beta M'$ then $M\equiv_\beta M'$.
For all terms $M$, $M\equiv_\beta M$ holds.
If $M\equiv_\beta M'$, then $M'\equiv_\beta M$.
If $M\equiv_\beta M'$ and $M'\equiv_\beta M''$, then $M\equiv_\beta M''$.
$\equiv_\beta$ is the smallest relation satisfying conditions 1-4.

More constructively, first apply rules 1 and 2, then
repeat rules $3$ and $4$ over and over until they add no new elements to the relation.


Can one insert non-unique elements into an AVL tree?

A BST (from which the AVL descends) with duplicate keys can have its rotation make nodes with the same key be on both sides of the parent node, in which case, some ambiguity might result. However, you could make your life a whole lot easier and have each node contain a key and the number of times that key had been inserted into the tree, to therefore keep track of successive inserts of successive keys and disambiguate its structure.

You would still insert a node (first by searching for the expected placement for the node) with respect to its key, initialize its count to 0, and towards the end of completing the insert increment that count).


Can a language with some set of higher-order functions like map, fold and filter but without recursion or iteration be Turing complete?

A functional language such as (a fragment of) Agda has:

inductive types (lists, trees, numbers, etc.)
higher-order functions
structural recursion (a generalization of fold and map)

However, such a language is not Turing complete. If we add the fix-point operator, which is a higher-order function

fix_t : (t -> t) -> t

then we can use that to implement general recursion and we have a Turing-complete language. Conversely, in Turing-complete functional language it is possible to implement fix_t, at least in the case t = nat.

So the obstruction to Turing completeness of functional languages is whether they can implement the fixed-point operator. (Partial combinatory algebras from another answer to this question also have the fixed-point operator.)


Is subtype polymorphism a kind of ad hoc polymorphism?

They're definitely different things, which is easier to see with a clearer definition of ad-hoc polymorphism. Quoting from Wikipedia:

  ...ad hoc polymorphism is a kind of polymorphism in which polymorphic functions can be applied to arguments of different types...

So in the definition you've quoted, they're using "on" to mean "passed as arguments", rather than "called from". Ad-hoc polymorphism is available in Java in the form of method overloading. For example BigDecimal has 5 divide(...) methods, all taking different sets of parameters. Other languages have more obvious examples of ad-hoc polymorphism, where there's only one function/procedure, with a list of parameters, and the programmer has to decide what to do with them inside the function/procedure.

Subtype polymorphism, however, is when you can treat an instance of one type as an instance of another type, so anything available on the second type is also avaialable on the first. This is the toString() example you give. toString() doesn't operate on different arguments, but it can be called from different types (because it's defined on Object which everything in Java is a subtype of).


Difference between encoding and modulation in transmission

Modulation: Way to send signals (information) from one place to another. exanmple: you have a carrier wave like a sine wave and your Information signal 10101010 or any analog signal you want to transmit. You simply just change the properties of carrier wave with respect to your signal. Like: AM, FM, ASK, PSK, QAM

Encoding: Somthing else than modulation. It is representation of data. Example: 5Volts could be 1 or 0 according to logic (examples are Unipolar encoding, Bipolar Encoding).


Linear Bounded Automaton that accepts all strings

For Turing machines another problem is also undecidable: whether it accepts any string at all. This is already undecidable for LBA. Basically the proof is by oberving that we can replace a TM accepting string $w$ by a LBA accepting the `trace of the computation' by the TM on $w$. The verification of the trace of the computation does not need more space than the computation itself, and thus can be verified by a LBA.

The question whether a device accepts all strings is already undecidable on a lower level of the Chomsky hierarchy, the context-free languages (CF grammars,or pushdown automata).


Prove Matrix Correspondence is NP-complete

As you mentioned, we can reduce maximum clique problem to this. In fact we can reduce the more general subgraph isomorphism problem to this one easily. Given graphs $G$ and $H$, define $A$ and $B$ as their (undirected) incidence matrices. Then we can see that solving the matrix correspondence tells whether $G$ is isomorphic to some subgraph of $H$, which is an NP-complete problem.


What is the difference between Consensus and Leader Election problems?

This is not a matter of terminology: they're related, but different concepts.

A consensus algorithm is one that allows all the participants in a distributed system to choose a value from a set in such a way that all the participants choose the same value. A solution to the consensus problem is a distributed algorithm that has the following properties:

At the beginning, each participant $i$ has an initial value $v^0_i$.
At the end, all the participants must have the same value: $\forall i, \forall j, v_i = v_j$.
The common final value must be the initial value of at least one of the participants: $\exists i, v_i = v^0_i$.

A leader election algorithm is a special case of consensus algorithm where the set is the set of participants. The leader election problem consists of requiring a leader election whenever there is no leader. If there are failures, this may require running more than one election, because a new election becomes necessary when the current leader fails.

In the absence of failures, if you can solve consensus then you can solve the leader election problem: apply consensus with every participant initially choosing themselves. Conversely, if you can elect a leader, then you can solve consensus by having everybody choose the leader's value. This is often how consensus is solved in practice: choose a leader (using a specialized consensus algorithm), then the leader broadcasts its choice of value each time a consensus is needed.

However, if there are failures, this equivalence no longer holds. There are failure models where it's possible to solve consensus, but not to elect a leader. See Laura S. Sabely and Keith Marzullo, Election Vs. Consensus in Asynchronous Systems, Cornell University technical report, 1995. The gap is that certain failure detectors are sufficient to run a consensus algorithm, so they are sufficient to run a leader election, but they are not sufficient to solve the leader election problem, because they aren't sufficient to detect when a new leader election is needed.


Finding a closed formula for recurrence relation

When you are not sure of whether you get the right answer, you can write a simple program in any of your favorite languages to double check.

For example, for the first function, I became pretty confident that I got the right answer once I had run the following script in Python.

def T(n):
    if n == 1: return 4
    return 2 * T(n // 2) + 4

for i in range(1, 20):
    print(T(2 ** i), 2 ** (i + 3) - 4)

Similarly, I ran the following script for the second function.

def S(n):
    if n == 0: return 1
    return S(n - 1) + 3 ** n

for i in range(20):
    print(S(i), (3 ** (i + 1) - 1) // 2)


Does virtual address space resides in virtual memory?

A virtual address space maps (addresses) in virtual memory. Typically one uses "virtual memory" when discussing the general concept and "virtual address space" for the concrete instance of a virtual memory.

(Virtual memory may be either relatively fast but expensive physical memory/primary storage [with a simple translation of virtual address to physical address and typically byte-granularity of access] or relatively slow but less expensive secondary storage [which typically involves software "translation", I/O processing, and page-granular access].)

In commonly used OSes, each process (but not necessarily each thread) is given a separate virtual address space, giving each process the illusion that it owns the entire machine's (virtual) memory capacity as if it was running on the computer by itself. Such OSes typically reserve a portion of the virtual address space (usually half) for OS use, in a sense providing the OS with its own address space. (Some earlier ISAs, e.g., Clipper and m88k, provided a separate address space for the OS.) This dedicated OS address range can typically share page tables across multiple processes (and TLB entries by using a global indicator bit). (For x86's hierarchical page tables, the top node cannot be shared since [ordinarily] half of its entries are process-specific. ARM uses separate global and per-process/ASID page table base pointers with indication of how much of the total address range is global.)

(One could consider Address Space IDentifiers as extensions of the virtual address. Segments in Power and Regions in Itanium provide address space extension similar to ASIDs, but apply separate extensions to large sections of the initial untranslated address [e.g., Power uses 256 MiB segments and Itanium provides 8 regions within the 64-bit initial address]. Power actually calls the address types effective [the address computed by the memory access instruction], virtual [the address after the segment translation], and real [i.e., physical].)

On the other hand, a Single Address Space OS shares the entire virtual address space among multiple processes (protection domains). This allows conceptually simple and potentially low overhead communication among processes very much like memory communication among threads within a single process in a more conventional OS. Obviously, in a SASOS a process is not free to use whatever memory address it wants for whatever purpose it wishes; the OS must prevent different processes from using the same address for different storage. This breaks the illusion that the process "owns" the entire machine.

Every virtual address with a valid page table entry maps to a physical address. If the page table entry is invalid, the address does not map directly to a physical address (it may be in secondary storage [e.g., disk] or may not yet be allocated by the process).

(Even the above has simplifications and missing concepts.)


this language and acceptance by queue automaton

Working with a queue automaton for me is intuitively equivalent to working with a circular tape.
Read the input $w$ from the automaton, and put it on the tape. Add two markers $A$ and $B$, so we obtain $Aw_1Bw_2$. Now we can one by one eat a letter after $A$ and one after $B$.
For the deterministic variant it suffices to put $B$ exactly in the middle of the input string. That position can be found using a method similar to this: How to find middle element of linked list in one pass?


Complexity calculation of a recursive function with additional O(n) complexity

The question is absolutely not answerable without knowing what aFunctionWhichComplexityisO(n) returns.

Assuming that the function takes x as an argument, it might for example check if x contains the decimal representation of an integer y, and returns a string with the decimal representation of y-1 if y > 0, and null if y ≤ 0 or x does not contain the decimal representation of an integer.

In that case if x contains n characters, the time is $O (n·10^n)$.

Or the function always returns null, then the time is $O (n)$.


Existence of Optimal Policy for infinite-state MDPs

If the state set is Polish (e.g the set of all real numbers), finiteness of action spaces suffices to conclude that the MDP always has an optimal stationary policy - refer to "Markov Decision Processes" by Puterman for the details.


Must an optimization problem with a greedy algorithm belong to P?

If the greediness here means moving on the input based on a specified score, and computation of the input item's score is polynomial, the answer is yes. It is correct.  Because moving on the input with $n$ items is linear, and if the scoring computation for each item will be polynomial, as sorting them will be polynomial as well; finally, we can solve the problem in polynomial time (by the greedy algorithm).
Notice that, the polynomial computability of the score is vital here. For example, if the computation of the score for each item will be an NP-complete/hard problem (for example if it is the minimum vertex covering of a graph), the statement will not be valid anymore.


I'll try to give a succinct answer to some of your questions. Please bear in mind that this is not strictly my field of research, so some of my info may be outdated/incorrect.

There are many tools that are specifically designed to formally prove properties of Java and C++.

However I need to make a small digression here: what does it mean to prove correctness of a program? The Java type checker proves a formal property of a Java program, namely that certain errors, like adding a float and an int, can never occur! I imagine you are interested in much stronger properties, namely that your program can never enter into an unwanted state, or that the output of a certain function conforms to a certain mathematical specification. In short, there is a wide gradient of what "proving a program correct" can mean, from simple security properties to a full proof that the program fulfills a detailed specification.

Now I'm going to assume that you are interested in proving strong properties about your programs. If you are interested in security properties (your program can not reach a certain state), then in general it seems the best approach is model checking. However if you wish to fully specify the behavior of a Java program, your best bet is to use a specification language for that language, for instance JML. There are such languages for specifying the behavior of C programs, for instance ACSL, but I don't know about C++.
Once you have your specifications, you need to prove that the program conforms to that specification.

For this you need a tool that has a formal understanding of both your specification and the operational semantics of your language (Java or C++) in order to express the adequacy theorem, namely that the execution of the program respects the specification.

This tool should also allow you to formulate or generate the proof of that theorem. Now both of these tasks (specifying and proving) are quite difficult, so they are often separated in two:

One tool that parses the code, the specification and generates the adequacy theorem. As Frank mentioned, Krakatoa is an example of such a tool.
One tool that proves the theorem(s), automatically or interactively. Coq interacts with Krakatoa in this manner, and there are some powerful automated tools like Z3 which can also be used.

One (minor) point: there are some theorems which are much too hard to be proven with automated methods, and automatic theorem provers are known to occasionally have soundness bugs which make them less trustworthy. This is an area where Coq shines in comparison (but it is not automatic!).
If you want to generate Ocaml code, then definitely write in Coq (Gallina) first, then extract the code. However, Coq is terrible at generating C++ or Java, if it is even possible.
Can the above tools handle threading and performance issues? Probably not, performance and threading concerns are best handled by specifically designed tools, as they are particularly hard problems. I'm not sure I have any tools to recommend here, though Martin Hofmann's PolyNI project seems interesting.

In conclusion: formal verification of "real world" Java and C++ programs is a large and well-developed field, and Coq is suitable for parts of that task. You can find a high-level overview here for example.


Is Math a MUST in computer science specificly in Software Development for Web servers

Your question seems to be based on the misunderstanding that software development = computer science.  They are not the same thing. Your questions starts out asking about software development, but then ends by asking about the roots and scientific aspects thereof, which brings you to computer science, so it is not entirely clear what you want.

If you want to focus on software development, then math is not required (though it will often come in handy).

If you want to focus on computer science, then it is absolutely essential.


Here is a simple proof which avoids L'Hôpital's rule.

We start with the observation
$$
\log n = \int_1^n \frac{dx}{x} \leq \int_1^n dx \leq n,
$$
and so
$$
\frac{\log n}{n^2} \leq \frac{1}{n} \xrightarrow{n\to\infty} 0.
$$

Given $\epsilon > 0$, using the fact that $\lim_{n\to\infty} n^{\epsilon/2} = \infty$, we see that
$$
0 = \lim_{n\to\infty} \frac{\log (n^{\epsilon/2})}{(n^{\epsilon/2})^2} =
\lim_{n\to\infty} \frac{\frac{\epsilon}{2} \log n}{n^\epsilon}.
$$
It follows that
$$
\lim_{n\to\infty} \frac{\log n}{n^\epsilon} = 0.
$$


k-means clustering with efficient point lookup?

Instead of the classical $k$-means algorithm where you

classify all points and then
update the center of each cluster to be the average of all points of that cluster,

you could use the sequential variant of $k$-means:

centers = random(k)
while True:
    p = next_point(points)
    c = find_center(centers, p)
    c = c + a * (p - c)

next_point iterates all the points and maybe prefers new points (online) for example by using deque and putting new points front.

find_center classifies a point. This takes $O(k)$ naive and $O(\log k)$ using a spacial datastructure like a k-d tree.

$a \in [0,1]$ says how much a center moves in the direction of the given point. Usually this is time dependent and gets lower with time, i.e. $a(t) = \lambda_1 e^{-\lambda_2 t}$. Maybe one could boost the weight of new points though.


Can an Earley Parser be made into a fuzzy parser similar to the Levenshtein Automata Algo for DFA?

The answer is yes. However I would not do that with an Earley parser
because there are simpler ones with the same capabilities.

Basically, Earley parser belongs to a family of general context-free
parsers, that produces all possible parses for a given string, when
the grammar is ambiguous.

There are two ways (at least) of understanding these parsers:

as dynamic programming interpretation of a pushdown automaton
corresponding to the grammar on the input string;
as the the construction of the intersection of the grammar
with a finite state automaton.

When parsing a single string, the finite state automaton to be
considered is a linear automaton that recognizes only the string $w$
to be parsed, one symbol at a time (number of state is $|w|+1$).  If
you apply the cross-product construction of a FA $A$ and a CF garmmar
$G$ (Bar Hillel, Perlis, Shamir 1961), you get a new CF grammar that
is a new grammar $F$ which generates $\mathcal L(A)\cap\mathcal L(G)$.
The interesting point usually overlooked is that $F$ preserves the
parse-trees used by $G$, up to non-terminals renaming (due to
cross-product).

Thus if the FA $A$ generates only your input string, the grammar $F$
will generate only that string (if it is in $\mathcal L(G)$, otherwise
it generates the empty language $\emptyset$). Furthermore, it
generates it with all the parse-trees that $G$ could use to generate
it.

This grammar $F$ is what is usually called a shared parse forest, and
all general CF parsing algorithms are a more or less optimized version
of the cross-product construction, whether CYK, Earley, generalized LR
or LL, or others. So all I am saying applies to them too.

But, as you see, this generalizes to parsing a whole regular set, if
anyone is interested in doing that.

That is precisely your question. You have a string $w$. You want to
parse it up to some variations defined by a finite state transducer,
which in your case is a transducer that produces all strings within
some given Levenshtein edit distance of $w$ (but the origin of the
transducer is immaterial). The set of those strings is a regular set
that can be defined by a FA, with weighted transition that can compute
the edit distance of each string.

If you do the cross-product with your grammar $G$, you get a shared
parse forest grammar $F$ that generates all the strings in the
intersection. Furthermore, you get the weights on some of the rules so
that you can compute the edit distance of each of the accepted
strings.

If desirable, this can be used to keep only the strings with minimal
distance.

However, this can be improved a bit since composition with finite
state machines is associative.

If you always use the same, finite state transducer, as is the case in
your question, the right way to go about is to compose the Grammar $G$
and the transducer (here the Levenshtein automaton), independently of
the input string. This gives you a weighted grammar that you can use
to parse the input string $w$. The problem is that parsing with the
brutal intersection construction with give you strings at any
Levenshtein distance, i.e. $\Sigma^*$.

It would be easy to prune that construction to get the same result as
before, but the best way is a more controlled intersection
construction, such as the dynamic programming organization used by
most parsers in the literature, including Earley's, and use it to
avoid generating useless rule by computing distances and aborting any
computational path when it exceeds the desired threshold. Dynamic
programming can also be used to compute directly the parse-forest (or
parse-tree) for the string that have the shortest distance to the
input.


List of algorithm problems in term of ideals

We all know that 3SAT is NP-complete. Here is how to reduce 3SAT to your problem.

Suppose that the 3SAT instance has variables $x_1,\ldots,x_n$ and clauses $C_1,\ldots,C_m$. The new instance will have variables $x_1,\ldots,x_n,y_1,\ldots,y_m,z_1,\ldots,z_m$, and the following polynomials:

$x_i^2 - x_i$ for each $i \in [n]$ and $y_j^2 - y_j, z_j^2 - z_j$ for each $j \in [m]$.
For a clause $C_\ell$ of the form $x_i \lor x_j \lor x_k$: $x_i + x_j + x_k - y_\ell - z_\ell - 1$.
If a clause has negated variables, say $x_i$ appears as $\overline{x_i}$, then replace $x_i$ with $1-x_i$ in the polynomial stated above.

Why does this work, the first type of polynomials constrain all variables to be $0,1$. The polynomial $x_i + x_j + x_k - y_\ell - z_\ell - 1$ states that $x_i + x_j + x_k = 1 + y_\ell + z_\ell$, and since $y_\ell,z_\ell$ occur only in this polynomial, this is the same as $1 \leq x_i + x_j + x_k \leq 3$, that is, $x_i + x_j + x_k \geq 1$, or equivalently, $x_i \lor x_j \lor x_k$.


Can a cycle be represented by L1 metric?

Firstly for a fixed $n$, consider a path around the hypercube which is $$P_n=(0,0,\dots,0)\to(1,0,\dots,0)\to(1,1,0,\dots,0)\to\dots\to(1,1,\dots,1)\to(0,1,\dots,1)\to\dots\to(0,0,\dots,0,1)\to(0,0,\dots,0).$$ Notice that if I give you two points $p,q\in P_n$, then the $L_1$-distance between $p$ and $q$ is exactly the distance between $p$ and $q$ in $P_n$ (the shortest distance, not necessarily following the arrows in $P_n$). Now, suppose we're given a cycle $C_n$ with all edge weights $w_e\in\mathbb{Z}^+$ and $w=\sum_e w_e$ is even. We will do the following: Let $p_1=0$ and $p_i=p_{i-1}+w_{i-1,i}$, so $p_i$ is the weight of the path in $C_n$ from vertex $1$ to vertex $i$ going clockwise. Label the vectors on $P_{w/2}$ starting with $(0,0,\dots,0)$ having label $0$ and going around and map vertex $i$ of $C_n$ to the $p_i$'th vector in $P_{w/2}$. By the previous comment, this is an $L_1$-embedding.

Now, if each $w_e$ is rational, we can find some $M$ for which $Mw_e\in\mathbb{Z}$ for all $e$ and $M\sum_e w_e$ is even, so we can use the previous embedding and then scale.

Now for the irrationals.

Now, for a finite set $V$ and a subset $S\subseteq V$, we define the metric $\mu_S$ on $V$ by $\mu_S(x,x)=0$ and $\mu_S(x,y)=\mathbf{1}[|S\cap\{x,y\}|=1]$ if $x\neq y$. It is not difficult to prove that any metric of the form $\mu=\sum_{S\subseteq V}c_S\mu_S$ is $L_1$-embeddable for any $c_S\geq 0$. I claim that, in fact, if $V$ is any finite subset of $L_1^n$, then there are constants $c_S\geq 0$ for which $\Vert x-y\Vert_1=\sum_{S\subseteq V}c_s\mu_S(x,y)$ for every $x,y\in V$. First, if $V\subseteq L_1^1$, then write the points $V=\{v_1\leq v_2\leq\dots\leq v_k\}$. Then we have
$$
\Vert x-y\Vert_1=\sum_{r=1}^k\Vert v_{r+1}-v_r\Vert_1\mu_{\{v_1,\dots,v_r\}}(x,y),$$ for any $x,y\in V$. For a general $V\subseteq L_1^n$, we can do this construction in each coordinate direction $e_i$ for $i\in[n]$ since the $L_1$ metric is additive over the coordinates. Thus, if $\mu$ is a metric on a finite set $V$, then $\mu$ is $L_1$-embeddable if and only if $\mu=\sum_{S\subseteq V}c_S\mu_S$ for some constants $c_S\geq 0$.

Now, suppose that some edge-weights are irrational, so suppose $w_e^{(k)}$ are rational numbers with $w_e^{(k)}\to w_e$. Let $\mu^{(k)}$ be the metric induced by the weights $w_e^{(k)}$. By above, we know that each $\mu^{(k)}$ is $L_1$-embeddable, so we can write $\mu^{(k)}=\sum_{S\subseteq V}c_S^{(k)}\mu_S$. By compactness, without loss, we may suppose $c_S^{(k)}\to c_S$. Finally, since $\mu^{(k)}\to\mu$, we must have $\mu=\sum_{S\subseteq V}c_S\mu_S$, so $\mu$ must be $L_1$-embeddable.


Prove an arithmetic property of a partial recursive function

The function $f$ computes the recurrence relation
$$
f(x) = \begin{cases}
4 & x \leq 1, \\
f(x-1)^2 f(x-2)^4 & x > 1.
\end{cases}
$$
Taking $\ell = \log_2 \circ f$, we get
$$
\ell(x) = \begin{cases}
2 & x \leq 1, \\
2\ell(x-1) + 4\ell(x-2) & x > 1.
\end{cases}
$$
Now, modulo 10 we have
$$
2 \cdot 2 + 4 \cdot 2 = 12 \equiv 2 \pmod{10}.
$$
An easy proof by induction then shows that $\ell(x) \equiv 2 \pmod{10}$ for all $x$.


Informally:

There are two applicable rules here, wrt. a polynomial:

You can throw away the constant coefficients of each term.
The fastest growing term is the only one that matters, since as $n \rightarrow \infty$ (approaches infinity), the other terms will be insignificant.

So due to rule 1, $20n^2 + 2n^2\log n - 2n + 1$ becomes $n^2+n^2\log n - n + 1$.

Now, only the largest-growing term here will be significant. The other terms will be insignificant when $n \rightarrow \infty$. The two first terms are obviously much faster growing, since they have an exponent of $2$. The second term is faster than the first because it has a non-constant multiplier that is more than $1$ as $n$ approaches infinity; it will thus make the term grow faster. Thus the second term becomes the only one remaining.

Now for the math:

How do we know we can throw away constants?

Because, let $f(x)$ be that term, then $af(x) \in \mathcal{O}\left(f(x)\right)$, where $a$ is a constant, not dependent on $x$. What this means, is that $f(x)$ will grow at the same rate as $af(x)$, (as $x \rightarrow \infty$), even if it will always be larger by a multiplicative constant. How can we prove this?

The definition of $f(x) \in g(x)$:

$$|f(x)| \le \; M |g(x)|\text{ for all }x>x_0.$$

Where $M$ is some positive constant, and there exists some $M$ and $x_0$ that makes this true.

So let's set $g(x)=f(x)$:

So the question becomes: Does there exist an $M > 0$ and $x_0$ such that this holds true?

$$|af(x)| \le \; M |f(x)|\text{ for all }x>x_0.$$

The answer is simple: set $M=|a|$, then we get $|af(x)| \le \; |af(x)|\text{ for all }x>x_0$, which is of course true, since they are actually equal. And since this is true, we get $af(x) \in \mathcal{O}\left(f(x)\right)$ as per the formal definition of big O notation.

How do we know we only care about the fastest growing term in a polynomial?

See wikipedia section on properties of big O notation:

  If a function f(n) can be written as a finite sum of other functions, then the fastest growing one determines the order of f(n). For example

  $f(n) = 9 \log n + 5 (\log n)^3 + 3n^2 + 2n^3 = O(n^3) \,, \qquad\text{as } n\to\infty  \,\!.$

  In particular, if a function may be bounded by a polynomial in n, then as n tends to infinity, one may disregard lower-order terms of the polynomial.

To prove this, we need to prove that given two terms in a polynomial, if one grows as fast or faster than another, then the entire polynomial is as fast as the faster growing term. Formally:

$\left.f(x) + g(x) \in \mathcal{O}\left(f(x)\right) \vphantom{\Bigg|} \right|
_{g(x)\in \mathcal{O}\left(f(x)\right)}$

Translation: term $f(x)$ plus term $g(x)$ is as fast as $f(x)$ if $g(x)$ is bounded by $f(x)$ (bounded means: grows at most as fast as).

Proof of this statement:

$$
\begin{eqnarray}
&&&\hspace{2pt}&\hphantom{(1)}&\hspace{1pt}&
\\
\exists_{x_0,M>0} ~ \left|f(x) + g(x)\right|
&\stackrel{?}{\le}&
M\left|f(x)\right|
~~~x>x_0 \text{ as } x\rightarrow \infty
&&(1)&&\text{Reformulate question}
\\
g(x) &\in& \mathcal{O}\left(f(x)\right)
&&(2)&&\text{Given}
\\
\exists_{x_{g0},M_g>0}~\left|g(x)\right|&\le&M_g\left|f(x)\right|
&&(3)&&\text{Restatement of (2)}
\\
&&~~~x>x_{g0} \text{ as } x\rightarrow \infty
\\
f(x) &\in& \mathcal{O}\left(f(x)\right)
&&(4)&&\text{Reflexive}
\\
\exists_{x_{f0}=0,M_f=1}~\left|f(x)\right|&\le&M_f\left|f(x)\right|
&&(5)&&\genfrac {}{}{0}{}{\text{Restatement of (4) via}}{\text{def., choosing values}}
\\
&&~~~x>x_{f0} \text{ as } x\rightarrow \infty
\\
\exists_{
  \genfrac{}{}{0}{} {x_{f0},x_{g0}} {M_f=1,M_g>0}
}
~|f(x)|+|g(x)|&\le&
M_f\left|f(x)\right|+M_g\left|f(x)\right|
&&(6)&&\text{Adding (3), (5)}
\\
&&
~~~x>\max\left(x_{f0},x_{g0}\right) \text{ as } x\rightarrow \infty
\\
&\le&
\left(M_f+M_g\right)\left|f(x)\right|
&&(7)&&\text{Simplying (6)}
\\
&&~~~x>\max\left(x_{f0},x_{g0}\right) \text{ as } x\rightarrow \infty
\\
|f(x)+g(x)| &\le&|f(x)| + |g(x)|
&&(7.1)&&\text{Math}
\\
\exists_{
  \genfrac{}{}{0}{} {x_{0}=\max\left(x_{g0},x_{f0}\right)} {M=M_f+M_g}
}~\left|f(x)+g(x)\right|&\le&
M\left|f(x)\right|
~~~x>x_0\text{ as } x\rightarrow \infty
&&(8)&&\text{Simplifying (7,7.1)}
\\
M_f &=& 1
&&(9)&&\text{Valid/chosen in (5)}
\\
x_{f0} &=& 0
&&(10)&&\text{Valid/chosen in (5)}
\\
\exists_{
  \genfrac{}{}{0}{} {x_{0}=\max\left(x_{g0},0\right)} {M=1+M_g}
}~\left|f(x)+g(x)\right|&\le&
M\left|f(x)\right|
~~~x>x_0\text{ as } x\rightarrow \infty
&&(11)&&\text{Simplifying (8,9,10)}
\end{eqnarray}
$$

Thus we can construct a valid $M$ and $x_0$ given a valid $M_g$, and $x_{g0}$, which we know exist, because $g(x)\in \mathcal{O}\left(f(x)\right)$ is given.


Can you give me an example word that is in the language $L = \{w | w ∈ \{a,b\}^∗ ∧ |w|_a = |w|_b\} $

Check your definitions: $*$ is the Kleene star.

So, $\{a,b\}^*$ is the set of all finite strings over alphabet $\{a,b\}$.


Solving recurrence relation for asymptotic analysis

Suppose $n = 2^m + 1$. Then
$$
T(n) \geq 2T(2^{m-1}+1) \geq 4T(2^{m-2}+1) \geq \cdots,
$$
and so $T(n) = \Omega(n)$ for $n$ of this form. Therefore you cannot get a better worst-case bound than $O(n)$.

In more detail, this example shows that if $T(n) = O(f(n))$ for a monotone function $f(n)$ then $f(n) = \Omega(n)$. You might be able to get an upper bound using more information on $n$.

Let's analyze a similar but slightly simpler recursion,
$$
S(n) = \begin{cases} S(n/2) + 1 & \text{if $n>0$ is even}, \\ 2S(\lfloor n/2 \rfloor) + 1 & \text{if $n$ is odd},\\ 0 & \text{if $n = 0$}. \end{cases}
$$
Let us denote
$$
S(a_1,\ldots,a_k) = S(2^{a_1} + \cdots + 2^{a_k}),
$$
where we implicitly assume that $a_1 > \cdots > a_k$. We have
$$
\begin{align*}
S(a_1,\ldots,a_k) &= 1 + S(a_1-1,\ldots,a_k-1) \\ &=
2 + S(a_1-2,\ldots,a_k-2) \\ &= \cdots \\ &=
a_k + S(a_1-a_k,a_2-a_k,\ldots,a_{k-1}-a_k,0) \\ &=
a_k + 1 + 2S(a_1-a_k-1,a_2-a_k-1,\ldots,a_{k-1}-a_k-1) \\ &=
(a_k + 1) + 2(a_{k-1}-a_k) + 4S(a_1-a_{k-1}-1,\ldots,a_{k-2}-a_{k-1}-1) \\ &=
(a_k+1) + 2(a_{k-1}-a_k) + 4(a_{k-2}-a_{k-1}) + \cdots + 2^{k-1}(a_1-a_2) \\ &=
2^{k-1} a_1 - 2^{k-2} a_2 - \cdots - a_k + 1.
\end{align*}
$$
Notice now that
$$
2^{k-1} a_1 - 2^{k-2} a_2 - \cdots - a_k + 1 \geq \\
2^{k-1} a_1 - 2^{k-2} (a_1 - 1) - \cdots - (a_k - (k-1)) + 1 = \\
a_1 + 2^k - k,
$$
and on the other hand,
$$
2^{k-1} a_1 - 2^{k-2} a_2 - \cdots - a_k + 1 \leq \\
2^{k-1} a_1 - 2^{k-2} (k-2) - 2^{k-3} (k-3) - \cdots - 0 + 1 = \\
2^{k-1} (a_1 - k + 3) - 1.
$$
This gives us a lower bound of $\Omega(\log n + 2^{|n|})$ and an upper bound of $O(n)$, where $|n|$ is the Hamming weight; note that if $n = 2^m-1$ then the lower bound is linear in $n$. Indeed,
$$
S(2^m-1) = 1 + 2S(2^{m-1}-1) = 1 + 2 + 4S(2^{m-2}-1) = \cdots = \\ 1 + 2 + 4 + \cdots + 2^{m-1} S(1) = 2^m-1.
$$

It is likely that you can find a similar formula for $T$.


Expressing functions using the arithmetic dictionary

I'm not sure this is exactly what you are looking for, but you might find what you want in Theorem 3.2.1 of Computability Theory by S. Barry Cooper:

  All recursive functions are representable in PA.

that is for any recursive function $f$, there exists a binary predicate $F$ in the language of arithmetic such that for any natural numbers $x$ and $y$ we have
$$ f(x) = y ~\Rightarrow~ \vdash_{PA} F(x,y) $$
and
$$ f(x) \neq y ~\Rightarrow~ \vdash_{PA} \lnot F(x,y) $$
where $\vdash_{PA}$ means 'PA proves'.

This theorem is central to Gödel's famous incompleteness theorem, so you might also want to take a look at ch. 8 of the mentioned book where it is discussed, and this notion of 'representability' is extended to 'semi-representability', to include the c.e. sets as well.


Let $P = \{ w \in \{ 0,1 \} \mid |w| \le 64 \land w \in L(M) \}$. Since $P$ contains only words over an alphabet (i.e., a finite set) and all words in $P$ have bounded length, $P$ is finite. Moreover, any word $w \in \{0,1\}^\ast$ with length $|w| > 64$ is in $L(M)$ if and only if there is a prefix of $w$ which is in $P$. Thus, to decide $L(M)$, we only need to check whether the input has a prefix out of finitely many possibilities (i.e., those in $P$).

Hence, $L(M)$ is not only decidable, it is decidable in constant time.

Note this construction does not require any knowledge of $M$ whatsoever (in particular, there is no need to simulate $M$). We only need to show the existence of a TM which decides $L(M)$, not actually construct one.


Deriving the expected number of steps that is taken to perform the k'th operation

Let $N_i$ be the random variable denoting the length of $T$ prior to the $i$th operation. You should be able to calculate $\mathbb{E}[N_i]$.

The expected running time $T_i$ of the $i$th operation is
$$
p \cdot 1 + (1-p) \cdot \frac{1+\cdots+N_i}{N_i} = p + (1-p) \frac{N_i+1}{2}.
$$
Given $\mathbb{E}[N_i]$, you should be able to calculate $\mathbb{E}[T_i]$ using this formula.

I leave you to figure out all remaining details.


How to solve recurrence T(n) = 2T(n/2) + n/log(n) using substitution method

$$T(n) = 2T\left(\frac{n}{2}\right) + \frac{n}{\log n}$$

Would yield the following summation (assuming $n$ is a power of 2 and base case is $n=2$):

$$
\begin{align}
T(n) &= \frac{n}{\log n} + 2 \frac{\frac{n}{2}}{\log \frac{n}{2}} + 4 \frac{\frac{n}{4}}{\log \frac{n}{4}} + \dots \\
& = \frac{n}{\log n} + \frac{n}{\log \frac{n}{2}} + \frac{n}{\log \frac{n}{4}} + \dots + n\\
& = n \left[\frac{1}{\log n} + \frac{1}{\log(n) - 1} + \frac{1}{\log(n) - 2 } + \dots + 1\right]\\
& = n \sum_{i = 0}^{\log n - 1} \frac{1}{\log(n) - i}\\
& = n \cdot H_{\log n}\\
\end{align}
$$

Where $H_n$ is the $n$th Harmonic number. It's known that $H_n = \Theta(\log n)$.

We can thus conclude
$$T(n) = \Theta( n \log \log n )$$

Now with this being said; I believe this issue in your logic is the following steps:
$$
\begin{align}
T(n) & \leq cn \log{\log {\frac{n}{2}}} + \frac{n}{\log n}\\
& \leq cn \log{\log {n}} + \frac{n}{\log n}
\end{align}
$$
The jump from step 1 to step 2, while not incorrect, is not tight. Which is why you're not meeting the necessary conclusion. It should be something like:
$$
\begin{align}
T(n) & \leq cn \log{\log {\frac{n}{2}}} + \frac{n}{\log n}\\
& \leq cn \left[\log \log \frac{n}{2} + \frac{1}{\log n}\right]
\end{align}
$$
It can then be proven by induction that:

$$\log_2 \log_2 \frac{n}{2} + \frac{1}{\log_2 n} < \log_2 \log_2 n$$

For $n > 2$. The proof is pretty straightforward and I'll leave it as an exercise for the reader, but it then follows that:

$$
T(n)  \leq cn \log\log n
$$


How does the NFA decide in a state where there are multiple equally valid "next states"?

It doesn't decide. Nondeterminism isn't intended to be a realistic model of computation. Check the definition: a nondeterministic automaton accepts if there's any valid sequence of transitions that reach an accepting state.


The minimization operator is an effective operator

The best way to solve such problems is to understand what they amount to in real programming code. All the stuff about Gödel encoding is very mathy and fancy but uneccessary in this day and age.

We can think of Gödel codes of $\mu$-recursive functions as source code. The fact that an enumeration satisfies the smn theorems amounts to the fact that, given the source code of a function on $k$ arguments, we can calculate the source code of the same function with one of the arguments fixed to a particular value. The utm theorem just says that there is an intepreter for the source code.

An operator $G$ is effective if there is a program which converts the source code of a function $f$ to the source code of $G(f)$. This program must work for all valid inputs (is total). To see that the minimization operator is effective we thus have to write a program p which does the following:

Input: source code $S$ of a function $f$
Output: source code for the function $\bar{x} \mapsto \mu \, y [f(y,\bar{x}) = 0]$

Our program converts some source code to some other source code. It should not try to minimize anything, or simulate $f$, or anything like that. At this point you should stop reading and do the exercise yourself, in whatever your favorite programming language is.

Really, stop reading and do it yourself.

Here is my solution:

def p(k, s):
    """Convert source code s of a function in k+1 arguments to a function in k arguments which
       minimizes in the first argument. We assume that the source code s for the function
       is given in the following form (had we chosen a more decent programming language,
       we could have used anonymous functions instead):

              "def f(x0, ..., xk):
                 <body of function>
              "

       The output is given as a source code of a function in the following format:

              "def f(x1, ..., xk):
                  <body of function>
              "
    """

    # The string "x1, ..., xk"
    xs = ", ".join(["x{0}".format(k) for k in range(1,k+1)])
    # The source code s indended by 4 characters
    s4 = "\n".join("    " + l for l in s.split("\n"))
    # Now we can generate the output
    return ("""def f({0}):
{1}
    y = 0
    while True:
       if f(y, {0}) == 0: return y
       else: y = y + 1
    """.format(xs, s4))

Our program p corresponds to a primitive recursive function because it contains only for loops with prescribed bounds (the while True is not part of our program because it is inside a string and so is really part of the source code that our program outputs).

Let us try an example:

## We look for the least y such that x <= 2 * y.

s = """def f(y,x):
   return (1 if x <= 2 * y else 0)
"""

t = p(1,s)

print(t)

The output printed is:

def f(x1):
    def f(y,x):
       return (1 if x <= 2 * y else 0)

    y = 0
    while True:
       if f(y, x1) == 0: return y
       else: y = y + 1


Proving a language is not regular using the Myhill-Nerode Theorem

The words $0^n1$ are pairwise distinguishable, since $0^n10^n$ is a palindrome but $0^n10^m$ isn't (for $n \neq m$).

With a bit more work, you can show that in fact all words are pairwise distinguishable. See for example here or here.


Are there repositories of automatically generated (spam) webpages?

Question: Where can I access automatically generated (spam) webpages?

You could use:

a parody generator program.

They're usually based on Markov chains (e.g. SubredditSimulator) or context-free grammars (e.g. the well known SCIGen... according to the authors "with Markov chains you might get something syntactically correct, but it is likely to be boring"!).

Also a cut-up technique could be enough.
a (web spam) dataset. The WEBSPAM-UK2007 collection is one of the largest and cleanest (and it's open). A description of the dataset can be found in A Reference Collection for Web Spam (the paper describes WEBSPAM-UK2006 but it's still valid).

You should check if it's too broad: the collections includes many different web spam aspects as possible (pages that are only advertising, pages with unrelated links, pages that automatically redirect...) and you seems only interested in pages that contain machine generated content.
the spam messages in the email: email spammers often include URLs in their spam messages. Following those links you can store the HTML content. You should add a few heuristics to identify some false positives (e.g. exclude Alexa's Top 500 list and use SiteAdvisor's rating system to compile a whitelist).

This is the method used to create another well known dataset: Webb Spam Corpus (the original corpus was collected by Steve Webb). Further details are contained in Introducing the Webb Spam Corpus: Using Email Spam to Identify Web Spam Automatically (Steve Webb, Jamesa Caverlee, Calton Pu).


Implementing the Schur decomposition of a matrix

It's italian but it's very clear... Read this:

Shur decomposition

Proposition 6.13


Is checking if regular languages are equivalent decidable?

It is decidable, all you have to do is use the closure properties of finite automata + emptiness checking; let me know if you want me details.
I’m not sure exactly how you’d check the equivalence of two regular expressions, other than by converting to automata, so unless this is a practical issue you’re trying to resolve and you receive input in terms of regular expressions, I’d think about it in terms of automata.
As for creating the Turing machine that actually does this, it’s probably not strictly necessary to write out the formal description, as long as you can argue why it’s possible to do so.


How good are current AI researchers at simulating complex, first-person emotional states?

Great Question!  One area to look into is Cognitive Architectures.  These are computer programs that solve AI problems by modeling how humans think and feel (emotion).  Here is a brief overview.

Prior to the mid-1980s the study of AI was concerned with creating general intelligent systems modeled after flexible human thinking (Fahlman, 2012).  Researchers in AI used findings in cognitive psychology to guide their work.

Currently, there has been a shift away from this approach.  The current trend in AI research is towards solving problems with “knowledge-lean” statistical methods which are data intensive and learn less efficiently than humans.  (Langley, 2012).  Thus, the AI field has shifted away from human-like models and toward "ideal" models.

However, a few AI researches still focus on creating intelligent systems modeled after the way humans think.  These researches work with Cognitive Architectures--Computer programs modeled after humans. The Office of Navel Research's Human Computer Interaction lab is actively working to create intelligent agents that can interact with humans.

I believe that the study of Cognitive Architectures is an interesting area of research for investigating how to create human-like systems.

Fahlman, S. E. (2012). Beyone Idiot-Savant AI. Advances in Cognitive Systems 1, 15-21.

Langley, P. (2012). Intelligent behavior in humans and machines. Advances in Cognitive Systems 2, 3-12.

Taatgen, N. A. (1999). Learning without limits. From Problem Solving towards a Unified Theory of Learning(dissertation). Groningen: Rijksuniversiteit Groningen.

http://www.onr.navy.mil/en/Science-Technology/Departments/Code-34/All-Programs/human-bioengineered-systems-341/Human-Robot-Interaction.aspx


Both MaxSAT and MaxUNSAT are NP-complete, and so can be reduced to one another. MaxSAT is NP-hard by (trivial) reduction from SAT. To see that MaxUNSAT is NP-hard, we follow Creignou [1] and reduce from MaxCUT. Given an instance $G=(V,E)$ of MaxCUT, consider the instance
$$ \bigwedge_{(x,y) \in E} (x \lor \lnot y) \land (\lnot x \lor y). $$
Each cut corresponds to a $0/1$ assignment to the vertices. If an edge $(x,y)$ is separated by a cut, then one of the two corresponding clauses will be unsatisfied, and otherwise none will be unsatisfied.

[1] Creignou, A dichotomy theorem for maximum generalized satisfiability problems, JCSS 51, 511-522 (1995).


How did they cancel out O-terms in this fraction?

First, let me mention that judging from the final result, in this context $O(f(N))$ means a function $g(N)$ such that $|g(N)| \leq Cf(N)$ for some $C>0$ and all $N$.

The first step is simple: we divide both numerator and denominator by $2a_0 N$. This gives us
$$
\frac{2\ln(2N) + O(2N)/2a_0N}{\ln N + O(N)/2a_0N}.
$$
Now if $f(N) = O(N)$ then $f(N)/2a_0N = O(1)$, since $2a_0$ is a constant. This is how we get to the second fraction.

Getting to the final expression takes more work. First, notice that
$$
\frac{2\ln(2N) + O(1)}{\ln N + O(1)} = \frac{2\ln N + O(1)}{\ln N + O(1)},
$$
since $2\ln 2$ is a constant. Denote now by $B(N)$ the $O(1)$ function in the numerator, and by $C(N)$ the $O(1)$ function in the denominator. Then
$$
\frac{2\ln N + B(N)}{\ln N + C(N)} =
2 + \frac{B(N) - 2C(N)}{\ln N + C(N)} = \\
2 + [B(N) - 2C(N)] \frac{\ln N}{\ln N + C(N)} \frac{1}{\ln N} = \\
2 + [B(N) - 2C(N)] \left(1 - \frac{C(N)}{\ln N + C(N)}\right) \frac{1}{\ln N}.
$$
We need to show that the second term is $O(1/\log N)$. By definition, $|B(N)-2C(N)|$ is bounded by some constant. The same can be said about the second factor, since it tends to 1 as $N \to \infty$. Hence the entire second term is bounded in absolute value by a constant times $1/\ln N$, i.e., it is $O(1/\log N)$.


Priority queue with a buffer for delayed insertion and other tweaks

There are several approaches that combine multiple buckets and heaps to improve shortest path algorithms. At good starting point would be Dial's algorithm or Cherkassky, Goldberg & Silverstein.


Grover algorithm when element not present in the array/database

The most basic version of Grover's algorithm has a fixed number of iterations and assumes there is one marked item. If there is no marked item instead of one marked item, you will do those iterations but then get a random answer.

As mentioned in the wikipedia article on Grover's algorithm, the algorithm can be extended to work when there are an unknown number of marked items while still running in $O(\sqrt{N})$ time. There's just more details to work out.


Finding the Kth largest element can be optimized to O(n) only if k is a constant?

The $k$th largest element can be found in time $O(n)$ for all $k$ using a deterministic algorithm. See Wikipedia or many textbooks, such as Cormen et al., Introduction to Algorithms.

Given the $k$th largest element, you can find the $k$ largest elements in $O(n)$ using a simple scan. If all elements are distinct, you just output all elements which are at least as large as the $k$th largest. Without this assumption, you output all elements which are strictly larger than that element, and then enough copies of the $k$th largest one.


Are there any useful deterministic quantum algorithms for decision problems?

There are some query complexity results that mention exact quantum algorithms. See this blog post about the paper "Separations in Query Complexity Based on Pointer Functions":

  a total boolean function $g$ on $n$ variables that has [...] exact quantum query complexity [...] $Q_E(g) = \tilde O(\sqrt n)$.

More generally, the complexity class you're looking for is called EQP: Exact Quantum Polynomial-Time.

EQP is not a very "nice" complexity class, especially compared to BQP. There's two big reasons for that:

Theoretical-side, there's no universal set of gates. EQP circuits may require a gate with irrational coefficients such as $\begin{bmatrix} \cos(10^\circ) & -\sin(10^\circ)\\ \sin(10^\circ) & \cos(10^\circ)\end{bmatrix}$, and approximations via other gates aren't allowed. So you end up with a bunch of different $\text{EQP}_{my\_favorite\_gate\_set}$s instead of a nice unified one.
Practical-side, there's no possibility of error correction. EQP lives in a world without errors, because otherwise it wouldn't be exact. Error correction is expected to be a necessity in practice, so if you care about actual implementation then you don't care much about EQP.


One of the basic operations supported by trees is searching for elements. A balanced binary tree (for example, a red-black tree) supports search in $O(\log n)$ time, where $n$ is the number of elements. In some scenarios, the elements we are searching for are close to one another, and finger search allows taking advantage of that. After having just searched the $j$th largest element, searching the $i$th largest elements only takes time $O(\log |i-j|)$. So scanning through all the elements in order would only take $O(n)$ time rather than $O(n\log n)$.

Finger search can be implemented using several different data structures. In particular, it can be implemented using balanced binary trees such as red-black trees.

For more on finger search, check out a research proposal by Maverick Woo and a book chapter by Gerth Stølting Brodal.


Is halting problem computable for particular inputs/assumptions

is halting problem computable by program P for all other programs used as input but P itself?

No. Consider the infinite sequence of programs $P_1, P_2, \dots$, where $P_i$ is "Move the head $i$ squares to the right, then $i$ squares to the left, then do exactly what $P$ would do." Every one of these programs produces exactly the same output as $P$ for every input (including looping forever if $P$ loops forever), but they're all different programs.

And you can't get around this by only requiring $P$ to work on programs that aren't functionally equivalent to itself, since that property is also undecidable. Perhaps the problem would be decidable when restricted to those instances (though I suspect it wouldn't) but the set of instances is undecidable, so you couldn't actually perform the restriction.


Is Wikipedia's formal definition of NP correct?

I am currently reading "Introduction to the Theory of Computation" by Sipser and think that it is a great introduction to complexity (as well as automata and computability). Here are his definitions of Verifier and NP:

Definition 7.18: A verifier for a language $A$ is an algorithm $V$, where $A = \{ w \mid V \text{ accepts } \langle w, c \rangle \text{ for some string } c \}.$ We measure the time of a verifier only in terms of the length
of $w$, so a polynomial time verifier runs in polynomial time in the
length of $w$. A language $A$ is polynomially verifiable if it has a
polynomial time verifier. (Sipser, 293)
Definition 7.19: NP is the class of languages that have polynomial time verifiers. (Sipser, 294)

Translating the wiki definition into the above, $A = L$, $V = M$, $w = x$, and $c = y$. It seems that the first condition of the wiki definition is correct, and this may make more sense given the alternative definition of NP. A language $L$ is in NP if there exists a non-deterministic TM $N$ that decides $L$ in non-deterministic polynomial time $NTIME(n^k)$. Here, the running time of $N$ is measured in terms of its input size $n = |w| = |x|$.
However, I have not seen nor am I familiar with the second condition, but that seems to set some upper bound on the length of $y$ so that $|y|$ is a polynomial in $|x|$, which should answer your question about if $|y| > p(|x|)$. I figure the second condition is to protect against padding arguments. At any rate, if $p(|x|) < q(|x|)$, then $p(|x|) < |y| < q(|x|)$, so $|y|$ is still a polynomial in $|x|$.


why swap function is use in union find algorithm? How rank or size array is used for optimization

To answer your first question, it is a matter of style. If you do it your way, then the code appears twice. Code duplication is more prone to bugs, since you have to duplicate every change that you make, taking care (in this case) to switch $a$ and $b$.


Shortest path in NL algorithm, need help to understand

What is probably meant is that the chosen vertex is substituted back into $p$. This way when the for loop is done, $p$ contains some vertex of distance at most $k-1$ from $s$. Note that comparing the counter $d$ to $r_{k-1}$ makes sure that you went over all the vertices of distance at most $k-1$ from $s$.


Can we make a PDA with only 1 state which accepts a^n and n is odd?

But can we have a non empty stack at the start?

By the formal definition PDA has the initial stack symbol $Z$ with which a computation starts.

The idea is to use three stack symbols $Z, Z_{even}, Z_{odd}$ to keep track of whether the number of $a$s read so far is even or odd. If the PDA reaches the end of string and topmost symbol is $Z_{odd}$ then empty the stack.


You are asking two questions:

How to count "winning groups" up to isomorphism?
Which winning groups are realizable as winning coalitions?

From the point of view of winning groups, we can assume that each voter always casts all her votes, and the resulting games is known as a weighted voting game.

Counting winning groups

Your concept of "winning group" is a same as a monotone Boolean function or an upset. The number of monotone Boolean functions up to permutation is enumerated in the sequence A003182, and grows pretty quickly. For $n=7$ the number is already pretty large: 490,013,148. It's probably not too helpful to list all of them. It is even non-trivial just to calculate the number, see this paper.

You can find all the 16351 non-constant monotone Boolean functions for $n=6$ listed here as sets of minterms, which are (in your parlance) minimal winning coalitions. The minterms form what is known as an antichain, a collection of sets none of which is a subset of another.

Which winning groups are achievable?

Let $S_1,S_2$ be two sets of voters. A swap consists of taking some $x \in S_1 \setminus S_2$ and some $y \in S_2 \setminus S_1$, and forming the new sets $S_1 - x + y, S_2 - y + x$ (that is, we exchange two voters, taking care not to have the same voter twice in any of the sets). Given several sets $S_1,\ldots,S_k$ of voters, a trade is the result of applying arbitrarily many swaps, resulting in a new $k$-tuple $T_1,\ldots,T_k$.

(Alternatively, $T_1,\ldots,T_k$ is a trade of $S_1,\ldots,S_k$ if the multisets $S_1 \cup \cdots \cup S_k$ and $T_1 \cup \cdots \cup T_k$ are the same.)

Let $W$ be a set of "winning coalitions". We say that $W$ is trade robust if whenever $S_1,\ldots,S_k \in W$, in any trade $T_1,\ldots,T_k$ obtained from $S_1,\ldots,S_k$ at least one of the $T_i$ is in $W$. It is easy to see that every set of winning coalitions arising from weighted voting games is trade robust (exercise). Amazingly, Taylor and Zwicker showed that the converse holds as well.


The median is a value of a sample which states that half of the other values of the sample have higher values and the other ones are smaller ones. In a 3⨉3 filter you are selecting the median out of a sample of 8 elements. Let's assume we have the following values in our sample (an image of size 3⨉3):

1  2   4
8  16  32
64 128 255

If we apply the median filter for the upper left value [sample: {2, 8, 16}], the median is 8 (not processing out of boundary values). After the first application of the median filter we get a new sample:

8  8  16
16 20 16
16 32 32

If we apply the median filter again, we get:

16 16 16
16 16 20
20 16 20

So my point here is that after each application of the median filter, you will get a new sample [0]. But the evaluation of one new pixel depends on all the other sample values and modifies the sample itself. Because of this dependence I cannot see any way to be able to apply the filter twice in one step. I also did not find any literature about this [1].

[0] Unless the image contains only the same value at each pixel which we cannot assume.
[1] which I don't want to use as a pro or contra argument.


NLP: Automatically categorize words semantically into non-predefined classes

You're looking for Wordnet https://en.wikipedia.org/wiki/WordNet ...


You are asking how to solve $e^{ax^2}=b$ for $x$, given constants $a,b$.  The solution is $x=\sqrt{\frac{1}{a} \log b}$, which can be computed (approximately) using standard algorithms for computing the log and the square root.

In particular, your specific equation has the solution

$$m = \sqrt{2s^2 \log (a/(\sqrt{2\pi} hs))}.$$

You can verify the correctness of this solution by plugging into the equation and verifying it works.


Proof of non-regularity, based on the Kolmogorov complexity

To my knowledge, this is not one of the "classical" approaches used to characterize regular languages.

This approach is discussed in "A New Approach to Formal Language Theory by
Kolmogorov Complexity", by Ming Li and Paul M.B. Vitanyi (see section 3.1).

They give several examples where one can use the statement you mentioned instead of using the pumping lemma. For example, proving non-regularity of $L$ where

$L=\left\{1^p|\text{p is prime}\right\}$.

Given some $x\in\Sigma^*$, $L_x=\left\{y| \hspace{1mm} xy=1^p \land \text{p is prime}\right\}$. Let us choose $x=1^{p'}$ where $p'$ is the $k$'th prime. Let $y_1$ be the first word in $L_x$. Obviously, $y_1=1^{p-p'}$ where $p$ is the $k+1$ prime. According to the statement you mentioned, $K(y_1)\le c$ ($n=1$), for some constant $c$ depending only on $L$ (see paper).

Since this holds for all $x$, we can bound the Kolmogorov complexity of all elements in $S=\left\{y_1^x| x=1^p \text{ for prime $p$ } \land \text{$y_1^x$ is the first string in $L_x$}\right\}$ by the same constant $c$. However, we saw that $S$ actually consists of differences between consecutive primes, i.e.
$S=\left\{1^{p_{k+1}-p_k} | k\ge 1\right\}$ where $p_k$ is the $k$'th prime. Since we know $S$ cannot have bounded Kolmogorov complexity (prime differences get arbitrarily large), this means $L$ cannot be regular.


Is the class of Turing-recognizable languages closed under Homomorphism?

Your proof has a flaw.

Assume $L=\{b\}$, and $f(a)=f(b)=w$ for some word $w$. We have $f(L)=\{w\}$.

TM $M'$ on $w$ finds the preimage $a$, then checks $a\not\in L$, and rejects. This is wrong, since $w$ should be accepted.

The point is, we should not reject $w$ just because we found a preimage of $w$ which is not in $L$. We should continue checking all such preimages.

Above, doing that we would consider $b$ as well, and cause $w$ to be accepted.


Using recursive descent in combination with an operator precedence variant for expressions is a very common approach. You might also want to search for Pratt parsing.

An older, now uncommon technique which combines LL and LR parsing is "left-corner" (LC) parsing, which should also be easy to search for.

In practice, the existence of easy-to-use and efficient LR parser generators makes all of these less powerful techniques much less useful. LC parsing was pretty well obsoleted as a technique with the discovery of the LALR algirithm.


Randomized Meldable Heap - Expected Height

In the paper, $h_Q$ isn't the height.  It's the length of a random walk away from the root in a full binary tree (they insist every leaf is "nil"), so the expression they have is the right thing.

Also, you can avoid induction.  The probability of ending at a specific leaf of depth $d$ is just $2^{-d}$.  So the expected length of the walk is

$$
\sum_{\ell\in \text{leaves}(Q)} \text{depth}(\ell)2^{-\text{depth}(\ell)}
$$

which the entropy of a distribution a set of size $|\text{leaves}(Q)|$.


What's the difference between cache miss penalty and latency to memory?

"Cache miss penalty" would be the extra time that is spent because of the cache miss.

Let's say your L1 cache has 5 cycles access time, and L2 cache has 23 cycles access time. That doesn't tell us enough yet.

A clever implementation might immediately detect that there is a cache miss, and send the data from the L2 cache simultaneously to the L1 cache and to whoever wanted the data. So without cache miss it might take 5 cycles, with cache miss 23 cycles. So you have 23 cycles latency for the L2 cache, but only 18 cycles miss penalty.

A less clever implementation might try the L1 cache first, then 5 cycles later start accessing L2 cache, put the data into L1 cache 23 cycles later, start the L1 cache access all over, and deliver the data another 5 cycles later. Total time 33 cycles, minus the 5 cycles without cache miss, so a 28 cycle miss penalty.


How to prove that a minimum edge cover is a forest?

A forest is a graph in which every component is a tree. If there is only one component, and that component is a tree, the graph is a forest.

So why is every minimum edge cover a forest? Suppose you have a graph $G=(V,E)$ and an edge cover $C\subseteq E$. Suppose some component of the graph $(V,C)$ contains a cycle, say $x_1x_2\dots x_kx_1$. Then $C\setminus\{x_1x_2\}$ is a smaller edge cover than $C$: $x_1$ is covered by the edge $x_kx_1$, $x_2$ is covered by $x_2x_3$ and every other vertex in $V$ is still covered by whatever covered it in $C$. Therefore, every minimum edge cover must contain no cycles, and an undirected graph that contains no cycles is a forest.

Indeed, we can go even farther. If an edge cover $C$ contains a path $x_1x_2x_3x_4$ then $C\setminus\{x_2x_3\}$ is a smaller edge cover, by essentially the same reasoning as above. Therefore any minimal edge cover is a forest that contains no path of three or more edges. So, not only is every minimum edge cover a forest, but it's a forest where every component is a star (a complete bipartite graph $K_{1,k}$ for some $k\geq 1$; note that $K_{1,1}$ is an edge and $K_{1,2}$ is a two-edge path).


Finding a lower bound for the expression $\log(n!)$

$\log n! \le \log n^n = n \log n = o(n^n)$.


How do I construct a doubly connected edge list given a set of line segments?

Data structure (conventions consistent with the Wikipedia article):

struct half_edge;

struct vertex {
    struct half_edge *rep;  /* rep->tail == this */
};

struct face {
    struct half_edge *rep;  /* rep->left == this */
};

struct half_edge {
    struct half_edge *prev;  /* prev->next == this */
    struct half_edge *next;  /* next->prev == this */
    struct half_edge *twin;  /* twin->twin == this */
    struct vertex *tail;     /* twin->next->tail == tail &&
                                prev->twin->tail == tail */
    struct face *left;       /* prev->left == left && next->left == left */
};

  Algorithm

  For each endpoint, create a vertex.
  For each input segment, create two half-edges, and assign their tail vertices and twins.
  For each endpoint, sort the half-edges whose tail vertex is that endpoint in clockwise order.
  For every pair of half-edges e1, e2 in clockwise order, assign e1->twin->next = e2 and e2->prev = e1->twin.
  Pick one of the half-edges and assign it as the representative for the endpoint. (Degenerate case: if there's only one half-edge e in the sorted list, set e->twin->next = e and e->prev = e->twin). The next pointers are a
  permutation on half-edges.
  For every cycle, allocate and assign a face structure.


Composition of handler types in algebraic effects and handlers

You are correct that the reason lies in the lack of computation abstractions. They are left out because they are not a standard programming construct, especially in a call-by-value calculus. But even if you added them, I don't think they should be given a type of the form $\underline X \Rightarrow \underline Y$ because they are in general not homomorphisms, what the type would suggest.

You can get around in two ways:

you can apply the function fun t -> with h' handle (with h handle t ()) of type $(\mathtt{unit} \to \underline A) \to \underline C$ on a thunked operation. For example, in Multicore OCaml the only way of making a general handler is through a function that takes a thunked computation.
you can precompose the handler similar to what @chi suggested.
If h is of the form

handler {
    return x -> c_ret,
    op1(x, k) -> c1(x, k),
    ...
}

then the composed handler

handler {
    return x -> with h' handle c_ret,
    op1(x, k) -> with h' handle c1(x, k),
    ...
}

has the type $\underline A \Rightarrow \underline C$.


The formula means "it is not true that there exists $y \in L$ and $z \in \Sigma^*$ such that $z \ne \epsilon$ and $x=yz$."  That is, there is no way of writing $x=yz$ such that $y\in L$ and $z\neq\epsilon$.


What is the name of the operator that translates from $X\rightarrow(Y\rightarrow Z)$ to $Y\rightarrow(X\rightarrow Z)$?

The function $$\lambda f.\lambda x.\lambda y.f\;y\;x$$ of type $$\forall X. \forall Y. \forall Z.(X \to Y \to Z) \to Y \to X \to Z$$ is often called flip. This is the case in Haskell (see here), and in some OCaml libraries as well (see here). According to wikipedia, people call this function (or combinator) $C$ in the context of combinatory logic (that name sounds pretty random though).


Does this language have a context-free grammar?

No, this language is not context-free. This is because the language requires to iterate $b^mc^m$ with the same number $m$ each time. Even if we restrict to $n=0$ and $p=2$ then the resulting language $\{b^mc^mb^mc^m \mid m\ge 0\}$ is easily recognized as non-context-free. Formally this restriction is obtained by intersecting with a regular language, a known closure property of context-free languages. To prove a language formally non-context-free one might use the pumping lemma discussed elsewhere in this forum.

Perhaps that is a mistake in its specification. If for each iteration the number $m$ can be different, the resulting language is context-free. That language would be $L_1 = \{ a^n w d^n \mid n\ge 0, w\in \{\; b^mc^m \mid m\ge 0\}^*  \;\}$. As an example, $bbbcccbc$ is an element of $L_1$, but not of $L$.

How to find a grammar (for $L_1$)? Observe the nesting structure. Context-free grammars are good in nesting, and iteration. For instance the part $\{\; b^mc^m \mid m\ge 0\}^*$ is generated by $T\to AT, T\to A, A\to bAc, A\to\lambda$, starting with $T$. Now add a matching number of $a$'s and $d$'s on both sides by nesting: $S \to aSd, S\to T$.


This is just lexicographical order, but left to right (not right to left as usual).


How can another process call $signal()$ when one process is executing $wait()$ in its busy waiting loop?

Your assertion that wait() and signal() are atomic is incorrect. The increment/decrement to s within the functions (s++, s--), are what's atomic.

That being said, what you have given here is only one possible implementation of a semaphore. An OS may or may not implement semaphores in this way, and they probably will choose a more efficient implementation. What's more important is to grasp the semantics of a semaphore, which you seem to understand correctly.


Characteristic vector is a string representation of a set in this case.
For a set $S$, the characteristic vector is denoted by $X_S$. $X_\emptyset$ and $X_U$ are referring to the characteristic vector of $U$ (Universal set) and $\emptyset$ (Empty set) respectively.
In your example,
$$\text{If }n = 4 \text{ and } S = \{1, 3\} \text{, then } X_s = 1010.$$
We simply need to replace $S$ with a set $\{0, 1, 2, \dots n-1\}$ to find $X_U$ and with $\{\} = \emptyset$ to find $X_\emptyset$. I think you can leave $n$ as a variable unless it is fixed to some value.


Is this push-down automaton non-deterministic, as JFLAP states?

All deterministic push-down automatons are also nondeterministic push-down automatons, so it is correct to say that your automaton is nondeterministic.
That said you are correct in saying that your first push-down automaton is also deterministic, according to the definition on Wikipedia.


Is the language $\{a^n b^n c^i | i \leq n\}$ context free?

Classical pumping works. According to the pumping lemma we can find a segmentation $uvwxy$ such that $uv^iwx^iy$ is in the language for all $i$.

Start with your own suggestion $a^pb^pc^p $.

Three easy steps.

Each of the "pumping segments" $v$, $x$ can only be within the boundaries of one the "letter segments" $a^p$, $b^p$, $c^p$.
It is not possible to have one of $v$ or $x$ to be in the $a^p$ segment without the other being inside the $b^p$ segment. And the other way around. In that case pump down ($i=0$).
Final possibility both $v$ and $x$ are in $c^p$. Pump up.


Balanced weight distribution in buckets, with different weight per bucket

This problem is known as Unrelated Parallel Machine Scheduling. Minimizing $max_j T(b_j)$ has a 2-approximation, by LP-relaxation and rounding.


Show that the Kleene star of any unary language is regular

Let $p$ be the $\gcd$ of the lengths of all the words in $L$.
We claim that there exists $N$ such that for all $n>N$, $1^n\in L$ iff $p|n$.

Observe that one direction is trivial: $p|n$ for every $1^n\in L$ by definition.

The converse is less trivial, you can find good guidelines in the answers here

Given this claim, you can write $L^*$ as the union of the relevant words up to length $N$, and then $1^{pi}$ for all large enough $i$.


Just follow the algorithm. First you have to do a zag-zag-rotation, which gives you

0
 \
  1
   \
    4
   /
  3
 /
2

Then you have to do another zag-zag-rotation and you obtain as the result of splay(4) the tree

    4
   /
  1
 / \
0   3
   /
  2