Difference between an a microcontroller and a system on a chip?

The microcontroller definition is, at best, poorly worded.  The distinction between an SoC and a microcontoller may be a bit fuzzy, but not that fuzzy.  A microcontroller might be included as one element of an SoC, but it is not an SoC.

SoC means (approximately) "single chip solution."  The SoC in a cell phone might have a 32-bit ARM processor running Linux (Android) and any apps that the user has installed.  In addition it would have a GPU, the wireless transceiver and modem, the video and audio decoders for streaming video, GPS, controllers for the accelerometer, controllers for battery management, and who knows what else.  There might be many microcontrollers in a SoC.

The "peripherals" included on the microcontroller itself are going to be a lot less specific.  They are really registers for communicating with the off-chip devices (or at least off-module, if the microcontroller is embedded in an SoC) that you are controlling with the microcontroller.  The peripherals might include some analog-to-digital or digital-to-analog converters, and/or a USB controller and/or I2C bus controller.

More often than not the microcontroller will be running a single program (no operating system, no apps), and that program will be stored in a read-only-memory (Flash).  (Usually the flash memory is included in the same chip as the microprocessor.)

As an example.  Here's the specs for the Microchip PIC16F77:

  This powerful (200 nanosecond instruction execution) yet easy-to-program (only 35 single word instructions) CMOS FLASH-based 8-bit microcontroller packs Microchip's powerful PIC® architecture into an 40- or 44-pin package and is upwards compatible with the PIC16C5X, PIC12CXXX and PIC16C7X devices. The PIC16F77 features 8 channels of 8-bit Analog-to-Digital (A/D) converter with 2 additional timers, 2 capture/compare/PWM functions and the synchronous serial port can be configured as either 3-wire Serial Peripheral Interface (SPI™) or the 2-wire Inter-Integrated Circuit (I²C™) bus and a Universal Asynchronous Receiver Transmitter (USART). All of these features make it ideal for more advanced level A/D applications in automotive, industrial, appliances and consumer applications.

It also has 14KB of flash to store the program and 368 bytes of RAM.  (Yes you read that right, bytes.)


How hard is finding restricted assignment of 3-SAT satisfying $7/8$ of the clauses?

The PCP theorem states that for every $\delta > 0$, it is NP-hard to decide whether a 3CNF is satisfiable or at most $(7/8+\delta)$-satisfiable. Take such a formula $\varphi$ and add to it lots of copies of $(a \lor b \lor c) \land \cdots \land (\lnot a \lor \lnot b \lor \lnot c)$, where $a,b,c$ are new variables (by $\cdots$ I mean eight clauses, exactly seven of which are always satisfied). Suppose these clauses take up $(1-\epsilon)$ of the new 3CNF. This replaces the original $1$ vs. $7/8 + \delta$ to $\epsilon + (1-\epsilon)7/8$ vs. $(7/8+\delta)\epsilon + (1-\epsilon)7/8$, that is $7/8 + \epsilon/8$ vs. $7/8 + \delta\epsilon$. That's not exactly what you wanted since $\delta \neq 0$, but it's pretty close.


Showing that the set of DTMs that run forever is not Turing-recognizable

This is not the halting problem, the halting problem is the set of TMs that do halt, the language $A$ is the set of TMs that don't halt. It's the complement of the halting problem.

You also seem to be mistaken in that the halting problem is recognizable, it's just not decidable.


How is Turing's Solution to the Halting Problem Not Simply "Failure By Design"?

In what follows, I'll distinguish a machine $M$ from its description, denoting the description of $M$ by $\langle M\rangle$.

Specification of the halt tester program, $H$

  $H$ takes as input a pair $(\langle M\rangle, i)$, where $\langle M\rangle$ is the description of machine $M$, and $i$ is the input required by $M$.

  $H$ halts on any input pair $(\langle M\rangle, i)$ and returns the correct answer, namely:

  $H(\langle M\rangle, i)$ returns true if and only if $M$ halts on input $i$.

Now, assuming that there is such a machine $H$, we can use $H$ as a subroutine to construct a program $P$ as follows:

Specification of the "perverse" program $P$

  $P$ takes as input a description, $\langle M\rangle$, of a machine $M$.

  $P$ works correctly on any input $\langle M\rangle$, namely

  $P(\langle M\rangle)$ halts if and only if $M$ doesn't halt when given input $\langle M\rangle$.

The key to this argument is that if we can define a machine $H$ that satiffies the specification above, then we can build a machine $P$ that satisfies the second specification.

However, $P$, when given $\langle P\rangle$, exhibits impossible behavior,

$\qquad\qquad\qquad P(\langle P\rangle)$ halts if and only if $P(\langle P\rangle)$ doesn't halt.

So $P$ fails to meet its second requirement on at least one input and consequently it must be the case that $H$ cannot satisfy its requirement, so consequently we cannot make $H$ as specified.

Now $H$ might very well behave as specified on lots of inputs $(\langle M\rangle, i)$, but the point is that no halt tester can be built that works on all possible inputs.


Is there an equivalence between "does this program halt" and "is this sentence provable"?

If a Turing machine halts on a given input, then you can prove this in any reasonable propositional proof system. The idea is to list the halting sequence of configurations of the Turing machine, and prove, one by one, that these are the configurations encountered by the Turing machine when run on the given input.

In the other direction, if a sentence is provable in a reasonable proof system, then the Turing machine which goes over all proofs in the system and checks whether they prove the sentence, will halt, and its halting implies that the sentence is indeed provable in the proof system.

What this shows is that Turing machines with an oracle for the halting problem have the same power as Turing machines with a provability oracle for any reasonable proof system.


What about using a "goal" variable initialized to NIL and taking as invariant "After iteration i, the goal variable contains an index $0 \leq j < i$ such that $A[j] = v$ if there exists one (in the range $\{0, \cdots, i - 1\}$), or NIL otherwise" ?


Myhill-Nerode classes for a Language $L_k = \{x1y | x \in \{0, 1\}^*, y \in \{0, 1\}^{k-1}\}$

First, I think you have to review the Myhill Nerode Theorem and its relationship to the states of finite automata. You seem to think the number of equivalence classes is the same as the number of states in the minimal NFA, but it's actually the same as the number of states in the minimal DFA.
As a side note, minimization of NFAs is apparently much trickier than minimization of DFAs, so in an introductory formal languages class, you're not going to hear much about minimal NFAs (except in cases like this, where it's straight forward).
So this means it's parts (a) and (b) that are closely related.
As this is a worksheet question, I'll try to only give a guiding hint, rather than a straight-out answer.
The key thing (at least in my opinion) is to realise that each language $L_{k}$ is that it is only really concerned with the last $k$ symbols in the string. So the number of equivalence classes is closely related to this, and the proof that the obvious guess here works is informed by this observation.
This same observation is what gives the minimal DFA (unsurprisingly, as the equivalence classes exactly correspond to the states!). As the DFA doesn't know when the end of the string is coming up, one way you can think of it is as a little sliding window algorithm, and you should be able to relate the states, transitions and equivalence classes in terms of moving this window along one symbol.
To get the minimal NFA, lean on the nondeterminism. What is the piece of information that the DFA doesn't have that you can just nondeterministically guess?


Matrix Chain Multiplication Greedy Approach

You don't state why you think that your algorithm is correct. In fact, it is incorrect. Here is an example. Consider the problem of computing the product of matrices of dimensions $2\times 1$, $1\times 2$, $2 \times 5$. Your algorithm first multiplies the first two at a cost of $4$, and then multiplies the remaining matrices at a cost of $20$, to a total of $24$. In contrast, the other option has complexity $10 + 10 = 20$.

According to Wikipedia, Hu and Shing came up with an $O(n\log n)$ algorithm, which is more efficient than your algorithm, and moreover is provably correct.


Best starter resources for learning about AI

Artificial intelligence is vast.

A seminal paper by Marvin Minsky (1963) will be best place to start. I consider it to be a fundamental resource. Minsky wrote this paper in 1963, and set the foundations of much of the modern terminology of AI.

Minsky, Marvin. "Steps toward artificial intelligence." Proceedings of the IRE 49.1 (1961): 8-30.

Books

"Artificial Intelligence: A Modern Approach" by Russell and Norvig
Overview of constraint programming "Principles of Constraint
Programming by Krzysztof Apt".
Advanced book "Foundations of Statistical Natural Language Processing
by Christopher D. Manning and Hinrich Schuetze".
Machine learning methods  "Machine Learning by Tom M. Mitchell".
Intelligence by Jeff Hawkins and How to Create a Mind by Ray Kurzweil
The Emotion Machine by Marvin Minsky
Artificial Intelligence: A Modern Approach by Peter Norvig and Stuart
J. Russell
Artifical Intelligence - A Modern Approach by Russell and Norvig
Sciences of the Artifical by Herb Simon
"INTRODUCTION TO MACHINE LEARNING" from Nils J. Nilson
"An Introduction to Neural Networks" from Ben Krose and Patrick
van der Smagt
"Information Theory, Inference, and Learning Algorithms" part V, from
David J.C. MacKay

Online material

Recommend blog The AI Revolution: Road to Superintelligence - Wait
But Why
Coursera
Udacity
20 free books to get started with Artificial Intelligence
The AI Programmer's Bookshelf
Artificial Intelligence: Foundations of Computational Agents
Deep Learning

Language (my prioritizes)

Python
Java

Open Source Software Library

Google's TensorFlow
Theano
Microsoft's CNTK
Facebook's Torch
DL4J
Caffe


If a DFA were implemented as a circuit, what would the empty string correspond to as input?

Deterministic automata over finite words (DFAs) that accept or reject a given word can be seen as finite-state machines that read elements from some alphabet $\Sigma$ and output elements from the output alphabet $\mathbb{B}$ that represent whether the word read so far is accepted by the original DFA.

Translating such finite-state machines to circuits is a classical topic in technical computer science. For instance, you could assign a bit-vector of the same length to every state and then use the Espresso logic minimizer to compute a relatively efficient circuit. Note that such circuits have memory.

Such finite-state machine come in two variants: Mealy and Moore machines. Both of them operate in discrete steps. At every step of their computation, Mealy machines first read an input character and them produce an output character. For Moore machines, it is the other way around: they first produce their output character and then read the next input character.

The answer to your question now depends on which model you use: If you translate your DFA into Moore machine form, the machine first outputs whether the word seen so far is accepted and only then looks at the next character. In the first step of its computation, it thus outputs whether the empty word is accepted. Mealy machines read the respective next character in every step and only then produce the next output. Thus, whether the empty word is accepted by the original DFA cannot be observed when looking at a run of the Mealy machine (unless you do the translation in a way that the machine always delays its output by one step, which normally increases the number of states by a factor of at most two).

The model that Yuval Filmus was referring to in his comments is one that is used in circuit complexity. There, it is looked at how large circuits need to be that categorize inputs of a fixed length into accepted and non-accepted ones. The characters of the input words are all read at the same time in this model and the circuits do not have memory.


How does a co-NP problem differ from an NP (its complement) one?

A co-NP problem differs from its complementary NP problem exactly by being its complement! That's the whole story.

  NP problems should accept YES instances -> instances where the answer is yes.

I think you've confused yourself. Every problem, of any complexity, is a division of all possible instances into "yes" instances and "no" instances. For TSP, the "yes" instances are the maps where the salesperson can visit all the cities within the distance requirement and for co-TSP, the "yes" instances are the maps where the salesperson can't (i.e., the "no" instances of TSP).

What differs between complexity classes is the amount of resources and model of computation that are required to tell the difference between a "yes" intance and a "no" instance. For NP, we use a nondeterministic Turing machine running for a polynomial number of steps and say that the machine accepts if at least one computation path accepts, and rejects otherwise. For co-NP, we do the opposite: the machine rejects if at least one computation path rejects, and accepts otherwise.


For MAX-SAT:

The optimization problem is, given a CNF, to find the maximal number of clauses that can be satisfied at once.
The search problem is, given a CNF, to find an assignment satisfying the maximal number of clauses.
The decision problem is, given a CNF and a threshold $k$, whether there is an assignment that satisfies at least $k$ clauses.

To reduce from search to optimization, use the self-reducibility of SAT: pick a variable $x$, and try substituting $x=0$ and $x=1$, using your optimization oracle to determine which of these partial assignments leads to an assignment satisfying the maximum number of clauses.


The subset sum problem is not in P because the question is about lossy compressed data? Why not?

The subset sum problem is quite different from your problem: Given a list of integers and a target sum $S$, it asks if there is a subset of the list that sums to $S$. No "compression", lossy or not. Any lossy technique will (by definition) tend to miss the target (because it works with an approximation). And we are looking for an exact solution, not one that is 10% off, it has to be right on.
It looks to me that the collection of subsets for which you need to compute the sums is even larger than the numbers in the original list. If so, it isn't any speedup.


Example of an algorithm that lacks a proof of correctness

Here is an algorithm for the identity function:

Input: $n$
Check if the $n$th binary string encodes a proof of $0 > 1$ in ZFC, and if so, output $n+1$
Otherwise, output $n$

Most people suspect this algorithm computes the identity function, but we don't know, and we can't prove it in the commonly accepted framework for mathematics, ZFC.


Find minimum number of time points that cross out all intervals

Hint:

   Try some more greedy algorithms; keep trying, and don't give up yet.  You might try solving some small examples by hand, to get some intuition for what is going on, and see what strategies you end up developing.  The way to look for a greedy algorithm is to try all greedy strategies you can think of -- it's not enough to just try one particular strategy and if that doesn't work give up on the entire paradigm of greedy algorithms.

This looks like a nice learning exercise, so keep at it.  You can do it.  (We're glad to help you understand concepts but just solving this exercise for you probably won't help with that.)


Tilting your head a few degrees to the side doesn't cause Viola-Jones face detectors to fail.  They are more robust than that.  I suggest trying some experiments to see for yourself.

As an aside: It's not always possible to rotate an image to the extent one might like.  You have a 2D representation of a 3D object.  As an extreme case, imagine trying to take a photograph and simulate rotating the face by 180 degrees around the vertical axis.  You can't, because that would require knowing what the back of their head looks like.  Even tilting around a horizontal axis has limits; imagine trying to tilt by 180 degrees -- which would require simulating the effect of your hair pointing in a different direction.  So while it may be possible to simulate rotation to a limited extent, but there are limits to what kind of synthetic rotation is possible.


How solve this recurrence: T(n) = 2t(n-1) - t(n-2) +5n +7

According to your recurrence equation  2t(n-1) futher breakdown like 2[2t((n-1)-1)+t((n-1)-2)+5(n-1)+7] and for solution of this equation explore
recurrence equation solution


Hardware protection needed for operating system kernel

The answer is actually none. This is not what your teacher expects in this homework assignment, but it's true.

The problem in process isolation is to protect against processes that try to access resources that they should not (resources that are used by other programs or by the operating system itself). Resources include memory and peripheral devices.

You can design an operating system that verifies all programs before running them, and only runs a program if it can prove to its satisfaction that the program will never attempt to access a resource that it is not allowed to access. Such operating systems are not very common, but they exist, for example some smartcards running Java Card work like this: only Java bytecode applications can be installed on the card, and they have to have been checked and passed by a bytecode verifier.

That being said, most operating systems enforce process isolation by leveraging hardware means. The most important part is the memory protection unit: a hardware component that assigns privilege levels to blocks of memory and ensures that only programs with the appropriate privilege level can access each block. Often memory protection is performed by a memory management unit which combines protection with virtual memory management, but the indirection afforded by virtual memory is not necessary for the protection aspect. There are processors with an MPU but no MMU. The uClinux project is an example of operating system which enforces process isolation and runs on processors with only an MPU.

In order to be of any use, the MPU has to be combined with some mechanism that assigns privilege levels to programs. Most CPU types that allow privilege isolation have at least two modes (sometimes more), which I'll call kernel and user, with kernel being the most privileged. At any time, the CPU is in one mode or the other. The CPU boots in kernel mode.  Switching into kernel mode from user mode always causes a jump to a fixed address. That way, the initial program that is loaded at boot time remains in control of what can be executed in kernel mode. It is up to that program to set up the MPU/MMU so that other programs cannot overwrite kernel code or access peripherals directly, thus enforcing isolation between kernel code and user code. The kernel is also responsible for changing MPU/MMU settings when switching between programs so that programs can only access their own memory and not other programs'.

That's two mechanism. I don't know what your teacher had in mind for the third one.


greedy algorithm for Maximum directed cut

The starting point is the trivial random algorithm that chooses $S$ completely at random. Each directed edge is cut with probability $1/4$ (why?), and so in expectation, this random algorithm gives a $1/4$ approximation.

We can derandomize this algorithm using the method of conditional expectations. Arrange the points in order: $1,\ldots,n$. At step $i$, we know which of $1,\ldots,i-1$ are in $S$ and which are in $\bar{S}$. If we put $i \in S$, then we can compute the expected cost of the output given that all further choices are made randomly; and we can do the same if we put $i \in \bar{S}$. One of these choices cuts at least $1/4$ of the edges (in terms of weight), and this is the one we choose.

We can further optimize this algorithm. Consider the following two expressions:
$$
A = \sum_{\substack{j<i\\j\in\bar{S}}} w_{ij} + \frac{1}{2} \sum_{j>i} w_{ij}, \\
B = \sum_{\substack{j<i\\j\in S}} w_{ji} + \frac{1}{2} \sum_{j>i} w_{ji}.
$$
(Here $w_{ij}$ is the cost of the edge from $i$ to $j$.)
If $A>B$ then the derandomized algorithm puts $i$ in $S$, whereas if $A<B$ it puts $i$ in $\bar{S}$ (if $A=B$ it doesn't matter). We can perhaps think of this algorithm as a greedy algorithm.

As an aside, the so-called double greedy algorithm gives a $1/2$ approximation algorithm. The greedy algorithm you suggest in the comments is good in combination with the random algorithm: if you run both and choose the better solution, you get a $2/5$ approximation (see Feige's paper). The semidefinite relaxation gives the (probably) optimal approximation ratio, which is roughly 0.874.


Always think of boundary cases. In this case - the languages that contain every string or no string.

Also, let $N$ be some arbitrary non-regular language.

i) The language that contains no strings, which is regular, is a subset of $N$.

ii) $N$ is a subset of the language that contains all strings, which is regular.

iv) For every string $S_i$ in $N$, construct a set $L_i$ that contains only $S_i$. Note that all of these constructed sets are trivially regular. But the union of all of these (infinite number of) constructed sets is $N$, which is not regular.


Yes and no.

A function $f(n)$ is said to be $O(g(n))$ if there exists a constant $c$ such that

$$
\lim_{n\rightarrow \infty}\dfrac{f(n)}{g(n)} \leq c
$$

Knowing this, a few things immediately become apparent:

Addition and subtraction preserves the largest $O$ of the result, thanks to the properties of limits.

For instance, $f(n) \pm h(n)$ are $O(g(n))$ if both $f$ and $h$ are
individually $O(g(n))$.

This is why you can say, if two operations are $O(n)$, then the resulting sum/subtraction is also $O(n)$.

If either $f$ or $h$ were $O(n^{2})$, then the result would be $O(n^{2})$. This is in agreement with intuition.
A function that is $O(n)$ is also $O(n^{2}), O(n^{3})$, etc. as you can prove by this definition.

For practical purposes, that is immaterial, as you only usually care about the smallest upper bound.
Multiplication can be simplified in the manner you require.

For instance, say I have $f, h$ that are both $O(n)$. This means

$$
   \lim_{n \rightarrow \infty}\dfrac{f(n)}{n} < c\;\;\mathrm{and} \; \; \lim_{n \rightarrow \infty}\dfrac{h(n)}{n} < c
   $$

or, equivalently,

$$
   \lim_{n \rightarrow \infty} f(n) < \lim_{n\rightarrow \infty} cn\;\;\mathrm{and} \; \; \lim_{n \rightarrow \infty}h(n) < \lim_{n\rightarrow \infty} cn
   $$

I can then argue that $f \times h$ is $O(n^{2})$, since, when we go to calculate it, this would require:

$$
       \lim_{n\rightarrow \infty}\dfrac{f \times h}{n^{2}} < c
   $$

which we can prove like so by substituting the inequalities above:

$$
       \lim_{n\rightarrow \infty}\dfrac{f \times h}{n^{2}} < \lim_{n\rightarrow \infty} \dfrac{cn \times cn}{n^{2}} < c^{2}\;\;\mathrm{which\;is\;a\;constant!}
   $$

In general, the product of two polynomial operations of order $O(n^{k}), O(n^{p})$ is at least $O(n^{k+p})$.
Division is a bit trickier. Let's take your example: say we have $f, h$ both $O(n)$.

We now try to calculate the limit, using the properties formally stated above, and find:

$$
   \lim_{n \rightarrow \infty}\dfrac{\frac{f}{h}}{n} < \lim_{n \rightarrow \infty} \dfrac{\frac{cn}{cn}}{n} < lim_{n \rightarrow \infty} \dfrac{1}{n} = 0 < c
   $$

so it is $O(n)$.

But wait a minute! It is also $O(1)$:

$$
   \lim_{n \rightarrow \infty}\dfrac{\frac{f}{h}}{1} < \lim_{n \rightarrow \infty} \dfrac{\frac{cn}{cn}}{1} < lim_{n \rightarrow \infty} \dfrac{1}{1} = 1 < c
   $$

so the same operation is somehow both $O(1)$ and $O(n)$ at the same time.

No, this is not some quantum spookiness at work. Remember that a function that is $O(n^{c})$ is also $O(n^{k})$ if $k > c$, as we stated above. Correctly speaking, it is not wrong to say either $O(1)$ or $O(n)$ or any other higher power (excluding deities).

In such cases, you may want to use the much stronger $\theta$ definition, which says a function $f$ is $\theta(g(n))$ if $f(n)$ is $O(g(n))$ and $g(n)$ is $O(f(n))$ i.e. they grow at the same pace.


Primality testing is not of the form $\text{SAT}(S)$ for a finite set $S$ of finite-arity relations over the Boolean domain.  Thus, it's not covered by Shaefer's theorem, and Shaefer's theorem says nothing about the hardness of primality testing.  See this answer: https://cs.stackexchange.com/a/43831/755.

See also Why does Schaefer's theorem not prove that P=NP? for a more detailed explanation.


Empirical evidence for the Church-Turing thesis in other disciplines

Proof is an inherently mathematical concept. "Effectively calculable function" has no definition in mathematics and you can't prove something that doesn't have a definition.


Does precedence matter in constructing parse trees of arithmetic expressions for postfix notation?

What you're missing is the associativity of operators. All operators you mention in your examples are binary. An expression of the form $A + B + C + D$ is interpreted by the parser as $(((A+B)+C)+D)$. When converting such a fully parenthesized expression into prefix form, we apply the rule $(\alpha + \beta) \to +\alpha\beta$. Denote this transformation by $T$. Then
$$
T[(((A+B)+C)+D)] = +T[((A+B)+C)]D = ++T[(A+B)]CD = +++ABCD.
$$
In a completely analogous way, the operator $S$ converting into postfix makes the transformation $S[(\alpha+\beta)] = \alpha\beta+$:
$$
S[(((A+B)+C)+D)] = S[((A+B)+C)]D+ = S[(A+B)]C+D+ = AB+C+D+.
$$

The operator $+$ is associative, but imagine what happens with an operator like $-$. The expression $A-B-C$ is interpreted as $((A-B)-C)$, and its prefix and postfix forms are $--ABC$ and $AB-C-$, respectively. Any other conversion would result in an arithmetically inequivalent expression. That's why associativity matters.

Most operators associate to the left, just like $+$. Exponentiation traditionally associates to the right.

On top of this, we also have operator precedence, which leads to the parsing of $A+B*C+D$ as $((A+(B*C))+D)$. If you apply the transformations $T$ and $S$ you will get the expressions given in the book.


Are type abstraction values and universal types not for non functions, but only for functions?

Short Answer: In λX₁. λX₂. ... λXₙ. t it doesn't matter if t is not a function, but if so, it may not be an interesting example for introduction.

Long Answer:

First of all, technically speaking, the type system defined in Figure 23-1 does NOT have any base types such as Bool or Nat. A type of t in λX. t is either a type variable X, a function type T → T, or a universal type ∀X. T.

Section 23.4, however, takes Nat as an example. So let's consider an extended type system by adding some base types and its values, terms, typing rules, etc. like Section 11.1 does.

Then we can consider, for example, a term λX. 42. This is a well-typed term. Proof:

\[
  \cfrac{}{
  \cfrac{\mathrm{X} ⊢ \mathrm{42} : \mathrm{Nat}}{
  ∅ ⊢ \mathrm{λ X. 42} : \mathrm{∀ X. Nat}
  }}
\]

This term, however, is not very interesting; polymorphism doesn't play any important role here.

Also, we can consider a type ∀X. X. But there is no term of type ∀X. X (i.e. there is no inhabitant of ∀X. X). This can be proved through the Curry-Howard correspondence. But this example may not be suitable for introduction of System F.

Section 23.7 writes a bit more interesting example. If we extend the type system by adding errors, we can consider a term λX. error. This term doesn't throw an error during an evaluation because of the type-abstraction. This observation gives an idea of a new type erasure method, described in Section 23.7.


How to solve a recurrence when the master theorem fails?

You can explicitly unroll the recursion:
$$
\begin{align*}
T(n) &= \frac{1}{n} + \frac{1}{2} T\left(\frac{n}{2}\right) \\ &=
\frac{1}{n} + \frac{1}{n} + \frac{1}{4} T\left(\frac{n}{4}\right) \\ &= \cdots \\ &=
\frac{m}{n} + \frac{1}{2^m} T \left(\frac{n}{2^m}\right).
\end{align*}
$$
This easily leads to the solution
$$T(n) = \frac{\log_2 n + T(1)}{n},$$
which is valid for powers of 2.


A lambda calculus evaluation involving Church numerals

I think your reduction is correct (I've only eyeballed it, though). At the end, you can't apply $(\lambda z. s s s z)$ to $z$, this never appears in the term. $\lambda z. f f z$ is $\lambda z. (f f) z$, not $\lambda z. f (f z)$. Functions in the lambda-calculus take a single argument; they are effectively curried: a two-argument function is implemented as a one-argument function that takes the first argument and returns a new one-argument function that takes the second argument and returns the result.

You made the same mistake when defining Church numerals. The Church numeral for $n$ is based on composing a function $n$ times. “The function $s$ applied $n$ times to the function $z$” $\lambda s. \lambda z. s (s ( … s \: z) … ))$. What you wrote is the function $s$ applied $n-1$ times to the function $s$ and finally to $z$, which doesn't strike me as a useful term.

$2 \times 3$ is thus $(\lambda m n s. m (n s)) (\lambda s z. s (s \: z)) (\lambda s z. s (s (s \: z)))$. I'll let you check that it does reduce to $\lambda s z. s (s (s (s (s (s \: z)))))$.


Quantum algorithms and quantum computation

This is more-or-less a reasonable description of quantum computation. A few remarks are in order:

Regarding "quantum parallelism":

  Quantum computers can process a massive amount of operations in parallel [...]
  Yet when we measure the qubits all the possible states collapse into a single state of either $|0\rangle$ or $|1\rangle$, which seems to negate the potential benefits of parallel operations. All we really know are the probabilities that the states will end up as.

This description, as it stands, applies equally well to randomized computation. We don't assume that random bits have any special sort of state-space, of course — we can just flip coins rather than having to carefully manipulate ions, or photons, or what-have-you — but the mathematics behind probability distributions and quantum states are nearly identical. (Try out some computations involving probability vectors some time, replacing the unitary transformations with stochastic transformations.)
Regarding "quantum properties":

  However, we can exploit quantum properties to increase the probability that we end up with a certain result. I believe Shor's algorithm is based on exploiting quantum properties too [...] e.g. in a quantum walk, quantum interference means the walk spreads faster than a classical random walk and hence can out-perform classical walks.

We do increase the probability that we observe a given result — but this is a consequence of the fact that we decrease the probability of seeing unhelpful outcomes. Classical probability distributions "interfere constructively" too, though we just call it cumulated probability — one thing which is special to quantum computation is the fact that destructive interference (partial or total cancelling of amplitudes) occurs.

This can be seen as one of the reasons why quantum computation is more powerful: the existence of amplitudes which would cancel if you simply added them, means that amplitudes sometimes do cancel when the computation calls for transitions involving both of those amplitudes.
This is something which simply doesn't happen with probability distributions — in fact, it doesn't even happen in nondeterministic Turing machines.

The trick, of course, is to find the particular ways in which you can conspire to have unhelpful outcomes partially cancel (or indeed, to determine which outcomes could be helpful to you, in order to arrange for the other outcomes to cancel). Simply recognising that amplitudes can possibly cancel is not in itself enough to figure out how to compute more quickly.
Regarding Shor's algorithm:

  I believe Shor's algorithm is based on exploiting quantum properties too, although I'm not sure in what way?

Shor's algorithm is an example of an algorithm which uses the quantum Fourier transform (or QFT), a unitary transformation which broadly speaking is helpful to find/expose periodic patterns. The fact that it can be performed unitarily means that certain simple periodic patterns which would otherwise be difficult to determine in a small number of trial calculations can be quickly discovered by looking at bulk properties.

Using QFTs to expose periodic properties is one particular trick in the bag of quantum algorithms; there are others as well.


Given an amount of sets with numbers, find a set of numbers not including any of the given

I was thinking of representing it as a graph and then inducting it to the Max Independent Set problem

I think that´s a good start. The problem you are looking for is independent set but in hypergraphs instead of regular graphs.

The opposite of the independent set problem in hypergraphs is the vertex cover problem as it is in regular graphs. Well, that problem is equal to the hitting set problem: https://en.wikipedia.org/wiki/Vertex_cover#Vertex_cover_in_hypergraphs.

Something that i will do is:

Sepparate from the universe set all elements that doesn´t appear in a given set and insert those elements inside the solution set: In your example the number 8. So the universe will be $\{1, 2, 3, 4, 5, 6, 7\}$ and the solution set will be $\{8\}$
Transform the hitting set instance into set cover. We will have the following subsets in your example:  $\{1\}$ ,  $\{1, 2\}$ ,  $\{2, 4\}$,  $\{4,5\}$,  $\{5\}$,  $\{5\}$,  $\{3\}$.
We find the minimum hitting set and we pick the complement of the minimum hitting set, we add those elements to the solution set and we are done. In your example the minimum hitting set will be:  $\{2, 4, 7\}$. The complement will be $\{1, 3 ,5 ,6\}$. By adding the elements of the complement set to the solution set we have the solution to the problem.


The concept of a nil pointer is an implementation detail which is programming language specific. In some implementations, an attempt to accept the grandparent when there is none will just trigger an exception. This hints that the algorithm designer should not worry about nil pointers.

Indeed, in your example, the rotation function should simply not be called on a node with no grandparent. If you use the data structure correctly, then this will simply not happen. There are only two cases in which you would try to rotate a node without grandparent:

Implementation bug. You haven't coded the algorithm correctly.
Non-conforming usage. Your program for some reason calls the rotation procedure directly.

If your program is correct and it is used according to the interface of the data structure, then you will never attempt to rotate a node without a grandparent. Therefore if your code is attempting to dereference a nil pointer, you can be sure that there is some bug in your code. During development, you should probably raise an exception. For production code, you should follow whatever convention you do in any other part of your code.


Number of Hamiltonian cycles on a Sierpiński graph

Nice idea! The problem seems to be in step $(b)$. Replacing $(X_1,B,X_2)$ in an $N$-path by $(X_1,X_2)$ gives an $\bar{N}$-path, but not every $\bar{N}$-path will contain $(X_1,X_2)$. So this is not a bijection. This only says $N(n) \leq \bar{N}(n)$.

Or you can in fact show that $\bar{N}(n) = 3N(n)/2$, resulting in $N(n+1) = 3N^3$.


Finding longest subset arithmetic progression with given difference

Using a hashtable, you can solve this in $O(n)$ expected time, as follows:

Fill a hashtable $H$ with the given numbers.
Go over all numbers in the list. For each number $x$, if $x-D \notin H$:

Go over the numbers $x + D, x + 2D, x + 3D, \ldots$ until you find a number not in $H$.

The running time of the first step is $O(n)$. As for the second step, the potentially expensive step is the sub-step. However, in this sub-step we go over each element in the list at most once (we check $y$ only for $x = y-aD$, where $a$ is the maximal integer such that $y-aD \in H$), and so the second step takes $O(n)$ time.

Without using a hashtable but assuming that the list is sorted, we can solve this in $O(n)$ time as follows:

Go over all numbers in the list. For each number $x$, add an edge to $x+D$ if $x+D$ is in the list.
Go over all numbers again. For each number $x$, if there is no edge pointing at $x$, follows the path starting at $x$ and calculate its length.

Using two pointers, we can implement the first step in $O(n)$. (The first pointer points at $x$, the other one is looking for $x+D$.) The second step takes $O(n)$ time for the same reason as in the hashtable algorithm.

Since it takes $O(n\log n)$ time to sort the list, this solution runs in time $O(n\log n)$. Using the fast $O(n\log\log n)$ integer sorting algorithm, we obtain a solution running in time $O(n\log\log n)$.


Solving the min edge cover using the maximum matching algorithm

Assume, w.l.o.g., that G=(V,E) is a graph without isolated vertex. Let's denote by $\mathcal{A}$ the algorithm you describe in your question. We seek to prove that given $G$, $\mathcal{A}$ outputs a minimum edge cover. Before we do that, it can be benifical to make some simple observations. First, both edge cover and matching are set of edges, and the subset of an edge cover can be a matching. Given a minimal edge cover $C$(not necessarily the minimum), we denote by $M_C \subseteq C$ the maximum matching containing in $C$ . Note that $M_C$ is the matching of maximum size whose edges are all in $C$. We call any edge in $M_C$ the matched edge. We use $V(M_C)$ to denote the vertices of edges in $M_C$
Observation 1 Every vertex in $V\setminus V(M_C)$ must be covered by an edge which is incident to an edge in $M_{C}$. Otherwise we could find a larger matching in $C$.
Observation 2 Every edge in $C$ covers 1 or 2 vertices. Specifically, an edge in $M_C$ covers two vertices, an edge in $C\setminus M_C$ covers 1 vertex.
Theorem 1 $|V|=|C|+|M_C|$
Proof $\;$  By observation 2 and the definition of edge cover, we have $2|M_C|+|C-M_C|=|V|$.
By observation 1 we have that algorithm $\mathcal{A}$ outputs a minimal edge cover. Then he correctness of algorithm $\mathcal{A}$ is obvious from theorem 1:  when $|M_C|$ is maximized, $|C|$ is minimized since they sum to a fixed number $|V|$. In such situation, theorem 1 is called Gallai’s theorem


Is the verifier for an $NP$ and its $co-NP$ the same?

I think you might be slightly confusing your definition for co$NP$. To show that a certain graph doesn't contain a Hamiltonian path, you need to show that all paths in it aren't Hamiltonian, and providing a specific path as a "counter example" isn't enough.

In general, $coNP$ isn't defined using a witness the same way $NP$ is, because if it did than it would be the same as $NP$, and for now this is an open problem (we don't know if the two are equal, and they are usually believed to be different). Therefore, it doesn't really make sense to talk about a witness for a $coNP$ problem the same way you talk about a witness for an $NP$ problem.

Specifically, for a certain language in $coNP$ and a witness-based TM $M$ accepting it, $x$ is in the language iff $M$ accepts $(x,v)$ for all witnesses $v$. This is in contrast to a TM for a language in $NP$ that needs to accept only for a single witness.

I would like to add that for me, studying about the Polynomial Hierarchy using its witness-related definitions helped me understand $coNP$ better, but it isn't a necessity.


How to prove computational completeness of a variant of P system

When you have studied a lot of papers, as you say, then you must have seen how it works. You prove a system to be computationally complete by showing how your new system is able to simulate a Turing machine. Instead of a Turing machine you can use any computational model that in itself is computationally complete, like counter automata (register machines) for example.

In P system theory there are many variants, some work on strings, other on numbers. The model you choose to simulate ideally must match that domain.

So, you do not use "formal language" as such, but only the models studied by formal language theory.


Go-Back-N ARQ Protocol Throughput Question

Window size Ws is 5.
the time to transmit one frame is: tf=3000/2  Mbps=1.5ms
As the frame may be received in error with probability 0.7, each frame need to be transmitted 10/3 times on average. Then the time needed for successfully transmitting one frame is

tf+7/3*Wstf=

38/3*tf=19ms.

The effective rate is (3000-100)/19ms=152.6kbps.
ii)
1001 in binary is 9 in decimal. Frame 8 must have be received by the receiver and the ACK has been sent back to the sender. Therefore, frame 3 must not be included in sender’s window. As frame 9 hasn’t been received yet, 9 must be greater than or equal to Slast. Therefore, Slast can be any of these: 4 to 9 in decimal. Orin binary, 0100, 0101, 0110, 0111, 1000, 1001.


Kolmogorov complexity of string concatenation

Your conjecture is wrong. For some constants $C,D$, it holds that $K(sr) \leq 2K(s) + K(r) + C \leq 2K(s) + |r| + D$ (proof: use a universal Turing machine to generate $s$ and then $r$; you need somewhat more than $K(s)+K(r)$ to store both programs, though $2K(s)+K(r)$ is an overkill). Therefore if $2K(s) + D < |s|$, your conjecture doesn't hold. Such easy strings $s$ certainly exist, for example $K(0^n) = O(\log n)$.


Anyone knows an algorithm that finds minimum distance for all permutations?

Surprisingly, if the distance is $L_p$, or the $p$-norm induced metric, then you simply sort $A$ and $B$ respectively, and then compute their distance, and that distance will be guaranteed minimal over all permutations. That is time complexity of $O(n\log n)$ and I believe it is the most efficient one.

The key proof is done in https://math.stackexchange.com/questions/1984686/is-x-1-y-2px-2-y-1p-ge-x-1-y-1px-2-y-2p-for-any-0-le-x-1-le.

Sometimes, before setting out to find an "efficient" algorithm, it might be a good practice to first think of proving the "greedy" algorithm is not right; because if the greedy indeed works, all efforts to search for the "efficient" algorithm will be in vain.


Efficient insertion of deterministic acyclic finite state automaton (DAFSA) into a full-text search index?

There is (probably) no such algorithm. At least, for suffix tries it is not possible:
For every word encoded by the DAFSA there must be at least an end-of-word marker in the suffix tree. Thus, the construction takes at least $\Omega(N)$ where $N$ is the number of words encoded by the DAFSA.
This argument cannot be extended to any kind of search index because it may employ some kind of compression – like the DAFSA does.


Create a new node for each entrant, then put a pointer to each such node in a FIFO queue. Remove the two pointers $p_1, p_2$ in front of the queue, then create a new node with children $p_1$ and $p_2$, and enqueue a pointer to it. Repeat until the queue size is $1$. The one element you're left with is the root of a binary tree that encodes the bracket.


What happens when the xor inBlock chaining returns false?

Say you have blocks ABCDEA that you want to encrypt. If you do this naively, then the first and second A produce the same encrypted result, and an attacker would know that your first and last block are the same.

Instead you encrypt to A’B’C’ etc. by encrypting A -> A’, A’ XOR B ->B’, B’ XOR C -> C’, ..., E’ XOR A -> F’. It looks like you are encrypting random data, nothing an attacker can do.

The identical plain text blocks are XOR-ed with different previously encrypted blocks, that what’s making them different.


Two-head one way finite memory machine accepts non-regular languages

Just a "visual" Hint :-D

H1: v
    A A A B B B $
H2: ^

H1:   v
    A A A B B B $
H2: ^

H1:     v
    A A A B B B $
H2: ^

H1:       v        // found "B" ... let's
    A A A B B B $  // count both sides
H2: ^

H1:         v
    A A A B B B $  // ... go on ...
H2:   ^

H1:           v
    A A A B B B $  // ... go on ...
H2:     ^

H1:             v
    A A A B B B $  // H1 is on $, H2 on (the first) B ...
H2:       ^


Why the need for TSP solvers when there are SAT solvers?

TL;DR: polynomial reduction increases the size of a problem; using a specific solver allows you to exploit the structure of a problem.

When you reduce one NP-complete problem to another one, the size of the problem usually grows polynomially. For example, when you reduce a HAMPATH on a graph with $n$ nodes to SAT, the resulting formula has size of $\Theta(n^3)$ (I don't remember about the constant that arises in a straight-forward TSP->SAT reduction). If you use the Cook-Levin theorem, then the growth might be even bigger because a Turing machine might have really huge (polynomyal) overhead. NP-completeness is mostly a theoretical idea. So is a polynomial-time reduction. Many theoretical papers only state that there is a reduction, saying nothing about how practical it is.

Let's informally assume that TSP is as hard as SAT. It means that it takes similar computational resources to solve TSP on $n$ nodes and SAT with $n$ clauses if you use state-of-the-art solvers for each problem. Now it is easy to see that writing a separate solver is more practical than reducing the problem to SAT and using some existing SAT solver. It is all about polynomial overhead.

There is one more thing to notice: exact problems are usually simpler than broad ones. When you reduce TSP to SAT, the SAT solver knows nothing about the underlying structure of the formula. And special solvers for TSP, of course, deal with the fact that the input is a graph, the problem is to find a shortest Hamiltonian path, so on.

Although for some problems reduction to SAT can be reasonable, mostly if the problem is not well-studied (and no cool solvers exist) and when reduction doesn't increase the problem size a lot. SAT solvers are still very strong for many practical purposes.


How many node does the final B-tree have?

Every node contains between $\lceil(m/2)\rceil-1$ and $m-1$ keys (where m is the degree), so we can say that every node has between $\lceil(m/2)\rceil$ and $m$ children.
If we imagine to construct a minimun nodes b-tree, we'll have:
$n = 1 + 2  + 2\lceil m/2\rceil + 2\lceil m/2\rceil^2 + ... + 2\lceil m/2\rceil^{h-2}$where every addend is the number of nodes for every level, from the root (that can contains even one key), to the leaves level, and
where h is the height of the b-tree;
If you consider the series, you have $n=1+2 \frac{ \lceil m/2\rceil^{h-1}-1}{\lceil m/2\rceil-1}$.
Instead, if you consider the maximum number of nodes, you will have:
$n= 1+m+m^2+...+m^{h-1} =  \frac{m^h-1}{m-1}$.
where at the same way, every addend is the number of nodes for every level, and
where h is the height of the b-tree;
You can easily find the result if you substitute 2 instead of m in the formula.


Many device drivers do read/write to memory.  For instance, consider a network device; it reads the packets to be sent from memory and writes the packets it receives to memory.  Or think of a hard disk driver; it does something analogous.   So, ultimately, it will depend on the driver.

That said, device drivers often do have a portion of their internal state that can be thought of a state machine.  For instance, the states could be something like UNINITIALIZED, ACTIVE, SUSPENDED, where it is initially in UNINITIALIZED state on boot; after it initializes the device registers, it could transition to ACTIVE state; on suspend, it might put the device into suspend mode and switch to the SUSPENDED state, and so on.  This only accounts for part of the behavior of the device driver, but it can still be a helpful way to organize the driver.  Or, in other words: often, some important aspects of the driver's behavior or state can be thought of as DFAs even though that's only approximately true.


Canonical infinitely ambiguous languages

I think your understanding the use of "canonical" here as "standard example" is correct; similarly, grammars for parenthesis matching or palindromes are canonical examples for context-free grammars, generally.


What's the definition of a (deterministic) formal language?

Formal languages could (potentially) mean different things in different contexts. The Wikipedia page explains one sense, while your teacher might be referring to a different (and more informal) sense. You should probably not worry too much about the formal definition of formal language.

The point your teacher is probably trying to get across is that a human language has an undesirable feature: it doesn't always have an accurate denotation. For example, what do we mean by a "sad song"? This doesn't have an accurate denotation. Compare this to "a string of a's and b's", which does have an accurate denotation. This highlights the vagueness of human language. Another problem is polysemy: the same term can have several different meanings. For example, "formal language" can mean "a set of strings over an alphabet" (the Wikipedia meaning) or the more vague "a language in which each expression has a well-defined and unique meaning", which is closer to your teacher's.

In contrast, formal language defines everything in an unequivocal way. You'll see many examples of formal definitions in class, and hopefully the difference will become clear. But more importantly, you are not a philosopher, and so you shouldn't necessarily be able to explain the difference or to consciously identify which is which. Rather, you should understand that in some contexts we try to banish vagueness as far as we can, and present things in a "formal" and unequivocal way. In other contexts, say writing a newspaper article or a novel, we have different aims, but that kind of writing doesn't fit in a UML class.


The way to answer this kind of question is to simulate the algorithm with pencil and paper to see what it actually does.

Initially, we have dist[i][i] = 0 for all i, dist[0][2] = dist[2][3] = dist[3][1] = 1 and every other entry is infinite.

When we consider k = 0, nothing changes, since dist[i][k] = ∞ for all i except i = 0.

When we consider k = 1, nothing changes, since dist[k][j] = ∞ for all j except j = 1.

When we consider k = 2, we have dist[0][2] + dist[2][3] = 2 < dist[0,3] = ∞, so we set dist[0,3] = 2; nothing else changes.

When we consider k = 3, we have dist[0][3] + dist[3][1] = 3 < dist[0,1] = ∞, so we set dist[0,1] = 3; nothing else changes.

So the algorithm has correctly computed the shortest path from 0 to 1.

The point is that we're not really using dynamic programming based on the length of the intermediate path but on the highest-numbered vertex along that path.  Suppose you want to compute the shortest path from a to b. That path must pass through some highest-numbered vertex – call it c. Because that's the highest-numbered vertex on the path, we know that all the vertices on the paths a-c and c-b have lower numbers. So, in particular, by the time we reach the k = c iteration of the outer loop, we've already calculated all shortest paths between all vertices that use only vertices 0...c-1 as intermediate vertices. And that's enough information to calculate the shortest paths a-c and c-b and, hence, the shortest path a-b.


Answer to question 1:
If $2^n$ is the size of the page then there are $2^{13-n}$ pages.
We know that each page table entry is 2 bytes.
So size of the page table will be $2\times 2^{13-n}$ bytes because $2^{13-n}$ is the number of pages and each page has an entry in the page table.
They have given that page table takes at most one page to store.
So, $2\times 2^{13-n}=2^n \Rightarrow n=7$.

Answer to question 2:
Each page table entry is two bytes which is $16$ bits so the remaining bits other than the valid bits (protection bits and the dirty bit) are $16-5=11$ bits.
Page size is $512=2^9$ bytes.
Physical address space $2^{16}$ bytes.
Number of bits required to represent a page is $16-9=7$ bits.
So, the available bits to store the aging information is $11-7=4$ bits.


What I think they mean is that while you only have 4 cores to do computation on sometimes they will halt, pause, or "idle". When they do that the OS will run another thread on that core. As such you should be able to have 1 more thread to fill in the periods where a core is not doing anything.


There are two questions that you're asking here.

The first is why there is a light source. That's the easy part. Think what happens in the real world: if there's no light source, everything is dark and you can't see anything. That's an uninteresting case in computer graphics, so we usually don't consider it.

The second question is why rays are pointing to the light source instead of away from it. Physically, photons are emitted by light sources, and scatter around the physical environment, before hitting the imaging device (e.g. eye, camera).

It's possible to produce an image this way, like this for example:

Richard Keene produced this image in 1991. It was produced by tracing almost 30 billion photons from the light sources, which scattered around the scene until they hit the virtual camera lens. This took a month of compute time on 100 SPARCstations, each with 10MHz CPUs, and it's still quite noisy.

Keene repeated the experiment in 2004, this time using volunteers around the Internet donating computer time. I can't recall how long this one took, but 382 billion photons were traced in total:

The important thing here is that this technique is highly impractical. If you need to render an 85 minute movie at 24 frames per second, and allow a year of compute time, this turns out to be less than 5 minutes per frame. Clearly you can't spend 100 CPU-months on each image.

The problem is that if you trace photons from light sources, most photons don't hit the camera lens most of the time. If you continue scattering until they do hit the camera lens, they're usually so attenuated by that point that they contribute very little to the final image.

Ray tracing fixes this problem by tracing from the camera lens instead. Mathematically, a ray is the adjoint of a photon. This ensures that every trace contributes to the final image. However, you do then have the opposite problem. If you trace a photon from a light source, there's no guarantee that it will end up in the camera lens, but if you trace a ray from the camera, there's no guarantee that it will end up at a light source.

For this reason, most modern rendering algorithms (well, the ones that attempt to solve Kajiya's rendering equation) actually work in both directions. Photon mapping, bidirectional path tracing, and the Metropolis light transport algorithm (to pick but three) use information both from the camera and the light sources to try to spend most of the computer time on light paths which contribute to the final image.

If you're reading the book that I think you're reading, you'll get to all this in time.

EDIT Richard Keene himself chimed in, but unfortunately doesn't have enough rep yet to post comments on questions. So here's the link to his Photon Soup paper.

Richard, welcome to cs.se!


Incorporating newline-as-statement-terminator heuristics into context-free languages

The basic problem we have to solve is how to separate sequences of statements

(A)
statement1
statement2

from multi-line statements

(B)
state
ment

Dedicated separators such as semicolons are a time-honored way to do this clearly
but some people dislike them. An alternative is to require some kind of syntax
for triggering (B) (I think I've seen state \ \nment) which is likely to be
rejected for similar reasons.

So, one way to do this is to ensure that the set of statements is prefix-free,
that is no statement of the form (B) can parse as (A) ever. Of course, that is
rarely possible as you want to allow (improperly parenthesised) statements like

x = 3 - 2 + x

and at the same time blocks like

x = 3
- 2 + x
[returns 1]

Such languages (e.g. Scala) are inherently ambiguous on a syntactic level (without dedicated statement separators). On a semantic level, you may be able to resolve the ambiguity, e.g. you might figure out during name analysis that x is not initialised in reading (B) or during type analysis that the block should return an integer, which reading it as (B) may not do.

Needless to say that many dynamic languages don't even allow for this because all variables may be implicitly initialised or every statement returns something or what not.

In other words, I think this language "feature" is beyond the capabilities of PDAs if you don't want rigid precedences. You need backtracking, look-ahead,
semantic analysis and even guesswork.


This problem is NP-hard, meaning it's very unlikely that any algorithm exists that can solve every instance in polynomial (let alone linear!) time.  I'll show this by reducing the NP-hard problem Clique to this problem.  In Clique, we are given an undirected graph $F$ and a number $K$, and the task is to determine whether or not $F$ contains a clique (complete subgraph) with at least $K$ vertices.  The strategy will be to add universal vertices to $F$ -- that is, new vertices that are connected to all existing vertices -- and show that doing so grows the size of cliques in $F$, but does not grow the size of any other regular subgraphs in $F$.

Let there be $n$ vertices in $F$.  We will construct an instance $(G, k)$ of your problem from the given instance $(F, K)$ of the Clique problem:

$G$ is formed by adding $n+1$ new vertices to $F$ that are adjacent to each other and to every vertex in $F$.
$k = K + n$.

First we show that if there is a clique in $F$ of size at least $K$, then there is a regular subgraph with degree at least $K+n$ in $G$.  Clearly a clique of $K+n+1$ vertices can be formed by including the $K$ clique vertices in $F$ and all $n+1$ new vertices.  A clique containing $i$ vertices is regular with degree $i-1$, so this clique is regular of degree at least $K+n$.  Thus a YES answer to the given Clique problem implies a YES answer to the constructed instance of your problem.

Now we show that if there is a regular subgraph $H$ with degree at least $K+n$ in $G$, then there is a clique of size at least $K$ in $F$.  First observe that this $H$ must include at least one of the $n+1$ newly added universal vertices, since the largest degree obtainable using just the original $n$ vertices of $F$ is $n-1 < n+K$.  The following lemma is key:

  Lemma: If a regular graph $I$ contains a universal vertex, then it must be a clique.

  Proof: Let $c \ge 1$ be the number of universal vertices in $I$, and let $a$ be the number of other vertices.  Since $I$ is regular, it
  must be that every non-universal vertex has the same degree $c+d$ for
  some $d$ -- that is, removing the $c$ universal vertices from $I$ must
  leave a $d$-regular subgraph, which I'll call $I'$.  Again, since $I$
  is regular, we must have that the degree $c-1+a$ of each universal
  vertex in $I$ is equal to the degree $c+d$ of the other vertices.  But
  this implies $a-1=d$, i.e., $I'$ is a clique of $a$ vertices, and thus
  $I$ is a clique of $c+a$ vertices.

Since $H$ contains at least one universal vertex, by the above lemma, it must be a clique of size at least $K+n+1$.  Since we only added $n+1$ universal vertices to $G$, at least $K$ of the vertices in $H$ must have come from the original graph $F$, where they also form a clique since every induced subgraph of a clique is a clique.  Thus a YES answer to the constructed instance of your problem implies a YES answer to the given Clique problem.

Since a YES answer to one problem instance implies a YES answer to the other, it follows that a NO answer to one problem instance also implies a NO answer to the other.  Thus any algorithm that could solve your problem could also solve Clique.  Since constructing the instance of your problem requires only polynomial time, a polynomial-time algorithm that could solve your problem could also solve Clique in polynomial time.


Is there a human-friendly version of the Pumping-Lemma?

I agree that the way the lemma is written is confusing, a more friendly way to write the lemma is as follows (I have added an intuitive explanation for the conditions appearing in the lemma, hoping that it is more human readable now):
The Pumping Lemma: for every regular language $L\subseteq \Sigma^*$, there is a positive pumping constant $p$ such that for every word $w\in L$ with $|w|\geq p$ (that is, for every long enough word in the language $L$ ), the following holds. There exists a partition of $w$ into three words over $\Sigma$, $w = xyz$,  such that:

$|xy|\leq p$ (that is, $y$ lies in the prefix of length $p$ of $w$).

$|y| > 0$ (that is, $y$ is nonempty).

$xy^iz\in L$, for every $i\geq 0$ (that is, if you take the word $w$ and pump the infix $y$ in $w$, $i$ times, the word $w$ remains in the language $L$).


Getting the essential from the fundamental matrix

You can only get the essential matrix from the fundamental matrix if you know the camera intrinsics:

E = K' * F * K

where K is the intrinsic matrix and K' is its transpose.


What is language of repeat(L) = {ww | w ∊ L}?

$repeat(\cdot)$ is an operator on languages. It takes as an input a language $L$, and outputs a language defined by $\{ xx \mid x \in L\}$. That is, for any word $x\in L$ the string $xx$ will be in the output language $repeat(L)$.
A Few examples:

$L=\{ 0,00, 11\}$  =>  $repeat(L) = \{ 00,0000,1111\}$
$L=\{ \}$   => $repeat(L) = \{ \}$
$L=\Sigma^*=\{\epsilon,0,1,00,01,10,11,...\}$ => $repeat(L)= \{\epsilon, 00,11,0000,0101,1010,1111,...\}$


Thanks for posting your question! See, normally parsers implement huge usage of regex or regular expressions. But regular expressions are just for text manipulation and cannot count. Because of this defect of regular expressions, it becomes quite difficult to balance number of open and close tags. Hence, software engineers have to do some extra work to deal with it. You can read more about regular expressions at Mozilla Developer Network Docs and at this post on Medium.


Context-free grammar for complement of $\{ab \mid b=\mathrm{complement}(a)\}$

As you have noticed, you can decompose between words of odd length and words of even length. Since the odd part is quite easy, I will focus on the even one, that is $L = \{uv \mid u, v\in \{0,1\}^*\wedge u\neq \mathrm{complement}(v)\}$.
Given $u, v\in\{0,1\}^*, |u|=|v|$, if we write $u = u_1…u_k$ and $v = v_1…v_k$, then $uv \in L$ if and only if $k \geq 1$ and $\exists i \in [\![1,k]\!], u_i = v_i$. In that case, we can write $uv = wu_ixv_iy$ where $|w| = u_1…u_{i-1}$ and $y = v_{i+1}…v_k$. We also have $|x| = k-i + i -1= k-1$, so $x$ can be written as $x = zt$ with $|z| = i-1 = |w|$ and $|t| = k-i = |y|$.
We will now write a grammar to generate these words. Let's define:

$S\to AA\mid BB$
$A \to 0 \mid 0A0 \mid 0A1 \mid 1A0 \mid 1A1$
$B\to 1\mid 0B0\mid 0B1 \mid 1B0 \mid 1B1$

It is clear that $A$ rules will generate a word $w0x$ with $|w| = |x|$. That means that $AA$ will generate $w0zt0y$, with $|w| = |z|$ and $|t| = |y|$. The same thing can be done with $BB$.
(This answer was greatly inspired by this one.)


Unfortunately, you cannot generally reconstruct the generators from Voronoi polygons. Look at the four simple examples below: all have the same two Voronoi cells but different placement of the generators.


Regular set of the "does not contain" kind

If a string doesn't contain $11$, then any $1$ is followed by $0$, unless it is the final $1$ in the string. Therefore you can break the string up into pieces of the forms $0,10,1$, the last one appearing only at the very end. This leads to the following regular expression for the set of binary strings excluding $11$:
$$ (0+10)^*(\epsilon+1). $$
If we furthermore want the string to end with $0$, then we have no terminal $1$. On the other hand, we also want to disallow the empty string. Altogether, we get
$$ (0+10)^+. $$
A similar case analysis leads to a regular expression for your language. Details left to you.


Formal algorithm to test whether two given regular expressions define equal/identical or unequal languages

If behaviour of the automaton didn't depend on the final states, transition function and alphabet, why would we define automata to have those useless things?


What does a non-deterministic guess "look like"?

Nondeterministic guess is a non formal term we use for two (or more) possible transitions from the same configuration. When talking about a non deterministic finite automata, if a state $q$ has two different transitions for the character $a$, and I want to show that it accepts a certain word $w$, then I treat the junction at $q$ where $a$ is read as the location where the "guess" happens. By "guessing correctly" I refer to the transition that will lead to the eventual acceptance of $w$ (whereas I don't care what would have happened if I took the other transition, the "wrong" guess).
One implementation of guessing a partition of $w$ to $w_1w_2$ would be to have two transitions from the initial state for each character read by the machine head. One transition goes to the state $q$, where $q$ refers to $w_1$ as whatever lies to the left of the current position of the head and $w_2$ as the rest. The other transition stays at the initial state and keeps moving right until it meets blank. Although it's important to realize how to implement such a "guess", it is arguably more important to develop the intuition around the power of nondeterminism and understanding the such a nondeterministic  partition can be done (without going through the tedious details and elaborating on the transition function).
For your problem non determinism doesn't really make things much easier, as you could simply execute both machines on every possible partition (of which there are $n$ where $n$ is the input's length) in parallel via dovetailing.


Maximal class for which function equivalence is decidable

There is no such maximal class.

Proof: suppose that there is a class $C$ of representations of total functions for which function equivalence is decidable. If $C$ is finite, then $C$ augmented with the constant function that returns $\max\{\overline{f_i}(0)\} + 1$ (which by construction is not in $C$) has decidable function equivalence (test the function at $0$ then apply the postulated decision algorithm). If $C$ is infinite, it is denumerable (because representations of functions are denumerable¹), so let $(f_i)_{i\in\mathbb{N}}$ be an enumeration of all function representations in $C$. Let $G(i) = \overline{f_i}(i) + 1$ (a classic diagonal construction). By construction, $G$ does not have a representation in $C$ (because $\forall i, g_i(i) \ne h(i)$). Let $g$ be a representation of a function that calculates $G$ (this is doable in any Turing-equivalent framework). The algorithm that reports that $g$ is distinct from any member of $C$, and otherwise applies the existing decision algorithm for $C$, is an equivalence decision procedure for $C \cup \{g\}$.

Any class of function representations with decidable equivalence can be augmented to a larger such class. Therefore there is no maximal class.

Intuitively speaking, if you have two classes of functions with decidable equivalence, you can apply the two decision algorithms inside each class, but it's not necessarily possible to compare two functions from different classes. And if you have an infinite set of classes, with a decision procedure for each, then even calculating which decision procedure to use is not necessarily doable.

¹  The set of all functions is not denumerable, but whatever representation of functions you choose (e.g. source code in some language), the set of inputs for your decision algorithm is denumerable.


The reason why the sorting solution works is that if you are given $K$ guesses, then with any deterministic strategy you can only guess at most $2^K - 1$ values. This can be proved by induction, first noting the base case $K = 1$ and then for $K + 1$, note that after you guess the first value then you have $K$ guesses left and you guess either on the left or right of your original guess depending on the outcome of the original guess, so by induction that gives $2(2^K - 1)$ values you can guess after the first, so if you add the original guess then you get $2^{K+1} - 1$.

Furthermore, if any of these $2^K - 1$ values is the correct value, it will be guessed and you will win. None of the other $N - 2^K + 1$ values will ever be guessed. So the probability that you win is the sum of the probabilities for the $2^K - 1$ values your deterministic strategy can guess. Obviously the optimal solution is to take the top $2^K - 1$ probabilities.


Which cellular automata rules are suitable for randomizing an input sequence?

Rule 30 is probably the "most random" of all 256 rules. It has been used as random number generator, but there are some issues:

Some initial states will result in repetitive output, which is not what we want from a random number generator. However, given that the automaton is large enough, and that the initial state is itself somewhat random, this shouldn't a problem.
There are better ways to generate random numbers.


Algorithm to find the closest possible value among several combinations

This is a common problem so there certainly exist many approaches to solve it. Below I'll sketch such an approach. It probably has a name but I don't know it:

The approach essentially sets up an array of target order sizes with an array length of actual order size + largest available package size. In each array element we store the ID of the package that can be used to increase the overall combined package size from a known solution for some smaller order size to get to the order size related to the index of the array. When we filled up the array we can go back from a realizable solution to an order size of 0 by collecting all the packages that lead to the respective solution. So this will be some kind of a dynamic programming approach.

We start at an order size of 0, go through all available packages and set the array index given by the respective package size to the ID of the package. Now we repeatedly increase the order size by 1 up to the target order size and for each order size we do the following:

If there is an ID of a package in the respective array element we again go through all available packages and store their ID in the array element "order size + package size" if that array element does not yet contain an ID. Otherwise we do nothing and just go on.

When we filled up the array in this way we can search in the neighborhood of the target order size for the array element that best fulfills our needs and also contains a package ID. From there we add the stored package ID to our solution and go back in the array by the size of that package. We do this repeatedly until we are back at a test order size of 0.

Of course, the solution we obtained in this way is not necessarily unique. We can prioritize certain packages by the order in which we process them when filling up the array.


how to find a node that is known to everyone but doesn't know anyone?

This can be done with the help of an auxiliary stack and elimination technique.
Let us call the node we are looking for the special node. We can make certain conclusions by examining the relation of any two nodes as following :

If node A knows node B, then A is surely not the special node and B may be the special node.
If node A doesn't know node B, then B is surely not special node and A may be the special node.
We repeat above two steps till we are left with only one node.
Examine the last node if it doesn't know anyone and is known to everyone.

Algorithm: (uses auxiliary stack)

Push all the nodes on the stack.
Pop off top two nodes from the stack, discard one node based on the observations made.
Push the remained node onto stack.
Repeat step 2 and 3 until only one node remains in the stack.
Check the remained node is the one we are looking for.

Why do we need the last step?

Because we have examined all the nodes relative to only one node which is adjacent to it on the stack but we don't know its relation with other nodes. So we need to ensure that the potential candidate for the special node is actually the special node.

This will require $3(n-1)$ comparisons in total. So the complexity is $O(n)$.


Does Halts reduce to all other undecidable languages?

Recall that $A \leq_m B$ iff $\bar A \leq_m \bar B$. Indeed, the same reduction function works for both cases.

So, let $H$ be the halting problem. Both $H,\bar H$ are undecidable. We prove $H \not\leq_m \bar H$.

By contradiction, assume $H \leq_m \bar H$. Hence, by the property above, $\bar H \leq_m H$. Hence $\bar H$ reduces to some RE problem, making $\bar H$ RE as well. Since $H,\bar H$ are both RE, we conclude that both are decidable. Contradiction.


Is it possible to use plants as a medium to store data? By what data structure?

What you propose sounds like it would be quite error laden, as plants are not necessarily independent, and those grown in the same area of the same species might share a common root system, so what you might consider redundancy is not a guarantee that your data will be preserved.  I would also venture to say that it's rare for a plant to be hardy against cold weather, and especially against something like an herbicide.

What you might consider is the concept of biocomputing and, more specifically, DNA computing, which uses the ordering of the base pairs to store and manipulate information.  The field is still in its infancy, but Turing machine-like behavior has been achieved, and in some cases basic algorithms can be implemented (e.g., the Hamiltonian path problem as cited in the Wikipedia article).


Algorithm to determine minimum server required?

This answer assumes that what you're trying to minimize is
$$
 \sum_{i \in S} c_i + \sum_{i=1}^n d(i,S),
$$
where $c_i$ is the cost of the $i$th server and
$$d(i,S) = \min_{\substack{j \in S \\ j \geq i}} \; j-i$$
is the distance from $i$ to the closest server.

Use dynamic programming. For all $j \leq j_0$, compute the minimum of
$$
 \sum_{i \in S} c_i + \sum_{i=j}^n d(j,S)
$$
over all $S \subseteq \{j,\ldots,n\}$ such that $\min S = j_0$.


Solving the Knapsack problem in $O(v^*n^2)$, where $v^*$ is the maximum value of all $n$ items

So, after eventually giving up on developing a different algorithm I looked back at the original solution, i.e. the one you can find e.g. on Wikipedia under 0/1 Knapsack problem.

The idea is to look closely at which fields of the table the algorithm builds are actually necessary, and which are not.


If current time in milliseconds is considered good enough random seed for a pseudorandom number generator, why not just use that time directly?

The key property that we want from (non-cryptographic) pseudorandom numbers is that they "look" independent. In particular, say you have some algorithm that requires a PRNG to perform well and you give it a current time function as a PRNG. Then, if the algorithm repeatedly queries what is supposed to be a PRNG, it will actually see that it gets the same value many times in a row until, until it eventually increments by one. These values are very, very far from random and can be detrimental to algorithmic performance.


What is the height of an empty BST when using it in context for balancing?

Any constant works as the height of Empty, because only the difference of heights is important for balancing. So, why not choose 0?


Does removal of unit production from the grammar may increase number of total production?

Hint: Consider the grammar
$$S \to \overbrace{X\cdots X}^{\text{$n$ times}} \\ X\to a|b$$
What happens when you remove unit productions?


The treewidth (and pathwidth) of the $k\times k$ grid is exactly $k$. (And, more generally, the treewidth and pathwidth of the $k\times\ell$ grid is exactly $\min\,\{k,\ell\}$). For the example grid

$$\begin{matrix}1&-&2&-&3\\|&&|&&|\\4&-&5&-&6\\|&&|&&|\\7&-&8&-&9\end{matrix}$$

the bags of the tree decomposition are $\{1,2,3,4\}, \{2,3,4,5\}, \{3,4,5,6\}, ..., \{6,7,8,9\}$.

Note that the bag $\{1,2,3,4\}$ already contains all edges adjacent to $1$, so we don't need to include that vertex ever again. Similarly, $\{2,3,4,5\}$ contains all of the edges adjacent to $2$ that weren't already in the first bag.


Finding the average time complexity for a max algorithm

Let $\small n = \mathsf{len}(L)$ and $\small t_n$ be the times that $\small \mathsf{max}$ is assigned a value. For $\small 0 \leq i < n$, define a random variable $\small X_i$ as
$$
\small
X_i = \begin{cases}
1 & \text{if } L[i] > \text{$\mathsf{max}$ in the $i$-th iteration of the algorithm}\\
0 & \text{otherwise}
\end{cases}
$$
Then we have
$$
\small
t_n = 1 + \sum_{i=0}^{n-1} X_i
$$ By linearity of expectation,
$$
\small
\mathbb{E}[t_n] = 1 + \sum_{i=0}^{n-1}\mathbb{E}[X_i]
$$
Observe that $\small X_i = 1$ if and only if $\small L[i] > \max\{L[0], L[1], \cdots, L[i-1]\}$. Therefore
\begin{align}
\small
\mathbb{E}[X_i] = \Pr[X_i = 1]  =&\small \sum_{v=1}^{100} \Pr[L[0] < v, L[1] < v, \cdots, L[i-1] < v, L[i] = v] \\
\small= &\small \sum_{v=1}^{100} \left(\frac{v-1}{100}\right)^i \cdot \frac{1}{100}
\end{align}
We thus conclude
\begin{align}
\small
\mathbb{E}[t_n] =&\ \small  1 + \sum_{i=0}^{n-1}\sum_{v=1}^{100} \left(\frac{v-1}{100}\right)^i \cdot\frac{1}{100} \\
\small =&\ \small 1 + \frac{1}{100}\sum_{v=1}^{100}\sum_{i=0}^{n-1}\left(\frac{v-1}{100}\right)^i \\
\small =&\ \small 1 + \frac{1}{100}\sum_{v=1}^{100}\frac{1 - \left(\frac{v-1}{100}\right)^n}{1 - \frac{v-1}{100}} \\
\small\text{(for sufficiently large $n$)}\quad\quad\approx&\ \small1 + \frac{1}{100}\sum_{v=1}^{100} \frac{1}{1 - \frac{v-1}{100}} \\
\small = &\ \small 1 + \sum_{v=1}^{100}\frac{1}{101-v} \\
\small =&\ \small 1 + H_{100}
\end{align}
where $\small H_{100}$ is the $\small 100$-th harmonic number.


Given two $a^n b^n$-style languages, how do I find out if their intersection is regular?

$L_1=\{a^ncb^n\}\cup\{a^mdb^{2m}\}$

$L_2=\{a^{2n}cb^{2m+1}\}\cup\{a^{2m+1}db^{2n}\}$

If we say $\;L_1=L_{11}\cup L_{12}\;\:$and$\;L_2=L_{21}\cup L_{22}$

$L_1\cap L_2=((L_{11}\cap L_{21})\cup (L_{12}\cap L_{21}))\cup ((L_{11}\cap L_{22})\cup (L_{12}\cap L_{22})) $

$L_{11}\cap L_{22}\:,\:L_{12}\cap L_{21}\;$will be zero because d and c are different symbols.

So $\;L_1\cap L_2=(L_{11}\cap L_{21})\cup  (L_{12}\cap L_{22}) $

$L_{11}\cap L_{21}=\emptyset \:\;$because it is not possible for an even number to be equal to an odd number.

$\;L_1\cap L_2=L_{12}\cap L_{22}=L=\{a^{2m+1}db^{4m+2}\}$

So the language is not regular but context free. It is impossible to construct a finite automaton for this language because finite automaton has a memory that is fixed and cannot thereafter be expanded. ( It cannot store number of a's ) But it is easy to recognize that L is context free since $L=(a(aa)^*db^*)\cap \{a^ndb^{2n}|n\geq 0\}$ ( intersection of a CFL with a regular language is CFL ) And $ \{a^ndb^{2n}|n\geq 0\} $ is context free because there exists a push-down automaton that accepts L. When this automaton sees an $\:a\:$ it pushes 2 $\:a\:$'s into the stack and when $\:d\:$ is the input it changes it's state to a final state and then for each $\:b\:$ it pops an $\:a\:$ from the stack.


Supporting queries for finding how many intervals in a dynamic set of 1D intervals contain a given point

I think I have an algorithm but I'm not sure if it's correct.

We want to maintain an augmented binary search tree $S$ on each interval end point. The splitting element will always be the median end point so that the total height of our tree in the end is in the order of $\log_{2}N$.

In every node we use some data structure to store all intervals that go through the splitting element.

Assuming nothing more for our data structure, we can see that if $x_q$ is the query point, every time we visit a node we check to see if $x_{q}$ is to the right or to the left of the splitting element. If it is to the left, then no interval stored in any node of the right subtree will intersect $x_{q}$ so we will only need to check the left sub tree. The same applies to the case where $x_{q}$ is to the right of the splitting element.

So far we can find all relevant intervals in $O(\log n)$ time, but to find the exact intervals that intersect $x_{q}$, we have to see what's going on in this structure that we have for every node, so we also have to query each such structure along a root to leaf path to find exactly the intervals that intersect $x_{q}$

To do this, we can have two sorted lists $L$, $R$ on every node, each list will store the same intervals but $L$ will store them in a sorted order according to the left point and $R$ according to the right point.

Then whenever we visit a node we see if $x_{q}$ is to the left of the splitting element. If that's the case, we do a binary search on $L$ to find the right most interval that contains this point, since we know the index of this interval in $L$ we can find the total amount of intervals.

We process similarly $R$ if $x_{q}$ is to the right of the splitting element.

This algorithm will give us a $O(\log ^2 N)$ complexity.


PDA for the language of strings containing the same number of a and b

You have solved half of the task. Now push $B$ for $b$ and pop $B$ for $a$.
To decide which operation to do, handle empty stack, pushing symbol when it is empty and popping otherwise.


Turing machine - Transition between two states by more than one condition allowed?

Yes, it's allowed.

I guess the underlying problem here is that you're not familiar with reading mathematical definitions. Properly written definitions state exactly the criteria that apply. So, for example, if you read the definition "An integer is even if it is divisible by two" you should assume that divisibility by two is the only criterion that applies. The definition says nothing about divisibility by three, for example, so divisibility by three doesn't matter.

In our case, the transition function of a Turing machine is defined as a function whose arguments are a state and a tape character, and whose outputs are a state, a tape character and a direction to move the head. No further restrictions (such as "you can't get the same output from two different inputs") are mentioned in the definition, so no further restrictions apply.


Diffie-Hellman and its disadvantage with large primes

Let $p$ be a prime number and denote by $\mathbb{Z}_p$ the ring of integers modulo $p$.
The set $\mathbb{Z}_p^*$ typically denotes the units of $\mathbb{Z}_p$.
This set is defined as $$\mathbb{Z}_p^* = \{n \in \mathbb{Z}_p : \exists m \in \mathbb{Z}_p, nm = 1\},$$ where arithmetic is done modulo $p$.
An important fact about $\mathbb{Z}_p$ is that it is a field.
This means that we can simplify the above to $\mathbb{Z}_p^* = \{1, 2, \ldots, p-1\}$.
This set forms a group under multiplication, and it is a standard fact that this is a cyclic group, i.e., it is isomorphic to $\mathbb{Z}_{p-1}$ where the group operation is addition.
In symbols, $(\mathbb{Z}_p^*,\times) \cong (\mathbb{Z}_{p-1},+)$.

Since $p-1$ is even, consider the two-element subset of $\mathbb{Z}_{p-1}$ given by $\left\{0,\frac{p-1}{2}\right\}$.
As $\frac{p-1}{2} + \frac{p-1}{2} = p-1 = 0$ in $\mathbb{Z}_{p-1}$, this set forms a subgroup of $\mathbb{Z}_{p-1}$.
The order of a subgroup is its cardinality as a set, so this is a subgroup of order two.

Via the isomorphism between $(\mathbb{Z}_{p-1},+)$ and $(\mathbb{Z}_p^*,\times)$, this corresponds to a subgroup of $\mathbb{Z}^*_p$ of order two.


Why is my algorithm version so slow with this input?

I've found the conceptual problem.
In a BFS kind of search, when optimization is needed because the length of the queue grows at critical speed, you have to take track of the visited items.

The goal is to avoid adding another item to the queue when it is already present a better item there.

Just some code, only to clarify the concept.

In my case I've added a visited map

let mutable visited = Map.empty<char,((char list) * int) list>

and I'm enqueuing only better items:

if visited.ContainsKey(solutionNext.tree.area)
    && (visited.[solutionNext.tree.area]
        |> List.exists (
            fun (keys, distance) ->
            distance <= solutionNext.tree.distance
            && solutionNext.keys |> List.forall(fun k -> keys |> List.contains k)
        ))
then ()
else
    solution_queue <- enqueue solution_queue solutionNext
    let previous = if visited.ContainsKey(solutionNext.tree.area) then visited.[solutionNext.tree.area] else []
    visited <- Map.add solutionNext.tree.area ((solutionNext.keys, solutionNext.tree.distance) :: previous)  visited

and skipping the worst ones

while (MyQueue.length solution_queue > 0) do
    let solution = dequeue &solution_queue
    if visited.ContainsKey(solution.tree.area)
        && (visited.[solution.tree.area]
            |> List.exists (
                fun (keys, distance) ->
                distance < solution.tree.distance
                && solution.keys |> List.forall(fun k -> keys |> List.contains k)
            ))
    then () else

Cost function

From a theoretical viewpoint, BFS can guarantee that the ﬁrst solution returned will be as short as possible, only if we can assume that every move has got a cost of 1. You could reduce the above examples to that, but the best fit remains a graph where the cost function is represeted by edges of different length.
With real cost functions finding the shortest path becomes more involved: this is exactly the case here. Especially because you have to optimize also the Space complexity (see previous paragraph), avoiding the worst-case time complexity of $O(b^d)$, with $b$ being the branching factor and $d$ the depth of the ﬁrst solution. You have described a scenario where $d$ is well known at start (the number of the keys in the maze) while the edge case you mention is obtained by a bigger $b$ (number of crossings of the maze)


What is the smallest time/space complexity class that is known to contain complxity class $\mathsf{SPARSE}$

If by SPARSE you mean the set of languages where the acceptance occurs on a set of zero density, then it is not in EXP or EXPSPACE. It isn't even computable. To see this, pick your favorite computable enumeration of Turing machines T_n, and consider the language L in the alphabet {0,1} where a string S is in L if and only if L is consists just of n 1s, and where T_n halts on the blank tape. Since the problem of whether a given Turing machine halts on the blank tape is undecidable (if one can do it, one can solve the Halting Problem), our language L is undecidable. Using this same trick with a padding argument we can make languages which are as sparse as we want but are not computable.


Can every program be parallelized infinitely and automatically?

If you're working in the strict lambda calculus, everything can be automatically parallelized. In particular, when evaluating a function application, the function and the argument can always be evaluated in parallel.

However, it cannot be infinitely parallelized. There are inherent data dependencies: the result of a function application can't be determined until both the argument and the function have been evaluated, meaning that you need to wait for your threads to both finish, then synchronize.

This is still relevant with your clarified definition of infinitely. For example, if you have 5 processors, it's possible that a particular program can only ever use 4 processors, because of the data dependencies.

Moreover, while this is automatic, it is not "performance for free." In practice, there is non-trivial overhead to creating and synchronizing threads. Moreover, it's difficult to do this in a way that scales only to the current number of processors: if you have 5 cores, the automatic parallelization might generate 6 threads, and in general, it's not possible to know at compile-time how many threads will be active at a given time.

So, you can automatically make a program that runs massively parallel, but with the current state of affairs, it will likely be slower than your original.

It's also worth mentioning that, in practice, this becomes difficult with shared access to resources and IO. For example, a real world program might write to a disk, which can cause problems if done in parallel without control. This is something that can't be modeled by the standard lambda calculus.


Why is there no regularity condition in case 1 of the master theorem?

You are asking why the regularity condition is absent in case 1. What you should be asking instead is why the regularity condition is present in case 3. Let's start with the latter question.

Consider the recursion
$$
T(n) = T(n/2) + f(n), \text{ where } f(n)=n^{1 + (\log_2 n \bmod 2)}.
$$
For simplicity I define the function $f$ only for powers of 2, and it is given by $f(2^{2k}) = 2^{2k}$, $f(2^{2k+1}) = 2^{4k+2}$. You can check that $T(n) = \Theta(n^2)$, and so it is not the case that $T(n) = \Theta(f(n))$ (since for $n = 2^k$, $f(n) = n$).

This shows that some regularity condition is indeed necessary in case 3. The proof shows that this particular regularity condition suffices for the conclusion $T(n) = \Theta(f(n))$ to hold.

In case 1, in contrast, the proof works for every function $f(n)$ satisfying the condition $f(n) = O(n^c)$, where $c$ is strictly smaller than the critical exponent. You can try to concoct an example like the one above, but you will necessary fail, since the master theorem states that the condition $f(n) = O(n^c)$ suffices for the conclusion $T(n) = \Theta(n^{c_{crit}})$ to hold.

You can still ask whether there is some deeper reason that the regularity condition is needed in case 3 but not in case 1. I think that the example above is very suggestive: the reason is that in case 3 the answer involves $f(n)$, whereas in case 1 it doesn't. Therefore if $f(n)$ is not well-behaved then it could show up in case 3, but is irrelevant for case 1.


NP-hardness of resource allocation problem

If you set $N = 2$, and $r_{i0} = r_{i1} = r_i$ for each $i$, and set $R = \frac12 \sum_{i \in [L]} r_i$, then the feasibility of this linear program is precisely the Partition problem. Namely, a feasible solution chooses for each $i \in [L]$ either $x_{i0}$ or $x_{i1}$, so that summing the $r_i$ for those $i$ for which you chose $x_{i0}$ equals $R$, and similarly for $1$.


Merge a set of strings based on overlaps

This is the DNA sequence assembly problem, an algorithms problem that has been well studied in the literature.  You can apparently find entire courses on the subject.  In general, the problem is NP-hard.  However, there are many algorithms that seem to work well in practice; greedy assembly is one very simple approach, but there are many others.


Recall a Hamiltonian cycle visits each vertex of a graph exactly once. Thus, the cycles H1 and H2 in your second example can't be Hamiltonian cycles in the same graph.

In your first example, the two cycles could be distinct Hamiltonian cycles in e.g. the complete graph on 4 vertices. That is to say, there can definitely be multiple Hamiltonian cycles in a graph.

If you care about naming conventions, you can call two cycles that don't share any vertices vertex-disjoint cycles. Similarly, two cycles can be edge-disjoint if they don't share edges.


How many languages exist over a finite alphabet?

The number of possible words is countably infinite, since we can list them in increasing order of length:
$$
\epsilon,a,b,aa,ab,ba,bb,\ldots \\
\epsilon,1,11,111,1111,11111,\ldots
$$
This is why $|\Sigma^*| = \aleph_0$ (to use a more common notation). The set of all possible languages is the set of all subsets of $\Sigma^*$ (known also as the power set of $\Sigma^*$), which by definition has cardinality $2^{\aleph_0} = \aleph$.

If you are unfamiliar with these terms, you need to do some reading on elementary set theory.


Is mapping reduction from $\overline{A_{TM}}$ possible?

The notion of mapping reducibility is completely general:

Let $A, B \subseteq \Sigma^*$ be languages. $A \leq_{\mathrm{m}} B$ if there exists a computable function $f: \Sigma^* \rightarrow \Sigma^*$ such that

$$w \in A \iff f(w) \in B$$

No properties are required of $A$ or $B$.

We can use a mapping reduction from $\overline{A_{\mathsf{TM}}}$ to show that $EQ_{\mathsf{TM}}$ is not recognizable. Let $f$ be given by

$$f(\langle M,w \rangle) = \langle M', M'' \rangle$$

where $M'$ is the TM

"On input $x$ simulate $M$ on input $w$ and answer what $M$ answered"

and $M''$ is the TM that rejects every input.

Clearly, $M$ does not accept $w$ if and only if $L(M') = L(M'')$.


Explanation of implication-introduction rule

Every assumption that is introduced between brackets has to be discharged at some point for the proof to be complete. Otherwise, we could prove that $A$ is true for any given $A$ as follows.

[A]¹
───
 A

This proof is incorrect, we have not discharged the initial assumption. The following proof of $A\to A$ would be correct, as it discharges the assumption (and the implication introduction rule is necessary to do so!).

 [A]¹
 ───
  A
───── (discharging ¹)
A → A

Now, let's compare two derivations of $A \to A \times A$ and $A \to A \to A \times A$. On the first one, we will discharge the two occurrences of $A$ at the same time (on the same deduction step). On the second one, we will discharge the two occurrences on two separate steps.

First proof

  [A]¹   [A]²
  ─────────
    A × A
───────────── (discharging ¹ and ²)
  A → A × A

Second proof

 [A]¹    [A]²
 ──────────
   A × A
───────────── (discharging ¹, note that ² is still alive!)
  A → A × A
──────────────── (discharging ²)
 A → A → A × A

Maybe looking at this from the perspective of the simply-typed lambda calculus is more illuminating. Instead of tracking superscripts, variable
names represent which assumptions are we choosing to discard at each point. Note the difference between the two proofs, and how the introduction rule of the implication corresponds to a lambda abstraction,
while the introduction rule of the conjunction corresponds to a pair type.

First proof

   a : A   a : A
   ─────────────
   (a,a) : A × A
 ────────────────────
 λa.(a,a) : A → A × A

Second proof

     a : A   b : A
     ─────────────
     (a,b) : A × A
   ────────────────────
   λb.(a,b) : A → A × A
 ───────────────────────────
 λa.λb.(a,b) : A → A → A × A

(I am using a lambda interpreter I wrote to generate these derivation trees. It may be useful for you if you are interested in the connection between propositional intuitionistic logic and lambda calculus.)


How must Grovers algorithm be modified in order to solve 3-SAT?

Grover's algorithm is already suitable.  It promises that if there is at least one match, then it will output at least one match.  It doesn't promise to output all matches, but you don't need all matches.

It is usually described to work in the case where there is zero or one items that match, but that's just because those are the hardest cases.  If there are multiple matches, the algorithm will still work and will still find a match; and the running time will remain the same.


Using interval graphs to find authorship disputes

I'll explain shortly the "archaeology example" your excerpt refers to. It seems that the authorship dispute problem is really no different from it, and any practical application would face similar problems as I will describe.

Around 1900, Flinders Petrie formulated a problem known as sequence dating while studying 800 types of pottery found in 900 Egyptian graves. To each artifact, we associate a time interval (unknown) during which it was used, and to each grave a time point (unknown) when its contents were interred. Then, the problem is to figure out the time relationships between the artifacts and the graves.

Now consider a graph $G$ whose vertices correspond to distinct artifacts. There is an edge between two vertices if they were found in some common grave. Assuming each pair of artifacts whose usage intervals intersect are to be found together in some grave we have that $G$ is an interval graph. Furthermore, an interval assignment for $G$ is a candidate for the usage intervals of the artifacts. However, of course in practice, it might be that we have incomplete data so the assumptions do not hold, and in any case, we need additional techniques to choose the correct interval assignment.


Do the "virtual memory"s mentioned in the 2 articles refer to different things?

That first link is bogus.   I can see where they're getting that misconception from, but it's not actually correct.


What is the relationship between the complexity class $L^n$ and $NL^m$?

It is not known whether $\mathsf{L} = \mathsf{NL}$, and this is a famous open question. More generally, I believe that no better bound than $\phi(m) \leq 2m$ is known for any value of $m$, nor is this bound known to be optimal for any value of $m$.


Is O(mn) considered "linear" or "quadratic" growth?

In mathematics, functions like this are called multilinear functions. But computer scientists probably won't generally know this terminology. This function should definitely not be called linear, either in mathematics or computer science, unless you can reasonably consider one of $m$ and $n$ a constant.