Why Instruction Decode and Register Read are in the same stage of MIPS pipeline

Instruction Decode and Register Read are done in parallel on that stage in order to prevent needing to wait on either to complete.  There's no reason not to do this since they are both known at that point in time for the MIPS-Pipeline, and since they will most likely be needed for the next step (Execution Cycle).

By "no reason", I mean that you would effectively be using more power while separating them (as mentioned in the comments below).  You would also be adding a whole extra stage in that case, as the stage before (Instruction Fetch) is what actually gets the information for ID and RR, and adding it to the stage after would not work because that stage requires both.  Thus the only way to do it would be to add the stage in-between the ID stage and EX stage, which would add a whole extra cycle to every operation, which would obviously result in slow downs overall.

If you're interested in reading more about this, I'd recommend this textbook I'm using for a class (Computer Architecture: A Quantitative Approach by John Hennessy and David Patterson).  It's got a pretty handy reference for MIPS especially from what I've read so far and it's where I pulled this information from.


Given n distinct numbers show that the second smallest element can be found in n + lg n - 2 comparisons in the worst case

The algorithm with $n + \lceil \lg n \rceil -2$ comparisons uses "tournament" (lecture note from utdallas).

To form a tournament tree: Compare $A[2i−1]$ with $A[2i]$ for $i = 1$
to $n$. We compare the "winners" in pairs and so on.
Collect all the keys that directly lost to the maximum and compute their maximum. That is, the second largest key.

The time complexity is $(n-1) + (\lceil \lg n \rceil - 1) = n + \lceil \lg n \rceil -2$.

Actually, the lower bound for "finding the second largest/smallest element" is $n + \lceil \lg n \rceil -2$, which can be proved by adversary argument (at the end of the lecture above).


Time complexity of $\sim c \cdot n^3$ with a computer which is 10 times faster

You've correctly reasoned that the additional speed doesn't change the $n^3$ part of the tilde expression. The only component left for it to effect then is $c$.

Let $c_1$ be the constant of the first computer and $c_2$ the constant of the second. If the second computer is 10x faster, then $c_2 = c_1/10.$ Now, all you need to do is solve the following equation:

$$c_1 \cdot n^3 = \frac{c_1 \cdot n'^3}{10},$$

which gives the same answer you came up with!


How to find efficiently the minimum modification to avoid close consecutive numbers?

Here is an algorithm that returns the minimum amount of elements that need to be modified. It is about as simple as possible and as fast as possible. Its time complexity is $O(n)$, where $n$ is the size of input array.

def minimize(arr, threshold):
    size = len(arr)

    # keep[i] or modify[i] is the minimal number of modification
    # needed on arr[0:(i+1)], keeping or modifying the i-th
    # element respectively, so that any two consecutive numbers
    # in arr[0:(i+1)] are greater than `threshold` apart.
    keep = [0] * size
    modify = [0] * size

    for i in range(1, size):
        modify[i] = min(keep[i - 1], modify[i - 1]) + 1

        if abs(arr[i] - arr[i - 1]) >= threshold:
            keep[i] = min(keep[i - 1], modify[i - 1])
        else:
            keep[i] = modify[i - 1]

    return min(keep[-1], modify[-1])

The criticall observation is that if a number at a certain index has been modified, we can consider it has been modified so wildly it will be more than threshold away from any of its neighbours, whether those neighbours will be modified or not.


Is it possible that the universe of types could be closed?

I'm uncertain what you're referring to exactly, but I can remark on a few things.

The first is that the usual problem with W-types is that encoding inductive types with them does not necessarily give you the right induction principles. For instance, we can try to define the natural numbers like so:

F : 2 → Type
F 0 = ⊥
F 1 = ⊤

ℕ : Type
ℕ = W 2 F

zero : ℕ
zero = sup 0 absurd

suc : ℕ → ℕ
suc n = sup 1 (const n)

induction : (P : ℕ → Type) → P zero → (∀ n. P n → P (suc n)) → ∀ n. P n
induction pz ps n = ???

The problem we'll run into is that induction on $W$ and $2$ allows us to observe the case $n = {\tt sup}\ 0\ f$, but we only have a proof of $P\ ({\tt sup}\ 0\ {\tt absurd})$. So we'll need a way to prove that $f = {\tt absurd}$, but there is no such principle in normal intensional type theory.

The answer to your question in this regard is that homotopy type theory does help in this regard, because e.g. univalence implies extensional equality of functions (and cubical type theory also includes this, for instance). So we should not have as many problems recovering the 'right' induction principles for $W$ based encodings.

However, another answer is that we didn't actually need this to begin with. This problem is somewhat particular to the specifics of $W$. Instead, we could use a more complex type of 'descriptions' of inductive definitions together with a decoding to a more 'first-order' representation of the container functor used in the $W$ definition. This approach is used in The Gentle Art of Levitation, which says it does not require extensional equality of functions (I believe).

This technique is also detailed in Ambrus Kaposi's thesis, which shows what sort of codes you need for inductive-recursive and inductive-inductive definitions.

The (I think) counter-intuitive bit about these systems is that they seem to actually be capable of describing themselves, and that this is not (it seems) contradictory.

So, it seems like we are relatively close to knowing how to to include most (commonly desired) definitions in type theory as a universe of descriptions with a 'decoding' function, instead of taking some universes to be open with respect to special definition forms. And this fact is somewhat independent of any features that homotopy type theory would have. I don't know of any system like Agda or Idris has this methodology on their roadmap, though.

I should say, there are potential traps, still. For instance, each universe Set i in Agda is called "Mahlo," because it admits inductive-recursive definitions. There are stronger universes known than Mahlo universes, too, which will in turn have (many) Mahlo universes within them. But the sort of 'universe' you define with induction-recursion cannot be Mahlo, because it is inconsistent for a Mahlo universe to have an induction principle. So any theory incorporating strong-than-Mahlo universes would at least need a different sort of 'description' system for those.


Are models of computation closed under composition?

Given that, I would expect that for any reasonable model of computation, if $f : A \rightarrow B$ and $g : B \rightarrow C$ are computable, then $g \circ f : A \rightarrow C$ should be as well.

Let's say our model is quadratic time computation. If $f$ is the function which maps a string of length $n$ to a string of $n^2$ zeroes, then $f$ is computable in our model, but $f\circ f$ is clearly not.

  I'd expect that if $L_f = \{(a, b) \in A \times B : f(a) = b\}$ and $L_g = \{(b, c) \in B \times C : g(b) = c\}$ are decidable, then $L_{g \circ f} = \{(a, c) : \exists b \in B s.t. f(a) = b \wedge g(b) = c\}$ should be decidable as well.

This is a bit of a weird definition since $L_f$ can be much easier than $f$ (e.g., let $f(a)$ be the function that outputs a prime factorization of $a$). $F_l$ is poly-time while it is not known that $f$ is. Let's make $f$ also take an additional input $i$, and then let $f(a,i)$ output the number $i$ together with a factorization of $a$. If we then make $g$ output the $i$th bit of the factorization we end up with $L_f$ and $L_g$ being poly-time computable but $L_{f\circ g}$ being as hard as factorization.


Suppose your stack alphabet is $\Gamma =\left\{Z_0,X\right\}$. You can eliminate transitions which don't pop stack, by guessing which stack symbol is at the top. like this:

before:
$(a,\epsilon)/XXX$

after:
$(a, X)/XXXX$, and
$(a, Z_0)/XXXZ_0$


P vs NP and can an oracle make P=EXPTIME?

First let me try to be a bit more precise about your first sentence.  The reasoning you list shows that no relativizing proof can prove or disprove P=NP.  "Diagonalization" is a fuzzy concept, and depending on what you mean by it, might or might not relativize -- diagonalization proofs tend to relativize, but no guarantees.  So the oracle result rules out some/many kinds of diagonalization proofs, but maybe not all.  See, e.g., https://cstheory.stackexchange.com/q/6575/5038.

Second, let's discuss your final question.  Yes, it is indeed true that $P^X \ne EXPTIME^X$ for all $X$; there is no oracle $X$ that will make them equal.  I'll talk through why that is.  The standard way to prove $P \ne EXPTIME$ is to prove $TIME(p(n)) \ne TIME(p(n)^2)$ (the time hierarchy theorem), then notice that this implies $P \ne EXPTIME$ (since $TIME(2^n) \ne TIME(2^{2n})$, but $P \subseteq TIME(2^n)$ and $TIME(2^{2n}) \subseteq EXPTIME$).  The proof of $TIME(p(n)) \ne TIME(p(n)^2)$ uses diagonalization.  This proof does indeed relativize.  In particular, for all oracles $X$, we do indeed have $TIME^X(p(n)) \ne TIME^X(p(n)^2)$.  It follows that, for all oracles $X$, we have $P^X \ne EXPTIME^X$ (by the same argument as before).

See also: https://cstheory.stackexchange.com/q/8902/5038, https://cstheory.stackexchange.com/q/6575/5038.


Circles covering a rectangular, how to verify it?

Create a Voronoi diagram on the $n$ disk centers in $O(n\log n)$ time. Intersect it with the rectangle in $O(n)$ time.

Now you have a set of convex shapes, thus the furthest point away from the center of the disk inside the cell is a vertex on the cell. Compute the furthest point for each cell can be done in $O(n)$ time. If for all of them, it is within $r$, then the set of disks covers the rectangle.

A $O(n \log n)$ algorithm.


Which graph partitioning algorithm can solve this problem?

Your problem is $\text{NP}$-hard. To see why, consider the version of the 3-Partition problem where we're given multiset $ X = \{ x_1, x_2, \ldots, x_{3n}\}$ of $3n$ nonnegative integers, and we need to decide whether $X$ can be partitioned into three disjoint multisets with the same sum each. Clearly, an instance $X = \{ x_1, x_2, \ldots, x_{3n}\}$ of the 3-Partition problem can be translated in polynomial time into a complete graph $G = \langle V, E \rangle$, where $V = \{ v_i\}_{i\in [3n]}$  and for each $v_i$, we have that the weight $w(v_i) = x_i$. That is, we view the integers as $3n$ vertices, and every two vertices are connected with an edge. Obviously, a balanced 3-clustering of $G$ corresponds to an appropriate 3-partition of the multiset $X$.


Busy Beaver machines on semi-infinite tape

We look to the first approach in this answer.

Let us denote this new function by $\Sigma_{\mathrm{semi}}(n)$.

Also, call the function of the second approach $\Sigma_{\mathrm{bounce}}(n)$.

Also, denote the original Busy Beaver function by $\Sigma(n)$.

First note that $\Sigma(n) \geq \Sigma_{\mathrm{semi}}(n)$ and $\Sigma_{\mathrm{bounce}}(n) \geq \Sigma_{\mathrm{semi}}(n)$, since every program that works for semi also works for bounce and the original version.

 Uncomputability of $\Sigma_{\mathrm{semi}}(n)$

In this part of the answer, I'll prove that $\Sigma_{\mathrm{semi}}(14n+3)>\Sigma(n)$, therefore it is uncomputable. (If it were computable, then $\Sigma(n)$ would be upper-bounded by a computable function, contradiction.)

This implies that $\Sigma_{\mathrm{bounce}}(n)$ is also uncomputable.

 Definitions

Number all cells on the tape, starting with 1 for the first cell.

We call the number of the cell the index.

Group every pair of consecutive cells such that the first cell in the pair has an on the tape into one macro cell, so the tape looks like

(1,2)(3,4)(5,6)(7,8)....

 Constructing a new machine

Consider the Busy Beaver with $n$ states that leaves $\Sigma(n)$ ones on the tape with states $B_1, B_2, B_3, \cdots B_n$. We leave the new symbol and direction intact, but instead of going to a new state $B_i$, we go to $B_{i,\mathrm{left}}$ if the direction is left, and to $B_{i,\mathrm{right}}$ if the direction is right. (Exception: If the new state is $\mathrm{HALT}$, then it remains $\mathrm{HALT}$.) We construct a machine that needs additional states for each state $B_k$.

The idea of this machine is that all cells with odd index contain exactly two ones: One that is further to the right than any one in a cell with an even index, and one that is at the cell with index 1. If we read the leftmost one, we know that we are on the edge of the tape and then we move the whole tape with even index two indices to the right. Because of the rightmost one we know up to where we should move the tape. So every cell with an even index will be used for executing a normal Turing machine. The cells with odd index will be used to ensure the Turing Machine doesn't run of the tape.

Anyway, here are the states:

$B_{k,\mathrm{right}}$ (odd index): This has the following ruleset:

If it reads a zero, then we go to the right, keep the symbol a zero and go to state $B_k$.
If it reads a one, then we go to the right, make the symbol a zero and go to state $B_{k,1}$.

$B_{k,1}$ (even index): This has the following ruleset:

It doesn't change the symbol it reads and goes to the right and to state $B_{k,2}$.

$B_{k,2}$ (odd index): This has the following ruleset:

If it reads a zero, it changes this into an one and goes to the left and to state $B_{k}$.
It is not possible to read a one in this state. When the machine enters this state, it is on a cell with an odd index. However, we removed a one in state  $B_{k,\mathrm{right}}$ two steps before this, so only the leftmost one remains and we are certainly more to the right than that one.

$B_{k,\mathrm{left}}$ (odd index): This has the following ruleset:

If it reads a zero, then we go to the left, keep the symbol a zero and go to state $B_k$.
If it reads a one, then we go to the right, keep the symbol a one and go to state $B_{k,3}$.

$B_{k,3}$ (even index): This has the following ruleset:

If it reads a zero, it writes a zero and goes to the right and to state $B_{k,4}$
If it reads a one, it writes a zero and goes to the right and to state $B_{k,7}$

$B_{k,4}$ (odd index): This has the following ruleset:

If it reads a zero, it writes a zero and goes to the right and to state $B_{k,3}$
If it reads a one, it writes a zero and goes to the right and to state $B_{k,5}$

$B_{k,5}$ (even index): This has the following ruleset:

If it reads a zero, it writes a zero and goes to the right and to state $B_{k,9}$
It is not possible to read an one, because we read the rightmost one on the odd index before this cell and thus the rightmost one on the tape.

$B_{k,6}$ (even index): This has the following ruleset:

If it reads a zero, it writes an one and goes to the right and to state $B_{k,4}$
If it reads a one, it writes an one and goes to the right and to state $B_{k,7}$

$B_{k,7}$ (odd index): This has the following ruleset:

If it reads a zero, it writes a zero and goes to the right and to state $B_{k,6}$
If it reads a one, it writes a zero and goes to the right and to state $B_{k,8}$

$B_{k,8}$ (even index): This has the following ruleset:

If it reads a zero, it writes a one and goes to the right and to state $B_{k,9}$
It is not possible to read an one, because we read the rightmost one on the odd index before this cell and thus the rightmost one on the tape.

$B_{k,9}$ (odd index): This has the following ruleset:

If it reads a zero, it writes a one and goes to the left and to state $B_{k,10}$
It is not possible to read an one, because we read the rightmost one on the odd index before this cell and thus the rightmost one on the tape.

$B_{k,10}$ (even index): This has the following ruleset:

It doesn't change the symbol it reads and goes to the left and to state $B_{k,11}$.

$B_{k,11}$ (odd index): This has the following ruleset:

If it reads a zero, it leaves a zero, goes to the left and to state $B_{k,10}$.
If it reads a one, than this is the leftmost one. It leaves this one unchanged, moves to the right and to state $B_k$.

If this helps, here are informal explanations of what the states $B_{k,\mathrm{something}}$ do:

$B_{k,\mathrm{right}}$: Bring the head to the cell with the even index and notice that the rightmost one on the odd index needs to be moved.
$B_{k,1}$: Bring the head to the cell with the odd index.
$B_{k,2}$: Write the new rightmost one.
$B_{k,\mathrm{left}}$: Bring the head to the cell with the even index and notice that the tape needs to be moved.
$B_{k,3}$: Write moved zeroes on cells with even index.
$B_{k,4}$: Move the head to even index and notice the rightmost one.
$B_{k,5}$: Write moved zeroes on cells with even index after the rightmost one was noticed.
$B_{k,6}$: Write moved ones on cells with even index.
$B_{k,7}$: Move the head to even index and notice the rightmost one.
$B_{k,8}$: Write moved one on cells with even index after the rightmost one was noticed.
$B_{k,9}$: Write a new rightmost one.
$B_{k,10}$: Move to the position the head should be.
$B_{k,11}$: Move to the position the head should be and notice the leftmost one. Note that the original position where the head should have gone is one to the left of the end of the tape, so it is not one to the right of the tape.

 Initial setup for the new machine

Before we will run this machine, we will put an 1 in cell 1 and cell 3, and move the head of the machine to cell 2. So the tape looks like

(1,_)(1,_)(_,_)(_,_)....

This can be done using three states:

State 1: It reads a zero. It writes an one. It goes to the right. It goes to state 2.
State 2: It reads a zero. It writes a zero. It goes to the right. It goes to state 3.
State 3: It reads a zero. It writes an one. It goes to the left. It goes to state $B_1$, as defined above.

 Conclusion

We created a new machine with 14 states per original state and 3 states for the initial setup that simulates $\Sigma(n)$ on a semi-infinite tape. Therefore $$\Sigma_{\mathrm{semi}}(14n+3) > \Sigma(n)$$

Note that I didn't necessarily tried to optimize those constants, since I just wanted to show uncomputability.


Why are there so many programming languages?

Programming languages evolve and are improved with time (innovation).

People take ideas from different languages and combine them into new languages. Some features are improved (inheritance mechanisms, type systems), some are added (garbage collection, exception handling), some are removed (goto statements, low-level pointer manipulations).

Programmers start using a language in a particular way that is not supported by any language constructs. Language designers identify such usage patterns and introduce new abstractions/language constructs to support such usage patterns. There were no procedures in assembly language. No classes in C. No exception handling in (early) C++. No safe way of loading new modules in early languages (easy in Java). No built-in threads (easy-peasy in Java).

Researchers think about alternative ways of expressing computations. This led to Lisp and the functional language branch of the language tree, Prolog and the logic programming branch, Erlang and other actor-based programming models, among others.

Over time, language designers/researchers come to better understand all of these constructs, and how they interact, and design languages to include many of the popular constructs, all designed to work seamlessly together. This results in wonderful languages such as Scala, which has objects and classes (expressed using traits instead of single or multiple inheritance), functional programming features, algebraic data types integrated nicely with the class system and pattern matching, and actor-based concurrency.

Researchers who believe in static type systems strive to improve their expressiveness, allowing things such as typed generic classes in Java (and all of the wonderful things in Haskell), so that a programmer gets more guarantees before running a program that things are not going to go wrong. Static type systems often impose a large burden on the programmer (typing in the types), so research has gone into alleviating that burden. Languages such as Haskell and ML allow the programmer to omit all of the type annotations (unless they are doing something tricky). Scala allows the programmer to omit the types within the body of methods, to simplify the programmer's job. The compiler infers all the missing types and informs the programmer of possible errors.

Finally, some languages are designed to support particular domains. Examples include SQL, R, Makefiles, the Graphviz input language, Mathmatica, LaTeX. Integrating what these languages' functionalities into general purpose languages (directly) would be quite cumbersome. These languages are based on abstractions specific to their particular domain.

Without evolution in programming language design, we'd all still be using assembly language or C++.

As for knowing a functional programming language: functional languages allow you to express computations differently, often more concisely than using other programming languages. Consider about the difference between C++ and Python and multiply it by 4. More seriously, as already mentioned in another answer, functional programming gives you a different way of thinking about problems. This applies to all other paradigms; some a better suited to some problems, and some are not. This is why multi-paradigm languages are becoming more popular: you can use constructs from a different paradigm if you need to, without changing language, and, more challengingly, you can mix paradigms within one piece of software.


Proving unsatisfiability of a propositional formula

If we take the problem precisely as stated, the answer is negative, assuming $P\neq NP$. Indeed, checkSymmetry is trivially implementable in polynomial time, since it takes as input both the formula $F$ and the assignment $A$, so it can check those. Hence, if a reduction existed, that would imply that unsatisfiability is polynomially decidable, hence $P=NP$.

(Update: my guess below was not what the OP wanted, but I am leaving it here anyway.)

However, I guess your checkSymmetry is meant to take only $F$ as input, and check something equivalent to the validity of $F \iff \bar F$, where $\bar F$ is $F$ with every atomic formula negated.

Then, we can reduce checking validity of any propositional formula to checking symmetry.

Given any $F$, take $G := P \land \lnot F$, where $P$ is an atomic formula not occuring in $F$. We have
$$
\models F \iff \models (G \iff \bar G)
$$

($\Rightarrow$)
Assume $\models F$: we deduce immediately $\models \bar F$.

We need to prove that
$$
\models (P \land \lnot F) \iff (\lnot P \land \lnot \bar F)
$$
but we know $F$ and $\bar F$ are true for all assignments, so the above simplifies to $\models \bot \iff \bot$ which is trivial.

($\Leftarrow$) Assume $\models G \iff \bar G$.
We need to prove $\models F$.
Let $A$ be an assignment for $F$. Extend it to $B:=A[P\mapsto \top]$.
We have
$$
B \models G \iff \bar G
$$
which is
$$
B \models (P \land \lnot F) \iff (\lnot P \land \lnot \bar F)
$$
which, thanks to the choice of $B(P)$ simplifies to
$$
B \models \lnot F \iff \bot
$$
hence $B \models F$, and we also have $A \models F$ since $P$ does not occur in $F$.


Number of ways of making change in Big O notation

Suppose that the two denominations are $a$ and $b$. Every solution to the coin-changing problem is a solution to the equation $\alpha a + \beta b = n$ in non-negative integers $\alpha,\beta$. For every possible value of $\alpha$ there is at most one solution. Since $0 \leq \alpha \leq n/a$, we conclude that there are at most $n/a + 1 = O(n)$ solutions.


Find the longest possible path in full binary tree

If it is a full binary tree, that is defined as:

  Full binary tree is a tree in which every node other than the leaves has two children.

Then you know the depth $D$ will be half of the total possible diameter. This is because we can take a maximum possible path of length $D$ from root to any leaf in the subtree rooted at the left-child of the root, and we can also take a maximum possible path of length $D$ from root to any leaf in the subtree rooted at the right-child of the root. Thus, adding these up would be a path of length $2D$.

Thus, we get that the maximum possible diameter would be equal to twice the depth (i.e. $\mathrm{diameter} = 2\cdot \mathrm{depth}$).


Reduce EXACT 3-SET COVER to a Crossword Puzzle

A reduction from PLANAR 3-SAT with bounded occurrences is more viable.

The upper bound of occurrences should be $3$ for each variables $x_i$ (two positive and one negative OR two negative and one negative).


What is the purpose of using NIL for representing null nodes?

As far as I'm concerned, null, nil, none and nothing are common names for the same concept: a value which represents the “absence of a value”, and which is present in many different types (called nullable types). This value is typically used where a value is normally present, but may be omitted, for example an optional parameter. Different programming languages implement this differently, and some languages might not have any such concept. In languages with pointers, it's a null pointer. In many object-oriented languages, null is not an object: calling any method on it is an error. To give a few examples:

In Lisp, nil is commonly used to stand for the absence of a value. Unlike most other languages, nil has structure — it's a symbol whose name is "NIL". It's also the empty list (because a list should be a cons cell, but sometimes there is no cons cell because the list is empty). Whether it's implemented by a null pointer under the hood, or as a symbol like any other, is implementation-dependent.
In Pascal, nil is a pointer value (valid in any pointer type) that may not be dereferenced.
In C and C++, any pointer type includes a NULL value which is distinct from any pointer to a valid object.
In Smalltalk, nil is an object with no method defined.
In Java and in C#, null is a value of any object type. Any attempt to access a field or method of null triggers an exception.
In Perl, undef is distinct from any other scalar value and used throughout the language and library to indicate the absence of a “real” value.
In Python, None is distinct from any other value and used throughout the language and library to indicate the absence of a “real” value.
In ML (SML, OCaml), None is a value of the any type in the type scheme 'a option, which contains None and Some x for any x of type 'a.
In Haskell, the similar concept uses the names Nothing and Just x for the values and Maybe a for the type.

In algorithm presentations, which name is used tends to stem from the background of the presenter or the language that is used in code examples.

In semantics presentations, different names may be used to refer to e.g. the NULL identifier which denotes a pointer constant in the language, and the $\mathsf{nil}$ value in the semantics. I don't think there's any standard naming scheme, and some presentations leave it up to a font difference, or don't go into concrete syntax at all.

It's possible that your lecturer wants to use the word null for a null pointer constant in the programming language used in the course (Java or C#?), and NIL to denote the absence of a node in some data structures, which may or may not be implemented as a null pointer constant (for example, as seen above, in Lisp, NIL is often not implemented as a null pointer). This distinction would be relevant when discussing implementation techniques for data structures. When discussing the data structures themselves, the null-pointer-constant concept is irrelevant, only the not-equal-to-any-other-value concept matters.

There is no standard naming scheme. Another lecturer or textbook could use different names.


Finding simpler equivalent regular expressions

A better approach would be to understand what words do these regular expressions represent. For example, what words are in $(r+\Lambda)^*$? They look something like $r_1r_2 \Lambda r_3 \Lambda = r_1r_2r_3$, where $r_1,r_2,r_3$ are generated by $r$. It seems that $\Lambda$ isn't making much of a difference. This should help you simplify $(r+\Lambda)^*$. The same approach works for the other expressions (including the first one, which you haven't simplified completely).


Optimizing resource management game (similar to Farmville)

In general, you cannot hope for a polytime solution to all such games.  For many such games, the problem of playing them optimally is NP-hard.

For instance, Minesweeper (on a $n\times n$ grid) is NP-hard, and thus does not have a polytime algorithm to solve it (unless $P=NP$, which most consider unlikely).  The same is true for Sudoku (on a $n^2 \times n^2$ grid) and Tetris.  Optimal play for chess, checkers, Go, and Scrabble (on a $n \times n$ grid) is either EXPTIME-complete or PSPACE-complete (depending upon whether you put a bound on the number of moves that a player can make), so they too are very unlikely to have any polytime algorithm to play them optimally (unless the polytime hierarchy collapses or something equally surprising).

In fact, I've seen some folks suggest that there's a strong connection here: the best games tend to be ones where finding the optimal solution is asymptotically hard.  If finding the optimal solution was too easy, the argument goes, the game wouldn't be fun for humans.  Obviously, this is not a rigorous argument and it is easy to come up with counterexamples, but I think there might be something to it.

There's lots more written on this sort of topic.  For a entry point and overview, see, e.g., the following:

http://for.mat.bham.ac.uk/R.W.Kaye/minesw/ordmsw.htm
https://en.wikipedia.org/wiki/Game_complexity
https://www.ics.uci.edu/~eppstein/cgt/hard.html


Decidability of Turing Machine accepting exactly 14 words

Your intuition is correct. Probably you can reduce emptiness (or maybe its complement) to this language but it's not the way I'd do it. Instead, think about how you prove that emptiness is undecidable.

You want to know if $M$ halts on input $w$ so you produce a TM that accepts everything if $M$ accepts $w$ and rejects everything if $M$ rejects $w$. A slight modification of that proof will show that your language is undecidable.


Your understanding is right. So in particular, for any graph $G$ with a clique of size $k$, you will need at least $k$ colors to properly color it. In case this is not obvious, you can think about it via a contradiction. So assume $G$ contains a clique of size $k$, and you have a proper coloring with less than $k$ colors. It follows that the clique contains at least two vertices with the same color. By definition of a clique, these two vertices are adjacent. But this is a contradiction to the coloring being proper.

Further, one might also wonder if the chromatic number of a graph would always equal the clique number. In this direction, you can have a look at perfect graphs for which the chromatic number of every induced subgraph equals its clique number. On the other hand, the Mycielski graphs show that there are graph that don't even contain a triangle (equivalently, a clique on 3 vertices), while the chromatic number can be arbitrarily large.


Algorithm to convert a fixed-length string to the smallest possible collision-free representation?

As ratchet freak says, you have ten decimal digits, which should give $10^{10}$ possible values. But in practice, there are a few more restrictions. The format of a North American telephone number looks something like this:

[2-9][0-8]\d - [2-9]\d\d - \d\d\d\d

This gives 8*9*10 * 8*10*10 * 10*10*10*10 values. In addition, the fifth and sixth characters can't both be 1, which removes 1% of these. This means there are 5,702,400,000 possible telephone numbers. (Let's call this number $T$.)

If you want to encode these using an alphabet with $b$ different characters, you'll need a code $\lceil \log_b T \rceil$ characters long. So if you want a code four characters long, you'll need $b \geq 275$. If you want a code five characters long, you'll need $b \geq 90$. And if you want a code six characters long, you'll need $b \geq 43$.

Unfortunately, this is the best you can do, unless you have additional information about what numbers you'll be getting. This comes down to the pigeonhole principle, a remarkably straightforward theorem that's quite useful in CS. It's mathematically impossible to use fewer characters than this without ever having any collisions. You can make collisions extremely unlikely, but never fully prevent them.

(You can also make some of the codes be shorter without collisions, but as a consequence some of them will have to be longer. Again, pigeonhole principle.)

P.S. Note that, while base64 also produces a six-character string (since 64 is between 43 and 90), you can take advantage of the fact that you only need 43 to choose a "nicer" character set. For example, you can get rid of o, O, 0, Q, I, l, and 1 to cut down on confusion in writing. My suggestion would be 23456789ABCDEFGHJKLMNPRSTVXYZabdeghknpqrt-=.


Find maximal subgraph containing only nodes of degree 2 and 3

Basically, in 2-3 graph, the lower bound 2 means that any node has to be in a cycle.

In DFS, when you reach an already visited node, you found a cycle. Just check if adding this cycle to your subgraph also respect the upper bound 3.

As you suggested, the maximal 2-3 subgraph is not unique. But if you built it following this method, you ensure that any node/vertex of $G$ you did not select in your subgraph:

either is not part of any cycle and would lead to a vertex of degree 1 if selected
either is part of cycles that would all lead to a vertex of degree 4 if selected

Thus, your 2-3 subgraph is maximal.


What are the drawbacks of using an algorithm that is not backwards stable?

Sivan Toledo responded to my query with the following:

  In general, the significance and the broad-context meaning of
  mathematical results is a matter of opinion and debate, so perhaps not
  every researcher would agree to our explanation below.

  In most of the literature, backward stability is a technical and/or
  analytic tool that makes it relatively easy to prove that an algorithm
  produces accurate results (or to bound the inaccuracy). In these
  contexts, the user of the numerical method worries about accuracy, not
  about backward stability, and the numerical analyst uses backward
  stability just as a mechanism to prove the bound that the user cares
  about.

  (The analysis in our paper proves accuracy without relying directly on
  backward stability, but this is atypical.)

  When an algorithm is backward stable, the user gets not only a bound
  on the magnitude of the error, but also an estimate of its direction;
  it lies in the direction of right singular vectors that correspond to
  small singular values (for the case of solving linear equations). In
  many cases this is completely meaningless to the user.

  Backward stability may be meaningful to the end user if the parameters
  of the problem (say the coefficients of a linear equation) are only
  known approximately, say because they are measured or estimated using
  some limited-accuracy physical instrument. In some of these cases it
  may be good for the user to know that the output she/he got is an
  exact solution to a nearby problem.

I'd still like to better understand theoretically what the drawbacks of using inv(A)*b are when b is "bad". That is, if the solution using inv is as accurate as with a "better" algorithm, what really matters. (This is hinted at computationally in my question: the projection matrix A * inv(A' * A) * A' is at least unreliable.)


Effective computation on linear data without random access

No.  Consider an algorithm on a graph (e.g., network flow).  It fundamentally requires random access to memory.  The restriction you propose would be painful and make many standard algorithms impossible.


Is this even true? Consider an undirected graph which is a star. That is, a central vertex $V_0$ is connected to all other vertices $V_1, V_2, \dots, V_{n-1}$, and there are no other edges in the graph. Then, if you start with an equal distribution on $V_1, V_2, \ldots, V_{n-1}$, after one step all the weight is on the central vertex $V_0$. So in one step the entropy has gone from $\log (n-1)$ to $0$.


Intuition on O(number of leaves) for master theorem

The recurrence in question is $T(n) = aT(n/b) + f(n)$. Suppose that $n = b^k$, and the leaves are at $n = 1$. The root $b^k$ has $a$ children labelled $b^{k-1}$ (the label is the size of the subproblem). Each one of them has $a$ children labelled $b^{k-2}$, and in total there are $a^2$ children at depth $2$ labelled $b^{k-2}$. More generally, there are $a^\ell$ children at depth $\ell$ labelled $b^{k-\ell}$. In particular, taking $k = \ell$, we see that there are $a^k$ leaves. Since $n = b^k$, we get that the number of leaves is
$$
a^k = (b^{\log_b a})^k = (b^k)^{\log_b a} = n^{\log_b a}.
$$


Algorithm to check whether a complete, undirected graph is fullfilling the triangle inequality

Yes.  If you have a complete graph, the simplest algorithm is to enumerate all triangles and check whether each one satisfies the inequality.  In practice, this will also likely be the best solution unless your graphs are very large and you need the absolute best possible performance.  For instance, enumeration will likely be faster than most shortest-paths algorithms.

None of the shortest-path algorithms provide better asymptotic runtime; they are more complicated to implement; and they will be slower in practice (because of a larger constant factor).

As AJed correctly points out, you can use matrix multiplication to beat the $O(n^3)$ bound.  However, this requires a bit more care.  While there are algorithms for matrix multiplication that are faster than $O(n^3)$ time, the algorithms are tricky to implement, so if you take this approach, you might want to use an existing library/implementation (e.g., BLAS).  Also, the asymptotically optimal algorithms (e.g., Coppersmith/Winograd, Stothers, Williams) only become faster once $n$ becomes extremely large so they won't be worthwhile in practice.  This suggests that if you want to wring out every last bit of performance, you'll need to actually benchmark this on realistic workloads: asymptotic complexity can be misleading.

If you care about extreme optimization, cache effects may also play a huge role here, so the way the graph is laid out in memory may have a significant effect on the constant factors.  Fortunately, if your graph is represented as an adjacency matrix, standard libraries for matrix multiplication already take this into account.

If it were me, I'd just enumerate all triangles and check the triangle inequality.  If you run into a problem domain where this is the bottleneck in the overall computation and where it is too slow, then you could consider more sophisticated approaches, like using matrix multiplication, at that point.  To paraphrase Knuth, "Premature optimization is the root of all evil".


What is the difference between "algorithm," "process" and "program"?

These terms are often used very loosely and to mean different things. The definitions below uses Wikipedias definitions as an outset, but tries to make them more clear and formal. Being this strict is usually not needed in practice.

Program

Computer Program: A collection of instructions that performs a specific task when run$^{1}$ by a computer [Wikipedia].

These instructions can be expressed in low level assembly or in some high level language in the source code. To be able to run the program the instructions must be represented as machine instructions for the targeted CPU.

Process

Computer Process: An instance of a computer program that has been "loaded" to virtual memory$^2$ [Wikipedia].

In contemporary operating systems a process can be in several states, such as running (i.e., being processed by the CPU) or waiting [Wikipedia].

Algorithm

Algorithm: An unambiguous specification, that can be expressed within a finite amount of space and time, and in a well-defined formal language, for calculating a function [Wikipedia].

Most programs includes one or more algorithms, but they also do other things, such as side effects (e.g., I/O operations) [Wikipedia].

Footnotes

$^1$ The Wikipedia article actually uses "executed" which is a very common verb to use in this case. There is two reasons why "run" or "being processed" could be preferable:

When a CPU is processing instructions it does more than just executing them: the other actions are usually defined as fetching instructions and decoding instructions.
As is shown in the definition for process, the term running is usually used when referring to this.

$^2$ The Wikipedia article actually uses "executed" (again) which is a very common verb to use in this case as well. For the same reasons as above, some other terminology can be preferable if one needs to be precise.

In addition, due to the process states, it might not even be running either, just being in the virtual memory space (i.e., in RAM or swapped).


Finite substitution and regular closure properties

You seem to have understood the operation of substitution. That maps any string into a language by concatenating the images of the letters.

Your argument that regular languages are closed under finite substitution does not work. Even if the substitution maps avery word into a finite language, the substitution of a regular language usually is infinite as the initial ragular language is infinite.

A possible approach is to use regular expressions.


If you have a complicated data structure, its representation in memory might ordinarily be scattered throughout memory.  (Think of a binary tree, for instance.)

In contrast, when you want to write it to disk, you probably want to have a representation as a (hopefully short) sequence of contiguous bytes.  That's what serialization does for you.


Mutual recusive definitions are tricky to eliminate. You'll have to work with the unwieldy expanded form of one of the rules. Here, let's expand $B$
\begin{align*}
B &\to Bb \mid Ab \mid d \\
& \to (Bb \mid Ab \mid d)b \mid Ab \mid d \\
&\to ((Bb \mid Ab \mid d)b \mid Ab \mid d)b\mid Ab \mid d \\
& \to ~\cdots \\
&\to (d \mid Ab) \mid (db \mid Abb) \mid (dbb \mid Abbb) \mid \cdots \\
&\to (d \mid Ab)b^*
\end{align*}
In general, $B \to B(x_0 \mid x_1 \mid \dots) \mid (y_0 \mid y_1 \mid \dots)$ will have an expanded form of $B \to y\cdot x^*$. Things get even more complicated if $B \to z B x \mid y$ and $z$ is nullable. But let's not worry about that just yet, instead, let's turn our attention back to $B$.

Now, notice that I have used the term $b^*$, this is actually just the nonterminal $b^* \to \epsilon \mid b b^*$; this is a standard trick that many "extended" BNF based parsers use as well.

Finally, we can inline $B$ into $A$ to get
\begin{align*}
A &\to Ba \mid Aa \mid c \\
&\to db^* a \mid Abb^*a \mid Aa \mid c \\
&\to (c \mid db^*a)(bb^*a \mid a)^*
\end{align*}

where once again $(bb^*a \mid a)^* \to \epsilon \mid (bb^*a \mid a)(bb^*a \mid a)^*$.

Now, if all you need is $A$, then this is already fine and dandy. However, if you need to expose $B$ as a public method as well, then you'll notice that there is a slight hitch: $\text{follow}((bb^*a \mid a)^*) = \text{follow}(A) = b$, since $B \to Abb*$. But since $\text{first}((bb^*a \mid a)^*)$ also contains $b$, then we can't decide whether we should shift to $\epsilon$ or $bb^*a$ when we encounter a $b$. You might try to inline $A$, so that
$$
B \to (d \mid (c \mid db^*a)(bb^*a \mid a)^*b)b^*
$$
but you still have the same problem. Now you can reason that $(bb^*a \mid a)^*bb^* = b^*(ab^*)^*$, but this is not very generalizable, and it breaks down fast when your language takes a step out of its regular territory. Instead, you'll want to start from the beginning. Expand $A$ first, and inline into $B$.


Time-Complexity Verification: Code with two loops with an index halved at each iteration

As said above, both approaches are correct but in approach #2 I don't get a tight-bound. Since I want a tight-bound using the second approach I failed to notice what $ n $ actually is once inside the while loop. Let's look at the code above but formatted a bit in the following manner:
def f1(L):
   n_0 = len(L)
   n_k = n_0
     while n_k > 0:
        n_k = n_k // 2
        for i in range(n_k):
          if i in L:
             L.append(i)
   return L

Analysing the time-complexity of code using "inside-out" approach as I wanted:
The for-loop's complexity is $ \sum_{i=1}^{n_k} \cdot O(n_0) $ ( Complexity of "in" is $ O(n_0) $ ), i.e. $ O( n_k \cdot n_0 ) $. Thus since the while-loop runs $ log(n_0) $ times by my analysis, the total time-complexity of code is $ \sum_{k=1}^{log(n_0)}O(n_k \cdot n_0 ) $ , notice that $ n_k = \frac{n_0}{2^k} $ ( $ k $ is the k-th iteration of while loop ) hence   $ \sum_{k=1}^{log(n_0)}O(n_k \cdot n_0 ) = O(\sum_{k=1}^{log(n_0)}n_k \cdot n_0 ) = O(\sum_{k=1}^{log(n_0)} \frac{n_0}{2^k} \cdot n_0 ) = O(n_0^2) $. Denote $ n_0 $ as $ n $ and we have $ O(n^2) $ and we're finished.


Could the empty language be NP-Complete?

You are correct that $\emptyset\in NP$, since we already know that $\emptyset$ can be decided in constant time (a TM that immediately rejects), and $DTIME(O(1))\subseteq P\subseteq NP$.
But $\emptyset$ is not NP-complete, regardless of whether $P=NP$. Indeed, by definition, a NP-complete language $A$ is such that every language $B \in NP$ admits a Karp reduction to $A$, i.e., a function $f$ that is computable in polynomial time and such that $x \in B \iff f(x) \in A$.
If $A= \emptyset$ and $B \neq \emptyset$ then no such function exists, since there is no way to satisfy $x \in B \implies f(x) \in A$.


Is there a way to test "Turing completeness"?

I don't know about specific models. It's pretty easy to become Turing Complete, since all you need is infinite search. So I can imagine a model where searching for finite vs. infiniteness boils down to Turing Completeness, but I don't know if any actually exist.

But a general algorithm "look at an arbitrary systems and tell if it's Turing Complete" can't exist. Otherwise we could do this:

RunTuringMachine = lambda (M1) . lambda (x). lambda (M2) .
  run M1 on x and discard the result
  run M2 //we only get to this line if M1 halts on x

Then, for any inputs M1, x, RunTuringMachine M1 x is a Turing-complete system if and only if M1 halts on input x, and we've solved the halting problem.

We could also prove this by Rice's theorem: if we can decide if any system is Turing Complete, then we can decide of a Turing Machine is a Universal Turing Machine, which is impossible by Rice's Theorem.


2SAT is the following problem: given $\varphi$ (a Boolean formula in 2-CNF), is $\varphi$ satisfiable?

To show that 2SAT is in $\textsf{AC}^0$, you must show a constant-depth, polynomial-size circuit that can solve 2SAT.  In other words, you need to come up with an algorithm to solve 2SAT, and then show that the algorithm can be implemented by an $\textsf{AC}^0$ circuit.

In your question, you showed that $\varphi$ is in $\textsf{AC}^0$, but that's not what we need.  We need to know that the algorithm to solve 2SAT (i.e., to check whether $\varphi$ is satisfiable) is in $\textsf{AC}^0$, not that $\varphi$ is in $\textsf{AC}^0$.


"Reshaping" vs Polymorphism In Data Wrangling

Am I missing something about this problem that renders it particularly immune to the application of mature technologies to hide data representation from the abstract functions?

I would say so. And that is empirical experience of what works.
In theory data is data. A general artificial intelligence agent should be able to classify a picture as a cat or a dog regardless of whether it's a photo, a drawing, in color or black/white, altered through an Instagram filter to have a human face, a PNG, JPEG or MP4, compressed with zip, or infinite other possibilities.
But that's purely theory. In practice data representation matters, a lot. The very same task your machine learning method gets state of the art on might not learn at all if you change the data representation. In practice feature engineering is a huge part of any machine learning project. And the existence and importance of this task should indicate that with current techniques it's not feasible to even begin to think of hiding the data representation.

As an example, take the recent success of GPT-3 and transformers. The entire novelty of this technique comes from the way data is represented and learned from inside the neural network.
Another example, AlexNet. It popularized the now standard deep convolutional neural network. A convolutional neural network only really 'works' on (multiple slices of) 2D data. Any other representation and the convolution stops making any sense at all.
In state of the art machine learning, data representation is everything.


Show that the following algorithm takes $O(n)$ time

Can't be done.

Consider the following sequence of access: $$\tfrac{1}{2}n, \tfrac{1}{4}n, \tfrac{3}{4}n, \tfrac{1}{8}n, \tfrac{3}{8}n, \tfrac{5}{8}n, \tfrac{7}{8}n, \ldots$$

The first access costs $\tfrac{1}{2}n$. The next two cost $\tfrac{1}{4}n$ each, for a total of $\tfrac{1}{2}n$. The next four also cost a total of $\tfrac{1}{2}n$. Overall we get a cost of $\tfrac{1}{2}n \lg n$.


How does a transition function behave in a FSM when an input is not recognized (i.e. the input is not contained in the alphabet)?

In my copy of the book, third edition, this is Theorem 1.25. From its proof, I quote:

The theorem remains true if they have different alphabets, $\Sigma_1$
and $\Sigma_2$. We would then modify the proof to let $\Sigma = \Sigma_1\cup \Sigma_2$.

What is suggested here is that in advance we assume the two alphabets to be equal, i.e., before we start the product construction. So we have to transform the original automaton $M_1$ with alphabet $\Sigma_1$ into an equivalent automaton $M_1'$ with alphabet $\Sigma_1\cup \Sigma_2$ accepting the same language. As you observe automata here are deterministic, i.e., have a transition function $\delta:Q\times \Sigma\to Q$.
The easiest way for the construction of $M_1'$ is extending the transition function for letters outside $\Sigma_1$. Any such letter should lead to not accepted computations. This can be done by adding a new garbage (or failure state) where all letters from $\Sigma_2\setminus \Sigma_1$ are mapped to.


Constraint-based Type Inference with Algebraic Data

See: Mini ML Specifically the Type Inference section.

This contains sample code in F# for a complete parser of a simple functional language. More importantly the Type Inference section implements the Hindley-Milner algorithm which is what is found in most type inference system. The author also provides links to two other important documents to help in understanding Hindley-Milner; one being a kind of high level introduction and the other being a paper that describes the implementation of the algorithm in code.


Why does a MP3 encoder use a fast Fourier transform before applying the psychoacoustic model?

I would suggest a more detailed explanation of mp3 codec.

FFT is applied on the time domain signal, so in fact it does not use the result from the MDCT.  The input to the psychoacoustic models is in the frequency domain, hence the FFT.

There at least several reasons to do it.
MDCT with filterbanks operates on very short overlapping chunks, maximizing the compression – the FFT uses longer samples and has better spectral resolution. (It is hard to compare since MDCT operates as short-term transform; if this is of big importance to you I will have to make that comparison.)

You can think of filterbank MDCT in the same way as JPEG quantization (it is a very good analogy, since both use DCT) and FFT to detect DCT artifacts from compression.
Then, the psychoacoustic model smooths the errors to fall under the "hearable" threshold, but in order to do that, the time domain samples (here PCM – Pulse Code Modulation is not enough, because sudden frequency shifts are heard as cracks) - so it uses the frequency domain to detect such discontinuities and then smooth it in time domain.

Two things are not explained in articles but are crucial. When PCM differences, are high the speaker has more distance to travel, so there is time delay and depending on speaker abilities it might just cause additional vibrations, which are quite distinct noises from speaker.
The second part is between lines, the quantized version of signal is transformed back to compare it with original sound and check how much it deviates.

Based on the masking type of windows (based on comparison of FFT and inverted MDCT) is chosen to compensate better for audible deviations from the original.

Humans perceive frequency shifts better than amplitude changes, so the filter operates in the both domains at once, and the quantized signal is reversed and smoothing is done back in time domain.

Yes, the resolution of MDCT with filterbanks is not enough, but this is the part where a fair share of the compression happens, and then it is masked. But the psychoacoustic model has spectral resolution as given in the paper.

Yes, FFT is more accurate because it gets longer samples, so it has better resolution between bins.

Footnote
The (M)DCT is commonly implemented by performing FFT, so this has nothing to do with transform used. MDCT can be seen as a bit-modified Short-Term Fourier Transform with a specially chosen filter (the filterbanks resemble Mel scale for speech recognition).

FFT is used longer, provides easier algorithms for pitch shifting and is easier to apply on sound.
(M)DCT minimizes the number of components, meaning that we can cut more data from the result than from FFT.

But in the case of sound those components are not stable, cutting always e.g. two bins out will give bigger disortion between consecutive frames than doing equivalent operation on FFT results.
So, the connection between FFT and what we hear is bigger than (M)DCT and what we hear, but available compression is the other way around.


Evaluation of $\beta$-Reduction with Parentheses in $\lambda$-Calculus

You are missing one important pair of parentheses, around an expression for $2$. It should be
$$\bigl(\lambda s. \lambda z. (s\ (s\ z))\bigr)\ s\ (s\ z)$$
Then we reduce by replacing $s$ with $s$ and $z$ with $(s\ z)$, obtaining
$$(s\ (s\ (s\ z)))$$

On the other hand, $\lambda s. \lambda z. (s\ (s\ z))\ s\ (s\ z)$ doesn’t reduce any further because it has no redex. It is just a $\lambda$-abstraction with variables $s,z$ and body $(s\ (s\ z))\ s\ (s\ z)$. Abstraction always goes as far right as possible.

Generally, when we have a name for expression (e.g. $2$, $myexp$,...) within some larger expression, we must surround it with parentheses when we expand it to its true lambda form, to avoid confusion regarding applications.
Just like you did with $1$ in the third row.

You can explore $\lambda$-calculus reductions, test your ideas and see how various expressions are implemented with this interpreter.


Performance of row- vs. column-wise matrix traversal

In today's standard architectures, the cache uses what is called "spatial-locality". This is the intuitive idea that if you call some cell in the memory, it is likely that you will want to read cells that are "close by". Indeed, this is what happens when you read 1D arrays.

Now, consider how a matrix is represented in the memory: a 2D matrix is simply encoded as a 1D array, row by row. For example, the matrix $\left(\begin{array}{ll} 2, 3 \\4, 5\end{array}\right)$ is represented as $2,3,4,5$.

When you start reading the matrix in cell $(0,0)$, the CPU automatically caches the cells that are close by, which start by the first row (and if there is enough cache, may also go to the next row, etc).

If your algorithm works row-by-row, then the next call will be to an element still in this row, which is cached, so you will get a fast response. If, however, you call an element in a different row (albeit in the same column), you are more likely to get a cache miss, and you will need to fetch the correct cell from a higher memory.


Why doesn't everyone use distributed operating systems?

This is part of an answer.  Others will probably be able to add other points.

A chess platform has to do a limited number of things, while an OS has to be able to do everything that OSes do, which is unlimited.  You need lots of utilities, lots of apps written, and to get those, lots of compilers and coders' tools, etc.  It's a much harder thing to get off the ground, and doing so is as much a social endeavor as a technical one.  It's quite interesting that Linux took off as it did, but there were other competing projects at the time such as FreeBSD and GNU (which was supposed to be an OS, and not just Linux's utility suite) that have fallen by the wayside.  This has a lot to do with choices that Linus Torvalds and others made early on in the process that gradually led to more and more people hacking on Linux and using it, I believe.  Some of the choices were reflected in the code itself, but some of them had to do with social factors.  Part of it is probably just chance, though.  It didn't happen overnight with Linux, either.  It took several years before it started to get popular enough that it might have had a chance to grow into the popularity it has now.

The point is that being better isn't enough.


If L is a regular language then also is the language $L1 = \{ w \in L | w \in L^R \}$?

The notation $L_1 = \{ w \in L \mid w \in L^R \}$ means "the collection of all $w \in L$ that satisfy the condition $w \in L^R$". In other words, $L_1 = L \cap L^R$.


(This is a cross-posted answer from Physics Stack Exchange)

The simple answer would be: consider a physical system that can be in two states. Its thermodynamic entropy is $k_B \log(2)$ due to this. When you erase the bit, then you have a definite microstate and the entropy is zero. Since entropy cannot decrease it has to go somewhere, and this means it needs to be transferred to the environment that has temperature T, giving us a cost $k_B T\log(2)$.

This is the simplified version of a slightly dodgy derivation (note how I facilely equated thermodynamic entropy with information entropy without justification and did not specify how erasure happened or the entropy got moved around). Once can do this more rigorously, like in this paper.

Also, it is worth pointing out it is a misconception that the cost has to be paid in energy. If you have an empty computer memory you can just swap the erased bit for a fresh zero reversibly. But empty computer memory is in a sense a heat reservoir at absolute zero but with very limited capacity (it will eventually run out). It is possible to show that the cost can be paid using other conserved quantities like spin. It is just that in practice we tend to move entropy around by dumping it as waste heat in a cool outside heat bath.

(Landauer's original paper)


Where to find practical exercises for algorithm analysis?

Textbooks in algorithms are chock full with examples of algorithms, often with analysis. For example, take a look at Erickson's "Algorithms", Dasgupta et al "Algorithms". Looking around for lecture notes will get you a lot of others. Analysis of algorithms requires some specialized techniques, a modern overview is Sedgewick and Flajolet's "Introduction to the analysis of algorithms".


tightest upper bound on binary search tree insertion?

For a binary search tree of $n$ nodes ,
Maximum height $=h_{max}=n-1 = \Theta (n) =O(n)$
which happens in the case of skewed binary search tree as below if all elements of a binary search are either right-skewed or left-skewed

So in worse case , to add a new node in to an existing skewed binary search tree , it takes $n$ comparisons (comparison at each level).
So, time taken $= h_{max}+1=n=\Theta\ O(n)$

Minimum height = $h_{min}=\lceil \log_2{(n+1)}\rceil-1=\Theta(\log(n))=O(\log(n))$
which happens in the case of complete binary search tree as below if all levels contains all elements except last level (Last level may be not contain all elements).

Now, number of comparisons $= h_{min}+1=\lceil \log_2{(n+1)}\rceil=\Theta(\log(n))=\ O(\log_2(n))$
Which may be the tightest upper bound you are asking for .
So, you can use either $\Theta$ or $\ O$ notation here. $\Theta$ is tighter .
Whenever you use $\Theta$ you can replace it with $\ O$ but not viceversa .


Are there strings which get accepted only by PDA by empty stack and not by PDA by final state, and vice versa?

Since it was not explicitly mentioned, I'll assume that the PDA in the question is a PDA $P_s$ that has been defined for acceptance by empty stack. Let the language accepted by $P_s$ be $L_s = N(P_s)$.

There definitely exists another PDA $P_f$ which produces a language $L_f = L_s$  by defining acceptance on final state. This is why we say that:

  A language L has a PDA that accepts it by final state if and only if L has a PDA that accepts it by empty stack.

However, it is wrong to expect that the two PDA $P_s$ and $P_f$ are the same.


See this page.
Essentially, create a new DFA $D$ in which the set of states $Q$ is the powerset of the set of states of your NFA $N$.
For $q \in Q$ and $a \in \Sigma$, add transition $\delta(q,a) = q'$ to $D$, if and only if, the set of states of $N$ that are reachable (in $N$) from at least one state in $q$ by reading character $a$ is exactly $q'$.
Mark a state of $q \in Q$ as a final state in $D$ if and only if $q$ contains a final state of $N$.
If $q_0$ is the initial state of $N$, then the initial state of $D$ is the set of states if $N$ that are reachable by $q_0$ using only $\varepsilon$-transitions.


what is the relationship between increasing the number of cores and scalability?

If the problem size (input data set and/or computation) is fixed , then NO. Amdahl's law says that. Speed up will be bounded by serial portion of the program.

If the problem size (input data set and/or computation) increases with the increase in the number of cores, then YES, Gustafson's law says that.


Intuitive explanation on why stochastic encoding performs better in channel coding

Well, I think you are conflating two things. It is correct that in a lot of settings probabilistic encoding (e.g., Polar Codes, Convolutional Codes, LDPC Codes) [assuming you know a good model for the noise process of the channel] does much better than algebraic coding, intuitively because channels have memory and block codes ignore that memory.
However, Ahlswede's Identification Problem is quite different. It is NOT a traditional channel coding problem There is a good review  here
The author states

In the problem of identification via channels, introduced by Ahlswede and Dueck the receiver is only
interested in testing whether a particular message was sent, but the encoder does not know which message
the decoder wants. Errors are now considered in terms of false alarm and missed identification. It turns out
that for this case, one can design systems such that the number of different messages one can identify grows
doubly exponentially with the blocklength. The trick is that each message can map into a list of codewords
and the encoder selects one randomly. As long as the fraction of the pairwise overlap of these lists is small,
the error probabilities will be small


Is there a meaningful difference between O(1) and O(log n)?

There are actually all sorts of cases where $\log n$ gets way bigger than 100. For example, if you're working with variable-length integers - say, for cryptography - $\log n$ represents the number of bits in the integer, which can get up to 4096 or higher in practice. Those bits will be spread out over many machine words, so the $\log n$ term refers to how many machine words the number occupies and therefore definitely has an impact on the runtime.

Similarly, $O(1)$ does not mean "constant time only if $n < 2^{64}$." Yes, the computer has a fixed word size, but that doesn't mean that an $O(1)$-time algorithm given a gigantic input can't run in a fixed amount of time. Taking large integers as an example, consider the problem of checking whether an integer is even or odd. That just requires you to look at the last digit, which takes time $O(1)$ even if the number is spread out over thousands of machine words.

The last detail is that typically, we assume that we work with a machine model where the word size scales with the log of the size of the input. This allowance a to safely assume that you can do array accesses in time $O(1)$ because array indices are assumed to fit into a constant number of machine words.


Total Number of Bits Needed to Represent a List of N elements

In the RAM model of computation, machine words are $\Theta(\log n)$ bits long (where $n$ is the size of the input in bits), and operations on machine words can be done in $O(1)$. Counting sort has running time $O(N + k)$ in the RAM model assuming that each value is $\Theta(\log n)$ bits long.

Let us now consider an array consisting of $N$ values, the maximal value of which is $k$. We would need $\log k$ bits to store each value. Assuming that we use $\Theta(\log k)$ bits per value, the input length is $n = \Theta(N\log k)$ bits, and so a machine word is $\log N + \log\log k + O(1)$ bits long. Let us denote by $w$ the number of machine words needed to store a single entry, which we can calculate by
$$ w = \left\lceil \frac{\log k}{\log N + \log\log k} \right\rceil = \Theta\left(\max\left(1,\frac{\log k}{\log N + \log\log k}\right)\right). $$
The running time of counting sort is $O(Nw + k)$.


If you are able to find the least expensive picks in linear (or even polynomial) time then $P=NP$.
Your problem is a generalization of the set-cover problem: given a set $X$ of items and a collection $S = \{S_1, \dots, S_m \} \subseteq 2^X$ of subsets of $X$, find $S' \subseteq S$ such that $\cup_{S_i \in S'} S_i = X$ and $|S'|$ is minimized.
This is exactly your problem once you set $n=|X|$, $s=1$, $P[i][1] = S_i$, and $C[i][1]=1$.


Transitions between lexicographical orders

Aside from trivial cases, transforming lexicographic order indices from one ordering to another ordering can can rarely be done more efficiently than unranking the index using the original alphabet ordering, and then ranking the resulting sequence using the new alphabet ordering.
That works fine in this case, because after precomputation of a table of size $O(N^2)$ (which doesn't depend on the chosen ordering), you can rank and unrank an element of the lexicographic sequence with an arbitrary lexical ordering in $O(N)$ time. (The naïve proof-of-concept code I wrote does the ranking and unranking in $O(Nk)$ time, where $k$ is the size of the bracketing algorithm. But it should be possible to get rid of the $k$.)
The algorithm can be found in Ranking and unranking of a generalized Dyck language and the application to the generation of random trees, Jens Liebehenschel (1999). Liebehenschel's algorithm uses a fixed ordering but extending it to arbitrary orderings is straight-forward.
Liebehenschel's generalisation of Dyck languages allows the use of an arbitrary many-to-many relation between opening and closing symbols (although it requires that the set of opening symbols and the set of closing symbols not have common elements). Restricting the relationship to an isomorphism doesn't significantly simplify the algorithm.


Trying to figure out if a modern computer is capable of manipulating arbitrarily large pointers

The universe is finite, so you can't build a real turing complete computer.

The best you can do is build a computer which observes whether the program it is running is getting close to the limitations of the computer, and when it exceeds them, builds a new, bigger computer, with higher limits, transfers the code to the new computer, and starts all over again.

PS. It is quite possible (and not really very difficult) to build a computer with 256 bit pointers. Since the universe is not just finite, but has a known size, 256 bit pointers are enough for anything.


Let us assume that each entry of $s$ is drawn independently from some distribution $\mathcal{D}$ whose expectation is $0$. Then
$$
\mathbb{E}\left[\left(\sum_{i=1}^d s_i x_i\right)^2\right] =
\sum_{i=1}^d x_i^2 \mathbb{E}[s_i^2] + \sum_{i \neq j} x_i x_j \mathbb{E}[s_i s_j] = \|x\|^2 \mathbb{V}[\mathcal{D}],
$$
since $\mathbb{E}[s_is_j] = \mathbb{E}[s_i]\mathbb{E}[s_j] = 0$ due to independence.

In your particular case, $\mathcal{D}$ is the uniform distribution over $[-1,1]$, whose variance is
$$
\frac{1}{2} \int_{-1}^1 x^2 \, \mathrm{d}x = \left. \frac{x^3}{6} \right|_{-1}^1 = \frac{1}{3}.
$$


Finding shortest path between two nodes with a set of forbidden nodes

Create two directed copies of the graph, one without the forbidden nodes. Connect the outgoing edges of the "forbidden" nodes to the second graph.


If a problem is complete for NP, is its complement complete for co-NP?

Let $L\in \text{NPC}$. For any $L' \in \text{coNP}$ we have $\overline{L'} \leq_P L$ and therefore $L' \leq_P \overline{L}$ (by the same reduction).


Prove that a language is regular if it is accepted by a DFA with more than one intial state

There are many ways of showing that DFAs with multiple initial states generate regular languages. Here are some:

You can prove using Nerode's theorem that for any DFA, the set of words taking the DFA from state $q_1$ to state $q_2$ is regular.
Using "dynamic programming", you can construct a regular expression for the set of all words taking a DFA from state $q_1$ to state $q_2$.
Using $\epsilon$ transitions from a new initial state, you can construct an NFA equivalent to your DFA.

NFAs with multiple initial states are in some sense more natural than NFAs with one initial state. Indeed, the power set construction, which constructs a DFA equivalent to a given NFA, works without any changes for this more general class of NFAs. Moreover, this more liberal definition allows you to prove that regular languages are closed under reversal by simply "reversing all arrows".


How to use a greedy algorithm to find the non-decreasing sequence closest to the given one?

Let's start with the following observation:

  Let $max$ denote the maximum of the sequence $a_1,...,a_n$, and let $min$ denote its minimum. If $a_1=max$, then choosing $b_1=b_2=...=b_n=\lfloor(max+min)/2\rfloor$ is optimal.

Why is this the case? Well, since the sequence starts with the maximum, either we choose $b_1$ large, and suffer a large deviation from the minimum of the sequence (since any subsequent $b_i$ must be greater or equal to $b_1$), or we choose $b_1$ small and suffer from the deviation to $max$. The average minimizes the maximal deviation.

We can now try to generalize this observation to use on general sequences $a_1,...,a_n$. For instance, we can partition any sequence into subsequences, such that each begins with the maximum of the respective subsequence.

  Example: $(2,6,4,1,5,2,8,7,5,1)$ is partitioned into $(2)$, $(6,4,1,5,2)$, and $(8,7,5,1)$.

Given this partitioning, we can now solve each these subsequences separately, and obtain an assignment of the $b_i$'s, which however might violate the non-decreasing condition. This can be fixed without losing optimality.

Observe that the last subsequence always contains the maximum $max$ of the whole sequence (otherwise, there would be another subsequence after it). Let $w_1,w_2,...,w_k$ be the values we assigned to the $k$ subsequences. Now, to achieve non-decreasingness in $w_1,...,w_k$, we start from the back at $w_k$ and work our way to the front. If $w_{k-1}$ is larger than $w_k$, we simply set $w_{k-1}:=w_k$. If it is smaller, we keep it. Then, we proceed with comparing $w_{k-2}$ with $w_{k-1}$ and so on. Note that lowering any $w_i$ to the value of $w_{i+1}$ never increases the deviation, since the maximium value in the subsequence assigned with $w_i$ is always lower than the maximum in the subsequence assigned with $w_{i+1}$.

This algorithm should be correct, I think. Concerning the running time, the key step is computing the increasing maxima for the subsequences, which is possible in $O(n)$? Not sure where $l$ contributes.


Someone explain the venn diagram for the logic equation A*(B+C)

$(B+C) = B\overline{C}+\overline{B}C + BC$

and A with that and you get:

$A*(B+C) = A*(B\overline{C}+\overline{B}C + BC) = AB\overline{C}+A\overline{B}C + ABC$

Remember that OR is the union and AND is the intersection.


Sum to a certain value of a group of integers

This is basically the subset sum problem, which is well-studied.  In particular, there is no efficient algorithm for solving all instances of this problem.

There's a small twist in your version of the problem: you allow multiplying numbers by -1.  However, your problem can still be reduced to the subset problem, by simply appending the negation of all numbers in your list to the list; then you have an instance of the subset sum problem.  For instance, if your list is 2 40 6 7 6 2, you ask whether a subset of 2 40 6 7 6 2 -2 -40 -6 -7 -6 -2 can sum to 30.  That's an instance of the subset sum problem.

If the numbers are not too large, you can use the standard dynamic programming algorithm, and it will be pretty efficient.  But this fails if the numbers are large.


Why does the square root of n! grow exponentially faster than exponential functions?

$\log(n!)=\Theta(n\log n)$, (see Stirling's approximation), hence

$\frac{2^{O(n)}}{\sqrt{\left(\frac{n}{2}\right)!}}=2^{O(n)-\log\sqrt{\left(\frac{n}{2}\right)!}}=2^{O(n)-\Theta(n\log n)}=2^{-\left(\Theta(n\log n)-O(n)\right)}=2^{-\Omega(n)}$.


Proofs based on narrowing down sets of possibilities

The more general argument is an example of an adversary argument. A nice example is a lower bound for the number of comparisons needed to find the minimum and the maximum at the same time. Said number is $\lceil 1.5 n \rceil - 2$. You can try to construct the algorithm and prove its optimality, or just have a look at the paper.


Computation of iterated logarithm function

$\lg^* n$ is just the minimum number of times you need to apply the $\lg$ function to $n$ in order to obtain a number that is smaller than or equal to $1$.

For example, assuming that you are working with base-2 logarithms and that $n=65536$ you have the following:

$\lg^{(0)} 65536  = 65536$,
$\lg^{(1)} 65536  = \lg 65536  = 16$,
$\lg^{(2)} 65536  = \lg 16  = 4$,
$\lg^{(3)} 65536  = \lg 4  = 2$,
$\lg^{(4)} 65536  = \lg 2  = 1$.

As you can see $4$ is the smallest integer value of $i \ge 0$ for which $\lg^{(i)} 65536 \le 1$. Therefore $\lg^* 65536 = 4$.


Is the Source Coding Theorem straightforward for uniformly distributed random variables?

The theorem you quote is not stated formally, so it is in fact impossible to prove it. That said, the idea behind the source coding theorem is that a variable of entropy $H(X)$ behaves (roughly) as if it was uniformly distributed on $2^{H(X)}$ values. When the distribution of $X$ is uniform, the theorem becomes trivial, once stated formally. So it's a good idea for you to look up a formal statement of the theorem, and then verify that it indeed holds for uniformly distributed random variables.


Minimum and maximum of sum of inverse degree of a graph

Nice question!

There is no simple closed form of $D$ for general graphs that involves $|V|$ since $D$ can take at least two different values for any connected graph with more than 2 vertices. $D=1-\frac1{|V|}$ for a start graph and $D=\frac{|V|}4 > 1-\frac1{|V|}$ for a cycle graph. In fact, I would believe that the number of different values of $D$ for a graph of $n$ vertices grows exponentially with respect to $n$.

Yuval's tight lower bound
Claim: $D \geq 1−1/n$ for a connect graph with $n$ vertices, where the equality holds for and only for star graphs.
Proof. Let $G$ be a connect graph with $m$ edges. Since $G$ is connected, $m\ge n-1$, where the equality holds for and only for tree graphs. Let $e=\{u,v\}$ be an edge in $G$.
$$\begin{aligned}
d(u)+d(v) &= \Sigma_{s\in E,\, s \text { contains u}} 1 + \Sigma_{s\in E,\, s \text { contains v}} 1 \\
&= (1 + \Sigma_{s\in E,\, s \text { contains u},\, s\neq e} 1) + (1 + \Sigma_{s\in E,\, s \text { contains v},\, s\neq e} 1)  \\
&= 2 + (\Sigma_{s\in E,\, s \text { contains u},\, s\neq e} 1 + \Sigma_{s\in E,\, s \text { contains v},\, s\neq e} 1)  \\
&\le 2 + \Sigma_{s\in E,\, s\neq e} 1\\
&= 2 + (m -1)\\
&= m +1
\end{aligned}$$
The inequality above holds since the only edge that contains both $u$ and $v$ is $e$. The equality $d(u)+d(v)=m+1$ holds when every edge besides $e$ has a common vertex with $e$.
So,
$$
D = \sum_{e=\{u,v\} \in E} \frac{1}{d(u)+d(v)} \ge m\, \frac1{m+1} = 1 - \frac1{m+1} \ge 1-\frac1n
$$
The equality $D=1-\frac1n$ holds when there are $n-1$ edges in total and every two edge has a common vertex, which means the graph is a star graph.

There is no positive constant $k$ such that $D \geq |V|/k$, since $|V|/k$ goes to infinity while $1-1/|V|$ stays below 1 when $|V|$ goes to infinity.


Algorithmic consequences of algebraic formula for partition function?

It is my uninformed belief that Rademacher's formula is faster in practice (and perhaps in theory also) than the Bruinier and Ono formula. While Rademacher's asymptotic expansion is an infinite sum, we know that $p(n)$ is an integer, so if we have bounds on the tails of the expansion, we can use the formula to compute $p(n)$. According to Calkin et al., "the exact formula of Rademacher yields a very fast algorithm".

Bruinier and Ono describe what would take to implement their algorithm in Section 5 of their paper. The first step is to determine representatives for $\mathcal{Q}_n$, of which there are $h(-24n+1)$. According to Soundararajan, we should expect $h(-24n+1) = \Theta(n)$, so the formula would involve $\Theta(n)$ summands. That makes it worse than Euler's formula for $p(n)$ (computationally speaking), though the latter admittedly requires $\Omega(n)$ memory.


The other answers are good, I just wanted to make it explicit that currying for dependent types is
$$
\textstyle
\prod (x : A) . \prod (y : B(x)) . C(x, y)
\ \cong \
\prod (p : \sum (x : A) . B(x)) . C(\pi_1(p), \pi_2(p))
$$
which is more suggestive in Agda-style notation:
$$
(x : A) \to (y : B(x)) \to C(x,y)
\ \cong\
(p : (x : A) \times B(x)) \to C(\pi_1(p), \pi_2(p))
$$
In your case, replace $\Pi$ and $\Sigma$ with $\forall$ and $\exists$.


For AVL Trees why is keeping a trit (left heavy, right heavy or balanced) sufficient?

The core argument is that the balance can never change by more than one when inserting or deleting a single key; of course, since heights can only change by at most one.

That way, knowing the old balance (which is in $\{-1,0,1\}$) and if (and how) subtree heights changed is enough to know the new balance (which is in $\{-2,1,0,1,2\}$).
If the balance is $-2$ or $2$ we rotate, of course, and restore balance (in that node).

In order to prove this, simply write out all possible cases of old balances and changes due to insertion or deletion.


Both computability and complexity are theoretical abstractions. A theoretical abstraction is most useful, if the gap between theory and practice is small.

It is well known that there is a large gap between a problem whose solutions is computable in theory, and one whose solution is computable in practice. Complexity theory managed to shrink that gap considerably, to the point where the remaining gap is caused by factors like cache behavior, parallelization, large scale distribution and similar advanced practical issues.
Computability theory has been able to prove that certain problems can't be solved. One might believe that there can't be any gap between theory and practice here, but this is not the case. It seems like Gödel's incompleteness theorems from 1931 would prove that the consistency of the Peano axioms can't be decided. However, Gentzen proved the consistency of the Peano axioms in a paper published in 1936. I know that there is a nice theoretical explanation for this, but I'm (still) unable to judge the practical consequences, and I guess I'm not alone in this.
Complexity theory still struggles to rigorously prove lower bounds for most important practical problems, even so it slowly advances in this direction. One may question whether these theoretical lower bounds are important at all, because we have no guarantee that the practical lower bounds have to respect these theoretical bounds. However, it turns out that the practical lower bounds closely match the theoretical lower bounds, so that this objection is unfounded in practice.
The above comparison might suggest that computability theory is not much use in practice compared to complexity theory. However, things like the Chomsky hierarchy and a bunch of other similarly useful results should easily disprove this suspicion.


Let's suppose the input array is $A = [3,1,4,5,2]$.  When sorting this array using pancake sorting, only flips of prefixes of the array are allowed.  Flipping the first four elements, i.e. replacing $3145$ by $5413$, gives $A = [5,4,1,3,2]$. Then, flipping all five elements gives $[2,3,1,4,5]$, which brings the largest element to its correct position.  By repeating this process to bring the next largest element to the last-but-one position, and so on, the array can be sorted.

The number of flips required to sort an array of length $n$ is at most $2n-3$. This is because bringing the largest $n-2$ elements to their correct positions can be done using at most $2n-4$ flips (because at most two flips are required for each element, as mentioned in previous paragraph).  Finally, the elements in the first two positions can be sorted using at most one flip.

The problem of finding the minimum number of flips to pancake-sort an array is still open.


Do correlated inputs imply existence of efficient communication protocols?

Deterministic communication complexity depends only on the support of the input distribution (the "promise"). Even if $H(X|Y),H(Y|X) < 1$ the distribution $(X,Y)$ could have full support, so the $\Omega(n)$ bound still holds.


DFAs that must reach a certain state at least once

If it happened that $F \{r\}$, then that would also happen to be a DFA to which you wouldn't have to do anything to answer the question, but it doesn't cover the case where $r \notin F$.

To rephrase the question a little, imagine you have a DFA $M$ that accepts language $L$, and someone picks a random state $r\neq s_{0}$, can you construct a DFA $M'$ that accepts language $L' \subseteq L$ where $s \in L'$ if it's in $L$ and it makes $M$ use state $r$?

Note that you don't get to pick $r$, it's essentially given as part of the input.

Taking it a little beyond your question, the answer is yes, it's possible, the trick is to do something special when you reach $r$.

A slightly more direct hint:

   Make a copy of $M$'s states (including accept status), cancel the accept status of any original states, and change the transitions out of $r$ to point to the counterparts in the duplicated set.


Gödels (first) incompleteness Theorem and the Halting Problem - How limiting is it?

The halting problem being undecidable has lots of practical relevance, here is a quick example:

Writing anti-virus software is hard: We can't decide whether a given piece of code is malicious because if we could we could decide the halting problem.

To see this take a piece of code which takes as input a Turing machine $M$ and an input word $w$ and does something malicious if and only if $M$ halts on input $w$. If we could decide whether a given piece of code were malicious then we could decide whether this piece of code was malicious but then we would be able to decide the halting problem, which we know we cannot do.

What this is saying is that there is no perfect anti-virus software, it can't be done. That doesn't mean we shouldn't try to write anti-virus sotware, just that we will never be able to write a perfect one. In fact any statement about deciding what programs do is undecidable (see  Rice's theorem).

With respect to Godel's theorem, Goodstein's theorem is an example of a statement which is unprovable using the Peano axioms.


Closure properties of non-context-free languages (concatenation & complement)

As for closure under complementation -- consider the following hint: context-free languages are not closed under complementation.

Regarding concatenation, this is slightly more tricky, but non-context free languages are not closed under complementation.

There are many ways of finding counterexamples for the latter, one is the following "trick":

Let $L$ be some non-context free language over some alphabet $\Sigma$, that does not contain $0,1$. Now define two languages: $A=(1\cdot \Sigma^*)\cup (0\cdot L)\cup \{\epsilon\}$ and
$B=(0\cdot \Sigma^*)\cup (1\cdot L)\cup \{\epsilon\}$

It is not hard to prove that neither $A$ nor $B$ are context free, basically due to presence of $L$.

However, we have that $A\cdot B=\{0,1\}\cdot \Sigma^*\cup \{\epsilon\}$, which is regular (and in particular context-free).


Context-free grammar how to have unequal number of a's on either side of b

Equal numbers of a’s on either side, then the middle is replaced by a+b or by ba+.


Is there an implicit condition OPT<P(|input|) in approximation schemes?

FPTAS is commonly used for optimization problems whose associated decision problem is in NP.  For those problems, it is guaranteed that the optimal solution has polynomial size (that's part of the definition of NP), so this issue does not arise.


Every nonempty context-free language has an ambiguous grammar. Consider any context-free grammar for the language with starting symbol $S$. We add new non-terminals $S',A',B'$, make $S'$ the new starting symbol, and add the following rules:
$$
\begin{align*}
&S' \to A' \\
&S' \to B' \\
&A' \to S \\
&B' \to S
\end{align*}
$$


An algorithm to turn descending order into ascending order, but why correct?

This is an interesting algorithm.

Conventions

Array indexes start with 0. Note this convention is different from the convention used in the question. This convention helps us see what is going on more easily.

All arrays have length $n=2^m$ for some positive integer $m$.

Given any array $b_0, b_1, b_2, b_3,\cdots, b_{n - 2}, b_{n-1}$, the magic shuffle $M$ maps it to the array $b_1, b_3, \cdots, b_{n-1}, b_0, b_2, \cdots, b_{n-2}.$ Please note that I avoid using the term "sort" since this algorithm is hardly about sorting.

Let $A_0$ be the array $a_0, a_1, \cdots, a_{n-1}$ (that is, $A_0[i]=a_i$). Define $A_k$ recursively by $A_{k+1}= M(A_k)$.

Claim: $A_m$ is the reverse of $A_0$, which is $a_{n-1}, a_{n-2}, \cdots, a_0$.

Proof of the claim. For an array $B$, we can check by the definition of the magic shuffle, $$M(B)[i] = \begin{cases} B[2i+1] & \text{ if }i\lt 2^{m-1},\\
B[2(i-2^{m-1})]&\text{ if } i\ge 2^{m-1}.\end{cases}$$

For an integer $i=i_{m-1}2^{m-1} + i_{m-2}2^{m-2} + \cdots + i_12 + i_0$, where $i_t\in\{0,1\}$, let $(i_{m-1}i_{m-2}\cdots i_1i_0)_2$ be its representation in base 2. We can easily check that

$$M(B)[(i_{m-1}i_{m-2}i_{m-3}\cdots i_1i_0)_2] = B[(i_{m-2}i_{m-3}\cdots i_1i_0\overline{i_{m-1}})_2]$$
where $\overline{x}=1-x$ for $x=0,1$. So we have
$$A_1[i] = M(A_0)[i] = A_0[(i_{m-2}i_{m-3}\cdots i_1i_0\overline{i_{m-1}})_2]$$
$$A_2[i] = M(A_1)[i] = A_1[(i_{m-2}i_{m-3}\cdots i_1i_0\overline{i_{m-1}})_2] = A_0[(i_{m-3}\cdots i_1i_0\overline{i_{m-1}}\overline{i_{m-2}})_2]$$
$$\cdots$$
$$A_{m-1}[i] = M(A_{m-2})[i] = A_{m-2}[(i_{m-2}i_{m-3}\cdots i_1i_0\overline{i_{m-1}})_2] = A_0[(i_0\overline{i_{m-1}}\overline{i_{m-2}}\cdots\overline{i_2}\overline{i_1})_2]$$
$$A_m[i] = M(A_{m-1})[i] = A_{m-1}[(i_{m-2}i_{m-3}\cdots i_1i_0\overline{i_{m-1}})_2] = A_0[(\overline{i_{m-1}}\overline{i_{m-2}}\cdots\overline{i_2}\overline{i_1}\overline{i_0})_2]$$

Since $i + (\overline{i_{m-1}}\overline{i_{m-2}}\cdots\overline{i_1}\overline{i_0})_2 = (\overline1\overline1\cdots\overline1\overline1)_2 = n-1$, we have proved the claim.

An exercise

Let $a_0, a_1, \cdots, a_{n-1}$ be an array of length $n=2^m$ for some positive integer $m$. For each step from 1 to m, repeat the following shuffle. For each term in the front half of the array, insert right before it the $n/2$-th term after it. Here is the result array after each shuffle for $n=16$.

[0]  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16
[1]  9  1 10  2 11  3 12  4 13  5 14  6 15  7 16  8
[2] 13  9  5  1 14 10  6  2 15 11  7  3 16 12  8  4
[3] 15 13 11  9  7  5  3  1 16 14 12 10  8  6  4  2
[4] 16 15 14 13 12 11 10  9  8  7  6  5  4  3  2  1

Show that we will obtain the initial array reversed in the end of $m$ shuffles.

If you consider the array as a deck of cards, then this shuffle is the (perfect) in (riffle) shuffle. In particular, if you repeat 10 in shuffles on a deck of 32 cards, you will end up with the deck of cards in its original order.


We don't consider the order of elements since what we are counting is the number of graphs on the vertex set $\{1,\ldots,n\}$ which are trees, that is, connected and having no cycles.

This is the usual graph-theoretic notion of tree. In computer science we often think of trees as rooted objects with ordered children, which is a similar but different concept.


Revisiting Fixed Point: What does it mean in the world of computer science?

A fixed point of a function $f$ is an element $x$ satisfying $f(x) = x$. A solution to a recursive equation can be put in that form.


Are finite-domain binary constraint satisfaction problems solvable in polynomial time?

I don't know, but if you manage, make sure to let us know.

The reduction seems easy indeed, with $d$ mapping to the number of colors and each constraint to an edge.

However, a polynomial-time algorithm for any $\mathcal{NP}$-complete problem exists if and only if $\mathcal{P} =\mathcal{NP}$; doing what you ask would imply $\mathcal{P} \neq \mathcal{NP}$.


Is it possible to eliminate the unit rules in this?

You can always eliminate unit rules. In fact, every context-free grammar can be massaged to one in Chomsky normal form, and there are several algorithms doing that. Their treatment of unit rules is more subtle than what you suggest.


Hash function floating point inputs for genetic algorithm

Hashing an array of floats

You need some hash function that:

low computational cost
low probability of generating the same hash value for two input vectors = evenly distributed hashes

If you language/library have some function for hashing float array, it should be ok.

For example, this function is what Java would do with an float array (it's not a direct copy of Java library):

int hashFloatArray(float[] arr) {
    //this is done in Arrays.hashCode()
    int h = 1;
    for (int i = 0; i < arr.length; i++){
        int floatAsInt = Float.floatToIntBits(arr[i]);
        //in C: int floatAsInt = *(int*)(&arr[i]);
        h = 31 * h + floatAsInt;
    }
    //this is done in HashMap
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

Finding matching hashes

Storing hashes instead of whole float arrays reduces amount of memory needed. Space of hashes is smaller than the space of float arrays, so matching hashes never give 100% certainty that original objects (float arrays) where identical. The longer hashes the smaller is the change of hash collision (situation when two different inputs produce the same hash).

Array indexed with hashes (as OP proposed)

Indexing array with hashes means that the length of the array must be 2^k where k is length of key in bits. For example: Assuming single field of array occupies 1 byte (boolean variable usually occupy 1 byte). Using 30 bit key requires 2^30 * 1 bytes = 1GB of memory (O(2^k) space complexity). As mentioned before:

shorter key = smaller array = higher chance of hash collision
longer key = bigger array = lower chance of hash collision

Hash table (Hash set)

Hash table is a data structure that can be used to implement hash set. Main advantage of hash set is it's O(1) average time complexity combined with O(n) space complexity.

You can use hash set to store and effectively find:

long hashes (64 bit?) of float arrays without wasting memory
float arrays themselves (if you have enough memory)

Hash sets are available in standard libraries of almost all programming languages.

java.util.HashSet in Java
unordered_set in C++11
set in Python

Why comparing and hashing floats is a problem?

Let's take two float numbers: 1.2345678 and 1.2345679
The difference between them is small enough to have no influence on the quality of your Robot, but comparing 1.2345678 and 1.2345679 results in "not equal" and hashing them results in two different hashes. Introducing an "almost equal" term may be a good idea, but that can't be done with hashes.


If a problem $A$ is reduced to $B$, this implies that an algorithm $\mathbb{A}$ that solves $B$ can also solve $A$.

If $\mathbb{A}$ is a polynomial-time algorithm, then $B \in \mathbf{PTIME}$ and also $A \in \mathbf{PTIME}$.

If it is the case that when $\mathbb{A}$ is polynomial-time algorithm, this implies that $\mathbf{P} = \mathbf{NP}$, then $B$ is an $\mathbf{NP}\text{-hard}$ problem. Which means $A$ is also an $\mathbf{NP}\text{-hard}$ problem.

These statements answer questions 1, 2, and 4. However, your third question cannot be answered with the information you provided. This is because any problem in PTIME is also in NP, and therefore having a polynomial-time algorithm does not necessarily mean that $B$ has a polynomial-time algorithm. It might or might not have.


The C's are not the same, but your statement about the AND gate is right.

Unfortunately, the people who drew your full-adder decided to save space instead of maximizing readability. This image does a better job of showing the relationship between half adders and full adders, even though the circuit is identical to the one above:

If they'd just put the wire splitting points inside the grey boxes showing the half-adders instead of outside, they'd be perfect.

Here's a block diagram you can use to see the exact relationship between a half-adder and an adder.  It shows clearly something I find quite interesting about adders.  The 'or' at the end looks like it could swallow a carry if both half adders were to emit a carry bit at the same time.  It seems like we might need another half adder to resolve this, in a never ending chain.  However, if you run the truth tables for the half-adder, you find that it is impossible for both half-adders to carry at the same time.  Rejoice!


The data that will be carried in the 4th segment is 1200 why?we can know it by simpley look at the sequence number of the 6th packet -a packet's sequence number is in simple words:"im sending data from this certain number"
if we take a look at the 3th packet we can see that it was sent from the client to the server with a sequence number of 1030 and we can see in the 6th packet that the sequence number of it is 2230 which means a total 2230-1030=1200 of data was sent from the clinet to server in the 4th packet


Complete problem for $\mathrm{QP}$ (quasipolynomial-time solvable languages)

Question 1: NO

Question 2: NO

Question 1: Assume to the contrary that $\mathrm{QP}$ has a complete problem $\mathrm{L}\in\mathrm{QP}$.

Then, there exists $k$ such that $\mathrm{L}\in\mathrm{TIME}(2^{\mathrm{log}^k(n)})$. Consider an arbitrary problem $\mathrm{L}'\in\mathrm{QP}$, by completeness of $\mathrm{L}$, we have that $\mathrm{L}'\leq_p\mathrm{L}$, i.e there exists a many-one polynomial-time reduction $f$ from $\mathrm{L}$ to $\mathrm{L}'$. So, given any instance $x\in\Sigma^*$ with $|x|=n$, we first reduce $x$ to $f(x)$. Since $f$ is polynomial-time computable, we have that $|f(x)|=n^{O(1)}$. Now, we run the $2^{\mathrm{log}^k(n)}$ time-bounded TM deciding $\mathrm{L}$, and accept or refute accordingly.

We now estimate the time complexity of this TM for $\mathrm{L}'$. We have:
$$2^{\mathrm{log}^k(n^{O(1)})}=2^{O(1).\mathrm{log}^k(n)}=2^{O(\mathrm{log}^k(n))}$$

So, the whole class $\mathrm{QP}$ collapse to $\mathrm{TIME}(2^{O(\mathrm{log}^k(n))})$ violating the Time Hierachy Theorem.

Thus, $\mathrm{QP}$ does not have any complete problem.

Question 2: The unconditional lack of complete problem of $\mathrm{QP}$ unconditionally separates it from $\mathrm{NP}$, $\mathrm{co}$-$\mathrm{NP}$, $\mathrm{PP}$, $\oplus P$, $\mathrm{US}$, $\mathrm{PSPACE}$. But that is of no help for computational complexity theory, since the interesting nasty, stubborn classes such as $\mathrm{ZPP}$, $\mathrm{RP}$, $\mathrm{co}$-$\mathrm{RP}$, $\mathrm{BPP}$, $\mathrm{MA}$, $\mathrm{AM}$ all remain elusive to whether any of them has a complete problem.


Basic Question in networking - why max data size of ip datagram 65535 BYTES and not 65535 bits?

16 bits is not the size of the IP datagram; it is the amount of bits required to encode its length. Hence, you can have datagrams of length up to 65536 octets (i.e., bytes), as described in RFC 760:

  Total Length:  16 bits

  Total Length is the length of the datagram, measured in octets,
      including internet header and data.  This field allows the length of
      a datagram to be up to 65,535 octets.

Notice 65536 is not a prescribed length, that is, the length of the datagram is (or can be) variable.

Now, to answer your two questions:

  Do we say each 16 bit pattern is 1 IP datagram or all those 65536 patterns as 1 IP Datagram?

Each octet pattern of up to 16-bit length is a datagram. In informal parlance, a datagram is simply a packet which IP adds its header to. You could call the set of all possible patterns a "datagram space", though I doubt that's standard terminology. (You might care to ask that in a separate question.)

  If i consider all 65536 patterns as max data size, then max ip datagram size =65536 patterns size=65536∗16 bits =65536∗16/8 bytes =65536∗2 bytes

I'm not sure I see a question here. Though I suppose any one you had is answered by my remark about the datagram length above.