It is a common misconception that O(g(N)) notation represents a function. It actually represents a set of functions whose asymptotic complexity is bounded by the function g(N) as N approaches infinity. In your example, g(N) = 3^N.

So to ask is 2^n = O(3^n) is mixing apples and oranges, or in this case you are comparing a function with a set of functions. We often write it this way, but it is understood that we are talking about membership in a set of functions, not equality.

The more correct way to state this is:

Is function 2^n contained in the set of functions represented by O(3^n)?

With the question phrased this way, the exact values of n do not enter into it because now you are asking if the function 2^n is a member of the set O(3^n).

The short answer is: yes it is.

But to understand why, you need to understand the formal definition of big-O notation which is:

   f(x) is contained in O(g(x))

if and only if for all sufficiently large values of x, the absolute value of f(x) is at most a positive constant multiple of g(x). That is, f(x) = O(g(x)) if and only if there exists a positive real number M and a real number x0 such that

|f(x)| <= Mg(x) for all x >= x0

So for 2^n and O(3^n), we can set M to 1 and x0 to 1, and we get:

|2^n| <= 3^n for all n >= 1

With n=1, we have 2 <= 3, which is true.
With n=2, we have 4 <= 9, which is also true,
and informally we can see that 3^n grows faster than 2^n, so we know this relationship holds for all n > 2 as well, and thus:

2^n is contained in O(3^n)

For a more complete description of big-o notation, refer to this excellent post  https://cs.stackexchange.com/a/23594/87624 or for something specific to BigO notation, read the Wikipedia article on big-o notation


The frame size is 2KB. Assuming memory is byte-addressable, we need an offset into 2000 different bytes. 2000 is approximately (2^10)*2 = 2^11, so we need 11 bits for the frame offset.

Then, we can easily calculate that 33 - 11 = 22 bits are used to identify  a physical page (frame), and 34 - 11 = 23 bits are needed to identify a virtual page.


Meaning of polynomially larger or smaller in the context of the master method

(This answer refers to the version 6 of the question, which does not contain "my professor's response".)
It looks like there is some typo/inconsistency/misunderstanding somewhere in your class, the slides or your post. Hence, I will start from scratch, addressing the problems I can recognize.
Let me fix the meaning of "polynomially smaller" and "polynomially larger" in the current context. There are other usages, which are not relevant here.
Meaning of polynomial differences.
$f(n)$ is polynomially smaller than $g(n)$ if $f(n) = O(g(n)/n^\epsilon)$ for some $\epsilon > 0$.
$f(n)$ is polynomially larger than $g(n)$ if $f(n) = \Omega(g(n)n^\epsilon)$ for some $\epsilon > 0$. We will never say $f(n)$ is polynomially equal to $g(n)$.
Here are some examples.

$f(n)=1$ and $g(n)=n^2$. Then $f(n)$ is polynomially smaller than $g(n)$. This is what you believed and it is correct.
$f(n)=g(n)=n^2$. Then $f(n)$ is not polynomially smaller nor polynomially larger than $g(n)$.
$f(n)=n^{1+\frac{1000}{\log n}}$ and $g(n)=n^2$. Then $f(n)$ is polynomially smaller than $g(n)$.
$f(n)=\dfrac{n}{\log n}$ and $g(n)=n$. Then $f(n)$ is not polynomially smaller nor polynomially larger than $g(n)$.

$T(n) = 4T(\dfrac n2) + 1$
$a=4$, $b=2$, $n^{\log_24}=n^2$ is polynomial larger than the constant function 1. This is case 1 of the master's theorem.
$T(n) = 4T(\dfrac n2) + \dfrac{n^2}{\log n}$
$a=4$, $b=2$, $\dfrac{n^2}{\log n}$ is not polynomially smaller nor polynomially larger than $n^2$. None of the three cases of master's theorem can be applied. However, the extension of case 2, case 2b can be applied.

Simple exercises
Exercise 1. Suppose $f(n)$ is polynomial smaller than $g(n)$. Show that $f(n)$ is eventually smaller than $g(n)$, i.e., there exists some constant $n_0$ such that $\lvert f(n)\rvert \lt g(n)$ for all $n>n_0$.
Exercise 2. Verify that $f(n)$ is polynomial smaller than $g(n)$ if and only if $g(n)$ is polynomial larger than $f(n)$, assuming that both $f$ and $g$ are always positive.
Exercise 3. Suppose $f(n)$ is polynomial smaller than $g(n)$. Find another function $h(n)$ such that $f(n)$ is polynomial smaller than $h(n)$ and $h(n)$ is polynomial smaller than $g(n)$.


How do I normalize a push down automaton?

What do you call a normalized PDA? There are many ways to specify
that. Also, a PDA is defined by its transition fonction. The diagram
is just a convenient graphical way to do that, as long as it is
precise and easily read.

For the example you give, a transition is not represented by a
directed edge, but by a directed edge together with a label. If you
have an edge with two labels, as in your loop on $q_1$, that
represents two transitions. Trying to do it with two separate loop
edges would only make your diagram less readable.

Now, it is possible that your instructor has defined "normalized
diagrams" in some way, and you should try to follow his wishes.  But I
do not remember of any such normalization of PDA diagrams with real
technical importance.

Yes it is OK to have multiple transitions from one state to
another. You could avoid it by introducing new intermediate states,
but that would serve absolutely no purpose other than making your life
miserable.


Operation on two CFLs which results in a non-CFL

Let's denote your operation by $\diamond$, so the question is, if $L_1$ and $L_2$ are CFLs, is $L_1\diamond L_2$ always a CFL? The answer is no.

Let $L_1=L_2=\{0^n1^n\mid n\ge 0\}$. This is, of course, a CFL. However,
$$
L_1\diamond L_2=\{0^n1^n0^n1^n\mid n\ge 0\}
$$
and it's not too hard to show that this language is not context-free.


Exponential averaging for SJF CPU scheduling

A possible interpretation of the problem is that we initially had jobs with actual run times 8, 7, 4, and 16. Assuming no new jobs entered the queue, we'd schedule then in increasing order of their times, namely 4, 7, 8, 16 (since that's what SJF means--shortest job first). Under these assumptions we'd have time slices
$$\begin{align}
T_2&=\frac{1}{2}(4+10)=7&\text{after the first job has run}\\
T_3&=\frac{1}{2}(7+7)=7&\text{after the second job has run}\\
T_4&=\frac{1}{2}(8+7)=7.5&\text{after the third job has run}\\
\end{align}$$
so the fourth job would be given a slice of 7.5, which is choice (3).

This isn't an entirely satisfactory answer since of course the OS might not know how much time the jobs would actually take before hand, but if the problem assumed they'd be run in that order (4, 7, 8, 16) we'd have what was mentioned as the correct answer, so it's at least a possible interpretation.


Is an infinite tape alphabet for TM valid?

Turing machines have a finite tape alphabet.

You can think of a generalization of Turing machines with infinite tape alphabet, but there are two problems:

The description of the machine is no longer finite.
Such a machine can decide any language over $\{0,1\}$ (exercise).

There are ways around it - for example, we might require the rules to be finitely specifiable in some specific form. The resulting model will then be equivalent to Turing machines (in terms of computability).


Algorithm to compose identity from a set of permutations

Assuming that "smallest composition" means smallest number of permutations used in the composition, then the NP-complete Pancake Flipping Problem is a special case of your problem.


What crossover operator should I use for arranging students in classrooms?

What you're (probably) doing:

0 = Bob
1 = Mary
2 = John
3 = Susan

parents
[2 | 1 | 0 | 3] => John takes first seat, ..., Susan takes fourth seat.
[3 | 2 | 1 | 0] => Susan takes first seat, ..., Bob takes fourth seat.
       ^
one point crossover
[3 | 2 | 0 | 3]   Where is Susan? (and Mary?)
[2 | 1 | 1 | 0]

What you can do:

allow the generation of an invalid chromosome / individual assigning a
very low fitness value. Such individual will be penalized (ignored) during evolution.

This is very time consuming and not effective
repair an invalid chromosome. It's time consuming but it could work
use ad-hoc operators.

E.g. with Partially Matched Crossover:

(from Genetic Algorithm)

PMX builds an offspring by choosing a subsequence from one parent preserving as many positions as possible from the other parent.

  A subsequence is delimited by two cut points. After this, the segments between the cut points are swapped (the positions in yellow). We have the map: 1↔8, 9↔5, 8↔7 and 6↔3.
  Fill the positions for which there is no conflict. In the example shown, the positions 4 and 2 in both chromosomes (the positions in blue).
  Use the map to fill the remaining positions (the positions in green). Note that using the mapping 1↔8 in the o1 vector a conflict occurs again so one must apply the mapping 8↔7 to obtain a number not repeated.

Other operators are listed in  Crossover for ordered chromosomes but pay attention to the fact that some operators tend to preserve the relative positions more than the absolute positions.
change point of view / representation.

E.g. [2 | 1 | 0 | 3] or [3 | 2 | 1 | 0] are permutations. Standard GA crossover operators produce offspring which aren't permutations. A clever representation of permutations could avoid the problem.

You can represent a permutation as its inversion sequence: for each element i, store in a[i] how many elements larger than i are to the left of i in the permutation.

The only constraint on a[i] is that it cannot be larger than N - i (N is the number of genes).

Now standard crossover of two valid inversion sequences always produces two valid inversion sequences: no need for special handling of repeating elements.

This idea is described in Genetic Algorithm Solution of the TSP
Avoiding Special Crossover and Mutation (Göktürk Üçoluk).


How does consistency imply that a heuristic is also admissible?

To proof the statement in your question, let us proof that consistency implies admissibility whereas the opposite is not necessarily true. This would make consistency a stronger condition than the latter.

Consistency implies admissibility:

Let me start by emphasizing that $h(t)=0$ if the heuristic function $h$ is admissible (where $t$ is a goal) since edge costs are assumed to be non-negative and thus, the optimal cost from one node to itself is necessarily 0. This certainly holds in case the heuristic function is admissible but we want to proof that consistency necessarily implies admissibility. For this, let us assume further that $h(t)=0$ for any goal ---and this fact will be used in the base case below.

The proof proceeds by induction:

Base case: take any predecessor of the goal node $t$. Let $n$ denote it, so that $t$ is a successor of $n$. If the heuristic function is consistent, then $h(n)\leq c(n,t) + h(t)=c(n,t) + 0 =c(n,t)$ and hence, $h$ behaves admissibly in this case.

Note that the base case does not assume that the edge $\langle n, t\rangle$ is necessarily the optimal solution from $n$ to $t$ and, indeed, there might be a different path from $n$ to $t$ with a lower cost. The importance of the base case, is that $h(n)\leq c(n,t)$ for all ancestors of node $t$! This result will be reused in the induction step.

Induction step: consider a node $n$. The optimal cost to reach the goal $t$ from $n$, $h^*(n)$, is computed as: $\min_{m\in\mathrm{SCS(n)}}\{c(n,m)+h^*(m)\}$, where $\mathrm{SCS}(n)$ is the set of successors of node $n$. As consistency is assumed by hypothesis, then $h(n)\leq c(n,n')+h(n')$. Furthermore, as $h(n')\leq h^*(n')$ is assumed by the induction step then $h(n)\leq c(n,n')+h^*(n')$  and this is true for all successors $n'$ of node $n$. In other words: $h(n)\leq \min_{m\in\mathrm{SCS(n)}}\{c(n,m)+h^*(m)\} = h^*(n)$, so that $h(n)\leq h^*(n)$.

Admissibility does not necessarily imply consistency:

For this, a simple example suffices. Consider a graph which consists of a single path with 10 nodes: $\langle n_0, n_1, n_2, ..., n_9\rangle$, where the goal is $n_9$. Let us assume wlog that all edge costs are equal to 1. Obviously $h^*(n_0)=9$, and let us make $h(n_0)=8$, $h(n_i)=1, 1\leq i<9$ and $h(n_9)=0$. Clearly, the heuristic function is addmissible:

$h(t)=0$
$h(n_i)=1\leq h^*(n_i)=(9-i)$, $\forall i, 1\leq i<9$.
Finally, $h(n_0)=8\leq h^*(n_0)=9$.

However, $h(n)$ is not consistent and $h(n_0)=8 > c(n_0, n_1)+h(n_1)=1+1=2$.

Hope this helps,


When is the AKS primality test actually faster than other tests?

Quick answer:  Never, for practical purposes.  It is not currently of any practical use.

First, let's separate out "practical" compositeness testing from primality proofs.  The former is good enough for almost all purposes, though there are different levels of testing people feel is adequate.  For numbers under 2^64, no more than 7 Miller-Rabin tests, or one BPSW test is required for a deterministic answer.  This will be vastly faster than AKS and be just as correct in all cases.  For numbers over 2^64, BPSW is a good choice, with some additional random-base Miller-Rabin tests adding some extra confidence for very little cost.  Almost all of the proof methods will start out (or they should) with a test like this because it is cheap and means we only do the hard work on numbers which are almost certainly prime.

Moving on to proofs.  In each case the resulting proof requires no conjectures, so these may be functionally compared.  The "gotcha" of APR-CL is that it isn't quite polynomial, and the "gotcha" of ECPP/fastECPP is that there may exist numbers that take longer than expected.

In the graph, we see two open source AKS implementations -- the first being from the v6 paper, the second including improvements from Bernstein and Voloch and a nice r/s heuristic from Bornemann.  These use binary segmentation in GMP for the polynomial multiplies so are pretty efficient, and memory use is a non-issue for the sizes considered here.  They produce nice straight lines with a slope of ~6.4 on the log-log graph, which is great.  But extrapolating out to 1000 digits arrives at estimated times in the hundreds of thousands to millions of years, vs. a few minutes for APR-CL and ECPP.  There are further optimizations which could be done from the 2002 Bernstein paper, but I don't think this will materially change the situation (though until implemented this isn't proven).

Eventually AKS beats trial division.  The BLS75 theorem 5 (e.g. n-1 proof) method requires partial factoring of n-1.  This works great at small sizes, and also when we're lucky and n-1 is easy to factor, but eventually we'll get stuck having to factor some large semi-prime.  There are more efficient implementations, but it really doesn't scale past 100 digits regardless.  We can see that AKS will pass this method.  So if you asked the question in 1975 (and had the AKS algorithm back then) we could calculate the crossover for where AKS was the most practical algorithm.  But by the late 1980s, APR-CL and other cyclotomic methods was the correct comparison, and by the mid 1990s we'd have to include ECPP.

The APR-CL and ECPP methods are both open source implementations.  Primo (free but not open source ECPP) will be faster for larger digit sizes and I'm sure has a nicer curve (I haven't done new benchmarking yet).  APR-CL is non-polynomial but the exponent has a factor $\log \log \log n$ which as someone quipped "goes to infinity but has never been observed to do so".  This leads us to believe that in theory the lines would not cross for any value of n where AKS would finish before our sun burned out.  ECPP is a Las Vegas algorithm, in that when we get an answer it is 100% correct, we expect a result in conjectured $O(\log^{5+\epsilon}(n))$ (ECPP) or $O(\log^{4+\epsilon}(n))$ ("fastECPP") time, but there may be numbers that take longer.  So our expectation is that standard AKS will always be slower than ECPP for almost all numbers (it certainly has shown itself so for numbers up to 25k digits).

AKS may have more improvements waiting to be discovered that makes it practical.  Bernstein's Quartic paper discusses an AKS-based randomized $O(\log^{4+\epsilon}(n))$ algorithm, and Morain's fastECPP paper references other non-deterministic AKS-based methods.  This is a fundamental change, but shows how AKS opened up some new research areas.  However, almost 10 years later I have not seen anyone use this method (or even any implementations).  He writes in the introduction, "Is the $(\lg n)^{4+o(1)}$ time for the new algorithm smaller than the $(\lg n)^{4+o(1)}$ time to find elliptic-curve certificates?  My current impression is that the answer is no, but that further results [...] could change the answer."

Some of these algorithms can be easily parallelized or distributed.  AKS very easily (each 's' test is independent).  ECPP isn't too hard.  I'm not sure about APR-CL.

ECPP and the BLS75 methods produce certificates which can be independently and quickly verified.  This is a huge advantage over AKS and APR-CL, where we just have to trust the implementation and computer that produced it.


Prove that $TQBF \notin SPACE(n^{\frac{1}{3}})$

The argument is actually surprisingly delicate. This sketch follows Tompa's Introduction to computational complexity, Chapter 10. The space hierarchy theorem shows that there is some problem $L \in \mathrm{SPACE}(n^{1+\epsilon}) \setminus \mathrm{SPACE}(n)$ for every $\epsilon > 0$. Since TQBF is PSPACE-complete, there is some logspace reduction from $L$ to TQBF. But we actually know more - using Savitch's theorem, we can come up with some reduction which blows up instances of $L$ of size $n$ to instances of TQBF of size $O(n^{2(1+\epsilon)} \log n)$ (at least according to Ryan Williams, page 1 at the bottom). If TQBF were solvable in space $O(n^\delta)$ then this would give an algorithm for $L$ in space $O(n^{2\delta(1+\epsilon)})$. Taking the limit $\epsilon \to 0$, this shows that $\delta \geq 1/2$.


How to state a recurrence that expresses the worst case for good pivots?

The worst case for the good pivot is one where you split in 3n/4 and n/4. Splitting into two equal parts of size n/2 is the best possible case you can have. On the other hand, for the good pivots, 3n/4 leaves you with the largest subproblem possible.


what is the best way to approach the construction of nondeterministic PDA's?

For the "$w$ part", as you said (or implied) yourself, you don't need the stack at all. After switching to the "$0^i1^j$ part", in some state $s_2$, you can put for the $0$'s in the input alternatingly first an $a$ on the stack, then delete it with a $b$ for the second $0$, then add a $c$ for the third $0$, then start over. By adding only two of the three symbols for each stream of three zeros (as you delete $a$), you get $2/3i$ symbols in the stack which is just equal to $j$. You get a stack like this:
$kbcbc\ldots$ ($k$ being the bottom stack symbol).

Now, you just have to delete each $b$ or $c$ with the ones coming on the input tape and accept iff you reach the bottom of the stack ($k$) when the input is complete.

The second part of the PDA might look something like this ($\lambda$ being the empty word):

$(s_2, 0, k) \rightarrow (s_2, ak)$

$(s_2, 0, a) \rightarrow (s_2, b)$

$(s_2, 0, b) \rightarrow (s_2, cb)$

$(s_2, 0, c) \rightarrow (s_2, ac)$

$(s_2, 1, c) \rightarrow (s_3, \lambda)$

$(s_3, 1, c) \rightarrow (s_3, \lambda)$

$(s_3, 1, b) \rightarrow (s_3, \lambda)$

$(s_3, \lambda, k) \rightarrow (s_e, k)$


P is undecidable and not semidecidable, Q is undecidable and semidecidable and P ⊂ Q

Hint: Following the OP's suggestion, let $P$ be the set of all TMs halting on every input, and let $Q$ be the set of all TMs halting on the empty input. It is known that $Q$ is undecidable and semidecidable (indeed, $\Sigma_1^P$-complete) and that $P$ is undecidable and not semidecidable (indeed, $\Pi_2^P$-complete). Moreover, $P \subseteq Q$ since if $T \in P$ then $T$ halts on every input, and in particular $T$ halts on the empty input, so that $T \in Q$.


How is a compiler related to the runtime system?

I just looked on my machine (which is running macOS Sierra), and I found four runtime systems for C and C++ alone:

/usr/lib/crt1.10.5.o
/usr/lib/crt1.10.6.o
/usr/lib/crt1.o
/usr/lib/gcrt1.o

They're not huge; only about 10kB each. Small enough that if you statically linked them to a typical program they would barely register. Still, there they are.

I'm certain that I have a bunch of others for different languages, too: Python and Java are fairly standard. Emacs seems to come pre-installed so there's a Lisp-like language. There's probably a Swift runtime if I look hard enough. And, of course, that's not including all the languages I installed myself because I like collecting programming languages.

Many modern operating systems are designed with C in mind (in that their system call APIs are C calls), and many languages with a "foreign function" interface support C natively because so many third-party libraries support a C API. So runtimes for many languages are often built on top of the C runtime.

It's useful to think of a runtime system as some kind of virtual machine. However, many programming languages do compile to machine code, so the job that the runtime system has to do can be as simple as initialisation and shutdown only, with nothing further needed while the program is running.

For example, a typical runtime for C and C++ (they are often shared these days) has to perform the following initialisation before any C code is run:

Set up the C stack.
Initialise any standard library data structures that need to be initialised (e.g. atexit or stdin/stdout/stderr).
Invoke static constructors (e.g. for C++).
Process command-line arguments and environment variables to pass to main().
Call main().

There's nothing here that really corresponds to interpreting the output of the compiler, with the possible exception of information that the compiler generates about static constructors.

Even for compiled languages, however, the runtime may provide subroutines to support source-level operations for which it would be wasteful or inconvenient for the compiler to generate code.

Exceptions in C++ are one example. Another is where some particular platform doesn't have a suitable instruction; many 32-bit platforms don't have a native 64-bit division instruction, but the compiler may still want to support 64-bit integers.


The concept of the creation of a trapdoor in NP-complete or NP-hard problems

A "trapdoor" function is a function which is hard to compute, but will become very easy (or a lot easier) to compute if you have some specific knowledge.
The classical example is solving y = x^3 (modulo n) where n is the product of two very large primes; it is the basis of RSA encryption and practically impossible to solve given x and n, unless you are given the two primes p, q such that n = pq.


Minimum s-t cut in weighted directed acyclic graphs with possibly negative weights

You've refined your problem some more in the comments. To be more specific, you have a DAG with all edges flowing away from the source $s$ and towards the sink $t$ (that is, all edges are on a path from $s$ to $t$). You want to find the minimum cut between two pieces of the DAG, where the first piece is connected to $s$, and the second connected to $t$. For this problem, a variation of the standard linear-programming algorithm for MIN-CUT works, even with negative edge weights.

We use the same notation as in Wikipedia. The cost of edge $(i,j)$ is $c_{ij}$. We put a potential function $p_i$ on each node, and let $d_{ij} = p_i - p_j$. The LP is
$$ \begin{align*} \mathrm{minimize\ } & \sum_{(i,j) \in E} c_{ij} d_{ij} \\
\mathrm{subject\ to\ } & \ \ \ d_{ij} = p_i - p_j \ \ \forall (i,j) \in E \\ &\ \ \ d_{ij}  \geq 0 \ \ \ \ \ \ \ \ \ \ \ \, \forall (i,j) \in E \\ & \ \ \  p_s\, = 1 \\ & \ \ \ p_t \, = 0  \end{align*} $$

These equations guarantee that $0 \leq p_i \leq 1$, since every vertex is on some $s$–$t$ path. Similarly, since $d_{ij} = p_i - p_j$ is non-negative, the potentials on any path from $s$ to $t$ are decreasing. We still need to show that there is an optimal solution to the LP with all $p_i$ either $0$ or $1$. This follows from the fact that the value to a solution of the LP above is the expected value of the cut $C_w$, where $w$ is chosen randomly in $[0,1]$, and where cut $C_w$ is obtained by putting all vertices $i$ with $p_i\geq w$ in the first set of vertices, and all vertices  with $p_i < w$ in the second set.


Interesting proposition.

Moreover, the trees in a collection can have height 1,3,4,8 as an example. It is not limited to increasing by 1.

How could 1,3,4,8 be an example? If you set $i=0$ in "there exist at least $i + 1$ x-heaps of $height \leq i$, where $0\leq i \leq k$", you know there exist at least 1 X-heap of height less than or equal to 0. That means $X_0$ must be 0. In fact, the height will be increased by 0 or 1 every time.
Reformulation
Since an x-heap is completely determined by its height, let us introduce almost-natural sequences, which comes from a collection of x-heaps in the question.
An almost-natural sequence is a non-decreasing sequence of integers $0=h_0, h_1,\dots,h_k$, where $k\ge0$, such that, for all $0\le i\le h_k$,

at least $i + 1$ of them are not greater than $i$
at most $i + 2$ of them are not greater than $i$.

Characterization of almost-natural sequences. An almost-natural sequence must be one of the following.

$0, 1, \cdots, k-1, k$, i.e., the first $k+1$ natural numbers.
$0, 1, \cdots, m-1, m, m, m+1, \cdots, k-2, k-1$, i.e., the first $k$ natural numbers with one of them, $m$ repeated once, where $0\le m\le k-1$.

Corollary. $2^k\le\sum_{i=0}^k2^{h_k}\le2^{k+1}-1$ for an almost-natural sequence $h_0,h_1,\dots,h_k$.
Exercises
Here are a few related exercises.
Exercise 1. Prove the characterization of almost-natural sequences.
Here is a hint. Does a given almost-natural sequence contain a repeated number? If yes, prove that number appears exactly twice and no other number is repeated.
Exercise 2. Prove the corollary.
Exercise 3. Let a d-natural sequence be a non-decreasing sequence of $k+1$ integers $0=h_0, h_1,\dots,h_k$ such that at least $i+1$ and at most $i+1+d$ of them are not greater than $i$ for all $0\le i\le h_k$. Determine the lower bound and upper bound of $\sum_{i=0}^k{h_k}$ and $\sum_{i=0}^k2^{h_k}\,.$


Random file access in a block based file format

A starting point for this would be the heap management algorithms, start perhaps here. I remember Knuth in his Art of Computer Programming has a detailed discussion, I believe in volume 1. The algorithms described are good for RAM, adding in the non-uniform access of rotating disks will be quite a challenge...

Isn't it much simpler to use a database and blobs? Your time is valuable too...


Strictly speaking do the Hoare and Lomuto partitioning algorithms work on the same algorithm: quicksort?

The term "Quicksort" stands for this abstract algorithmic idea:

Pick a value $x$.
Partition the input into $\{y\mid y \leq x\}$ and $\{y \mid y > x\}$.
Recurse on the partitions (if they are non-trivial) and append the results.

You may want to generalise to multiple pivots, or create a third partition for elements equal the pivot, but mostly that's it.

There are many, many implementations. All of them are called "Quicksort", but many modify the name.
See here for a discussion about the differences of these particular two variants.


As Yuval indicated in the comment, a right-moving TM is already essentially a FA. Here's the construction:

Given a TM move rule $\delta(q, x)=(p, y, d)$ where, as usual, $q$ is the current state, $x$ is the contents of the current cell, $p$ is the new state, $y$ is the symbol replacing $x$ in the current cell, and $d$ is the direction to move the head. Since the machine can only move right, it is immaterial what gets overwritten on the current cell and since $d$ is always move right, we can ignore both of these, leaving us with moves of the form $\delta(q, x)=(p)$, i.e., the moves for a FA.

The construction above is for a DFA, the one for a NFA is essentially the same.


What is the time complexity of finding the residual network in this case?

The time complexity of this problem is (at most) the time complexity of the network flow problem.  You are given a graph and you want to find a flow of size $f$.  You can use any network flow algorithm for this.  Different algorithms have different running time.  Wikipedia has a list of algorithms, with their running times.  There is not a single optimal algorithm; different algorithms work better in different situations.

You mentioned you want to find a flow of size at least $f$, rather than a max flow.  Many of the algorithms for max flow can be adjusted to stop early when you've found a flow that is large enough.  Or, you can adjust the graph to ensure that a flow of size $f$ is a max flow -- if the original source vertex is $s$, add a new vertex $s_0$ and an edge $s_0 \to s$ of capacity $f$, then treat $s_0$ as the new source vertex and solve the max flow problem.

Once you find the flow itself, you can compute the residual network in $O(m)$ time.  For each edge, you compute how much remaining capacity it has (the capacity of that edge minus the amount sent by the flow); and you add a reverse edge if necessary (the amount of the flow).  This is $O(1)$ work per edge.  All known network flow algorithms take $\Omega(m)$ time.  Therefore, the time to compute the residual network once you find the flow is negligible; the bottleneck is finding the flow itself.


A reduction from a problem $A$ to another problem $B$ is a transformation $f$ of any instance $a$ of $A$ into an instance $f(a)$ of $B$, such that

$$\qquad\qquad x∈A ~~⇔~~ f(x)∈B \qquad \qquad (E)$$

If $f$ is a transformation preserving the complexity you are interested in (e.g. $f$ is a polynomial transformation if you consider $\mathsf{NP}$-hardness) then the existence of an algorithm $\mathcal A_B$ solving $B$ implies the existence of an algorithm solving $A$: it is enough to run $f$, then $\mathcal A_B$.

Hence the existence of such a reduction from $A$ to $B$ means that $B$ is not easier than $A$. It is not necessary to have a reduction the other way.

For example, for graph coloring. You can reduce 3-coloring to 4-coloring but not in the immediate way. If you take a graph $G$ and you choose $f(G)=G$ then you will have that $x∈3\mathsf{COL}$ $⇒$ $f(x)∈4\mathsf{COL}$ but you don't have $f(x)∈4\mathsf{COL}$ $⇒$ $x∈3\mathsf{COL}$ of course. The conclusion is that the equivalence $(E)$ is not respected, so $f$ is not a reduction.

You can build a correct reduction $f$ from $3\mathsf{COL}$ to $4\mathsf{COL}$ but it is a little more complicated: for any graph $G$, let $f(G)$ be the graph $G$ extended with another node $u$ that is linked with an edge to every other node.

The transformation is complexity-preserving (polynomial, here);
if $G$ is in $3\mathsf{COL}$ then $f(G)$ is in $4\mathsf{COL}$: just use the fourth color for $u$;
if $f(G)$ is in $4\mathsf{COL}$ then you can prove that all the nodes except $u$ have a color that is not $u$'s, hence $G$ is in $3\mathsf{COL}$.

That proves that $f$ is a reduction and that $4\mathsf{COL}$ is harder than $3\mathsf{COL}$. You can prove the same way that $n\mathsf{COL}$ is harder than $m\mathsf{COL}$ for any $n≥m$, the interesting proof being of the fact that $3\mathsf{COL}$ is harder than any $n\mathsf{COL}$.


Proving NP-completeness for a not so cheesy problem

The problem is in $NP$ since a certificate is the path itself, which has length at most $2B-1 + 2 = 2B+1$.
Given an instance $\langle S, k\rangle$ of subset sum where $S = \{x_1, \dots, x_n\}$ is a set of integers and $k$ is the target value, you can create an instance of your problem by choosing: $B=n+2$, $M = \mbox{diag}(0, x_1, x_2, \dots, x_n, 0)$, and $A = k$.
Clearly any path in $M$ that collects $A$ pieces of cheese implies the existence of a subset $S' \subseteq S$ such that $\sum_{x_i} x_i = A = k$.
On the converse notice that, given any $S' \subseteq S$ satisfying $\sum_{x_i} x_i = k$, it is possible to find a path $P$ in $M$ with the sought constraints (actually, backtracking is not even required) that traverses $M[i+1, i+1]$ if and only if $x_i \in S'$. This shows that pieces of cheese collected by $P$ are exactly $k=A$.
Also notice that your problem can be solved by pseudopolynomial-time dynamic programming algorithm having complexity $O(A \cdot B^2)$.


I was under the impression that if a Turing machine can perform the same actions and satifies unrestricted access to unlimited memory they're all pretty much equivalent.

Hint 1: So your first step should be to determine whether a and b have, or can obtain, unrestricted access to unlimited memory.

Hint 2: If yes, then try to emulate the missing pieces of your preferred Turing machine model.

Hint 3: If no, then try to show that the halting problem (with empty tape as input) is decidable.


Do there exist coding languages where the halting problem is solvable but not trivial

I think I understand what you are trying to ask. But you may have to work
harder on the asking to get a non-trivial answer. As it stands, your question
has a trivial answer. Take a language that always terminate, and add a command
that never terminates and is syntactically constrained to be used first if at
all in a program. To check termination, you only have to check whether the
program contains the non-terminating command.

In some sense, I think you can only have trivial answers. Consider some
language L that meets your definition of halting being decidable, though not always
terminating or always non-terminating. Given the halting decision procedure for L,
we can always change that language L into an almost identical one L' that will
always terminate, though by returning a new special value $\perp$ (read
'bottom'), when language L does not terminate. Now we can look at our
contraption from the other end, and see L as a language derived from the always terminating language L', in a
way that replaces all computations producing a specific result, namely $\perp$,
by an infinite loop. So L is a trivial answer derived from L'.


$S_0$ is the empty set.

Let $i=0$.
$$\begin{align}
 S_1= S_{0+1} & = \;\;\;\{true, false, 0\} \\
& \;\;\;\cup \; \{succ \: t_1, pred \: t_1, iszero \: t_1\ |\: t_1 \in S_0\} \\
&  \;\;\;\cup \; \{if\: t_1 \:then \: t_2 \:else \: t_3\: |\; t_1, t_2, t_3 \in S_0\} \\
& = \;\;\;\{true, false, 0\} \\
& \;\;\;\cup \; \emptyset \\
& \;\;\;\cup \; \emptyset \\
& = \;\;\;\{true, false, 0\} \\
\end{align}$$

So $S_1$ contains 3 elements.

Let $i=1$.
$$\begin{align}
 S_2= S_{1+1} & = \;\;\;\{true, false, 0\} \\
& \;\;\;\cup \; \{succ \: t_1, pred \: t_1, iszero \: t_1\ |\: t_1 \in S_1\} \\
&  \;\;\;\cup \; \{if\: t_1 \:then \: t_2 \:else \: t_3\: |\; t_1, t_2, t_3 \in S_1\} \\
& = \;\;\;\{true, false, 0\} \\
& \;\;\;\cup \; \{succ \: true, pred \: true, iszero \: true, \\
&\quad\quad\;\;succ \: false, pred \: false, iszero \: false, \\
&\quad\quad\;\;succ \: 0, pred \: 0, iszero \: 0\} \\
&  \;\;\;\cup \; \{if\: true \:then \: true \:else \: true,\\
&\quad\quad\;\;if\: true \:then \: true \:else \: false,\\
&\quad\quad\;\;if\: true \:then \: true \:else \: 0,\\
&\quad\quad\;\;if\: true \:then \: false \:else \: true,\\
&\quad\quad\;\;if\: true \:then \: false \:else \: false,\\
&\quad\quad\;\;if\: true \:then \: false \:else \: 0,\\
&\quad\quad\;\;if\: true \:then \: 0 \:else \: true,\\
&\quad\quad\;\;if\: true \:then \: 0 \:else \: false,\\
&\quad\quad\;\;if\: true \:then \: 0 \:else \: 0,\\
&\quad\quad\;\;if\: false \:then \: true \:else \: true,\\
&\quad\quad\;\;if\: false \:then \: true \:else \: false,\\
&\quad\quad\;\;if\: false \:then \: true \:else \: 0,\\
&\quad\quad\;\;if\: false \:then \: false \:else \: true,\\
&\quad\quad\;\;if\: false \:then \: false \:else \: false,\\
&\quad\quad\;\;if\: false \:then \: false \:else \: 0,\\
&\quad\quad\;\;if\: false \:then \: 0 \:else \: true,\\
&\quad\quad\;\;if\: false \:then \: 0 \:else \: false,\\
&\quad\quad\;\;if\: false \:then \: 0 \:else \: 0,\\
&\quad\quad\;\;if\: 0 \:then \: true \:else \: true,\\
&\quad\quad\;\;if\: 0 \:then \: true \:else \: false,\\
&\quad\quad\;\;if\: 0 \:then \: true \:else \: 0,\\
&\quad\quad\;\;if\: 0 \:then \: false \:else \: true,\\
&\quad\quad\;\;if\: 0 \:then \: false \:else \: false,\\
&\quad\quad\;\;if\: 0 \:then \: false \:else \: 0,\\
&\quad\quad\;\;if\: 0 \:then \: 0 \:else \: true,\\
&\quad\quad\;\;if\: 0 \:then \: 0 \:else \: false,\\
&\quad\quad\;\;if\: 0 \:then \: 0 \:else \: 0\}
\end{align}$$

So $S_2$ contains 3+9+27= 39 elements.

Let $i= 2$, we will get $S_3=S_{2+1}=\cdots$, which contains 3+39*3+39^3=59439 elements.

You are supposed to get lost in case you want to find the meaning or the semantics of the elements in $S_1$ and $S_2$, because there is no meaning attached to those elements yet at this stage of the book. In other words, although you, I suspect, have understood all that are supposed to be understood, you do not feel or know that you have. Be relaxed, this introductory book is not supposed to be difficult here.

At this stage of the book, $S_0, S_1, S_2, \cdots$ are just sets of words over the alphabet $\Sigma=\{ true, false, 0, succ, pred, iszero, if, then, else \}$. In fact, 3.2.1 Definition [Terms, inductively] defines the language $\mathcal T$ by the following context-free grammar.

$S\to true \mid false \mid 0$
$S\to succ\ S \mid pred\ S \mid iszero\ S$
$S\to if\ S\ then\ S\ else\ S $

Once again, let me emphasize that there is no meaning to each symbol in the alphabet $\Sigma$. For example, $true$ is just one symbol, which happens to look like "true". It should have worked equally well had we used $asdf$ or $easypeasy$ or $humptydumpty$ instead. It is expected that we will assign meaning or semantics to all symbols in $\Sigma$ and many words in $\mathcal T$; however, that has not been done yet at this stage of the book.

To compute $|S_3|$, we need to prove the formula,
$|S_{i+1}| = {|S_i|}^3 + |S_i| \times3+3$, which comes from the following equality, where $\sqcup$ means disjoint union.

\begin{align}
 S_{i+1} & = \;\;\;\{true,\, false,\, 0\} \\
& \;\;\; \sqcup \, \{succ \: t_1\mid t_1 \in S_i\}
         \,\sqcup\, \{pred \: t_1\mid t_1 \in S_i\} \;
         \sqcup \; \{iszero \: t_1\mid t_1 \in S_i\} \\
&  \;\;\;\sqcup \, \{if\: t_1 \:then \: t_2 \:else \: t_3\: |\; t_1, t_2, t_3 \in S_i\} \\
\end{align}

Note that it might not be trivial to show the cardinality of the last set $\{if\: t_1 \:then \: t_2 \:else \: t_3\: |\; t_1, t_2, t_3 \in S_i\}$ is $|S_i|^3$ for $i\ge2$ in general since we need to show more or less that the grammar above is deterministic. However, the cases of $i=0,1,2$ that are needed for the moment can be easily enumerated.


When does kernel accessing virtual memory cause problems

Same as with any program that uses pointers: dereferencing one that points nowhere sane will give grief. If in the kernel of the system, with little or no protection against accidents (and nobody who can clean up the mess afterwards), it is much worse.


If $A$ is an $n \times m$ dense matrix then $AA^T$ is an $n\times n$ matrices given by
$$
(AA^T)_{ij} = \sum_{k=1}^m A_{ik} A_{jk}.
$$
This gives a $\Theta(n^2m)$ algorithm for computing $AA^T$.
If $n \geq m$ then faster algorithms exist, but they are not used in practice (at least in most situations).
If $A$ is sparse, that is, stored as a list of non-zero entries, then $AA^T$ can be calculated using different algorithms which exploit the sparsity of $A$. For example, we can sort the non-zero entries in $A$ according to the second coordinate, and then compute $AA^T$ by going over all $k$ and adding $A_{ik} A_{jk}$ to $(AA^T)_{ij}$ for any $i,j$ in the list of $k$. If $s$ is the sparsity of $A$ and $s_k$ is the number of non-zero entries with second coordinate equal to $k$, then this runs in time
$$
\sum_{k=1}^m \binom{s_k+1}{2} \propto \sum_{k=1}^m s_k^2 \in [s^2/m,s^2].
$$
Therefore the worst-case running time is $\Theta(s^2)$, and the best-case running time is $\Theta(s^2/m)$.


What is the meaning of 'moderately exponential' running time?

Moderately exponential is not a widely accepted term in general theoretical computer science, though it might have a widely accepted meaning in the area to which the paper you are citing belongs.

From context, it seems that the meaning here is $\exp O(n^\alpha)$ for $\alpha < 1$; an exponential running time would be $\exp O(n)$ or worse.


Providing Tight Example in Approximation Algorithm Analysis

That depends on your definition of approximation ratio. Normally the approximation ratio is defined as the worst ratio between optimal solution and the one produced by your algorithm. If this is the case, all you need to show that the ratio is tight is come up with one bad example.

Sometimes, however, you prove something like $ALG \leq 2OPT + 1$. This means that your approximation ratio is really $2 + o(1)$. To show that this is tight, you will need an example for infinitely many sizes (but not necessarily for a generic size; perhaps all your examples have even size).


Why are these features missing in modern day general purpose computer languages?

You are asking a lot of questions, here are quick answers on some of them:

Syntactic sugar for integer literals: in a language like C, commas already have a function (they are an operator on their own), so there would be an ambiguity. Other languages allow them. In many countries in Europe, the roles of , and . are switched, and this highlights the fact that this type of issue is best handled by a preprocessor.
Large integers: operations on larger integers are slower than ones on smaller integers, so it makes sense to have different types in many circumstances. Libraries typically provide support for large integers even if the language doesn't natively support them.
Math library lacking support for your favorite functions: everybody's favorite functions are different. There is probably a library that supports yours, and otherwise you can write one. Computer algebra systems tend to support all mathematical functions you will ever want to use.
Indentation: you might like indentation, others might not. Generally speaking, the rule in most programming languages (other than Python and perhaps a few others) is that whitespace shouldn't matter. There are many reasons for that, including (historically) macro expansions (or INCLUDEs), and differing indentation styles. If you want to enforce your type of conventions, use a preprocessor.
Built-in profiling: many C compilers already have this feature, and it is part of the tool chain in most widely used programming languages. There is no need for explicit support in language syntax.

In general, one can think of many "improvements" and features for programming languages. That is one of the reasons why there are so many of them. Different compilers might actually implement some of these, perhaps optionally. To answer your general question, why your favorite feature isn't part of your favorite language, the answer is twofold. First, there are many potential features, and programming languages cannot implement all of them (see for example the recent C++ standards, adding lots of features and making the language ever harder to learn). Second, there are some performance issues that you might be ignoring.


Implementation of QuickSort to handle duplicates

The simple implementation idea is to separate the values into three groups: values less than the pivot, values equal to the pivot, and values greater than the pivot.

In pseudocode, the algorithm looks like the following.

algorithm quicksort(A, lo, hi):
    if lo < hi then
        p ← pivot(A, lo, hi)
        left, right ← three-way-partition(A, p, lo, hi)

        quicksort(A, lo, left - 1)
        quicksort(A, right, hi)

The partition procedure looks like the following.

procedure three-way-partition(A, pivot, lo, hi):
    l ← lo
    r ← lo
    u ← hi

    while r ≤ u:
        if A[r] < pivot:
            swap A[l] and A[r]
            l ← l + 1
            r ← r + 1
        else if A[r] > pivot:
            swap A[r] and A[u]
            u ← u - 1
        else: // the element is equal to pivot
            r ← r + 1
    return l, r

It uses three indices l, r and u (left, right, and upper bound), maintaining the following invariant in the while loop.

lo ≤ l ≤ r ≤ u ≤ hi
the elements with index in [lo, l) are smaller to the pivot.
the elements with index in [l, r) are equal to the pivot.
the elements with index in [r, u] are not examined yet.
the elements with index in (u, hi] are greater than the pivot.

There are a few minor variants. The above should be enough for you to understand what is going on.


How do I search for Verification of Quantum Computing

The answer is, when working with sufficiently small numbers, we can simulate the quantum process on a classical computer.  It might take exponentially longer on the classical computer, but for small numbers, that's still feasible (the exponential of a small number is still not too large).

See Question 6 at Scott Aaronson's FAQ (https://www.scottaaronson.com/blog/?p=4317) as well as part (2) of https://www.scottaaronson.com/blog/?p=4372.


The final result is true. But, you have a fault in your computation, as in each iteration you have at least a comparison. Hence, instead of $\frac{n^2}{2}$, we will have $n^2 - 3$. Anyhow, the final result is the time complexity is $\Theta(n^2)$.


This is indeed a nontrivial problem. A solution can be found in this paper: Enumeration and Random Generation of Accessible Automata.


always compress random data sets by more than 50%

That's impossible. You can't compress random data, you need some structure to take advantage of. Compression must be reversible, so you can't possibly compress everything by 50% because there are far less strings of length $n/2$ than there are of length $n$.

There are some major issues with the paper:

They use 10 test files without any indication of their content. Is the data really random? How were they generated?
They claim to achieve compression ratios of at least 50%, while their test data shows they achieve at most 50%.

  This algorithm defines a lossless strategy which makes use of the prime numbers present in the decimal number
  system

What? Prime numbers are prime numbers regardless of the base.
Issue #1 with decompression: prime factorization is a hard problem, how do they do it efficiently?
Issue #2 with decompression (this is the kicker): they multiply the prime numbers together, but doing so you lose any information about the order, since $2\cdot 5 = 10 = 5\cdot 2$. I don't think it is possible to decompress at all using their technique.

I don't think this paper is very good.


Understanding basic queue and dequeue operations

CLRS defines a queue using an array which wraps around i.e when we no longer can insert/delete in the last position, we move to the first position.

From the book,

  The elements in the queue are in locations head[Q], head [Q] + 1, . . . , tail [Q] - 1, where we "wrap around" in the sense that location 1 immediately follows location n in a circular order.

Thus,

  if Q.tail == Q.length

This is for the condition when the tail points to the last element.

  if Q.head == Q.length

This is for the condition when the head points to the last element.

In both cases, we move to the first element due to circular nature.

An example would be this:


What is the complexity to show this theorem?

This is just SAT in disguise. Given a clause, you can encode the set of assignments falsifying the clause as a sum of the type you indicated. The formula is unsatisfiable iff every assignment falsifies some clause, that is, iff the sum of the regular expressions is $(0+1)^{n-1}$.


User level threads are transparent to the kernel?

As, the linked answers and the explanations provided by your textbooks describe that, user level threads are transparent to the kernel, yes they are indeed.

Kernel Level threads are not transparent to the kernel, but user level threads are. Because you yourself said, that User Level Threads are managed by the User level library, and what happens is, the user level threads can get assigned to one or many kernel threads. About these kernel threads the kernel keeps track of (are not transparent to kernel). But it doesn't know which user threads have got assigned onto these kernel threads and how many.

Say, if five user threads are assigned onto one kernel thread and 4 other user threads are assigned onto another kernel thread, the kernel sees just two kernel threads (requesting execution) and doesn't know that there are altogether 9 threads, but it just knows that the program called the User Level Application(s) is(are) using two of the kernel threads.

I hope this helps. Also, I suggest you read the linked posts carefully. They're pretty explanatory.


List of major Open Problems in Computational Complexity and their Likelihood?

What you are searching for could be Some Estimated Likelihoods
For Computational Complexity by R. Ryan Williams, 2018.

Here are "Some Estimated Likelihoods for Some Major Open Problems" in that paper. Note that "The numerical values of my 'estimated likelihoods' are (obviously) nothing
too rigorous. What is more important is the relative measure between problems."


The main benefit is in the size of routing tables. Instead of having to store an entry for every machine on the network, you only need to store an entry for the particular subnet.

For example ISP might have X.Y.Z.W/16 and anyone sending a packet from the outside to any machine in this subnet only needs to know the route to their border. Their border router has a more fine grained view of the subnet (which is probably further split into many more subnets) and then knows which router on their network to send the packet to based on which smaller subnet it belongs to. Thus, subnets provides a level of abstraction to the OUTSIDE. Not the INSIDE which you seemed to have expected.

EDIT: Here's a simplified example. Assume that some large ISP has the network 1.0.0.0/8. Within this large network there are two smaller networks 1.0.1.0/24 and 1.0.2.0/24. To reach a system on either of the two smaller networks a system outside of 1.0.0.0/8 only needs to know the address of the border router of 1.0.0.0/8. Once the packet reaches the router managing 1.0.0.0/8, that router will know how to get to 1.0.1.0/24 or 1.0.2.0/24. Finally, your home router does not even need to know the address of the router of 1.0.0.0/8. It will just blindly send all your packets to a router on your home ISP assuming that this larger router will know how to get to 1.0.0.0/8 (this is what's typically called the default route/gw).

Here's a way to think about this. Think about being on a train station and having to get from city A to B. When you look at the map at the train station in city A it will tell you what trains to take to get to city B. However, that map will not tell you how to get you to your final destination in city B. However, in city B you can probably find a more detailed map that will tell you how to get you to your final destination within city B, but you don't need to have access to that map while still in city A.


Constructing an FSA, where Ratio of number of states of FSA to its Minimal DFA Equivalent < 0.5

What the question is really asking you is:

  How much saving can be achieved by "compressing" a DFA to its equivalent minimal DFA?

The answer is: the amount of saving which can achieved is unbounded. There are (at least) two ways to measure the saving:

Number of states which are eliminated.
Number of states in the new automaton as a fraction of the original number of states.

The number of states which are eliminated is unbounded, and the number of new states as a fraction of the number of original states can be arbitrarily close to zero.

An example is not hard to come by: pick you favorite minimal DFA, and add as many dummy states as you want. These dummy states will not be reachable from the initial state of the original DFA, so thy won't affect the language accepted by the DFA; but they will increase the number of states by an amount of your choice.

What if we disallow this example by asking all states in the DFA to be reachable? What if ask, moreover, that there be an accepting state reachable from any state? (This makes sense as stated if we're allowing the DFA to get stuck, in other words, for the transition function to be a partial function; but a similar condition can be defined for DFAs with total transition functions.) The statements above still hold true, and an example is not difficult to come up to. I challenge the readers to figure out such an example.


Why does P/Poly can also receive bad advice?

Lets review the definition of the class $P/poly$ by Turing machines which take advice.

The class $T(n)/a(n)$ is the set of languages decidable by a Turing machine which runs in time $T(n)$ with advice of length $a(n)$.

More formally, $L\in T(n)/a(n)$ if there exists a Turing machine $M(x,y)$ and a sequence of strings $\left\{\alpha_n\right\}_{n\in\mathbb{N}}$, with $\alpha_n\in\left\{0,1\right\}^{a(n)}$, such that for all $x\in\left\{0,1\right\}^n$ $M$ runs in time $T(n)$ and $x\in L \iff M(x,\alpha_n)=1$.

$P/Poly=\bigcup\limits_{c,d}n^c/n^d$.

As you can see in the definition above, we only require the existence of some sequence of advice $\alpha_n$ that we can trust. Perhaps for some different sequence, $\beta_n\in\left\{0,1\right\}^{a(n)}$, and some $x\notin L$, it holds that $M(x,\beta_{|x|})=1$, but we don't care, since we only required the existence of a "good" sequence of advice.

This is unlike the case with $NP$, where if $x\notin L$, all witnesses must be rejected.


Algorithms for procedural generated mazes

If you have to create the maze:

Without boundaries
Generated uniformly
Generated from a seed

It is unfortunately impossible without risking an endless loop, but most times it is good enough to create a really large maze.
Daedalus has lots of features and implements all the algorithms on this page.
To generate a really big maze in Daedalus, start the program -> press File -> run script -> Worlds largest maze -> click Ok -> press i.
From Daedalus features: (beware the rabbit hole)

World's Largest Maze: This script has the option to use different algorithms to generate the parts of the Maze being viewed, which are nested cell fractal, binary tree, recursive division, unicursal Labyrinth, classical Labyrinth, and Hilbert curve Labyrinth.
Mazes created here are enormous, and measure at least a billion passages on each side. Visiting one cell per second, it would take over 31 years just to walk from one side of the Maze to the opposite side, and that’s assuming no walls are in your way. Wall following to actually solve the Maze will take on average 31 billion years

Wall following a maze this large on a regular computer, would take over 100 years. Exceeding the lifetime of a person, I would say this is "big enough".

Nested Fractal: This creates a fractal Maze, which is composed of smaller Mazes connected together. Each cell of an outer Maze contains an inner Maze nested inside of it, where this Maze nesting process can be repeated multiple times.
Consider a 10^9 by 10^9 passage Maze, or a 10x10 Maze nested with 9 levels total. If we want at least a 100x100 section around us, we only need to create the 100x100 passage submaze at the lowest level, and the seven 10x10 Mazes it's nested within, to know exactly where the walls lie within a 100x100 section.  To ensure the Maze remains consistent and never changes as you move around, have a formula to determine a random number seed for each coordinate at each nesting level.

The nested fractal maze has an obvious texture, where you can see the maze is split up into "blocks"

This is the closest i have come to an infinite maze, and it should be possible to extend this by adding randomization to the edges of the lowest level to break the "blocky" texture.
From Daedalus features:

Binary Tree: The algorithm creates Mazes with the special property that each cell has a passage that leads either up or left, but never both or neither. This creates a biased texture, where one can always easily travel diagonally up and to the left without hitting barriers or having to make choices. Moving down and to the right is when the Maze becomes a challenge, so the Maze is hard to solve but easy to solve backwards. The Maze forms a binary tree, with the upper left corner the root, where each node or cell has one or two children, and one unique parent which is the cell above or to the left of it.

Recursive Division: The algorithm creates a Maze by adding walls, where the area within the Maze is divided by a randomly positioned horizontal or vertical wall with a passage opening within it. Each subarea is then recursively divided with more walls until all areas are filled.

Every time we subdivide, we only have to subdivide the part of the maze we are in.

The images are from World's Largest Maze in Daedalus, (the subjectively best) open-source maze generation program, written in C++, and it even has its own scripting language. If you want a more detailed explanation of the algorithms, you can also check out the source code. The images above are colored based on the distance you have to walk to another cell. Black cells can't be reached without exiting the viewport.


Proving preservation under substitution System F Omega

Throughout $y$ should have type $T_1$ instead of $T_2$.

Let us be more careful about step 3. We are going to apply the following induction hypothesis:

  If $\Gamma, y : T_1, x : S \vdash t_1 : T_2$ and $\Gamma, y : T_1 \vdash s : S$ then $\Gamma, y : T_1 \vdash [x \mapsto s] t_1 : T_2$.

After that we will use abstraction to get $\Gamma \vdash (\lambda y : T_1 . [x \mapsto s] t_1) : T_2$, and finish the proof by observing that $(\lambda y : T_1 . [x \mapsto s] t_1) = [x \mapsto s](\lambda y : T_1 . t_1)$.

So let us make sure that the induction hypothesis is applicable:

First we need $\Gamma, y : T_1, x : S \vdash t_1 : T_2$: because $\Gamma, x : S \vdash (\lambda y : T_1 . t_1) : T_1 \to T_2$ by inversion we obtain $\Gamma, x : S, y : T_1 \vdash t_1 : T_2$ and then we use exchange to get $\Gamma, y : T_1, x : S \vdash t_1 : T_2$. This is your step 1. (The exchange is valid because types are non-dependent in this argument.)
Second, we need $\Gamma, y : T_1 \vdash s : S$: we already have $\Gamma \vdash s : S$. By weakening we obtain $\Gamma, y : T_1 \vdash s : S$, this is your step 2.

Supplemental: It seems unclear how induction works. To perform a proof by induction we need to specify what the induction is on. In this case the induction is on the derivation of $\Gamma, x : S \vdash t  : T$. Thus, we have to look at all the possible cases of deriving $\Gamma, x : S \vdash t  : T$. Each inference rule gives us one case, and we've just discussed the case of $\lambda$-abstraction. Each case has its own induction hypotheses, one for each premise of the rule.

Let me give you a simpler example. Suppose we only had the following typing rules:

Variables: $$\frac{(x : T) \in \Gamma}{\Gamma \vdash x : T}$$
Pairs: $$\frac{\Gamma \vdash e_1 : T_1 \qquad \Gamma \vdash e_2 : T_2}{\Gamma \vdash (e_1, e_2) : T_1 \times T_2}$$
First projection: $$\frac{\Gamma \vdash e : T_1 \times T_2}{\Gamma \vdash \mathsf{fst}\,e : T_1}$$

A derivation is a finite tree built from these rules (if you are not clear about that, you should first understand what a derivation is). Suppose we want to show that every derivable judgement has some given property $\phi$. To prove this by induction on the derivation, we need to show three things:

Variable case: if $(x : T) \in \Gamma$ then $\Gamma \vdash x : T$ has property $\phi$.
Pair case: if $\Gamma \vdash e_1 : T_1$ has property $\phi$ and $\Gamma \vdash e_2 : T_2$ has property $\phi$ then $\Gamma \vdash (e_1, e_2) : T_1 \times T_2$ has property $\phi$.
First projection case: if $\Gamma \vdash e : T_1 \times T_2$ has property $\phi$ then $\Gamma \vdash \mathsf{fst}\, e : T_1$ has property $\phi$.

The first case has no induction hypothesis, it is a base case. This is so because the corresponding inference rule has no premises (only the side condition $(x : T) \in \Gamma$). The second case has two induction hypotheses, namely that $\Gamma \vdash e_1 : T_1$ has property $\phi$ and that $\Gamma \vdash e_2 : T_2$ has property $\phi$. This is so because the corresponding inference rules has these two premises. The third case has one induction hypothesis, and you should be able to see why that is if you understood what I am saying.


Is $\{ w_1cw_2 \mid w_1 ≠ w_2 \}$ a context-free language?

The idea is that $w_1 \neq w_2$ if and only if either (1) $|w_1| \neq |w_2|$ or (2) the $i$th letters of $w_1,w_2$ are different. This leads to the following partition of $L_1$:
$$
\begin{align*}
L_1 &= (a+b)^+(a+b)^nc(a+b)^n \\ &\cup (a+b)^nc(a+b)^n(a+b)^+ \\ &\cup (a+b)^na(a+b)^*c(a+b)^nb(a+b)^* \\ &\cup (a+b)^nb(a+b)^*c(a+b)^na(a+b)^*
\end{align*}
$$
Each of the summands is clearly context-free, hence so is their union.


Sorting an array of strings by length in linear complexity

Assume the maximum length of strings is $k$, which is less than some constant.

Here is a simple algorithm that runs in linear time and $O(1)$ space complexity. The strategy is simply counting strings by length followed by in-place rearrangement.

Assume the input is an array $s[0], s[1], \cdots, s[n-1].$

Count the number of strings of length $i$. Store it in $a[i]$. We can imagine that $s$ is split into $k+1$ blocks of size $a[0], a[1], a[2], \cdots$. In the following steps, the $i$-th block will store the strings of length $i$.

Let $b$ be the partial sums of $a$, i.e., $b[0]=0$, $b[i+1]=b[i]+a[i]$ for all $0\le i\le k-1$. Note that $b[i]$ is the index of the first string in the $i$-th block.
Let $t[0], t[1], t[2],\cdots,$ be an array of $k$ numbers. We will use $t[i]$ to track the next available position to settle the next string of length $i$. Initially, $t$ is a clone of $b$.
Let $j=0$, the index of the first unsettled string. Loop the following.

Suppose the length of $s[j]$ is $i$.

If $j\neq t[i]$, switch $s[j]$ and $s[t[i]]$. Now $s[t[i]]$ is a settled string. Increase $t[i]$ by 1.
If $j= t[i]$, increase $t[i]$ by 1. Keep increasing $j$ until either we find the next unsettled string or we have passed all strings, in which case we return $s$ and stop the algorithm.

How can we increase $j$ efficiently and correctly? We can keep another integer that tracks which block $j$ is in. Note that all strings from index $b[i]$ to $t[i]-1$ inclusive are settled while all strings from index $t[i]$ to $b[i+1]-1$ inclusive are not settled.

It is clear the algorithm runs in linear time. The spaces used besides the original array $s$ are arrays $a,$ $b$ and $t,$ several looping variables, one temporary place needed to switch two strings. In total, the working memory is less than $3(k+1)+c+k=O(1)$.

Exercise. Improve the memory usage of the algorithm by reusing array $a$ for $b$.


How does each element in the output array of a DFT correspond to a specific frequency?

Let us denote the input signal by $x(0),\ldots,x(n-1)$ and the output signal by $y(0),\ldots,y(n-1)$. Your program is using the following formula:
$$
y(k) = \sum_{t=0}^{n-1} e^{-2\pi i tk/n} x(t).
$$
We also have
$$
x(t) = \frac{1}{n} \sum_{k=0}^{n-1} e^{2\pi i tk/n} y(k).
$$
In other words, any input signal can be represented as a linear combination of the functions $\chi_k(t) = e^{2\pi i tk/n}$, and the output signal gives the coefficients of this representation (up to a normalization factor).
The parameter $k$ is analogous to frequency. You can see the analogy more clearly if you write
$$
\chi_k(t) = \cos \frac{2\pi k}{n} t + i \sin \frac{2\pi k}{n} t.
$$


This problem is equivalent to TSP. Compute all pairwise shortest distances between the vertices in the given graph $G$. Then take the complete graph $K_n$ that is weighted with the shortest-distances of the original graph $G$. The TSP tour of the complete graph corresponds to the shortest min-cost closed walk.

More precisely, a shortest tour $\pi$ in $K_n$ decodes a closed walk in $G$: just replace every edge $(u,v)$ in $\pi$ by the shortest path from $u$ to $v$. Clearly, the costs are preserved. Assume that there would be a shorter closed walk in $G$. Select select the vertices in order they appear first. This permutation implies a tour in $K_n$ (maybe even shorter than the closed walk in $G$), hence we have a contradiction.

See the figure for your example.


First, observe that $\lfloor \log N \rfloor < 2\lceil \log N \rceil$ holds for all $N \geq 2$.
Let $n_0 = 2$, $c_1=2$, $f(N)=2\lfloor \log N \rfloor$, $g(N) = 2\lceil \log N \rceil$.
So $$f(N) \leq c_1 \cdot g(N)$$
holds for all $N \geq n_0$.
Next, observe that $\lfloor \log N \rfloor > \frac{1}{2}\lceil \log N \rceil$ is true for all $N \geq 2$.
Let $c_2 = \frac{1}{2}$.
Thus,
$$f(N) \geq c_2 \cdot g(N)$$
Therefore, $$f(N) \in \Theta(g(N))$$
But the second question, it is obvious that the statement is incorrect, so I'll not be proving here.


Proof by contradiction for greedy algorithms

Just think like this. Without loss of generality, assume

$\begin{equation*}
   \dfrac{v_1}{w_1} > \dfrac{v_2}{w_2} > \dotsb > \dfrac{v_n}{w_n}
\end{equation*}$

(item types with same $v_i/w_i$ can be merged, it doesn't matter in the end).

Let ALGs choices be $p_1, p_2, \dotsc, p_n$, OPTs choices be $q_1, q_2, \dotsc, q_n$.

Assume ALG doesn't give an optimal solution, so $\mathbf{p} \ne \mathbf{q}$. As they are different, there is $i$ such that $p_k = q_k$ for $1 \le k \le i$ and $p_i \ne q_i$. By the way ALG works, it adds as much of $i$ as it possibly can, so $p_i > q_i$.  What OPT looses by this against ALG on $i$ is $(p_i - q_i) \cdot v_i / w_i$, and it more than makes up the loss by adding $(p_i - q_i)$ weight of items that are all worth less per weight than $i$. That is impossible.


Systematic approach or algorithm for designing a pushdown automata that accepts a langauge

Your question is something very natural, that comes up a lot when first encountering computational model.
The main problem is that your question does not "compile":

You ask if there is an algorithm that constructs PDAs. What would be the input for such an algorithm? This is the main crux of the problem.

Until you specify that, you won't really have an answer. As Yuval commented, if you get a CFG as input, then there is an easy procedure to convert it to a PDA.

Let's look at the other extreme: suppose you are given a Turing Machine, and you just ask whether there exists a PDA for its language (even without constructing it). As it turns out, this problem is undecidable (it's an immediate consequence of Rice's theorem, but in fact it's neither in RE nor in coRE).

This problem is something that often comes up in designing computational models - how do we specify what we want? If we give a rich specification formalism, such as Turing machines, then things become undecidable. And if we give something too poor, such as CFGs, then the construction task becomes easy, but writing down the specification becomes the hard part, so it's debatable whether we actually did any good...


Depending on the exact semantics of the replace operation (regarding multiple matches, overlapping matches, etc.), it can likely be modelled as a finite-state transducer.  The set of possible values of s can be modelled as a regular language.  It is known that the application of a finite-state transducer to a regular language gives you another regular language, and there are standard algorithms for computing it, using the product construction.


Where does the decimal to binary "Divide by 2" algorithm come from?

The algorithm follows fairly directly from our usual representation of numbers. Since most of us are more familiar with decimal, let's start there. Let's pick a number--say, 937. Since this is decimal, this means 9 * 102 + 3 * 101 + 7 * 100. So, repeatedly taking the remainder after dividing by 10 gives us the digits.
If we convert to binary, that's 11'1010'1001, because 937 is 1 * 29 + 1 * 28 + 1 * 27 + 0 * 26 + [...] + 1 * 20.
Just like in decimal, taking the remainder with repeated division by the number base we care about (2 in this case) gives us the digits of the number, starting from the least significant and progressing to the most significant, because that's pretty much how we define the representation of a number in a particular base.


Is it Possible to Get Maximum Weighted Input Value in a Neural Network?

No, not with standard activation functions, but you might be able to approximate it.  For instance, if the activation function is differentiable, then the output of such a network will always be differentiable, but the "max" function is not differentiable.

You're more likely to get a useful answer if you provided some context about what you're trying to accomplish or how you'll use the answer.  I suspect an XY problem.


How does one use the Nerode-Myhill theorem to prove that a language is regular?

It is just as straightforward to show a language is regular using Nerod-Myhill theorem as to show a language is not regular using that theorem since Nerode-Myhill theorem characterizes when a language is a regular.

For example, let us take the simple language $L=\{s: |s|\equiv 0 \text{ (mod 2)}\}$. There are two equivalent classes of $L$, assuming $a$ is a letter in the alphabet.

$\left[\epsilon\right]_{\equiv_{L}}=\left\{s: |s|\equiv 0\text{ (mod 2)}\right\}$
$\left[a\right]_{\equiv_{L}}=\left\{s: |s|\equiv 1\text{ (mod 2)}\right\}$

It should be easy for you to show that the above two classes are well-defined equivalence classes of $L$. There are no other equivalence class of $L$, since every word belongs to one of two classes. If a word is of even length, it belongs to class $\left[\epsilon\right]_{\equiv_{L}}$; otherwise, it belongs to class $\left[a\right]_{\equiv_{L}}$.

Hence, there are two equivalence classes of $L$ in total. That is, the number of equivalence classes of $L$ is finite. According to the Nerode-Myhill theorem, $L$ must be regular.

  I think that showing that there is a surjective mapping is not sufficient, because the image may still be of infinite size.

I am not sure which surjective mapping you are talking about.

As you can see from the example above, it is enough to show that the union of the finitely many equivalence classes you have found contains all words. Why? If we have another equivalence class $E,$ let $w\in E$. Then $w$ must belong to $F$, one of the equivalence classes you have found. Since $E$ and $F$ share one word, they are the same equivalence class. That is, $E$ has been found.

You may want to check a few related questions and answers such as finding separating words (Nerode) and how I can find all equivalence classes by Myhill-Nerode?.


Extract Max for a max-heap in $\log n + \log\log n$ comparisons

Explanation for log n + log log n comparisons:

1) First, remove the max element from the heap, leaving a hole at the root.

2) Next, remove the last element of the heap (at the bottom right), and hold it in a temp.

3) Reconstruct the heap by iteratively replacing the hole with the greater of its 2 children.  This loop takes log n comparisons (comparing the children at each level of the tree).  Here is an example implementation:

p = root;
while (p->left != NULL) {
    if (p->right == NULL || p->left->val > p->right->val) {
        p->val = p->left->val;
        p = p->left;
    } else {
        p->val = p->right->val;
        p = p->right;
    }
}

4) Now, you have a hole at the bottom of the heap, and you have an element that you removed in step #2.  Insert the element into the hole.  This element needs to be fixed because it could be greater than its parent.

5) Fix the heap in log log n time.  Where you inserted the element, if you take all of its parents, it forms a sorted list of log n elements.  You can do a binary search to find the correct position of the inserted element in this list of parents.  This takes log log n comparisons (binary search in a log n list).  Once you find the position, you can insert the element in the correct place, moving the rest of the elements down.

Total number of comparisons: log n (step 3) + log log n (step 5)


Proof that a quantum computer is equivalent to some logical circuit

It's not a valid proof (yet) because you haven't described how you plan to do step 3.  You also haven't described how you plan to deal with superpositions of states.


A B-Tree is a type of dictionary, no more and no less. It can be used to implement a set (e.g. see the interface for java.util.Set for the sort of operations we're talking about), but is most commonly used to implement a map (ditto for java.util.Map). So let's just look at maps for a moment.

If you think about a linguistic dictionary, it's ordered by "word", and associated with each word is a definition. You look up a word, and get a definition.

So the context of a map data structure is that you have keys ("words") and you want to map this to values ("definitions").

B-trees are like other kinds of search tree (e.g. binary search trees) in that keys can be accessed in sorted order. This has an advantage for certain types of query. For example you can do range queries, say if you want to find all entries where the key is between two values (e.g. all words in the dictionary starting with "q").

The main advantage of B-trees over other kinds of search tree is that it is particularly efficient when represented on disk. B-trees are page-structured (meaning they can be implemented on top of fixed-size disk pages; this also avoids fragmentation), and have a wide ply, which minimises the number of disk accesses needed to perform a query.

A typical use in a database server is to implement indexes. An index is, once again, much like the index in a paper book. Some books have multiple indexes (e.g. there might be a general index and an index of names of people). Given a key, the index in a book returns a set of pages on where you can find references to whatever is indexed (be it a concept, name, or whatever).

A database index typically maps a key to a set of database records. In a typical organisation, there is one data structure in which records are stored, and multiple indexes which map keys to record identifiers. To find records, you query the index, which gives you a collection of record identifiers. Then you can use those record identifiers to find the records in the store.

A typical use in a modern filesystem is to implement directories ("folders" if you're more used to GUIs). A directory is, logically, a map from names (file names or directory names) to filesystem objects. A filesystem object may be a file, or another directory, or what have you.

As has been pointed out elsewhere, you might want to do some reading on this. Any "introduction to databases" textbook will probably do.


Turing machine - infinite tape - does that thing exist?

The tape is not infinite. It is unbounded.
There is an important difference.
We don't need infinite memory.
We only need to be able to add more memory over time as needed.
This is actually pretty close to what people do in practice.
When a program needs more memory it asks the operating system and
receives more memory.
If we see that a computer is short on memory we increase its memory.
It is becoming even easier with cloud computing.
So the assumption is not that the machine has infinite memory.
The assumption is that we can increase the memory as needed.

If your question is about the limit where
the needed memory reaches the limit of information
that can be stored in the universe
(assuming that it is finite and bounded by some fixed number)
then yes, we will not be able to add any more memory at that point.
In fact, if you assume that
the amount of information is bounded by a fixed number
then the world is a finite state machine.
However that is not the usual case.

However if you try to design programs as finite state machines
you are going to have a very difficult time
because the number of states is huge.
The number of states for a Turing machine with $m$ bits of memory
would be something like $2^m$.
Turing machines (and other similar models)
simplify things.
This is a rather common thing in sciences.
It is important to know the limits of a model but
the fact that a model is not a completely accurate representation of the world
doesn't imply it is useless.


Base cases: $T(0) = T(1) = a, T(2) = b$. How did we get these base cases? Well, from the code:

if len(lst) <= 1:
    return

This tells us that for n < 2, T doesn't depend on the input list size; hence, the function takes some constant amount of time for these input sizes.

if lst[0] > lst[-1]:
    ...

if len(lst) >= 3:
    ...

This part tells us that for input sizes between 1 and 3, exclusive (i.e., for 2) we do some more work than in the n <= 1 case but not as much as in the n >= 3 case. THe amount of work done still doesn't depend on the input size, so it's constant, but it might be difference from that of the n <= 1 case.

Now we consider the n >= 3 case.

Recursive part: $T(n) = 3T(\frac{2}{3}n) + c$. Notice that the three recursive calls each use a list two thirds the size of the input list. To see this, let's consider the code:

if len(list) >= 3:
    split = len(lst) // 3
    do_something(lst[0..len(lst) - split - 1])
    do_something(lst[split..len(lst) - 1]
    do_something(lst[0..len(lst) - split - 1])

First off, we see that split will be equal to one third the length of the input list, rounded down (we assume // means integer division). We then have three recursive function invocations. To get the input size for these recursive calls, we have to see how big the lists we're passing are. All three are slices of the original input list; we can determine the size of the lists being passed to recursive calls by computing the indices used to determine slices. Observations:

The first and third slices use the same indices.
0 .. len(lst) - 1 is the entire list, size n.
split is one third the list size, equal to n/3.
The second slice uses split .. len(lst) - 1; to get the size of this slice, we can use simple subtraction of the size of the smaller interval (0..split) from the bigger interval (0..len(lst) - 1): n - n/3 = 2/3 n.
The first and third slices work similarly: if we take a slice of size n and stop it n/3 indices earlier, we get n - n/3 = 2/3 n.

Now that you have a recurrence relation, you can resolve it using any of a several of techniques.


How to get the optimized quicksort algorithm's time complexity

The height of tree is not $log(\frac{k}{n})$ which is negative because $k<n$. We stop expanding the tree when we reach $k$, therefore we reduce the height of the original tree by $log(k)$. So the height is $log(n)-log(k)=log(\frac{n}{k})$ and the average running time will be: $$c_1nlog(\frac{n}{k})+c_2nk=c_1nlogn-c_1nlogk+c_2nk$$
As noted in comments, since $k$ is constant, that is equivalent to $\theta(nlogn)$.

EDIT: I just noted that the problem was about average case complexity and you assumed the partition to have 1:1 ratio, which is the assumption for best case scenario.
For average case analysis, we shouldn't consider any fixed partition ratio.

You can use the average case analysis in section 7.4.2 of CLRS book; except that here the probability of comparing the ith and jth element would be at most $\frac{1}{j-i+1}$, so the $c_1nlogn$ would be an upper bound on the Quicksort part of the average case. As for Insertion sort part, there would be at most $n/k$ leaves with size $k$, with total cost of $\frac{n}{k}c_2k^2=c_2nk$.


Complexity of dynamic card game algorithm

As pointed out in the comments, your recurrence is wrong (though equivalent for $b=r$; it's a recurrence for $E(b,r)+b-r$). Also, you can solve this efficiently using memoization or its more principled cousin, dynamic programming. The dynamic programming solution calculates iteratively $E(i,j)$ for $i+j=0,1,\ldots,52$.

Finally, to answer your question, if you implement you original solution, you get a running time satisfying the recurrence
$$
T(b,r) = C + T(b-1,r) + T(b,r-1),
$$
with initial conditions $T(b,0) = O(1)$, $T(0,r) = O(1)$. If $T'(b,r) = T(b,r)-C$ then
$$
T'(b,r) = T'(b-1,r) + T'(b,r-1),
$$
a recurrence solved by $\alpha \binom{b+r}{r}$. Taking the initial conditions into account, we get that
$$
T(b,r) = \Theta\left(\binom{b+r}{r}\right).
$$
In particular,
$$
T(n,n) = \Theta\left(\binom{2n}{n}\right) = \Theta\left(\frac{4^n}{\sqrt{n}}\right).
$$
(This assumes all arithmetic is $O(1)$. The running time is actually somewhat larger since the relevant numbers grow fast, but this is a (multiplicative) lower-order factor.)


How is the right, root, left order traversal called in a binary search tree?

As per wikipedia (Tree Traversal), it is called Out-order traversal

Though, you could also find reference to reverse in-order traversal, which means the same.


Why do we have different algorithm for MST when graphs are directed?

Your question was already asked before it seems, but got no explicit examples. I try to give these here.

First note the question only makes sense if we consider a node $u$, and there exist spanning trees starting with $u$. The algorithms of Prim and Kruskal make choices in a greedy way. Once the choice is made, it will not be reconsidered. We show how this choice will go wrong for certain example.

The left picture has two spanning trees, with weight $6+2$ and weight $6+4$. Starting with node $u$ Prim will consider the two edges $4$ and $6$ and choose the lightest one. Now, only one spanning tree remains, not the best one.

The right picture has three spanning trees, with weight $4+2$, weight $6+1$, and weight $6+4$. Kruskal will choose the lightest edge $1$. Now, only one spanning tree remains, not the best one.


A subgraph is isomorphic to a clique if, and only if, it is a clique.


How can $ww = www$ hold for any word $w$?

The only way that $w w = w w w$ is that $w = \epsilon$. Algebra of strings (for mathematician types, the free monoid on $\Sigma$) isn't that different from multiplication...


Formulating a linear program s.t. only extreme point solutions are found

Perturb the vector of the objective function slightly. If you got multiple optimal solutions than this vector is orthogonal to a facet $F$ of the polytope that defines the feasible area of the LP. Notice that $F$ could be an edge, but also a higher dimensional flat. By changing the objective function slightly you will get an extreme point that lies on the boundary of $F$.

You might want to check that the perturbation was small enough. So check the computed point with the original objective function, if it produces the optimum.


Can one use the PCP theorem to prove correctness of deternimistic algorithms?

The statement you state is not the PCP theorem. The PCP theorem is a characterization of NP.

The statement you mention is much easier to prove. It says in effect that a polytime algorithm that uses $O(\log n)$ random bits can be made deterministic while keeping it polytime (given reasonable completeness and soundness properties). The proof is very simple – we can run the algorithm over the $2^{O(\log n)} = n^{O(1)}$ many choices of random bits, check how many times the algorithm accepts, and so determine whether the input belongs to the language.

At most you can think of this as a derandomization procedure – if your algorithm uses only logarithmically many random bits, then you can make it deterministic by "exhaustive search".


A file size is measured in bits, you cannot have a portion of a bit, only a whole bit, it is a discrete quantity. Something is continuous if it can can have any possible value in a range, bounded or not. Something can be discrete and at the same time infinite.

The best way to think about discrete or continuous is if for any two values you can find a value between them then it is continuous, otherwise it is discrete.


Is it possible to solve the Mountain Car reinforcement learning task with linear Q-Learning using the state as direct input?

I just found out the answer and it's actually pretty simple: while there is a good linear policy for the mountain car task, the value function itself is non-linear.

The state space of this task is like a spiral, and there is no linear approximation possible even for a mediocre value function. If you increase the value for going right and reaching the top, going left will have the lowest values. This is why the car never reaches the top.

By applying a simple random projection and transforming the input space, it is possible to show that the task becomes linearly solvable (with a value-based method).


Upper (or lower) envelope of some linear functions

Suppose that we add $Mx$ to all your functions. This doesn't change the $x$-coordinate of your breakpoints (because $m_1 x + b_1 - m_2 x - b_2$ has the same sign as $(m_1 + M) x + b_1 - (m_2 + M) x - b_2$). Furthermore, for each breakpoint $x$, it just increases the value of the $y$-coordinate by $Mx$. This means that you can recover the original breakpoints, in linear time, given the breakpoints for the linear functions $(m_i + M)x + b_i$.

Now let $M = \max (-m_i)$, which can be found in linear time. The functions $(m_i + M)x + b_i$ all satisfy your condition. Hence if you could solve your problem in $f(n)$, then you could solve the original problem in $f(n) + O(n)$. Therefore you need not expect a more efficient solution for your special case.


Advice needed. NLP and ML. Where to start?

As far as I can see, your reading list lacks specific NLP introductions. A really good starting point is Dan Jurafsky and Chris Manning's Coursera course (for example here https://www.youtube.com/watch?v=nfoudtpBV68 ). This specifically covers spell checking in one of the first videos.

In general, spell checking is a rather easy task, while (convincing) text generation is a lot harder. Grammar checking should be easy in theory but I'm not sure about that. Concerning proofreading, I'm not completely sure what you mean by that. Does this extend over spell and grammar checking, in your point of view?

Artistic style transfer is possible although I'm not sure what the current state of the art. You could be more luckily diving into stylometry (https://en.wikipedia.org/wiki/Stylometry) there.

A really good NLP text book to start with is Jurafsky and Martin: Speech and Language Processing (specifically covering generation). 1st edition is publicly available as pdf (just google). But there is also a 2nd edition and they are currently working on a 3rd (the chapters they are done writing are freely available as well).


Finding $L^*$ when $L=\{a^nb^n | n \geq 1\}$

$L^2 = LL = \{uv | u,v\in L\}$. In words, $L^2$ is a set of all strings that formed by concatenation of all strings from $L$. For instance, if $u=a^kb^k \in L$ and $v=a^tb^t \in L$ then $uv = a^kb^ka^tb^t$. That's why $L^2 =\{ a^{n_1}b^{n_1}a^{n_2}b^{n_2}\}$ for all $n_1, n_2 \geq 1$.
Similarly $L^3, L^4,\dots$

Example with a finite set: $L=\{ab, cd\}$. Then $L^2 = \{abab, abcd, cdab, cdcd\}$.


Writing the coherence conditions for a monad in a functional laguage

First off, you've confused $\nu$ and $\eta$ in your class. I'm going to go with $\eta$.

The coherency law:

$$\mu \circ T \eta = \mu \circ \eta T = 1_T$$

translates to:

mu . fun eta = mu . eta = id

And the other coherency law:

$$\mu \circ T\mu = \mu \circ \mu T$$

translates to:

mu . fmap mu = mu . mu

Intuitively, the reason why the $T$ "disappears" when translating $\mu T$ to mu is the same reason why it "disappears" when translating $1_T$ into id: in Haskell, types are passed implicitly. If you translate this into System $F_\omega$ (or GHC Core!) the types are passed explicitly and the correspondence is more obvious. I'm going to leave you that one as an exercise.

One more thing. Don't forget the other conditions on mu and eta: they have to be natural transformations! The coherency conditions in category theory are:

$$\forall f : X \rightarrow Y, \eta_Y \circ f = T(f) \circ \eta_X$$
$$\forall f : X \rightarrow Y, \nu_Y \circ T^2(f) = T(f) \circ \nu_X$$

In Haskell:

∀ f, eta . f = fun f . eta
∀ f, nu . fun (fun f) = fun f . nu

In category theory, you might need to prove these, but in Haskell you don't because they are the free theorems for those functions. This is a very nice property of Haskell: Ignoring bottom values and general recursion, any function with the type of a natural transformation must be a natural transformation.

(This is also a good piece of intuition as to what is so "natural" about natural transformations. It means that the "forall" in a polymorphic type is a real "forall"; it's true for any type with no exceptions.)


Finding a fixed-size set whose members are contained by the largest number of other sets

I believe your problem is a direct instance of the NP-hard Maximum Coverage Problem, which is related to Set Cover.

From wikipedia, Maximum Coverage Problem:

  As input you are given several sets and a number k. The sets may have some elements in common. You must select at most k  of these sets such that the maximum number of elements are covered, i.e. the union of the selected sets has maximal size.

So, in your case, there is a set for each language with cardinality equal to the number of students speaking that language. The input is the number N of maximum number of translations.


Simple examples of Artificial Intelligence

Artificial Intelligence is a catch-all term for a large collection of everything from philosophical questions down to very specific programming techniques.

At heart, AI comes from the question is it possible to build a machine that displays intelligent behavior to the same level as human beings? This is often clarified with examples like, can we build a machine that plays chess, composes a sonnet, tells a joke or recognizes kittens. Investigating this question has led to the distinctions between strong and weak AI, and thought-experiments like the Turing test and the Chinese room.

On the more practical side, there is a collection of techniques that are being used to (partially) solve some of these problems. For instance, we can build a machine that beats any human at chess or checkers. Computers can recognize objects in images with reasonable accuracy. They can diagnose diseases, sometimes better than doctors, they can parse a sentence into its constituents and make a reasonable mapping to the meaning behind it.

Many of these algorithms and techniques use probability, linear algebra, logic and a variety of other subjects, but that's just a matter of using what works. There are plenty of systems that use linear algebra that have nothing to do with AI. What makes a technique AI is that, in some sense, it attempts to behave intelligently.

A precise definition beyond that is difficult to give. The trouble with defining AI is that it's the study of something that doesn't exist yet, and we don't know that it ever will. But we're pretty sure that we'll know it if we see it.


If a term has a normal form then there is a sequence of $\beta$-reductions leading to it. However, $\Omega$ has only one $\beta$-redex, which leads back to $\Omega$. Therefore, because $\Omega$ is not already in normal form it has no normal form.

It is easy to generate other terms that have only infinite chains of reductions. For instance, the related $Y$ combinator $Y = \lambda f . (\lambda x . (f (x x)) (\lambda x . (f (x x))$ gives
$$Y \to \lambda f . f Y \to \lambda f . f(f Y) \to \lambda f . f(f(f Y)) \to \cdots$$
Note that by applying $Y$ to a specific $f$ we may get a normalizing term (because for a specific $f$ there will be additional reductions that may lead to a normal form). In fact, $Y$ is quite useful because for any term $g$ we have $Y g = g (Y g)$, so $Y$ computes fixed points.


Why we can't have some algorithm to be polynomial if there are generic conditions that make them so?

It's often the case that an NP-complete problem has some parameter $b$ that when fixed to a small constant makes an polynomial algorithm possible, yes.
However in fixing $b$ that problem (at least as of writing when $P =^? NP$) loses its completeness. That means when we want to do a reduction we (for at least some instances) need this parameter to be bigger than $b$.


How does the problem of having a coffee-machine close relate to vertex cover?

As I already pointed out in my comment, there is in fact a need for a transformation of the problem. The problem you ask for is not known as vertex cover, but as dominating set.
The proof then goes as follows:

We transform an instance of vertex cover $(V, E, k)$ as follows (we assume that the graph $(V,E)$ is connected). For every edge - just as the hint says - add two edges and one vertex. More precisely, for an edge $uv \in E$, add a new node $w \not\in V$ and edges $vw, wu$ to the graph. The resulting graph constitutes an instance of Coffee in the obvious way, that is, the "close-enough"-relation is represented by edges and the meeting rooms are represented by vertices. Let $(V', E', k)$ denote the instance of coffee produced by the transformation.

We now need to show now that $(V, E)$ has a vertex cover of size $\leq k$ if and only if for $(V', E')$ it suffices to use $\leq k$ coffee machines.

"$\Rightarrow$": Let $v_1, \ldots, v_l, l \leq k$ be a vertex cover of $(V,E)$. It is clear that the same choice of nodes produces a valid choice for coffee machine placement on $(V', E')$, as we assumed $(V, E)$ to be connected.

"$\Leftarrow$": Let $v_1, \ldots, v_l, l \leq k$ be a valid choice for coffee machine placement. WLOG, assume that $\forall i \in \{1, \ldots, l\}: v_i \in V$, for if $v_s \in V' - V$ with $1 \leq s \leq l$, we can obtain another valid choice for coffee machine placement by replacing $v_s$ with $v \in V$ such that $vv_s \in E' - E$, that is, with one of the two nodes "between" which $v_s$ was inserted by the transformation. Note that these two nodes were also precisely the ones that were covered by choosing $v_s$ to have a coffee machine. By construction, there must have been an edge between the two nodes and an edge between $v_s$ and each of the two nodes. So by replacing $v_s$ with one of them, we don't shrink the set of covered nodes.
Then, $v_1, \ldots, v_l$ constitutes a vertex cover of $(V, E)$. To show this, let $uv \in E$. By construction, there is $w \in V' - V$ and $uw, wv \in E' - E$, and no other edges are incident to $w$. As $(V', E')$ covers $w$, one of $u$ or $v$ need must have been chosen as places for a coffee machine, and thus, $uv$ is incident to at least one node in $\{v_1, \ldots, v_l\}$. Thus, $v_1, \ldots, v_l$ is a vertex cover of size $l \leq k$.


Big O Notation Simplification in the fraction form

It is indeed confusing if you are expecting some kind of simpler form.

However, ${n^3}/{\log^{3}n}$ is already in the simplest form in term of big-$\Theta$ notation. Consequently, it is also sort of the best form in term of big-$\Omega$ notation or big-$O$ notation. It is certainly true that $n^3/\log^3n = O(n^3)$. However, that kind of big-$O$ bound are usually frowned upon since it is obviously not tight, $n^3/\log^3n = o(n^3)$. In fact, in a similar vein, many time-complexities is described by $\Theta(n\log n)$, $O(n\log n)$ or $\Omega(n\log n)$, where the factor $\log n$ cannot be or is not removed.

The point is that although you can ignore the asymptotically insignificant terms in a sum to arrive at a simpler big-$O$ (or big-$\Theta$, big-$\Omega$) bound, you cannot do away with any unbounded factors without losing significant asymptotical information. For example, it is correct that $n^3+\log^{3}n=O(n^3)$ or $n^3+\log^{3}n=\Omega(n^3)$ or $n^3+\log^{3}n=\Theta(n^3)$, but neither $n^3/\log^{3}n=\Omega(n^3)$ nor $n^3\log^{3}n=O(n^3)$ is correct.

If you want to compare $n^3/\log^3n$ with $(2^{n})^{0.008}$, you can proceed as the following.
$$\text{Since } n^3/\log^3n = O(n^3) \text { and } n^3=o((2^{0.008})^n), \text{ so } n^3/\log^3n =o((2^{0.008})^n)$$
where the second equality comes from the fact $2^{0.008}>1$ and the fact that any polynomial function grows slower than any increasing exponential function, which is proven in another answer of mine. Please note that I am using the little $o$-notation, which means basically "asymptotically growing slower than".

If you want to compare $n^3/\log^3n$ with $2^{n^{0.008}}$, you can proceed as the following.
$$\text{Since } n^3/\log^3n = O(n^3) \text { and } n^3=2^{3\log_2n} = o\left(2^{(n^{0.008})}\right), \text{ so } n^3/\log^3n =o\left(2^{n^{0.008}}\right)$$
where the second equality comes from the fact $\log_2n=o(n^{0.008})$, which is also proven in that answer of mine since $\log_2n=(\log_2e)\log n$.

You can check the reference question and answers on sorting functions for good advices and more detailed and systematic treatment.


Converting If-else condition to Linear Programming

This can be expressed with just the equation $X=Y$.  Since $X,Y$ are zero-or-one variables, the only possible assignments that are consistent with your condition are $X=Y=0$ and $X=Y=1$.

See Express boolean logic operations in zero-one integer linear programming (ILP) for many more boolean conditions and how to express them as linear inequalities.