Scripting languages are a class of programming languages. This class is rather fuzzily defined.

One possible definition is that they're languages that are designed to automate small tasks, rather than to write large, complex programs. Because they are small tasks, the author tends to spend some time tweaking them, so it makes sense to make the path from source code to executable as simple as possible, and it doesn't get simpler than making the source code itself executable. Because they are simple tasks, the end-user might want to tweak them, too, so it makes sense to distribute them as source code. Because the tasks are relatively small and simple, there's little to be gained by static checking and optimization, so there's little value in using a compiler.

Another possible definition is that a scripting language is one in which the source code is executable. In other words, a scripting language is pretty much defined as one that's intended to be interpreted.

Few scripting languages are purely interpreted though. Most at least parse the whole file before starting execution. Many even compile to some form of bytecode that can be saved to disk.


Witness for the $EU(\phi_1,\phi_2)$ using BDDs

What you describe is symbolic model checking, and it is treated in this set of slides, using reduced ordered BDDs.

In a nutshell, you still do the fixpoint iteration, the main issue being how to do the transformation $Q\mapsto \phi_2\vee(\phi_1\wedge EXQ)$ on BDDs. The elementary operations you need are renaming (to replace unprimed by primed variables in $Q$, obtaining $Q'$), boolean operations (to form $\phi_2\vee(\phi_1\wedge R\wedge Q')$) and abstraction (to do existential quantifier elimination on the primed variables). The witness generation can then be done similarly forwards from the initial states, requiring at step $i$ that $s_i$ is in $Q_{n-i}$ as you did above.


The following answer assumes that each state in a DFA must contain an outgoing edge for each symbol. Otherwise, you might need one state fewer.
Let us say that two words $x,y$ are equivalent modulo $L$ if for any word $z$, either both $xz$ and $yz$ are in $L$, or both of them are not in $L$.
If two words $x,y$ are not equivalent modulo $L$, and $A$ is any DFA accepting $L$, then the state of $A$ after reading $x$ must be different from the state of $B$ after reading $y$ (why?).
As a consequence, if $x_1,\ldots,x_n$ is a collection of words, any two of which are not equivalent modulo $L$, then any DFA for $L$ must contain at least $n$ states.
(Furthermore, it is known that if the minimal DFA for $L$ contains $n$ states, then we can find $n$ such words: for each state, we take some word leading to it; but we don't need this direction here.)
In your case, the following words are pairwise inequivalent: $\epsilon, 0, 1, 10$. To show this, we need to consider all six pairs:

$\epsilon,0$ are inequivalent since $10 \in L$ but $010 \notin L$.
$\epsilon,1$ are inequivalent since $0 \notin L$ but $10 \in L$.
$\epsilon,10$ are inequivalent since $\epsilon \notin L$ but $10 \in L$.
$0,1$ are inequivalent since $00 \notin L$ but $10 \in L$.
$0,10$ are inequivalent since $0 \notin L$ but $10 \in L$.
$1,10$ are inequivalent since $1 \notin L$ but $10 \in L$.

This shows that every DFA for $L$ contains at least $4$ states. Conversely, there is a DFA for $L$ containing $4$ states, which I will let you figure out.


Prove L = L(R) based on a regular expression

In the expression you propose it seems you require the string to start with 011 rather than have it as an arbitrary substring.

So in my dialect of RegEx the expression would be (0+1)*011(0+1)*010. By definition that would specify all strings of the form $u 011 v 010$ where $u,v$ are arbitrary. This means all those strings have 011 as subword and end in 010.

We also have to explain the converse. That every string with that subword and suffix is covered by the expression. For that it suffices to note that 011 and 010 cannot overlap. So, 010 must come before 011. Which means it is of the form  $u 011 v 010$.


Why is casting float to double applicable?

This is really not a computer science question...

First, you failed to distinguish between "casting" and "conversion". In many computer languages, "casting" is an explicit instruction to convert a value from some type to another type. For example in C,

double d = 3.7;
float f = d; // Automatic conversion, no casting

double d = 3.7;
float f = (float) d; // Casting as requested by programmer
double e = (float) d; // Casting to float, followed by conversion to double

So what you were really talking about was value conversion, not casting. (Being precise in what you write is arguably part of computer science).

The effect of any conversion is defined by the computer language in question. "Shrinking down (leveraging) the significant bits" is something that doesn't make any sense at all. Bits don't have a size, you can't shrink them. And the word "leveraging" doesn't mean what you think it means. I assume you meant "removing the significant bits".

But that's not how value conversion is defined. In C and C++, it is defined in terms of values. A conversion between scalar types results in the exact same value if the old value can be represented in the new type. If the value cannot be represented, then there are rules for conversions between integer types; in some cases the value is modified according to rules in the language, sometimes the value is modified according to implementation defined rules (and "implementation defined" has a very specific meaning in C and C++ that you need to learn), or it is undefined behaviour.

Converting non-integral floating point values to integer values first rounds the value towards zero, and then other rules apply. Conversion between floating-point values will produce the original value if possible, rounds according to rounding rules in the language if that is not possible, with additional rules if the value is too large to represent.

Do you notice how nothing at all here is talking about bits?

Swift distinguishes between conversions that cannot fail and conversion that can fail. Conversions that can fail produce an optional value. Which is a totally different thing. For example, you cannot convert UInt to Int, only to an optional Int. You cannot convert Int64 to Int32, only to an optional Int32. But you can convert Int32 to Int64, because it is a conversion that cannot fail.


Is every reduction function $f \in O(n)$?

I'm not sure exactly what you mean. In essentially all interesting cases, $L_1$ is infinite, so you can't say that $|L_1|=n$. Second, the function $f$ is a function from strings to strings, so it doesn't make sense to ask if it's $O(n)$ because $O(\cdot)$ is a class of functions from numbers to numbers.

However, you're most probably asking if all reductions are in $\mathrm{TIME}[O(n)]$, i.e., if they can all be computed in linear time. They can't.

By the time hierarchy theorem, for any $r>s$, there are languages in $\mathrm{TIME}[O(n^r)]$ that are provably not in $\mathrm{TIME}[O(n^s)]$. So, consider any problem $X$ that is P-complete under polynomial-time reductions. We must have $X\in\mathrm{TIME}[O(n^s)]$ for some $s$. By the time hierarchy theorem, there is some langauge $Y\in\mathrm{TIME}[O(n^{s+1})]\setminus\mathrm{TIME}[O(n^s)]$.  Since $X$ is P-complete and $Y\in{}$P, there must be some polynomial-time reduction $Y\to X$. However, this reduction cannot run in linear time. If the reduction did run in linear time, there would have to be some $k$ such that it transforms every length-$n$ instance of $Y$ into an instance of $X$ with length at most $kn$ (a function running in linear time can only produce linearly much output). But, then, we would be able to decide $Y$ via the reduction in time
$$O(n) + O((kn)^s) = O(n) +O(n^s) =O(n^s)\,,$$
contradicting our choice of $Y\notin\mathrm{TIME}[O(n^s)]$.

Note that, in general, if we're talking about computability rather than complexity, we only care that the reduction is computable – we usually don't care about its time or space complexity at all. However, in other contexts, we do care about linear-time reductions, for example in proving problems hard under the exponential time hypothesis.


Logic programming with substructural logics has been studied, starting in the second half of the 90's. I am not an expert, but I can probably provide enough references to get you going.

There is Dale Miller's Lolli, a programming language for linear logic programming.

Major research was carried out by Frank Pfenning and his coworkers and students. For example:

Frank Pfenning: lecture notes on Linear logic programming, part of a course on linear logic (the web site also has some software)
Iliano Cervesato, Frank Pfenning: A Linear Logical Framework
Jeff Polakow, Frank Pfenning: Properties of Terms in Continuation-Passing Style in an Ordered Logical Framework
Frank Pfenning, Robert J. Simmons: Substructural Operational Semantics as Ordered Logic Programming

I am pretty sure someone implemented logic programming for ordered linear logic, poke around the work done by Jeff Polakow and Frank Pfenning. I don't seem to be able to find it right now.


Who invented the state elimination algorithm for converting finite automata into regular expressions?

According to my information the technique is by J.A. Brzozowski and E.J. McCluskey. The method is described in Signal Flow Graph Techniques for Sequential Circuit State Diagrams, IEEE Transactions on Electronic Computers, 67 - 76, 1963.


Number of solutions to linear system of equations over GF(2)

You can take any subset of the free variables, and then correct any resulting sum using the fixed variables.

Thus, after Gaussian elimination the total number of solutions is  $2^f$ where $f$ is the number of free variables.


What usage is the delta defined in the polynomial hierarchy?

The polynomial hierarchy is an analog of the arithmetical hierarchy in recursion theory, which also has $\Sigma,\Pi,\Delta$, and several other hierarchies also have $\Delta$ terms.

The usage is exactly the same as the usage of $\Sigma_i^P$ and $\Pi_i^P$. For a given problem, you try to find its exact location in the polynomial hierarchy. If a problem is in $\Delta_i^P$ then it can't be $\Sigma_{i+1}^P$-hard (unless the polynomial hierarchy collapses), but perhaps it is $\Delta_i^P$-hard. So you might need these classes for some problems.


Hamiltonian path and minimum spanning tree

No.  Every path is a tree, but not every tree is a path.  Therefore,  the minimum spanning path might be more expensive than the minimum spanning tree.

If you work through some examples you should be able to find an explicit counterexample.  I'll let you have the joy of finding it on your own.


A language $L$ is in $P$, we have an algorithm $A$ that runs in polynomial time that recognizes it.

It is easy to show that the complement of $L$,  $\bar{L}$, is in $P$. The algorithm to recognize it is to simulate $A$ but just invert the answer.

As long as $\bar{L}$ is in P (thus in NP), $L$ is in $co-NP$.


What is the computational complexity of intuitionistic propositional logic?

A quick google search shows that the problem is PSPACE complete, a result apparently first proven by R. Statman.


Pumping Lemma for $L = \left \{ a^{c}\mid \text{c is a composite number} \right \}$

Let $p$ be the pumping length, and choose a prime $q > p$. The word $a^{q^2}$ is in $L$, and so it can be written as $a^{q^2} = uvwxy$ so that $|vwx| \leq p$, $|vx| \geq 1$, and $uv^iwx^iy \in L$ for all $i \geq 0$. If $|vx| = \ell$ then $1 \leq \ell \leq p$, and for all $i \geq 0$, $q^2 + (i-1)\ell$ is composite. Since $\ell \leq p$ and $q$ is prime, $(q^2,\ell) = 1$, and so Dirichlet's theorem about primes in arithmetic progressions shows that for infinitely many $i \geq 0$, $q^2 + (i-1)\ell$ is prime. We have reached a contradiction.

An easier argument uses Parikh's theorem, which states that a unary language (a subset of $a^*$) is context-free iff it is regular. In particular, it is enough to show that $L$ isn't regular. Since the complement of a regular language is regular, it's enough to show that $\overline{L} = \{ a^k : k \text{ is prime}\}$ is not regular. It is easier to use the pumping lemma for this language. Given a pumping length $p$, choose a prime $q > p$. As before, there must exist $\ell \leq p$ so that $q + (i-1)p$ is prime for all $i \geq 0$. However, for $i = q+1$ we get $q + (i-1)p = q + qp = q(p+1)$, which isn't prime.


CFG for words that are not a concatenation of the same word

The question has been asked before, but since it's faster to describe the answer than to find the previous question, I'll outline the answer here.

We can characterize words in $L$ as belonging to one of two classes:

Words of odd length.
Words $z_1 \ldots z_n w_1 \ldots w_n$ where $z_i \neq w_i$ for some $i$.

It is easy to generate words of the first type. As for words of the second type, for fixed $i$ and $n$ we can generate them using rules of the form $\Sigma^{i-1} a \Sigma^{n-i} \Sigma^{i-1} b \Sigma^{n-i} = \Sigma^{i-1} a \Sigma^{i-1} \Sigma^{n-i} b \Sigma^{n-i}$ and its counterpart with $a,b$ replaced by $b,a$. I'll let you figure out how to generate all of these words (for all $i,n$).


When is an ATM network connection superior to an IP connection?

AFAIR ATM was specifically designed to also transfer real time data like voice. This requires guaranteed properties like bandwidth and latency.

IP can't give those guarantees as it looses packets and reorders packets.

Also ATM is connection oriented, whereas IP needs the complexity of TCP to get that.


Conversion from nondeterministic PDA to deterministic PDA

There are languages accepted by nondeterministic PDAs that cannot be accepted by deterministic PDAs. Perhaps the easiest way to see this is to consider inherently ambiguous context-free languages. As context-free languages, they are accepted by some nondeterministic PDA. On the other hand, every language accepted by a deterministic PDA has an unambiguous grammar, so they cannot be accepted by any deterministic PDA.


Is the ability to do depth first search a proof of Turing Completeness? Can we write a non-TC automaton that does DFS?

Most functions you'll ever deal with in practice are primitive recursive, a model of computation that is properly less powerful than TMs.

More specifically, the problem from the question can be implemented on linear-bounded automata (LBA), a model of computation that is equivalent with context-sensitive grammars -- properly less powerful than TMs.


What complexity class is this set of grammars? RE?

That grammar is unrestricted (not context free, as there are right hand sides shorter than the corresponding left hand side). The languages they generate are recursively enumerable, recursive only in special cases.


number of ways evaluation of expression such that value not changed

What's wrong with (i) + j + k ?

I live in a world where floating-point arithmetic has rounding errors, and where integer arithmetic has overflow checks, so (i + j) + k and i + (j + k) are most definitely not the same, for example if i is a large positive integer, and j, k are two large negative integers then the second one can produce an overflow (crash) while the first one doesn't.


How to calculate virtual address space from page size, virtual address size and page table entry size?

Since Logical address size is 47 bit, that means logical address space is 2^47 bytes ( assuming system is byte addressable ).

Otherwise in general if the logical address is not given then also it can be found.

Page size is 16 KB
Logical address size is 47 bit
3 levels of page tables; all have the same size
Page table entry size is 8 byte

From the information assuming the entire page is being used,

number of entries in each page = (page size) / (page table entry size ) = (2 ^ 11)

Now consider the outermost page table. It has 2 ^ 11 entries, which means the second level page table has 2 ^ 11 pages and each page has 2 ^ 11 entries.

Going by this logic it can be derived that the number of pages in process ( logical address space ) = 2 ^ 33

And given page size = 16 KB
Therefore, the logical address space size = ( 2 ^ 33) * 16 KB = 2^47 bytes


Visual Studio Code
Supports many languages including C/C++. It's a very simple IDE. Have a look at it.
https://code.visualstudio.com/


Why is the set for which a decision problem is true called a "language"?

I believe a lot of this came out of linguistics research. People wanted to write down a formal description (grammar) of, e.g., the English language. By extension, the set of strings defined by any grammar is a language and, since unrestricted grammars are Turing-powerful, any computable set of strings is the language of some grammar.


Is it possible to simplify $O(A \times B \times C + A^B)$ into $O(A^B)$

No, it is not possible. The function $ABC$ is $O(ABC + A^B)$ but not $A^B$, since for no $M$ is it the case that $ABC \leq MA^B$ for large enough $A,B,C$; for any "large enough" $A,B$, this would imply that $C = O(1)$ is bounded, but $C$ need not be bounded.


How to prove greedy algorithm for number partitioning?

There is nothing to prove about the statement you highlight. It is an empirical statement.

In order to have something to prove, you will need to formulate this claim formally in some way or another. There are many options, including average-case analysis, smoothed analysis, and restricted instances (which is what the statement points at). Until you have done so, it is impossible to prove or refute the statement.

The example given in your source shows that, in fact, the heuristic doesn't always succeed. Perhaps it gives a good approximation in some circumstances. The statement, unfortunately, doesn't hint at a provable claim which has any chance of being true.


Is it possible to entangle more than 2 qubits? If so, is it useful?

Ok, entanglement just clicked for me and totally makes sense.

Yes it is completely possible to entangle more than two qubits!

Entanglement is a fancy word with a really simple meaning.

In quantum computing, you can modify the probabilities of values being read.

If you have two qubits, normally there is some probability for each of the possible states: reading a 0 for each qubit, reading a 1 for each qubit, reading a 0 for qubit a and a 1 for qubit b, and reading a 1 for qubit a and a 0 for qubit b.

When you modify probabilities such that any of these probabilities drop to zero, it limits the possibilities of what can happen when you measure the qubits.

Most specifically, in the two qubit case, you could eliminate the situations where they disagree (states $|01\rangle$ and $|10\rangle$), and make it a 50/50 chance between the states of them both being on, or both being off.

Now, they have NO CHANCE of disagreeing when you read their values.

Who knows how reality "implements" this situation, since distance doesn't matter, but there you go... it's pretty darn simple.

A very simple 3 qubit entanglement would be this: $|000\rangle$, or this: $1/\sqrt{2}(|000\rangle + |111\rangle)$


Different topologically sorted order based on DFS vertex ordering

A topological ordering of a DAG $G$ is any ordering $v_1,\ldots,v_n$ of the vertices in which $(v_i,v_j) \in G$ implies $v_i \leq v_j$. That is, if there is an edge from $x$ to $y$, then $x$ must precede $y$ in the ordering (assuming $x \neq y$). A DAG can have many topological orderings. For example, the empty DAG on $n$ vertices has $n!$ topological orderings. In contrast, a path $v_1 \to v_2 \to \cdots \to v_n$ has a unique topological ordering.


It's an apples and oranges comparison.
When you want something to be truly random, you must use a TRNG. Examples include a lottery, or a secret/private key in cryptography.
When you want something repeatable, you must use a PRNG. An example is a large secret keystream for XOR encryption, generated (imperatively: identically) on both the transmit and receive side from a short common shared secret key.

What are the advantages of using PRNG over TRNG?

PRNGs can be portable to different computers and languages. Their implementations are easy to validate. They have a mathematical security definition, and it's easy to make fast PRNGs that experimentally match it (on the other hand, we don't know how to prove that).
TRNGs are not portable (they are not entirely software anyway), and are much more complex (typically there's a hardware source, tests ofthat at power-up and in use, and a conditioning stage). It's hard to convince a neutral party that a TRNG works.
In practice, the best choice is almost always a Cryptographically Strong PRNG, seeded by a public constant when one wants repeatability, or seeded by the output of a TRNG (or a secret constant changed manually as needed, perhaps combined with a counter, or time from a truly strictly increasing reference) otherwise. The CSPRNG will mask any small imperfection of the TRNG there will be, and have a high throughput: modern CSPRNG are extremely fast (in the order of 10 CPU cycles per byte generated for Salsa20, which supports "skip-ahead").


One way to show that SSUM is NP-hard is by reduction from SUBSET-SUM. The idea is to replace each number $n_i$ by two numbers $Mn_i + \epsilon_i$ and $\epsilon_i$, where $M$ is a "large" integer and $\epsilon_i$ is a "small" integer. By varying $\epsilon_i$ you ensure that all numbers are different. You set your target at $MT+\delta$, where $T$ is the original target and $\delta = \sum_i \epsilon_i$. Further details left to you.


Is there any algorithm that finds the time complexity of another algorithm provided that it halts?

I think this is correct and incorrect at the same time. It depends on how we define the problem we want to solve.
Formulation I
If we are interested in an algorithm that given $\langle M, w\rangle$ will tell you how much time $M$ runs on $w$ (assuming it halts), then there is such an algorithm: emulate $M$ on $w$ and count the number of steps it does until it halts.

Formulation II
But, if we are interested in an algorithm that given $\langle M\rangle$ will give you a function $f:\mathbb{N}\rightarrow \mathbb{N}$ that bounds the running time of $M$, things get a little bit more complicated.
First, how do we describe a function $f$ with finite storage? there are $|\mathbb{N}^\mathbb{N}|=2^{\aleph_0}$ functions, and $2^{\aleph_0}$ words in $\{0,1\}^*$ as well. This means there is some way to map each word to a function and vice versa. We will ignore from now the problem of computing this mapping between words and functions, and will still show there is no algorithm for the problem.
Assume towards contradiction there is some $\hat M$ that solves our problem. Let us create a new machine $M'$ that given input $\langle M\rangle $, will first emulate $\hat M$ on $M$ to find some $f$ which describes the upper bound on the time it takes $M$ to halt (assuming it halts). Then, $M'$ will enter a loop for $f(|\langle M'\rangle |) + 1$ steps.
Now, consider what happens when $M'$ runs on the input $\langle M'\rangle$. $\hat M$ will give an upper bound $f$ on the running time of $M'$, and $M'$ will run for more than $f(|\langle M' \rangle|)$ steps, contradicting that $f$ is an upper bound (since the original input of $M'$ was $\langle M'\rangle$).
Thus, no such $\hat M$ can ever exist!


Calculating the number of non-intersecting routes in an Euclidean graph

There are exponentially many such routes.

Think of a sequence of $n$ diamonds.  At each diamond, you can go either left or right, independently of what you do at all other diamonds.  This leads to $2^n$ paths, each of which is non-intersecting.  Now the complete graph on those vertices contains all of these paths, plus some more, so this is a lower-bound on the number of non-intersecting paths.

Therefore, you can't hope to find the optimal one in polynomial time by guessing or enumerating non-intersecting routes.

You probably could have guessed or suspected this, from the fact that Euclidean TSP is NP-complete....


Determine if an array is divisible in pairs of equal sum

You sort the array in increasing order.

If you pair an element equal to the largest element with any element that is larger than the smallest element, then pairing the smallest element with any other element will give a smaller sum, and therefore a different sum.

Therefore, to find pairs that all have the same sum, you must pair an element equal to the largest with an element equal to the smallest, and then repeat for the remaining elements. This will give you pairs with equal sums if it is possible. If not possible, then of course you won't get equal sums.


Assuming for simplicity that $n$ is even, if we guess that $T(n) \leq C^2n$ then we can prove our guess by induction (for powers of 2) for an appropriate value of $C$ since
$$
T(n) = 2T(n/2) + 1 \leq C(n/2)^2 + 1 = \frac{C}{4} n^2 + 1
$$
is smaller than $Cn^2$ as long as $C \geq 4/3$ (assuming $n \ge 1$).


Conditions for a binary tree being balanced

This is an interesting question. How do we define a family of binary trees is balanced?

A generalized definition of balanced binary trees

One of the most general definitions is that the height of a tree $T$ in the family is $O(\log n)$, where $n$ is the number of nodes in $T$. In other words, there is a constant $c$ such that the height of each tree $T$ in the family is no more than $c\log n$. We call such a family of binary trees balanced. Each tree in the family is called balanced (with respect to the family).

For example, the family of AVL trees is balanced. The family of red-black tree is balanced. For any given $0\lt \alpha\lt1$, $\alpha$-weight-balanced trees are balanced. A family of finitely many trees is balanced.

The family of all degenerated trees is not balanced.

$c$-height-balanced trees are balanced

Let $c$ be a constant. Let $T$ be a binary tree such that for each node of it, the difference in height between the two sub-trees is at most $c$. We call $T$ $c$-height-balanced. The family of $c$-height-balanced trees is balanced, which you have probably proved.

$O(\log n)$-average-height trees may not be balanced.

Let us call a family of trees that satisfies the condition (B) $O(\log n)$-average-height family of trees. Here is an example of an $O(\log n)$-average-height family of trees that is not balanced.

Let us start from a perfect binary tree with node $1,2, \cdots, 2^m-1$, where the children of node $i$ are node $2i$ and $2i+1$. Add node $2^m, 2^m+1, \cdots, 2^m+m^2-m$ to the tree so that the right child of node $j$ is node $j+1$ for all $j\ge 2^m-1$. Denote the tree thus obtained by $T_m$. The number of nodes in $T_m$ is $n=2^m+m^2-m$.

The rightmost nodes of $T_m$, $$2^1-1, 2^2-1, \cdots, 2^m-1, 2^m, 2^m+1, \cdots, 2^m+m^2-m$$ form a linear tree with $m+ m^2-m = m^2$ nodes.

The sum of heights of all nodes is

$$\begin{aligned}
\sum_{1\le i\le 2^m+m^2-m} h(i)
&= \sum_{1\le j\le m-1}\sum_{2^j\le i\le 2^{j+1}-2} h(i) + \sum_{0\le j\le m-1}h(2^{j+1}-1)+ \sum_{2^m\le i\le 2^m+m^2-m} h(i) \\
&= \sum_{1\le j\le m-1}(2^j-1)(m-1-j) + \sum_{1\le k\le m^2}(k-1) \\
&\lt m\sum_{1\le j\le m-1}(2^j-1) + \sum_{1\le k\le m^2}m^2\\
&\lt m2^m + (m^2)^2\\
&\lt 10m2^m\\
&\le 10mn.\\
\end{aligned}$$

So the average height of each node is not greater than $10m \le 10\log_2 n.$

However, the height of node $2^m+m^2-m$ is $m^2-1=\Theta((\log n)^2)$. So the $O(\log n)$-average-height family of trees $T_1, T_2, \cdots$ is not balanced.

Exercises

Exercises 1. Show that the height of a tree $T$ in a given balanced family of binary trees is, in fact, $\Theta(\log n)$.

Exercises 2. Construct an $O(\log n)$-average-height family of trees such that the height of a tree $T$ is $\Omega(\sqrt {n})$.

Exercises 3. Let $F$ be a family of binary trees such that the ratio between the heights of two subtrees with the same parent node is bounded for all parent nodes of all trees. In other words, there is a constant $c$ such that for every $T$ in $F$, for every node $v$ of $T$, the ratio between the heights of two subtrees of $v$ is at most $c$. In order to avoid dividing by zero, if any subtree of $v$ is empty, the height of that empty subtree is redefined as 1/2. We call $F$ height-ratio-bounded. Is a height-ratio-bounded family balanced?


Binary Search Tree: Replace $k$ min elements with their average

The following is either a proof, or an argument that runs in circles.

Given a binary search tree the ordered sequence of keys can be retrieved using the symmetric inorder traversal. Conversely any ordered sequence of keys can be stored in a binary tree with the BST property only if the keys are mapped precisely in inorder. (Proof: the root has a unique value as all keys the the left must be smaller, to the right must be larger. Use recusion for the subtrees).

Now take a BST tree and retrieve its keys in order. Take any consecutive segment of the keys and replace these keys by any value between the first and last of the segment. The result is again an ordered sequence of keys and remapping to the original tree will give again a BST.

Taking the minimum $k$ values and replacing with the mean is a special case.


Finding the language generated by a context-free grammar

Hint: What can you say about the number of $a$s and $b$s in the produced words?

  It would be very helpful if someone were able to provide some tips on
  solving these sorts of problems.

There is no one-size-fits-all recipe here. It is undecidable in general, whether two CFGs produce the same language or two CFLs are the same language. A useful method is trying to notice the properties which remain invariant during the productions.


Can not follow the example for max-flow-min-cut on Wikipedia

Max flow isn't 9 it is 7. 4 from s to 1 and 3 from s to 2.It cannot have more than that.You can see that it is also equal to min-cut.


Is Timsort more efficient than merge sort and why?

In terms of asymptotic complexity, timsort and merge sort have the same worst-case complexity: they both make $O(n \log n)$ comparisons to sort a list of $n$ elements.

Given a particular input, a particular implementation of timsort may or may not be faster than a particular implementation of merge sort.

Timsort is designed to have a maximum overhead over merge sort, i.e. it won't be more than a certain constant factor slower than merge sort, because it's based on merge sort, and only uses other techniques for small parts of the data.

Timsort uses insertion sort for very small amounts of data; this is typically more efficient than a pure merge sort because the benefits of merge sort over insertion sort are asymptotic. Merge sort is asymptotically faster than insertion sorts, which means that there is a threshold $N$ such that if $n \ge N$ then sorting $n$ elements with merge sort is faster than with insertion sort. The numerical value of threshold depends on the specific implementations though. With typical optimized implementations, insertion sort beats merge sort for a small amount of data. Most sort routines in the real world are hybrid, using an $O(n \log n)$, divide-and-conquer technique for large amounts of data and using a different technique (usually insertion sort) when they've broken down the data into small enough pieces. Thus a properly implemented timsort is faster on average than a pure merge sort.

Timsort is furthermore optimized to deal well with real-world data. Real-world data is not randomly distributed: it's common to have sorted runs in the data to be sorted. Compared with a basic merge+insertion sort, timsort attempts to detect and make use of such runs. This adds a small overhead of checking whether parts of the data are already sorted, but with typical real-world data this saves some actual sorting work which more than compensates.


Analysing the algorithm of a language called CONNECTED in Sipser to show that it belongs to class P

Step 2 causes at most $n$ repetitions since each repetition other than the last one marks a node which wasn't previously marked. Since there are only $n$ nodes and one of them is marked in Step 1, there are at most $n-1$ repetitions which mark a new node, and one more which doesn't (and so moves to Step 4).

In Step 3, we go over all nodes in $G$ ($n$ nodes), and check all its neighbors ($n-1$ neighbors), so there are at most $n(n-1)$ repetitions of the inner part.

As for how many steps does this take when implemented on a Turing machine, this depends on the implementation. Outside of introductory courses on theory of computation, we almost never consider Turing machines, preferring instead to work with more intuitive models such as the RAM machine. Therefore mastering the intricacies of Turing machine behavior is not so important.


In general you can't change the state and action spaces (rows and columns of your reward matrix) since that changes the underlying model that you are sampling with Q-learning.  It'd be similar to changing the population you're sampling when statistically sampling.  Hence, you have to define a set of actions and states that don't change in order to use Q-learning.  Instead of the house graph, you'd need something else.  Ideally you'd have to come up with a set of states and actions that didn't change as the house's topology changed. E.g. actions could be strategy to use could be the action given the number of rooms in the house and total number of edges (note: this'd probably be a poor choice, but I needed an example.).
All that said Q-learning albeit a little slow is pretty robust to some types of disturbances.  If the model doesn't change significantly (e.g. you add a room) and you are exploring a large state space (statistically), then your older policies (solved Q matrices) might be nice breadcrumb trails for your new algorithm's exploration strategy, and the algorithm may re-learn much faster.  However, I don't know about the theoretical guarantees (look into terms like "cross learning").


Definition of space complexity when algorithm cycles.

So how does one measure the space complexity of an algorithm that may cycle forever?

When we say that some language $L$ belongs to some complexity class it is assumed that a TM (algorithm) decides $x \in L$ in finite space and time amount. In other words, the TM/algorithm terminates, i.e. it may not cycle forever. However, an algorithm that loops forever may use finite space,  but it still cannot decide.

But I don't understand the following statement

  In an algorithm where space is counted, there can exist computations that never end, but one can always transform the algorithm into another that doesn't cycle.


A round robin scheduler has a fifo queue of processes in state runnable.  At each time step the scheduler runs the process at the head of the queue for one quantum.

At the end of each time quantum the running process is interrupted and placed at the tail of the queue.  If the process blocks (requests i/o) during the time quantum it is typically completely removed from the queue.

The difference between your solution and your instructor's solution is the assumption you are making about what happens when a process's i/o request finishes, and the process again becomes runnable.   Your instructor assumes that the process is placed on the tail of the queue.  You seem to be assuming that the process is placed at the head of the queue.

Either choice (placing the newly unblocked process at the tail or at the head) is reasonable, but they have different consequences as described by @Gille's answer to a broader question.

If you place the newly unblocked process at the tail of the queue then you maintain the guarantee that no process will ever be starved.  In practice however, i/o-bound jobs are sometimes given higher priority, both to reduce the latency of those jobs, and to maximize throughput of i/o devices.  You could implement this increase in priority by putting newly unblocked processes at the head of the queue instead of the tail, but you would lose your starvation-freeness guarantees.


Looking for two-way communication/consensus/contract algorithm for use in marriage proposal

If you're feeling up for something particularly geeky, you might enjoy a fair exchange protocol, either one based on gradual release (see e.g., this paper) or one based on Bitcoin (e.g., this).  The number of steps is very large though!  Probably not suitable to carry out by hand.

You could try a simpler protocol:

Alice picks a message $m_A$, computes a commitment $C(m_A)$ to  $m_A$, and reveals the commitment $C(m_A)$.  For instance, maybe Alice writes down $C(m_A)$ in view of Bob.
Bob picks a message $m_B$, computes a commitment $C(m_B)$ to  $m_B$, and reveals the commitment $C(m_B)$ -- say, writing it down too.  (Steps 1 and 2 can be done simultaneously or in any order.)
Alice opens her commitment to reveal $m_A$ (e.g., she writes $m_A$ down on the piece of paper).  Bob verifies that the message matches her commitment.
Bob opens his commitment to reveal $m_B$.  Alice verifies that the message matches his commitment.  (Steps 3 and 4 can be done in any order; but they shouldn't be started until both Steps 1 and 2 are complete.)

In your case, Alice could choose as her message "Bob, will you marry me?" or "Bob, let's not get married yet" and Bob could choose as his message "Alice, will you marry me?" or "Alice, let's not get married yet" and then you could compare at the end.

There are various ways to do a cryptographic commitment.  One way is with a cryptographic hash function (you could use a web site to compute it for you).  A simpler method is to secretly write down the message on a piece of paper, then put the paper in an envelope, seal the envelope, and place the envelope on the table in front of both of you.

See, e.g., https://keybase.io/blog/cryptographic-coin-flipping for a gentle introduction to related ideas.

Another idea is to execute a two-phase commit protocol.


Implementation/translation of the $s^1_1$

Roughly, s11 a program which takes as its first argument a representation of a 2-arguments program e.g. a string like

def foo(x,y):
   return g(x,y)

and a number n as its second argument.

The result of s11 is the representation of another program, obtained by "hard-coding" the value n for x in the source code, effectively removing the argument x. In the example above we would get the string

def newFoo(y):
   return g(n,y)

or something equivalent to that, e.g.

def newFoo(y):
   return foo(n,x)
def foo(x,y):  # original code unaffected
   return g(x,y)

The code posted by the OP does this using LISP lambdas. The part

(let ((y (gensym)))

generates a new variable name y, while

(list 'lambda (list y) (list f x y))))

returns the representation of the function

$$
\lambda y.\ f (x, y)
$$

where x is the value to "hard-code" (the one which we called n above).

The representation is a LISP s-expression / tree instead of a string, but the concept is the same. LISP is famous for being able to express code as data (roughly as an AST), and being able to run it in a simple way (homoiconicity).


What is the difference between a problem and an algorithm?

A problem is a thing that needs to be done; an algorithm is a procedure for doing it.

To address your specific example, "What is $x\times y$?" is a problem and "Multiply the length by the width" is an algorithm for solving the problem, "What is the area of this rectangle?" It uses, as a subroutine, some unstated algorithm for multiplying numbers.


how to draw a complement of a Turing Machine?

You cannot do it in general.

It would make the complement of your language semi-decidable, like the language itself. Hence they would be both decidable by running both machines in parallel.

Of course, this concerns only the case of semi -decidable languages for which the TM does not always halt for words not in the language.

If you have a decidable language for which the TM always halt with a yes or a no, you just exchange the yes and the no.

However there are some precautions to be taken:

compatibility of accepting and non-accepting configurations

Depending on your chosen definition of Turing Machines, accepting and
halting non-accepting configurations may not be compatible, hence may
not be
interchangeable. If it is allowed for an accepting state to have
transitions that could be used, then making it a normal state may
just make the computation go on, rather than halt without
accepting. Hence some rather simple precautions must be taken
regarding how acceptance and rejection are identified and how to
exchange them.
non-deterministic machines

Non deterministic machines are anti-managers. When a manager says
"no" it means no, and when he says "yes" it means "maybe".

Non deterministic machines do the opposite: when they say "yes" it
means "yes", and when they seem to say "no" (halting in a non-accepting configuration) it means "maybe". The reason it means maybe is that it might have answered yes with a different non-deterministic choice of some transitions. Actually, non-deterministic automata should be more accurately supposed never to give a negative answer. It is convenient with deterministic automata, but means nothing with non-deterministic ones.
It is also "maybe" when they do not terminate, for two reasons: (1) another transition choice might have produced acceptance, and (2) you cannot assert non acceptance as the computation may go on.

Hence it is not easy to complement a language recognized by a
non-deterministic or non halting device. You cannot simply exchange
"yes" and "no", since you only have "yes" and "maybe". You would only
get a managerial machine answering only "no" or "maybe", not
recognized by the Automata Theory Union. Automata must accept by terminating and answering "yes" unambiguously iff the word to be recognized is in the
language. Being able to answer no in some cases is just a bonus of deterministic machines, when kind enough to halt.

So, you must first convert your machine into a deterministic
one. Then you can exchange accepting and rejecting configurations
(with due respect to the previous point above), assuming furthermore
that the machine always halt.

To get the complement of a regular set, it is convenient to first
buid a DFA that recognizes it.

A Turing machine can always be turned into a deterministic one, but
it may not halt, thus leaving room for "maybe". Hence it is not
always possible to complement a language recognized by a Turing
Machine, as stated above. But it is possible for a (determinized) TM
that always halt with a yes/no answer.


CLRS pseudocode involving both subscripting and property access of a data structure

In pseudocode we can use whatever convention we want, as long as the reader understands what we mean.

That said, in languages like python and C++ you can actually define the subscript operator to access the underlying array, and for such languages the pseudocode could work literally.


Do CPUs have big circuits such as asynchronous multipliers or BCD to binary converters?

Last time I checked (more than 15 years ago), Wallace trees (and variants such as Dadda trees) were still the state of the art ($O(N^2)$ number of gates, but $O(\log N)$ latency; if you are naive in the way you do the additions, the latency may be $O(N)$).

Note that multipliers may be pipelined so you can still achieve a throughput of one multiplication per cycle but with a latency of more than one cycle if the latency of the multiplier is too big for your target clock rate.


What are some real world applications of graphs?

Graphs are definitely one of the most important data structures, and are used very broadly

Optimization problems

Algorithms like Dijkstra's enable your navigation system / GPS to decide which roads you should drive on to reach a destination.

The Hungarian Algorithm can assign each Uber car to people looking for a ride (an assignment problem)

Chess, Checkers, Go and Tic-Tac-Toe are formulated as a game tree (a degenerate graph) and can be "solved" using brute-force depth or breadth first search, or using heuristics with minimax or A*

Flow networks and algorithms like maximum flow can be used in modelling utilities networks (water, gas, electricity), roads, flight scheduling, supply chains.

Network Topology

The minimum spanning tree ensures that your internet traffic gets delivered even when cables break.

Topological sort is used in project planning to decide which tasks should be executed first.

Disjoint sets help you efficiently calculate currency conversions between NxN currencies in linear time

Graph coloring can in theory be used to decide which seats in a cinema should remain free during a infectious disease outbreak.

Detecting strongly connected components helps uncover bot networks spreading misinformation on Facebook and Twitter.

DAGs are used to perform very large computations distributed over thousands of machines in software like Apache Spark and Tensorflow

Specialized types of graphs

Bayesian networks were used by NASA to select an operating system for the space shuttle

Neural networks are used in language translation, image synthesis (such as fake face generation), color recovery of black-and-white images, speech synthesis


Difficulty in understanding this summations to analyze time complexity

Shellsort is notoriously difficult to analyze (surprising for such a simple algorithm). In Knuth's "Sorting and Searching" it gets an inordinate scrutiny, papers on its performance get published regularly.

Then again, the Busy Beaver function (At most how many ones does an $n$ state Turing machine write starting on an empty tape before halting?) is known only up to $n = 4$, the current record holder with 6 states writes $3.515×10^{18267}$ ones before halting...


Finding maximal factorization of regular languages

As suggested in the comments to the question, I will try to give an (unfortunately partial) answer to the question, at least to the extent that I have understood the problem myself (this implies that you may well find mistakes, and if you find a way to more briefly or clearly explain one of the below points, feel free to edit the answer accordingly):

First, one should note that we do not actually have to compute the universal automaton of a language if we want to compute the factorizations of a language.

From the paper mentioned in my comment¹, there is a 1-1 correspondence between left and right factors of a regular language, that is, given a left factor of the language, the corresponding right factor is uniquely determined and vice versa.
More precisely, we have the following:

Let $(X,Y)$ be a factorization of $L$. Then
$$Y = \bigcap_{x \in X}x^{-1}L, X = \bigcap_{y \in Y}Ly^{-1},$$
that is, any left factor is an intersection of right quotients, and any right factor is an intersection of left quotients. Conversely, any intersection of left quotients of $L$ is a right factor of $L$, and any intersection of right quotients of $L$ is a left factor of $L$.

Note that for a regular language, there is only a finite set of left and right quotients, and thus or problem reduces to computing the left and right quotients of a language, and then to compute their $\cap$-stable closure, that is, a minimal superset of the quotients that is closed under intersection. These are then precisely the right factors and left factors, and then it is usually easy to see which pairs are subsets of $L$.

Example

In order to illustrate the above points, consider the first example in the question (of which I also think that it is incorrect in the paper):

Let $L = \Sigma^\ast ab \Sigma^\ast$. Now, the left quotients of $L$ are the sets $x^{-1}L$ for $x\in \Sigma^\ast$, that is, those words $u$ in $\Sigma^\ast$ that can be prefixed with $x$, i.e. $xu \in L$. When is $y^{-1}L=x^{-1}L$ for distinct $x,y$? This is the case if and only if $x$ and $y$ can be augmented to words in $L$ with precisely the same suffixes. This means, to put it into more familiar terms, they are Nerode-equivalent, and the suffixes that are needed to append to words in a Nerode class are precisely the respective left quotients.

For $L$, we see that our Nerode-equivalence classes are

$N_1$, the set of words not containing $ab$ as a factor and ending with $a$,
$N_2$, the set of words ending with $b$ and not
containing $ab$ as a factor, and
$N_3$, the set of words
containing $ab$ as a factor, that is, $N_3 = L$

They can be augmented with the following sets (that is, these are the left quotients of the words in the respective classes):

$S_1 = x^{-1}L$ for $x$ in $N_1$ consists of all words in $L$ (any word can be augmented with a word containing $ab$ as a factor and thus becomes a word in $L$) and $b\Sigma^\ast$, that is $S_1 = L \cup b\Sigma^\ast$
$S_2 = x^{-1}L$ for $x$ in $N_2$ is the language itself, that is, $S_2 = L$ and
$S_3 = x^{-1}L$ for $x$ in $N_3$ is obviously $\Sigma^\ast$. That is, we have found three right factors of $L$. As $S_2\subset S_1\subset S_3$, their $\cap$-stable closure is trivially ${S_1,S_2,S_3}$, and those are then precisely the right factors.

Hence, our factorization set $\mathcal{F}_L$ is of the form $(P_1,S_1),(P_2,S_2),(P_3,S_3)$.

Now, for the left factors $P_i$, we use the equations of the beginning of this answer:

$$ P_i = \bigcap_{x\in S_i} Lx^{-1} $$.

For $P_1$, this yields $L \cup \Sigma^\ast a$, for $P_2$ we get $\Sigma^\ast$ and for $P_3$, we obtain $L$. You can see this by inspection (the most popular excuse for being too lazy to state a formal proof) or by explicitly computing the right quotients (which is fairly analogous, although not completely, to computing the left quotients).
Our factorizations are thus given by $\mathcal{F}_L = {u,v,w}$ where

$u = (P_1,S_1) = (\Sigma^\ast ab \Sigma^\ast \cup \Sigma^\ast a, \Sigma^\ast ab \Sigma^\ast \cup b\Sigma^\ast)$
$v = (P_2, S_2) = (\Sigma^\ast, \Sigma^\ast ab \Sigma^\ast)$ and
$w = (P_3, S_3) = (\Sigma^\ast ab \Sigma^\ast, \Sigma^\ast)$

Summary

To summarize (as you were asking for a simple procedure):

For computing the factorizations of a language $L$, first compute the left quotients of $L$.
You can do so, in the language of the paper, by constructing a minimal DFA $A$ for $L$ and then for each state $q$ in $A$ (corresponding, as a Nerode-equivalence class, to a left quotient) compute the future of $q$ in $A$, thus obtaining one left quotient of the language for each state.
The collection of left quotients obtained in this way yields, in general, a subset $S_R$ of the right factors.
Compute then the $\cap$-stable closure of $S_R$, which can be done in practice by forming the intersection of any subset of $S_R$ and adding any subset obtained in this way to $S_R$.
The set $S_R$ together with all the intersections from the previous step is then the set of right factors of $L$.
In order to obtain the left factors, we can compute the right quotients of $L$.
These are sets of the form $Ly^{-1}$, for $y\in \Sigma^\ast$. Now, these are again only finitely many, and for $x\neq y$, we have $Ly^{-1} = Lx^{-1}$ if and only if  for all $u\in \Sigma^\ast$, $ux \in L \Leftrightarrow uy \in L$, that is they can be prefixed to words in the language with precisely the same set of strings.
To compute $Lx^{-1}$, consider those states $q$ in $A$ such that $x$ is contained in the future of $q$. The union of the pasts of those states constitute one right quotient. Find all these quotients.
You know you are done when you have found as many left factors as you have right factors.
Find those pairs of left and right factors $X,Y$ such that $X\cdot Y \subseteq L$. This is $\mathcal{F}_L$.

The Universal Automaton by Lombardy and Sakarovitch (in Texts in Logic and Games, Vol 2:  Logic and Automata: History and Perspectives, 2007)


KMP algorithm is able to solve your problem. Suppose your input string can be represented as $S=AB$ where $A$ is a palindrome ($B$ can be an empty string). Now reverse $S$ we can get $S'=B'A$. consider the string $T=S*S'=AB*B'A$ where '*' is a character which doesn't appear in $S$.

As we can see, $A$ is a border of $T$. Conversely, if $X$ is a border of $T$, then $X$ is a palindrome and thus a palindromic prefix of $S$. So the answer of your problem is the longest border of $T$, which directly corresponds to the last item of "fail" array in KMP algorithm.

In fact, in order to obtain the longest palindromic prefix of a word, you can use some general methods such as Manacher's algorithm, which is the best choice in dealing palindromes.

Manacher's algorithm can find the longest palindromic substring for every palindromic center in linear time. For example, if the input string is "abbabbba", then the algorithm can give you the following results (every digit corresponds to a length of palindromic substring centered in its position):

a b b a b b b a
101410501252101

Manacher's algorithm can solve your problem easily. After getting the longest palindromic substring for every palindromic center, you can simply check for every palindromic center, whether the longest palindromic substring touches the left first character. Consequently, the whole algorithm can be done in $O(|s|)$, where $s$ is the input string.


Computational Complexity of Integer Linear Program [with Fixed number of 'Pure Constants']

Yes, it's still NP-hard.  Suppose the two allowed values for $c_0$ are 0 or 1, and that you're allowed to have equations of the form

$$c_0 + c_1 x_1 + \dots + c_k x_k = 0$$

as well (not just inequalities).  Suppose that we wish we could use the constant 17.  We can introduce new variables $z_1,\dots,z_6$, add the equalities below, and replace all occurrences of 17 with $z_6$.

$$\begin{align*}
1 - z_1 &= 0\\
0 + 2 z_1 - z_2 &=0\\
0 + 2 z_2 - z_3 &=0\\
0 + 2 z_3 - z_4 &=0\\
0 + 2 z_4 - z_5 &=0\\
0 + z_1 + z_5 - z_6 &=0
\end{align*}$$

Notice how the above equations force $z_1=1$, $z_2=2$, $z_3=4$, $z_4=8$, $z_5=16$, and $z_6=17$.

Of course there's nothing special about 17; you can do this for any other number as well.  In general, if you have any constant $\kappa$  you wish you could use, you can find an addition chain for $\kappa$, then use that to introduce temporary variables $z_1,\dots,z_t$ that force $z_t=\kappa$, then replace all occurrences of the constant $\kappa$ with the variable $z_t$.

In this way you can eliminate all constants other than 0 or 1 for $c_0$.  The length of the addition chain for $\kappa$ will be at most $2 \lceil \lg \kappa \rceil$, so the number of extra variables and equalities added is not too large (and in particular is polynomial in the size of the original problem), so this increases the size of the instance by at worst a polynomial factor.


How to analyse the time complexity of an algorithm based on the input values in addition to input size

If we analyze a Time Complexity dependent also on the values of a given input, then as you say a more defined notation would be O(max(n)).
Though, saying O(max(n) + n) in O notation means O(max(n))
So it will still be accurate, since in both outcomes the Complexity is linear in the given input.


Normally in graphics, you interpolate values across a line like so:

Point $A$ has value $V_A$ and point $B$ has value $V_B$, then you want to blend the value/color linearly between them as $C$ moves between $A$ and $B$. To do this, you first calculate the ratio (or percentage) of how far $C$ lies across the line $\overline {AB}$. This is equal to $\overline{AC}$ over $\overline {AB}$. Thus the ratio is calculated as follows:

$$
t=\frac {(C-A)}{(B-A)}
$$

Once you have this ratio, you can use it to find the interpolated value between $V_A$ and $V_B$, since they should have the same ratio.

$$
t=\frac {V_C - V_A}{V_B - V_A}
$$

The unknown variable here is $V_C$, so solving for $V_C$:

$$
(V_B - V_A)t=V_C-V_A\\
V_C=(V_B - V_A)t+V_A
$$

However, this assumes that point $C$ lies on the line $\overline {AB}$. If it is not on the line, then you can't really "interpolate" in this way without some additional definition of what you want to interpolate. For example, if $C$ lies far below the line, then you can't really compare $\overline {AC}$ to $\overline {AB}$ like this; the ratio can be greater than 1, even though $C$ is "in between" them. So in your example, point $(2,3)$ is off the line. You have many possible variants.

For instance:

You can interpolate between the distances of $\overline {AC}$ and ${BC}$. You would thus create a new straight line, $\overline {ACB}$ (even though in the graph it would be an angle) and do the above interpolation on that.
You can interpolate a particular color to a dimension. For example, you take the values $A_x$, $B_x$ and $C_x$, and interpolate $\overline {A_xC_x}$ over $\overline {A_xC_xB_x}$, and use that for Red, then use $y$ for Green etc. However this works better for 3 dimensions, where each dimension can correlate to a color.


Proof that PDA's with different definitions have same expressive power

You prove it the same way you prove that any two models of computation are equivalent: you show that, for every machine of type A, the language accepted by that machine is accepted by some machine of type B, and vice-versa. Sometimes, this is trivial, for example if A is just a restricted version of B (e.g., proving that every language accepted by a DFA is accepted by an NFA). In other cases, it involves simulating the features or acceptance criteria of A using B (e.g., proving that every language accepted by an NFA is accepted by a DFA by using the subset construction).

If you're looking for details of how to prove all the equivalences mentioned in your question, then I think your question is too broad. You should be able to find some of them in any good textbook that covers PDAs, and you'll probably find the rest as exercises because the specific proofs probably use the same general principles.


Can a cellular automata structure simulates another cellular automata structure?

Any cellular automata that could be classified as a universal Turing machine would be able to do this. The Game of Life is one such cellular automata. Here is it (rather pointlessly) simulating itself on a larger scale. Here is a Turing machine implemented in it. This 'category' that you want is probably "cellular automata that qualify as universal Turing machines".
I suspect this question will be of interest to you.


Why does my answer sheet say the set of computable functions is uncountable?

There are countably many computable functions. If $f_n$ is a complete list of all (total) computable functions, then the function $g(n) = f_n(n)+1$ cannot be any of the functions on the list, and so is not computable. This is one way to construct an uncomputable function.


ground terms in logic and $\lambda$-calculus?

I think you're basically correct. "Ground term" is more or less the same as "closed term".  Certainly the definition you gave is the same as closed term.  Personally, I don't think I've seen "ground term" used much for first-order logic or any system with binders.  The place where I most commonly see "ground term" used is universal algebra where there are no binders and so "ground term" means a term with no variables at all.

To be pedantic, the notion of "free variable" is used defined when defining the syntax of whatever formal system you're using.  As such, the notion is tied to the system being defined.  Conceptually, though, the it's the same idea.  In the last decade or so, there's been a lot of research in the CS community in capturing and manipulating binders in a languange-agnostic manner so that tools, libraries, and languages can be defined that allow easy definition and manipulation of languages with binders.  For example, the languange Beluga and the various "nominal" systems.


top k selection in fixed size priority queue with dynamically changing values

The problem is known as partial sorting. Wikipedia gives various algorithms, using heaps and so on.


Optimization of Thompson Construction of an NFA

In general these reductions are OK when there are no other edges incident to the edges you are contracting. Whenever there are other edges there can be unexpected paths.

I do not know of a good characterization when they can be used. If such an improvement would have been obvious, I think Thompson would have included it.


Are two elements always in a relation within a partially ordered set?

In a partially ordered set, there may be members which are not comparable. A partial order where all elements are comparable is called a total order.

We say $a$ and $b$ are comparable when at least one of the following holds:

$a\leq b$,
$b \leq a$.


Find the longest contiguous subsequence such that its sum $(a_i + a_{i+1} + \cdots + a_j)$ is divisible by $D$

There exists a linear time algorithm.

Compute partial sum $s_j = \sum_{i=1}^j a_i$ and their remainders $r_j = s_j \mod D$.
Consider the sequence $\{(j,s_j,r_j)\}_{j=0}^N$.  For each $0\leq r < D$, compute the subsequence consisting of all tuple $(j,s_j,r_j)$ such that $r_j  = r$.  An easy approach is to sort the tuples in the sequence by their third component, using an stable sorting algorithm ($O(N \log N)$ time).  In this problem, $D \approx N$, so we could use bucket sort, improving the running time to linear; otherwise, using hash could also improve the running time to linear.
For each subsequence, apply the following algorithm on it.

Pick two pointer $i,j$, both initialized as the first element in the
subsequence.
If $s_j - s_i > DM$, point $j$ to the successor of $(j,s_j,r_j)$ in the subsequence, otherwise point $i$ to the successor of $(i,s_i,r_i)$ in the subsequence.
Repeat step 2 until $j$ points to the last element in the sequence.

Among all temporary values of $(i,j)$, find one that maximize $j-i$ under constraint $s_j-s_i \leq DM$.


For a B+ tree the order of a node is the maximum number of keys that it can contain. This satisfies the definition of maximum number of children because for a leaf node number of record pointers(children) is same as number of keys. The last pointer present in a leaf node is not considered a children since it links one leaf to another(is not a record pointer).


Intersection of two generative neural networks

No, not in general.  It's possible that $G(x)=\neg F(x)$, for instance.


Elegant approach to finding largest $n$ such that $n\lg(n) \leq 10^6$

We just solve $x \log x = 10^6$ and round down. This sort of equation typically does not have a closed form solution (so what, closed form solutions are so 18th century, we've got computers now), so we just feed this into a computer and we get $n \approx 87847.5$, so the answer is 87847.

You did ask for the most elegant approach, you know, and that would be to use the right tool.

Now, you could also wonder how you would compute this by hand if you found yourself in the middle of a jungle. You could use the iteration method (is this what you called substitution?). Write the equation in the form of a fixed point:
$$x = \frac{10^6}{\log x}$$
Start with any initial guess for $x$ and keep applying the right-hand side. With some luck, you converge. You find a python in the jungle and make it compute:

>>> import math
>>> x = 42
>>> for i in range(20):
...    print x
...    x = 1000000.0/math.log(x)
...
42
267546.386419
80018.8957423
88573.8173924
87784.0460781
87853.1196966
87847.0493964
87847.5826391
87847.5357949
87847.5399101
87847.5395486
87847.5395803
87847.5395775
87847.5395778
87847.5395778
87847.5395778
87847.5395778
87847.5395778
87847.5395778
87847.5395778

That was kind of slow. A better method would be Newton's method. We are looking for the root of $f(x) = x \log x - 10^6$. The derivative is $f'(x) = 1 + \log x$ so the Newton's method step is
$$x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)} = x_n - \frac{x_n \log x_n - 10^6}{1 + \log x_n}.$$
So now we get:

>>> x = 42
>>> for i in range(10):
...     print (x)
...     x = x - (x * math.log(x) - 1000000.0)/(1 + math.log(x))
...
42
211083.102152
91333.5177989
87852.9643949
87847.5395913
87847.5395778
87847.5395778
87847.5395778
87847.5395778
87847.5395778

Much better.


Coursera has materials on Automata by Ullman. You can always "preview" that material. Also for a more complete reference on a first course, may I suggest Gusfield's Lectures (available in iTunesU)

For more advanced treatment, Tim Gowers has few online lectures on Computational Complexity and Quantum Computation

Also, the AB book is really good. you may want to stick with that.

If you want more advanced materials, looking into the proceedings of STOC or FOCS from the previous years, might be insightful.


What is the significance of a Θ-bound on the running time of Mergesort?

Mergesort takes $Θ(n \log n)$ compares to sort n elements [in the worst case].

Just unfold definitions. Step one:

  Mergesort takes $O(n \log n)$ and $\Omega(n \log n)$ compares to sort $n$ elements [in the worst case].

Step two (and three, I guess, since I recombine the unfolded definitions of $O$ and $\Omega$):

  For some $n_0 \in \mathbb{N}$ and $a,b \in \mathbb{R}_{>0}$, the number of comparisons $C_n$ Mergesort uses to sort $n$ elements [in the worst case] is bounded by $a \cdot n \log n \leq C_n \leq b \cdot n \log n$ for all $n \leq n_0$.

That's it. Would I call that insight? Hardly.

Adding the justification for why we ignore constant factors in the first place and that comparisons are a dominant operation in Mergesort, I guess the intended statement is something like this:

  If you implemented this Mergesort algorithm on a machine [that fits the RAM model and can compare all input numbers in constant time], its running-time cost would be roughly proportional to $n \log n$ for large enough $n$.

Note that neither the proportionality constant nor the sense of "roughly" and "large enough" are specified by the formal definitions. It may very well be that the algorithm is utterly unusable for all instances relevant to you. Hence, statements about algorithm performance using Landau notation are, for practical purposes, mostly vacuous -- formally speaking.

Implicitly, "we know" that "usually" constants are small and lower-order terms behave "nicely" (see e.g. here for a more precise result on Mergesort) so comparing Landau bounds is a somewhat meaningful criterion for choosing algorithms in practice. It has serious limitations, though, and it is important to keep those in mind.


You already proved in First part that using random assignments to the values it solves $\frac{m}{2}$ equations in expected value. Moreover, this fact came from knowing that each individual equation will be solved with probability $\frac{1}{2}$ on every random assignment. So we can use the following algorithm to solve this problem:

E = Unsolved equations (initially all equations)
A = {} # Assignments that solves the problem.

while E is not empty:
    a = Random assignment
    SE = solved_by(E, a) # Equations in E solved by assignment a
    if |SE| * 2 >= |E|:
         E = E \ SE      # Remove solved equations
         A = A U {a}     # Add this assignment to the solution

return A

This algorithm will find at most $\lfloor log_2(n) \rfloor + 1$ assignments so that every equation is solved by at least one assignment because condition if |SE| * 2 >= |E| half the size of |E| and add one assignment to A after every success. This will also run in time, since the probability of success is $\frac{1}{2}$, so the expected iterations for success is 2.


Efficient way to find the i-th size in a BST

(Please check the problem statement: having sub-tree sizes at each vertex available in constant time is very useful to find the $i$−th smallest/largest element/key (with $2$ being the 3rd smallest element in $1, 2, 2, 2, 3, 4$).)

For finding the $i$−th largest size, notice the tree to be a max-heap with respect to sub-tree sizes.
In search of the $i$−th smallest size, assume that the tree is perfectly balanced but for the path to one leaf, which is longer by i ($∄j: i = 2^j-1$). Before encountering that path/vertex, all sizes no larger than i will have been of the form ($2^j-1$). As you don't know if and where such a path/vertex exists, you will have to visit on the order of all n vertices.
Unless you find a way to know the $i$−th size among $Ο(n)$ candidates faster, this will be $Ω(n \log(i))$ in $Ο(i)$ space. (This depends on how much additional memory can be used, e.g., with $Ο(n)$ memory, you can do a counting sort of sizes encountered in $Ο(n)$ time.)

Run-time can be reduced by properly bounding the search:
Every non-empty tree will contain at least one leaf, so if i is $1$, return $1$.
For $1 < i$, keep track of the highest size s such that every size up to s is known to have been encountered. When s reaches $i$, return that. Never descend from vertices with size no greater than s.


What is the advantage of Day-Stout-Warren algorithm for balancing BST?

The Wikipedia article states:

  The algorithm [...] is in-place.

You algorithm requires at least twice as much space. This is a significant drawback on huge data sets.

A further possible advantage (I did not check) lies in the constant factors of the runtime function. Intuitively, you always construct a perfectly balanced BST so you may well do (lots) more work than DSW, even if you are still linear. Again, even a factor of magnitude $< 10$ is significant on huge data sets.

In my opinion, this question is more interesting: why use simple BST + DSW instead of using balanced BSTs in the first place? (The answer is hinted at in the article, too.)


Say you want to pick, out of a multiset $S$, the numbers $x_1$, $x_2$, ..., $x_n$ with multiplicity $m_1$, $m_2$, ..., $m_n$  (i.e., you want to pick $x_1$ exactly $m_1$ times).
Furthermore, assume that in $S$ the numbers  $x_1$, $x_2$, ..., $x_n$ have multiplicity $s_1$, $s_2$,..., $s_n$.  (we assume for every $i$, $s_i \ge m_i$, otherwise no solution exists).

Consider the first element $x_1$:
you have exactly $s_1 \choose m_1$ different ways to pick $m_1$ occurrences of $x_1$ from the $s_1$ times it appears in $S$.

In a similar way for all the other elements,  the answer would be
$${s_1 \choose m_1} {s_2 \choose m_2} \cdots {s_n \choose m_n} = \prod_{i=1}^n {s_i \choose m_i}$$

For your example, set $x_1=6$, $x_2=5$, $x_3=4$, $x_4=2$.
In the data set they appear with multiplicity $s_1=1$, $s_2=2$, $s_3=1$, $s_4=4$ and you want to have $m_1=1$ sixes, $m_2=2$ fivess, $m_3=1$ fours and $m_3=2$ twos, so the number of different options is
$$ {1 \choose 1} {2 \choose 2} {1 \choose 1}{4 \choose 2}  = 1 \cdot 1 \cdot 1 \cdot 6$$


Studying Skiena. War Story: What’s Past is Prolog

Each (non-trivial) run is given by two (different) indices, marking the beginning and end of the run, so if the sequence is of length $n$, there are $\binom{n}{2}$ possible runs. If we only consider maximal runs, there are at most $n$ (or even less, if we don't consider trivial runs).


Is the halting problem decidable for pure programs on an ideal computer?

Here is a proof of undecidability by reduction from the Halting problem.

Reduction: Given a machine $M$ and an input $x$, build a new Turing Machine $H$ which does not read any input, but writes $M$ and $x$ on the tape and simulates $M$ on $x$ until $M$ halts.

The behaviour of this new machine $H$ is independent of the input tape, so it is a pure Turing Machine on which only static analysis is applicable. If static analysis were sufficient, then it could show whether $H$ halts, which would show whether $M$ halts on $x$, which would solve the halting problem for impure machines, which we know is undecidable, and therefore your problem is undecidable too.


How to prevent overflow and underflow in the Euclidean distance and Mahalanobis distance

That is a long solved problem. First, if you are using double precision floating point numbers in IEEE754 format (which is most common), that's what extended precision was invented for. Even in the extreme case, $X_i$ and $Y_i$ huge, $L_i$ tiny, the numbers involved are less than $10^{1300}$ and extended precision goes up to about $10^{4000}$.

Without extended precision available, or if your numbers are already in extended precision, you just calculate the result and check whether you had an overflow or if the result is tiny. Tiny results are critical as well: If you use double precision floating point numbers, and your numbers are around $10^-200$, then squaring them gives you zero. There will be a lower bound c where you can prove "if the result is greater than c, then any underflow in the calculation didn't change the final result".

If overflow happens, or underflow happens, then you scale the numbers by a suitable power of two. Do NOT divide by the maximum value, because that introduces rounding errors, and there are cases with n = 2, $L_i = 1$, where $|X_1 - Y_1| ≤ |x_1 - y_1|$, $|X_2 - Y_2| ≤ |x_2 - y_2|$, yet the calculated distance of X, Y is greater than the calculated distance of x, y, due to rounding errors. Scaling by a power of two avoids the problem because it doesn't create any rounding errors.

And you want to make sure that the order of numbers doesn't make a difference. For n = 2 you must make sure that no fused multiply/add operations are used. For n ≥ 3 you probably want to sort the numbers so the ones with smallest absolute difference come first. Otherwise you can get into situations where the distance between $(X_1, X_2)$ and $(Y_1, Y_2)$ is not the same as the distance between $(X_2, X_1)$ and $(Y_2, Y_1)$.


Why, in programming languages in general, must function declarations be followed by a parameter set, external to the sub-routine scope?

In my opinion, your question is formed on the basis of working with a small number of programming languages and extrapolating  conclusions that may not be valid.

Here are some assumptions I have recognised that may not be valid which I will later explore in greater detail:

All function calls must use parenthesis.
All programming languages use these syntactic notations to mean the same thing
There is some common underlying nature that requires things to be like this

I further understand you hinted that you have no significant background in Computer Science theory, but some of the background material to why functions are usually written like this, is about the theoretical evolutionary route that most current languages came from;
So, lets review some of that, as it may help readers (such as students of Computer Science and programming per se) understand your question and our answers more fully.

Consider an early computer language, such as Fortran, which was devised in 1954. It had functions and used parentheses. Actually, at that time the character set available on computer was so limited that it had no other bracketing symbols, and only had upper case letters. It did not have access to []{}<> symbols. Originally all comparisons were made to zero so that comparison operators were not needed, but when they were later introduced they had to be written as .GT. and .LT. due to the lack of characters. The result of this was we could write:

       FUNCTION B
       B=1.0
       RETURN

       FUNCTION C(D)
       C = D
       RETURN

       DIMENSION A(10)
       A(1) = C(1) + B
       STOP
       END

You can see that we have used parentheses for A(1) (which is an array) and C(1) which is a function call, but not for + B which is also a function call. We have used parentheses for A(10) which is an array declaration and also for C(D) which is a function declaration with a formal parameter. Thee design on the language is such that the compiler can work out what is intended and instruct the computer in its machine code to take appropriate actions. However, sometimes this is not convenient for the compiler writer as that may require multiple passes (or readings) of the program to determine what use of parenthesis was intended before determining the semantics of that fragment of code.

Algol 60 also has a similar situation, shown in this example:

  integer function one;
  begin
  one := 1
  end;

  integer function two (integer p);
  begin
  two := p
  end;

  begin
  integer array a [ 1: 10 ];
  a[one] := two(1)
  end

In the above example one is a function that uses no parentheses in its declaration or invocation, whereas two is a function that used parentheses to indicate the formal parameter list (integer p) and also the actual argument (1). this time they are not  confused with arrays at all, because the array exclusively used [] in both its declaration and application. So thus invalidating your assumption on what () might mean.

We also get some symbol overloading in more modern advanced languages. Take Algol 68 for example. It also uses parentheses for arrays and functions (but also almost everything else), but also like Algol 60 that proceeded it, it uses square brackets []:

  ( [] int a := (1,2,3);
      print((a[1])) )

Here '[]' are used to indicate the array declaration, whereas (1,2,3) indicates the array constant used to initialise it. The print statement is even more complex. The inner parentheses (a[1]) indicate an array constant containing one element and the outer print() indicates a function call, and the [1] indicates an array selection operation. The all-encompassing () are used for the program begin and end.

One more historical language is important here, which is LISP. Using LISP we can explore functions as first class objects, lambda functions and other aspects of functions and the notation associated with them. In LISP we can store a function in a named variable like this:

(setq double (function (lambda (x) (+ x x)) ))

Notice that everything is using parentheses; that is the nature of LISP. LISP is constructed entirely of lists denoted by the tuples in parentheses like this:

(x x x x)

Those lists can be either or both data and functions, it makes no difference. Now that the name double contains a function we can do various things with it.

We can invoke the function like this:

(funcall double 11)

This leads into coverage of the notation used in command command languages such as Windows/DOS command prompt and unix shells. In them each line is essentially a function call:

cd path/file

Function calls can be nested by using backtick notation:

cd `which file`

Here no parentheses have been used at all, yet it is a notation familiar to many experienced computer users.

I have not really covered other uses of functions and their notations, such as functions as first class objects, passing functions as arguments, partial parameterisation, lazy evaluation and many many more concepts that could shine a light onto why function notation is as it is. We have to have a notation to ultimately say: This name is a function and I want it to be invoked at this point.

Some of what we are exploring here is the separation between programming language syntax and its semantics. How much of the symbols indicate structure and how much communicate meaning (semantics), and  how can this be determined by automated means. An introduction (to a deeper) theoretical topic can be started by looking at Chomsky Language Hierarchy. Algol 60's nice separation of [] from  () meant that a Context Free Grammar could be used to describe the syntax of the language. Algol 68, in contrast, by the use of symbol overloading (and for other reasons) mean that a more complex Context Sensitive Grammar (known as W-grammars) needed to be used.

The more complex the grammar needed to express the language the more complex the compiler implementation. Language designers wanted both a powerful and expressive language, but also one that could be implemented without undue complexity in the compiler. This often resulted in some stereotyping of language features in ways that were know to be implemented more easily.

In the evolution of languages they developed into different families as they grew from one to another. To prevent the overloading of () meaning begin and end the use of the symbols {} became common place, and the use of [] for array was considered sensible. However many languages use () to indicate both formal parameters and actual arguments, but this is by no means a universal characteristic, and there are exceptions to everything.

When we think that many  languages seem to use the name() notation for function invocation, what we are really seeing is that many languages in common use today inherit a set of notations from the C family of languages through the Algol route. That is all we are seeing is the genealogy of language in the notations.

I hope by a brief tour on the history of the use of parenthesis in the evolution of computer languages and its relation to computer science theory you have gained an insight into what you are trying  to understand.

And if it matters: yes I have worked on Fortran, Algol 60, Algol 68 and other esoteric language compilers


Your grammar generates the language $L(A)^*$, where
$$
L(A) = \{0^i 1^j : j \geq i\}.
$$
You can generate $L(A)$ unambiguously in many ways. Two options are:

Use $0^i 1^j = 0^i 1^i 1^{j-i}$.
Use $0^i 1^j = 0^i 1^{j-i} 1^i$.

Given that, the current productions for $S$ will already generate $L(A)^*$ unambiguously.


Non Regularity proof using Kolmogorov Complexity (Li - Vitanyi Theorem)

You are asking many questions. Let me answer your first two, regarding $Y^A_{0^k,n}$ for $A = \{0^k1^k : k \geq 0\}$. Recall that $Y^A_{0^k,1},Y^A_{0^k,2},\ldots$ is the list of all strings $y$ such that $0^ky \in A$, arranged in some order - apparently first according to length, and then lexicographically. It is easy to see that the strings $y$ such that $0^ky \in A$ are of the form $0^m1^{k+m}$. Arranged according to length, these are $1^k,01^{k+1},0^21^{k+2},\ldots$, and more generally, $Y^A_{0^k,n} = 0^{n-1}1^{k+n-1}$.


Using DCEL to represent "simple geometric objects"

First of all, while being generic is nice from an user perspective, it is usually the best idea to use the simplest structure that you require from an algorithmic perspective. The proper solution to this problem is simply to offer the user a single interface (or 'wrapper', as you call it).

(Another problem is that unnecessary abstraction is potentially unbounded. Why use a plane when $\mathbb{R}^n$ is more general? Why use that when an abstract metric space is more general, etc.)

Now, for your specific construction:

  For the segment case I would just have two vertices entries not empty, two half edges entries not empty, the faces list would be empty.

The problem with this construction is that a lot of fields are empty that I would expect to be filled. Why do some edges have no face, why do some edges have no successor? Both these cases do not occur in a DCEL, so to make this particular structure work you must already define a generalisation of a DCEL that allows for empty fields. Most importantly, you are trying to store something that is not a subdivision of the plane in a DCEL, which is designed to store precisely that!

If you really want to store 'simple geometric objects' in the plane, using a trapezoidal decomposition seems like a decent idea, as it can reasonably store both segments and polygons. (It is even possible to store both a trapezoidal decomposition and a DCEL for the same data) However, this all depends on the actual application, since some operations are more efficient with a DCEL or other structures.

If you insist on storing segments in a DCEL, an approach is to represent a segment by a pair of edges (so 4 half-edges), where one of the 'faces' is the space surrounding the segment and the other the face 'inside' the segment (with 0 area).


Complexity of generating non-uniform random variates

The binomial, negative binomial, and hypergeometric distributions are discrete distributions. Knuth and Yao (1976) gave complexity results for discrete distributions in general. Given a stream of i.i.d. unbiased random bits, any algorithm that samples from a discrete distribution will require at least—$$b = -\sum_{x\in\Omega} \mathbb{P}(X=x)*\log_2(\mathbb{P}(X=x))$$random bits on average to sample a variate $X$ from that distribution (where $\Omega$ is the distribution's support), and they gave an algorithm that comes within 2 bits of this lower bound (and showed that coming within 2 bits is the best possible for any algorithm).
The case of continuous distributions such as the normal distribution is more complicated, but Devroye and Gravel gave complexity results for sampling a continuous variate to a desired accuracy, given a stream of i.i.d. unbiased random bits, using Wasserstein distance as the accuracy metric.
I also want to note one more thing. If the distribution of $X$ has a continuous and bounded quantile function (inverse cumulative distribution function) $F^{-1}$, I suspect that the bit complexity of sampling $X$ also depends on the modulus of continuity of $F^{-1}$, call it $\omega(h)$. In this sense, Lipschitz continuous quantile functions (where $\omega(h) = O(h)$) are the simplest cases of such functions and in that case it's simple to describe an algorithm to sample $X$ to a desired accuracy. For such functions, the algorithm uses—$$ceil(\ln(\max(1, L))-\ln(\epsilon))/\ln(\beta))$$random digits, where $L$ is the Lipschitz constant, $\epsilon$ is the desired accuracy, and $\beta$ is the digit base (such as 2 for binary). I suspect that with other moduli of continuity, the complexity will be as follows: $$ceil(-\ln(\omega^{-1}(\epsilon))/\ln(\beta)).$$
REFERENCES:

Knuth, Donald E. And Andrew Chi-Chih Yao. "The complexity of nonuniform random number generation", in Algorithms and Complexity: New Directions and Recent Results, 1976.
Devroye, L., Gravel, C., "Random variate generation using only finitely many unbiased, independently and identically distributed random bits", arXiv:1502.02539v6 [cs.IT], 2020.


In a DFA, does the restriction for a total transition function apply to accepting states?

Unfortunately there seem to be several different definitions of DFAs in the literature. Here is the classical definition:

A DFA is a quintuple $\langle \Sigma,Q,q_0,F,\delta \rangle$, where $\Sigma,Q$ are non-empty finite sets, $q_0 \in Q$, $F \subseteq Q$, and $\delta \colon Q \times \Sigma \to Q$.
We extend $\delta$ to a function $\hat\delta \colon Q \times \Sigma^* \to Q$ using the recurrence $\hat\delta(q,w\sigma) = \delta(\hat\delta(q,w),\sigma)$, with base case $\hat\delta(q,\epsilon)=q$.
The language accepted by the DFA is $\{ w \in \Sigma^* : \hat\delta(q_0,w) \in F \}$.

Other definitions are possible. For example, you might allow $\delta$ to be a partial function. However, the definition I stated has a significant advantage: the Myhill–Nerode theorem holds for it.
Under my definition, from each state there is exactly one transition for each alphabet symbol. Other definitions could be different. Only you know which definition you use.
It is important to stress that this "strict" definition doesn't restrict the power of DFAs one bit. It is known that DFAs accept the very same languages as NFAs, for example, though there could be a dramatic difference in state complexity (the number of states needed to accept a given language).


For all oracles A, If $P^A \neq PSPACE^A$, then Does it imply that $P \neq PSPACE$?

If $A = \emptyset$, or more generally, if $A \in \mathsf{P}$, then $\mathsf{P}^A = \mathsf{P}$ and $\mathsf{PSPACE}^A = \mathsf{PSPACE}$, and so $\mathsf{P}^A \neq \mathsf{PSPACE}^A$ is the same as $\mathsf{P} \neq \mathsf{PSPACE}$.
It is also interesting to ask whether $\mathsf{P}^A \neq \mathsf{PSPACE}^A$ for a random oracle implies $\mathsf{P} \neq \mathsf{PSPACE}$. This was disproved (with $\mathsf{P}$ replaced by $\mathsf{IP}$) by Chang, Chor, Goldreich, Hartmanis, Håstad, Ranjan, and Rohatgi in their paper The random oracle hypothesis is false.


There are two ways that lookaheads 'come into being'. The first is that the start production $S' \rightarrow S$ has lookahead $\$$ in the initial state of the $LR(1)$ automaton. Hence, $S' \rightarrow \bullet S, \$$ is an item in the initial state.

Pendantry note: we therefore accept in the state containing the item $S' \rightarrow S \bullet, \$$ on lookahead $\$$ and we pad any input with $\$$.

The rest of the lookaheads are computed from lookaheads which we have already computed. If we have in some state an item $A \rightarrow \alpha \bullet X \beta, l$ (so $l$ is the lookahead and $X$ is a nonterminal) and another production $B \rightarrow \gamma$, then for every $a \in \mathsf{FIRST}(X \beta l)$ we add in the completion step for that state the item $B \rightarrow \bullet \gamma, a$.

In other words, the lookahead is some terminal that can appear as the first terminal in a string derived from $X \beta l$. As $l$ is a terminal and appears at the end of $X \beta l$, this means that $X \beta l$ does not derive the empty string (so we don't need $\mathsf{FOLLOW}$). Also note that we only ever derive items and therefore new lookaheads from items that already have lookaheads, so there is no problem there.

The precise definition of $\mathsf{FIRST}$ is: $\mathsf{FIRST}(a \alpha) = \{a\}$ if $a$ is a terminal, $\mathsf{FIRST}(A \alpha) = \mathsf{FIRST}(A)$ if $A$ is a nonterminal and $A$ does not derive the empty string, and $\mathsf{FIRST}(A \alpha) = \mathsf{FIRST}(A) \bigcup \mathsf{FIRST}(\alpha)$ if it does. $\mathsf{FIRST}(A)$ is the well-known relation denoting the first terminals in the strings derivable from $A$ (which is also used in $LL(1)$).


Take your DFA and change each of its input symbols into a single symbol, say $a$. Now of course your automaton no longer is deterministic, but lengths are preserved. Then make the automaton deterministic again. The form of the new DFA is that of a initial linear path leading to a loop. This is because of the single letter restriction.

The accepting states in the initial linear path are the finite component of the language, of lengths that do not repeat. The accepting states in the loop represent the $a_i$ for your construction. The length of the loop is the single $b$ in the $a_i+kb$ representation.


Each subset of $S$ either contains the first element or doesn't. So we can implement a generic enumeration of subsets which match a predicate as (code given in Python but untested):

def subsets_matching_predicate(elements, predicate, included = []):
    if len(elements) == 0:
        if predicate(included):
            yield included
    else:
        for subset in subsets_matching_predicate(elements[:-1], predicate, included):
            yield subset
        for subset in subsets_matching_predicate(elements[:-1], predicate, included + elements[-1:]):
            yield subset

This is essentially what your approach does.

But the sum is monotone, since the numbers are restricted to be positive, so this can be optimised.

def subsets_having_sum(elements, target_sum, included = [], included_sum = 0):
    if included_sum > target_sum:
        return

    if len(elements) == 0:
        if included_sum == target_sum:
            yield included
    else:
        for subset in subsets_having_sum(elements[:-1], target_sum, included, included_sum):
            yield subset
        for subset in subsets_having_sum(elements[:-1], target_sum, included + elements[-1:], included_sum + elements[-1]):
            yield subset

We can also simplify in various ways:

Pass target_sum - included_sum instead of two variables
Accumulate on the way out rather than the way in
Once we hit the target, we don't need to keep going

def subsets_having_sum(elements, target_excess):
    if len(elements) > 0:
        for subset in subsets_having_sum(elements[:-1], target_excess):
            yield subset

        if elements[0] == target_excess:
            yield elements[-1:]
        else:
            for subset in subsets_having_sum(elements[:-1], target_excess - elements[-1]):
                yield elements[-1:] + subset

There's a further optimisation whereby we pre-calculate the numbers which can be reachable with each sublist, and don't bother calling in if they're not reachable. The memory/speed tradeoff depends on the expected length of elements and value of target_sum.

def calculate_masks(elements, target_sum):
    masks_of_interest = (1 << (target_sum + 1)) - 1
    accumulated_mask = 1
    accumulated_mask = []
    for element in elements:
        accumulated_mask = (accumulated_mask | (accumulated_mask << element)) & masks_of_interest
        accumulated_masks.append(accumulated_mask)

def subsets_having_sum_impl(elements, target_excess, masks):
    if len(elements) > 0 and (masks[-1] >> target_excess) & 1:
        for subset in subsets_having_sum(elements[:-1], target_excess, masks[:-1]):
            yield subset

        if elements[0] == target_excess:
            yield elements[-1:]
        else:
            for subset in subsets_having_sum(elements[:-1], target_excess - elements[-1], masks[:-1]):
                yield elements[-1:] + subset

def subsets_having_sum(elements, target_excess):
    masks = calculate_masks(elements, target_excess)
    return subsets_having_sum_impl(elements, target_excess, masks)


Your problem has been solved by Myers, Approximately Matching Context-Free Languages. A more recent algorithm, together with many relevant pointers, is Rajasekaran and Nicolae, An error correcting parser for context free grammars that takes less than cubic time.


Why do we care about random Boolean SAT formula?

If your solver is efficient for random 3-SAT, it by no means entails that it is efficient for an arbitrary 3-SAT instance. Randomly generated instances are very different from instances that arise in practice (meaning they are structured differently). For instance, you can read about the phase transition in random $k$-SAT: depending on the clause-to-variable ratio, an instance can be easy (not constrained enough, or too constrained) or hard (in some sense critically constrained). This phenomenon is rather fascinating in itself.

You can always argue that if you have a solver that does not exploit any structure of the input and is always rather magically efficient, much of the theory we have developed around SAT is useless. Unfortunately, many people have worked a lot on the problem, and we are still unable to give an efficient algorithm for e.g. SAT (not to mention an algorithm that would be efficient in practice as well!). So how do we cope with this? We look at e.g. structural aspects of the input: what can we leverage? How can we be fast at least sometimes? Because we can't solve a problem we care about, we look for other approaches and angles of attack.

I think the main reasons we have been interested in random $k$-SAT is that first, such instances are easy to generate to test our solvers. We have also learned that random instances are very different from instances that arise in practice (and of course those are the instances we often care about). This has increased our understanding of the nature of computation, heuristics, complexity, and ultimately made us able to build faster solvers as well.


While using K-means, how do I represent IP addresses and languages on the coordinate axis?

If your data doesn't map in an obvious way onto vectors of continuous real numbers, don't use K-means.

To use K-means clustering you need to have a well defined distance between any two points in the space.  To do that you need to have a notion of distance for each axis.

Typically discrete classifications like "language" don't have any natural mapping onto real numbers.


What Is The Complexity of Implementing a Particle Filter?

It appears that the speaker feels that there isn't a definitive complexity analysis yet for the technique. This could be due to a couple of factors.

The analysis is hard, and no one has figured it out yet.
The technique has multiple different appropriate implementations, based on the problem context.

I'd bet on the second option, particularly in light of the speaker's comment that the technique may not be appropriate for higher dimension parameter spaces. Keep in mind that the video did not present an algorithm, it presented a very high-level discussion of a technique.


Assignment algorithm for symmetric matrices

Your problem is exactly the same as maximum weight perfect matching, solved by the blossom algorithm. Although $\delta$ is not given as symmetric, you can reduce your problem to the symmetric case by replacing $\delta$ with
$$ \delta'(\alpha,\beta) = \max(\delta(\alpha,\beta),\delta(\beta,\alpha)). $$
I'll let you figure out how to translate a solution which is optimal with respect to $\delta'$ to one which is optimal with respect to $\delta$.


Can any problem in P be converted to any other problem in P in polynomial time?

If by convert you mean reduce (through a Karp-reduction), then it is possible to reduce any problem $A$ in $P$ to any non-trivial problem $B$ in $P$.

Here "non trivial" means that $B$ has at least one yes instance $I_Y$ and at least one no instance $I_N$ (i.e., the language associated to $B$ is not $\emptyset$ nor $\Sigma^*$).

To map an instance $I_A$ of $A$ to an instance $I_B$ of $B$ simply solve $A$ using a polynomial-time algorithm. If $I_A$ is a yes instance let $I_B = I_Y$, otherwise let $I_B = I_N$.

It is not possible to reduce any problem $A \in P$ to any problem $B \in P$. To see this let $A$ be a non-trivial problem and let $B$ be a trivial problem.
Two possible languages corresponding to $A$ and $B$ are $\{ \varepsilon \}$ and $\emptyset$, respectively.