What does it mean for something to be $\prod_x^y$-complete or $\sum_x^y$-complete?

The search term you're looking for is "arithmetical hierarchy".
The arithmetical hierarchy
All of the following relates to the logical language of Peano arithmetic. The operations available to us are the unary successor function $S$, the constant $0$ and the binary relation $=$, all with the usual, obvious meanings.  Variables range over the natural numbers.
In the notation $\Sigma_n^m$ or $\Pi_n^m$,

$\Sigma$ denotes a formula equivalent to one in prenex normal form with an existential quantifier outermost;
$\Pi$ denotes a formula equivalent to one in prenex normal form with a universal quantifier outermost;
$n$ denotes the number of quantifier blocks;
$m$ denotes the kinds of objects being quantified.

A formula is in $\Sigma_0^0=\Pi_0^0$ if it contains no quantifiers.  A formula is in $\Sigma^0_{n+1}$ if it is equivalent to one of the form $\exists x_1, \dots, \exists x_k\,\varphi$, where $\varphi\in\Pi_n^0$. A formula is in $\Pi^0_{n+1}$ if it is equivalent to one of the form $\forall x_1, \dots, \forall x_k\,\varphi$, where $\varphi\in\Sigma_n^0$.
All of the quantifier aboves are first-order: they range over the natural numbers.  Call the natural numbers "level $0$" objects and define level-$(m+1)$ objects to be sets of level-$m$ objects (or, equivalently, functions from level-$m$ objects to $\mathbb{N}$).  $\Sigma_n^m$ and $\Pi_n^m$ extend the definition of $\Sigma_n^0$ and $\Pi_n^m$, respectively, by allowing quantification over objects at any level between $0$ and $m$, inclusive.
Completeness
So far, we've only talked about formulae but a set $X\subseteq \mathbb{N}$ is said to be in $\Sigma_n^m$ if there is a formula $\phi(x)\in \Sigma_n^m$ with one free-variable such that $X = \{x\mid \phi(x)\text{ is true}\}$; similarly for $\Pi_n^m$.
Completeness just means what it always means. A set is complete for $\Sigma_n^m$ if it's in $\Sigma_n^m$ and every other set in $\Sigma_n^m$ can be reduced to it (similarly for $\Pi_n^m$-completeness). The notion of reducibility is usually either many-one reductions or Turing reductions.  So, for example, a set $Y$ is complete for $\Sigma_n^m$ under Turing reductions if, for every set $X\in\Sigma_n^m$, there is a Turing machine with an oracle for $Y$ that decides membership of $X$.  For many-one reductions, we insist that the oracle is called only once and the result of the oracle must be the result of the Turing machine's computation.  (Many-one reductions are the ones usually used to prove NP-completeness but, here, we're not restricting to polynomial-time reductions.)


Sure, the zero matrix $0$ is nilpotent since any of its powers is again the zero matrix.
Just a side note: This question would be more suitable at the math stackexchange.


"Visited" vs "Seen" Positions in Breadth-First Search

I recommend you to take the same approach as I did to draw my conclusions: take a graphical approach to see the differences and drawbacks.

For that, do the following:

Comment out all print lines except print("Frontier:", frontier)
Then do python program.py > version1.txt, modify your program such that it represents verison 2, and then do python program.py > version2.txt.
Get pen & paper and draw a 4 × 4 table.

Here is a comparison of the first lines of both log files:

    Version 1           Version 2

Frontier: (4, 4)     Frontier: (4, 4)
Frontier: (3, 4)     Frontier: (3, 4)
Frontier: (4, 3)     Frontier: (3, 4)
Frontier: (2, 4)     Frontier: (4, 3)
Frontier: (3, 3)     Frontier: (2, 4)
Frontier: (3, 3)     Frontier: (4, 4)
Frontier: (4, 2)     Frontier: (3, 3)

I leave it as an exercise for you to draw this with pen & paper. Can you take it from here?

Note that the duplicate (3, 4) is version 2 is suspicious. Can you guess where it comes from?

  I would like to know if there is a "canonical" version which is considered best practice.

You typically want the invariant that everything in the queue is already put in the seen queue. As a formula, this amounts to saying $$\text{work queue}\ \subseteq\ \text{seen queue}.$$

Otherwise, you could pick the tip of the work queue, say item $i_1$, go through its neighbors to then add its neighbor $i_2$ to the work queue. However, $i_2$ was already part of the work queue before (perhaps just after $i_1$!), but you couldn't know since you didn't keep the seen queue synchronized.

Hence, implementing this invariant amounts in your code to

putting start onto the seen queue

queue = collections.deque([[start]])
seen_or_visited = set([start])

choosing version 2, i.e.

seen_or_visited.add(next_pos) # Uncomment for version (2)

You may also want to comment out version 1, i.e.

#seen_or_visited.add(frontier) # Uncomment for version (1)

since the invariant, fulfilled by the two points above, guarantees that whatever you pick from the queue (here, frontier) has already been added to the seen queue.

By the way, your function is missing a return None in case it doesn't find the target position.


In asymptotic notation how to prove that $\mathcal{O}(g(n))\subseteq\mathcal{O}(f(n))\implies\mathcal{O}(f(n)+g(n))=\mathcal{O}(f(n))$

I think you are pretty much done.

$$
g(n) \ge 0 \implies f(n) \le f(n) + g(n), \quad \forall n \in \mathbb{N}
$$

So pick $c = 1 \in \mathbb{R}^+$ and $n_0 = 1 \in \mathbb{N}$, then
$$
f(n) \le c\cdot(f(n) + g(n)), \quad \forall n\ge n_0
$$


How to Trace Path in Proof that Regular Languages are Closed Under Reversal

Whether a proof is sufficiently detailed is in part a question of taste. Your last statement is very general and with little detail. A more detailed argumentation could be like this:

Let the path from $q_0$ to $q_{acc}$ go through the sequence of states $q_0 -> q_1 -> ... -> q_{n-2} -> q_{n-1} -> q_{acc}$.
Transition $q_{n-1} -> q_{acc}$ reads the letter $w[n]$ (w has length n) which is equal to $w^R[1]$. According to the third clause in the definition of $\delta'$ there is a transition $\delta'(q_{acc},w[1]) = q_{n-1}$ which can start a path for $w^R$ in M.
Now you can continue by induction or by simply stating that the same is true for every transition in the path for $w$. At any rate, since your construction is on the level of transitions, your argumentation should go down to the level of transitions somewhere and not stop at the level of paths.


Converting between (standard) primal to dual forms (LP)

In class you have been shown several algorithms:

Algorithm A: Convert a primal canonical to a dual canonical.
Algorithm B: Convert a primal canonical to a primal standard.
Algorithm C: Convert a primal standard to a dual standard.
Algorithm D: Convert a dual standard to a dual canonical.

Notice that if you run Algorithms B,C,D in sequence, then you get another algorithm for converting a primal canonical to a dual canonical. The question is to compare the dual canonical program constructed this way to the one constructed by applying Algorithm A.


How exactly does a Max 2 Sat reduce to a 3 Sat?

It seems that the lecture note has abused the symbol $c_i$. You should check the original paper.

Replacing each clause $C_i = (a_i \lor b_i \lor c_i)$ of 3CNF by the collection of 2CNF clauses:

$$(a_i), (b_i), (c_i), (d_i), (\bar{a_i} \lor \bar{b_i}), (\bar{a_i} \lor \bar{c_i}), (\bar{b_i} \lor \bar{c_i}), (a_i \lor \bar{d_i}), (b_i \lor \bar{d_i}), (c_i \lor \bar{d_i})$$

where $d_i$ is a new variable.

  Theorem: If an assignment $\alpha$ satisfies $C_i$, then exactly seven of the ten clauses in the 2-CNF collection can be satisfied.

Proof: $\alpha$ satisfies $C_i$, then either one, two, or three of $a_i, b_i, c_i$ must be true. In all cases, there is a truth setting for $d_i$ causing exactly seven of the clauses to be satisfied. For example, suppose $a_i = \top, b_i = c_i = \bot$, then $d_i = \bot$ causes 7 clauses to be satisfied.

  Theorem: If an assignment $\alpha$ does not satisfy $C_i$, then exactly six of the ten clauses can be satisfied.

Proof: $\alpha$ does not satisfy $C_i$, then $a_i = b_i = c_i = \bot$. In this case, if $d_i = \top$, 4 clauses are satisfied; if $d_i = \bot$, then 6 clauses are satisfied.


Recovering data from under sampled data streams

It's not the same, but it reminds me of super-resolution.


Are non-trivial sets formed by set operations on NPC sets still in NPC?

Non-trivial sets formed from the unions and intersections of NP-complete sets are also not
necessarily NP-complete (of course this is all under the assumption
that P != NP).

Let $L$ be a NP-complete language, $A$ be any set in P, and $B:=
{\{0,1\}}^*$.  Then the following sets are all NP-complete since they
are just the disjoint unions of a sets based on $L$, $A$, and $B$.

$L_1 := 00L \cup 01A$

$L_2 := 11L \cup 01A$

$L_3 := 01L \cup 10B$

$L_4 := 10L \cup 01B$

Then $L_1 \cap L_2 = 01A$ and $L_3 \cup L_4 = 01B \cup 10B$
These results are both in P and and non-trivial sets.

On the other hand, as mentioned in a comment above, the Cartesian
product of two NP-complete sets is always NP-complete:  If $X$ and $Y$
are two NP-complete sets  then $X \times Y$ is in NP since a
NP-witness for $(x,y) \in X \times Y$ is simply a witness for $x \in
X$ along with a witness for $y \in Y$.  Furthermore, the map $x
\rightarrow (x,y_0)$ is a polynomial time reduction from $X$ to $X
\times Y$ where $y_0$ is a fixed member of $Y$.


Lower bound of degree of polynomial approximating parity

You can show a polynomial of degree $O(\sqrt{n\log n})$ can agree with parity on all but $o(1)$ fraction of the inputs. (In fact, this argument should work for anything of degree $\omega(\sqrt{n})$).

Let $S = x_1 + x_2 + \dots + x_n$. Note that $\text{MOD}_2(x_1, x_2, \dots, x_n)$ can be written as a single-variable function of $S$. By Lagrange interpolation, there exists a univariate polynomial of degree $O(\sqrt{n\log n})$ in $S$ (and hence in the $x_i$s) that agrees with $\text{MOD}_2$ on the interval $S \in [(n-\sqrt{n\log n})/2, (n+\sqrt{n\log n})/2]$. By the central limit theorem, this range of $S$ accounts for all but $o(1)$ of the $2^n$ inputs $(x_1, x_2, \dots, x_n)$.


Minimum number of ways to write a string

First observation: As first pen you can always take a pen with which you can write the longest prefix.

Let's consider given pen-strings as bit stings. For each such bit string let's generate all substrings which correspond to subsets of an initial bit string and put them in hashtable. Moreover, let's generate them in descending (by nesting) order and when we generate some bit string which is already in hashtable, we terminate this branch of recursion. So each of $2^{20}$ possible bit strings will be generated at most twice.

Precompute for each prefix of string $S$ the number of times $i$-th letter occurs in it.

Then let's walk by string $S$ from left right and on each step let's check whether current prefix can be written with a single pen. We can do it in $O(1)$ using precomputed hashtable and prefixes.

So the overall complexity is $O(2^\alpha + K + N\cdot\alpha)$, where $\alpha$ is an alphabet size ($20$ in our case).


How do you prove a heuristic is admissible?

Proving a heuristic is admissible usually means proving two things:

it follows the triangular inequality principle
given the same preconditions, the heuristic never overestimates the actual solution


Can we use Big O notation to predict actual running time of the algorithm on machine?

I'll give you an example where it unexpectedly goes totally wrong:

Write a program that calculates the product of two square matrices with real values, stored as double precision numbers. Use the straightforward algorithm where c [i, j] = sum of a [i,k] * b [k,j]. Measure and print the time for say n = 1 to n = 1000 (this will take a while). The time is $\Theta(n^3)$, so if r (n) is the measured time, you are interested in $c_n$ where $c_n$ is defined by $r (n) = c_n·n^3$.

You will find several interesting effects. You might expect that $c_n$ is quite large for n = 1, 2, 3 etc. because all the overheads are quite large compared to $n^3$, and at some point $c_n$ stays quite unchanged.

If you learned about cache memory, you will realise that a modern processor may have say 64KByte of very fast L1 cache, maybe 256KByte of fast L2 cache, say 4M of not so fast L3 cache, and uncached memory is quite slow. So as n grows, $c_n$ will jump up every time the memory used exceeds one of those cache limits.

But there are worse problems: The naive algorithm uses a really bad pattern to access memory, but how bad it is depends on particular values of n. Worst case is n = multiple of a large power of 2. You can expect the runtime for n = 128 to be massively larger than for n = 127 or n = 129.

So I'd say your advisor is completely wrong.


Route finding on a graph that must go through multiple edges

I have decided that the best solution to this is a variation on Dijkstra's algorithm. Since it doesn't require a Hamiltonian Circuit and makes it easy to manage the weights. I will also use Homeomorphism as suggested in the comments of the question to make weighting the distance between the nodes and addresses more accurate.


If L is not regular and is a proper subset of L1, does it follow that L1 is not regular?

@Vladislav's answer is probably more interesting, but observe that every language over an alphabet $\Sigma$ is a subset of $\Sigma^*$, which is certainly a regular language.


I would say that at t=0 the first bit would begin getting pushed on the link, which would imply that the 245th bit would begin getting pushed at t=244. Thus you'd want to start pushing at t=244.

Disclaimer: I know nothing of networking and little of comp sci but hey, I thought I'd give the logic a whirl. I could be completely wrong.


Polynomial-time algorithm for Graph Isomorphism in case of Maximum Constrained Maximum Degree

Algorithms used in practice differ a lot from theoretical algorithms. One popular software package is nauty. The link should also explain the algorithms used, which probably rely on combinatorial methods.

As for the running times for specific algorithms, they are likely stated in the papers. I suggest checking the references.


Split graph in two parts, such that most nodes have even number of edges

By induction , we can prove that a partition exists with all nodes having even degree within the partition.
If all vertices have even degree , then we are done (Just partition it into the whole graph and an empty graph)
Otherwise let $v$ be a node with odd degree , now modify the graph by inverting the neighbourhood of $v$ (If $a$ and $b$ are neighbours of $v$ , then if they have an edge , remove it otherwise add it) and also remove $v $ from the graph , for the new graph , split it into 2 parts $A$ and $B$ such that all nodes in $A$ and $B$ have even degree , add $v$ back to $A$ if $A$ has even neighbours of $v$ , else add it to $B$. This works because in $A$(Or $B$ if we added $v$ to $B$) all degrees are even except for neighbours of $v$ which become even after adding $v$


Why is there the regularity condition in the master theorem?

Not a rigorous proof, but a "from the top of my head" explanation.

Imagine the recurrence $aT(n/b)+f(n)$ as a tree. The third case covers the scenario when the root node dominates the running time asymptotically, i.e. most of the work is being done in measly node on top of the recurrence tree. Then the running time is $\Theta(f(n))$.

To make sure the root actually does more work you need the

  $a f(n/b) \leq cf(n)$.

This says that $f(n)$ (the amount of work done in the root) needs to be at least as big as the sum of the work done in the lower levels. (The recurrence is called $a$ times on $n/b$ of the input.)

E.g. for the recurrence $T(n)=2T(n/4)+n$ the work on the level below the root is one fourth as big and only done twice $(n/4+n/4)$ versus $n$ so the root dominates.

But what if the function didn't fulfill the regularity condition? E.g. $\cos(n)$ instead of $n$? Then the work done on the lower levels might be bigger than the work done in the root so you are not certain that the root dominates.


Suppose your array has $n$ elements.  As you have noted, the median is always in the bigger part after the first partition.  The bigger part has size at most $\alpha n$ if the smaller part has size at least $(1-\alpha) n$.  This happens when you pick a pivot that isn't one of the smallest or largest $(1-\alpha) n$ elements.  Because $\alpha > 1/2$, you know these are disjoint sets, so the probability of hitting one of the bad pivots is just $2 - 2\alpha$, and $1- 2 + 2\alpha=2\alpha - 1$.


Dynamic selection of cache replacement policy

Various processors have had instructions that affect cache operations. Some examples:

Clear cache line. This takes a memory address, allocates a cache line for it, and sets all data in the memory area contained in that cache line to values with no information content (usually all zeroes). This allows then storing data without reading the cache line.
Uncached read. This takes a memory address, reads the data, but doesn’t write it to the cache.
Prefetch: This takes a memory address and loads the data into cache without giving the results to the CPU. So when the data is needed later it’s already in the cache, no wait needed.
Streaming: Whenever data is read, the processor starts filling either the next or the previous cache line.


Approximate subset sum with two-dimensional vectors

Let $\rm V$ be the $2 \times n$ matrix whose $i$-th column is vector $\rm v_i$. We have the Boolean optimization problem in $\mathrm z \in \{0,1\}^n$
$$\min_{\mathrm z \in \{0,1\}^n} \| \mathrm V \mathrm z + \mathrm w \|_2^2$$
Let
$$\rm z = \frac 12 (x + 1_n)$$
where $\mathrm x \in \{\pm 1\}^n$. Hence, we have an instance of the Boolean least-squares (BLS) problem
$$\min_{\mathrm x \in \{\pm 1\}^n} \| \mathrm A \mathrm x - \mathrm b \|_2^2$$
where
$$\rm A = \frac 12 V \qquad \qquad \qquad b = - \left( \frac 12 V 1_n + w \right)$$
Since $\{\pm 1\}$ is the solution set of the quadratic equation $x_i^2 = 1$, we have the following (non-convex) quadratically constrained quadratic program (QCQP) in $\mathrm x \in \mathbb R^n$
$$\begin{array}{ll} \text{minimize} & \| \mathrm A \mathrm x - \mathrm b \|_2^2\\ \text{subject to} & x_i^2 = 1 \quad \forall i \in \{1,2,\dots,n\}\end{array}$$
Exhaustive evaluation of the objective function at all $2^n$ points is only feasible for small $n$.

SDP relaxation
Note that
$$\begin{array}{rl} \| \mathrm A \mathrm x - \mathrm b \|_2^2 &= (\mathrm A \mathrm x - \mathrm b)^{\top} (\mathrm A \mathrm x - \mathrm b)\\ &= \mbox{tr} \left( (\mathrm A \mathrm x - \mathrm b)  (\mathrm A \mathrm x - \mathrm b)^{\top} \right)\\ &= \mbox{tr} \left( \begin{bmatrix} \mathrm A & -\mathrm b\end{bmatrix} \begin{bmatrix} \mathrm x\\ 1\end{bmatrix} \begin{bmatrix} \mathrm x\\ 1\end{bmatrix}^{\top} \begin{bmatrix} \mathrm A & -\mathrm b\end{bmatrix}^{\top} \right)\\ &= \mbox{tr} \left( \begin{bmatrix} \mathrm A^{\top}\\ -\mathrm b^{\top}\end{bmatrix} \begin{bmatrix} \mathrm A & -\mathrm b\end{bmatrix} \begin{bmatrix} \mathrm x\\ 1\end{bmatrix} \begin{bmatrix} \mathrm x^{\top} & 1\end{bmatrix} \right)\\ &= \mbox{tr} \left( \begin{bmatrix} \,\,\,\, \mathrm A^{\top} \mathrm A & -\mathrm A^{\top}\mathrm b\\ -\mathrm b^{\top}\mathrm A & \,\,\,\, \mathrm b^{\top}\mathrm b\end{bmatrix} \begin{bmatrix} \mathrm x \mathrm x^{\top} & \mathrm x\\ \mathrm x^{\top} & 1\end{bmatrix} \right)\end{array}$$
Since $\mathrm x \in \{\pm 1\}^n$, all $n$ entries on the main diagonal of $\mathrm x \mathrm x^{\top}$ are equal to $1$. Thus,
$$\begin{bmatrix} \mathrm x \mathrm x^{\top} & \mathrm x\\ \mathrm x^{\top} & 1\end{bmatrix}$$
is symmetric, positive semidefinite and has only ones on its main diagonal, i.e., it is a correlation matrix. Its rank is $1$. Let
$$\mathrm C := \begin{bmatrix} \,\,\,\, \mathrm A^{\top} \mathrm A & -\mathrm A^{\top}\mathrm b\\ -\mathrm b^{\top}\mathrm A & \,\,\,\, \mathrm b^{\top}\mathrm b\end{bmatrix}$$
Hence, the BLS problem can be written as the following rank-constrained optimization problem in $(n+1) \times (n+1)$ symmetric matrix $\rm Y$
$$\begin{array}{ll} \text{minimize} & \langle \mathrm C , \mathrm Y \rangle\\ \text{subject to} & y_{ii} = 1, \quad \forall i \in \{1,2,\dots,n+1\}\\ & \mathrm Y \succeq \mathrm O_{n+1}\\ & \mbox{rank} (\mathrm Y) = 1\end{array}$$
which is a hard problem due to the rank constraint. Relaxing the optimization problem above by discarding the rank constraint, we then obtain the following semidefinite program (SDP) in $\rm Y$
$$\boxed{\begin{array}{ll} \text{minimize} & \langle \mathrm C , \mathrm Y \rangle\\ \text{subject to} & y_{ii} = 1, \quad \forall i \in \{1,2,\dots,n+1\}\\ & \mathrm Y \succeq \mathrm O_{n+1}\end{array}}$$
which is convex and computationally tractable. This SDP relaxation provides a lower bound on the minimum of the original BLS problem. In the very, very fortunate case where the optimal solution of the SDP happens to be rank-$1$, we have solved the BLS problem.

References

Alexandre d'Aspremont, Stephen Boyd, Relaxations and Randomized Methods for Nonconvex QCQPs, EE392o, Stanford University, Autumn 2003.

Stephen Boyd, Convex Optimization, IAM-PIMS, Vancouver, 3/15/04.

Laurent El Ghaoui, Homework Assignment #1, EE227A, January 2012.

Semidefinite relaxation for Boolean least squares, Mathematics Stack Exchange.


How to Efficiently Define the Natural Numbers in Type Theory

There's nothing stopping you from defining binary numbers in type theory, and this should give greater efficiency in practice.

For example:

https://coq.inria.fr/library/Coq.Numbers.BinNums.html

EDIT: Why not base 10?

Comparison on binary numbers can be done in $O(\log_2 n))$ time. If you have base 10, you can do it in $O(\log_{10} n)$ time. But if we apply the change of base formula, $O(\log_{10} n) = O(\log_{2} n / \log_{2} 10) = O(\log_2 n)$, since $O(\log_2 10)$ is constant.

There's a speed tradeoff. You get constant speedup for some operations, but you get constant slowdown for others. For example, each pattern match now has 11 options instead of 3. So, given that they have the same asymptotic behavior, we usually go with the simplest one.

Finally, the advantage with base 2 is that, if you limit yourself to 32 or 64 bits, you can represent them using machine integers, for example, if you extract your Coq code to OCaml, which means you can get very fast extracted code.


How to prove that a language is not regular?

Proof by contradiction is often used to show that a language is not regular: let $P$ a property true for all regular languages, if your specific language does not verify $P$, then it's not regular.
The following properties can be used:

The pumping lemma, as exemplified in Dave's answer;
Closure properties of regular languages (set operations, concatenation, Kleene star, mirror, homomorphisms);
A regular language has a finite number of prefix equivalence class, Myhill–Nerode theorem.

To prove that a language $L$ is not regular using closure properties, the technique is to combine $L$ with regular languages by operations that preserve regularity in order to obtain a language known to be not regular, e.g., the archetypical language $I= \{ a^n b^n \mid n \in \mathbb{N} \}$.
For instance, let $L= \{a^p b^q \mid p \neq q  \}$. Assume $L$ is regular, as regular languages are closed under complementation so is $L$'s complement $L^c$. Now take the intersection of $L^c$ and $a^\star b^\star$ which is regular, we obtain $I$ which is not regular.

The Myhill–Nerode theorem can be used to prove that $I$ is not regular.
For $p \geq 0 $, $I/a^p= \{ a^{r}b^rb^p\mid r \in \mathbb{N} \}=I.\{b^p\}$. All classes are different and there is a countable infinity of such classes. As a regular language must have a finite number of classes $I$ is not regular.


States 2 and 5 are distinguishable. We have $(2, 5)\stackrel{b}{\longrightarrow}(1,5)$ and state 1 is a non-final state while state 5 is final. In addition, as HueHang and Amy have noted, $(6, 3)$ is also distinguishable, so the original DFA is already mimimized.


Why is there a precision loss for floating-point numbers?

Many people can afford to buy a computer with a powerful processor and say 128GB of RAM. Maybe the same cost as a small car.

That's enough to store one number with 300 billion digits. It's enough to store 300,000 numbers of a million digits. But it is also enough to store 16 billion double precision floating point numbers. There are problems where 300,000 numbers are nothing.

The number of operations is another matter. That computer can probably do 50 billion floating-point operations per second. It cannot do anywhere near that number of operations with one million digit numbers. Going down from 50 billion operations to 10,000 operations with one million digit numbers, that hurts.

Higher precision is almost never needed. And if it is not needed, it is an absolute waste of speed and memory. And remember that with a million digits precision, 0.1 + 0.2 still doesn't equal 0.3, but it equals 0.3 (one million zeroes) 4.


How does Server know window size for TCP Header?

The Window Size field in the TCP packet header is the number of bytes the sender will buffer for the response. Basically, during the handshake each side will say how large its receive window is. That is, the Window Size field in a packet sent by the client, tells the server how much data the client can receive and thus how much the server can send before the client would need to drop packets. Symmetrically for the packets the server sends to the client. See the flow control section for details on how the window size changes. Of course, see the relevant RFCs for the authoritative recommendations.

As far as how the initial receive window is calculated, this is based on local resources and policies. Clearly, the initial receive window shouldn't be set to be larger than the amount of buffer memory you have. For a specific connection, larger is better for throughput if packets aren't being dropped, but larger packets are more likely to be dropped and when they are dropped require more data to be resent. RFC3390 presents a recommendation for what the initial receive window size should be assuming local resource limitations aren't a concern. This link describes what the Linux 2.6 kernel did (at least for RedHat distributions), though it may be out of date.

There is a different thing called the congestion window which each host may maintain itself as an estimate for how much data it can reliably send. This isn't communicated since it's unlikely there's anything the receiving end can do about it as it may well be intermediate nodes in the network that are limiting the rate. Again, this is an estimate and many variations of TCP are due to different strategies to estimate this value. Hosts don't have to agree on these congestion control algorithms for TCP to work.


One approach to see what is going on here is via the notion of an open ball under a given distance. Given a distance $d$, the open ball of radius $r$ around a point $p$ is given by $B_r(p):=\{q\mid d(p,q)<r\}$, i.e. the set of all points with distance less than $r$ to the center of the ball, $p$. In the plane and under the Euclidean distance, a ball is an open disk (a disk with the boundary removed) of radius $r$.

Since $\delta$ is the minimum distance between any pair of points in the left half, any pair of points in the left $\delta\times\delta$ square has a distance of at least $\delta$. This is equivalent to saying that the open ball of radius $r$ centered at a point $p\in P_L$ contains no other point $q\in P_L$. So, the maximum number of points from $P_L$ that can be in the $\delta\times \delta$ square is the largest number of points you can 'fit' into the square such that the ball surrounding each of those points contains no other point from $P_L$.

An open ball under the Euclidean distance is an open disk. If you place four points at the corners of the $\delta\times \delta$ square, the open disks of radius $\delta$ centered at those points together cover the entire square, so there is no position in the square to place for a fifth point.

However, under the Manhattan distance, an open ball of radius $\delta$ is an open square with diagonal length $\delta$, rotated by $45$ degrees (an "open diamond"). If we place such an open diamond at each corner of the $\delta\times \delta$ square, then there is exactly one position in the square not covered by an open diamond: the center of the square. This is the location where you can place a fifth point under the Manhattan distance.

As for the $L_m$-distance with $m>2$, note that the balls under these metrics all strictly contain the ball under the $L_2$-distance. I'll leave it up to you to use this fact to determine the maximum amount of points that can be in the $\delta\times\delta$-square.


Is it possible for a stack-based programming language to be concurrent?

So, can stack-based programming languages be concurrent?

Sure.

  Could they achieve concurrency by using multiple stacks at the same time or something alike?

Already for normal languages multi-threading usually means having multiple "call" stacks. It would be completely natural to give each thread its own data stack. It would be straightforward to have an actor, say, whose body was implemented by code in a stack-based language. Explicit parallelism a la GHC's par annotations should be reasonably straightforward. The main issue with executing things in parallel is that you don't know what the stack effect of the code will be until you execute it. However, using a Joy-like syntax, one could imagine [a b c] par as executing a b c either against an empty stack or a copy of the stack and only keeping the top-most element of the stack on completion (or pushing some dummy value if the stack is empty). You could imagine variations. Implicit parallelism would be harder to do naively as compared to, say, a purely functional language, but certainly could be done as well. The compiled code of a user-defined combinator is often not too different from "normal" code.

  Is it possible to implement lazy evaluation in a stack-based programming language?

Unknown stack effects are again the tricky part. If you design the language such that all stack effects can be determined statically, then it doesn't seem too challenging. If you have laziness be explicit, then it also seems relatively straightforward and would look roughly like Joy's quotations and i. One language that calls itself a lazy concatenative language seems to do a mixture of both of the above approaches from what I can tell. I don't really see how an implicitly lazy concatenative language would work in the face of dynamic stack effects, at least not in any vaguely usable way, but that might just be a lack of imagination on my part.

Incidentally, it is not uncommon for stack-based languages to have multiple stacks, e.g. Forth has a data stack and a return stack upon which you can also place arbitrary data.


Does preparing min DFA by combining equivalent states always result in min DFA

The answer to Q1 is no.

$1^{11}$ is in $(1^3 + 1^5)^*$, but not in $(1^3)^* + (1^5)^*$

I think that leads to the remaining confusions.


General Approach To Calculate Minimum Number Of Flip-Flops Required

The links you have provided (gateoverflow) are themselves quite helpful. However if you want a even more elaborate explanation then read further.

In the very first question you have sequence 0--1--0--2--0--3
now these numbers represented in binary are:  00--01--10-00-10--00-11
So clearly you would need 2 bits to determine each of those number so 2 FF for that. Moreover there are 3 similar states for that are 000,000,000 so in order to differentiate between them you further would require 3 combinations that would need log(3)base2 digits =2 digits. thereby 2 FF would be required here too.

So that is a total of 2+2 Flip flops required.
Let me know if I could help you further.


A Turing Machine that can only move right can only read its input once, hence I don't see how it could be more powerful than a DFA.

It does have the ability to write to the tape, but it can't go back to read what it wrote, so this can't be used as memory. I seems that it's essentially equivalent to a Finite State Transducer, which are DFAs that have an output tape as well as input, but are no more powerful. In this case, the TM just happens to overwrite the input as it goes, rather than having a second tape.


How to read $NC^1\subset L \subset NL \subset SAC^1$, $SAC^1=LOGCFL/poly$, and similar statements?

The source of the confusion is probably uniformity. A circuit class like $\mathsf{NC}^1$ can be defined in two different ways:

Languages computed by bounded fan-in circuits of polynomial size and logarithmic depth.
Same as 1, only the circuits are uniform: there is an efficient Turing machine that on input $1^n$ generates the $n$th circuit.

The definition of uniformity is vague since there are several different definitions, many of them fitting the above description (with different definitions of efficient). The classic paper On uniformity within $\mathsf{NC}^1$ shows that many of these definition are in fact equivalent, and as far as I know, their common definition remains popular today. It often goes by the name "$\mathsf{AC}^0$-uniform".

If you want $\mathsf{NC}^1 \subseteq \mathsf{L}$ then you need the uniform version of $\mathsf{NC}^1$. If you want $\mathsf{NL}/poly \subseteq \mathsf{SAC}^1$ then you need the non-uniform version of $\mathsf{SAC}^1$.


Confirmation of alternative correctness proof for Floyd-Warshall's all-pair shortest-path algorithm

Your effort towards a new kind of proof for Floyd-Warshall algorithm is appreciated.

On one hand, your proof is very well written. It cannot be said to be all wrong as apparently you have tried to avoid saying anything wrong.

On the other hand, I would not call you proof a proof that is different from the usual induction proof on the loop variable of the outer-most loop.

  ... $p_m$ has the biggest index in the matrix, meaning that the algorithm would have already correctly found the length of $P_1$ and $P_2$ and stored them in $d_{i_{p_m}}$ and $d_{p_{m_j}}$, since they share intermediate vertices of smaller index and therefore would have been found in previous iterations of the outer-most loop.

Take a moment to reflect. What you said above is basically the induction hypothesis in the usual induction proof on the loop variable of outer-most loop. That induction hypothesis can be viewed as a proposition that is even stronger than the final result of the Floyd-Warshall algorithm. Armed with that kind of knowledge, it is expected the correctness can be proved easily. In other words, it is not far fetched to say you just proved its correctness by admitting its correctness. Or, you just repeated the usual proof with some extra unnecessary logic.

There is another hidden flaw in your proof that is actually critical. Suppose there is a negative cycle in a connected graph. Floyd-Warshall algorithm handles that situation graciously. However, there is no shortest paths between any pairs of vertices in the graph, since given any path, you can always find another path that is shorter. So, your induction hypothesis becomes void in that case.


How a reduction can help up solve a problem?

This is a natural trap that almost everyone falls into when encountering this style of reduction for the first time - you have your logic inverted, but in an understandable way.

To start with, note a couple of things:

If $N$ accepts at least one string, it accepts every string, so $L(N)$ is either $\emptyset$ or $\Sigma^{\ast}$, nothing in between.
$\langle N \rangle$ is an encoding of a Turing Machine, and what we want to know is whether we can decide if $\langle N \rangle$ is in $L$ or not.

So the argument is by contradiction. Imagine that we did have a TM $X$ that decided $L$, then we could give it $\langle N \rangle$ and, as it decides $L$, it would say, correctly, $\mathrm{Yes}$ or $\mathrm{No}$.

But if it says $\mathrm{Yes}$, then we know that $M$ halts on $x$, because that's how we built $N$, and similarly if it answers $\mathrm{No}$, $M$ doesn't halt on $x$.

So having $X$ (i.e. being able to decide $L$) allows us to decide the Halting Problem, and hence we have a contradiction.

Note that we're not trying to 'run' $N$, we're asking if there can possibly be an $X$ that looks at $\langle N\rangle$ and says something about it (for every $N$).


What is a sticky bit in computer architecture?

A sticky overflow bit means that the next operation that does not overflow (but would set the bit if it did) will not clear the bit. The value is sticky/persistent and must be cleared to detect newer overflows.


Number of seeks in an I/O efficent algroithm

You're missing the trivial point that the input is on disk, and needs P seeks to be read, while the output needs to go to disk and needs Q seeks to be written. (Or 1+1 in the cases they're contiguous on disk).

This is just setting the baseline; when you exceed the internal memory size you'll need more seeks to write out temporary data structures.


Is a sum of n terms considered O(1) or O(n)?

If you have ten elements, then that's a constant and considered $O(1)$.  However, if you're given an input to a function, and want to analyze the running time of your algorithm in terms of the input length, then that's $O(n)$, provided that you at least read the entire array (and $n$ is the array length).

It all has to do with what you measure your running time in.  In parameterized complexity, for instance, we typically measure the complexity in two parameters; the length of the input, and an additional parameter $\kappa$.  Hence, there you will often see running times like $O(n \cdot 2^\kappa)$.

In your problem, we say $O(n)$ because we sometimes consider "summing integers" as a constant operation.  That's obviously not possible if we allow arbitrarily large integers.  If the max (absolute) integer is $N$, then your algorithm might be $O(n \log N)$.


Greedy heuristic for buying fewest fridges of set temperature for products that can be kept in some temp. ranges?

The formalized problem here is selecting the minimum number of points such that for each temperature interval $\ell_i\in L$ we have at least one point that covers it. Let each interval $\ell_i$ be represented by $(c_i, h_i)$

Order all $\ell_i\in L$ by their $h_i$.
While there are still items that need fridges.

Buy a fridge and set it to $h_1$.
For every item with $c_i\leq h_1$, put item $i$ in the fridge and discard the interval from $L$

The runs in $O(n\lg n)$ time.

We can show this is optimal. Let the solution obtained above be $S$ and let any feasible solution be $R$. We can show that for any point $x_i\in R$, there is at most one point from $S$ between $x_{i-1}$ and $x_i$.

If the above is not true then we have some $x_{i-1}\leq y_{j-1} < y_j < x_i$ for both $x\in R$ and both $y\in S$. In this case, the interval $\ell_k$ ending at $y_j$ would not be covered by $R$. $x_i$ can’t cover it, since by definition $y_j < x_i$. $x_{i-1}$ can’t cover it either. If it did, that would mean the start point of $\ell_k$ would be less than $x_{i-1}$ and thus also less than $y_{j-1}$. This can’t be the case, though, because then $y_{j-1}$ would have covered $\ell_k$, therefore removing it from the list of intervals in the next step our algorithm. Thus we have shown that for any point $x_i\in R$, there is at most one point from $S$ between $x_{i-1}$ and $x_i$ and therefore $S$ is optimal.


Note that using an existential quantifier in front of a decidable language we can obtain any r.e. language, i.e. every r.e. language is expressible as

$$ \{ x\in \Sigma^* \mid \exists y \in \Sigma^* \ \langle x,y \rangle \in V \} $$

where $V$ is a decidable language. These include undecidable r.e. languages like
$$A_{TM} = \{ \langle e, x\rangle\ \mid \text{$e$ encodes a Turing machine which accepts $x$} \}$$.

The only difference here is that here we have to separate $x$ and $y$ ourselves. The standard trick is to use a new symbol to separate the two parts (assume that the separator belongs to $y$). Therefore any r.e. language including undecidable ones can be expressed in this format.

For the second question, there is no general algorithmic way to check if the prefixes of a  given decidable language is undecidable. This follows from Rice's theorem.


NP-hardness does not imply lower bound, strictly speaking?

Yes, if P = NP then any decision problem is NP hard as long as there is one problem instance where the answer is "YES" and one where the answer is "NO".

Just check the definition of NP-hard (and check why problems where every instance has the answer YES or every instance has the answer NO are not NP-hard by that definition).


What is the Space Complexity of Tail Recursive Quicksort?

If you either use a compiler that supports tail recursion, or make the small change not to use recursion for the larger partition at all, the recursion depth depends on the sizes of the smaller intervals.

The worst case for recursion depth is the case that each partition divides your subarray exactly in half, making the depth $log_2 (n)$. The best case for recursion depth is the case that each partition divides your subarray into n-1 and 1 items, recursion depth = 1 (obviously the absolutely worst case for execution time).

So this is a bit paradoxical: Best case space complexity = worst case time complexity. But on the other hand, worst case space complexity = log n is so little that nobody cares about the space complexity. As long obviously as people don't make the mistake of sorting the larger partition first.

Without eliminating the recursion for the larger half, the worst case for recursion depth is n, and the order of the calls doesn’t matter.

Usually you can’t make an assumption that values would be different, so the quality of your partition function is important. Some will misbehave with many identical values.


Massalin's Synthesis Quajects equivalent to ASM generating macros used in Game Oriented Assembly LISP?

As I see it, a Quaject is a kind of software component in the sense that it has a provided interface (the callentry functions), which contains the functions it offers, and a required interface (the callout functions), which contains the functions it needs  to operate. The callback part of the interface is for call back functions, which are functions that are available to call the caller of a function. (In Java you cannot call the caller unless an explicit reference is passed.)

I don't think it is correct to say that "a Quaject is construct that generates Assembler customised for the function being used at the time." For example, in Section 4.1.4 of the thesis it states that

  Higher-level kernel services are built by composing several basic
  quajects.

So the quajects are the ingredients that are used to build the custom services. They do not build them.

GOAL seems to be a variant of Scheme that allows inline assembly language, which I can image allows quite some flexibility in the programming. The language is compiled to assembly. The assembly language it includes is not in the shape of any sort of component, as far as I can tell.

Based on this, I would say that the answer to your question is no.


IS there a consensus on the definition of a computer program in CS literature and if so, what is it?

Computer Science is far too diverse to have a single notion of program. For a theoretician, it might be an input tape to a universal Turing Machine, or any lambda expression in lambda calculus. For someone working on the front end of a compiler, it could be defined by a formal grammar while for someone working on the back end, or to the HW architect, it might be a sequence of binary instructions. For someone working on operating systems, it might be any file with the executable bit set.

Perhaps it could be said that a unifying theme is any form of information that can used to control the operation of a process, or an abstract or real machine, to produce information in the same or different form.

For some, I’m sure this will be too broad, for others, too narrow.


Can g(n) be same for big O and omega notation for f(n)

If you write down $f \in O(g)$ and $f \in \Omega(g)$ then you clearly intend both instances of "$g$" to refer to the same function. Otherwise, it would be pretty confusing.

Note how this is equivalent to $f \in \Theta(g)$.

If, however, you write down $f \in O(n^2)$ and $f \in \Omega(n)$ and want to unfold both the definition of $O$ and $\Omega$, you'll have to instantiate two different "$g$"s. That is, you'd write

$\qquad c_1 g_1(n) \leq f(n) \leq c_2 g_2(n)$

for all $n \geq n_0$ for some $c_1, c_2 > 0$ and $n_0 \geq 0$. Here, we know that $g_1 = n \mapsto n$ and $g_2 = n \mapsto n^2$.


Getting minimum DFA for regular expression (11)*+(111)*

The problem is that you did not make state $A$ accepting during $\epsilon$ transition elimination. Since it has $\epsilon$ transitions to accepting states, you should have done so. As a result, the automaton you obtain doesn't accept the empty word as it should. If you fix this, minimization then merges $A$ with $B,D$.


Proving the validity of a sequent using Modus Tollens

Modus Tollens is the following rule:

Given $A \to B$ and $\lnot B$, deduce $\lnot A$.

In your case, you are given $p \to (q \lor r)$, and so $A = p$ and $B = q \lor r$. Therefore you need to prove $\lnot B = \lnot (q \lor r)$. This is not the same as $\lnot q \land \lnot r$, though the two are logically equivalent. What you have to do is deduce $\lnot (q \lor r)$ from the premises $\lnot q$ and $\lnot r$.


Are Elementary Cellular Automata structures considered to be fractals?

Cellular automata can generate fractal patterns (as in the case of Rule 90), but they don't always (e.g., Rule 0).

Willson was perhaps the first to demonstrate that CA can produce fractal patterns in the early 80's.

Shortly thereafter Wolfram characterized the fractal properties of a variety of 2-D CAs.

A few years later Culik and Dube went a bit further and proved that certain types of CA :

  ...will always produce a highly regular [fractal] behavior on an arbitrary finite configuration as the initial seed.

The take-home message is that some very simple CA rule sets generate complex behavior, but others don't do anything interesting at all.


About the interpretation of the SOS hardness results of the planted Max-Clique problem

The planted clique problem and the maximum clique problem are different problems, though the former was introduced as an average case version of the latter. A paper addressing the planted clique problem doesn't address the maximum clique problem, and vice versa.

In particular, the papers you mention concern the planted clique problem, not the maximum clique problem.


How to make a parse tree for the following propositional logic formula?

As it is, your formula is ambiguous; it is not clear which pair of parentheses to insert in order to get a binary tree. Both

$\qquad \displaystyle \varphi_1 \lor (\varphi_2 \lor \varphi_3)$

and

$\qquad \displaystyle (\varphi_1 \lor \varphi_2) \lor \varphi_3$

are feasible. Luckily for you, $\lor$ is associative, so you can choose either one:

[source]

For the purposes of parsing, you would either require formulae to be completely parenthesised, or specify operators to be left- (or right-) associative. Operator precedences would be the next thing to look into, in order to disambiguate formulae like

$\qquad \displaystyle a \land b \lor c$.


Update: There was an error in the answer sheet, it turns out I was right.


Regarding a theorem that says a language that is Turing-Recognizable iff some enumerator enumerates it

The Turing machine M is running the Turing machine E as its subroutine. In the other words, you can think of E's printer tape as another tape for Turing machine M. Although we don't know what is going on E, E's computation is part of (inside) M's computation. And of course, as nir shahr said in the comment, comparing is part of M's computation too.
I drew something maybe it can help to have some intuition.


L'Hôpital's rule shows that for $\epsilon > 0$,
$$
\lim_{n\to\infty} \frac{\log n}{n^\epsilon} =
\lim_{n\to\infty} \frac{\frac{1}{n}}{\epsilon n^{\epsilon-1}} =
\lim_{n\to\infty} \frac{1}{\epsilon n^\epsilon} = 0.
$$
In other words, $\log n = o(n^\epsilon)$ for all $\epsilon > 0$.
This immediately implies that $\log^C n = o(n^\delta)$ for all $C,\delta > 0$, taking $\epsilon = \delta/C$.


Conceptually, screen recording works by taking a screenshot of the screen many times per second.  Taking a screenshot works by taking a copy of what is displayed on the screen.  To understand how that works, you need to understand how things are displayed on the screen; for that, I recommend reading about framebuffers.  The screen capture might then be stored in a compressed or uncompressed format.  The file size will be influenced by the resolution of the screen, the length of the video, and what compression is used (if any).


How do I replace a D Flip Flop with a JK Flip Flop

Just as a hint, the general way to solve a problem like this is to write a truth table. The "inputs" to the truth table are the inputs to the machine plus the states of the flip-flops (one bit per FF), and the "outputs" are the outputs of the machine and the outputs of the flip-flops.

From that truth table, you can see if it's a Mealy machine. And given the desired "state on this time" and "state next time", and you can work out what the inputs to a J-K flip-flop should be:

 Q Q' | J K
------+-----
 0 0  | 0 X
 0 1  | 1 X
 1 0  | X 1
 1 1  | X 0

Where X is "don't care".

I only mentioned the truth table because you wanted to show that it was a Mealy machine, and finding the mapping of inputs and outputs is a definite way to get there.

As for the main question you're asking, you can't replace a D flip flop with a JK flip flop in the general case due to timing. D flip flops "read" their input on (say) the leading edge of the clock, and "output" their result effectively straight away, after a short propagation delay. JK flip flops, on the other hand, "read" on the leading clock edge and "output" on the trailing edge.

This property of JK flip flops can be useful; they are extremely resistant to combinational hazards, for example. But it does mean that they respond half a clock cycle later than a D flip flop.

Assuming that this isn't an issue (and I doubt it is in your circuit), you can just feed D into J and not-D into K.


Why F-bounded polymorphism and F-bounded quantification are called, well, F-bounded

It appears that "F" does not stand for anything in particular: rather, it is the metavariable symbol that is used in the definition of F-bounded quantification. In the paper in which F-bounded quantification was introduced, F-Bounded Polymorphism for Object-Oriented Programming, the authors write:

  To solve this problem and related difficulties with other forms of recursive types we introduce a generalization of bounded quantification which we call F-bounded quantification, for want of better terminology.

suggesting that they do not view the name as particularly descriptive. Later, when they define F-bounded quantification explicitly, they write:

  We say that a universally quantified type is F-bounded if it has the form
  $$\forall t \subseteq F[t] . \sigma$$
  where $F[t]$ is an expression, generally containing the type variable $t$.

As far as I can tell, the paper contains no other explanation and the most apparent explanation is that the "F" in the terminology is chosen to coincide with the symbol $F$ chosen, arbitrarily, for the definition.


A cache memory has a line size of eight 64-bit words and a capacity of 4K words

First, I'm going to do everything in bytes.

A 64-bit word means 8 bytes.

Line size: 8 words in a line, means 8 x 8 bytes = 64 bytes in a line = 26 bytes.

Cache size: 4k words, meaning 4096 x 8 bytes = 32k total bytes.

Cache indexes: 32k total bytes / 8 way set associative = 215 / 23 = 212 index positions in the cache line-set array.

Main memory: 1024 MBits = 1024 * 220 = 230 and, 230 / 8 bits-per-byte = 227 bytes (or 128 Mbytes).

So, that means there are 27 addressing bits in total for the cacheable memory.  Those 27 bits break down into 3 parts:

+--------------------+
| tag | index | rest |
+--------------------+

The "index", which is 12-bits in width, is used to lookup into the cache array to identify one cache line set.

The tag bits are used to isolate one of the lines in the set of 8 (or determine a miss).

The "rest" bits determine which bytes in the 64-byte line are the particular bytes of interest for a given memory reference instruction.  More precisely, the rest bits indicate the first byte of interest, and the memory reference instruction encodes the number of bytes of interest (e.g. 1, 2, 4, 8).

Since the line size is 64-bytes, then the "rest" is 6 bits; these 6 bits are used after the cache lookup identifies the line (on hit).

That means that the tag, which makes up the remainder, must be 27-12-6 = 9 bits wide.  A tag of this size is stored in the each cache line in the set for comparison with the tag in the address bits.

So, the 27 bits of address break down into 9 tag bits, 12 index bits, and 6 "rest" bits.  The cache line lookup operation consumes the 9 tag bits and 12 index bits, and, after the line is identified, the rest bits (and instruction-specified length) are used to extract the bytes of interest.


So, $F_{n} = f_{\{\, 0,1 \,\}^{n}}(x)$ for a fixed $x \in \{\, 0,1 \,\}^{n}$, right?

Nope. That's not right.  Consider the set of functions $\{f_s : s \in \{0,1\}^n\}$.  According to what you have written, $F_n$ is a random variable that is drawn uniformly at random from that set.  (I find this a confusing choice of notation, but I'm going with your proposed definitions.)

  This definition is seems correct, but it implies that $A$ can ask the query of $f_{s}$ for at most $poly(n)$ times, $s$ may be different, but $x$ is always the same. It looks strange.

Actually, what it means is that $s$ is the same for every query, but $x$ can be different for each query.  Yes, $A$ can only ask polynomially queries -- that's a crucial restriction.

  How about let $F_{n}$ be distribution of functions $f_s$ whose input $x$ is uniformly distributed over $\{\, 0,1 \,\}^{n}$

First off: Please don't redefine the meaning of existing notation.  $F_n$ was already defined to mean something else.  Don't define it to mean two different things in two different parts of your post.  That's just confusing.

Second, that definition doesn't make sense.  There's nothing such thing as a function whose input is uniformly distributed over something.  That doesn't make sense.  A function is a function; its a mapping from inputs to outputs.  You don't get to specify an input distribution; a function is whatever it is.  Think of a function as a truth table -- there's no way to specify an input distribution, as that's not part of the definition of a function.

I suggest finding a textbook on theoretical cryptography -- e.g., Introduction to Modern Cryptography by Jonathan Katz and Yehuda Lindell -- and follow the definitions there.  I wouldn't recommend relying upon Wikipedia for definitions or to learn from.


Largest set of vertices that is larger than its set of neighbors

Consider the following problem.

  Find $X''$ such that $|X''| = k$ and $|f(X'')| = m$

If it was P then so would set cover: fix $m = |Y|$ and iterate over all $k \in \{1, \dots, |X|\}$ to find a minimum.

Let's call this problem $\text{exact}(G, k, m)$ and let's call your problem $\text{largest}(G)$.

Let $G(X, Y, E)$ be any bipartite graph. Let $G^1$ be a graph with one additional vertex in $X$, not connected to anything. Let ${_1}G$ be a graph where for every vertex of $X$, a new vertex is added to $Y$ and the two are connected. Let ${^1}G$ be a graph where for every vertex of $Y$, a new vertex is added to $X$ and the two are connected. Let ${_k^l}G^i = ({_k}({^l}G))^i$ be these transformations applied repeatedly. Note the order.

$G^i$ will be used to artificially raise $|X^+|$ and therefore $|f(X^+)|$. ${_k}G$ will be used to weight down vertices $v$, so we can control whether $v \in X^+$ even if $f(v) \subset f(X^+)$ in $G$. ${^l}G$ will be used to prioritize larger $|f(X^+)|$.

Say $X^+ = \text{largest}(G^i)$. This implies that $\text{exact}(G, |X^+|-i, |f(X^+)|)$, because you know that the $i$ new vertices in $X$ will be used and thus $|X^+|$ old vertices have a neighborhood of $|f(X^+)|$ old vertices. Similarly $X^+ = \text{largest}({_k}G)$ implies $\text{exact}(G, |X^+|, |f(X^+)|-k|X^+|)$.

To find $\text{exact}(G, k, m)$, let $X^+_i = \text{largest}({_M^i}G^{(mi+k)M+(m-k)})$ for sufficiently large $M$ (say, $M = |X|+|Y|$).

If $|X^+_0| < kM + (m-k) + k$ then $\text{exact}(G, k, m)$ is false.
If $|f(X^+_i)| = (mi+k)M+m$ then $\text{exact}(G, k, m)$ is true. Note that if $\text{exact}(G, k+ix, m-x)$, then $|f(X^+_i)|$ could also have the value $(mi+k)M+m-x$.
Raise $i$ until $\forall x>0, \neg \text{exact}(G, k+ix, m-x)$ (you can jump directly to $i=|X|$). Then $|f(X^+_i)| = (mi+k)M+m$ if and only if $\text{exact}(G, k, m)$.


Complexity of the Kitten Adoption problem

This is the min-cost max-flow problem.

Consider a graph $G=(A\cup B\cup \{s,t\},E)$, where $A$ is the set of kittens, $B$ is the set of people.

Let $C:E\to \mathbb{R}^+$ be the capacity of the edges, and $c:E\to \mathbb{R^+}$ be the cost of an edge. We make sure that

There is an edge between $a_i,b_j$, where $a_i\in A$ and $b_j\in B$, and $C(a_i,b_j)=1$, $c(a_i,b_j)=c_{i,j}$.
There is an edge between $s$ and $a_i\in A$, and $C(s,a_i)=1$, $c(s,a_i)=0$.
There is an edge between $b_j\in B$ and $t$, and $C(b_j,t)=u_j$, $c(b_j,t)=0$.

If the max flow is $M$, then we know there exist a solution. You can construct a min-cost solution from the min-cost max-flow.


Round Robin Scheduling: No process in Ready Queue

your first process will take time only upto 5 seconds as its service time is only upto 5 seconds and then you have to keep blank space between 5-7 and then your next process arriving at 7 would be processed,i think.


About the behaviour of multi-layer perceptrons

The answer is no. What you want to do is to predict randomness. The perceptron network takes randomboolean(true/false) and it outputs outputboolean(not random!!). The random generation of targetboolean is independent from the generation of outputboolean.

Perceptrons generally learn functions. If you have $f(A)=B$ and $f(A)=C$ and $B\neq C$, then $f$ is not a function.

EDIT: To predict temporal behavior you should add some time dependent variable in the input of the network.


Not understanding this way of proving undecidability of the termination problem

This is a very succinct way of presenting the contradiction argument, and I strongly recommend you read a textbook on the topic, or some detailed explanations. There are tons of resources that explain this remarkable and beautiful argument, from many viewpoints.
Still, to answer your question: denote by $Q$ the program you describe. Then $Q$ is a valid program, that takes as input another program $P$, and works as above.
Now ask yourself - what would $Q$ do if you gave it its own encoding $Q$? Would it terminate or not?

If $Q$ terminates when given $Q$, then the "while" condition would stay true, meaning $Q$ would not terminate when given $Q$, but this is a contradiction.
If $Q$ does not terminate when given $Q$, then the while condition is false, so $Q$ does terminate when given $Q$, which is again a contradiction.

Therefore, a procedure such as "terminate" cannot exist.
Again, I cannot stress this enough -- read this proof elsewhere, watch youtubes of it, read textbooks. It's one of the most fundamental and exciting results in computer science!


Yes, an algorithm should always stop after a finite number of steps, otherwise we would call it a procedure or process or computation specification.  A procedure that doesn't halt for certain inputs can be considered partial algorithms.  Algorithms are more useful, since they terminate for any input.

An algorithm can be viewed as a function $f: \mathbb{N} \to \mathbb{N}$.  if it is defined for all input values, we say that $f$ is "total" ; for an algorithm, it means that it halts for any input.  On the other hand, if a function $f$ is "undefined" for an input, say $4$, we say that $f$ is a partial function, and in computation theory, we write $f(4)\uparrow$ meaning it "diverges", or simply "doesn't halt".

An example for a partial function can be the inverse of the integer square function, i.e. $sq(n) = n^2$.  The inverse, $sq^{-1}$ is defined only on perfect squares, that is, $$sq^{-1}(n) = \cases{\sqrt{x} \text{ if $x$ is a perfect square} \\ \text{undefined otherwise.}}$$


When you negate $\Omega$ you get $\stackrel{\infty}{O}$, the analog of $\stackrel{\infty}{\Omega}$. I suggest writing the definition of $\Omega$ as a first-order formula and then negating it.

To see the difference between $\Omega$ and $\stackrel\infty\Omega$, consider the functions $f(n) = n$ and $$g(n) = \begin{cases} 1 & \text{$n$ even,} \\ n^2 & \text{$n$ odd.} \end{cases}$$
You can check that $f(n) \neq O(g(n))$ and $f(n) \neq \Omega(g(n))$, whereas $f(n) = \stackrel\infty O(g(n))$ and $f(n) = \stackrel\infty\Omega(g(n))$.


Why more and more handcraft lex do not use regular expression any more?

While I cannot give you a definitive answer, but I think there are a couple of reasons for handcrafting lexers and parsers:

Good error reporting and recovery: most of tools such as Lex that provide a declarative way of defining regular expressions are hard to customize for error reporting or recovery. When you hand-craft your lexer or parser, you have more control when you encounter an error.
Performance: while Lex is using Finite State Automata in their lexers, and they are efficient (assuming the automata can be loaded in memory) it may pay off to handcraft your lexer to have a tight control on both runtime and memory usage. Most regular expression engines in programming languages use backtracking and may have exponential worst case runtime.
Infrequent changes: the token definitions (and even syntax) of programming languages doesn't change that often. So I think in the prototyping phase it makes sense to use a tool to automate the process, but when the syntax became stable, it will pay off to handcraft the lexer and parser, both in terms of error reporting and performance.


How to find a condition which leads to deadlock in non-reentrant locks

A single thread can get itself deadlocked by locking the same lock twice without an unlock in between. Which is obviously a stupid thing to do.

I don’t see your problem with the other cases: if one thread deadlocks itself, you have a deadlock, no matter how many other threads and locks you have.


Your dancers are vertices of a graph, and there is an edge between two dancers if they are compatible.  A set of dancers is a component if there's what you might call a "chain of compatibility" between every pair of them: that is, every pair of dancers is either compatible or you can come up with a sequence such as "Alice is compatible with Bob, Bob is compatible with Charlotte and Charlotte is compatible with Daniel" to get between them.
A group of dancers who are all compatible with each other are a clique.

What you're looking for is a component that is also a clique. These are easy to find because you can use a greedy strategy.  Suppose we want to know if a particular dancer (say, Alice) is in one of these groups.  We grow a set of dancers as follows.  Initially, the set is just Alice.  Then, we keep adding dancers to the set if they're compatible with anybody inside the set. When we can't add anyone, we've found the component. So now, we just need to check that the component is a clique: that is, everybody within the component is compatible with everybody else.

You can do this more efficiently by checking for being a clique as you add new dancers. Again, start with just Alice.  Then define a set of newcomers to be all people who are compatible with somebody in the set we've built so far.  If any of those people are incompatible with each other or with somebody who's already in the set, Alice isn't part of a group; otherwise, add all the newcomers to the set and select the next set of newcomers.


Simple Uniform Hashing Assumption and worst-case complexity for hash tables

I think the answer is no, SUHA does not imply anything regarding worst-case time complexity.

The bottom line is that

the hashing is (even though uniform) still viewed as random, and
the keys are unknown.

Regardless of how small the probability is for all keys to hash to the same bucket, it's still a theoretical possibility, thus the theoretical worst-case is still O(n).

When discussing hash tables and complexity, I think this is mentioned briefly, regarded as irrelevant in practice and then the discussion moves on to expected run time complexity, and we're in O(1) land.

With the assumption mentioned in the question...

  The difference between the largest and smallest bucket is bounded by a constant factor.

...(which is strictly stronger than SUHA) it can indeed be shown that the worst-case run time complexity is O(1). This assumption implies that even the largest bucket is within a constant factor of the load factor limit. This in turn means all linked lists are bounded by a constant and we get O(1) as worst case.

This assumption however is somewhat unreasonable. While it's quite probable that it holds true for any descent hash function and non-pathological set of keys, how would one guarantee such property? One would have to push this assumption further down and make constraints on what keys are allowed to be stored in the hash table and so on. This is what makes it unreasonable in a sense.


If DFA has two states, which of the conditions hold?

You seem to be misunderstanding the statement of the exercise. It wants you to show that if $L$ is a language accepted by a DFA containing two states, then either $L$ is empty, or $L$ contains the empty word, or $L$ contains a word of length 1. Which of the cases holds depends on $L$. More explicitly:

If no state of the DFA is accepting, then $L = \emptyset$.
If the initial state of the DFA is accepting, then $\epsilon \in L$.
If the other state of the DFA is accepting, then either the state is reachable, in which case $\sigma \in L$ for some $\sigma \in \Sigma$, or else it is unreachable, in which case $L = \emptyset$.

More generally, the proof of the pumping lemma shows that if $L$ is accepted by a DFA containing $n$ states, then either $L = \emptyset$ or $L$ contains some word whose length is less than $n$. This is sharp, in the following sense: for each $n \geq 1$ and $m \in \{0,\ldots,n-1\}$, there is a language accepted by a DFA of length $n$ whose shortest word has length exactly $m$ (exercise).


efficiently minimizing quasiconvex function

Avriel and Wilde, in their article Optimality proof for the symmetric Fibonacci search technique, showed that Fibonacci search is optimal in the following sense: if you want to bracket the minimum in an interval of length $\delta$ using at most $k$ evaluations, then Fibonacci search maximizes the length of your initial interval.


Show that every infinite language has a non-regular subset

The powerset of the language contains all the sublanguages. This will be uncountably infinite, but there are only countably many regular languages (for a particular, finite alphabet)


What is exponent of denormalized real in IEEE 754 floating point format?

Both an exponent field of 00000000 and 00000001 encode an exponent of -126, but with 00000000 there is no implicit leading 1 and with 00000001 there is. Consider going from 0x00800000 (smallest normal) to 0x007fffff (biggest denormal). For 0x00800000 the significand (including leading 1) is still 0x00800000 (a nice coincidence), for 0x007fffff is significand is just 0x007fffff. Since the exponent remains the same, these are just as adjacent as they seem (the distance between them is the lowest non-zero denormal).

If the exponent for denormals was -127, the denormals would only fill up to halfway between zero and the lowest normal, leaving a large gap between the highest denormal and the lowest normal.

Normally the number line including denormals looks like this (if you had 2 bits of significand, so 4 numbers per binade): (source)

You can see the denormals and the numbers in the first normalized binade are equally spaced, meaning they have the same exponent. What happens if the denormals had the exponent which their encoding seems to imply?

A gap appears.


How to measure the complexity of the discrete logarithm problem?

It doesn't matter whether you choose the size of the group $|G|$ or the size of the integer representing it $n$ as a parameter, since $n \approx \log |G|$. There are two reasons that usually the complexity is described in terms of $n$ rather than $|G|$:

$n$ is the length of the input (more accurately, the input has length $\Theta(n)$), and we usually measure the complexity of algorithms as a function of the input length.
Usually $n$ is a small number such as $1024$, whereas $|G|$ is a huge number such as (roughly) $2^{1024}$.


Lower Bound for Comparison-based sorting algorithms

The lower bound of sorting algorithm comparison based is $O(nlogn)$.
The best case lower bound is $O(n)$ which comes from fact that you need to check if numbers are sorted, so you traverse all of them to find out if they are ordered.

The lower bound is applied to all instances of problem, not just lucky particular case.


Finding a mapping reduction from $A_{TM}$ to $\overline{CF_{TM}}$

Let $L$ be recursively enumerable but not context-free (and, therefore, not empty). We only need the existence of such an $L$; the actual choice is immaterial. In addition, recall the empty set $\varnothing$ is context-free. The idea is to map to a TM which accepts $L$ in case $M$ accepts $w$ (i.e., $\langle M,w \rangle \in A_{TM}$) and to $\varnothing$ otherwise.

Given an instance $\langle M,w \rangle$ of $A_{TM}$, map it to the description $\langle S \rangle$, where $S$ is the TM which does the following:

  On input $w'$:

  Run $M$ on $w$. If $M$ rejects, reject.
  If $M$ accepts $w$, then accept if and only if $w' \in L$.

Note that, if $M$ does not halt on $w$, then $S$ does not halt either. Also, $w' \in L$ can be checked because $L$ is recursively enumerable (and $S$ need not halt in case that is false). We conclude that $L(S) = L$ if $\langle M, w \rangle \in A_{TM}$ and $L(S) = \varnothing$ (which is context-free) otherwise.

An observation. The trick behind 98% of these problems lies in understanding what you need to do (i.e., what I wrote in the first paragraph). The actual description for the instance you are reducing to (in this case, $\langle S \rangle$) might look tricky or esoteric at first sight, but it actually simply follows as a consequence once you have the right ideas in mind.


Is the language of all non-palindromes context-free?

If $w$ is not a palindrome then there must be some $i$ such that the $i$th letter from the left is different from the $i$th letter form the right; and vice versa (prove!). This means that
$$
L = \{ \Sigma^{i-1} a \Sigma^* b \Sigma^{i-1} : i \geq 1 \} \cup \{ \Sigma^{i-1} b \Sigma^* a \Sigma^{i-1} : i \geq 1 \},
$$
which is easily seen to be context-free.

Your grammar almost manages to capture this characterization. Unfortunately, it doesn't generate the words $ab$ and $ba$. A simpler grammar is
$$
\begin{align*}
&S \to aSa|bSb|aTb|bTa \\
&T \to aT|bT|\epsilon
\end{align*}
$$


Draw DFA that accepts concatenated binary string with condition

Hint: $3\operatorname{value}(u)=\operatorname{value}(u)+\operatorname{value}(0u)$. Then you're just doing a simple addition with carry.

By the way, there's a much stronger result: For any first order formula $\varphi(x_1,\dots,x_n)$ of the Presburger arithmetic, there is an automaton $A$ over $\{0,1\}^n$ so that $A$ accepts $u$ iff $\varphi(\operatorname{value}_1(u),\dots,\operatorname{value}_n(u))$ is true (where $\operatorname{value}_i(u)$ is the same value that you defined except that since each "letter" of $\{0,1\}^n$ contains several digits, it only looks at the $i^{th}$).

Your question is a special case of this where the formula is $\varphi(a,b)= ``a=3b"$. (Kind of: if $L$ is what you get for this formula, then you'd need to take $f(L)$ where $f$ is the morphism defined by $(b_1,b_2)\mapsto b_1b_2$).


Can PDA model Turing Complete objects if the objects' state are finite?

where the domains of the object variables are restricted to finite sets. Hence, such objects can be modeled with a pushdown-automaton (PDA).

You are correct that if you understand it as using a pushdown-automaton to model the full behavior of the object, since as you indicated, you can put a Turing complete Turing machine inside any object.

However, I would believe that the authors intend to use a pushdown-automaton to mode an object in the domain with its possible states as defined by the values of its fields and its execution stack, since the whole paper is focusing on the ECF(Effectively Callback Free) property for objects. The actual moments when the object is still in the middle of changing from one state to another state are ignored/irrelevant/transparent/skipped. More specifically, the following shows the purpose of the object.

  Such a PDA for an object o is able to simulate any modular well-formed execution $\kappa \in \pi$ where the active object of all states in $\pi$ is o


Minimum total waiting time for arrivals/durations

Yes, this is NP-hard. Since neither the $a_i$ nor the $d_i$ depend on the solution, the problem is equivalent to the problem of minimizing the sum of the completion times of the requests, which is known in the scheduling literature as "$1|r_i|\sum C_i$" and is NP-hard. Reference:

J.K. Lenstra, A.H.G. Rinnooy Kan, and P. Brucker.
Complexity of machine scheduling problems.
Ann. of Discrete Math., 1:343-362, 1977.

Also, I disagree with the statement that "the only difference to Interval Scheduling is that here all clients have to be serviced". There is one more important difference: in Interval Scheduling, the algorithm can just accept or reject the clients, while in this problem, even after the algorithm accepts a client, it has to choose when to start it.


Relationship between height and depth of a binary tree

You're not missing anything: it's a typo, which I've fixed. The page gives two separate definitions of "full binary tree" (a recursive one and the one you quote) and both of them include the following trees, which have even fewer nodes than yours ($2n-1$, to be precise):

  o
 / \
o   o
   / \
  o   .
       .
        .
         \
          o
         / \
        o   o


Is it possible to create a "Time Capsule" using encryption?

The problem is known as timed-release cryptography. For some references/introduction look at:

"Time-lock puzzles and timed-release Crypto" by R.R. Rivest, A. Shamir, and D. A. Wagner (1996)

Our motivation is the notion of "timed-release crypto", where the goal is to encrypt a message so it cannot be decrypted by anyone, not even the sender, until a pre-determined amount of time has passed. The goal is to "send information into the future" ...

or "Provably Secure Timed-Release Public Key Encryption" J.H. Cheon et al. (2008)


You must need an extra stack to sort an stack. With the help of two stacks this problem can be solved.

So, suppose you have n elements in the stack. and you have an other stack, which is empty.

Now, in bubble sort, after each iteration highest element reaches to its final position. So, to implement this algorithm, we can make use of that second stack.

For the first Iteration:
There are n elements in the stack, pop each element one by one in the empty(second stack) stack and keep track of highest element at each stage. After the first stack is completely empty, you will have the highest element of the stack. Now push that highest element in the first stack and then pop all the elements from the second stack and push them in first stack. So, after this iteration, highest element is set to its position. and we now have n-1 unsorted elements. Be alert to not to push highest element again in the first stack.

  for example, elements are 5,10,7,2,15. So, after first iteration stack
  content is 15,5,10,7,2.

For the next Iterations:
So, after 1st iteration highest element is set, and we are remaining with n-1 unsorted elements in first stack, while the second stack is empty. So, during this iteration, instead of n elements, pop only n-1 elements to the second stack and keep track of maximum. After n-1 elements are pushed to second stack we have highest element among those n-1 elements, which second highest element of original stack. Push that element in the first stack, above the highest element already there. And then push all the elements back in the first stack from second stack.

  So, after first iteration stack content is 15,10,5,7,2.

Then reduce the size to n-2 and follow same method.

Complexity of this method is same as bubble sort, which is $O(n^2)$.


Count nodes within K-distance from all nodes in a set

Add a new node(let's say s) and connect it to all the marked nodes in the set. Then, find all the nodes which are at a distance less than k+1 from s and subtract number of marked nodes from it. T(n)=O(V+E)

In the second approach, we can actually find the two nodes (let's say uand v) with maximum distance between them in O(V+E). How do we find those vertices? Pick a vertex w and place it in a queue. While the queue is non-empty add the neighbors of the next vertex in the queue to the end of the queue. When the queue is empty, take note of the most recently removed vertex. This will be u. Perform the procedure again and you will have v. Check this link for proof.
https://stackoverflow.com/questions/9951363/finding-the-root-that-minimize-tree-depth


my new sorting algorithm, what should my upper bound be?

It looks like the algorithm you are describing is called counting sort.
This algorithm works in $O(n+k)$ where $n$ is the number of items in the input, and $k$ would be their range: $k=max - min$.
This algorithm is indeed better in computational time complexity than mergesort when you restrict $k$ to be small enough. For your examples, you "fixed" a value for $n$ and $k$, which makes no sense to compute the big-O notation on. The big-O describes the algorithm in its full behaviour, and is an upper bound for any "fixed" value you would give.
As a side note, this algorithm is not a comparison-based sorting (sorting only by comparing numbers), and can only sort natural numbers. Actual comparison-based sorting algorithms (like mergesort) must take at least $\Omega(n\log(n))$, but are capable of sorting any list, and not just natural numbers.


Why NAT is a disadvantage when TCP source port field is 16 bits?

The practical limit to the number of hosts that can use a single NAT'd address is much less than 61,440.  This is because even a modest Internet-capable computer will use many simultaneous TCP connections to hosts beyond the firewall.  Each of these connections, while it is open or being negotiated open or closed, counts against that 61,440 figure.  If each local host needs to reliably be able to initiate 200 external TCP connections at once, then that 61,440 value is reduced to only 307 hosts.  This won't be a problem for a typical home network (yet), but a small business could easily reach this limit.
If the TCP source port size were larger, then that would offer a correspondingly larger number of address:port pairs for address translation to use, permitting many more hosts and connections from behind the firewall.


Why is the running cost of SQUARE-MATRIX-MULTIPLY-RECURSIVE in CLRS $\Theta(n^3)$ instead of $\Theta(n^2)$?

What you are asking is indeed answered in section 4.5 of CLRS using a methodology described later in the book. I will post here an alternative answer you should be able to understand with your current knowledge.

Think of the recursive relationship
 $$T(n) = 8T(\dfrac{n}{2}) + cn^2.$$

Let us first see what happens if we substitute $T(\dfrac{n}{2})$

$$T(n) = 8 (8T(\dfrac{n}{4}) + c (\dfrac{n}{2})^2) + cn^2 = 8^2 T(\dfrac{n}{4}) + 8c(\dfrac{n}{2})^2 + cn^2.$$

By substituting $T(\dfrac{n}{4})$ we get:

$$T(n) = 8^2 (8T(\dfrac{n}{8}) + c (\dfrac{n}{4})^2) + 8c(\dfrac{n}{2})^2 + cn^2 = 8^3 T(\dfrac{n}{8}) + 4cn^2 + 2cn^2 + cn^2.$$

It becomes obvious that in the general case after $k$ iterations we have:

$$T(n) = 8^k T(\dfrac{n}{2^k}) + cn^2(2^{k-1} + 2^{k-2} + \dots + 2 + 1).$$

Let $n = 2^k$.

Notice that $k = \log_2n \Rightarrow8^k = 8^{\log_2n} = 2^{3\log_2n} = 2^{\log_2n^3} = n^3$. By substituting $k = \log_2n$ in the previous relationship we get:

$$T(n) = n^3T(1) + cn^2 (\dfrac{1}{2} + \dfrac{1}{4} + \dots + \dfrac{1}{n})n.$$

$T(n) = n^3 T(1) + cn^3$, therefore you have $\Theta (n^3)$.


Meaning of $\mu t$ terms in dependent type theory

The term μ t is the application of a closure μ to a term t. Similar to how t t' is the application of a term t to t'.


Non Deterministic PDA accepted language not clear

The PDA you're linking to is non-deterministic; indeed, the state you are confused about has two out-edges labeled $a$. For the PDA to accept its string, it's enough for there to be one accepting computation – what you refer to inaccurately as "human interference" [intervention?]. Regarding the acceptance condition of the PDA, figure out what acceptance condition makes this PDA accept the advertised language, and this is the accepting condition that you should have in mind.


Firstly:

  König's Theorem (1936): A graph is 2-colorable iff it has no circuits of odd length.

  ― www-math.ucdenver.edu

Also:

  A graph is bipartite if and only if it does not contain an odd cycle.
  A graph is bipartite if and only if it is 2-colorable, (i.e. its chromatic number is less than or equal to 2).

  ― wikipedia

So we see we are looking for a 2-colorable graph, or a bipartite graph. These are all the same thing.

Edit:

  A digraph has an odd-length directed cycle if and only if one (or more) of its strong components is nonbipartite (when treated as an undirected graph).

  ― algs4.cs.princeton.edu

Since your graph is strongly connected, we can treat it as an undirected graph and test for bipartiteness using the regular testing algorithms.

The wikipedia article gives an example algorithm to test bipartiteness using Breadth First Search. A presentation explaining the algorithm is available from The University of Maryland website.


Can I prove that $\sqrt n\log{\sqrt n}=\Theta(n)$?

$$\lim_{n\to\infty} \frac{\sqrt n \log\sqrt n}{n} = 0$$

Since this $\Theta(\sqrt n \log \sqrt n) = o(n) < \Theta(n)$.

Two functions $f(x), g(x)$ are asymptotically equal iff

$$\lim_{x\to\infty} \frac{f(x)}{g(x)} = c,\ c \in \mathbb{R},\ c > 0$$


My algorithm is different from CLRS' -- is it wrong?

You are right, there is a assuption that the set is available as an unsorted array, but I think that most set representations will allow you to obtain all elements in linear time. I also agree with you that your solution is straightforward, and uses no funny tricks.

I guess their solution is to impress you that only sorting and merging is needed, no such complicated things as binary search. (insert smiley here.) Perhaps binary search was not yet introduced at that point?

To illustrate the point Raphael makes — there are infinitely many implementations — here is mine. I believe it is correct, and uses only one sort, and a linear pass over the array. So: sort the array (from small to large). To check whether $y,z\in S$ exist such that $y+z=x$ move over the array from both sides. If the sum of the two elements of the array is larger than $x$ move the larger element one down, if it is less than $x$ move the smaller element one up. (How does this compare to your proposal?)

Nevertheless I would not consider their solution as incorrect. I like to think that it is good to have several solutions available. In some circumstances one implementation may outperform another. E.g., if the set was to be given as a sorted linked list, your solution would be hard to implement. (And mine only works if the list is doubly linked.)


Help in understanding the implementation/application of scope trees

My opinion on this is that the scope tree is a derived entity from the syntax tree, therefore as you perform your semantic analysis by walking the syntax tree you create a temporary scope tree on the fly and by doing that, the current position is automatically tracked.

The point is that both the scope tree and the syntax tree have to be married together somehow. As this would allow you to track the position of the symbols in unison. So as you traverse a method called a() on the syntax tree you statically know where to start in the symbol tree.

Note: you do not require a scope tree, you could use a stack but the advantage of the tree is that the storage of the scope is persistent. Therefore for simple validations a stack could be used to determine whether or not a variable is out of scope but for mode advanced analysis problems a scope-tree which behaves like a multidimensional stack would be required.

i.e.:

int a()
{
    int b;
    int c;
    {
       int b;
       int c;
    }
}

int b()
{
     int a;
}

So whenever you go into a function such as a you can create a function node and every time you see a declaration you can create a symbol and add it to the function's scope (push) and when you see a declaration you can resolve it by traversing up the tree.

Language implementation patterns by Terence Parr has a complete example of this and a very useful book.


checking whether a language is turing recognizable

Let $U$ be a universal Turing machine.  Then running $U$ on the input $\langle M \rangle, x$ will produce the same output as running $M$ on the input $x$ -- that's what it means for $U$ to be a universal Turing machine.  Others have shown how to build a universal Turing machine.

Then, you can build a Turing machine to do what you want by using $U$: namely, on input $\langle M \rangle$, your Turing machine should run $U(\langle M \rangle, \langle M \rangle)$.  Or, to put it another way, your Turing machine should make a second copy of the input it receives on the input tape, then run $U$.  If you know how to build a Turing machine to copy a bit-string, and if you have a universal Turing machine $U$, you'll have a solution for your problem.

This might not sound very enlightening, but it's the easiest way to describe how you can do it.  Programming Turing machines is incredibly tedious and usually not enlightening: it's like programming in a particularly nasty and human-unfriendly programming languages.  Therefore, it's best avoided wherever possible.  In this case, my solution lets you take advantage of the fact that someone else has already figured out how to build a universal Turing machine.

You might be wonder how to do that.  Well, the basic idea is that you need to implement an interpreter for Turing machines.  Pick your favorite programming language, like Python; could you write a Python program to interpret a Turing machine, one step at a time?  I bet you could -- it's a simple matter of programming.  Now you just need to do that, but this time instead of writing a Python program, you need to write a Turing machine -- a nastier and messier task that's far more tedious, but not conceptually different.


Can we construct a binary tree with width and height Θ(n)?

Statements about $\Theta$-classes are statements about the behaviour of an algorithm/data structure, as (in this case) $n$ gets large. Thus, a single example can never prove such a statement. You'd have to provide a set that contains examples that become arbitrarily large and behave as desired. (The set, however, doesn't have to contain an example for every value of $n$.)

So you should try to construct such a set of examples. (And if you fail constantly, try to find out why. This might lead to a proof that no such set exists, i.e. the claim is false.)


Are loop counters spatially or temporally local?

A set of variables has temporal locality if they are accessed within a relatively short period of time. sum, k and n are all accessed at every iteration of the inner loop; assuming that n is relatively large, i and j are not accessed frequently. So sum, k and n are temporally local, j could be considered temporally local with them but i probably isn't.

Variables have spatial locality if they are stored at addresses that are close together – e.g., close enough to be in the same cache line or, at least, the same page in memory. As such, spatial locality is a property of compiled code, not source code, so it's impossible to say what variables in the code are spatially local: a stupid compiler or memory manager could scatter them to the four corners of the address space. But one would hope that temporally local variables that are accessed repeatedly would be spatially local.


Is $\epsilon$ always contained in $\Sigma^*$?

Normally, $\epsilon$ stands for the empty string: the string with no characters, which would be "" is most programming languages. It's too confusing to have $\epsilon$ be a symbol in the alphabet, so I'm going to rename it and write your alphabet as $\Sigma=\{e,0,1\}$. (The alternative would be to use some other symbol to denote the empty string.)

Now, by definition, $\Sigma^*$ is the set of all finite strings that can be written using the characters of $\Sigma$. This always includes the empty string $\epsilon$ and, as long as $\Sigma\neq\emptyset$, it also contains strings of all finite lengths. So the claim in the question that $\Sigma^*=\{e, 0, 1, 01, 10\}$ is incorrect: $\Sigma^*$ is an infinite set.

The regular expression for $\Sigma^*$ is $(e+0+1)^*$; the automaton consists of a single state, which is accepting and has transitions to itself for each symbol in $\Sigma$.


The theorems you quote are unfortunately wrong. As an example, $2 + \sin n = \Theta(1)$ although the limit $\lim_{n\to\infty} \frac{2+\sin n}{1}$ doesn't exist.

Here are some theorems which do hold.

Theorem 1. Let $f,g$ be two functions such that $f(n),g(n)$ are eventually positive. If the limit $c := \lim_{n\to\infty} f(n)/g(n)$ exists then

$f(n) = O(g(n))$ iff $0 \leq c < \infty$.
$f(n) = \Omega(g(n))$ iff $0 < c \leq \infty$.
$f(n) = \Theta(g(n))$ iff $0 < c < \infty$.
$f(n) = o(g(n))$ iff $c = 0$.
$f(n) = \omega(g(n))$ iff $c = \infty$.

Theorem 2. If $f,g$ are two polynomials which are eventually positive, then the limit $\lim_{n\to\infty} f(n)/g(n)$ exists.

Theorem 3. Let $f,g$ be two functions such that $f(n),g(n)$ are eventually positive. Then

$f(n) = O(g(n))$ iff $\lim\sup_{n\to\infty} \frac{f(n)}{g(n)} < \infty$.
$f(n) = \Omega(g(n))$ iff $\lim\inf_{n\to\infty} \frac{f(n)}{g(n)} > 0$.
$f(n) = o(g(n))$ iff $\lim_{n\to\infty} \frac{f(n)}{g(n)} = 0$.
$f(n) = \omega(g(n))$ iff $\lim_{n\to\infty} \frac{f(n)}{g(n)} = \infty$.


Is the inverse of MST cycle property always true? Why?

If you want to test whether a specific edge belongs to some MST, you can use the following property.

Claim. An edge $e$ belongs some MST if and only if for every $\epsilon > 0$, if we reduce the weight of $e$ by $\epsilon$ then it belongs to all MSTs.

Proof. We first show that if $e$ belongs to some MST then for every $\epsilon > 0$, if we reduce the weight of $e$ by $\epsilon$ then it belongs to all MSTs.

Suppose that MSTs in the original graph have weight $w$. When we decrease the weight of $e$ by $\epsilon$, only trees containing $e$ have decreased weight. Since $e$ belongs to some MST, the new graph has MSTs of weight $w - \epsilon$, and all of them contain $e$.

We complete the proof by showing that if $e$ doesn't belong to any MST then for small enough $\epsilon > 0$, if we decrease the weight of $e$ by $\epsilon$ then $e$ still belongs to no MST. Indeed, suppose that MSTs in the original graph have weight $w$, and the lightest spanning tree containing $e$ has weight $w+\delta$ for $\delta > 0$. If we decrease the weight of $e$ by less than $\delta$, it still belongs to no MST. $\qquad \square$

I'll let you figure out how to use the claim to test whether $e$ belongs to some MST; it suffices to find one MST in one graph. The same approach seems wasteful if you want to test all edges. I'll leave you to ponder whether any optimization is possible in that case.


To prove Turing-completeness, is it enough to prove capability of producing arbitrary output?

Turing-completeness means that the machine model in question can compute everything that is computable. That means that for every computable function $f$, there is a corresponding program for your model which behaves "like" $f$, where I put the quotes since the input and output may look differently.

Showing that the machine can generate arbitrary output is hardly enough - consider the machine model which executes only one program, copying its input to its output.


Why is $\log n+\log \frac{n}{2}+\log \frac{n}{4}+\log \frac{n}{8}+\cdots+\log \frac{n}{n}=\Theta (\log^2 n)$?

Assuming $n$ is a power of $2$, you have:
$$
\sum_{i=0}^{\log n} \log \frac{n}{2^i} =
\sum_{i=0}^{\log n} \left( \log n - i \right) =
\sum_{i=0}^{\log n} i =
\frac{(\log n)(\log n+1)}{2} = \Theta(\log^2 n).
$$


Why does Randomized Quicksort have O(n log n) worst-case runtime cost

Both of your sources refer to the "worst-case expected running time" of $O(n \log n).$ I'm guessing this refers to the expected time requirement, which differs from the absolute worst case.

Quicksort usually has an absolute worst-case time requirement of $O(n^2)$. The worst case occurs when, at every step, the partition procedure splits an $n$-length array into arrays of size $1$ and $n-1$. This "unlucky" selection of pivot elements requires $O(n)$ recursive calls, leading to a $O(n^2)$ worst-case.

Choosing the pivot randomly or randomly shuffling the array prior to sorting has the effect of rendering the worst-case very unlikely, particularly for large arrays. See Wikipedia for a proof that the expected time requirement is $O(n\log n)$. According to another source, "the probability that quicksort will use a quadratic number of compares when sorting a large array on your computer is much less than the probability that your computer will be struck by lightning."

Edit:

Per Bangye's comment, you can eliminate the worst-case pivot selection sequence by always selecting the median element as the pivot. Since finding the median takes $O(n)$ time, this gives $\Theta(n \log n)$ worst-case performance. However, since randomized quicksort is very unlikely to stumble upon the worst case, the deterministic median-finding variant of quicksort is rarely used.


A formula $\varphi$ in DNF is valid if and only if $\neg\varphi$ in CNF is unsatisfiable. Since CNF-SAT is NP-complete, it follows that DNF-VAL is coNP-complete. You are right that you need to show an NP-complete language can be reduced in polynomial time to the complement of DNF-VAL. Since this complement is just CNF-SAT, try reducing SAT to CNF-SAT.

There are a lot of proofs of this reduction around; this one[1] looks good if you just want to see an answer.

[1] Howell, Rod. "SAT-CNF Is NP-complete." (2000).


is there any hardware device to convert source code into machine language?

No, and yes.

The answer is "no", in the sense that the vast majority of computers have no hardware that does what you typically expect a compiler to do; compilers are written in software. Obviously this ultimately runs on hardware, but we're talking general-purpose hardware.

However, the answer is "yes", in the sense that the machine code that is actually executed often isn't the same as the machine code that a programmer sees (i.e. the instruction set architecture, or ISA for short). Almost all modern CPUs do some degree of dynamic translation of the "machine code" into a form that is more suited for out-of-order execution.

Intel/AMD-type CPUs, for example, translate machine code into RISC micro-operations (called "uops"). It is these instructions which are scheduled and executed.

ARM has something similar. Its ISA is much closer to the format that's executed, but ARM also features Thumb instructions, which are dynamically translated into "core" instructions. The short-lived Jazelle DBX/ThumbEE did a similar thing with direct execution of JVM bytecode.

Almost all modern high-performance CPUs do this to varying degrees. Indeed, there is a fuzzy line between "dynamic translation" and "instruction decoding".


The page you reference for Coq defines inLeft and inRight as constructors of the inductive type sumor. The names themselves come from "left/right injection", as in the left/right injection into a sum type. Other names commonly used are inl/inr, Left/Right, $\iota_0$/$\iota_1$, and variations on these (e.g. that Coq file also defines left/right in the definition of sumbool). It also defines inl/inr as the constructors of the general sum type. sum, sumor, and sumbool are minor, technical variations of each other.

Which terms are used depends on the author, but they are most commonly used for injections into a sum type, particularly in a type theory/category theory context. Of course, an author is always free to use them for something else if they provide a definition.