Problem with the mapping reduction from $A_{TM}$ to $HALT_{TM}$

Your conception of a reduction is incorrect. The reduction takes an instance $\langle M, w \rangle$ of $A_{TM}$ and returns an instance $F(\langle M,w \rangle)$ of $HALT_{TM}$ such that $\langle M,w \rangle \in A_{TM}$ iff $F(\langle M,w \rangle) \in HALT_{TM}$.

Second, $M'$ is a Turing machine that accepts a single input $x$. The pair $\langle M',w \rangle$ belongs to $HALT_{TM}$ if $M'$ halts when running on the input $w$. Hence when analyzing whether $\langle M',w \rangle \in HALT_{TM}$ or not, the relevant value of $x$ is $w$.

Here is another way to think of the proof. Given a Turing machine $M$, we construct another Turing machine $M'$ such that $M$ accepts $w$ iff $M'$ halts on $w$.

When describing $M'$, we use $x$ to denote its input. There is no definite value of $x$ like your post seems to assume — it stands for the input to $M'$. For a similar example, consider the function $f(x) = x^2$. What is the value of $x$? It has no definite value, being just a place holder. If we plug in $w$ for $x$ then we get $f(w) = w^2$.


Can someone explain this conclusion for Finite State Machines?

In both cases, the number of states is the LCM. This is because a number is divisible by $m$ and $n$ if, and only if, it is divisible by $\mathrm{lcm}(m,n)$ and, for any positive integer $d$, you can check that the input length is divisible by $d$ by having states $\{0, \dots, d-1\}$ such that the automaton is in state $i$ when the number of characters read is congruent to $i$, modulo $d$.


Why top down merge sort is popular for learning, while most libraries use bottom up?

Because top-down mergesort is conceptually simpler, and fits right into the curriculum of new computer scientists that learn about recursion. A small constant performance difference between top-down and bottom-up is irrelevant for its educational value.


Superdense coding - What are the individual qubits A and B?

Is it just that A and B cannot be written using the standard basis?

Correct.
Entangled qubits are not separable.
You can't factor them into a form like $(a_0 |0\rangle + a_1 |1\rangle) \otimes (b_0 |0\rangle + b_1 |1\rangle)$.

You can get a per-qubit density matrix by tracing out the other qubit, but the resulting density matrix doesn't capture the correlation between the two qubits. It just looks like a maximally mixed state.


Game of Nim (Find winning states in large range)

Let $a=a_{n-1} \cdots a_0$ and $b=b_{n-1} \cdots b_0$ be two positive integers with given binary expansion. Since $z+w = 2(z \land w) + (z \oplus w)$, we have
$$
a + b = a \oplus b + 2(a \land b),
$$
where $a \oplus b$ and $a \land b$ are bitwise XOR and AND. In particular, $a + b = a \oplus b$ iff $a \land b = 0$.

Consider now the equation $x \oplus 2x \oplus 3x = 0$. We can rewrite it as $x \oplus 2x = 3x = x + 2x$. Above we have seen that this is equivalent to $x \land 2x = 0$. If $x = x_{n-1} \ldots x_0$ then
$$ x \land 2x = 0 (x_{n-1} \land x_{n-2}) \ldots (x_1 \land x_0) 0. $$
Thus $x \oplus 2x \oplus 3x = 0$ if the binary expansion of $x$ doesn't contain two adjacent 1s.

It remains to count how many binary strings of length $n$ (in your case, $n = 61$) satisfy this condition. It is a standard exercise to show that the answer is the Fibonacci number $F_{n+2}$.


Are empty-set languages recursively enumerable?

The empty language is recursive. The TM accepting this language just returns $0$/REJECT on any input. Similarly, the language $\Sigma^*$ is also recursive. Just return $1$/ACCEPT on any input.

Basically, it does not matter how a language is defined. What makes them recursive/RE is the fact that we can effectively decide its membership. For
a recursive language $L$ there is a TM that always accepts $x$ if $x \in L$ and rejects $x$ if $x \notin L$. For a recursively enumerable language $L$  there is a TM that always accepts $x$ if $x \in L$.


What's the difference between a reorder buffer and an instruction window?

Correct.  The instruction window is not a hardware structure.  It is the set of instructions that is contained in the reorder buffer at any moment in time.  Looked at another way: the reorder buffer is a container (like a drinking cup is a container) and the instruction window is the thing the reorder buffer contains (like milk, juice or water is the thing contained in a drinking cup.)


Drawing an implication graph for 2-SAT clauses

{¬uv¬x} : I have u-->¬x and ¬x-->¬u

LMFTFY:

$$(\neg u \vee \neg x) = \left[(u \implies \neg x) \wedge (x\implies \neg u)\right]$$

  {¬wvx} : I have w-->x and ¬w-->¬x

LMFTFY:

$$(\neg w \vee x) = \left[(w \implies x) \wedge (\neg x\implies \neg w)\right]$$

From this you get the following graph:

graphviz source

And the strongly connected components (there is only one):

graphviz source

And we get $\left\{u,\neg u,w,\neg w, x,\neg x,y,z,\neg z\right\}$, obviously a contradiction (the elements of this set implies each-other).

  I would argue that these literals are not satisfiable because of the infinite loops you can have from ¬w ¬x ¬y ¬z ¬w and w x y z w. Is this a sufficient enough explanation?

It isn't the "infinite" loops that make it unsatisfiable. "infinite loops" or cycles, make strongly connected components; and a 2sat formula is satisfiable iff (if and only if) there are no contradicting terms in any of its strongly connected components. In this graph there are clearly contradicting terms in the one large strongly connected component, as I demonstrated above, therefore it is unsatisfiable.


For most of this answer, I discuss the decision version of the problem, in which an instance having at most one solution is given (the "promise"), and you have to decide whether it has any solutions or none.

You can reduce PARTITION to your problem (exercise). (PARTITION is the problem of determining whether a set of integers can be partitioned into two parts with equal sum.) Admittedly, this doesn't necessarily satisfy the condition that the solution be unique.

With some more work, you can (directly) reduce SAT to (the decision version of) your problem, and perhaps that can be done in such a way so that if the SAT instance has a unique solution, then so does the resulting instance of your problem. In that case, we get that the decision version is not solvable in polytime unless NP=RP, which is considered unlikely.

Note that if the decision version (more accurately, the promise version) of the problem is not solvable in polytime, then no algorithm can solve all YES instances in polytime: if it did, you could run it up to its allotted running time, and check the solution (if the algorithm stopped in time).


Is NPSPACE also closed under polynomial-time reduction and under log-space reduction?

Savitch's theorem implies that NPSPACE is equal to PSPACE, and so it is closed under polynomial time reductions.


How do I show that $a^n w b^n$ is not regular?

It's reasonable to conjecture that $L=\{a^nwb^n\mid w\in (a+b)^*, |w|=m\ge n>0\}$ is not regular, since it looks a lot like the $a^nb^n$ language, which we know isn't regular. However, $L$ is indeed regular and is in fact the language denoted by the regular expression
$$
a(a+b)(a+b)^*b,
$$
assuming that $0 \notin \mathbb{N}$ (otherwise the language is just $\Sigma^*$).
The key idea here is that $L$ is defined to be "all strings over $\Sigma=\{a, b\}$ which can be expressed as $a^nwb^n$ where $|w|\ge n>0$". This means that strings in $L$ might not obviously be of the right form, but can be expressed in other ways that are of the right form.

We'll show that $L$ is the same language as $M=\{axb\mid x\in (a+b)^*, |x|\ge 1\}$. Here's a proof that $L=M$:

($M\subseteq L$): Let $s\in M$, then $s=axb=a^1xb^1$ with $|x|\ge 1=n>0$, so $s\in L$.
($L\subseteq M$): Let $s\in L$, then $s=a^nwb^n$ with $|w|=m\ge n > 0$. We also have
$$
s=a^{n-i}(a^iwb^i)b^{n-i}=a^{n-i}xb^{n-i}\qquad\text{with $x=a^iwb^i$}
$$
for any $0\le i \le n-1$. If we pick $i=n-1$ we'll have $s=a^1(a^{n-1}wb^{n-1})b^1$ and we'll have $|x|=2(n-1)+m\ge 2n-2+n=3n-2\ge 1$ and so $s\in M$, completing the proof.


Finding the nearest neighbour of an existing 2d point in a set of points within $\mathcal{O}(\log{}n)$ time

If you have a voronoi diagram you have neighbour information of each $p$. You can use that to path search (using A* or even greedy depth first) to the 3 points that surround $q$. Then you can extract the closest from that.

If the voronoi is stored as a binary tree where each line divides the space into half-planes then it's just a dive into the search tree.


Consider the path graph of length 3: $x-y-z-w$.

Take $S$ to be $y-z$, and $S'$ to be $x-y,z-w$.

A set of constraints for which your kind of argument does work is known as a matroid. The greedy algorithm that you describe does work for matroids (and, more generally, for greedoids). Your set of constraints satisfies a weaker condition: it is 2-extendible, meaning that in order to add a new element (in this case, an edge), you need to throw out at most two existing elements. The greedy algorithm always gives a 2-approximation for such systems of constraints.


Comment $\rightarrow$ answer.

Without loss of generality, we assume that all weights are strictly positive (otherwise, we can take all non-positively-weighted items ahead of time and change $W$ as appropriate).

From here, one can use an approach reminiscent of Randomized Quick-Select to solve this in expected linear time. First, define a tie breaking procedure for weights that consistently breaks ties between equal weighted items. For example, one can use the ordering of items as given in the input.

Now repeat the following procedure. Pick a random element $k$ and check if the sum of weights of all elements no heavier than $k$ (using the above tie-breaking rules) is less than $W$. If so, the optimal solution must contain all such elements, so put them all aside and recurse on the subproblem of elements heavier than k, with $W$ decreased appropriately. Otherwise, the optimal solution must be a strict subset of these elements, so discard all larger elements and recurse with the same $W$ you started with. The base case of the recursion is one where you return the empty set when $W$ is less than the cost of the cheapest item (or if no items remain).

Each round takes time linear in the input size for that round, but it takes a constant number of rounds (in expectation) to reduce the size of the instance by a constant factor, so the total running time intuitively should be expected linear. Indeed, the usual analysis of Randomized Quickselect works identically here, too, proving the result.

Here's a non-tail-recursive implementation in Python.

def uniformKnapsack(items, W):
    import random

    def subProcedure(remaining, new_W):
        # base case
        if remaining == [] or min(i[0] for i in remaining) > new_W:
            return []

        # sample random item
        random_item = random.choice(remaining)

        # split input into larger and smaller subsets based on the item
        smaller = [i for i in remaining if i < random_item]
        not_smaller = [i for i in remaining if random_item <= i]

        # compute the total cost of all smaller items
        smaller_cost = sum(i[0] for i in smaller)

        if smaller_cost <= new_W:
            # include all smaller elements and recurse on the rest with a smaller W
            return smaller + subProcedure(not_smaller, new_W - smaller_cost)
        else:
            # recurse on the smaller subset with the same W
            return subProcedure(smaller, new_W)

    # convert a list of items (a, b, c) to  a list of the form ((a, 0), (b, 1), (c, 2)) for
    # consistent tie breaking in comparison operations
    augmented_items = [(j, i) for (i, j) in enumerate(items)]

    # compute the solution over the augmented items
    solution = subProcedure(augmented_items, W)

    # return the un-augmented items from the solution
    return [i[0] for i in solution]


Algorithm for solving a mixed integer programming problem in polynomial time?

Finding an upper limit for k is trivial. Let d be the minimum of $b_i - a_i$ over all i, then k ≤ floor (1 / d).
And for each k up to the upper limit, it is trivial to check that floor ($a_i \cdot k$) = floor ($b_i \cdot k$).


There are many equivalent Hamming codes depending on the ordering of parity and data bits.
Assuming that:

You are using the specific bit ordering described here: https://en.wikipedia.org/wiki/Hamming_code#General_algorithm
By "even parity" you mean that the parity bits are computed as the sum (modulo 2) of the corresponding groups of bits
By "odd parity" you mean that the parity bits are computed as 1 minus the sum (modulo 2) of the corresponding groups of bits,

then yes, your simulation of the algorithm is correct.


Difference Between Small and Big-step Operational Semantics

Small-step semantics defines a method to evaluate expressions one computation step at a time. Formally speaking, a small-step semantics for an expression language $E$ is a relation $\rightarrow : E \times E$ called the reduction relation. Small-step semantics describes what happens to an expression in detail. It's able to give a precise account of even non-terminating programs, with an infinite chain $e_0 \to e_1 \to e_2 \to \dots$. A terminating program is one such that $e_0 \to e_1 \to \dots \to v$ terminates with a value $v$ such that $\forall e' \in E, v \not\rightarrow e'$.

$\newcommand{\llbracket}{[\![} \newcommand{\rrbracket}{]\!]}$

At the other end of the spectrum is denotational semantics. Denotational semantics assigns a “meaning” to each expression. It is a function from expressions to denotations: $\llbracket \cdot \rrbracket : E \to D$ ($D$ is called the domain). The space of denotations can be completely unrelated to the syntactic space, for example $E$ could be expressions that evaluated to a number and $D$ could be a set of numbers like $\mathbb{N}$ or $\mathbb{R}$.

Big-step semantics are kind of in the middle. A big-step semantics on an expression language $E$ and a set of values $V$ is a relation $\Downarrow : E \times V$. It relates an expression to its value (possibly multiple values if the language is non-deterministic). Often, a special value $\bot$ is used for non-terminating expressions.

So why do we have these three notions? All of these notions can model each other, but the model adds a degree of complexity.

Given a small-step semantics $\to$, you can define a corresponding big-step semantics that relates each expression to its value (or values, if the reduction is non-deterministic): $e \Downarrow v$ iff there exists a chain $e \to e_1 \to \dots \to v$ and $v$ cannot reduce any further. Note that in general you cannot reconstruct the small-step semantics from the big-step semantics. For example, all non-terminating expressions are indistinguishable under the big-step semantics.
Given a big-step semantics $\Downarrow : E \times V$, you can say that it's a small-step semantics on $E \cup V$. This is not particularly useful.
Given a small-step semantics $\to$, you can define a corresponding denotational semantics where the denotation of an expression is the set of reduction chains starting from it. This satisfies the formal definition, but it isn't particularly useful, because it adds a set theoretic overhead to objects which are easier to reason about by looking directly at the syntax.
Given a denotational semantics $\llbracket \cdot \rrbracket$, you can define a small-step semantics by adding all possible denotations as values in the language. That requires creating values that are not part of the syntax that the programmer can write, which means that some interesting results have to state “for all programs that the programmer can write” rather than “for all programs”. This one is thus not very useful either.
Given a big-step semantics $\Downarrow$, you can define a corresponding denotational semantics where the domain is the set of sets of values: $\llbracket e \rrbracket = \{v \mid e \Downarrow v\}$. If the big-step semantics is deterministic (each expression reduces to a single value), you can define a simpler denotational semantics where the domain is the set of values.
Conversely, given a denotational semantics $\llbracket \cdot \rrbracket$, you can define a big-step semantics $E \Downarrow \llbracket \cdot \rrbracket$. Again this one is a little pointless.

Operationally speaking, small-step semantics corresponds to looking at each operation performed by an interpreter for the language. Big-step semantics only looks at the resulting value. Denotational semantics looks at a mathematical interpretation which may or may not have anything to do with what happens on a computer.

Small-step semantics is the most obvious one. It clearly provides useful information about non-terminating programs. More generally, it provides detailed information about the behavior of the program.

Denotational semantics transforms syntactic constructs into arbitrary mathematical objects; it can express whatever the scientists wants (you can define the denotation of an expression to be all possible reduction chains from it), but at the cost of adding a level of complexity. It's used when we do want to abstract away some details such as exactly how the expression is evaluated.

Big-step semantics is in the middle: it abstracts away the details of the evaluation but retains the syntactic nature of the result. Usually the concept is used when there is an underlying small-step semantics, as a way to express concisely “$\exists (e_1, \dots, e_n), e \to e_1 \to \dots e_n \text{ and } \not\exists e', e_n \to e'$” as “$e \Downarrow e_n$”. In such constructions, while the concepts are very different (one allows us to talk about individual computation steps and about non-terminating programs, the other doesn't), the definitions will look very similar, because in this case the rules that define the big-step semantics are basically of the form “if $e_1 \to^* e_2$ and … and $e_n \to^* v$ and $v$ is a value then $e_1 \Downarrow v$”.


Running time of heap sort, when all number are identical

It would be $O(n)$, because each call to a siftdown or siftup procedure would be executed in $O(1)$ if well implemented.
Indeed, in a maxheap, the siftdown procedure is called in the heapify procedure, or to extract a node from the tree, and is defined as follow:
siftdown(x):
   while x is not a leaf and x is strictly smaller than its two children:
      swap x and its largest child

Since you consider an array of $n$ equal values, the test x is strictly smaller than its two children will never be true, so the loop will never be executed and the complexity is $O(1)$.
Now, the heapsort procedure in an array of size $n$ is defined as follow:

heapify the array ($n$ siftdown from last to first element);
extract each value ($n$ siftdown).

The total complexity is indeed $O(n)$. Please note that one can prove that the heapify procedure can be executed in $O(n)$ in all cases (and not only with equal values).


Proving $L = \{a^nb^m \mid n, m≥0, n \neq m\}$ is not regular by use of Pumping Lemma

This is a trick question. Your proof doesn't quite work, but can be turned into a proof, as follows.

Let $p$ be the constant in the pumping lemma, and consider the word $a^pb^{p+p!} \in L$. According to the pumping lemma, it can be decomposes as $xyz$, where $|xy| \leq p$, $y \neq \epsilon$, and $xy^iz \in L$ for all $i \geq 0$. Since $|xy| \leq p$, we must have $y = a^q$ for some $q \leq p$; since $y \neq \epsilon$, we must have $q \geq 1$. Let $i = p!/q + 1$. Then you can check that $xy^iz = a^{p+p!} b^{p+p!} \notin L$, contradicting the pumping lemma.

Here are two more proofs. The first uses closure properties. If $L$ were regular then so would the following language be: $a^*b^* \setminus L = \{ a^nb^m : n = m \}$. However, this language is known to be non-regular.

Another proof uses Myhill–Nerode theory. Let us say that two words $x,y$ are incomparable if there exists a word $z$ such that $xz \in L$ but $yz \notin L$, or vice versa. In any DFA for $L$, we must have $\delta(q_0,x) \neq \delta(q_0,y)$ (why?). Therefore, if we can find an infinite collection of pairwise incomparable words, then the language is not regular (why?). In the case of $L$, such a collection consists of the words $a^i$ for all $i \geq 0$. Indeed, if $i \neq j$ then $a^ib^j \in L$ whereas $a^jb^j \notin L$, showing that $a^i,a^j$ are incomparable.


How to determine if a database schema violates one of the less known normal forms?

From Wikipedia:

  1NF: The table faithfully represents a relation and has no repeating
  groups.

  2NF: Non-prime attributes are non functionally dependent on a proper
  subset of a candidate key.

  3NF: Non-prime attributes are non-transitively dependent on every
  candidate key in the table.

  BCNF: Every non-trivial functional dependency is a dependency on a
  superkey.

  4NF: Every non-trivial multivalued dependency in the table is a
  dependency on a superkey.

  5NF: Every non-trivial join dependency in the table is implied by the
  superkeys of the table.

  DKNF: Every constraint in the table is a logical consequence of the
  table's domain and key constraints.

Please let me know which, if any, of these requires further explanation. Each provides a means of checking whether a table is in the normal form.

EDIT: Again from Wikipedia:

  A join dependency is a constraint on the set of legal relations over a
  database scheme. A table $T$ is subject to a join dependency if $T$
  can always be recreated by joining multiple tables each having a
  subset of the attributes of $T$. If one of the tables in the join has
  all the attributes of the table $T$, the join dependency is called
  trivial.

  The join dependency plays an important role in the Fifth normal form,
  also known as project-join normal form, because it can be proven that
  if you decompose a scheme $R$ in tables $R_1$ to $R_n$, the
  decomposition will be a lossless-join decomposition if you restrict
  the legal relations on $R$ to a join dependency on $R$ called
  $*(R_1,R_2,...R_n)$.

In other words, if a constraint on your table $T$ is that T = R JOIN S for some tables $R$ and $S$, then $T$ has a join dependency $*(R, S)$.


Choose $n$ out of $2n-1$ boxes containing at least half of all white balls and half of all black balls

Let $B^*, B_1, B_2, \dots, B_{2n-2}$ be the the bins sorted by the number of white balls, in non-increasing order (break ties arbitrarily). Notice that the first bin is called $B^*$.

Consider the two groups $G_E = \{ B^* \} \cup \{B_i \mid i \text{ is even} \}$ and $G_O = \{ B^* \} \cup \{B_i \mid i \text{ is odd} \}$.
Clearly $|G_E| = |G_O| = 1 + \frac{2n-2}{2} = n$.

Moreover, each of $G_E$ and $G_O$ contains at least $W/2$ white balls.
This is true since since for each bin not in $G_E$ (resp. $G_O$) the previous bin in the sorted order must be in $G_E$ (resp. $G_O$). That is, the total number of white balls in $G_E$ (resp. $G_O$) is at least as large as the number of white balls not in $G_E$ (resp. $G_O$).

Now, total the number of black balls in at least one group $G^* \in \{G_E, G_O\}$  must be at least $B/2$. This is easy to see since $\{G_E, G_O \setminus \{B^*\}\}$
is a partition of the set of bins, and hence the bins in at least one set of the partition (which is either $G_E$ or a subset of $G_O$) must contain at least half the black balls.


If $R,F \cap R, F \cap \overline{R}$ are regular, is $F$ regular?

Here's a hint. First, show that for any two sets $A, B$, that $A = (A\cap B)\cup(A\cap\overline{B})$. Then use the fact that the union of two regular languages is regular.


Can the Lambda Calculus or Turing Machines model signals, callbacks, sleep/wait, or buses?

Yes, there are natural extensions of the $\lambda$-calculus for handling I/O, parallelism, concurrency, exceptions, timeouts, etc. In general such things are viewed as computational effects and there is a rich theory of $\lambda$-calculus for computational effects. This is what Haskell monads are about -- Haskell is $\lambda$-calculus extended with features that you are asking about.

But let me point out that you mix a bunch of features together which are really of two different kinds:

Interaction with external environment: I/O, communication, timeouts, concurrency, etc.
Programming models: callbacks, semaphores, shared memory, parallelism, etc.

A classical Turing machine does not interact with an external environment, but it can be modified to do so. For instance, an oracle is essentially an input stream. The so-called "type 2 machines" are Turing machines with infinite input and output tapes which correspond to an input and an output channel, etc. I am sure someone invented "real-time Turing machines", but I think such endaveours miss the point of mathematical models of computation. A mathematical model is designed specifically to fit well a chosen set of features that we want to model. Turing machines were invented to explain what "possible to compute" means, not "how to compute". If you want to model I/O and such then there are better mathematical models to stick to ($\pi$-calculus was suggested by someone).

The second set of features you asked about is really a bunch of programming methods. As is well known, any Turing complete computational model can be used to simulate any other such model. For instance, a Turing machine can compute things in parallel through a technique known as dovetailing. I would not be surprised if dovetailing was invented several decades before the first parallel operating sytem came into existence. (In fact, it must be the case that dovetailing appreaded already in Turing's original 1936 paper, can someone confirm this?)

Callbacks are well known to functional programers, as these are just functions (but if you spend your life programming operating systems in C you will think they are special), while threads and coroutines are known as continuations. So some concepts that look fancy from one perspective are basic and straightforward from another. Another that comes to mind is the object-oriented idea of an "iterator" which gets vastly generalized in functional programming.


Normal order sequencing vs applicative order sequencing

You're misreading the combinator. In these lecture notes, lambda abstraction binds tighter than application (the opposite convention is more common — it's apparent from the spacing but the author should state that explicitly). I'll use extra (redundant) parentheses in my answers to avoid any potential for ambiguity. The combinator is
$$ \mathit{Seq} = \lambda x. \lambda y. ((\lambda z.y) \: x)$$
So
$$ \begin{align}
  & ((\mathit{Seq} \; (\text{display "hello"})) \; (\text{display "world"})) \\
  &\qquad = (((\lambda x. \lambda y. ((\lambda z.y) \; x)) \; (\text{display "hello"})) \; (\text{display "world"})) \\
  &\qquad \to^2 ((\lambda z. (\text{display "world"})) \; (\text{display "hello"})) \\
  &\qquad \xrightarrow{\text{display "hello"}} (\text{display "world"}) \\
  &\qquad \xrightarrow{\text{display "world"}} \mathord{?} \\
\end{align} $$
where $M \xrightarrow{\text{action}} N$ means that $M$ evaluates to $N$ performing the specified action.


How many clauses are required for SAT to be NP-hard in CNF formulas?

Lower bound. For $g \le c \cdot \sqrt{\log n}$ there exists a polynomial-time algorithm. The idea is the following: if some clauses have too many variables, then it should be trivial to select some variable to satisfy this clause, without hurting clauses with few variables. We repeat the following:
Find the clause with the smallest number of variables. Let $x_1,\ldots,x_k$ be the variables participating in this clause.

If $k > g$, then the entire formula is satisfiable (we process clauses one by one and select a variable which we didn't select before).
Otherwise, we remove the clause. We also remove $x_1,\ldots,x_k$ from all other clauses.

Now, we have to satisfy the removed clauses. Since there are at most $g$ clauses and each of them introduces at most $g$ new variables, it means that there are at most $g^2 = c^2 \cdot \log n$ variables overall. Therefore, there are at most $n^{c^2}$ variable combinations, and we can just use brute-force.
Conditional upper bound. It is almost tight in the following sense. Assume that the lower bound on the SAT with $n$ variables and $\ge c\cdot n$ clauses (for some $c$, e.g. coming from $3$-coloring) is $\alpha^n$ ($\alpha \in (1, 2]$). Note that the same lower bound holds after our transformation (since we can just apply it before any algorithm). Therefore, if there are at least $\log^{1+\epsilon} n$ clauses, they can have $\frac {\log^{1+\epsilon} n} c$ variables and the lower bound for running time for our problem is
$$\alpha^{\frac {\log^{1+\epsilon} n} c} = n^{\frac {\log^\epsilon n \cdot \log \alpha} {c}},$$
which is super-polynomial.


Algorithm A vs Algorithm A*: What's the difference?

Both A and A* algorithm use a best-first search to find the least cost path from a start state to a goal state.

Best-first search applies a heuristic evaluation on the states to find the 'best' state.
Consider the evaluation function f,

f(n) = g(n) + h(n)

where g(n) measures the cost of reaching any state n from the start state
and h(n) is a heuristic estimate of the cost of going from state n to a goal.
f(n) estimates the total cost of the path from the start state throngh n to the goal state

If this evaluation function is used with best-first search, then the result is Algorithm A.
Here h(n) is just an estimate of the cost of going from n to a goal. The actual cost is not known.

Now consider the evaluation function f*,

f*(n) = g*(n) + h*(n)

where g*(n) is the cost of the shortest path from start state to state n
and h*(n) is the actual cost of the shortest path from state n to goal.

Although f* does not exist for most real problems, we would like f to be a close estimate of f*.
In algorithm A, g(n) is a reasonable estimate of g*(n).

g(n) >= g*(n)

They are equal when the graph search has discovered an optimal path to n.

Although we may not compute h*, it is often possible to determine whether or not the heuristic estimate h(n) is always less than or equal to the actual cost of minimum oath, h*(n).

If the Algorithm A uses a function f in which

h(n) <= h*(n) ,

it is called algorithm A*.


An integer is a value, whereas a pointer to an integer is a pointer, that is, a memory address. In most systems, all pointers have the same size, but the objects they point to can have different sizes. For example, in your systems pointers are 8 bytes long, whereas integers come in various sizes — possibly from 1 byte up to 8 bytes.

You might be misled by the specific quirky syntax of C, which allows declarations of the form

int a, *b;

This declares an integer a and a pointer b. This is just a confusing feature of C syntax.


Space optimised versions of Coin Change and Knapsack Problems in Dynamic Programming

The difference is whether the solution to the "add element i" subproblem being considered (dp[j - weight[i]] or dp[j-a[i]], as the case may be) allows or forbids a contribution from the current element (value of i).

When the inner loop moves right-to-left, at the time dp[j - weight[i]] is evaluated, that table entry has not yet been updated in this iteration of the outer loop, so it definitely does not include a contribution from element i. Thus the candidate solution having value val[i] + dp[j - weight[i]] includes exactly one copy of element i (and the other candidate solution, dp[j], includes exactly zero copies of it).

OTOH, when the inner loop moves left-to-right, at the time dp[j - weight[i]] is evaluated, that table entry has already been updated in this outer loop cycle, so it may represent a solution that already contains an element i, to which we are now considering adding a second element i. In fact it may already contain multiple copies of element i, since that table entry may have been computed as the result of choosing val[i] + dp[j - weight[i] - weight[i]], etc.


How hard is recovering a binary matrix from its check sums?

Parity problem

It is clear that $\sum_i R_i \equiv \sum_j C_j \pmod{2}$ must hold if any solution exists. On the other hand, if this holds then some solution exists. Let $R$ contain $a$ ones, and let $C$ contain $b$ ones. We can assume without loss of generality that $a \geq b$. Arrange the rows and the columns so that
$$
\begin{align*}
&(R_1,C_1) = \cdots = (R_{n-a},C_{n-a}) = (0,0) \\
&(R_{n-a+1},C_{n-a+1}) = \cdots = (R_{n-b},C_{n-b}) = (1,0) \\
&(R_{n-b+1},C_{n-b+1}) = \cdots = (R_n,C_n) = (1,1)
\end{align*}
$$
Note that there is an even number of occurrences of the second type. We now construct a block diagonal matrix with the following blocks:
$$
\begin{pmatrix}
0
\end{pmatrix}
 \times (n-a), \quad
\begin{pmatrix}
1 & 0 \\ 1 & 0
\end{pmatrix}
\times (a-b), \quad
\begin{pmatrix}
1
\end{pmatrix}
\times b
$$

Sum problem

When the actual sums are given, we have the digraph realization problem, which can be solved efficiently.


supply a matching data structure that supports MakeEmpty, Insert and DeleteFreq

"""

This file is both Markdown and Python.

We keep the keys in two data structures. One is a
doubly-linked list, like this:

| <- [] <-> [] <-> [] <-> [] -> |

Here, [] is a node and | is None. Pointers are one-way
(->) or two-way (<->).

Instead of being terminated by null pointers, the list
will be terminated by nodes that point to themselves. An
empty list looks like this:

[o] <-> [o]

Here [o] is a node that points to itself. These nodes
are called "sentinals".

Nodes keep two other pieces of data. The first is a set of
keys. The second is a frequency, which represents the
number of times each of those keys is in the multiset. For
instance, If you insert a twice and b seven times and
c seven times, there is a node in the list with
frequency set to 7 and the set of keys {b, c}.

[o] <-> [7, {b,c}] <-> [3, {a}] <-> [o]

The other invariants that are maintained:

The nodes are stored in frequency order
The sentinal at the high-frequency end has frequency
None
The sentinal at the low-frequency end has frequency 0
No node has negative frequency
No two nodes have the same frequency
The sentinals have empty key sets, but no other nodes
have empty key sets

So:

"""
class FreqBucket(object):
  def __init__(self, lo, hi, freq):
    self.lo = lo
    self.hi = hi
    self.freq = freq
    self.kids = set()

  def __repr__(self):
    return ("FreqBucket({}, {}, {}, {})"
            .format(self.lo.freq, self.hi.freq,
                    self.freq, self.kids))

  def unlink(self, key):
    """Remove key and remove self from the list if necessary"""
    if key in self.kids: self.kids.remove(key)
    if not self.kids:
      self.hi.lo = self.lo
      self.lo.hi = self.hi

  def increase(self, key):
    """Increase the frequency of the given key from this node"""
    result = self.hi
    if self.hi.freq != self.freq + 1:
      # There is no FreqBucket with the right .freq, so we
      # must make a new one:
      old_hi = self.hi
      self.hi = FreqBucket(self, self.hi, self.freq + 1)
      old_hi.lo = self.hi
      result = self.hi
    # Move the key to the next FreqBucket:
    result.kids.add(key)
    self.unlink(key)
    return result
"""

TallPoppies uses the list of FreqBuckets described
above. It keeps a map in which each key in the structure
maps to its corresponding FreqBucket.

"""
class TallPoppies(object):
  def __init__(self):
    # The keys of the self.keys dictionary are the inserted
    # objects; the values are FreqBuckets.
    self.keys = {}
    # Make the sentinels and link them to each other and
    # themselves. We need mini for inserts and maxi for
    # deletes.
    self.mini = FreqBucket(None, None, 0)
    self.mini.lo = self.mini
    self.maxi = FreqBucket(None, None, None)
    self.maxi.lo = self.mini
    self.maxi.hi = self.maxi
    self.mini.hi = self.maxi

  def __repr__(self):
    return ("TallPoppies({}, {}, {})"
            .format(self.keys, self.mini, self.maxi))

  def insert(self, key):
    if key in self.keys:
      self.keys[key] = self.keys[key].increase(key)
    else:
      self.keys[key] = self.mini.increase(key)

  def delete_freq(self):
    result = self.maxi.lo.kids.pop()
    self.maxi.lo.unlink(result)
    del self.keys[result]
    return result

insert and delete_freq take expected amortized O(1) time. You need hash tables and linked lists, but not search trees.


Is Equational Reasoning an application of Referential Transparency?

Referential transparency is an operational notion: it describes what happens when you evaluate a same piece of code (typically a function) several times, namely, the return value is the same. In particular, the evaluation context can generally be ignored when considering the operational semantics of a referentially transparent language.

Equational reasoning is, well, a way to reason about code: it allows you to replace pieces of code with others without worrying about things like evaluation order or current state. This is usually valid because of referential transparency; in general the value of a given code block is dependent on it's context which prevents replacing a piece of code by another regardless of it's position within another block.

In conclusion, referential transparency is a property of the evaluation semantics and the ability to do equational reasoning is a benefit of this property.


It's necessary to replace all the population each generation in a genetic algorithm?

GAs are heuristic algorithms. They don't guarantee optimality in any but the most trivial problems. Hence there are no strict rules how to implement them. What works and what doesn't depends your exact problem. Tuning the parameters of a GA is somewhat of a dark art and people turn to heuristics for tuning their heuristics.


How to find all paths of length up to k between two nodes in a directed graph?

I'm not sure whether "best" is answerable, but I will describe one simple strategy that appears reasonable.  Let $S(u,v,d)$ be the set of all such paths of length $d$.  Then

$$S(u,w,d+1) = \{u \leadsto v \to w \mid u \leadsto v \in S(u,v,d), v \to w \in E\}$$

Also $S(u,u,0) = \{u \to u\}$. This gives a dynamic programming algorithm for computing the set of all such paths, if you evaluate these sets in order of increasing $d$.

As an optimization, you can delete all vertices that aren't reachable from $u$ or that can't reach $v$ before beginning this computation.  As another optimization, you can precompute the matrices $A^k$, where $A^k_{uv}=1$ if there is a path of length $k$ from $u$ to $v$ (these can be obtained from the adjacency matrix by repeated multiplication); then you only evaluate $S(u,w,d)$ for $u,w$ such that $A^d_{uw}=1$ and $A^{k-d}_{wv}=1$.

With these optimizations, if there are a total of $Q$ such paths that you want to output, then the running time will be at most $O(kQ \cdot |E|)$.  There's not much opportunity to do much better than that; obviously any algorithm must take at least $\Omega(Q)$ time, and since $Q$ will typically be exponentially large compared to $k|E|$, the gap between the upper and lower bounds will typically be a small factor compared to the total running time.


Intersection of languages using closure properties

One of the closure properties of CFL is that they are closed onder intersection with regular languages. This can be directly applied, rather than first promoting the regular language to context-free language.

In general, if we want to know the family in which the intersection (or whatever operation $\oplus$) of two languages belongs, then we look for the smallest families $\mathrm{X}$ and $\mathrm{Y}$ that contain the two languages and for which we know an applicable closure property.

In your terminology, we "promote" as little as possible, but enough to find a family/families for which the closure property is known.


Maximum Enclosing Convex Polygon of a Given Area

It sounds like your problem is the following:

  Given $n$ points $p_1,\dots,p_n$ in the plane and an area $A$, find a polygon $\mathcal{P}$ whose area is $\le A$ and that contains as many of the $n$ points as possible.

This problem looks pretty tough to me, and I don't have a great algorithm for it, but I'll suggest two schemes.  The first solves a simplified version of this problem (for rectangles instead of arbitrary polygons), and the second is a heuristic algorithm that might or might not work "well enough" on real-world instances.

Simplified variant: rectangles

Suppose we focus on the easier case where $\mathcal{P}$ must be an axis-aligned rectangle.  Then I can give a $O(n^2 (\lg n)^2)$ time algorithm.

Without loss of generality, the $x$-coordinate of the left and right sides of this rectangle must agree with the $x$-coordinate of some pair of points, and similarly for the top and bottom sides.

So, guess the $x$-coordinate of the left side of the rectangle (there are $\le n$ possibilities), say $x_L$.  Now, do a binary search on the width of the rectangle (there are $\le n$ possibilities), using the following ideas.

Given a guess at the width $w$ of the rectangle, you can calculate the maximum number of points that can fit in an allowable rectangle with those $x$-coordinates for the left and right sides, as follows.  Start by filtering out all points whose $x$-coordinate is not in $[x_L,x_L+w]$.  Sort the remaining points by their $y$-axis.  Now look for the $y$-value $y_B$ for the bottom side of the rectangle, which maximizes the number of remaining points whose $y$-coordinate is in the range $[y_B,y_B+A/w]$.  This can be found with a straightforward linear scan of the remaining points (with two pointers advancing monotonically).

With this, given $x_L$, you can do a binary search for $w$.  Each guess at $w$ takes $O(n \lg n)$ work to compute the maximum number of points that can be fit into a rectangle of that sort.  Since there are $\le n$ possible values for $w$, you'll do $O(\lg n)$ iterations in the binary search.  Since there are $\le n$ possibilities for $x_L$, the overall running time is $O(n^2 (\lg n)^2)$.

Since a rectangle is a convex polygon, this gives you a lower bound on the number of points that can be covered by a convex polygon with area $\le A$.  It might not be an especially tight lower bound, but maybe it's a start.

Heuristic for arbitrary polygons

We could use branch-and-bound type techniques here.

Define a directed acyclic graph (dag), the search dag, where each vertex is a convex polyhedron $\mathcal{P}$ obtained as the convex hull of some subset of the $n$ points, and there is an edge from $\mathcal{P}$ to $\mathcal{Q}$ if there is some point $p_i$ not in $\mathcal{P}$ such that the convex hull of $\mathcal{P},p_i$ is $\mathcal{Q}$.  The root of this graph is the empty polyhedron, which covers no points.  Call any node of this graph that has no out-edges a "leaf".  The best polyhedron must be some leaf.

A naive approach would be to do a breadth-first search on this dag.  Unfortunately, the dag is probably exponential in size, so this naive approach will probably be too slow.

You might do better using branch-and-bound techniques.  Define the "quality" of a leaf in this graph to be the number of points covered by its associated polyhedron.  Also, define the "quality" of a node $x$ in this graph to be the maximum of the quality of all of the leaves that are reachable from $x$.  Of course, we cannot compute the quality of a node without exploring everything reachable from it (which is too expensive), but we can estimate it.

In particular, we can compute an upper bound on the quality of any given node.  This is enough to do branch-and-bound.  We basically iteratively explore the graph.  At each stage, we keep track of the "best" solution we've found so far: i.e., among all the polyhedron $\mathcal{P}$ corresponding to some node we've visited, keep track of the maximum number of points covered by any of these.  Say this number is $b$.  Now if we reach a node $x$ where our upper bound on its quality implies that the quality of $x$ is $\le b$, then we don't need to visit $x$ or any of its descendants.  This might help us reduce the search space.

How do we get an upper bound on the quality of a node?  Well, here's one way.  Suppose we have precomputed, for each $i=1,2,\dots,k$, the minimal area of any convex polygon that contains $i$ points, call it $\alpha(i)$.  Now if we have a node $x$ that corresponds to a polyhedron $\mathcal{P}_x$ of area $A_x$, and if $A_x+\alpha(i) > A$, then here's an upper bound on the quality of $\mathcal{P}$: it must be at most the number of points contained in $\mathcal{P}$, plus $i-1$.  This could be a somewhat loose bound, but it is something.

How do we do the precomputation?  Well, that's basically an easier instance of the same problem, with a smaller value for $A$.  So, we can do the precomputation via a recursive or iterative application of this algorithm, for increasing values of $A$ (or via similar ideas).


Does this pushdown automaton describe the language {$a^n b^n c^i \in \{a,b,c\}^*\ |\ n \ge 0,i\ge 0$}?

As I am (not) yet certain of the PDA model you are using, I will not comment on correctness of your construction, but I have a general remark on PDA.

There happen to be two generic ways of defining languages for PDA: by final state and by empty stack. Let a configuration be a description of the PDA, its (yet unprocessed) tape, state, stack.

Using final state acceptance means that we accept any word that leads from the initial configuration of the automaton to a configuration that is in a final state (no matter what is the contents of the stack) after reading the complete input.
Similarly, empty stack acceptance means that we accept any word that leads from the initial configuration of the automaton to a configuration in which the stack is empty (no matter what is the state) after reading the complete input.

By standard constructions one is able to change a PDA into an equivalent one using the other acceptance type. so for practical reasons the two notions are interchangeable. When dealing with technicalities (in case of deterministic automata for instance) the acceptance type does matter.

In conclusion: if you are using final state acceptance, then do not worry about remaining stack symbols.


Why do Amdahl's law and Gustafson's law give us different speedups, when applied on the same task?

The reason is that Amdahl's law and Gustafson's law refer to two very different situations.

In particular, Amdahl's law applies to those cases in which the problem size is fixed, e.g. you need to process a static dataset or an image of given dimensions. The law treats the problem size as being a constant (size constrained model), and clearly shows how the execution time decreases as the number of processors increases. This law can be applied to any system, not just to parallel systems; it is a very general statement about any improvement  in a system, i.e., no matter how much one improves one part of a  system, the improvement in the overall performance is bounded by  $1/f$, where $f$ is the fraction of the original time spent in parts of the system one does not improve. This model, fixing the amount of data per processor, usually provides the highest efficiency possible (this is commonly referred to as strong scaling).

On the other hand, rather than assuming that the problem size is fixed, it is just as valid to assume that the parallel execution time is fixed. This is exactly what the Gustafson's law does: as the parallel system size is increased (i.e. the number of processors $p$ is increased), the problem size is increased to maintain constant parallel execution time (weak scaling). Therefore, this is a time constrained model. So, the important difference is that the scaled speedup of Gustafson starts with a big problem on a big ($p$ processors) machine and looks back toward the one-processor case and asks how  long it would have taken to execute, whilst Amdahl's law starts with a problem on the one-processor machine, and asks how long it might take on a many-processor parallel machine. Gustafson simply noted that there were lots of problems that seemed  to run well on lots of processors: they computed for a great deal of time $(1-s)$ using all the processors, and not all that long $(s)$ in a serial fashion. So he derived the scaled speedup formula to help explain that.

Does this contradict Amdahl's law? No, of course.
Amdahl works when you are given a fixed size input and you want to understand how fast you can process in parallel that input. Gustafson works when you can increase the problem size and you want to solve larger problems in the same amount of time. For instance scientist are actually interested to solving larger instances of problems, or want to increase the complexity of a model to gain better accuracy.


How to write an algorithm which doubles stack in order to accommodate for new members where push is in constant time in the worst case?

I don't think that it is possible to push an element to a full array-based stack in worst case $\mathcal{O}(1)$ time. However, you can rest assured that each push runs in constant amortized time whenever you multiply the length of the full array by a factor of $q > 1$ (like you do; $q = 2$ in your case). This is why:

Suppose the initial array capacity is $m$. Next we choose $q > 1$ such that $\lfloor qm \rfloor > m$, or namely, $q$ must be sufficiently large in order to trigger an array expansion.

Suppose the total accumulated work of adding $n$ elements to the stack is

$$W = m + mq + mq^2 + \dots + \overbrace{mq^k}^n$$.

We require $k$ to be the smallest integer such that $mq^k \geq n$, which leads us to the following inequalities:

$$
\begin{aligned}
mq^k &\geq n \\
q^k &\geq \frac{n}{m} \\
\log_q q^k &\geq \log_q \Bigg( \frac{n}{m} \Bigg) \\
k &\geq \log_q n - \log_q m.
\end{aligned}
$$

Since $k$ is required to be the smallest integer satisfying the above inequality, we can set $k = \lceil \log_q n - \log_q m \rceil$. Also,

$$
\begin{align}
qW = mq + mq^2 + \dots + mq^{k + 1} &\Rightarrow W - qW = m(1 - q^{k+1}) \\
    &\Rightarrow W = m\frac{1 - q^{k+1}}{1-q}.
\end{align}
$$

Since $k = \lceil \log_q n - \log_q m \rceil$, we obtain
$$
\begin{align}
W &= m\frac{1 - q^{\lceil \log_q n - \log_q m \rceil + 1}}{1 - q} \\
  &\leq m\frac{1 - q \cdot q^{\lceil \log_q n \rceil}}{} \\
  &\leq m \frac{1 - q \cdot q^{\log_q n + 1}}{1- q} \\
  &= m \frac{1 - q^2n}{1 - q}.
\end{align}
$$

Now we have that

$$
\begin{align}
\frac{1}{n} W &\leq \frac{1}{n} \Bigg[ m \frac{1-q^2n}{1-q} \Bigg] \\
              &= \frac{1}{n} \Bigg[ \frac{m}{1-q} - \frac{nmq^2}{1-q} \Bigg] \\
              &= \frac{m}{(1-q)n} - \frac{mq^2}{1-q} \\
              &\leq \frac{m}{1-q} - \frac{mq^2}{1-q} \\
              &= \frac{m(1-q^2)}{1-q},
\end{align}
$$
which is constant since $m$ and $q$ are fixed parameters independent of $n$.


Equivalence of states between two "quasi-deterministic" strongly connected Büchi automata accepting the same $\omega$-language

Your property does not hold.

Consider the following languages over $\Sigma = \{a,b\}$:

There are infinitely many $a$s at even positions in a word
There are infinitely many $a$s at odd positions in a word

Both are representation as DBAs with the same set of states (of size 3). We can build DBAs for them that only differ in their initial states.

If we want to build an automaton for the disjunction of these languages, we can do so by taking both initial states for both of them as new initial states. This gives us a qDBA $B_1$.

The disjuction is equivalent to the language "there are infinitely many $a$s", for which a DFA $B_2$ only needs two states, each of which have the same language.

Now, $B_1$ and $B_2$ are a counter-example to your conjecture.


The inner loop will iterate $n - r + 1$ times for each iteration of the outer loop. To find the total runtime, we can sum this expression over $r = 1$ to $r = n$:
\begin{align*}
\sum_{r = 1}^{n} (n - r + 1) &= n^2 - \left(\sum_{r = 1}^{n} r\right) + n \\
&= n^2 - \frac{n(n + 1)}{2} + n \\
&= \frac{1}{2}n^2 + \frac{1}{2}n
\end{align*}
which is $\Theta(n^2)$.

To simplify the proof, we can note that the sequence $(n - r + 1)_{r \in [1, n]}$ is just the sequence $1, 2, \ldots, n$, which you can see by substituting $r = 1$ and $r = n$ into $(n - r + 1)$. We know that this sum $\sum_{i = 1}^{n} i$ equals $\frac{n(n + 1)}{2}$, giving the same result as the first method.


What's the difference between a bridge, a mediator and a wrapper?

It was very common for early patterns research to put a lot of emphasis on the "intended use" of a pattern, over and above any structural differences in the implementation.  Then, people who were at that stage of architectural maturity where they were "doing patterns because patterns is what you do" developed long, often elaborate explanations on why these alleged differences were important.

However, research has shown that the structure is really all that matters, because the semantic distinctions:

have no formal distinctions, even in the mathematical treatment of type theory
are not enforceable without syntactic differences in developing the type relations (compiler needs something to enforce)
therefore change with changing requirements
and should not be forced not to change, as reuse is the point of good architecture

So much of those large discussions on why strategy is different than state have turned out quite labored, unconvincing, ineffectual, and slightly humorous as the years have moved on.

My suggestion is to ignore any "is used for" discussion at all and completely focus on the type relationships.  If you do that, then you will find that (depending on your particular definition of these patterns, but fairly standard here)

Mediator > Bridge > Adapter

where the > relation should be read as "is implemented using".  Adapter is a functional relationship between three or more types around on one abstraction tree.  Bridge and Mediator are functional relationship between four or more types around two abstraction trees, defining an interface between the abstraction trees.  Mediator adds to the type coupling usage relationships between concrete nodes of the abstraction trees.

Typically, Mediator is a bad pattern (antipattern) that doesn't scale well and causes an application to become monolithic.  It is used very frequently because people read what it does and go "oh, I need that" and use a pattern becasue, as above, well, patterns are "what you use".  They may be an intermediate step while decoupling a heavily coupled application during refactoring, but typically if you are making that step, full decouple to Bridge (with a factory) is indicated and just as easy.


What is the difference between quantum computing and parallel computing?

For a parallel computer, we need to have one billion different processors. In a quantum computer, a single register can perform a  billion computations. This is known as quantum parallelism. Also a quantum computer returns a single randomly-selected correct result, while a parallel computer can directly return all valid results. That's the reason why reading results out of quantum computers generally is slow and getting all results requires running the quantum computation enough times to be relatively certain that the random sampling has seen all possible results.
Hope this helps!
See this also: differences-between-quantum-computing-and-parallelism


How do I continue learning programming, beyond the basics?

If you're looking for some hands-on programming experience that also allows you freedom to do what you want, why not join an open source project? One such project is the Sage Math project

http://www.sagemath.org/development.html

It basically is an open-source project that develops a Python-like language for coding math. It has some cool features, especially in algebra and graphs, but also suffers from many bugs. Of course, there are many other open source projects you could find.

This would help you on many levels

Learn at your own pace
Work on anything that you like (provided that it is math related)
It will give you hands on experience at code development, committing, bug reporting and tracking. Basically anything and everything that you'll ever need to become a full-on programmer. Many people who work on such projects are top notch experts in their fields, so this could be a real opportunity.
You are contributing to society!

Alternatively, you could also take some online coding tasks (http://www.topcoder.com/) and even get paid for them. However, if your coding knowledge is not too great, this may not be the ideal place to start.

Good luck!


Solving T(n) = 3T(n/3)+n/2 using master method

While applying master's theorem all you have to do is compare which of $f(n)$ or $(n^{\log_b{a}})$ is asymptotically greater. The greater of the two functions determines the solution to the recurrence. There are only possible outcomes for this comparison:
[1] $(n^{\log_b{a}})$ is asymptotically greater than $f(n)$
[2] Both are asymptotically equal
[3] $f(n)$ is asymptotically greater than $(n^{\log_b{a}})$

Yours falls in case 2.


How is Johnson's shortest path weighting function $\hat{w}(u, v) = w(u, v) + h(u) - h(v)$ proven by the triangular inequility?

You're right that you can't (necessarily) apply the triangle inequality to the edges of the original graph, but that's not what's being discussed here.

We know $h(u)$ is, by definition, the shortest path to $u$.  Thus we immediately know that $w(u,v) + h(u) \geq h(v)$ because, if it wasn't true, $h(v)$ would not be the shortest path to $v$.  The author is calling this the "triangle inequality" of the reweighted graph.


Is it possible to get information from websites as a human?

The comments by David and D.W. are accurate. Your question is way too broad. But to give you a hint were you might start to dive deeper into the field, here is a very general answer to your question:

Yes, it is possible. Although, the methods we have are at the moment not as good as human performance (not surprisingly—the task is very hard; side note: If you restrict the text genre and the kind of information you are looking for strongly enough (say gene interactions in biomedical texts) then it is actually possible to achieve near-expert performance).

The name of the task you are describing is information extraction.

An excellent text book which covers elementary methods of it (as well as lots of basics in natural language processing you need to know for that) is this one. There should be free pdf version around in the web as well.


Can a 600 MB text file with digits of the square root of 2 be compressed to 600 KB?

Clearly that's a way too good compression rate. $\sqrt{2}$ is not a rational number, so the decimal expansion will not start repeating. So there has to be something really fishy going on.
I run your script, and looked at the resulting file.
On my machine, the file square_root_of_2_with_536870912_bits.txt contains 161.614.250 digits, and the last 161.597.755 digits are all zeros. Only the first 16.495 digits are different from zero.
So given that pretty much almost everything in the files are zeros, it's not unexpected that the compression rate is so high.

I'm not experienced with the bigfloat package, so I can't tell if the bug is in your program or in the package itself. If you can't figure the error out yourself, open an issue on their Github page.
Btw, from those 16.495 digits, only about 5.000 of those are correct.


In the average case, you want the circuit to succeed in computing the function for a large portion of all possible inputs. Since a constant function always succeeds for at least half the inputs (the majority of $f$), the interesting case in where you can achieve advantage which is greater than $\frac{1}{2}$.
In the worst case, you want the circuit to succeed in computing the function for all inputs, so you want to say that $f$ is at least $H(n)$ worst case hard if any circuit of size $\le H(n)$ disagrees with $f$ on at least one input in $\{0,1\}^n$.


Algorithm for length of longest common subsequence

The algorithm is incorrect. That is it may return a length that is greater than the actual length of a longest common subsequence. Here is a test case which fails to produce the correct length: ['baaa', 'aaba', 'baba'].


Calculate the sum of all sub-arrays with given indices

You can use the concept of segment trees. Check this link:
https://en.wikipedia.org/wiki/Segment_tree and https://www.geeksforgeeks.org/segment-tree-set-1-sum-of-given-range/
The above link works for finding the sum of all the elements in a given range [i,j]. However, you can use the same approach to find the minimum element in the range [i,j] in $O(\log n)$ time. The idea is that you can break the range [i,j] into $O(\log n)$ smaller ranges, and for each of these ranges you already know their minimum values via some binary tree (built during pre-processing step). Thus, you can take the minimum over all these small ranges, and it will give the overall minimum in the range [i,j] in $O(\log n)$ time.

Building the binary tree comes under the pre-processing step and it will only take $O(n)$ time.
Also, there are $m$ queries and each query takes $O(\log n)$ time. The overall time complexity would be $O(n + m \log n)$. Since $m < n$, the overall complexity is $O(n \log n)$.


Why is log(n/p) asymptotically less than log(n)/log(p)

I assume that $p > 1$ (which is equivalent to $\log p > 0$, otherwise we have negative-valued functions which are meaningless as complexity measures.

For a given $p$,  $O\left(\frac{\log n}{\log p}\right) = O(\log n)$ since big oh isn't affected by multiplication by a positive constant.
$\log \frac{n}{p} = \log n - \log p$. Since $\log p = o(\log n)$, $O\left(\log \frac{n}{p}\right) = O(\log n)$.

So up to big-oh complexity (or big-theta, for the same reasons), these two classes are the same.

Your diagram doesn't show a visual difference: you need to bring the two curves to the same scale. One is $a \log n$ for some constant $a > 0$, the other is $\log n + b$ for some constant $b$.

If you want to study the variation in $p$, then $O$ or $\Theta$ with respect to the variable $n$ are not good ways of modeling the complexity of your problem. You need more precise approximations that treat multiplicative constants as relevant. The complexity in $p$ is probably relevant to your problem, and is very different. I'm not familiar enouhg with parallelism to know whether it's the right measure to use here, this could warrant a separate question (with more information about what you're modeling). You're going to need express the complexity in terms of $n$ and $p$, and look at how the variation in $p$ (not the complexity itself) behaves for large $n$.


Algorithmic Design to Undo Rotation of Array

I assume this is a homework question, so I will not solve it for you. I'll just give you some hints.

The problem is basically to find the drop in $A_k$, that is the pair of consecutive elements such that the second one is smaller than the first one. Indeed, these two must be the last and first element of $A$.

Now, if you are given a subinterval of $A_k$, how can you tell whether it contains the drop? Hint: It can be done in $\Theta(1)$.


Why is this a proof by contradiction for this algorithm? Isn't this a direct proof instead?

You seem to think the structure of the proof is:

suppose the algorithm is incorrect;
prove that the algorithm is, in fact, correct;
this contradicts 1., so the algorithm is correct.

That's almost, but not quite true. Step 2 doesn't prove that the returned value $\mathrm{max}$ is bigger than every element of the array, which is what would be required to prove that the algorithm is correct. It just proves that $\mathrm{max}$ is bigger than the specific array value that was supposed to be a counterexample in step 1.

But, as Yuval has pointed out, the proof is much easier if you forget about contradiction completely and prove that $\mathrm{max}$ is in the array (identical to the given proof) and then show that $\mathrm{max}$ is at least as big as every array element (identical to the proof except "for all $j$" instead of just for one supposed counterexample.


A Turing Machine that exclusively accepts an infinite string

In contrast to the commenters, it is perfectly possible to define a Turing machine formalism whose input can be infinite. Let $\Sigma$ be an alphabet, and let $\#$ be a symbol not in $\Sigma$. We say that a Turing machine $T$ accepts a finite word $w \in \Sigma^*$ if it halts in an accepting state when the tape is initialized by $w \#^\omega$ (i.e., $w$ followed by infinitely many copies of $\#$; I assume for simplicity that the tape is only one-way infinite). Similarly, $T$ accepts an infinite word $w \in \Sigma^\omega$ if it halts in an accepting state when the tape is initialized by $w$.

We say that a language $L \subseteq \Sigma^* \cup \Sigma^\omega$ is $\omega$-computable (non-standard terminology) if there exists a Turing machine which halts on all inputs, and accepts exactly the strings in $L$. We say that $L$ is $\omega$-r.e. if there exists a Turing machine that accepts the strings in $L$, and never halts on strings not in $L$.

Under this definition, the language $\Sigma^*$ consisting of all finite words is not $\omega$-computable (as we show below), but is $\omega$-r.e. (exercise). It then follows that $\Sigma^\omega$ is not $\omega$-r.e., and in particular not $\omega$-computable (though we can show the latter directly).

Suppose that $T$ is a machine which halts on all inputs and accepts $\Sigma^*$. In particular, it halts on $\sigma^\omega$, where $\sigma \in \Sigma$ is arbitrary. Suppose that it halts after $N$ steps, at the rejecting state $s$. Then $T$ also halts on $\sigma^N$ (exercise), at the same state $s$, thus rejecting the finite word $\sigma^N$.

The same proof also shows directly that no Turing machine accepts $\sigma^\omega$.


It seems that the missing piece here is that the switching does not only occur when a process completes.  The switch will occur when either 1) the process completes, or 2) when the process explicitly yields its remaining run time slice (whatever it has not used of its time quantum), or 3) when the OS pre-emptively interrupts the process due to that process having been running for all of its assigned time quantum.

The OS is responsible for allowing all the processes that need to get 'OnProc' (on processor) some time to actually be running on a processor.  The scheduling algorithm is what determines how "fair" the choice of which process next gets to run on a processor is.  Note that technically all of the above really should have the word 'process' replaced with the word 'thread' (of which a single process may have many, and also not all threads necessarily have a process associated with them)

As for what the impact is on the OS - that is a question that needs more definition.  I can say that other than the scheduler threads and timers and interrupts, generally all threads are subject to the scheduler so the OS will be impacted by the choice of algorithm.


Problems in P with provably faster randomized algorithms

Polynomial identity testing admits a randomised polynomial time algorithm (see the
Schwartz-Zippel lemma), and we currently don't have a deterministic
polynomial time or even a sub-exponential time algorithm for it.

Game tree evaluation Consider a complete binary tree with $n$ leaf nodes each
storing a 0/1 value. The internal nodes contain OR/AND gates in alternate levels.
It can be proved using adversary argument that every deterministic algorithm
would have to examine $\Omega{(n)}$ leaf nodes in the worst case. However there is
a simple randomised algorithm which takes has expected running time of $O(n^{0.793})$
Look at slides 14-27 of the talk.

Oblivious routing on a hypercube Consider a cube in $n$-dimensions containing
$N=2^n$ vertices. Each vertex has a packet of data and a destination that it
wants to eventually deliver the packet to. The destination of all the packets
are different. Even for this, It has been proved that any deterministic routing strategy would take $\Omega{\big(\sqrt{\frac{N}{n}}\big)}$ steps. However, there is a simple
randomised strategy which will finish in expected $O(n)$ steps with high probability.

Note that in randomised algorithms, the expected cost $E(F(n))$ with high probability (like for eg. $Pr[F(n) > 10 \cdot E(F(n))] < \frac{1}{n^2}$) is
equivalent to worst case in practice.


Proving that the halting problem is not Turing-reducible to the acceptance problem for Turing machines

The two problems are equivalent up to many-one reductions.

Reducing $\mathrm{Halt_{TM}}$ to $A_{\mathrm{TM}}$. Given a Turing machine $M$ and an input $w$, let $M'$ be the machine obtained from $M$ by marking all rejecting states as accepting. Then $\langle M,w \rangle \in \mathrm{Halt_{TM}}$ if $\langle M',w \rangle \in A_{\mathrm{TM}}$.

Reducing $A_{\mathrm{TM}}$ to $\mathrm{Halt_{TM}}$. Given a Turing machine $M$ and an input $w$, let $M'$ be the machine obtained from $M$ by getting to an infinite loop at every rejecting state. Then $\langle M,w \rangle \in A_\mathrm{{TM}}$ if $\langle M',w \rangle \in \mathrm{Halt_{TM}}$.


Split in AVL tree with complexity $O(\log n)$

Yes, this is possible.

You can read about it in Ramzi Fadel and Kim Vagn Jakobsen's "Data structures and algorithms in a two-level memory", section 3.1.6, (mirror) or in the OCaml standard library, at the "split" function.

One of the key insights is that the merge function you mention is, with more careful accounting, $O(h_1 - h_2)$, where $h_1$ is the height of the taller tree and $h_2$ is the height of the shorter tree. As such, merging a list of trees that have descending or ascending heights costs only $O(h_{\max} - h_{\min})$, since the sum telescopes.


What textbooks does the course recommend? I like "Probability and Computing" by Mitzenmacher and Upfal and "Randomized Algorithms" by Motwani and Raghavan. They introduce the necessary theory from an algorithms viewpoint. I also recommend a book on inequalities, as bounding things is quite essential to the analysis of randomized algorithms. At the very least this cheat sheet.


In this context, the line means $f(n) = O(n^{\log_b a - \epsilon})$ for some $\epsilon > 0$.

More generally, there are a few possible interpretations. Under one interpretation, $f(n)$ is at least polynomially smaller than $g(n)$ if $f(n) = O(g(n)/n^\epsilon)$ for some $\epsilon > 0$; and $f(n)$ is at most polynomially smaller than $g(n)$ if $f(n) = \Omega(g(n)/n^\epsilon)$ for some $\epsilon > 0$.

A different interpretation has $f(n)$ at least polynomially smaller than $g(n)$ if $f(n) \leq g(n)^{1-\epsilon}$ for some $\epsilon > 0$, and at most polynomially smaller than $g(n)$ if $f(n) \geq g(n)^\epsilon$ for some $\epsilon > 0$.


Recommendations for a good (rigorous) text to study Computational Complexity.

Following are my recommendations:

Introduction to Theory of Computation by Michael Sipser. It is an introductory book. Although proofs are complete and not hand waving, but not much maths is needed as a pre requisite. Although Turing machines are covered nicely.
Complexity and cryptography by Talbolt and Welsh. In this book little math background is required. Turing machines is not covered in much details. But the book gives proofs for almost all theorem's it introduces.
From my experience ( as I am a beginner myself ) Sanjeev Arora and Boaz Barak is the most concise with covering advanced topics like quantum computation etc. Although I think you should have a back ground in probability, number theory to read the part I of the book intended to be for undergraduates, as the book leaves some proofs upto the readers. Again for number theory the book I find readable as ( as there is no pre requisite ) :
Number theory by Willian Stein.


Computational complexity based in the input size

Let the length of the input (in bits) be $n$ and let the number represented be $m$.  We have $n \approx \log_2 m$ (that's how many bits it takes to write down the number $m$) so $m\approx 2^n$.


What is growth of $\psi_q(m) = \min \{ p: m ∣ (q^p−1) \}$ for fixed $q$?

Bottom line: I expect the answer to be $\psi_q(m) = O(m)$, and this to be approximately tight: I don't expect you to be able to prove any significantly better upper bound on $\psi_q(m)$.

Basically, $\psi_q(m)$ is the order of $q$ in the multiplicative group of integers modulo $m$, i.e., in $(\mathbb{Z}/m\mathbb{Z})^*$.  In other words, it is the smallest natural number $p$ such that $q^p \equiv 1 \pmod m$.

The structure of $(\mathbb{Z}/m\mathbb{Z})^*$ is well-characterized: for instance, when $m$ is prime, it is cyclic of order $m-1$.  As a consequence, $\varphi(m-1)$ of the elements of this group will have order $m-1$ (where $\varphi(\cdot)$ denotes Euler's totient function).  It's known that the typical value of Euler's totient function $\varphi(r)$ for a random value of $r$ near $N$ is about $6N/\pi^2$, i.e., $\Theta(N)$; so heuristically we can expect that the typical value of $\varphi(m-1)$ will be $\Theta(m)$ (roughly some constant times $m$).  See, e.g., this summary on Wikipedia.

In particular, when $m$ is a random prime, close to half of all elements of $(\mathbb{Z}/m\mathbb{Z})^*$ have order $m-1$: or to say this in a more careful way, we should expect that a constant fraction of group elements will have order $m-1$.  This means that, for a randomly chosen element of $(\mathbb{Z}/m\mathbb{Z})^*$, the average order will be $\Theta(m)$.  Of course, $q$ is not a random element -- it is a fixed number -- but as $m$ gets large, we can heuristically treat $q$ as a  random element of $(\mathbb{Z}/m\mathbb{Z})^*$.

Moreover, the primes are relatively dense among all the integers.  (And even for a random composite, I think the same is still true: a randomly chosen element of $(\mathbb{Z}/m\mathbb{Z})^*$ will have expected order $\Theta(m)$.)

Therefore, heuristically, I think $\psi_q(m) = O(m)$ is about the best bound you're going to be able to get.  This entire argument is based upon heuristics and is not something I can prove formally, but I think it should give an estimate that's good enough for evaluating the running time of your algorithm.


The meaning of $S$ and $\Sigma$ is defined on slide 6. $S$ is a set of base types (for example, natural numbers $\mathbb N$, Booleans $\mathbb N$, etc.): these are just formal symbols. $\Sigma$ is a set of operators, which included constants and functions (for example, $0 : \mathbb N$, $\text{true} : \mathbb B$, $\text{not} : \mathbb B \to \mathbb B$, etc.): these are pairs of an element of $S$ and a formal symbol. In the definition on slide 7, they seem to be limiting the operators to just constants.

The mapping $⟦-⟧ : S \to \mathrm{Ob}(\mathcal C)$ gives us an interpretation of a base type in the category $\mathcal C$: given any type $A \in S$, we have an object $⟦A⟧ \in \mathcal C$ interpreting that type.

They overload notation and also define a function $⟦-⟧: \Sigma \to \mathcal C^\to$. We interpret each constant $(c : A) \in \Sigma$ as a morphism $⟦c⟧: 1 \to ⟦A⟧$, where $1$ is the terminal object (called $\star$ in the lecture slides). This aligns with the usual interpretation of terms $\Gamma \vdash t : A$ as morphisms $⟦t⟧ : ⟦\Gamma⟧ \to ⟦A⟧$.

Together, both of these mappings $⟦-⟧$ allow us to interpret a signature for a simply-typed $\lambda$-calculus inside a cartesian-closed category, which is the first step in showing the equivalence between simply-typed $\lambda$-calculi and cartesian-closed categories.


I would use a SAT solver.  Use one boolean variable per edge to encode whether that edge is present or not.  Encode the type of a node via a one-hot encoding ($k$ variables per node, where $k$ is the number of possible types).  Then each constraint you mention should translate directly into a simple formula on a few of these boolean variables.

I like Z3 for ease of programming.

I see no reason nor benefit to using bitvectors or SMT; plain SAT should suffice.


3SAT solvable in polynomial time...but with exponential tuning?

If the tuning parameters depend on the entire input, then it's not a self-contained algorithm, so it says nothing about whether 3SAT is in P.

After all, I can give you an algorithm that has that property: in my algorithm, the 'tuning parameter' for a 3SAT formula $\varphi$ is 0 or 1, according to whether the formula $\varphi$ is satisfiable or not.  My algorithm ignores the formula on its input and just outputs its tuning parameter.  Sure, it may take exponential time to find the right tuning parameter for any particular formula, but once you've got it, my algorithm can output the right solution in polynomial time -- in fact, in just $O(1)$ time.  Yet this says nothing about whether 3SAT is in P or not.


You're right, minimum distance is the minimal nonzero weight, thus 1.

A basis is what you gave. There are many bases. And youre right on size and dimension as well.

Edit: As pointed out in the other answer the distance is 2 if $n=2.$


How to design a finite state machine to detect 0110 in the input?

It looks like you're missing the overlap case, if I understand your diagram correctly.  This does the trick:

A    // goto B if read 0 else stay
B    // goto C if read 1 else stay
C    // goto D if read 1 else goto B
D    // goto E if read 0 else goto A
E    // emit rising edge, goto B

assuming that you have a falling edge after every read.


Inference rules are "more general". A recursive equation, actually any equation $E_1 = E_2$ is like an inference rule without premisses:
$$\frac{}{E_1 = E_2}$$
A general inference rule may have premisses, and so it is like a conditional equation.
Only very special kinds of inference rules may be equivalently expressed as equations. For instance, it seems difficult to express
$$\frac{a \bullet c = b \bullet c}{a = b}$$
and
$$\frac{add(x,add(y,z)) = add(x,z)}{add(y,z) = z}$$
as equations.


Computing the intersection of N sets over an M-element universe

Usual method is you sort all the sets, and select common elements by looking at the beginning of each sorted sequence. This gives you $O(NM)$ algorithm if you do bucket sort. Or in the bucket sort step itself you may check if all the sorted sequence has common elements by doing an operation AND on the bits.

There is even better algorithm that runs in $O(\Sigma_{i=1}^N |S_i| + M$ (i.e. $O(n+M)$) if sets are not multisets (which is the case here). Let $V[1..M]$ be a zero vector. For each $i \in 1..N$, for each $x \in S_i$ do  increment $V[x]$. Select those $x$ for which $V[x] = N$. (Note: For multisets also we can do something similar, but we need to do some housekeeping to ensure that we increment only once for a particular element $x$ in a set $S_i$ even if it occurs multiple times.)

If the elements of each sets are already stored in efficient search data structure they you can do it another way. This also works if you have domain as general values rather than values from $Z_M$. You take the smallest sized set $S_{min}$ and select elements from $S_{min}$ one by one by checking if it belongs to every set $S_i$ in time $O(\log |S_i|)$. This gives you $O(N\cdot
|S_{min}|\cdot \log(|S_{max}|))$-time algorithm, where $S_{max}$ is the largest set, and which might be better than $O(NM)$ if smallest and largest sets are small enough.


Why checking if tuple belongs to join of two tables is NP-complete?

If the claim is:

  for instance, given a join query $Q$ and a relational database $D$, checking if $Q(D)$ returns a tuple is NP-complete as well

the NP-completness is about the decision if that join operation returns an empty set or not (for instance because the join condition is not satisfied by any pair of tuples).

So, if this hypothesis is true, the claim is not, as you are asserting, about the fact that a certain tuple belongs to the result or not (for instance this could be checked by verifying that the tuple satisfies the join condition).


Choosing a shortest representative number from interval in arithmetic coding

While you are encoding symbols between the ranges, you are not choosing which to use for the specific symbol. You are narrowing down the possible chooses there are.  You can arbitrarily choose them per symbol, but how would you adjust the ranges to make that the actual choice. It is true that the LAST symbol you can make a choice to make it fit within the rounding error , so long as it is within the range for that symbol.

The point of the example was that the incorrect distribution gives poor or worse compression. Choosing a better statics gives better results.  Hoffman encoding is at most within 1 bit per symbol of encoding, where arithmetic coding is within a fraction of a bit per-symbol, if the correct statics are used.  You can choose how accurate you do the encoding. Increasing the length of the RANGE's precision allows for more accurate representation of the given statics, thus  less error.   Choosing the wrong distribution for the specific message, regardless of the how accurate the encoding process is will get very poor compression or make it larger than the original message.  So.. think of it is an error rate.  The smaller you can make the error rate the, closer to the real limit you can achieve.  choosing a "static" distribution for all text files, will never give you the smallest compressed file this specific method can give you.

JUST A NOTE: "Optimum" is misunderstood. It simple means that the best a specific method can be.  Not that it is the highest compression available.


Interpretation of an asymptotic notation

What this means is:

  For every algorithm solving the problem, it is not the case that the worst-case running time $T(m,n)$ in terms of $m,n$ satisfies the following property: for every $c > 0$ there is $m_0(c)$ such that for all $n \geq m \geq m_0(c)$,
  $$ T(m,n) < c(m + \log n). $$

This doesn't rule out an $O(\log n)$ algorithm, since $\log n$ doesn't satisfy the property written above.


Which measure of sortedness explains the phase transition in Quicksort's runtime?

Inversions are one way to measure "disorder" in a list:

  Let $A[1..n]$ be an array of $n$ distinct numbers.  If $i < j$ and $A[i] < A[j]$ then the pair $(i,j)$ is an inversion of $A$.

However, it's not the only such measure. In general, this concept is formalized in the notion of presortedness - roughly:

  An integer function on a permutation $\sigma$ of a totally ordered set that reflects how much $\sigma$ differs from the total order.

The survey papers by Mannila [1] and Estivill-Castro & Wood [2] might be good places to start.

The question How to measure "sortedness" is related.

[1] Heikki Mannila. "Measures of Presortedness and Optimal Sorting Algorithms." IEEE Transactions on Computers 34.4 (1985): 318-325.

[2] Estivill-Castro, Vladmir, and Derick Wood. "A survey of adaptive sorting algorithms." ACM Computing Surveys (CSUR) 24.4 (1992): 441-476.


Kosaraju's Algorithm-Strongly connected components

What separates theoretical computer science from more applied areas within computer science is the notion of proof. If an algorithm claims to do something, we want proof that it does so, preferably a mathematical proof. (In rare occasions, experiments are also accepted.) We work under the maxim an algorithm doesn't work unless it is proved to work, whereas you seem to be working under the maxim an algorithm works unless we can find a counterexample.

For these reasons, I don't find it a good use of my time to find a counterexample. If you did want to find a counterexample yourself, there are several things to try. First, you can try a few random graphs; often this works. Second, you can try to concoct a parametric situation and determine parameters that defat your algorithm; this seems harder to apply in your case since your edges are not weighted, and so the parameters are too discrete. Third, you can try to prove that your algorithm works, fail at some step, and produce a counterexample as part of the process. Fourth, you can play with your algorithm on several graphs until you get an intuitive understanding of what it does, and given this understanding try to construct a counterexample. Fifth, if you really believe that the algorithm doesn't work but can't use any of the preceding method, treat it as a research project and use your research skills to construct a counterexample.

Kosaraju's algorithm is that way that it is for a reason. If a simpler or more intuitive algorithm worked, probably by now people would have discovered it, and it would be known. The fact that we still teach Kosaraju's algorithm suggests that similar but simpler algorithms don't work. That's why I'm pretty sure that your algorithm doesn't work, even without reading it. Of course, I can be wrong. To prove me wrong, all you have to do is to prove that your algorithm works.


What is the type of linked list where order doesn't matter

I took a look at the book you are referencing, and it does appear that Steven Skiena made an unordered Dictionary implemented as a linked list.  It's not a terribly efficient data structure, but he was only using it to illustrate basic linked list coding techniques, so I expect he just wanted to keep things as simple as possible.

For what it's worth, a stack is a container that only allows you to add to or access from the very top item, which isn't really index based in the way we'd usually use that term.  I mention this only to highlight that Containers do not need to have index-based retrieval.


Based on your comments, I'm assuming that if the problem asked to find all paths between $A$ and $B$ on a directed graph, you'd have no problem.  So the only hurdle is how to deal with the extra route information.
Here's an outline of the most obvious approach that I can see:

Convert the given set of routes to an adjacency matrix. Since each edge $(A,B)$ belongs to some route $R$, store that route in the corresponding entry for $(A,B)$ in the matrix.
Run your algorithm to find all paths between your start and goal nodes.
Convert the output of your algorithm to the desired form by collapsing all consecutive edges that belong to the same route into one edge.


If you want to look for an exact match, use a hashtable.  Choose a hash function that hashes a 10,000-bit string to a short hashcode.  This approach will be simple and highly efficient: the running time will basically be the time to compute the hash of the 10,000-bit value that you are searching for.


Searching the best trading route - algorithm

This problem is NP-Complete by reduction from Directed Hamilton Path. I use the method of the linked mathoverflow answer. Let's say $b(v)$ and $s(v)$ is the good that villager $v$ buys and sells, respectively (each villager only buys/sells one good). Then you may ask, what dealers can I visit consequtively? This is the following graph:

$$G = \langle \text{Villagers}, \{ (\sigma, \beta) | s(\sigma)=b(\beta) \rangle $$

This directed graph has an edge from $\sigma$ to $\beta$ iff $\sigma$ sells something that $\beta$ buys (using the letters $\sigma$ and $\beta$ because they sound like 's' and 'b' for seller and buyer). In this graph, you are one node called $y$ and you have a good, $s(y)$, which you want to sell. You can verify that you are looking for a route through $G$. How much profit do you make? If $\$_b(v)$ and $\$_s(v)$ are the buying and selling price of villager $v$'s goods, and you travel some route $v_1\cdots v_k$ through the village, then your profit is: (w.l.o.g. assume that you start with $1$ unit of your good)

$$ \text{Profit}(v_1\cdots v_k) = \prod_{i=1}^{k}\frac{\$_s(v_i)}{\$_b(v_i)}$$

This suffices for a reduction from Directed Hamilton Path: Take a directed graph $H=\langle V, E \rangle$, and say you want to find out whether there is a Hamilton Path starting in vertex $x$. Suppose that the $n$ vertices are villagers. Each villager $v_i$ trades his own good for his own good at a $1/1$ ratio. Now populate the village further as follows. For each edge $(\sigma,\beta)\in E$ in the graph, add a "stockbroker" villager called $\tau_{\sigma,\beta}$ who buys $\sigma$'s goods and sells the goods that $\beta$ buys at a rate of two units of $\beta$ for each unit of $\sigma$. That is, $b(\tau_{\sigma,\beta})=s(\sigma)$ and $s(\tau_{\sigma,\beta})=b(\beta)$ at $\$_b(\tau_{\sigma,\beta})=1$ and $\$_s(\tau_{\sigma,\beta})=2$. In this scenario, you are villager $x$.

If your profit problem were easy, then you could ask 'Is there a route from $x$ which makes  $2^{n-1}$ profit?' Iff there is such a route in the graph I constructed, then there is a Hamilton Path in the graph I constructed it from. $\square$

So this problem is NP-Complete and in fact it is hard even to approximate. Instances of the problem that are not contrived are probably more difficult. You can also make an elegant reduction from Traveling Salesman by assigning to each villager a profit $\varepsilon(v_i)=\log\left(\frac{\$_s(v_i)}{\$_b(v_i)}\right)$, I'll leave the details up to you. If you really mean to solve this problem practically, you can look for some advice in this question here (link) and in the extensive literature on TSP and related problems. Personally, I would use a greedy algorithm which looks ahead some fixed number of steps, say $3$ steps. Or you can use an evolutionary approach, which should work just fine, too.

Here's one heuristic: given a candidate solution $v_1\cdots v_k$ computed by an evolutionary algorithm, you can check the intermediate profits halfway along the route, and quickly find the point at which you should have stopped. Fix only the last part of the path $v_j\cdots v_k$.


Write a routine to print the numbers 1 to 6 and back to 1 again without using any loops

public class Foo {
    public static void main(String[] java_is_silly) {
        System.out.print("1 2 3 4 5 6 5 4 3 2 1");
    }
}


Automaton-based model checking on finite traces

The nice thing about finite traces is that they end at some point. LTLf is now a logic in which you can only look into the future, and not in the past.

This means that you label every character in the word by which subformulas of your LTLf formula hold for a word starting from that character. You start with the last character and just apply the semantics of LTLf there. Then you do the same for the second-last character, where you can use the fact that for the last character, you already know which LTL subformulas hold.

And then you continue in this way until you hit the first letter. Once you are done with that, you know for all subformulas if they hold there. You just have to look at the whole formula as subformula and are done.


Here is the complete proof:

reverse(append(Cons(w,ws),z)) =
reverse(Cons(w,append(ws,z))) =
append(reverse(append(ws,z)),w) =
append(Cons(z,reverse(ws)),w) =
Cons(z,append(reverse(ws),w)) =
Cons(z,reverse(Cons(w,ws)))

At one point we used the inductive hypothesis.


Does simultaneously finding max/min in array of coordinates by x and y increase comparisons?

does this double the amount of comparisons or can I still claim it’s $O(3n/2)$?

You misunderstand the big $O$ notation.

Even if you double or quadruple the amount of comparisons, you can still claim it is $O(3n/2)$. That is, the amount of comparisons as a function of $n$ is asymptotically not bigger than $3n/2$.  The very purpose of big $O$ notation is to hide a constant factor so that it becomes clearer what is the asymptotic picture. In fact, $O(3n/2)$ = $O(n)$. When I write "=", I mean equality. That is, the left hand side and the right hand side represent exactly the same set of functions.

Here is what you could say.

If I use this method to find the min/max for the left/right box boundaries and then use the same algorithm to find min/max of y for the top/bottom boundaries, I will use $2(\lceil 3n / 2\rceil - 2) \le 3n -3$ comparisons. That is, I will use $O(n)$ comparisons.


what is the relevance of computability when applying diagonallization?

There are no catches. Diagonalization is a very general proof technique that works in classical, constructive and computable setting. It is used to prove:

that there is no surjection from a set to its powerset
that the real numbers cannot be enumerated
that the computable real numbers cannot be computably enumerated
that the Halting oracle does not exist
etc.

In its most general form it is known as Lawvere's fixed-point theorem.
You ask what happens if you diagonalize against the rational numbers. You did not specify in what form the rationals are given, I am assuming you mean their decimal expansions. The diagonalization will produce a real number which is not a member of the enumeration (this real may be rational or irrational, depending on what enumeration you started with). If you start with a non-computable enumeration, the result may be non-computable. If you start with a computable enumeration, you will get a computable result, because diagonalization preserves computability.
Likewise, if you take a computable enumeration of computable real numbers (given as infinite sequences of digits), the result of diagonalization will be a computable real number which is not a member of the starting enumeration.


Maximum I/O Data Transfer if DMA is used

After reading more about it and reading the question again and again, I understood the logic

  The question says that on an average an instruction requires $5$
  $cycles$ and the CPU is busy $95$% of the time in executing those
  instructions. Out of these $5\ cycles$, $3\ cycles$ are needed for memory operations. During this time $DMA$ cannot access the memory.

So only $2\ cycles$ are left for $DMA$ to use for 95% of the time.
For 95% time DMA uses
$$0.95 * 2\ cycles$$

For rest 5% time, CPU isn't executing instructions, so all cycles are available, so DMA uses
$$0.05 * 5\ cycles$$

Total cycles available for DMA
$$(0.05 * 5 + 0.95 * 2)\ cycles$$

In $1 second$, CPU can execute  $10^6$ instructions. So rate of transfer is

$$
10^6 * (0.05 * 5 + 0.95 * 2) = 2.15 * 10^6
$$


We first choose an alphabet of symbols that our Turing machines can read and write on the tapes. Typically we have three symbols: $0$, $1$, and "empty". A word is a finite sequence of symbols.

If $u$ and $v$ are words we can form a new word $\langle u, v \rangle$ which represents the two words put together (this requires some coding so that we can tell where one words stops and the other begins).

A Turing machine can be be described by a word.

Like in all decidability problems, $H_{TM}$ is a set of words. More precisely, $H_{TM}$ contains all those words of the form $\langle M,w \rangle$ where $M$ is a Turing machine, $w$ is any word, and $M$ halts when we run it with input $w$.


What's the purpose of ANDing a bit mask with all bits set to a value?

The reason is crc that it's calculating is defined to be a 16-bit value, the And &HFFFF will truncate the most significant bit outside the 16-bit range if there is any overflow during the calculation.


How many knights can be placed on an n-by-m chessboard?

For an 8*8 chess board,

You need to observe that when 2 knights beat one another they lie on cells of different colors.
We can generate a solution by placing 32 knights in the 32 white cells so that no 2 knights beat each other.
To prove that this is the optimal solution, we can group our rows into pairs (1,3),(2,4),(5,7),(6,8). Let us consider the row pair (1,3). Consider the pairs of cells (R1C1,R3C2) and (R1C2,R3C1). We can see that we can place only 1 knight in the cell pair (R1C1,R3C2) and only 1 knight in the cell pair (R1C2,R3C1). Continuing this idea, we can show that we cannot place more than 32 knights in an 8X8 chessboard.
We already have an arrangement of 32 knights from point 2. Hence, the solution described in point 2 is optimal.

Expanding the above idea, below are the maximum no. of knights that can places such that no 2 beat each other on any N*M chessboard.

If both N and M are odd, then the solution is ((N*M)+1)/2
If either N or M is even, then the solution is (N*M)/2


Showing that Bayes classifier is optimal

The true error of a classifier $h$ is
$$
\begin{align*}
L_D(h) &= \sideset{\mathbb{E}}{}{}_{x,y \sim D} \Pr[h(x) \neq y] \\ &=
\sideset{\mathbb{E}}{}{}_{x,y \sim D}
\begin{cases}
\Pr[y \neq 0|x] & \text{if } h(x) = 0, \\
\Pr[y \neq 1|x] & \text{if } h(x) = 1.
\end{cases}
\end{align*}
$$
(All probabilities are with respect to $D$.)

The optimal classifier is thus the one that minimizes the loss function
$$
\phi(x) = \begin{cases}
\Pr[y \neq 0|x] & \text{if } h(x) = 0, \\
\Pr[y \neq 1|x] & \text{if } h(x) = 1
\end{cases}
$$
for all $x$. We can rewrite the loss function as
$$
\phi(x) = \begin{cases}
\Pr[y = 1|x] & \text{if } h(x) = 0, \\
1-\Pr[y = 1|x] & \text{if } h(x) = 1
\end{cases}
$$
So if $\Pr[y=1|x] < 1-\Pr[y=1|x]$ we should choose $h(x) = 0$, and if $\Pr[y=1|x] > 1-\Pr[y=1|x]$ we should choose $h(x) = 1$; if $\Pr[y=1|x] = 1-\Pr[y=1|x]$ then the choice doesn't matter.

Finally, $\Pr[y=1|x] < 1-\Pr[y=1|x]$ is the same as $\Pr[y=1|x] < 1/2$, and this explains the formula for $f_D(x)$.


Context Free Grammar for Try-Catch-Finally Statement and Throw

You need more terminals, for the reserved words try, catch, finally, and throw, and possibly for braces and for semicolon (depending on the interpretation of Statement).

Here is an example to help you get started. It gives the syntax of a simple if statement, assuming that Statement also includes compound statements (i.e. { ... }), and that statements do not end in a semicolon.

IfStatement → if ( Expression ) Statement


Does there exist any work on creating a Real Number/Probability Theory Framework in COQ?

The standard library of Coq has a section about real numbers. These are the classical real numbers, using the Dedekind completion. There are also results about complex numbers, I suppose there are several libraries, I happen to know this one. Note that there is also a lot of results for constructive real and complex numbers, C-CoRN is the reference.

Side note: you could also define (computable) real numbers inductively with some of the constructive axiomatics, for example using rational numbers from the Cauchy sequences or some constructive version of the least-upper-bound property. I am not sure how much inductive that this.

I know there are some people working on probabilities with Coq. Unfortunately I am not sure how advanced their works are. My guess is that there is likely no such specific result about Chernoff bound or union bound. (But it's just a guess)