How do you proceed if your milp is not solvable

It's hard to specify one approach because it depends on your needs. From my experience I can suggest the following:

Precision

Typical solvers report solutions as "optimal" using gap parameters specifying relative and absolute differences. Take this CPLEX parameter as an example: https://www.ibm.com/support/knowledgecenter/SSSA5P_12.8.0/ilog.odms.cplex.help/CPLEX/Parameters/topics/EpGap.html

You can use this in two ways:

Sanity tests

If you don't know if your problem is solvable in practice, i.e., constraints are not contradictory in a non-obvious way, just set the precision to lowest possible value and try to solve the problem. The solver should just find anything meeting the constraints practically ignoring the cost function.

Next, when you know that the problem is solvable, you can tighten the constraints. In your example you mention the number of people, first you can start with $x+10$ and if it works you then decrease it to $x+5$ and so on. By doing so you can easily estimate which set of parameters and constraints you can further optimize.

Practical precision

The question is whether you need the highest possible precision or maybe you can bend the rules and consider using less "optimal" solution. This can highly speed up the calculations, i.e., in my problems I was able to find the solution in seconds instead of hours by switching gap from $0.0001$ to $0.01$ in Gurobi.

Hard constraints and soft constraints

Common approach is to change some of the constraints to constraints with penalty. For instance, instead of saying that $x < 10$ you say that $x - p < 10$ where $p \ge 0$. Next, you add $p$ to your cost function with big negative multiplier. Such a variable splitting can help finding solutions in case of infeasibility, what's more, if you report the solutions during calculations you can use them to get better approximations of the constraints you can drop to get better results. It looks like this is something you already considered and this is a common approach.

Presolve

Depending on the type of your problem, you may be able to divide it into multiple phases and calculate the solutions in parallel. Using this method with "sanity tests" method mentioned above you can still have some solution in case when your most wanted model is not feasible.

Example: if you are optimizing for two "realms" (like number of people and number of tasks), try to set some value manually and optimize the other value for that case. By doing this you make the model much easier so you can calculate multiple of them.

Simplify the model

It sounds easy but in fact can be very hard. Make sure that you don't perform unnecessary difficult operations (like calculating GCD or multiplying variables). Look for easier formulations including constraints moved to cost function (i.e, instead of calculating the minimum of a set and them maximizing it with the cost function, use min-max trick). Make sure that you have smallest possible domains (especially for so-called "big $M$" variables). Also, check your floating point precision.

Just deal with it

Sometimes you just can't mitigate it, after all it might not be solvable in any acceptable time. You can consider calculating different problem (i.e., completely different approach) or use different algorithm at all (neural nets, simulated annealing etc).


Grammar of words with exactly $k$ prefixes in another grammar

Unfortunately there is no such construction, as the context-free languages are not closed under this operation.

Consider the language $\{ a^nb^n \mid n\ge 1\} \cup \{ a^kb^nc^n \mid k,n\ge 1 \}$.

The language that has two prefixes in this language is $\{ a^nb^nc^n \mid n\ge 1\}\cdot \{a,b,c\}^*$, which is not context-free.


Was there an attempt to make reusable regular expressions?

Lex, the lexical analyser generator, supports this notation. In the "definitions" section, you can define patterns which you can then use in the "rules" section:

DIGIT    [0-9]

%%

{DIGIT}+"."{DIGIT}*  { return T_FNUM; }

Most lexer generators have something similar; ANTLR has "fragments", for example.


Complexities of basic operations of searching and sorting algorithms

For general algorithm of bubble sort worst case comparisons are $\Theta(n^2)$ But for special case algorithm where in you add a flag to indicate that there has been a swap in previous pass. If there were no swaps then we come out of the loop since array is already sorted. In this case comparisons are $n$ not 0.

For Quick sort you have mentioned that worst case swaps are $n^2$. Well worst case scenario for quick sort is when all elements are in sorted order thus there won't be any swaps so it should be zero.


Turing machine with k-tape, tape of output

There is no generally accepted definition of Turing machine. Various authors use various models. One author's definition might specify the output tape, another's might leave the choice to the Turing machine designer.

The reason that we don't care about this "calling convention" is that it doesn't matter from the point of view of computability (and, to a large extent, from the point of view of complexity). All of the different variants of Turing machine are Turing-equivalent; the languages they decide are the computable languages, and the languages they recognize are the recursively enumerable languages.

If you're writing a paper, the choice of which model to use is up to you. But this hardly ever comes up, since Turing machines are usually described very informally. The informal description can be implemented in any reasonable variant of the Turing machine model.


Is there a relation between the size of the domain/range of a function and its computability?

(Note: As mentioned by Apass.Jack in the comments, there are apparently two different usages of the terms "domain" and "range". In this answer, I adopt the usages which I am more familiar with. That is, given a function $f\colon X \to Y$ (i.e., $f \subseteq X \times Y$), $X$ is the domain of $f$ in the sense that $f(x)$ is defined for all $x \in X$; similarly, the range (or codomain) $Y$ is a set such that $f(x) \in Y$ for all $x \in X$. Additionally, every function is total; partial functions are explicitly denoted as such.)

Let $f\colon X \to Y$ be a function. The question is: What can we say about the computability of $f$ (strictly) based on $|X|$ and $|Y|$? The following is more or less a structured breakdown of what I have written in the comments:

Domain

Case 1: $|X|$ is finite. Then the values $f(x)$ of $x \in X$ may be hardcoded (e.g., as a lookup table) in an algorithm to compute $f$.
Case 2: $|X|$ is infinite. There are plenty of both computable and uncomputable functions in this case.

Range

If $Y$ is such that the image $\text{im}(f) = \{ f(x) \mid x \in X \}$ of $f$ is a proper subset of $Y$, then there is not much that can be said about $f$ (e.g., $Y$ could be an infinite set but $f = \{ \}$ the empty function; see Case 1 below). Thus, let us assume $\text{im}(f) = Y$ holds.

Case 1: $|Y| = 0$. Then $f$ must be the empty function $\{ \}$, which indicates $|X| = 0$; see "Domain", Case 1.
Case 2: $|Y| = 1$. $f$ is computable by an algorithm which ignores its input and outputs the only possible value for $f$.
Case 3: $|Y| \ge 2$ but $|Y|$ finite. An example of an uncomputable $f$ is, for instance, the membership relation for the halting problem (as mentioned in the question) or any non-recursive (i.e., undecidable) language; similarly, a computable $f$ would be the membership relation for a recursive (i.e., decidable) language.
Case 4: $|Y|$ infinite. As in case 3, there are both computable and uncomputable choices for $f$. For example, $X = Y$ and $f = \text{Id}_X$ is trivially computable. An uncomputable example for $f$ (off the top of my head) would be the busy beaver function.

It is possible to extend these results if further assumptions are made about $X$, $Y$, and $f$. In the general case, however, this is as much (and it is not much, I know) we can say about the computability of $f$.

If we are dealing with a partial function $f \subseteq X \times Y$ instead, note there is always a (maximal) $X' \subseteq X$ such that $f \subseteq X' \times Y$ is a (total) function $X' \to Y$. As pointed out by chi in the comments, it might be tempting to say we may simply generalize the above discussion by considering the total restriction of $f$ instead. This does not work, however, since, for example, the partial function $f \subseteq \mathbb{N}_0 \times \{ 1 \}$ with $f(x) = 1$ if and only if TM number $x$ does not halt is not computable, despite its image having a single element (cnf. "Range", Case 2). Nevertheless, note this is the only case in which the generalization fails.


Is there any scenario whereby randomly shufflying a sequence improves it's compressibility?

I now think that it's because of this:-

  ZPAQ has 5 compression levels from fast to best. At all but the best level, it uses the statistics of the order-1 prediction table used for deduplication to test whether the input appears random. If so, it is stored without compression as a speed optimization.

... from https://en.wikipedia.org/wiki/ZPAQ#Compression

I'm referring to LZMA in my question, but I'm not familiar with how it's implemented in code. If it followed the same speed optimisation strategy as ZPAQ, the hypothesis would be consistent with my observations. You can imagine in edge cases where $ \frac{\text{size compressed shuffled}} {\text{size compressed original}} = 1 - \epsilon $, that an $n$ order predictor decides that there is insufficient advantage to be had due to the necessary compression encoding overhead. My $\alpha \approx 0.01$, but recently I've seen it as high as 0.04.


What sort of algorithm/communication model/data structure do collaborative real time editors use?

The usual approach is operational transformation. The wikipedia page seems to be pretty good. Here are some other references:

Understanding and Applying Operational Transformation
Operational Transformation: An Introduction
OT FAQ
ShareJS - javascript library implementing OT

Here's a paper on a different approach: Real time group editors without operational transformation. (Note: I haven't actually read it, so can't speak to how good it is)


Prove Partition is NP-Complete using that SubsetSum so is it

Define your $\rm P{\small ARTITION}(S, K)$ problem as:

"Are there partitions $S_1, S_2$ of $S$ such that $|\text{sum}(S_1) - \text{sum}(S_2)| \leq K$, where $\text{sum}(S_i)$ is the sum of all elements of $S_i$?".

Then $\rm P {\small ARTITION}(S, 0)$ would mean $|\text{sum}(S_1) - \text{sum}(S_2)| \leq 0$ which is true only if $\text{sum}(S_1) = \text{sum}(S_2)$. Thus, given $S$ we could reduce the $\rm S{\small UBSET}(S,k)$ problem to the problem asking for existence of two partitions of $S$ with equal sums of elements---$\rm P{\small ARTITION}(S, 0)$.

The reduction to the latter can be done as following:
Let $s=\text{sum(S)}$ and define a new set $S_{new} = S \cup \{2k − s\}$. We choose $2k-s$ since the sum of $S_{new}$ is $2k-s+s = 2k = k+k$, and we want two partitions with equal sizes equal to $k$.

Now call (reduction!) $\rm P{\small ARTITION}(S_{new},0)$. If it returns YES/TRUE then $S_{new}$ can be partitioned into two sets $S_1$ and $S_2$ with sums equal to $k$. Also notice that either $S_1$ or $S_2$ can contain the new element $2k − s$ (since they are partitions) meaning that either $S_1$ or $S_2$ is a subset of $S$. Thus we have a subset (without the element $2k − s$) of $S$ with the sum $k$, and we return YES/TRUE. Otherwise, if we get NO/FALSE then return NO/FALSE.


You need to determine at what time each job is completed. With a first-come-first-served scheduler, this is simple to calculate: each job starts as soon as the processor becomes free, and takes exactly its burst time to complete. You've already calculated the start and end times to calculate the wait times, so use that to obtain the turnaround time.

For example, A arrives at time 0. The processor is free, so it starts at time 0 and ends at time 6. Then the processor runs B, which had to wait for 5 units, and finishes at time 8, for a turnaround time of 7.

The answer from the book seems to be totaling the completion times, without regard for the arrival time. This is not something I recognize as “turnaround time”.


The Least-Recently Used (LRU) is a very common algorithm for page replacement, especially in system softwares that are exposed to data access of temporal locality.


Does strong typing contribute to better performance optimization by compiler?

I think your friend somewhat presents a false dichotomy.
I will just give one example: when it first came out, the Self VM was one of the fastest dynamic language implementations. In fact, the Smalltalk VM written in Self that shipped as part of the Self system was one of the fastest Smalltalk VMs of its time, despite being written in a dynamic language (much more dynamic than Smalltalk, Python, or Ruby) and running on top of another VM.
Even more, at the time it was first released, Self was one of the fastest OO language implementations in general, even competing with some C++ compilers of that time.
However, it achieved this performance precisely because of its aggressively optimizing JIT compiler aided by dynamic type inference and type feedback!
It is precisely because JIT compilers have more and better type information than AOT compilers that JIT-compiled language implementations can be so fast.
A JIT compiler can potentially have all the same information available that an AOT compiler has. But, a JIT compiler also has runtime information that an AOT compiler cannot possibly have because of all our favorite impossibility results such as the Halting Problem, Rice's Theorem, etc.
For example, Escape Analysis is equivalent to solving the Halting Problem. So, an AOT compiler cannot know in every circumstance whether a reference will escape the local scope or not, and thus must conservatively allocate it under the assumption that it will escape. A JIT compiler, however, can simply assume that the reference will never escape and compile the code accordingly, and then when it observes the reference escaping at runtime, it recompiles the code. (This is sometimes called Escape Detection.)
Likewise, Class Hierarchy Analysis is equivalent to solving the Halting Problem (in languages with dynamic code loading at least). So, an AOT compiler is limited in its ability to de-virtualize and thus inline potentially overridden methods. A JIT compiler, however, can simply look at the class hierarchy at runtime and see whether the method is overridden or not, and thus potentially inline it. And if it observes a piece of code loaded later that overrides the method after the fact, it can re-compile the code so that the method is no longer inlined but dynamically dispatched again.
So, yes, type information is helpful, and JIT compilers do use type information in their optimizations, including type information empirically collected at runtime that is not available to AOT compilers.
Your friend even uses an example of using type information in their own example! Modern ECMAScript execution engines indeed use type information about numeric values collected at runtime to optimize them even though semantically ECMAScript only has IEEE Std 754-2019 binary64 as its one and only numeric type. (The recently added bigint is a distinct type with distinct numeric literals.) Typically, modern ECMAScript execution engines will segregate numeric values into at least doubles and 53 bit integers, possibly even more.
Similarly, they will detect the type of arrays and represent them as machine arrays (i.e. contiguous pieces of memory) even though semantically, an array is actually just a dictionary whose keys are the strings "0", "1", "2", etc.
The two key differences between an AOT compiler and a JIT compiler are:

The JIT compiler has more information available: it can theoretically gather all the same static information that an AOT compiler can, but it also has runtime information available that the AOT compiler cannot possibly have.
On the flip side, the AOT compiler has "infinite" resources available (it can take as long to compile and use as much RAM as it wants), whereas the JIT compiler is competing with the user program for the same resources while the user is waiting for their program to start.

However, the kinds of information and the kinds of optimizations are mostly the same for both. Both like long stretches of straight-line code, both like type information, etc.
Personally, I believe that the best possible performance will come from an approach that has not yet been heavily explored commercially: use an AOT compiler to crunch out as much static information as possible, and perform heavy and expensive optimizations, but keep all that information around and keep a rich representation of the program. Then, hand this off to a JIT compiler which can use all of the expensively calculated information and the rich representation to even further optimize at runtime.
Real world systems typically work differently. For example, C++ compilers are highly sophisticated, by they typically produce very low-level "anemic" output such as x86 machine code which has no types and loses almost all of the information and intent of the original program. On the other hand, we have typical Java implementations which have sophisticated JIT compilers but very stupid practically non-optimizing AOT compilers.


Is my formal definition of programming language correct?

It is certainly not a full definition; one might reasonably expect a "real" programming language to have not merely an abstract mathematical model defining the language's semantics, but also a concrete implementation of a compiler or an interpreter which runs on an actual computer. Then again, one might reasonably not expect this. Is lambda calculus, for example, a programming language? Wikipedia doesn't define it as one, but if somebody else does then I can't say they are wrong.

There are many aspects of what makes a language a "programming language"; reasonable people might disagree on whether a certain aspect (say, Turing completeness) is strictly necessary for something to count as a true programming language. It is unlikely that any list of such aspects would ever be agreed by all computer scientists, or even just the academic computer science community, to be both correct and complete.

The concept of a "programming language" is not in the same category as mathematical concepts such as "group". It is possible for a formal definition of a group to be correct or incorrect, but a formal definition of a programming language can merely be useful or not useful (or, more useful or less useful) relative to the use at hand. Presumably, the definition you quoted was useful for the author of the paper you found it in.


Does an algorithm exist for scheduling jobs on two processors?

The algorithms for $n$ processors will do the job just fine for the 2-processor case. In this context, $n$ does not refer to the number of tasks to be scheduled, which probably caused the confusion when you looked for algorithms.

Then, there is a great website for searching for scheduling problems, which you can access at http://www-desir.lip6.fr/~durrc/query/ -- You select the properties of your problem and will receive an overview of known results. Your case is called $P2 \mid r_j \mid C_\mathit{max}$ on that page. This is not quite your setting, as this assumes that the finishing times are the same for all tasks. But even in this slightly easier case, the web page gives you a reference for an NP-completeness proof for your problem:

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

So your algorithm will probably not yield a feasible schedule whenever there exists one.


Find the shortest path that goes through an even number of red edges

Here's a nice way to do it. Make two copies of the input graph; call them $A$ and $B$. Now redirect the red edges so that they jump across to the other copy, but leave the blue edges untouched. Any path which starts and ends in $A$ must use an even number of red edges (after using a red edge to get to $B$, it has to use another red edge to get back to $A$). So just run any shortest-paths algorithm on this new "doubled" graph and keep only the shortest paths that both start and end in $A$.

More formally, let $v_A$ and $v_B$ be the two copies of $v$ that appear in $A$ and $B$, respectively. For each original edge $(u,v)$,

if $(u,v)$ is blue, the new graph will have edges $(u_A, v_A)$ and $(u_B, v_B)$.
if $(u,v)$ is red, the new graph will have edges $(u_A, v_B)$ and $(u_B, v_A)$.

Note that this transformation only works because the edge weights are positive. Otherwise you could do funky things like traverse a negative edge twice (once within $A$ and once within $B$) to achieve lighter paths in the doubled graph.


Do Kruskal's and Prim's algorithms yield the same minimum spanning tree?

Found this which states that if all the conditions I mentioned above are met, a graph necessarily has a unique MST. Therefore, in terms of my question, Kruskal's and Prim's algorithms necessarily produce the same result.


Finding the maximum bandwidth along a single path in a network

A very simple approach for question 2 is the following. Sort the edges by capacity. Remove the edge with lowest capacity, and check if there is still a path from $s$ to $t$. If there is, move on the edge with the second lowest capacity, and so on.

At some point, we will disconnect $s$ from $t$ by removing an edge of capacity $c$. Now, we know that $c$ is the maximum capacity of a single path from $s$ to $t$.

This algorithm takes time $O(m^2)$, since the connectivity check can be made in time $O(m)$, and we can remove each edge at most once.

Now you can find the actual path (there might be many) of maximum capacity, by finding any $s$-$t$ path in this reduced graph.

When considering node-capacity, remember to change your graph to support that.


Why focusing on dags and not general directed graphs? I think you should have a look at the directed minimum spanning tree problem. The problem can be solved using the Chu-Liu/Edmonds algorithm. The wikipedia entry is not as clear as I was expecting, but it does have links to the original papers.


This is the problem of sampling from a multivariate distribution.

Simple method

In your case, there is a fairly simple method that will probably suffice.  First, randomly pick a value for $X_1$ according to the marginal distribution on $X_1$.  In other words, we define

$$g(x_1) = \int_{x_2=x_1}^{x_2=1} f(x_1,x_2) \; dx_2,$$

the probability density function for $x_1$, and sample $X_1$ according to $g$.  Since this is a univariate distribution, you already know how to do that (using the methods you described).  Here we have $g(x_1) = 1 + 2x_1 - 3 x_1^2$.

Second, randomly pick a value for $X_2$ according to the conditional distribution on $X_2$ given the value of $X_1$ picked earlier.  This has probability density

$$h_{x_1}(x_2)  = f(x_1,x_2)/g(x_1),$$

which is also a univariate distribution, so you already know how to sample from $X_2$ (once $X_1$ is fixed).

More general method

Alternatively, you can apply any of the general methods for sampling from a multivariate distribution.  They are probably shooting a fly with a cannon -- they're probably much more complex than what you need.  But if you want a relatively simple one, you could take a look at slice sampling.


There's another possibility: hypercomputation is not implementable in the real world, and is only an imaginary/theoretical concept.  If this is the case, then there is no contradiction with the Church-Turing thesis.

Of course, anyone can invent imaginary worlds where strange things are true.  For instance, there's the computer scientist's Superman: not only can he leap tall buildings in a single bound, he can also solve undecidable problems in his head!  I suppose one could imagine such a thing, but that doesn't mean it has any correspondence to the real world, and the possibility of imagining such a Superman doesn't contradict the Church-Turing thesis.  The study of hypercomputation can be thought of as asking, well, ok, so Superman might not be real, but what if he were?

The Church-Turing thesis is a hypothesis about the real world, so imaginary schemes that can't be implemented in the real world don't contradict it.


A real life system that faces and solves the dining philosophers problem

The dining philosopher's problem is a worst case scenario used to illustrate issues in algorithms. It's a test case. You probably won't find a static one-to-one mapping between it and a real world case.

However, similar situations can occur dynamically. If at any point the graph of actors waiting for resources forms a cycle, you are stuck in a deadlock. Most of the time this happens with n = 2 actors, but sometimes you can get more complicated deadlocks.


Efficiently pick a largest set of non-intersecting line segments

EDIT: Falk Hüffner gave a reduction in his comment to the question, the problem is in fact NP hard. What follows is pretty useless for that reason. I'll leave it up anyway so the answer doesn't look butchered.

This might be an NP-hard problem (as Teepeemm rightly pointed out, I did the reduction in the wrong direction, and I can't come up with one in the right direction), which would mean no one knows a subexponential algorithm. Brute force approach: check all sets whether some segments in them intersect, pick the largest one. This will cost you exponential time.

You can speed it up somewhat. Let n be the number of segments you have, then you can do a binary search like this: start out with checking whether there is a set with k1 := n/2 segments. If there is, check k2 := n*3/4, if there isn't, check k2 := n*1/4. Always remember all sets of the largest size for which you know that there exists something, because going up only supersets of those can work.

But to be completely honest, your best bet is to reduce this to SAT and use a SAT-solver. Anything you whip up yourself will pale in comparison to the finely tuned tools that SAT-solvers are nowadays. I don't know whether there is a SAT-solver you can easily use in Javascript though, you might have to use one on your server and let Javascript deal with the interpretation of results.
Another option would be to look into the algrithms mentioned on the sites that @MvG linked to in his comment to your question.


help understanding formal grammar for subtraction example

T = "0" | "1" means that if you want a T string, 0 or 1 will
do.

E = T "-" E | T means that if you want an E string, a T string
followed by - followed by an E string will do, or a lone T
string will do.

Thus, for example, 1 is a T string, and is thus also an E
string. Hence, 1-1 is an E string since it follows the T "-" E
pattern.

Note that the double quote is just a notational device to distinguish
terminal symbols from non-terminal ones.

Can you go on from here?


Determine what is the best order for running filters on a dataset

You can prove that the optimal ordering is according to ascending order of e(i)/f(i).

Proof:

Let r(i) = 1 - f(i).
The total cost of an ordering is: e(1) + e(2)*r(1) + e(3)*r(2)*r(1) + ... + e(N)*r(N-1)*...*r(1)

Now, assume that there's an optimal ordering that doesn't follow the rule above. It follows that there are two adjacent tasks t(i) and t(i+1) such that e(i)/(1-r(i)) > e(i+1)/(1-r(i+1)) => e(i)*(1-r(i+1)) > e(i+1)*(1-r(i))
swapping these two will change the value of only two expressions in the total cost expression, resulting in a delta of:

e(i) * r(i-1)*...*r(1) + e(i+1)*r(i)*...*r(1) -
e(i+1)*r(i-1)*...*r(1) + e(i)*r(i+1)*r(i-1)*...*r(1) =
r(i-1)*...*r(1)*[e(i) + e(i+1)*r(i) - e(i+1) - e(i)*r(i+1)] =
r(i-1)*...*r(1)*[e(i)*(1-r(i+1)) - e(i+1)*(1-r(i))] > 0

The delta is positive, meaning that the original configuration is more expensive than the outcome of the swap, therefore we have a contradiction.


How can you represent a Huffman-tree in Hex?

This practical problem comes up in JPEG, where you can define your own Huffman tables. The codewords are limited to 16 bits, and the table is stored as follows:

For $\ell=1,\ldots,16$, the number of codewords of length $\ell$ bits.
For each $\ell$, a list of the values encoded by the codewords of length $\ell$.

The codewords themselves need not be stored, since a Huffman code can be extracted from this description. See Imran Nazar's notes.


How do people measure performance overhead?

The meaning of overhead is usually an additional expense occurring in
addition to normal cost (whatever normal cost may be).

In the case of program, you may talk of overhead if it is run under
conditions such that it will cost more than it normally should, in
time or in memory usually, but it could be some other measure.

For example, at a time when compilers did not produce very good code,
compiled programs code size or execution time was compared with
programs handwritten in machine code. The quality of the compiler was
measured by the overhead of the generated code compared to a similar
program written in machine code. The overhead could be defined by the
ratio of the two costs, or by the percentage to be added.

An overhead of 20% in code size meant that the compiled programhad a
machine code version 20% larger than the hanwritten one. An overhead
of 20% in speed meant that the compiled program took 20% more time to
execute. An overhead of 20% in memory meant that the compiled program
required 20% more memory to execute.

Nowadays, compilers are quite good and this kind of overhead would
probably be negative.  Compilers make the better code.

In the case of a virtual machine, you can have a program that run
directly on the hardware, or runs under the control of a virtual
machine that hides (and protect) somewhat the hardware. Running on a
virtual machine will slow the program, and the variation in running
time is the overhead (extra time cost) caused by the virtual machine.
You just measure the time taken by the same program running in both
situations, and you determine the percentage of additional time
required when running in a virtual machine.  It may depend on the type
of application you use to test the overhead of the virtual machine.

Overhead is a measure of extra cost. It applies to devices or programs
or procedure that cause an extra cost (but usually provide an extra
servive).

You could also measure the time overhead incurred by your programs
when you reduce the available real memory.

Overhead is a way of comparing two related performances, intended to
achive the same result, separately measured.

Does this clarify things for you?


For all engineering purposes, you are right, if you choose a cryptographically strong hash function $H$.

For theoretical purposes, nope.  There's no proof.  Your argument is based on unproven assumptions, hence it can't be regarded as a proof that NC $\ne$ P.  In particular, we don't know of any hash function $H$ that we can prove is cryptographically strong, or that we can prove is inherently sequential when repeated like this. All of our hash functions are either heuristic (we think they are good but we have no ironclad proof) or are based on other assumptions (such as that factoring is hard; something we suspect but have no proof of).  And assuming that $H$ behaves like a random oracle is an unproven assumption.  So if you're a theorist and what you care about is proving that NC $\ne$ P, none of these count as a suitable proof.

Personally, I do consider them pretty good evidence that in all likelihood NC $\ne$ P... but it's not a proof.


Enumerate all solutions to integer programming problem

It's possible to enumerate all solutions, using a recursive algorithm that repeatedly invokes an integer programming solver.  Basically, at each step, you pick a variable, find its range of feasible values, partition its range into two subranges, and then recursively enumerate solutions that fall into each subrange.

In pseudocode, the algorithm looks like this ($\mathcal{P}$ is an integer programming instance):

EnumSolns($\mathcal{P}$, $M$):

Find a variable $x$ mentioned in $\mathcal{P}$ but not in $M$.  (If no such variable exists, find any solution to $\mathcal{P}$, output it, and return.)
Let $a$ denote the smallest feasible value for $x$ (found using a call to the IP solver).  Let $b$ denote its largest feasible value (another call to the IP solver).
Recursively call EnumSolns($\mathcal{P} \cup \{x=a\}$, $M \cup \{x\}$).
If $a<b$, recursively call EnumSolns($\mathcal{P} \cup \{a+1 \le x \le b\}$, $M'$) where $M'=M \cup \{x\}$ if $a+1=b$, or $M'=M$ otherwise.

To enumerate all solutions to an integer programming problem $\mathcal{P}$, call EnumSolns($\mathcal{P}$, $\emptyset$).  If $s$ denotes the total number of solutions and $n$ the number of variables, the running time will be at most $O(ns)$ calls to the IP solver.

In practice, various optimizations may be possible.  Some IP solvers support pushing and popping inequalities, and can remember facts that were learned during a search for the previous system of inequalities and make use of them after pushing another inequality; this may speed up this algorithm substantially.

For a 0-1 integer program, there is a simpler recursive algorithm:

Enum01Solns($\mathcal{P}$, $M$):

If $\mathcal{P}$ is not feasible (determined with a call to the IP solver), return.
Find a variable $x$ mentioned in $\mathcal{P}$ but not in $M$.  (If no such variable exists, find any solution to $\mathcal{P}$, output it, and return.)
Recursively call Enum01Solns($\mathcal{P} \cup \{x=0\}$, $M \cup \{x\}$) and Enum01Solns($\mathcal{P} \cup \{x=1\}$, $M \cup \{x\}$).

If you just want to count the number of feasible solutions to the integer program, without listing them, see Finding all solutions to an integer linear programming (ILP) problem.


Conditions for string substitution commutativity

It's really simple. Just build two finite state transducers A and B , one for each substitution, then perform their composition A○B and B○A check if they are equivalent. Checking equivalence of transducers is undecidable, but in this case the transducers should be functional and equivalence in this special case is decidable.


Some slight confusion with the UNTIL operator in CTL (e.g. a U b)

You have some misconception regarding transition systems:
The alphabet of the system is $2^P$ for some set $P$, and paths induce words over $2^P$. In the first system, there is a single path: $(S_0,S_1)^\omega$, and it induces a single word: $(\{a\},\{a,b\})^\omega$.

Now, this word satisfies $aUb$, since $a$ holds until the secod letter, in which $b$ holds.

The $\forall$ quantifier here is somewhat useless, since there is a single path.

The second system is problematic, since there is nowhere to go to from $S_2$...


Distributivity of $\omega$-regular expressions

As suggested by Raphael, here's a proof doing it via the sets represented by those expressions.

$\qquad L_\omega((E_1+E_2) \cdot F^\omega)  \\= L(E_1+E_2) \cdot L_\omega(F^\omega) \\= (L(E_1) \cup L(E_2)) \cdot L_\omega(F^\omega) \\= \{w_1w_2 | w_1 \in (L(E_1) \cup L(E_2)) \wedge w_2 \in L_\omega(F^\omega) \} \\= \{w_1w_2|(w_1 \in L(E_1) \wedge w_2 \in L_\omega(F^\omega)) \lor (w_1 \in L(E_2) \wedge w_2 \in L_\omega(F^\omega))\}\\= \{w_1w_2|(w_1 \in L(E_1) \wedge w_2 \in L_\omega(F^\omega))\} \cup \{w_1w_2|(w_1 \in L(E_2) \wedge w_2 \in L_\omega(F^\omega))\} \\= (L(E_1)\cdot L_\omega(F^\omega)) \cup (L(E_2)\cdot L_\omega(F^\omega))\\=L_\omega(E_1 \cdot F^\omega) \cup L_\omega(E_2 \cdot F^\omega)\\=L_\omega(E_1\cdot F^\omega + E_2 \cdot F^\omega)$

So the only thing that's actual work here is to translate the logical operators into set operators.


This is difficult to answer because in part we have to guess what your instructor actually meant, but that said, I can't see a way to reconcile the statement.

You could ask if the components that are strongly connected in the underlying undirected graph are DAGs, but this is trivial, any subgraph of a DAG is also a DAG - we're not adding any edges, so we can't introduce a cycle.

Alternatively, we could ask for strongly connected components of a DAG, but here your observation is correct, there are no non-trivial strongly connected components in a DAG. The trivial ones are just each vertex by itself, which is trivially a DAG too, so that kind of works, if your instructor is looking to test your understanding of the definitions.

The last thing I can think of is that if you take a directed graph (not necessarily acyclic), and shrink each strongly connected component to a single vertex, the resulting graph is a DAG (called the "condensation" of the original graph). The condensation of a DAG is the DAG itself (we're back to the trivial strongly connected components again).


How can a cyclic tag system halt with an output?

Neary and Woods describe an efficient simulation of Turing machines using cyclic tag systems, improving on work of Matthew Cook. Turing-completeness is a somewhat fluid and informal notion. A computing system X simulates another computing system Y if given each program in Y we can come up with a program in X such that looking at the transcript of the X-program, we can recover a transcript of the Y-program.

You can look at the papers above to see what this means for cyclic tag systems. The basic idea is that when the Turing machine halts, the cyclic tag systems keeps going, forever repeating the same sequence of configurations, representing the halting configuration of the Turing machine. In this sense it can actually compute functions.

In an earlier answer I noted that some computation models can only compute decision problems, in the sense that they either don't halt, or they halt with just one bit of output. In that case you can encode general function in at least two ways:

Given a function $f$, consider the language of pairs $\langle x,f(x) \rangle$.
Given a function $f$, consider the language of triples $\langle x,i,b \rangle$ such that the $i$th bit of $f(x)$ (if any) equals $b$.

As usual, we require that the machine always halt.


Proving using a SAT solver that KB entails D

TL;DR: Use the SAT solver to search for a counterexample.
To check that $KB \models \varphi$, you need to know whether there is any assignment that is consistent with $KB$ but that does not satisfy $\varphi$.  In other words, you need to know whether $KB \land \neg \varphi$ is satisfiable or not.  If $KB \land \neg \varphi$ is satisfiable, then you have found a counterexample that demonstrates that $KB \not\models \varphi$.  If $KB \land \neg \varphi$ is not satisfiable, then you proven that $KB \models \varphi$ is true.
Now apply that to your specific example.


Deterministic Turing Machine with infine tape in both directions

You can design a Turing Machine that goes one step left, then two right, then 3 left and so on...
You don't need too much states for that: just put two markers on the tape: $b$ for the current left boundary and $c$ for the current right boundary of what you explored, and push them back from one cell each time you reach them.
You have one state $q_b$ going left until $b$ is reached, and one state $q_c$ going to the right until $c$ is reached. Plus special states to shift them by one position.

You will eventually find the $a$ letter, at which point you just go to $q_f$.


This is part of the field called CALLS, or computer-assisted language learning.

It is an interesting subject, and the straight-forward approach would be to first do speech-recognition, then use NLP to find errors, and notify the user. Interestingly, I would think that any good speech recognition software would have to use NLP to disambiguate the speech (and possibly use NLP in additional ways).

So it is sort of a catch-22: in order to recognize the speech, some sort of assumption that the user is using (mostly) correct langauge is made, and therefore NLP can be used to assist the speech recognizer. But in this case, you have to be much much more sensitive to the user using incorrect language. So I think a different approach is necessary, where you integrate the "incorrectness detector" directly into the speech recognition somehow.

Or, perhaps use statistical/machine learning methods entirely (or a combination); ie. train the machine on data of non-native language speakers, and use a learning algorithm to teach the machine what mistakes commonly happen. I am unsure how feedback would work here though.

More info, on non-native pronunciation error detection and feedback:

Rosetta Stone can evaluate pronunciation
Byki (the paid version gives feedback on pronunciation, I don't know how it works though)
Automatic Pronunciation Evaluation And Mispronunciation Detection Using CMUSphinx

Basically, research into exactly what you are asking, via speech recognition software method, I wrote about above.
EduSpeak®: A speech recognition and pronunciation scoring toolkit for computer-aided language learning applications (paywalled)

Machine learning approaches:

A new method for mispronunciation detection using Support Vector Machine based on Pronunciation Space Models
Automatic Error Detection for Unit Selection Speech Synthesis
Using Log Likelihood Ratio based SVM Classiﬁer
Mispronunciation Detection via Dynamic Time Warping on Deep Belief Network-Based Posteriorgrams

This is all mostly about pronunciation. For grammar, you can tack on something to speech recognition, using NLP. The same caveats apply to grammatical error detection as to pronunciation; NLP would normally likely be used as part of speech recognition, so the error detector would likely have to be integrated directly into the speech recognition software.

More info on non-native grammatical error detection and feedback:

Presentation: The Computer and Natural Language. Special Topic: Grammatical Error Detection
An Analysis of Grammatical Errors in Non-native Speech in English


Check if a row is in the span of a matrix

Let your vector be $x$, and let the first row be $r$.

If $x_1 = 1$ and $r_1 = 0$, then $x$ is not in the span.

If $x_1 = 0$ and $r_1 = 1$, then $r$ cannot be part in any linear combination that results in $x$, so we can remove $r$ and continue.

If $x_1 = 0$ and $r_1 = 0$, then we can remove the first column and continue.

If $x_1 = 1$ and $r_1 = 1$, then for $x$ to be a linear combination of the rows, $r$ must be one of the rows in the linear combination. So we can replace $x$ with $x \oplus r$, remove the first row and column, and continue.

You can also present this algorithm in an iterative manner.

Let $i$ be the index of the first $1$ in $x$. For $x$ to be in the span, there must be a row whose first $1$ is also at index $i$. Find this row $r$, replace $x$ with $x \oplus r$, and continue, until eventually $x = 0$.


NFA equality for automata with partial transition functions and all states accepting

The problem is PSPACE-complete, by reduction from the equivalence problem for NFAs.

Suppose we are given two NFAs $A_1,A_2$ over an alphabet $\Sigma$. Let $\dashv$ be a new symbol. To each of the NFAs we add two new states $q_f,q_t$, and the following transitions:

An $\epsilon$-transition from the initial state to $q_t$.
A self-loop on $q_t$ labeled $\Sigma$.
A transition labeled $\dashv$ from every accepting state to $q_f$.

Let $B_1,B_2$ be the new NFAs, after making all of their states accepting. Then
$$
L(B_i) = \Sigma^* \cup (L(A_i)\dashv).
$$
Therefore $L(A_1) = L(A_2)$ iff $L(B_1) = L(B_2)$.


What is the standard way to choose a new leader in Multi-Paxos?

Using the terminology of the Leslie Lamport Paxos Made Simple a leader is implicitly chosen when phase 1 is executed and a node hears it has the highest proposal. The problem is not leader election as phase 1 is leader election; the trick is that any server can start and win a new election before the previous leader can make any progress. So rather than the challenge of getting a leader the challenge is not getting too many competing leaders duelling; yet not waiting too long before attempting to get a new leader.  See this answer that quotes where the original Paxos papers talk about having a stable leader after a proposal has been accepted.

The raft paper has a lot of detail about leader timeouts. Basically you should have the leader send heartbeats. These can be no-op values as described in the Paxos Made Simple paper. If a follower does not get a message for a while it can timeout and propose. You add a bit of randomness to the timeout to try to prevent simultaneous proposers. You should respond with nacks as mentioned in the Papxs paper stating the higher promise value. That way if you do get simultaneously proposers the nacks will suppress candidates as only one candidate will get the highest number to a majority leading to nacks to the other candidates inside of one full round of phase 1+2 messages to the winner.

If servers stay up after the failure and the network stays stable a new leader should emerge promptly without too much delay or wasted messages on failed rounds due to duelling. The exact timeouts to set can be tuned to a given environment exactly as described in the raft paper.


What will trigger a worst time search for a binary heap and what is the run time?

Heaps are maintained so that they are always balanced. A heap containing $n$ elements will have height $O(\log n)$. All operations on heaps take time linear in the height.


What is the most efficient algorithm to compute polynomial coefficients from its roots?

This can be done in $O(n \log^2 n)$ time, even if the $x_i$ have duplicates, via the following divide-and-conquer method.

First compute the coefficients of the polynomial $f_0(x)=(x-x_1) \cdots (x-x_{n/2})$ (via a recursive call to this algorithm).  Then compute the coefficients of the polynomial $f_1(x)=(x-x_{n/2+1})\cdots(x-x_n)$.  Next, compute the coefficients of $f(x)=f_0(x)f_1(x)$ using FFT-based polynomial multiplication.

This yields an algorithm whose running time satisfies the recurrence

$$T(n) = 2 T(n/2) + O(n \log n).$$

The solution to this recurrence is $T(n) = O(n \log^2 n)$.  This all works even if there are duplicates in the $x_i$.

(You might also be interested in Multi-point evaluations of a polynomial mod p.)


How can a Turing machine run another machine for an infinite amount of strings?

The technique is knows as dovetailing. The machine $P$ keeps a two-dimensional tape and uses the following algorithm:

Run $M$ on the first string for one step.
Run $M$ on the first two strings for one step.
Run $M$ on the first three strings for one step.
...

(We imagine that all possible strings are arranged in some arbitrary computable order, say $\Lambda,0,1,00,01,10,11,000,\ldots$.)

Each simulation of $M$ runs on its own "row" of the two-dimensional tape of $P$, which also stores the location of the head and the current state. (A two-dimensional tape can be simulated by a one-dimensional tape.)

If $M$ ever halts on one of the strings, then $P$ halts. Therefore $P$ halts iff $M$ halts on some input.


Interesting question. I think the biggest barrier preventing something like that from happening is that computers are engineered to be extremely robust to random, non-human errors. Computers will do what programmers instruct them to do, and unless the hardware is being pushed beyond its limits or subjected to extreme environments like cosmic radiation in space, they do not deviate from programmer instruction.

It is necessary for computers to have these near-zero error rates due to the sheer quantity of operations they perform. An error rate of one in a million seems pretty good...until you consider that a modern desktop computer is capable of performing about 100 billion operations per second. A one in a million error rate  would result in 100,000 errors per second, rendering your computer completely unusable due to constant crashes!

The same reasoning applies to storage mediums as well. If you assume that one in a million bits stored on a 1TB drive gets corrupted every day, then that would result in 360 megabytes of corrupted data per year!

The necessary low error rates are achieved through a combination of robust engineering and manufacturing, as well as software tricks to detect and repair errors such as checksums and error-correcting codes. In situations where these measures are insufficient, such as on spacecraft computers where cosmic radiation can wreak havoc, fully redundant computers check each others' results though voting.

Therefore I'd argue that "descent with modification" doesn't really exist here. Computers operate more or less deterministically and without error by design, so it would be very difficult for an unexpected program to spontaneously emerge.

If we designed computers that were much more error-prone, then it would be more likely that such an event could happen. But such a computer is also likely to be pretty useless, so we don't build computers like that.


The grammar is LR(1) and LALR(1). It is not, however, SLR(1). The purpose of this example in the Dragon Book is to show a grammar which is LR(1) but not SLR(1).

The items that you've got so far are completely correct. To understand why state $I_2$ is deterministic, you have to understand what the parser has to do.

The parser has to choose between the following two items:

$S \rightarrow L \cdot = R; \{ \$ \} $

$R \rightarrow L \cdot ; \{ \$ \} $

The first one is a shift of a $=$ symbol which will transfer you to a state with the kernel item $S \rightarrow L = \cdot R; \{ \$ \}$. The second one is a reduce which reduces by the production $R \rightarrow L$.

The lookahead set is what the parser expects to see after it has read the whole production, but the dot indicates what the parser expects to see right now. In the case of the first item, it expects to see $=$, then $R$, then $\$$. When constructing the parser actions, the symbol that you're looking for to do the shift is $=$, because that is the symbol which is shifted.

If the second item's lookahead set contained the symbol $=$, then the shift-reduce conflict would not be resolvable and the grammar would not be LR(1), because it would not be clear which direction to take if the next symbol were $=$.

As it is, the state is deterministic. If the next symbol is $=$, shift it and take the first item. If the next symbol is $\$$, reduce.

(Warning: The rest of of this is a slight digression.)

As well as deriving the machine by hand, I fed the grammar into a parser generator (I used yacc, you could use Bison, ANTLR etc) just to be certain. If you do this, then you should be aware that production-quality parser generators sometimes take a shortcut by not consulting the lookahead symbol on reduction if they don't have to.

In this case, if you found yourself in state $I_2$ and the next symbol was $id$, then you may as well reduce, even though you could have detected a syntax error at this point.

There are three main reasons for this.

First, you don't have to check, since the error will eventually be detected when you try to shift the $id$ symbol. Remember, even the LR(0) machine is correct for this grammar, it's just nondeterministic; what we call a "conflict" in LR-speak we would call "nondeterminism" in other kinds of automata. If the decision is already deterministic, using lookahead information doesn't make it more deterministic.

Second, it's expensive to store and check the lookahead set. Even though computers are big these days, smaller is still better. Saving space is good.

Third, and perhaps most importantly these days, in real parsers, you need to report the syntax error to the user in a way that helps them understand what went wrong. The "bigger" the concept that you can use in the report (e.g. "expression" rather than "lvalue"), the more understandable it is. Reducing before reporting helps with this.

So if you feed this grammar into a production parser generator like ANTLR, Bison, or YACC, you will find that the actions for this state basically say "if you see $=$ then shift and go to state X, otherwise reduce". If you were wondering why they don't consult the lookahead set, that's why.

(Digression ends.)


Which is the most efficient out of Bubble Sort, Selection Sort, Insertion Sort for a identical set of elements?

All elements being the same is equivalent to data being sorted. The class of algorithms you are looking for is adaptive sort, which benefits from presortedness of the input data - this is the justification - since data is already sorted we have to find algorithm that uses this fact. The classic example is the insertion sort, but also Timsort (a variant of natural merge sort) and other exist. All adaptive algorithms should show the best case performance as $\mathcal{O}(N)$, which in case of insertion sort is exactly $N - 1$ comparisons, where $N$ is the length of input data.
There is no need to implement or run those algorithms, it is suficcient to show that part responsible for swapping elements is never executed, show that appropriate conditions are always true (or false depending on code) so analysis is easier.

From the possible algorithms you have provided the best cases are: Bubble sort - $\mathcal{O}(N)$, Selection Sort - $\mathcal{O}(N^2)$ and Insertion Sort - $\mathcal{O}(N)$.


Is generalized XOR-SAT efficiently solvable?

It looks like the Wikipedia article you linked to says that XORSAT (not just 3-XORSAT) is in P. The method by which they are solving that 3-XORSAT formula in their example very easily generalizes to formulas in which the clauses can have arbitrarily large numbers of variables and differing numbers of variables.

You just look at the formula as a system of linear equations where you have an equation for each clause, and a variable for each variable. For example, the formula:

$$(x_1\oplus x_2\oplus\lnot x_3\oplus x_5)\land (x_2\oplus x_3)$$

has a satisfying assignment if and only if the following system of equations has a solution:

$$x_1+x_2+(1+x_3)+x_5\equiv 1 \mod 2$$
$$x_2+x_3\equiv 1 \mod 2$$

And we can find solutions to linear systems of equations like these in polynomial time using Gaussian elimination!


Any book for learning to correctly find out complexity of one's algorithm?

Simply pick up any algorithms book out there, they will all take you through these things.  What you are describing is essentially the algorithms (and computational complexity) field.

The most popular books are Algorithms by Sedgewick and Wayne, which is free for download, the CLRS Introduction to Algorithms, and the epic Art of Computer Programming by Knuth.


Is $L_{half} = \{w : \text{for some } z \in L, x \in \Sigma^*, z = wx \wedge |w| = |x| \} $ regular?

Yes, the language is regular:
Consider a DFA A such that $L(A)=L$
Now, assume that you know, somehow, that when given a word $w$, the run of $A$ will end up in state $q$.

All you need to check now is that there is a run of $A$ on some word of length $|w|$ that gets from $q$ to an accepting state. This can be done by using the product automaton $A\times A$, where the first component acts exactly like $A$, and the second acts like $A$, but starts from state $q$ and ignores the input - that is, for each letter it nondeterministically goes anywhere that $A$ can go. Then, a run is accepting if the first component ends up in $q$, and the second component ends in an accepting state.

Finally, you can drop the assumption by taking $|Q|$ copies of this construction, where each copy "guesses" in which state $A$ will end up in. You end up with a nondeterministic construction of size $|Q|^3$


Are recursively enumerable languages closed under shuffle?

Hint: A language is recursively enumerable if and only if it can be recognised by a nondeterministic Turing machine. Use this fact to build a nondeterministic recogniser for $\textsf{shuffle}(L_1,L_2)$ from the deterministic recognisers for $L_1$ and $L_2$. What is it, that one most use nondeterminism to guess?


Shuffling a collection too large for memory

Let $n$ denote the number of items in the set, and $f(i)$ denote the $i$th value.  Use format-preserving encryption to construct a random permutation $\sigma:\{1,\dots,n\} \to \{1,\dots,n\}$.  Define $g(i) = f(\sigma(i))$.  Then $g$ is a representation of a randomly shuffled version of your set, and specific items can be accessed very efficiently.

To address your concrete problem, you'd pick a random permutation on $\{0,1\}^{24}$, i.e., $\sigma : \{0,1\}^{24} \to \{0,1\}^{24}$.  This can be done using format-preserving encryption: format-preserving encryption will give you a block cipher $E:K \times \{0,1\}^{24} \to \{0,1\}^{24}$ such that if you pick a key $k \in K$ random, $E_k$ will be (indistinguishable from) a random permutation on $\{0,1\}^{24}$. Moreover, $E_k$ can be efficiently evaluated.  Then, if you want $m$ random RGB colors, you'd pick a random key $k$ and output the $m$ colors $E_k(0), E_k(1), \dots, E_k(m-1)$.

A reasonable way to build a 24-bit block cipher is to use a Feistel cipher on 24 bits: say, 4 rounds, where in the $i$th round you map the input $L||R$ to the output $R||(L \oplus f_k(R,i))$, where $L,R$ are each 12 bits long and $f_k$ is a PRF, say $f_k = AES_k(R||i)$, and $||$ denotes concatenation of bits.  You can adjust the number of rounds (fewer rounds is faster; more rounds gives higher amount of pseudorandomness; you probably want at least 3 rounds), and you can adjust the choice of $f$ (for instance, instead of a cryptographic-based construction, you could use any fast, non-cryptographic hash function).  This is the construction proposed in https://en.wikipedia.org/wiki/Format-preserving_encryption#FPE_from_a_Feistel_network.  I suggest referring to the Wikipedia link I shared above for an overview of standard constructions for format-preserving encryption.


If L is regular language then each equivalence class is also regular?

Given a DFA $D$ and a word $x$, let $D(x)$ denote the state of $D$ after reading $x$.

Let $D$ be a minimal DFA for $L$ and $x,y \in \Sigma^*$.
If $D(x) \neq  D(y)$ then $x$ and $y$ have a distinguishing extension.
Indeed, if $x$ and $y$ had no distinguishing extension, it would be possible to construct a DFA $D'$ with one less state by merging the states $D(x)$ and $D(y)$ of $D$.

On the converse, if $D(x)=D(y)$ then $x$ and $y$ have no distinguishing extension (since the states reached by $D$ from $D(x)$ and $D(y)$ after reading any string $z$ must coincide).

Then, $x$ and $y$ are in the same equivalence class iff $D(x)=D(y)=q$, for some state $q$ of $D$.

Given a state $q$ of $D$, the language of all the words $x \in \Sigma^*$ such that $D(x)=q$ is regular. To see this, consider the DFA obtained from $D$ by changing the set of final states to $\{q\}$.


The first reference seems to be Rank permutation group codes based on Kendall's correlation statistic by Chadwick and Kurz; your notion of distance is known as Kendall's tau distance. A more modern reference is Codes in Permutations and Error Correction for
Rank Modulation by Alexander Barg and Arya Mazumdar


What future working opportunities do computer science students have?

If I am right students learning computer science at universities learn very theoretical kind of knowledge.

You are largely incorrect. A significant portion of most CS curricula includes hands-on, applied, practical programming, computer systems and software development exposure. The ACM publishes curriculum guidelines for ABET/CAC-accredited CS programs in the US. You should check their list of recommendations to get a more-or-less complete picture of what most CS programs worth the name cover.

  A knowledge most of which (e.g. algorithm theory) can't be used to create everyday software (e.g. MS Word, IE, etc.).

Algorithm theory is absolutely and vitally important for creating everyday software (such as MS Word, IE, etc.), specifically, for differentiating the software sufficiently to compete. To even write a web browser, one needs to understand HTTP, TCP, multithreading, parsing, etc.

  What opportunities do computer science graduates have if they don't want to do research but rather work at some company where they can make use of what they have studied. (e.g. not writing MS Word)

Any company that needs people to write software will need to hire somebody. Having academic credentials is a plus and a computer science degree is more applicable than just about any other option. More applicable, applied, practical options are typically viewed with some skepticism in the US since they're viewed as less rigorous (perhaps rightly so).

  In case of still not being clear enough, generally speaking, what I would like to know is what can a computer science gradute work?

Anywhere most graduates can work. Most of industry bases hiring decisions on individual circumstances; a CS major with experience in mechanical engineering could be hired as a mechanical engineer. A CS major with experience making puff pastry could be hired as a chef. Most CS majors would be well qualified to take jobs writing software since, by virtue of being a CS major, they have some experience writing software.


Distinguishability given black box access to the distribution

You can't.  Your intuition is wrong.  I will give an explicit counter-example.  Actually, I'll give you two: two for the price of one.
Suppose $n=1$, the distribution $D$ always outputs 1, and $U$ is uniform on $\{0,1\}$.  The following algorithm is an optimal distinguisher:

Never use the black box.  If the input $z$ is 0, guess that it came from $U$, otherwise guess that $z$ came from $D$.

Suppose we run this algorithm on an input $z$ and it guesses that $z$ came from $D$.   Then it's not true that $z$ must be equal to one of the queries to the black box; the algorithm didn't make any queries to the black box.
If you're not happy with that, you can obtain another explicit counterexample by considering the following algorithm, with $U$ being the uniform distribution and $D$ a distribution that outputs $1$ with probability $3/4$ and $0$ with probability $1/4$:

If the input $z$ is 0, get a sample $z_1$ from the black box, ignore $z_1$, and guess that $z$ came from $U$.
Otherwise, get a sample $z_1$ from the black box, ignore $z_1$, and guess that $z$ came from $D$.

Notice that if this algorithm guesses that $z$ came from $D$, it is not necessarily true that $z=z_1$ (it can happen that $z=1$ but $z_1=0$), so your claim is not true about this algorithm either; yet this algorithm is an optimal distinguisher.
It's often useful to test your intuition on some simple examples.
I suspect what you're missing is that the adversary is assumed to know the distributions $D,U$ in advance and then choose an algorithm based on knowledge of $D,U$ -- a different distinguisher algorithm for each different $D$.  There's no requirement to choose a single algorithm that works for all $D,U$.


What are the differences between Oracle Turing Machine and PAC?

An oracle access to a random oracle can simulate the effect probabilistic TM's have. However, oracle machines aren't limited to using a random oracle, you can specify whatever oracle you would like, to any problem - no matter how hard the problem is, and a TM with an oracle access to it would solve it in constant time.
So, in this line of thinking - an oracle machine can be thought of as a really general extension of the probabilistic case.
I don't know if this answered your question, but I hope I managed to help a little!


Shortest paths when edge weight depends on previous edge

Let your graph be $G=(V,E)$.  Build a new graph $G'=(V',E')$, where each vertex in $G'$ corresponds to a pair $(u,v)$ of vertices in $G$.  Add an edge $(u,v) \to (v,w)$ in $G'$ iff there is an edge $v \to w$ in $G$.  The intended meaning of the vertex $(u,v)$ is that you are currently at vertex $v$ in $G$, and previously were at vertex $u$.  Thus, you can now figure out what weight to put on the edge $(u,v) \to (v,w)$ -- namely, whatever weight you want to put on the edge $v \to w$ assuming you previously traversed the edge $u \to v$.

Let $X' = \{(x,u) \in E : x \in X, u \in V\}$ and $Y' = \{(u,y) \in E : u \in V, y \in Y\}$.  Now, the find the shortest path in $G'$ from each vertex in $X'$ to each vertex in $Y'$, using an all-pairs shortest paths algorithm.  From this you can infer the length of the shortest path in $G$ from some vertex in $X$ to some vertex in $Y$, while taking into account the fact that edges switch weights.

If you use the Floyd-Warshall algorithm, the running time will be $O(|V'|^3)$, which is at most $O(|V|^6)$.  As an optimization, the vertex set $V'$ can be taken to be $V' = \{(u,v) : u,v \in V, (u,v) \in E\}$.  Then the running time of Floyd-Warshall in $G'$  will be at most $O(|E|^3)$.  Given that your original graph $G$ is fairly small, this might already be feasible without further optimizations.

If you want further optimizations, here's one more.  You can add to $G'$ a special vertex  $x^*$ for each $x \in X$, with an edge $x^* \to (x,u)$ in $G'$ for each $(x,u) \in E$ with the same weight as the edge $x \to u$ in $G$; and similarly add $y^*$ for each $y \in Y$, with edge $(u,y) \to y^*$ of weight 0.  Now find the shortest path from each $x^*$ to each $y^*$.  This can be done by applying Dijkstra's algorithm $|X|$ times, once for each $x \in X$, to find the distance from $x^*$ to each other node in the graph.  The total running time will be $O(|X| \cdot |E'| \log |V'|)$, which is $O(|X| \cdot |V| \cdot |E| \log |V|)$.  You can also achieve running time $O(|Y| \cdot |V| \cdot |E| \log |V|)$ by searching backwards (e.g., reversing the graph).  Given that you have $|Y| \approx 300$, $|V| \approx 2000$, and $|E| \le |V|^2 = 4000000$, this might complete rapidly.


The idea behind Pollard $\rho$ is that if you take any function $f : [0, n - 1] \to [0, n - 1]$, the iteration $x_{k + 1} = f(x_k)$ must fall into a cycle eventually. Take now $f$ as a polynomial, and consider it modulo $n = p_1 p_2 \dotsm p_r$, where the $p_i$ are primes:

$\begin{equation*}
  x_{k + 1}
    = f(x_k) \bmod n
    = f(x_k) \bmod p_1 p_2 \dotsm p_r
\end{equation*}$

Thus it repeats the same iteration structure modulo each of the primes into which $n$ factors.

We don't know anything about the cycles, but it is easy to see that if you go with $x_0 = x'_0$ and:

$\begin{align*}
  x_{k + 1}
    &= f(x_k) \\
  x'_{k + 1}
    &= f(f(x'_k))
\end{align*}$

(i.e., $x'$ advances twice as fast) eventually $x'_k$ and $x_k$ will span one (or more) cycles (see Floyd's cycle detection algorithm for details), thus in our case, $x'_k \equiv x_k \mod{p_i}$,
and $\gcd(x'_k, x_k)$ will be a factor of $n$, hopefully a non-trivial one.

Any polynomial works, but we want irreducible ones (no non-trivial factors, detecting those is not the point of the exercise). Linear polynomials don't give factors, next simplest to compute is a quadratic one, but just $x^2$ doesn't work either (reducible), so take $x^2 + 1$ for simplicity. Remember the idea here is to work with very large numbers, few and simple arithmetic operations are a distinct bonus. The analysis of the algorithm (e.g. in Knuth's "Seminumerical algorithms") models $f(x) \bmod p$ as a random function, which is close enough to explain the overall characteristics of the algorithm.


Circular Doubly Linked List find length with single pointer

I think the following algorithm would do it:

Start by setting the value in the first node to $1$.
Follow next pointers until you encounter a node with value $1$, while keeping a counter $c$ of how many nodes you have encountered.
Set the value of the node to $0$ and follow prev pointers for $c$ steps

If the value of the node (which should be the first node) is now $0$, the list has $c-1$ elements,
otherwise, follow next pointers for $c$ steps and continue with step 2.


How to prove that the reduction relation is not symmetric

In order to show that $L_1 \leq L_2$, we need to come up with a computable function $f$ such that $x \in L_1$ iff $f(x) \in L_2$. Since $L_1 = \Sigma^*$, every $x$ satisfies $x \in L$, and so we need to find a computable function $f$ such that $f(x) \in L_2$ for all $x$. The easiest way to satisfy this is to choose $f$ to be a constant function.
In order to show that $L_2 \not\leq L_1$, we need to show that $f$ is a computable function that it is not the case that $x \in L_2$ iff $f(x) \in L_1$. That is, we need to show that for every computable $f$ there exists $x$ such that it is not the case that $x \in L_2$ iff $f(x) \in L_1$. Since $L_1 = \Sigma^*$, we always have $f(x) \in L_1$, so the only way in which "$x \in L_2$ iff $f(x) \in L_1$" can fail is if $x \notin L_2$. That is, we need to show that for every computable $f$ there exists $x$ such that $x \notin L_2$. The goal doesn't involve $f$, so it suffices to show that there exists $x$ such that $x \notin L_2$.
You take it from here.


Differentiating between BubbleSort and InsertionSort

Unfortunately, your problem statement is contradictory, so the problem cannot be solved in its current form.  Your question states that we can obtain the running time for finite values of $n$.  However, it also states that we only learn the asymptotic running time.  This is self-contradictory, because it is not possible to infer the asymptotic running time based on any finite number of measurements.

If I had to speculate, I'd guess that maybe what the instructor actually wants you to do is find an infinite sequence of inputs $a_1,a_2,a_3,\dots$ such that: (1) $a_i$ is an array of length $i$; (2) the asymptotic running time of Insertion Sort on these inputs differs by more than a constant factor from the asymptotic running time of Bubble Sort on these inputs.  If that's correct, your next step should be to investigate various ways you might construct such a sequence.  I emphasize that this is only speculation, and not something that can be definitively derived from the problem statement as provided.


Don’t understanding argument on words of a certain form

I think the book is right.  In your example, the word $u=abcd$ satisfies the conditions: it is not a prefix of a word in $a^* b^* c^*$.

In general, I think that proof is valid.  I'll try to explain why the minimality of $n$ proves the existence of such a word $u \in L$. If there did not exist such a word $u \in L$, then that would mean that every word $u \in L$ is a prefix of $l_1^* \cdots l_{n-1}^*$, which in turn would mean that $n$ wasn't the minimum possible (we could have used $n-1$), which contradicts how $n$ was chosen in the second sentence.  That's a contradiction.  If you start from an assumption and derive a contradiction, then you can conclude that the assumption must have been wrong.  In particular, the only alternative that remains possible is that there does exist such a word $u \in L$.

Put another way, there are only two possibilities: either there does exist such a word $u \in L$, or there doesn't.  I've shown why the second choice is always impossible.  That means the first choice must actually always be true.


2-3 tree: Sum of leaves in a given range

Storing the sum for internal nodes is a good plan.
For every query you also need to search for the two bounds of the interval, and find the leftmost and rightmost leaf with elements in the interval. (The bounds themselves do not need to be in the tree.) The two search paths will split a a certain node. Continue there. While searching for the leftmost leaf you include all sums to the right.


Randomized BST height analysis : How $Z_{n,i}$ and $Y_{k-1}$ are independent?

I haven't watched the video, but presumably it uses the following model of random BST. You start with one element. Then you insert an element which is smaller than the existing element w.p. 1/2, and larger w.p. 1/2. Then you insert an element which is smaller than both existing elements w.p. 1/3, is between them w.p. 1/3, and larger than both w.p. 1/3. In the $n$th step, you similarly insert the new element in one of the $n$ positions, with equal probability for all.

This means that $Z_{n,k}$, which indicates whether the $n$th element got inserted in the $k$th position, is independent of anything that went on before, and in particular of $Y_1,\ldots,Y_{n-1}$.


Finding the grammar type of the programming language

Programming languages are typically defined in several stages. A language in formal language theory is a set of strings, but that isn't a very useful concept to explain programming languages. The meaning of a source program is defined by several stages of translation; here are typical stages in the compilation of a translation unit:

Lexical analysis, i.e. splitting the program into tokens. Token recognition is often performed by finite automata, but not always (e.g. languages with nested comments need a stack at this stage).
Parsing. This stage is usually described by a context-free grammar. Although lexical analysis could be described by that same context-free grammar, this would typically result in an extremely complex and slow-to-parse grammar, which is why the two stages are separate.
Variable binding, i.e. associating the different uses of the same name to mean the same variable. In particular, in most languages, variables need to be declared before use. This cannot be described by a context-free grammar.
Typechecking, if the language has a static type system. There is a lot of variability here.
After that point, subsequent compilation stages tend not to have failure cases. There are exceptions, for example some languages regulate recursive definitions at a late stage.

There's no grammar type that describes valid programs in typical programming languages (unless you go for a formalism that can describe all decidable languages or more, such as unrestricted grammars). Many languages can be described by a context-free grammar up to stage 2, but there are exceptions (for example, C has feedback from variable binding to parsing because something like f(); foo * bar; is valid in C89 if foo is a variable but not if foo is a type defined by typedef). When you reach the binding stage, there has been work on general models for binding, but I'm not aware of any name for the kind of languages and transducers that correspond to context-free-grammars-plus-bindings. For typechecking, the sky's the limit: there are languages with Turing-complete type systems, and even the ones that aren't are typically very ad hoc and don't particularly fit any interesting category other than decidable.


What are the other language models of computation similar to lambda calculus?

Yes, there are many models of computation, and of those many are extensions or modifications of the $\lambda$-calculus. You may wish to learn about partial combinatory algebras, which are very general models of computation, of which the $\lambda$-calculus is an example. Every partial combinatory algebra has a $\lambda$-like notation for defining functions. They encompass examples such as: $\lambda$-calculus, Turing machines, Turing machines with oracles, topological models of computation, PCF, etc.

Many models of computation can be seen as extensions or modifications of the $\lambda$-calculus. Let us consider the simply typed $\lambda$-calculus augmented with various features:

System T is $\lambda$-calculus with natural numbers and primitive recursion. It is not Turing complete.
The aforementioned PCF is $\lambda$-calculus extended with natural numbers and general recursion. It is Turing complete.
There are many extensions of PCF, for instance PCF++ can perform parallel computations, PCF+catch can throw and catch exceptiosn, PCF+quote can disasemble code into source code, etc. These are all different computation models based on the $\lambda$-calculus.
In another direction, we can extend the $\lambda$-calculus with more powerful types, for instance System F is a $\lambda$-calculus with polymorphic types. It is quite powerful but not Turing complete.

All of this is just scratching a rich theory of models of computation and functional programming languages (which is what extensions of $\lambda$-calculus are, more or less). If you are interested in the topic, you can start by reading some books on the principles of programming langauges (for practical aspects), or some books on realizability theory (for theoretical aspects).


What's a general rule for this little lambda calculus identity?


Problem with understanding two sided Matching Algorithm: maximium cardinality

The standard definition of the stable marriage problem is, given $n$ men and $n$ women, find a stable matching that marries all of the men and women.  Consequently, by definition, everyone will be matched and the number of matches will be exactly $n$ in any solution.  So, no, what you mention cannot happen, if you use that as the definition of the stable marriage problem.

I'm not 100% sure what your text is referring to when it talks about maximum cardinality matching, but I suspect it's referring to find a maximum matching in a bipartite graph, which is completely separate problem.  In this problem, the matching is not required to be a stable matching and it has nothing to do with the stable marriage problem.


Why is the k-bounded spanning tree problem NP-complete?

The question has been asked before on stackoverflow, where it has also been answered. The idea is to connect each vertex to $k-2$ new vertices. The new graph has a $k$-bounded spanning tree iff the original graph has a hamiltonian path.

Mohit Singh and Lap Chi Lau gave a polytime algorithm which find a $(k+1)$-bounded spanning tree if a $k$-bounded spanning tree exists. So we can determine the minimum degree of a spanning tree up to an uncertainty of $1$.


How to prove that $n\log n$ is space constructible?

You are right that if we can construct both $n$ and $\log n$ in $O(n\log n)$ space, we can construct $n\log n$ by multiplying these two values. I think constructing $\log n$ is actually the harder part here, which you seem to have already figured out. But let's go through it.

First, recall that a $k$-tape Turing Machine can be simulated on a single-tape Turing Machine by concatenating all the tapes onto a single tape. I am glossing over the details a bit here (but see Sipser for the details), but the key observation is that the space complexity can equivalently be viewed as the total space used across all tapes of a $k$-tape Turing Machine. So if we can construct a procedure for a $k$-tape Turing Machine that uses $O(n\log n)$ space across all tapes, then we have shown that $n\log n$ is space constructible.

We can construct $\log n$ through repeated halving of $n$. Specifically, we can copy $1^n$ from our initial tape containing the input to a second tape. Then, we can blank half of the ones on this second tape. Once we have blanked half of the ones, this tape will store $1^{n/2}$. We can repeat this halving process until there is only a single $1$ left. We count the number of halvings performed, in binary. We simply maintain a binary counter on a third tape, and perform a binary increment each time we perform a halving on $n$. At the end, the third tape will store the binary representation of $\log n$.

I am assuming that you already had figured the above out since you said you managed to prove $\log n$ is space constructible. And indeed you are correct that if we can independently construct $n$, we can multiply $n$ by $\log n$ in binary, using at most $n\log n$ space (in fact we will need less). All we really need then is to write out the binary representation of $n$ to another tape. Recall how we convert numbers to binary representation: the least significant bit of the binary representation of $n$ is $n\bmod 2$. Then, we can convert $\lfloor n/2\rfloor$ to binary (in a recursive manner) to compute the remaining bits. So, our Turing Machine will continue as follows: Copy $1^n$ to an available tape. Then, compute $n\bmod 2$. Note that we can do this fairly easily (If you are following Sipser, you should hopefully be comfortable with the fact that the set of all even-length strings is even a regular language). We write out the value of $n\bmod 2$ to another tape (call this the "$n$ tape"). Then, we perform the halving procedure on the $1^n$ again. Here, we should be careful about how we handle the case where $n$ is odd: we round down (For example, if $n=5$, after the halving procedure, the tape should contain $11$, the unary representation of $2$). This is to ensure the halving semantics are consistent with $\lfloor n/2 \rfloor$. Then, we move the head on the "$n$ tape" to the left one space, compute the mod once again, and write the result to the "$n$ tape" again. If we continue this modding and halving, writing the results of the modding to the left of the previously written bits on the "$n$" tape, we will eventually write out the binary representation of $n$ (once the working tape has only a single $1$ on it, the "$n$ tape" will contain the binary representation of $n$).

After these two procedures, we should have $\log n$ on one tape and $n$ on another tape, both in binary. Then, as you have already recognized, we can compute the product in $O(n\log n)$ space.


Minimum spanning subgraph of even degree

I just realised that example A is an instance of the Travelling Salesman Problem, which is NP-hard. So the best we can hope for is an approximation algorithm.

I also realised that this is problem is an instance of b-matching, where you want to select up to b edges incident on each node of minimal total weight. Here we have the additional constraint that b is even. I found a couple of papers that solve b-matching:

http://www.aporc.org/LNOR/10/ISORA2009F12.pdf
http://proceedings.mlr.press/v15/huang11a/huang11a.pdf


Page Table Size in a 4 Level Hierarchical Page Table

The virtual addresses must be canonical, the top 16 bits are all copies of the 48th bit. Using a non-canonical address (in the sense of using it as an address) generates a #GP. See also, the manual, volume 3, chapters 3 and 4.

That is independent from the maximum physical address, which is not "canonical" in that way but just goes from 0 to some large number determined by MAXPHYADDR. You can find MAXPHYADDR using CPUID:80000008H, the lowest 8 bits in eax. It specifies the bit index in the page table entries (and some other places where you specify a physical address) at which the physical address stops and the reserved region begins. It's at least 36. It could be 48, but that wouldn't have anything to do with the limits on virtual addresses. The page table entry format allows it to go up to 52 (allowing you to address 4PB of RAM), but that hasn't happened yet. Intel seems to like 39 and 46, AMD seems to mostly use 48 now (they've used lower in the past) (source).


Closure of context-free languages under left-half

Let $L = \{a^nb^na^mbba^{3m} : n,m \geq 1 \}$, which is clearly context-free. Then
$$
\operatorname{half}(L) \cap a^+b^+a^+b = \{ a^nb^na^nb : n \geq 1\},
$$
which is not context-free. Hence $\operatorname{half}(L)$ is not context-free.
(If $L$ is a unary context-free language then $L$ is regular, and so $\operatorname{half}(L)$ is regular.)


What is the natural language of computers mathematics or logic?

There is really no such thing as a natural language for computers. Natural language is a concept from linguistics, and pertains mostly to humans (and perhaps also to some animals).

The corresponding concept for computers is machine language or native code, which is what the computing core of the computer (the CPU) runs. Machine codes consists of various instructions, some of which perform arithmetic and logical operations. Others are in charge of control flow, of memory access, and so on.

Related to machine language is assembly code, which is a readable representation of machine code. While machine code consists of bytes, assembly code consists of textual symbols. (Assembly code also usually contains some features which make it a barebones programming language.)


The easiest way (for me) to understand co-NP is as the class of problems where certificates for "No" answers can be quickly verified (i.e. certificates of non-membership).

So if we look at NP as a class of nondeterministic Turing Machines which quickly (in polynomial time) determine that their input satisfies some property $\Pi$, co-NP is the class of nondeterministic Turing Machines that quickly determine that their input does not satisfy $\Pi$ (or equivalently satisfies $\neg\Pi$).


Is a kind of reverse Kleene star of a context-free language context-free?

Let me solve a simpler question first. Suppose we'd like to know

  If $C$ is context-free, must $F(C)=\{w: ww \in C\}$ be context-free?

The answer is no: $F(\{a^i b^i c^j a^j b^k c^k\})=\{a^i b^i c^i\}$.

As for the original problem, consider the context-free language that contains words of the form $\{a^i b^i c^j d a^j b^k c^k d\}$ or those which don't contain exactly two $d$'s.

Define $D=\{w: w^\ast \subseteq C\}$. Suppose $D$ is context-free. Then $E=D\cap a^\ast b^\ast c^\ast d$ is context-free.

I claim $E=\{a^i b^i c^i d\}$, which is not context-free. Suppose $w = a^i b^j c^k d$. We have $w \in E$ exactly if $w^n \in C$ for every $n$. This condition is clearly satisfied when $n \neq 2$, because $w^n$ will not have exactly two $d$'s. For $n=2$, $w w=a^i b^j c^k d a^i b^j c^k d\in C$ which is equivalent to $i=j=k$.


Is there a way to tell a picture has been resized?

As Raphael already said, in general it's impossible.

There is the field of image forensics where people look for methods to detect tampering with images. For JPEG images for example, there is a paper about detecting resizing: A new approach for JPEG resize and image splicing detection.


Finding shortest path for DAG using dynamic programming vs topological sort?

To use dynamic programming, you need to choose the order in which you fill in values for the vertices.  The correct order is a topologically sorted order (any other order won't work).  So, the two solutions are in some sense equivalent.  Any solution is likely to use both components: topological sorting to determine the order to enumerate the vertices, and something like dynamic programming to fill in the value at each vertex.


Fast implementation of basic addition algorithm

In a positional number system, there is one highest digit; every other has a successor in the set of digits. At the (low-significant) end of the sequence of digits (the integer's representation), there is either one of those other digits, or a sequence of that highest one.


Strict polynomial hierarchy and reduction

$\newcommand{\PH}{\mathsf{PH}}$To expand the comments:

Suppose there did exist a $\PH$-Complete language $L \in \Sigma_i$ for some $i$. By definition of completeness $L' \leq L$ for all $L' \in \PH$. Therefore there exists some language $L' \in \Sigma_{i+1}$ that reduces to $L$. This is a contradiction with the strictness assumption. Indeed, we conclude that no such $\PH$-Complete language exists.


How to compute quotient subgroup efficiently?

Based on the following snippet from https://en.wikipedia.org/wiki/Quotient_group:

  In a quotient of a group, the equivalence class of the identity element is always a normal subgroup of the original group, and the other equivalence classes are precisely the cosets of that normal subgroup.

It seems that you can simply set $H$ to be the identity element of $G/H$ (taking O(1) time), and then for each element $g \in G$ that has not yet been assigned to any coset, calculate the (say, left) coset of $H$ w.r.t. $g$ explicitly: $\{gh : h \in H\}$, and assign all such elements $gh$ (not just the $g$ we started with) to this coset.  Calculating the coset for a particular $g$ takes $O(|H|)$ time, but the entire second phase takes only $O(n)$ time overall, since we only consider elements $g \in G$ that have not yet been assigned to a coset -- this is allowed because (according to that page) the cosets form an equivalence class, meaning no element can appear in two different cosets.


Which algorithms have runtime recurrences like $T(n) = \sqrt{n}\,T(\sqrt{n}) + O(n)$?

Think of an algorithm, which do something linear with an integer list of length $n$, for example computes the maximum. Afterwards, the algorithm divides the list of length $n$ into $\sqrt{n}$ lists of length $\sqrt{n}$ and starts the algorithm for them. The result of the algorithm is for example the product of the computed maximum and the results of the $\sqrt{n}$ lists. For the base case, a list of length $1$, you can return  the value of the only element.

This algorithm has the time complexity, you asked for.


Maximum cut using a 1/2 approximation greedy algorithm

Let us say that an edge $(v,w)$ belongs to $v$ if when $v$ is processed, $w \in A \cup B$, and that $(v_1,v_2)$ belongs to $v_2$. Denote by $N_v$ the number of edges belonging to $v$, and by $C_v$ the number of those edges that are cut by the algorithm. Step 2 ensures that $C_v \geq N_v/2$ (this clearly holds for $v = v_2$ as well). Therefore $\sum_v C_v \geq \sum_v N_v/2$. Finally, notice that $\sum_v N_v$ is the number of edges in the graph, and $\sum_v C_v$ is the size of the cut produced by the algorithm.

Here is a sketch of another proof. At any point in time, define the score of an edge $(u,v)$ as follows:

If $u,v \in A$ or $u,v \in B$, the score is 0.
If $u \in A$ and $v \in B$ or vice versa, the score is 1.
Otherwise the score is 1/2.

You can check that the initial score is at least half the number of edges, the score never decreases, and the final score is number of edges cut by the algorithm.


For any element at index $i$ store its left chid at index $2i +1$ and right child at index $2i+2$.

Your heap in the form of array without any insertion. The $0$ in the array given below
 means no key at that index.
  $$\fbox{4}\fbox{6} \fbox{8}  \fbox{7}\fbox{0}\fbox{0} \fbox{0} \fbox{0}$$

After inserting $2$.

$$\fbox{4}\fbox{6} \fbox{8} \fbox{7}\fbox{2}\fbox{0} \fbox{0} \fbox{0}$$

But you need to maintain the min heap property. So

$$\fbox{4}\fbox{2} \fbox{8} \fbox{7}\fbox{6}\fbox{0} \fbox{0} \fbox{0}$$

Again $2$ is less than $8$. So

$$\fbox{2}\fbox{4} \fbox{8} \fbox{7}\fbox{6}\fbox{0} \fbox{0} \fbox{0}$$


Are there dynamic programming examples that run in exponential time?

A well-known example is the Held-Karp dynamic programming approach to solving the traveling salesman problem (TSP), running in $O(n^22^n)$ time and $O(n2^n)$ space. For more, see these notes.


How to prove: If $\textsf{EXP} \subseteq \textsf{P/poly} $ then $\textsf{EXP} = \Sigma^p_2$

The more classical statement is that if $\textsf{EXP} \subseteq \textsf{P/poly}$ then $\textsf{EXP} = \textsf{MA}$, due to Babai, Fortnow and Lund. Impagliazzo, Kabanets and Wigderson showed that $\textsf{NEXP} \subseteq \textsf{P/poly}$ iff $\textsf{NEXP} = \textsf{MA}$. See lecture notes of Bogdanov for proof sketches.


Help with model answer for time complexity

The loop body will be executed $n - 1$ times because your index variable is initially set to $2$ rather than $1$.
Hence, at the start of the loop body, the values for index are from the range $\{2, 3, ..., n\}$, which has $n - 1$ elements.


What is the complexity of finding the two prime numbers a composite number (used in RSA Protocol) is made of?

Large numbers are factored with the General Number Field Sieve, which is, as of now, the fastest non-quantum algorithm.
You can find the heuristic runtime in the linked Wikipedia-article.
Also in use is the Elliptic Curve Factorization, which needs longer runtime in the worst-case, but has the advantage that the runtime depends on the second-largest factor. Thus every now and then it's faster.
The largest "RSA"-number yet factored is a 768 bit number (RSA Factoring Challenge).


DFS vs. Union Find for computing connected components of a static graph

When the graph is dynamic, union-find can update the list of connected components in time $O(\alpha(V))$ per vertex or edge, whereas it is not clear how to run DFS progressively. So we can complement the statement you quote by

  When the edges of the graph are dynamic – changing over time – DFS is not a good choice since it cannot be applied progressively; we can compute the connected components faster by using union-find.

That said, union-find is helpful only if edges and vertices are never deleted.


Is there a more efficient algorithm than backtracking/dynamic programming?

(Throughout this answer I use $\phi = \frac{1+\sqrt{5}}{2}$, which is the Golden Ratio.)

Solution:

If $s\leq n$, the attackers can win in one day.
If $s+dpw<\phi^2n$ and $s<2n$, the attackers can win in $2+\max(k,0)$ days, where
$$k=\left\lceil\frac{\log_\phi{\left(\frac{n+(dpw+s-2n)\phi^{-1}}{n-(dpw+s-2n)\phi}\right)}}{4}\right\rceil.$$
If $dpw<n$, the attackers can win in $c+\max(k,0)$ days, where
$$c = \left\lceil\frac{\sqrt{dpw^2+4 n\cdot dpw}-dpw+2 n-2 s}{2 (dpw-n)}\right\rceil$$
and
$$k = \left\lceil\frac{\log_\phi{\left(\frac{n+(s + c\cdot dpw-(c+1)n)\phi^{-1}}{n-(s + c\cdot dpw-(c+1)n)\phi}\right)}}{4}\right\rceil.$$
If the attackers cannot win, the minimum number of days for the castle to win is $2$ (the attackers all fire their cannons and are wiped out on day two).

Proof:

For a given day $i$, let $s_i$ be the remaining castle strength, $a_i$ be the remaining attacking force, and $d_i$ be the remaining defending force.

First consider the case that $d_i = dpw$ (that is, the attackers killed all defenders the day before). Assume that the attackers leave $x$ defenders alive but do not destroy the castle; then
$$a_{i+1} = a_i-x;$$
$$d_{i+1} = dpw+x;$$
$$s_{i+1} = s_i-(a_i-(dpw-x)) = (s_i+dpw)-(a_i+x).$$
On day $i+1$, the defending force is larger than on day $i$ and the attacking force is smaller than on day $i$. Furthermore, even if the attackers return to the strategy of wiping out the defending force on day $i+1$,
$$a_{i+2} = a_i-x;$$
$$d_{i+2} = dpw;$$
$$s_{i+2} = s_{i+1}-(a_{i+1}-d_{i+1}) = s_i+2dpw+x-2a_i.$$
If, instead, the attackers had wiped the defending force on day $i$, the castle's strength would be $s_i+2dpw-2a_i$. Therefore, it is never advantageous to leave both defenders and the castle alive on the same day.
(Note that if $s_i+2dpw+x-2a_i<0$ -- that is, they destroyed the castle on day $i+1$ -- they could have have done the same thing without losing troops; therefore, while it might not always be disadvantageous, it is never advantageous.)

Now the question is, when the attackers do destroy the castle, how many days will it take to kill the remaining defenders (with the obvious assumption that the attackers would not make a final push on the castle unless they can still win)? Assume, without loss of generality, that the castle is destroyed on day $q$ and that there are $x$ defenders remaining alive. So
$$d_{q+1} = x;$$
$$a_{q+1} = n-x;$$
$$d_{q+2} = d_{q+1}-a_{q+1} = 2x-n;$$
$$a_{q+2} = a_{q+1}-d_{q+2} = 2n-3x;$$
$$d_{q+3} = d_{q+2}-a_{q+2} = 5x-3n;$$
$$\dots$$
From this we can see that $d_{q+i+1} = Fib(2i+1)x-Fib(2i)n$. Therefore, (finding the closed form of $Fib(\cdot)$ and four pages of algebra later), the attackers will win
$$k = \left\lceil\frac{\log_\phi{\left(\frac{n+x\phi^{-1}}{n-x\phi}\right)}}{4}\right\rceil$$
days after destroying the castle. $x = s'+dpw-n$, where $s'$ is the strength of the castle on the day it is destroyed.

On every day that the attackers can make a final push on the castle, the question is, "Would it be advantageous to wait until tomorrow?" Every day (after the first) that the attackers do not make a final push, the castle's strength decreases by $n-dpw$. Therefore, at the beginning of the day of the final push (day $i$), $s' = s-n-(i-1)(n-dpw)$, so $x_i = dpw-(n-s') = $ $s + i\cdot dpw-(i+1)n$ (where $x_i$ is the remaining defending force if the attackers pushed on day $i$). It is advantageous to wait another day if
$$
\frac{\log_\phi{\left(\frac{n+x_{i+1}\phi^{-1}}{n-x_{i+1}\phi}\right)}}{4} + 1
<
\frac{\log_\phi{\left(\frac{n+x_i\phi^{-1}}{n-x_i\phi}\right)}}{4},$$
that is, when one more than the number of days to destroy the $x$ beginning on day $i+1$ is less than the number of days to destroy $x$ beginning on day $i$. Three pages of algebra later, we find that it becomes advantageous to destroy the castle on the day
$$c = \left\lceil\frac{\sqrt{dpw^2+4 n\cdot dpw}-dpw+2 n-2 s}{2 (dpw-n)}\right\rceil.$$

After destroying the castle, we still have to kill the troops, so the total number of days is $c+k$, using $i=c$ to find $k$.

Finally, we must handle the edge case that $dpw \geq n$. Intuitively, the attackers can only be victorious only if they can destroy the castle on the first day of fighting (day 2) with enough troops left to defeat the remaining defenders. This can only happen if $s<2n$ (they can destroy the castle by the end of the second day) and if $s+dpw<(\phi+1)n$ (they can destroy the castle and do enough damage that the defenders cannot effectively retaliate); it will take $\left\lceil\frac{\log_\phi{\left(\frac{n+(dpw+s-2n)\phi^{-1}}{n-(dpw+s-2n)\phi}\right)}}{4}\right\rceil$ days to kill the rest of the defenders.


TSP is actually OptP-complete and so are many other optimization problems, including Knapsack, MAX-SAT, 0-1 Integer Linear Programming. This class and proof technique is largely the work of Mark Krentel; orig paper STC'86. The journal version of the paper has more details, including the fact that OptP is subclass of FPNP.

LEX-MIN-SAT, finding the lexicographically smallest satisfying assignment, is OptP-complete under metric reductions. There's also an analogue of Schaefer's dichotomy theorem
for LEX-MIN-SAT proved by Reith and Vollmer http://arxiv.org/pdf/cs/9809116.pdf

I think is almost a research-level, or at least graduate-level question, by the way.