Why are most (or all?) polynomial time algorithms practical?

The comment is wrong. It is very easy to give examples of polynomial time algorithms which aren't practical at all:

The ellipsoid algorithm for solving linear programs runs in polynomial time but is too slow to be practical. The simplex algorithm, whose worst-case running time is exponential, is preferred in practice.
The AKS primality testing algorithm runs in polynomial time but is too slow to be practical. Instead, randomized polynomial time algorithms are used. We sacrifice certainty for performance.
Fast matrix multiplication algorithms run asymptotically faster than high-school matrix multiplication (both are polynomial), but are too slow to be practical. The high-school algorithm is used in practice.
A similar issue occurs in fast integer multiplication algorithms. The algorithm with the best asymptotic complexity, Fürer's algorithm, is too slow to be used in practice. Instead, relatively simple algorithms are used even for quite large integers.
Big data algorithms need to run in linearithmic time (which is $O(n
\log^{O(1)}n)$) to be practical.

These examples show that the identification of polynomial time with practical is not accurate, and might depend on the circumstances. Researchers in theoretical algorithms feel a need to justify their field of research, and so they ideologically believe in the sentiments expressed in the comment you mention. You shouldn't take such comments too literally.

In fact, many algorithms used in practice are heuristic and we don't have any estimates on their running time other than empirical results. Such algorithm don't fit into the theoretical framework at all, yet there are very useful in practice. Several (but not all) machine learning algorithms belong to this class just in terms of running time (not to mention in terms of performance), as do search algorithms such as A* and alpha-beta, and SAT solving algorithms.


How can we compute how many processes should be in memory at a time to make CPU utilization max?

Let $U$ indicate the CPU utilization in percent. What you have calculated is:
$$\log(U) = \log(1 - P^n) \stackrel{!}= \log(1) - \log(P^n) = \log(1) - n \log(P)$$

However, the equality marked with an exclamation mark is incorrect since $\log(a - b)$ is, in general, not equal to $\log(a) - \log(b)$.

The correct line of reasoning is restating the original equality as $P^n = 1 - U$ and then:
$$n \log(P) = \log(P^n) = \log(1 - U)$$
Thus:
$$n = \frac{\log(1 - U)}{\log(P)}$$

(Of course, this all assuming $P > 0$ and $U < 1$; otherwise, there is no (unique) solution.)

Tip: when reformulating mathematical expressions, always do it one step at a time, and question every single step! Else you are bound to make mistakes. (Source: personal experience)


Can someone explain the language L = {w: w = uu, u \in La(1*01*)}

No, your simplification is wrong.

Consider, as a simpler case, $A=\{a,b\}$ and $L'=\{ w \mid w=uu , u\in A\}$. Then, $L'=\{aa,bb\}$.

Instead, if we apply your simplification and write $L''=AA$ then we have $L''=\{aa,ab,ba,bb\}$ which is a larger language, since we forgot that both $u$'s in $w=uu$ must be the same word.

Keeping that into account, your original language $L$ seems to be $\{1^n01^m1^n01^m \mid n,m\geq 0 \}$


The formula's you propose are very reminiscent of the operations of monadic second order logic: position variables, existence letter on position, relative order of positions, boolean operators and position quantification. As you probably know the power of this scheme equals regular languages.

The transformation from MSO to FSA seems to be horrible (negation is complementation, and existential quantification is handled using nondeterminism, hence exponential blow-up for each combination of the two).

Nevertheless, that gives a very different complexity, linear in $n$, but multiplied by a tower of 2-powers of height $k$.


When the compressor clears the dictionary, it emits the clear code.  This enables the decompressor to stay in sync: when it sees the clear code, the decompressor clears its own dictionary.  In this way, the decompressor can reconstruct/infer the state of the encoder's dictionary at each step.
Wikipedia says:

Smart encoders can monitor the compression efficiency and clear the table whenever the existing table no longer matches the input well.


This is a phase shift gate.

Notice that

$$\begin{bmatrix}e^{i\sigma}&0\\0&e^{i\theta}\end{bmatrix}=
e^{i\sigma}\begin{bmatrix}1&0\\0&e^{i(\theta-\sigma)}\end{bmatrix}
$$

Multiplying the state by a constant (with unit norm) will not affect your measurements.


What is the difference between R precision and precision at K?

R-Precision

R-Precision is defined as $\frac{r}{R}$, which is the ratio between all the relevant documents retrieved until the rank that equals the number of relevant documents you have in your collection in total ($r$), to the total number of relevant documents in your collection $R$.

Suppose in your collection there are 100 documents in total, 30 of which are relevant ($R = 30$), the rest irrelevant. So you retrieve the first 30 documents (because 30 are relevant in total in your collection) and, say, 10 of them are relevant ($r = 10$). Your R-Precision is then $\frac{10}{30} = \frac{1}{3}$.

Precision@K

Precision@K is defined as the precision at rank $k$, which is more intuitive if you know about the definition of precision itself. Suppose your system retrieves 10 documents, where the relevant ones are at ranks ${1,3,6,7,9}$ and you want to know how 'well' your system does until rank 5 ('well' depends on the objective of your system of course but here we'll say we want high precision at low ranks). So you compute your Precision@5, which is the ratio of the number of relevant documents until (including) rank 5 to the total number of documents until $k$ (this number is $k$ itself). Your Precision@K where $K = 5$ is therefore $\frac{2}{5}$.

Youc an see that R-Precision is a measure that allows for assessment of your entire system whereas Precision@K really only takes the documents until $K$ into account. Depending on what you want to measure, either of them may be suitable.


It helps to remember that $\forall$ (or $\Pi$ as you sometimes see) is a type. It's generalizing $\to$. So while it makes perfect sense to say $(\lambda x : A. M)\ N$, it doesn't make sense to say $(\forall x : A. M)\ N$ because $\forall ...$ is just a type. You wouldn't say $(A \to B)\ N$ becaues $\to$ isn't for computing per-se, it's there to classify lambda terms which can be applied like this.

This was something that tripped me up as well, but this is how the calculus of constructions (as well as any other dependently typed system is defined).

The two programs you wrote have very different intentions and the first one is ill-typed. It doesn't make sense to say $\forall x : A.\ \lambda x.\ x$ because $\forall$ requires both its arguments by types which means that if $\forall x : A. B$ is to be well-typed, we must have $B : *$. However, $\lambda x. x$ isn't a type, it can only ever be assigned a type of the form $\forall x : A. B$, never $*$. The second one on the other hand is almost (I think you meant to return $a$ not $x$) is a function and is given a type using two $\forall$s.


Here are some crazy ideas, with absolutely no guarantee that they'll find a good solution -- but ideas you could try.

One possible heuristic approach might be to use quadratic programming combined with randomized rounding and some more heuristics.

In particular, introduce variables $x_i$ (for $i=1,2,120$); the idea is that $x_i=1$ means that $i$ is one of the 12 items you select, and $x_i=0$.  Now we have linear constraints $0 \le x_i \le 1$ and $x_1+x_2+\dots+x_{120} = 12$.  We could fix some constant $U$, introduce the constraint $\sum_i C_i x_i \le U$, and maximize the quadratic function $(\sum_i A_i x_i) \times (\sum_i B_i x_i)$.  Now the values of $x_i$ you get back won't necessarily be 0 or 1 (they'll probably be fractions), but you could use randomized rounding to convert it to a 0/1-solution.  Now sweep over a range of possible values of $U$ (increasing each time by a multiplicative factor of, say, 1.1 times the previous value), and keep the best solution you find.

This might work, or it might not, but it's something you could try.

You could also try formulating this as a semidefinite programming problem or quadratic programming with quadratic constraints (with each $x_i$ representing whether you take item $i$ or not), then apply randomized rounding to account for the fact that the $x_i$'s should all be 0 or 1.  In particular, if you work on the decision problem (does there exist a solution whether the objective function exceeds $r$?), then you can phrase everything using quadratic constraints -- the requirement that $(\sum_i A_i) (\sum_i B_i)/(\sum_i C_i) \ge r$ is equivalent to $(\sum_i A_i) (\sum_i B_i) - r (\sum_i C_i)$, which is a quadratic function in the $x_i$'s.  You might be able to express this as a semidefinite programming problem.

Another heuristic might be to try splitting this into sub-problems and then trying to merge, using a divide-and-conquer style approach.

Randomly partition the 120 items into two sets of 60, namely sets $L,R$ such that $|L|=|R|=60$ and $L\cup R=\{1,2,\dots,120\}$.  Enumerate all $60 \choose 6$ ways to choose 6 items from $L$, and compute the value of $(\sum A_i) (\sum B_i)/(\sum C_i)$ for each such subset of 6 items.  This gives you a list of ${60 \choose 6} \approx 2^{26}$ different 6-subsets, and a $U$-value for each.  Sort that list by decreasing value.  Do the same for $R$.

Now try to combine these two lists.  For instance, you could throw away all but the top 5% of each of the two lists, then try all ways of pairing up one subset of 6 items from the first list with one subset of 6 items from the second subset; compute the value of your objective function for each such subset of 12 items, and keep track of the best you've seen so far.

Repeat many times with many different ways of partitioning the 120 items into two sets of 60.

Again, I have no clue whether it will work well or not.  There's no reason to believe it will necessarily give the best solution.


In Big-O notation, what does it mean for T(n) to be upper bounded by something

Try it like this: "we can pick a constant $C$ such that, for sufficiently large $n$, $T(n)$ will always be less than $Cf(n)$".

Intuitively, this does indeed mean that lower-order terms and constant factors don't matter. Because lower-order terms stop mattering once $x$ gets sufficiently large, and constant factors can be cancelled out by an appropriate choice of $C$. If $T(n) = n^3 + 2019n^2 + 99999n + 10^{10}$, for example, that will still eventually be dominated by $Cn^3$, as long as $C > 1$ and $n$ is large enough—the $n^3$ term in that expression will eventually outweigh everything else. So we say that $T(n) \in O(n^3)$. (Some people use an equals sign instead; the meaning is the same.)

The "sufficiently large $n$", by the way, is why it's called "asymptotic" complexity: we only care about what happens as $n$ goes toward infinity, not what happens for "small" values.


Trouble finding what this recurrence solves to

Hint: can you solve it for $n = 2^k$ where we replace $O(1)$ with constant $c$ and let $f(1) = c$? Then you have:

$$f(2^k) = 2f(2^{k-1}) + c$$

Then the pattern starts $f(1) = c$, $f(2) = 3c$, $f(4) = 7c$, $f(8) = 15c$... any guesses?


There is no such thing as a C application. Code written in C is compiled to a binary ELF file on Linux or a .exe file on Windows.
The answer to the question is it depends if the function requires a syscall or not. If it doesn't require a syscall (on Linux):

You launch the ELF executable
The ELF executable is interpreted and the code and data is placed in memory. A new process takes place. All code including the Linux kernel code that the process requires is placed into memory and linked against the user code (dynamic linking).
When the process calls a function, its arguments are placed on the stack, the function code runs and the function returns.

It is as simple as that for a situation when the kernel function doesn't require a syscall.
If it requires a syscall:

Steps 1 and 2 above.
The function is called as usual with its arguments on the stack.
When the kernel function requires to access hardware (like when using printf() to print to the screen), it uses system calls.
A system call is done using software interrupt 0x80 (the assembly instruction int 0x80).
The CPU is interrupted, looks in the IDT (https://wiki.osdev.org/Interrupt_Descriptor_Table), determines the address of the handler and jumps to the handler.
The interrupt handler for a system call contains a special instruction: SYSENTER (https://wiki.osdev.org/Sysenter). The SYSENTER instruction makes the processor switch from user mode to kernel mode. A special MSR register contains the address at which the processor will jump when executing a SYSENTER instruction. To write to this register, the OS uses the WRMSR special instruction at boot.
The CPU jumps to the address specified by the MSR register. It is now in kernel mode. It runs whatever code is needed to perform the requested operation (specified in EAX by the caller). It then returns the result to the caller by using certain registers depending on the system call. To return it calls SYSEXIT.
The request was fulfilled, so the user code can continue where it was.

Here is an example of Hello World app in assembly which does a syscall. Your printf() function will be compiled to something similar.
section .data
    hello:     db 'Hello world!',10    ; 'Hello world!' plus a linefeed character
    helloLen:  equ $-hello             ; Length of the 'Hello world!' string

section .text
    global _start

_start:
    mov eax,4            ; The system call for write (sys_write)
    mov ebx,1            ; File descriptor 1 - standard output
    mov ecx,hello        ; Put the offset of hello in ecx
    mov edx,helloLen     ; length of the string in edx

    int 80h              ; Call the kernel

    mov eax,1            ; The system call for exit (sys_exit)
    mov ebx,0            ; Exit with return code of 0 (no error)
    int 80h

The right answer would be
printf() -> User-space library -> system call -> kernel driver
The printf() function is placed in RAM alongside your code (and dynamically linked against it), the function is called, makes a system call which brings the processor in kernel mode using SYSENTER and then calls kernel drivers which do the required task like writing to the screen or writing to IO devices.


Quicksort where element comparison outcome is random. Probability of element being in a certain position

In quick sort, after a partition, you have placed every element smaller than your pivot p below p and every element larger than p above it. Therefore after a partition you know the pivot is in the correct position and therefore it will not be moved again. Since you choose the last element (M8) as your pivot, this simplifies the process, since you only have to go through one iteration.

When you compare each element to M8, you will randomly be told that M8 is greater or the other element is "greater" each with 1/2 odds, and if the other element is "greater" it will be placed to the right of M8. Therefore, for M8 to end up in position 0, 1, or 2 it will have to have 2 or less elements that are determined to be "smaller" than M8. We can determine this probability through a geometric sequence:

0: (0.5^7)(0.5^0)(C(7,7)) = (0.5^7)(1) = .0078125

1: (0.5^6)(0.5^1)(C(7,6)) = (0.5^7)(7) = .0546875

2: (0.5^5)(0.5^2)(C(7,5)) = (0.5^7)(21) = .1640625


Can an independent set (of vertices) be a vertex cover as well?

If something satisfies the definition of $X$ and the definition of $Y$, then it is both an $X$ and a $Y$.

Although it's true that, whenever $S$ is independent, $V\setminus S$ is a vertex cover, it's possible for both $S$ and $V\setminus S$ to be independent: this happens when $S$ is one side of a bipartite graph, as is the case in the example in the question.


Error correction for windowed reads from cyclic tapes

I don't know if this problem has been studied, and I bet there will be better solutions, but I'll suggest a scheme that I suspect might work well enough, even if it's not optimal.
Naive approach: brute-force decoding
I would bet that any erasure code would work, if combined with brute-force decoding.  For decoding, I am imagining that a naive algorithm is to enumerate all possibilities for what the starting point was, decode under that assumption, and check whether it leads to a correct reconstruction that is consistent with that assumption (i.e., all symbols you read match).  Heuristically, I would expect that typically there will be only one decoding that is consistent with the observed data.  This might be a bit slow -- decoding might take $O(MN)$ time for many codes, because of need to try all $O(N)$ possibilities for the starting point -- but if that's acceptable, it should be something that's easy to implement.
For instance, you could use a Reed-Solomon code.  To encode a message, you treat it as a polynomial $p(x)$ of degree less than $M$ (say, of degree $M-1-\lg N$) over some finite field (i.e., the bits of the message determine the coefficients of $p(x)$).  Then, you write $p(\alpha^i)$ in the $i$th position on the tape, for $i=1,2,\dots,N$ (where $\alpha$ is a fixed element of the finite field).  For each guess at where the read symbols might have started from, you can decode using polynomial interpolation.  The entire procedure will take $O(MN \log M)$ time, to decode.
Faster approach: rolling hash
Here is an alternative that should be me faster: it runs in linear time.  I expect it will be close to optimal.
Encoding algorithm.  Let $C$ be a small constant, to be chosen later.  Let's suppose we have a message that is $M-C$ symbols long.  We'll compute a Rabin-Karp rolling hash of the message, a hash that is $C$ symbols long, and append it to the message.  Then, we'll repeat these $M$ symbols cyclically, to get a $N$-symbol word.  That will be the codeword that is the encoding of the message.  Encoding can be done in $O(N)$ time.
Decoding algorithm. Given an observed value $Y$ with $M$ symbols, we'll try all $M$ possibilities for cyclically shifting it to see which is correct.  We can recognize when we have the correct shift because the last $C$ symbols will be the valid hash of the first $M-C$ symbols.
Naively, this decoding procedure would take $O(M^2)$ time.  However, we can use the properties of the Rabin-Karp rolling hash to make decoding much more efficient.  Let $H(x)$ denote the Rabin-Karp hash of $x$.  Note that we can apply the Rabin-Karp rolling hash to $Y$ and learn $H(Y_{1..i})$ for each $i$; we can compute all $M$ of these hashes in $O(M)$ time.
From $H(Y_{1..i-1})$ and $H(Y_{1..j})$, we can compute $H(Y_{i..j})$ in $O(1)$ time. Also, given two hashes $H(x_1)$ and $H(x_2)$, we can compute the hash $H(x_1||x_2)$ of the concatenation of $x_1$ and $x_2$ in $O(1)$ time.  Thus, for any candidate cyclical shift of $Y$, we can compute the hash of the first $M-C$ symbols in $O(1)$ time, given the precomputed values $H(Y_{1..i})$, and thereby check whether this candidate shift is correct (by comparing that hash to the last $C$ symbols of the shifted value).  This decoding algorithm does an initial $O(M)$-time precomputation to compute all of the $H(Y_{1..i})$ values, and then checks $M$ candidates, each of which takes $O(1)$ time, for a total decoding time of $O(M)$.
Choosing parameters. Lastly, I need to describe how we choose the constant $C$.  I suggest choosing it so that it is very unlikely that any incorrect decoding will survive the hash-value check.  Suppose each symbol is $b$ bits long.  Then, a $C$-symbol hash is $bC$ bits long, and each incorrect candidate shift has a $1/2^{bC}$ chance of being wrongly accepted (by having the hash value match just by sheer chance).  We test $M$ candidate shifts, so there is about a $M/2^{bC}$ chance that one of these is wrongly accepted.  We might set as a goal that this chance should be at most $1/2^{50}$ (so that the chance of wrongly accepting an invalid message is less than the chance of being struck by lightning multiple times, and less than the chance of a cosmic ray hitting your computer and causing a bitflip error, i.e., negligibly small).  This means we need $M/2^{bC} \le 1/2^{50}$, so it suffices to take $C = \lceil(50 + \lg M)/b \rceil$.


Proving that finding wheel subgraphs is NP-complete

Hint: Hamiltonian Cycle is $NP$-Complete.


As far as we know, there is no polynomial-time algorithm for HPP. Put differently, there is no known polynomial-time reduction from any NP-hard problem with the properties that you require to Parity-HPP.

If such a reduction did exist, we could reduce any NP-hard problem A to Parity-HPP (in polynomial time) and then solve A using the polynomial-time algorithm that you claim.


Can subtracting o(1) from the parameter of a function change its Θ-class?

Let $g(n) = 1/n$ and define
$$ f(n) = \begin{cases} n & \text{if $n$ is an integer}, \\ \log \lceil n \rceil & \text{otherwise}. \end{cases} $$
For an integer $n>1$, $f(n) = n$ while $f(n-g(n)) = \log n$.


Can you explain this improvement to this frequency distribution algorithm?

You don't really choose $\epsilon$. Rather, you (virtually) add $k-\epsilon$ and $k+\epsilon$ to your linear order at the correct spots, a feat which you accomplish by modifying your comparison function. Binary search requires you to answer queries of the form $x < y$. When looking for $k-\epsilon$ (or $k+\epsilon$), either $x$ or $y$ could be $k-\epsilon$ (or $k+\epsilon$), and so we have to extend the definition of the comparison function, as follows:
$$
k-\epsilon < y \text{ if } k \leq y \\
x < k-\epsilon \text{ if } x < k \\
k+\epsilon < y \text{ if } k < y \\
x < k+\epsilon \text{ if } x \leq k
$$
The comparison functions on the right are the original ones (with $x \leq y$ being shorthand for $x < y$ or $x = y$), and the ones on the left are the new ones.


complexity classes defined as limits or "globally"?

Complexity classes are (usually) expressed using Landau notation, which makes precise what you state. See also our reference questions.

Yes, by definition (usual) complexity classes don't say anything about the real world per se. That is by design; complexity is a model for classifying the inherent hardness problems, not a tool to design or analyse algorithms.
See also here for some related thoughts.

  Is there a way to talk about complexity for finite n?

"Complexity" and "finite" are mutually exclusive. Of course you can study, say, the (relative) performance of algorithms on real(istic) data. The machinery of complexity theory and, sadly, "Big-Oh"-driven algorithm analysis will be mostly useless then.


How to reduce number of move operations in an array?

The example in the question

The minimum number of moves needed for the example in the question, from [0, 1, 2, 3, 4, 5] to [2, 1, 4, 0, 5, 3] is 3.

            // [0, 1, 2, 3, 4, 5], where 2, 4, 5 are good.
move(2, 1); // [0, 2, 1, 3, 4, 5], where 2, 1, 4, 5 are good.
move(0, 4); // [2, 1, 3, 4, 0, 5], where 2, 1, 4, 0, 5 are good.
move(2, 5); // [2, 1, 4, 0, 5, 3], where 2, 1, 4, 0, 5, 3 are good.

The idea is to split the target array into two subsequences, 2, 4, 5 and 1, 0, 3 where the first subsequence is the longest increasing subsequence. Keeping the order of elements in the first subsequence, we will move the remaining elements  from left to right to their expected positions respectively, i.e, first moving 1 to its expected positions and so on.

An algorithm

Input: Array $A = [0, 1, 2, ..., n-1]$ and array $B[0], B[1], ..., B[n-1]$ which is a permutation of $0, 1, 2, ..., n-1$.

Output: A list of minimum size each of whose elements is an operation of the form move(fromIndex, toIndex) such that after performing that list of operations on $A$, $A$ becomes $B$.

Procedure: $B$ is intact while $A$ will be changed move by move.

Let $B[s_1], B[s_2], \cdots, B[s_m]$ be the longest increasing subsequence of $B$. This can be done as described in this Wikipedia article. It can also be done as described in this Wikipedia article since the longest increasing subsequence of $B$ is the longest common subsequence of $A$ and $B$.  Let $s_{-1}=-1$ and $s_{m+1}=n$.
Let $O$ be an empty list of operations. For $i$ from -1 to $m$ inclusive do:

For $j$ from $1$ inclusive to $s_{i+1} - s_i $ exclusive do:

Find $x$, the index of $B[s_i]$ in $A$. If $i=-1$, let $x=0$.
find $y$, the index of $B[s_j + j]$ in $A$.
Move $A[y]$ to the $j$-th place after the place of $A[x]$.
Add $\text{move}(y, x + j)$ to $O$.

Now all numbers in $B$ up to index $s_{i+1}$ are good, i.e., sorted in the same order in $A$ and in $B$, although the same number might be at different indices in $A$ and in $B$.

Correctness

It is clear that at the end of the algorithm, all numbers in $A$ are sorted in the same order in $B$ and in $B$, i.e., $A$ is $B$. The total number of moves in the algorithm is $$(s_0-s_{-1}-1) + (s_1-s_{0}-1)+\cdots + (s_{m+1}-s_{m}-1) = s_{m+1}-s_0-(m+1)=n.$$

On the other hands, each move(fromIndex, toIndex) in any algorithm can increase the common longest subsequence between $A$ and $B$ by at most 1. So $n-m$ moves are needed.

This is pointed out by xskxzr first.

Complexity

It takes $O(n\log n)$ or $O(n^2)$ to find the longest increasing subsequence. Finding the index of a number in $A$ is performed about $2n$ times, which costs $O(n^2)$ in total. It takes $O(n^2)$ to perform all $n$ moves. So the algorithm runs in $O(n^2)$ time.

The implementation of finding the index of a number can be sped up so that the algorithm can be implemented to run in $O(n\log n)$ time.

Exercises

Exercise 1. (One minute or two) Array $A$ is a permutation of $0, 1, \cdots, n-1$. State an algorithm that find a list of operations of the form move(fromIndex, toIndex) such that will sort $A$ in minimum steps.

Exercise 2. The same input is given. Find an algorithm that computes the minimum number of moves needed to change $A$ so that it ends up the same as $B$ up to a cyclic shift. For example, when $B=[2, 1, 4, 5, 0, 3]$, $A$ should be changed to one of $[2, 1, 4, 5, 0, 3]$, $[1, 4, 5, 0, 3, 2]$, $[4, 5, 0, 3, 2, 1]$, $[5, 0, 3, 2, 1, 4]$, $[0, 3, 2, 1, 4, 5]$ and $[3, 2, 1, 4, 5, 0].$


This is a weighted version of Set Packing, which was one of the 21 classic problems proven NP-hard by Richard Karp:

  Richard M. Karp (1972). "Reducibility Among Combinatorial Problems"
  (PDF). In
  R. E. Miller and J. W. Thatcher (editors). Complexity of Computer
  Computations. New York: Plenum. pp. 85–103.

As the unweighted version is already NP-hard, your weighted version is too, so it's unlikely that any algorithm will solve every instance of it in polynomial time.


"100% greater throughput" means a (local) speed-up by factor $k=2$.


Adding an ordered into a relationship without violating the functional dependencies

First of all, the classical relational theory does not include null values, and for this reason the concept of functional dependency (and violation of FD) is not defined in presence of such values.

Note that NULL is not a constant, neither a different value each time it is used. This can be seen if you try something like:

SELECT NULL = NULL;

the result is neither TRUE (the two values are in effect the same value) nor FALSE (the two values are different), but NULL, which means that we have no information at all about the real values (even if they exist or not!). And this is the foundamental reason for which it has no sense to consider or not a violation of a FD in presence of a null value.

For instance, considering your question, let's think about the meaning of a functional dependency. Since from the dependencies that you have listed we can derive A -> D, this means that each time in a tuple there is a certain value of the attribute A, there should be the same value of the attribute D. But if we have two tuples with the same value of A, and one of them has a NULL value for D, while the other has a normal value, this means that we do not know if the dependency is violated or not, since we do not know nothing about the value of the attribute specified as NULL. It could be unknown, and be the same, or different, or it could not be present. So nothing can be said about the violation.


What does Godels Incompleteness theorem "true but unprovable" mean?

Your difficulties are hinting toward Gödel's second incompleteness theorem. The proof system $\Pi$ can formalize most steps in the proof, other than its own consistency – the fact that $\Pi$ cannot prove a statement and its negation. Following exactly this train of though, Gödel showed that a sufficiently strong proof system cannot prove its own consistency.

For more information, I suggest looking up resources on Gödel's second incompleteness theorem.


Karp hardness of searching for a matching erosion

In the theory of finite undirected graph, a basic notion that is broadly studied is the notion of matching cut. A matching cut in a graph $G$ is defined to be a matching subgraph of $G$ that is also the edge set of a cut. A $\it cut$ of a graph $G = (V, E)$ is a partition of the vertex set $V$ into two sets $(A, B)$ such that $A$ and $B$ induces two disjoint induced subgraphs that were before incident to some crossing edges which are the edges in the corresponding so-called edge cut set. Specifically, the edge set of the cut $(A, B)$ is then defined to be the subset of $E$ containing all the edges with one endpoint in $A$ and the other endpoint in $B$, i.e. those edges $uv$ with $u\in A$ and $v\in B$. A matching cut is formally defined to be the edge set of such a cut, whenever its edge cut set is indeed a matching. It is worth noting that a matching subgraph which removal increases the number of connected components of a graph $G$ is not necessarily a matching cut, since it may contain edges inside the two separated induced subgraphs. It is a matching cut if it contains exactly the edges of the cut. In order to have more hard computational problems in our still very limited arsenal of proven hard problems, we want to restrict this notion further. We define a {\it matching erosion} as a matching cut $(A, B)$ such that $A$ is exactly one side of the matching. It means that each vertex $v\in A$ has exactly one edges out of $A$, and for any two different vertices $u, v\in A$ their crossing edges end in different vertices in $B$. Intuitively, such a matching split $M=(A,B)$ visually ''peels" off $A$ from $G$.

Formally, we define a matching erosion of an undirected graph as follows:

DEFINITION 1

Given an undirected graph $G=(V, E)$, a matching erosion $(A, B)$ is a partition of $V$ into two disjoint sets $V = A\cup B$ such that:

$G[A]$ and $G[B]$ are two disjoint induced subgraphs
The edge set of the cut is a matching: $M = \{uv\in E\vert u\in A \land v\in B\}$ is a matching
Every $u\in A$ is incident to an edge in $M$

Then, our problem naturally asks whether a given undirected graph $G$ has a matching erosion.

DEFINITION 2

Matching Erosion of a graph:

Input: An undirected graph $G(V, E)$

Output: Yes if $G$ has a matching erosion $(A, B)$, otherwise No

In the next section, we will show that Matching Erosion is computationally hard.

We will reduce Exact 3-Set Cover problem to our problem. Exact 3-Set Cover is another decision problem defined as follows. In Exact 3-set Cover, we are given a universe set of elements $U=\{e_1, e_2, \dots, e_{3n}\}$ and a collection $F=\{s_1, s_2, \dots, s_m\}$ of subsets of $U$. Each subset $s_j$ in $F$ contains exactly $3$ elements $e_{s_j1}, e_{s_j2}, e_{s_j3}\in U$. The decision problem asks whether there exists a subcollection $F'\subseteq F$ such that each element $e_i$ of $U$ is contained in exactly one subset $s_j$ in $F'$. Obviously, $F'$ will contain exactly $n$ subsets in the collection $F$. Such a collection $F'$ is called an exact cover of $U$.

DEFINITION 3

Exact 3-Set Cover problem:

Input: a universe $U = \{e_1, e_2, \dots, e_{3n}\}$ and a collection $F=\{s_1, s_2, \dots, s_m\}$ of subsets of $U$, where each $s_j$ contains $3$ elements $e_{s_j1}, e_{s_j2}, e_{s_j3}\in U$

Output: Yes if there exists an exact cover $F'\subseteq F$, otherwise No

Exact 3-Set Cover is shown to be hard by Garey and Johnson. After describing and proving the correctness of the reduction in the next section, we will establish the following claim.

CLAIM 4

We have that Exact 3-Set Cover $\leq_p$ Matching Erosion

Reducing EXACT 3-SET COVER to MATCHING EROSION

In this section, we prove the claim 4.

Proof:

Describing the construction: Given an instance $(U, F)$ of Exact 3-Set Cover, we will construct an undirected graph $G=(V, E)$ as the produced instance of our problem Matching Erosion. For each element $e_i$ in the universe $U$, we create a new vertex $e_i\in V$. Similarly, for each subset $s_j\in F$, we create a new $K_3$ consisting of 3 new vertices $s_{j,1}, s_{j,2}, s_{j,3}\in V$. For each such subset $s_j = \{e_{s_j1}, e_{s_j2}, e_{s_j3}\}$, we add the $3$ edges to $E$, namely $s_{j,1}e_{s_j1},\:s_{j,2}e_{s_j2},\:s_{j,3}e_{s_j3}$. Finally, we add all edges between pairs of two different vertices of the $e_i$'s vertices to turn these into a $K_{3n}$ clique.

Correctness of the construction:
Suppose that $(U, F)$ has an exact cover $F'\subseteq F$ consistig of $n$ subsets in $F$, then based on that solution to \textsc{Exact 3-Set Cover}, we will easily construct a solution to the produced instance $G(V, E)$ of our problem Matching Erosion. Namely, our matching erosion for $G$ would have $A$ to be the set of all the $K_3$'s of the subsets included in the exact cover. Clearly, each vertex $s_{j,k}$ (where $s_j$ is included in the exact cover and $1\leq k\leq 3$) in this set $A$ is connected to exactly one vertex outside of $A$, namely its corresponding element $e_{s_jk}$ in the universe $U$. Obviously, this is a matching cut that happens to be also a matching erosion.

Conversely, if $G(V, E)$ has a matching erosion $M = (A, B)$, we shall show that none of the elements $e_i$ in the universe is included in $A$. Indeed, if some $e_i$ is included in $A$ then at most one $e_l$ is not in $A$. This is because if there exist $e_i\in A$ and $e_{l1}, e_{l2}\not\in A$ then $A$ cannot form one side of a matching erosion since $e_i\in A$ is incident to two crossing edges $e_ie_{l1}$, $e_ie_{l2}$, recall that the universe $U$ is turned into a $K_{3n}$ in $G$. So, if one element in $U$ is included in $A$, at most one element $e_l$ can be in $B$, but this is also clearly not the case. Because if so, then all the other element $e_i$'s (which are included in $A$) are connected to $e_l\in B$ violating the definition of a matching erosion. So, we have shown that if some element $e_i$ is included in $A$, then all of the $K_{3n}$ corresponding to $U$ in $G$ are included in $A$. But, this also cannot be the case for a matching erosion. We need the following observation.

Observation: For each $K_3$ corresponding to a subset $s_j$, a vertex $s_{j,k}$ in this $K_3$ is included in $A$ iff. all the three vertices of this $K_3$ are included in $A$.

Proof (of the observation):
Obviously, by definition of a matching erosion.

Using this observation, we are able to show that a matching erosion cannot include all the $K_{3n}$ to $A$. Indeed, if so, the matching erosion will then partition the $K_3$'s into two disjoint sets of $K_3$'s, those in $A$ and those in $B$. The $K_3$'s in $B$ would then intuitively form an exact cover for $U$. But, unfortunately, in this case, those vertices of the $K_3$ in $A$ cannot have any crossing edge in $M$, thus violating the definition of a matching erosion.

We have therefore shown that none of the elements $e_i$ in the universe is included in $A$. This implies that $B$ contains all the $K_{3n}$. So, the matching erosion needs to partition the set of $K_3$'s into two disjoint sets of $K_3$'s, those in $A$ and those in $B$ like before. But fortunately, the situation is now reversed. the $K_3$'s in $B$ does not need any crossing incident edge (this is only required in a matching split). And, the $K_3$'s in $A$ would form an exact cover for $U$.


How is this formula for dynamic array reached?

Let's look at the moment just after we copy the array to insert element $2^k + 1$, so we're doubling the array size from $2^k$ to $2^{k+1}$. There are $n = 2^k$ elements in the array at this moment.

The first term in the sum is $1 \cdot n/2$, representing the fact that $n/2$ elements (namely, elements $(n/2+1), \ldots, n$) have been copied exactly once (just now!).

The next term is $2 \cdot n/4$. The previous $n/4$ elements - that is, elements $(n/4) + 1, \ldots, n/2$ - will have been copied exactly twice, once just now and once when we expanded the array from size $n/2$ to $n$.

The next term is $3 \cdot n/8$. The previous $n/8$ elements will have been copied three times: now, at the last expansion and at the second-to-last expansion when we expanded from size $n/4$ to $n/2$. You can probably see where this is going by now.

The thing to remember is that each element gets copied every time the array expands after the element in question has been inserted, and the copies happen every time the size exceeds a power of two.


Is developing an OCR considered a research project?

Rifat, you have to ask your supervisor.  If (s)he accepts, then go for it, otherwise go back to the drawing board.

If this is, as you say, an area for which an OCR does not yet exist, then it sounds perfectly fine for an undergraduate project, but do not expect any reputable conference or journal to publish your results.


If I understand you correctly, one solution to your problem would be to compute a spanning forest. A spanning forest of a graph is a smallest possible (in terms of number of edges) graph such that there's a path between two vertices in the forest if, and only if, there's a path between them in the original graph.


Time complexity of insertion in binary search tree

It can't   be $O(n)$.
Suppose $n=2^k$,and for given $n$ elements, we inserted $\frac{n}{8}$ and $T$ is balanced. Now suppose you insert next $\frac{n}{8}$, But suppose when you inserted
$\frac{1}{2}\frac{n}{8}$ elements that  those make a chain with length $O(n)$. So for next $\frac{1}{2}\frac{n}{8}$    elements you maybe have cost $O(n)$ for each insertion. As a result the time complexity of $n$ insertion is $O(n^2)$.


Consider such a triplet $(a,b,c)$, and root $T$ at $a$. Let $e$ be the lowest common ancestor of $b$ and $c$. If $e = a$ then $d(b,c) = 2d(a,c)$, and we conclude that $a=b=c$. If $e \neq a$, then if we now root $T$ at $e$ then $e$ is the lowest common ancestor of $a,b,c$ (pairwise). That means that $a,b,c$ belong to different branches below $e$.

This gives rise to the following algorithm. First, there are $n$ triplets of the form $(a,a,a)$, which you may or may not want to count. Second, each triplet $(a,b,c)$ comes with its unique vertex $e$. So we enumerate over the vertices $e$, root $T$ at $e$, and for each child $f$ of $e$, count the number of vertices at any given depth; this takes time $O(n)$. Now for each depth $D$, we are given a list $a_1,\ldots,a_k$ corresponding to the number of vertices at depth $D$ for the children of $e$. We want to compute
$$ \sum_{i<j<k} a_i a_j a_k = \frac{1}{6} \left(\sum_i a_i\right)^3 - \frac{1}{2} \left(\sum_i a_i^2\right) \left(\sum_i a_i\right) + \frac{1}{3} \sum_i a_i^3.$$
This phase can also be accomplished in $O(n)$ (going over all possible depths), with some care (you need to sort the children according to depth, but that can be done in linear time since the depths are integers from $0$ to $n-1$; other details left to you). Therefore the entire algorithm is $O(n^2)$.

My guess is that you can find the number of triplets in $\tilde{O}(n)$.


How is CFL-reachability solvable in exponential time and space?

Please refer to the paper Program Analysis via Graph Reachability by
Thomas Reps where he mentions clearly that CF-reachability is solvable in cubic time.

I assume CFL-reachability is defined as follows:

A CFL-reachability problem is  where a path is considered to connect two nodes only if the concatenation of the labels on the edges of the path is a word in a particular context-free language (an $L$-path):

Definition 2.1 (from paper above). Let $L$ be a context-free language over alphabet $\Sigma$, and let $G$ be a graph whose edges are
labeled with members of $\Sigma$. Each path in $G$ defines a word over $\Sigma$, namely, the word obtained by concatenating, in order, the labels of the edges on the path. A path in $G$ is an $L$-path if its word is a member of
$L$.


Find the error in the following “proof” that $O(n) = O(n^2)$

You're basically claiming that $O(n^2+n-n^2)$ is the same thing as $O(n^2)$, and that's not true.


A category consists of:

Objects.
Directed arrows between objects. There can be multiple arrows between any two given objects, or a unique arrow, or none.
A composition map for arrows that takes an arrow $f$ from $x$ to $y$ and another arrow $g$ from $y$ to $z$ and outputs an arrow $gf$ from $x$ to $z$.
Depending on the formulation, there might also be a distinguished arrow between every object and itself (the identity arrow).

The composition map has to satisfy the following axioms:

Associativity: if $f\colon x \to y$, $g\colon y \to z$ and $h\colon z \to w$ then $h(gf) = (hg)f$.
Identity: if $f\colon x \to y$ and $1_x\colon x \to x$ and $1_y\colon y \to y$ are the distinguished self loops then $f1_x = 1_yf = f$. (If the formulation does not include the distinguished self-loops: there exist arrows $1_x\colon x\to x$ and $1_y\colon y\to y$ such that $f1_x = 1_yf = f$.)

You can represent this data in many ways. A graph with multiple edges is, however, not enough, since you also need to specify the composition map.


Show Resource Allocation Problem is NP-Complete

Let's try to do some pattern matching. In independent set, we are given a graph, and want to find a maximum number of vertices satisfying some constraints. In your problem, we are given a collection of tasks and resources, and want to find the maximum number of resources satisfying some constraints. Hence it seems that tasks should correspond to vertices.

What about the constraints? In independent set, we are allowed to choose two vertices together if no edge connects them. In your problem, we are allowed to choose two tasks together if they have no common resource. Hence it seems that resources should correspond to edges.

You take it from here.


Many such exercises are best solved by writing down programs in your favorite programming language. However, a typical programming language cannot examine its own source code, or the source code of a subroutine, or of another program, whereas a Turing machine can. So we need to enrich the language with two special constructs:

eval(x,y) which runs source code x on input y and returns the result. This is more or less the universal Turing machine. (Yes, the Python toplevel interactive shell is the same thing as a universal Turing machine.)
uneval(f) which accepts a function f and returns its source code. This allows us to inspect source code, and to simulate it step-by-step (we can implement a "debugger" by hand once we get acces to source code).

Strictly speaking, eval is not needed because it can be implemented in a general-purpose programming language. It amounts to implementing an interpreter for the language inside the language itself, a favorite programming exercise of people who design programmng languages.

So, to so solve your exercise in Python:

def H1(x):
  "Simulate the machine x on input x. Return 1 if it halts, cycle otherwise."
  eval(x, x)
  return 1

That was easy, and to the point. Fiddling with Turing machines just obscures the fact that this is a very easy exercise (although at some point you do need to convince yourself that Turing machines can do all the things that a programming language can do, and vice versa).

By the way, when you pose questions here, you should not assume that everyone knows your textbook by heart. You should explain notation such as $\Phi(x,x)$. I had to guess what you meant.


The validity of the potential function for splay tree

Answer My Own Question:

The short answer:

We don't have to verify $$\forall 1 \le i \le m: \Phi(T_i) \ge \Phi(T_0).$$ This condition is a special case of a more general one, which we need to verify for this example.

The detailed answer:

Consider a data structure $D$ and its states $D_0 \cdots D_m$ produced by a sequence of $m$ operations $o_1 \cdots o_m$:
$$
D_0,\; o_1,\; D_1,\; o_2,\; \cdots,\; \underbrace{D_{i-1},\; o_{i},\; D_{i}}_{\text{the $i$-th operation}},\; \cdots,\; D_{m-1},\; o_{m},\; D_{m}.
$$

The amortized cost of the $i$-th operation $o_i$ is defined as:
$$\hat{c_i} = c_i + \Big(\Phi(D_{i}) - \Phi(D_{i-1})\Big)$$

Therefore, the total actual cost of these $m$ operations equals the total amortized cost plus the net decrease in potential from the initial to the final state.

$$
\sum_{1 \le i \le m} c_i = \left( \sum_{1 \le i \le m} \hat{c_i} \right)
 + \Big(\underbrace{\Phi(D_{0}) - \Phi(D_m)}_{\text{net decrease in potential}} \Big).
$$

For each upper bound $\Box$ for $\Phi(D_{0}) - \Phi(D_m)$, we get a corresponding upper bound for the total actual cost of all operations:

$$
\sum_{1 \le i \le m} c_i \le \left( \sum_{1 \le i \le m} \hat{c_i} \right) + \Box.
$$

The condition $$\forall 1 \le i \le m: \Phi(D_i) \ge \Phi(D_0)$$ in the post is just a special case of deriving upper bounds for the total actual cost, where the upper bound is the total amortized cost. Moreover, it is common to choose $\Phi$ such that $\Phi(D_0) = 0$ and $\Phi(D_i) \ge 0$ for all $i$.

To verify the validity of the potential function for splay trees, we use the following upper bound for $\Phi(T_{0}) - \Phi(T_i)$:

$$\Phi(T_{0}) - \Phi(T_i) \le n \log n.$$


Inference rules for deriving invariants in Hoare logic

There are two ways to answer the question.

The first is on the level of propositional logic. You have three statements, $S_1=S_2$, $(X=\Lambda\wedge Y=\Lambda)$, and $E=true$. Let's call them $A$, $B$, and $C$ for short. (2) is $A\Leftrightarrow(B\wedge C)$ and (3') is $A\Leftrightarrow C$. At point (3') we know $B$. Every assignment of the propositional variables that satisfies $B$ and (2) also satisfies (3'). In other words, at the position (3') we know

$(A\Leftrightarrow(B\wedge C))\wedge B$

from which

$(A\Leftrightarrow C)$

follows semantically. If the propositional proof system of your choice is complete, the above can also be derived using its rules.

The second answer addresses Hoare logic instead of propositional logic. Hoare logic has its own derivations. The neat thing is that most of them can be automated. And they work backwards. In the case at hand, (3') is derived from (4) by copy. After all, at the end of the else clause, the same invariant must hold as after the if-then-else. The then clause does not follow that rule, so let us fix the code

// (2) S1 = S2 <=> X = /\ and Y = /\ and E = true
// (2') (!(X == /\ and Y == /\) and (S1 = S2 <=> false = true)) or
//    ((X == /\ and Y == /\) and (S1 = S2 <=> E = true))
if !(X == /\ and Y == /\)
  // (3'') S1 = S2 <=> false = true
  E = false
  // (3) S1 = S2 <=> E = true
else // an empty else
  // (3') S1 = S2 <=> E = true
// (4) S1 = S2 <=> E = true

Now (3) is derived from (4) by copy, (3'') is derived from (3) by substitution (that is the Hoare logic rule for assignment) and (2') is derived from (3''), (3') and the if condition. It remains to see how (2') follows from (2). That is propositional logic plus $false\not=true$.


Length of shortest word accepted by exactly one of two DFAs

Construct the product automaton $M = M_1 \times M_2$, which contains $nm$ states. Since $L(M_1) \neq L(M_2)$, the automaton $M$ contains a state $(q_1,q_2)$ reachable from its initial state such that $q_1$ is an accepting state of $M_1$ and $q_2$ is not an accepting state of $M_2$, or vice versa. Since $M$ contains $nm$ states, this state is reachable from the initial state of $M$ by a path of length at most $nm-1$. This corresponds to a word of length $nm-1$ which is in $L(M_1)$ but not in $L(M_2)$, or vice versa.

Using the method of this answer, we can improve the bound to $n+m-2$. This is tight for $m=1$, as the example of $L(M_1) = \sum_{k=0}^{n-2} \Sigma^k$ and $L(M_2) = \Sigma^*$ shows.


What is the Relationship Between Programming Languages, Regular Expressions and Formal Languages

Whoever told you that regular expressions are used to parse code was spreading disinformation. Classically (I don't know to what extent this is true in modern compilers), the parsing of code – conversion of code from text to a syntax tree – is composed of two stages:

Lexical analysis: Processes the raw text into chunks such as keywords, numerical constants, strings, identifiers and so on. This is classically implemented using some sort of finite state machine, similar in spirit to a deterministic finite automaton (DFA).
Parser: Run after lexical analysis, and converts the raw text into an annotated syntax tree. The grammar of programming languages is (to first approximation) context-free (actually, one needs an even stricter subset), and this allows certain efficient algorithms to parse the lexified code into a syntax tree. This is similar to the problem of recognizing whether a given string belongs to some context-free grammar, the difference being that we also want the proof in the form of a syntax tree.

Grammars for programming languages are written as context-free grammars, and this representation is used by parser generators to construct fast parsers for them. A simple example would have some non-terminal STATEMENT and then rules of the form STATEMENT$\to$IF-STATEMENT, where IF-STATEMENT$\to$if CONDITION then BLOCK endif, or the like (where BLOCK$\to$STATEMENT|BLOCK;STATEMENT, for example). Usually these grammars are specified in Backus-Naur form (BNF).

The actual specifications of programming languages are not context-free. For example, a variable cannot appear if it hadn't been declared in many languages, and languages with strict typing might not allow you to assign an integer to a string variable. The parser's job is only to convert the raw code into a form which is easier to process.

I should mention that there are other approaches such as recursive descent parsing which doesn't actually generate a parse tree, but processes your code as it parses it. Although it doesn't bother to generate the tree, in all other respects it operates at the same level as described above.


How to analyze the performance of a genetic algorithm experimentally?

The typical approach is performing several runs of the evolutionary algorithm (EA) and plot the average performance over time (average performance of best-of-run-individual NOT population average).

A good rule of thumb is performing a minimum of 30 runs (of course 50-100 runs is better).

The average is better than the best-value-achieved-in-a-set-of-runs but variance should also be taken into account.

There are some nice examples on Randy Olson's website:

  The average fitness of both algorithms over several replicates. From this graph, we would conclude that our algorithm performs better than the current best algorithm on average.

  The average fitness with a 95% confidence interval for each algorithm. This graph shows us that our algorithm does not actually perform better than the current best algorithm, and only appeared to perform better on average due to chance.

The basic breakdown of how to calculate a confidence interval for a population mean is as follows:

Identify the sample mean $\bar{x}$. While $\bar{x}$ differs from $\mu$, population mean, they are still calculated the same way: $$\bar{x} = \sum {x_{i} \over n}$$
Identify the (corrected) sample standard deviation $s$: $$s = \sqrt{\frac{\sum_{i=1}^{n}{(x_i - \bar{x})^2}} {n-1}}$$
$s$ is an estimation of the population standard deviation $\sigma$.
Calculate the critical value, $t^*$, of the Student-t distribution. This value is dependent on the confidence level, $C$, and the number of observations, $n$.

The critical value is found from the t-distribution table (most statistical textbooks list it). In this table $t^*$ is written as $$t^*(\alpha, r)$$ where $r = n-1$ is the degrees of freedom (found by subtracting one from the number of observations) and $\alpha = {1-C \over 2}$ is the significance level.

A better way to a fully precise critical $t^*$ value is the statistical function implemented in spreadsheets (e.g. T.INV.2T function), scientific computing environments (e.g. SciPy stats.t.ppf), language libraries (e.g. C++ and boost::math::students_t).
Plug the found values into the appropriate equations:
$$\left({\bar x} - t^{*}{\frac {s} {\sqrt n}}, {\bar x} + t^{*}{\frac {s} {\sqrt n}}\right)$$
The final step is to interpret the answer. Since the found answer is an interval with an upper and lower bound it's appropriate to state that, based on the given data, the true mean of the population is between the lower bound and upper bound with the chosen confidence level.

The more the confidence intervals of two algorithms overlap, the more likely the algorithms are to perform the same (or we haven't sampled enough to discriminate between the two). If the 95% confidence intervals don't overlap, then the algorithm with the highest average performance performs significantly better.

In EA, the source distribution is essentially never normal and what said so far formally applies only if it's a normal distribution!

Indeed it still tells many things. The following table summarizes the performance of the t-intervals under four situations:

                             Normal curve | Not Normal curve
Small sample size (n < 30)      Good      |       Poor
Larger sample size (n ≥ 30)     Good      |       Fair

For more accurate answers non-parametric statistics are the way to go (see An Introduction to Statistics for EC Experimental Analysis by Mark Wineberg and Steffen Christensen for further details).


Context free grammar for L={ ((ab)^n)^m }

No need for a CFG: this language is regular!

$$L = (ab)^*$$

Any number of $ab$s is in the language: just set $n$ to 1, and $m$ to the number of repetitions. So all you need is a Kleene star.

If you really want a CFG, you can do it like this:

$$S \rightarrow SX \mid \varepsilon$$
$$X \rightarrow ab$$

This is the "standard" way of translating a Kleene star into a CFG.


What is the official name of a specific type of combination algorithm

You are probably looking for subsets of a set. If a set has $n$ elements, it has $2^n$ subsets when counting also the empty set (there is a clear correspondence to all bit strings of length $n$). So if in your case $n=26$, there are about 67 million subsets of variables to check which might be unfeasible.


Determining the complexity of calculating n-th root of an integer, and performing modulo arithmetic?

You can multiply two n-bit numbers trivially in $O(n^2)$, but using FFT (fast fourier transform) you can get the time down to $O (n \log n \log \log n)$. Lets call this time T(n).

For the modulo, you would calculate ab, then z = floor (ab / m), then r = ab - mz. If mz > ab then z was too large, so decrease z by 1 and subtract m from mz.

To find ab / r, you can use Newton iteration. There is a clever way to arrange this without any divisions, just multiplications. This is an iterative method with about log n iterations, but only the last iteration needs the full precision, so the total time is O (T(n)).

Things are even better if you want $z = a^{1/b}$ rounded to an integer, and to check if it is an integer. Again you use Newton iteration, but you only need a result with a bit over n / b bits precision. The result itself is a bit harder to calculate, requiring about log b multiplications, so the time to calculate this is $O (T (n / b) \log b)$. If you can't decide whether z is an integer or not due to precision, you can calculate $round(z)^b$ in T(n).


Show that NP is closed under concatenation

The easiest way to prove that NP is closed under concatenation is the following:

Assume that $L_1 , L_2 \in NP$. Thus, there are two nondeterministic deciders $M_1$ and $M_2$ such that $M_1$ decides $L_1$ in nondeterministic time $O(n^l)$ and $M_2$ decides $L_2$ in nondeterministic time $O(n^k)$.
Let $M$ a TM s.t.

  $M$ on input $w$:

  Split $w$ into $w_1 \in L_1$ and $w_2 \in L_2$ s.t. $w = w_1 w_2$;
  Run $M_1$ on $w_1$. If $M_1$ rejects then reject;
  Else run $M_2$ on $w_2$, if $M_2$ rejects then reject;
  Else accept.

This will use $O(n^{\max{l,k}})$ steps. So $M$ is a polytime nondeterministic decider for $L_1L_2$.


Proving an algorithm exists to find independent set from a graph given an oracle

If the problem has the property that the decision version can be converted to the search version, it is self reducibility. You can show that all NP-complete problems are self reducible. The idea is to build the instance with the prefix of the verifier for NP-complete problem, and solve it based on the decision version. This is kinda well-known several lines proof.

I am not aware of any other methods to show the fact you asked for.


Be sure to complete the first task before reading below.

Hint 1:

   What are the conditions necessary to use the Floyd-Warshall's algorithm? Does it match those of your exercise?

Hint 2:

   Well, I think you are ready to write the corresponding pseudo-code :-)


How is diagonalization a valid argument for the undecidability of the halting problem?

Try the following code instead:

def quote(s):
    return s.replace("'", "\\'")

def g():
    s = '''
def g():
    s = \'\'\'%s\'\'\'
    if halts(s %% quote(s)):
        while True:
            pass
'''
    if halts(s % quote(s)):
        while True:
            pass

If we add the following halting routine:

def halts(prog):
    print prog
    return False

then we can run g() and see that the input to halts is indeed the code for g():

>>> g()

def g():
    s = '''
def g():
    s = \'\'\'%s\'\'\'
    if halts(s %% quote(s)):
        while True:
            pass
'''
    if halts(s % quote(s)):
        while True:
            pass

A program that prints itself is called a quine. The corresponding result in computability theory is the recursion theorem, which ensures that (in a sense) a program can have access to its own source code.


Why half of the medians are greater than the median of medians?

Because $x$ is the median of all the $\lfloor n / 5 \rfloor$ medians obtained in Step 2, it is smaller than or equal to half of those medians by definition of median. See the figure below (from CLRS, the 3rd edition; Figure 9.1).

The problem with your example is that you are finding the median-of-medians $x$ recursively, however, without completing all the recursive steps. You should not stop at Step 3 (the "median of medians" step) in the recursion. Continue the remaining steps. In particular, in Step 4, you will use the "Partition" procedure to establish relationships between the medians obtained in Step 2 and this median-of-medians $x$.

For your added problem: You find it recursively. Why is the time complexity $O(n)$? Well, you can follow the analysis in CLRS.


L is not a regular language.
We can contradict by pumping lemma for regular languages.
Let assume L is regular, so there exists an integer $ k $ of pummping lemma.
$ w = a^kb $
$ w^R = ba^k $
$ ww^R = a^kbba^k \in L $
$ w' = a^{k-r}bba^k \notin L , r>0 $
Contradiction to $ w' \in L $.


Existence of d-regular subgraphs in a k-regular graph

Your conjecture is false. There are regular graphs with an even number of vertices yet without a 1-regular subgraph. See this question on Mathematics.

The complement of such a graph gives a counterexample to your claim that you can always add a perfect matching to increase the regularity (when the number of vertices is even).

In the bipartite case, however, your conjecture is true. Any $k$-regular bipartite graph can be decomposed into $k$ perfect matchings. This follows from Hall's theorem.


How to construct the objective function for genetic algorithm optimization?

tl;dr-  Objective functions are supposed to quantify how good a set of parameters is.  It doesn't matter how you got the parameters; for example, it doesn't matter that you're using genetic algorithms.  You just need to create some function that says how well the parameters work.

So you're designing a filter, which requires that the filter's parameters be optimized to fit its application, and you'd like to use genetic algorithms for the optimization?

You're correct that the filter's parameters should be used to construct the chromosomes in the genetic algorithm.  The genetic algorithm then does its work by:

Calculates how well its chromosome (combination of parameters) performs.
Discards the chromosomes that didn't perform well.
Modifies (mutates) the parameter sets (chromosomes) that did perform well.
Goes back to Step (1), looping until either it finds a parameter set that's good enough or it gives up (fails to converge).

However, how should the algorithm assess how "good" the parameter sets are?  That's what the objective function's for.  The objective function takes the chromosome as input, then produces a result that quantifies how good that chromosome is.

Since chromosomes are sets of parameters, they're often represented as a vector (array).  For example, if your filter's, say,$$
f\left(x\right)=ax^2+bx+c,
$$then the chromosome's the array of the parameters $\left\{a,b,c\right\}$.

The question statement doesn't specify your filter or exactly what sort of problem you're working on.  However, since you want to use sum-squared error, that implies that your filter produces an output with quantifiable error.

So, presumably, your objective function would be$$
\text{error}=\sum_{{\forall}\text{data}~i}{\left(f_{\text{measured}}\left(x_i\right)-f_{\text{model}}\left(x_i\right)\right)}^2,
$$or something like that.  Some folks prefer to use the root-mean-square, i.e.$$
\text{error}=\sqrt{\sum_{{\forall}\text{data}~i}{\left(f_{\text{measured}}\left(x_i\right)-f_{\text{model}}\left(x_i\right)\right)}^2},
$$but that shouldn't matter here.

In general, I'd suggest seeing genetic algorithms as stepping functions.  Their core duty is to produce new guesses during an optimization process.  Objective functions live elsewhere in the optimization process's structure; this is, objective functions don't care how you're stepping - whether you're using genetic algorithms, Newton's method, Simplex, gradient descent, bisection, random guessing, or whatever else - it doesn't matter to the objective function.  All the objective function has to do is say how good a guess is, regardless of how that guess was generated.


Are the implications of the diagonalization language different from those of the halting problem?

I think that "limits of computation" is a good entry point. Usually, computer scientists learn how to solve problems in an logical and algorithmic way. The whole concept of undecidability is to show that there are problems which cannot be solved in this way, which may sounds surprising but also exciting, that there is an actual limit to what is possible with computers (even with infinite memory).

You actually do not need the diagonalization language to show that there are undecidable problems as this follows already from a combinatorical argument:
You can enumerate the set of all Turing machines (sometimes called Gödelization). Thus, you have only countable many decidable languages. But the set $2^{\{0, 1\}^\ast}$, i.e. the set of all languages over $\{0, 1\}$, is uncountable, so there have to be undecidable languages.

The diagonalization language (I assume $D = \{\langle M \rangle \mid M \text{ halts on } \langle M \rangle\}$ is by all means very constructed but the proof that this language is undecidable is a good stating point because the proof via diagonalization is easy and the usual variations of the halting problems are not really far away. The next steps are probably Turing reductions from this language to some of these variations.


In double hashing, we have (for a specific $k$) the series $h(k) + nh'(k) \mod m$
Since we have that $gcd(h'(k), m) = 1$ (they are relatively prime), then from Bézout's identity there exists two integers a,b such that $ah'(k) + bm = 1$. since $h'(k)$ is not 0, we can conclude that b is not 0 and thus also a is not 0.
We have $ah'(k) = 1 \mod m$, which means that a is the inverse of h'(k) in modulo m.
Now, let $0 \leq i \leq m$ be an integer. by choosing $n = ia$, we have $( h(k) + nh'(k) ) \mod m = ( h(k) + iah'(k) ) \mod m = ( h(k) + i ) \mod m$.
This concludes the proof (think why).
I hope i managed to help!


What is the requirement for bubble sort to complete in 1 pass?

I'm assuming that a pass of bubble sort on the array $A[1],\ldots,A[n]$ proceeds as follows:

If $A[1] > A[2]$ then swap $A[1]$ and $A[2]$.
If $A[2] > A[3]$ then swap $A[2]$ and $A[3]$.
...
If $A[n-1] > A[n]$ then swap $A[n-1]$ and $A[n]$.

Bubble sort halts after a pass in which no swaps were made.
As is evident, if bubble sort halts after one pass, then the array must have been sorted.
When does bubble sort halt after two passes? If after the first pass, the array is sorted. In this case, if we know which swaps were made, then we can recover the input permutation. Furthermore, different sets of swaps correspond to different initial permutations. It follows that there are $2^{n-1}-1$ permutations that cause bubble sort to halt after exactly two passes. Together with the identity permutation, it follows that there are $2^{n-1}$ permutations that cause bubble sort to halt within two passes.
How do these permutations look like? Suppose that the first $k$ swaps are made, and then the following swap isn't made. Since the first $k$ swaps are made but the following one isn't made, at the end of the pass the first $k+1$ elements of the array will be $A[2],\ldots,A[k+1],A[1]$, which must correspond to the permutation $1,\ldots,k+1$. Hence the original permutation started $k+1,1,\ldots,k$.
From here, it's not too difficult to describe all $2^{n-1}$ permutations. Starting with the identity permutation, partition it in an arbitrary way, and rotate each part one step to the right. For example, when $n = 3$ we get:

$1|2|3 \to 1|2|3$.
$1|23 \to 1|32$.
$12|3 \to 21|3$.
$123 \to 312$.

Each division in the partition corresponds to a step in the pass during which there was no swap.

Here is another way of describing these permutations: they avoid the patterns $231$ and $321$. This means that for any $i<j<k$, it cannot be that $A[k] < A[i],A[j]$. To prove this, we show that any permutation above satisfies this constraint, and then prove the converse.
Consider any of the $2^{n-1}$ permutations above, and let $i<j<k$. Since each element in a part is smaller than each element in a subsequent part, $A[k] < A[i]$ is only possible if $i,j,k$ are all in the same part. Moreover, $A[k] < A[j]$ for indices $j<k$ in the same part only if $j$ is the first element in the part, which is impossible since $j>i$.
Suppose now that we are given a $(231,321)$-avoiding permutation. Let $i$ be any index such that $A[i] > i$. All elements in $i,\ldots,A[i]-1$ must appear before all elements in $A[i]+1,\ldots,n$, since otherwise there will be a copy of $231$. Furthermore, the former must appear in increasing order, since otherwise there will be a copy of $321$. Therefore the part of the array that follows $A[i]$ is $A[i],i,i+1,\ldots,A[i]-1$.
Imagine now scanning the array in the order $A[1],A[2],\ldots$. The first time that $A[i] \neq i$, necessarily $A[i] > i$ (since we've already seen all smaller elements), and so the following elements are $i,\ldots,A[i]-1$. When we continue the scan, again the first time that $A[i] \neq i$ we must have $A[i] > i$ (since we've already seen all smaller elements), and so on. Therefore the array is of the form above.


There is no simple answer for how to choose parameters.  This is a heuristic, so there are no guarantees.

Here are a few strategies that are widely used:

Random search: Try many different parameters.  In each trial, you randomly choose all parameters, solve the optimization problem using those parameters, and then remember the solution.  Take the best solution found.
Grid search: Systematically search over the space of possible parameters.  For instance, if there are two parameters $\alpha$ and $\beta$, you might let $\alpha$ range over values $0.1$, $1$, $10$, and $100$, and let $\beta range over a similar set, and try all combinations; then take the best solution found.
Try smaller problems: Construct a smaller problem (e.g., synthetically).  Find the best parameter settings for it (by applying one of the prior two methods).  Then, use those parameter settings on your larger problem, and hope they'll be good for your larger problem, too.


Is finding a single digit of a computation is as hard as finding the computation?

For some functions $f$ you might be correct. For example, we can arrange that $f(|n|) \neq n$ for all $n$ (by controlling the length of $f(x)$) while keeping $f$ arbitrarily difficult, and so $L_1$ reduces to $L_2$ trivially.

Here is a function $f$ satisfying your constraint, for which $L_1$ does not polynomially reduce to $L_2$. The construction uses diagonalization. (There is some ambiguity in your notation, but the proof can be adapted however you resolve the ambiguities.)

Let $L$ be some computable language which requires time $2^{2^{2^n}}$ (such languages exist due to the time hierarchy theorem). We define the function $f$ as follows: $f(\epsilon) = f(0) = 0$, and $f(0x)$ is the indicator of $x \in L$. We define the rest of the function $f$ by giving an algorithm which eventually defines all remaining values.

Let $\phi_i$ be an enumeration of all functions computable in polynomial time. We can construct such an enumeration using timed Turing machines.  We go over the functions $\phi_i$ in order. When it's time to process $\phi_i$, let $n \geq 1$ be the smallest value on which $f$ is undefined. Let $m = \phi_i(0^n,2)$. We consider several different cases:

Case 1: $f(|m|)$ is already defined. If the second digit of $f(|m|)$ is $0$, define $f(n) = 1^n$, otherwise define $f(n) = 0^n$.
Case 2: $f(|m|)$ is not defined, and $|m| \neq n$. Define $f(|m|)$ arbitrarily, and proceed as in case 1.
Case 3: $|m| = n$. Set $f(n) = 10$.

In all cases, we ensure that $f(n) \neq 0^n$ iff the first digit of $0^n$ equals the second digit of $f(|m|)$, showing that $\phi_i$ is not a polytime reduction from $L_1$ to $L_2$.


Does the order matter in the adjacency matrix?

Let $f$ be an isomorphism from graph $G$ to graph $G'$ which takes vertex $v_i$ to vertex $v_i'$.  Let $A$ and $A'$ be the adjacency matrix of $G$ and $G'$, respectively.  If the rows and columns of $A$ are in the order $v_1,\ldots,v_n$, and the rows and columns of $A'$ follow the same order $v_1', \ldots, v_n'$, then it can be seen that $A=A'$.

If $f$ is an isomorphism from $G$ to itself, then $f$ is called an automorphism of $G$.  Thus, $f$ is a permutation of $V(G)$ which maps edges to edges and nonedges to nonedges.  If we permute the rows of the adjacency matrix $A$ by $f$, and if we apply the same permutation to the columns of $A$, we get back the same matrix $A$. Equivalently, a permutation $f$ of $V(G)$ is an automorphism of $G$ if and only if the permutation matrix $P$ corresponding to $f$ satisfies the equation $P^{-1}AP=A$.  Recall that premultiplying a matrix $A$ effects row operations/permutations and postmultiplication effects column permutations.

So, graphs with the same structure (i.e. isomorphic graphs) have the same adjacency matrix (up to a permutation of the rows and columns - here, the same permutation must be applied to both the rows and the columns).  The graph invariants which we study are the same for isomorphic graphs and so the ordering of vertices you choose for the adjacency matrix shouldn't matter.


There appears to be some considerable confusion in this community regarding this question. I'll give a detailed answer in the hope of clearing up the water and illuminating the relationship between computability and NP-hardness.
First, I believe that being clear and explicit about the various definitions involved will resolve a lot of the confusion.

A string is a finite sequence of characters from some fixed finite alphabet.
A decision problem is a set of strings. (This set is typically infinite.) Think of the decision problem as testing strings for some property: the strings with the property are in the set, and the strings without the property are not.
Assume we have two decision problems, $A$ and $B$. Say $A$ is polynomial-time reducible to $B$ if there is some polynomial $p(x)$ and algorithm some algorithm $M$ such that, for all strings $s$,

If you provide $M$ with input $s$, $M$ halts in fewer than $p(|s|)$ steps (where $|s|$ is the length of the string $s$) and outputs a string $M(s)$.
$s$ is in $A$ if and only if $M(s)$ is in $B$.

A decision problem $B$ is NP-hard if, for every NP decision problem $A$, $A$ is polynomial-time reducible to $B$.
A decision problem is computable if there is an algorithm $M$, that, for all strings $s$,

If you provide $M$ with input $s$, $M$ halts and outputs either "yes" or "no".
The output is "yes" if $s$ is in $A$ and "no" otherwise.

With the above definitions, we can immediately clarify what I think might be the root confusion in your question: nothing in the definitions of decision problem, reductions, or NP-hardness requires the decision problems to be computable. The definitions make perfect sense thinking of decisions problems as arbitrary sets of strings, and these sets can be very nasty indeed.

That leaves two questions on the table:

The definitions leave open the possibility that non-computable functions might be NP-hard. Are there actually non-computable, NP-hard functions?
There is an intuition that saying a problem is NP-hard is saying that it is hard to solve. Saying that it is non-computable is like saying it's "really hard" to solve. So, are all non-computable problems NP-hard?

Question 1 is easier to answer. There are two particularly important ways to find non-computable decision problems that are NP-hard. The first is the halting problem: the halting problem, $H$, has the property that every computable decision problem is polynomial-time reducible to $H$. Since NP problems are computable, every NP problem is polynomial-time reducible to $H$, so $H$ is NP-hard.
The other important way to build a non-computable, NP-hard problem is to observe that we can combine any known NP-hard problem with any known non-computable problem. Let $A$ be NP-hard and $B$ be non-computable. Form the decision problem $A \oplus B$ as follows: $A \oplus B$ contains those strings of the form "0, followed by a string in $A$" and those of the form "1, followed by a string in $B$". $A \oplus B$ is NP-hard because we can turn any reduction (of any problem) to $A$ into a reduction to $A \oplus B$: just tweak the algorithm to output an extra "0" at the front of its output string. $A \oplus B$ is non-computable, since computing $A \oplus B$ requires deciding which strings that start with "1" are in the set; this is impossible, since $B$ is non-computable.

Question 2 is considerably tricker, but in fact there are non-computable decision problems that are not NP-hard (assuming P $\neq$ NP). Yuval's fine answer constructs such a decision problem explicitly. (For any computability theorists in the room, any "Cohen $\Pi^0_1$-generic" will do the trick, as well.) I'll break down why the intuition that "NP-hard problems are hard, non-computable problems are harder" is wrong.
NP-hardness and non-computability both say that a problem is "hard" in a very general sense, but they are very different and shouldn't be lumped together as the same kind of phenomenon. Specifically, NP-hardness is a "positive" property: an NP-hard problem $A$ is hard in the sense that, given access to a cheat sheet for $A$, you can solve a hard class of problems. On the other hand, non-computability is a "negative" property: a non-computable problem $A$ hard in the sense that you cannot solve $A$ with a given class of resources.
("Forcing," by the way, is the technique used to produce the "Cohen $\Pi^0_1$ generic" that I mentioned. To be very very vague, forcing is a general way to produce things that are "generic" in that they have no positive properties and every negative property. That's why forcing can directly produce a problem that's neither computable nor NP-hard.)


You haven't defined your language, but presumably
$$
L \cap [^*0+0](+0])^* = \{ [^n[0+0](+0])^n : n \geq 0 \},
$$
where I replaced parentheses with square brackets. The latter language is essentially $\{a^nb^n : n \ge 0 \}$ in disguise, and so isn't regular. It follows that $L$ isn't regular as well.


Store and sort a large number of 64-bit integers

You're not going to get much in the way of programming tips here, this is a site for computer science, not programming.

For the sorting algorithm, you probably want to use Radix Sort, which will run in time $O(k n)$, for you $k = 64$ and $n = 500 000 000$.

For the storing of these numbers, you might want to look into compressed data structures. However, these are necessarily going to bring some overhead. You're looking at approximately 4GB of memory, which is reasonable on many modern machines. As you will learn in computer science, there is often a tradeoff between time and space. Here, you must choose between a fast data structure and a space-efficient data structure.

EDIT: I change the time complexity to $O(kn)$, I'd mistyped and originally written $O(k\log n)$. Sadly, it's impossible to sort a list without actually looking at the entire contents of the list.


Algorithm for nearest edge detection with respect to a point (in all directions)

I would suggest you use a sweep line algorithm, sweeping a line that emanates from the origin and rotating around it.  Think of a lighthouse placed at the origin, with a beam of light that rotates around in a circle, and find the closest point illuminated by that beam of light.

In more detail: Convert the points to polar coordinates $(r,\theta)$ and sort them by increasing angle $\theta$.  Let $S$ denote the set of resulting points. Then for each angle $\theta$ find the point closest to the origin out of all points whose angle is in the range $[\theta-\epsilon,\theta+\epsilon]$, and use this as the location of the perimeter at that angle.  In particular, let $f(\theta) = \min \{r : (r,\theta') \in S, |\theta-\theta'| \le \epsilon\}$; then $f$ defines a curved line/path. You can apply some smoothing to it, and then use that as your red line.  If there is no point with angle in the range $[\theta-\epsilon,\theta+\epsilon]$, then there is no red line there; you have a break in the line.

You could of course apply a standard clustering algorithm first, and then do this separately on each cluster, removing clusters that are "hidden" (further away than another cluster).  From your image it looks like the clustering problem should be easy and you shouldn't have a difficult time finding a clustering algorithm that does a good job of separating the points into clusters.  However, I'm not sure that's even necessary.


How many bits are needed? Advantages/disatvantages of this configuration?

for each instruction, we were trusting one particular component of the kernel to handle it

This seems to represent a misunderstanding of how code is executed.  That's not how CPUs work.  Instructions are executed by the CPU -- not handled by the kernel.  So, the question seems to be based on a faulty premise.

(OK, there are sometimes occasional exceptions to this in real-world architectures -- e.g., in old x86 platforms, some floating-point instructions might be emulated by the kernel when running on a CPU that didn't have floating-point support -- but that's a detail.  Treat what I've described above as the basic rule.)


Proof of Space Hierarchy Theorem incompatible with Linear Speed Up Theorem for time

The Wikipedia proof is bogus.

As you have proven, the description for $L$ is incomplete. It should read:
$$
 L =  \{ (\langle M \rangle, 10^k) : M \mbox{ does not accept } x = (\langle M \rangle, 10^k) \mbox{ using space } \le f(|x|)
 \; \textbf{and time} \; \le 2^{f(|x|)} \}
$$

This corrects the proof because now $M$ (or $M'$) can still accept $x = (\langle M \rangle, 10^k)$ and take space $\le f(|x|)$. Actually, $(\langle M \rangle, 10^k) \in L$ has a quite reasonable explanation in that $M$ attempts to simulate $M$, which (as a subroutine) attempts to simulate $M$ again, and so forth and so on, until eventually $2^{f(|x|)}$ steps elapse and the whole procedure is interrupted. Hence, $M$ does not accept $x$ using space $\le f(|x|)$ and time $\le 2^{f(|x|)}$, although it does accept it taking space $\le f(|x|)$ (well, perhaps actually $O(f(|x|))$) and time $> 2^{f(|x|)}$.

As a matter of fact, the purported algorithm for $L$ in the article explicitly states it runs its simulation with a $2^{f(|x|)}$ stopwatch. This is precisely the detail that is missing from the definition of $L$.


One major overhead of virtual memory is that virtual pages that are being used in the current computation have to
be loaded in physical memory, which usually means also transferring
out another page back on disk. Since this is costly, you want to avoid
doing it too often. Hence an important concept is the locality of
programs: though a program may have to use considereable space, you
try to organize the program so that only a much smaller part of memory
is used at any time, a smaller part that evolves only slowly.

THis concerns the code being executed, but also the data used. And
data is often orders of magnitude larger than the code. So, a program
handling large amounts of data will often be organized so as to
improve the locality of the data organisation in memory (but this depends also on what the code does with the data). As a
consequence, too naive a use of classical textbook algorithms may result in
very slow programs, because of too many page faults.

I guess there are tools to analyze the locality of programs, or to
optimize them to improve it. A specific example is the design of
garbage collectors, which have developed various techniques to improve
data locality by reorganizing the information, and which are of course
design to explore the memory in a very local way, for example by
looking in priority at pages the main program has already loaded in
physical memory.

Programs with bad locality spend too much time loading pages compared
to actual computing time. This is called thrashing.


A problem with the greedy approach to finding a maximal matching

You're correct, you're not missing anything -- except that the algorithm is not wrong.  The task is to choose a maximal matching, not a maximum matching.  There may be many possible maximal matchings, many of which are not maximum matchings.  It's the difference between a local optimum vs a global optimum.


Karp reduction from optimization problems to decision problems

Thanks to comments by Yuval Filmus, I understand that my question does not make sense as Karp reductions are defined for decision problems. Since Cook reductions allow more freeness, it makes sense to talk about a Cook reduction from a decision problem to an optimization problem, but this is not true for Karp reduction.


Why is $\emptyset L = L\emptyset = \emptyset$ correct?

$L_1L_2$ means the set of all strings you can make by choosing one from $L_1$ and one from $L_2$ and concatenating the two strings.  So how many ways can you choose a string from the empty set of strings and one from $L$?  None at all! So there are no such concatenations and $\emptyset L = \emptyset$.

The key point is that $\emptyset$ is the language that contains no strings at all. The empty string is a string (it's the string with no letters at all) so the empty string is not a member of the empty language: $\{\epsilon\}\neq\emptyset$.


Reduction of Hamiltonian cycle to Hamiltonian cycle & clique

For NP completeness, two things must be demonstrated.

That a solution to the problem can be verified in polynomial time (usually easy).
That the input to another NP Complete problem can be formatted as an input to the potentially NP complete problem (also that a solution from the potential NP Complete problem can be turned into a solution to the NP complete problem) all in polynomial time.

It looks like you are trying to go the wrong direction with your question. You are asking about inserting a Clique into a graph, but you only need to concern yourself with a graph that would be sent to a HP solver and modify the inputs so they are appropriate for a HP+Clique solver.  The HP part of the candidate problem doesn't require any modification - it just takes an undirected graph G(V,E).  A clique takes an undirected graph G(V,E) and a goal, k.  So you need to define a k that is in $G_{HP}$.  what if you set k=1?.  This way, the only graphs that your solver will fail to find a solution for are those that don't have a HP since every node is a clique with itself. This takes O(1) to define k=1.

Now, you just need to modify the output of the HP+Clique so it is the same as the output for the HP problem.  e.g. If the candidate problem produces a solution, you would only return the path part and drop the clique part.   If a solution is not found, you return NO.


Difference between Quick sort, Merge sort and Heap sort

Well. If you considered only the asymptotic time complexity $\mathcal{O}(\mbox{N log N})$, then there would be practically no difference between Quick and Heap sort. So both algorithms runtime is:

$\mbox{constant} \cdot \mbox{N log N}$

but, the constant may differ significantly and this is what makes a big difference. So, in practice, Quick sort is much more effective and requires much less comparisons than Heap sort (see e.g. here) - so the constant in the above expression for Quick sort is much smaller. That's why Quick sort is the one most used for general purpose..


TSP decision problem vs TSP optimization problem

Only decision problems can be NP-hard or NP-complete; these are problems for which the answer is either Yes or No.

Optimization problems have an optimal solution as an answer. The associated decision problem is, given an instance and a value, whether the the value of an optimal solution is as good or better than the given value.

When we say that an optimization problem is NP-hard, we mean that its associated decision problem is NP-hard; it is an abuse of terms. We could also say that an optimization problem is NP-complete if its associated decision problem is NP-complete.

The TSP optimization problem is, given a graph, find a TSP tour of shortest length. The associated decision problem is, given a graph and a value $k$, decide whether the shortest TSP tour has length at most $k$. These are different than the problems that you describe.

Sometimes we are interested in a weaker version of the optimization problem, namely, given an instance, find the value of an optimal solution. This is the perspective usually considered in the field of hardness of approximation, in which the goal is to show that it is NP-hard to even approximate the optimal value.


Using MyHill Nerode theorem to prove a language is non-regular

The classes are defined over words of the alphabet such that two words $x, y$ are equivalent if for any word $z$ we have $xz \in L$ if and only if $yz \in L$.

Consider for each $n\in \mathbb{N}$ the class $C_n$ defined as $$C_n = \{x \in S : \#_b(x) \geq 1 \text{ and } \#_a(x) -\#_b(x) = n\}.$$

Note that for each word in this class we can append exactly the strings $b^i$ where $i \leq n$. So for two different values $n_1$ and $n_2$ where $n_1 < n_2$ the word $b^{n_2}$ is a valid suffix to words in $C_{n_2}$ but not in $C_{n_1}$. Hence we have infinitely many such classes. Words ending with the letter $a$ accept additionally more $a$s and hence do not even belong to these classes and we have even more classes. Since we have infinitely many classes, the language is not regular.


Minimizing inversions in an array with a single swap

Let's calculate the difference in number of inversions given that you swap $a_i$ and $a_j$. We can assume that $i < j$. There are three kinds of pairs of indices whose status (being inversions or not) could change as a result of the swap: $(i,j)$ and, for $i < k < j$, $(i,k)$ and $(k,j)$. We can distinguish two cases: $a_i < a_j$ and $a_i > a_j$.

If $a_i < a_j$ then the pair $(i,j)$ becomes an inversion, and for every $i < k < j$, there are three possible cases:

$a_k < a_i < a_j$: number of inversions stays the same.
$a_i < a_j < a_k$: number of inversions stays the same.
$a_i < a_k < a_j$: number of inversions increases by 2.

This is clearly not a good idea if you can avoid it. If you must (when the permutation is monotone increasing), it's best to switch a pair $a_i,a_{i+1}$.

In contrast, if $a_j < a_i$ then the number of inversions decreases by one plus twice the number of indices $i < k < j$ such that $a_j < a_k < a_i$. As a consequence, if the permutation is not monotone increasing, your goal is to choose a pair $(i,j)$ such that $a_j < a_i$ and the number of indices $i < k < j$ satisfying $a_j < a_k < a_i$ is maximal. You take it from here.


Reason for global update steps in the push-relabel algorithm

Global relabeling is not required; it's an optimization. In the push-relabel paper, Goldberg and Tarjan describe a parallel version not amenable to such an update. The kind of performance problem global relabeling addresses is when two nodes u and v with surplus and residual arcs to one another become disconnected from the sink in the residual graph. The local relabeling rule can only increase u's label to one more than v's, and vice versa, so surplus is pushed back and forth and the labels slowly count up until the maximum of n is reached. Now imagine if this happens to a dense subgraph with many nodes.

By alternating m steps of push/relabel with global updates, the running time at worst goes up by a constant factor but in practice typically goes down, by a lot. The best implementations of push-relabel use gap relabeling as well as global relabeling. Both heuristics are described, with some experiments, by Cherkassky and Goldberg.


Given two data feeds, find out if they capture the same information

The problem of finding the relationship between two scenes shot from two different angles is known as the correspondence problem and there is a lot of literature on how to approach it; I suggest you start by reviewing the research literature on methods for solving this.  In particular, I'd suggest that if you can consistently find a correspondence between the two images, you might conclude that they are from the same feed; and if you can't, you might conclude that they aren't.


Your algorithm, which requires $\lceil \log_2 n \rceil$ weighings, is in fact not optimal. This paper proposes an algorithm which uses $\lceil \log_3 n \rceil$ weighings, which is optimal by the argument outlined by Tom van der Zanden. Let's assume for simplicity that $n$ is a power of 3, leaving the general case as an exercise. Suppose we are given $3^k$ objects, which we divide into three groups $X,Y,Z$ of size $3^{k-1}$. We weight $X$ against $Y$. If $X > Y$, we recurse with $X$; if $Y > X$, we recurse with $Y$; if $X = Y$, we recurse with $Z$. After $k$ such steps, we will have zeroed in on a single object.

For the lower bound, suppose that we only do $k$ weighings. There are $3^k$ possible outcomes of this weighings – each one can be either "left side heavier", "right side heavier", or "both have the same weight" – and each of them causes the algorithm to output a definite answer. Since any of the $n$ objects could be the heavier one, we must have $3^k \geq n$. This argument will make more sense after you review the $\Omega(n\log n)$ comparison lower bound for sorting.


Is this "superset existence" problem NP-complete?

The problem is NP complete.
It is trivially in $NP$ (a certificate is the collection of the $y$ selected subsets of $S$), and it is $NP$-hard since it is the decision version of the Maximum Coverage Problem.


Language of lists of words, not all of which are different, is not context-free

If $L$ were context-free then so would $L' = d(L \cap (0+1)^*\#(0+1)^*)$ be, where $d$ is the homomorphism that deletes $\#$. However, $L'$ is the language of squares (words of the form $w^2$), which is well-known not to be context-free.
If for some reason you have to prove that $L$ is not context-free directly using the pumping lemma, this suggests looking at the proof that $L'$ is not context-free and trying to adapt it.


Repeated String Match: need help to understand the maximum number of repeats needed to be looked at

Here is a proof by example. We want to check whether $B$ is a substring of some power of $A$. Instead, let us check whether $B$ is a substring of $A^\omega$, that is, $A$ repeated infinitely many times. It suffices to test the following starting positions (why?):

abcdabcdabcdabcd...
cdabcdab

abcdabcdabcdabcd...
 cdabcdab

abcdabcdabcdabcd...
  cdabcdab

abcdabcdabcdabcd...
   cdabcdab

In order to perform these checks, we don't need to consider $A^\omega$; it suffices to consider the smallest power of $A$ which covers the very last case. This power is $q+1$ (or possibly just $q$).


Corresponding noun for "side-effect-free"?

A good rule of thumb for grammatical questions is, if it's so complicated that you need to ask, it's better to just rephrase the sentence.  For example, "Side-effect-freedom of the function guarantees X" is more simply and elegantly written, "Because the function is side-effect free, X is guaranteed" or even, "The function has no side-effects, so X is guaranteed."

Having said that, keywords for articles are expected to be noun phrases so that would be a place to use "side-effect freedom".

(By the way, "non-side-effective" is an adjective.)


Time complexity, Big-O for this function?

It runs in time $O(n)$. Remember that a function only returns once.  In each call to f, the for loop is immediately terminated at i=0 by the return statement, so the function body is equivalent to

if n < 100000
    return 0;
else
    return f(n-1);

However, your answer of $O((n!)^2)$ is not wrong: $(n!)^2$ is a huge overestimate of the running time, but big-$O$ essentially means "at most this much."