How to prove that a language is context-free?

A practical approach that in many examples works [but not always, I know] is trying to find the nesting structure of the strings in the language. "Nested dependencies" have to be generated at the same time in different parts of the string.
Also we have the basic toolbox:

concatenation: $S\to S_1S_2$ if you can split the language in two consecutive parts use this production

union: $S\to S_1 \mid S_2$ split into disjoint parts

iteration: $S\to S_1S \mid \varepsilon$

Example 1
Unequal numbers can be handled using a simple trick.
$L= \{ a^mb^n \mid m\neq n \}$
Now clearly
$L= \{ a^mb^n \mid m< n \} \cup  \{ a^mb^n \mid m> n \}$.
Consider first half: $L_1 = \{ a^mb^n \mid m< n \}$. If there must be more $b$'s we can generate an equal numbers of $a$'s and $b$'s on the one and and add at least one extra $b$:
$L_1 = \{ a^mb^m b^i \mid m\ge 0, i>0 \} = \{ a^mb^m \mid m\ge 0 \}\cdot \{ b^i \mid i>0\}$. This we can handle with concatenation from the basic toolbox.
Now the complete language also deal with the case we have more $a$'s. This we handle by using union.
$S \to S_1 \mid S_2$ (choose which part)
$S_1 \to XB$ (extra $b$ part)
$X\to aXb\mid \varepsilon$ (equal number of $a$ and $b$)
$B \to Bb \mid b$ (one or more $b$'s)
$S_2 \to AX$ (extra $a$ part)
$A \to Aa \mid a$ (one or more $a$'s)
Example 2
Here an example for the nesting (thank you Raphael).
$L=\{b^ka^l(bc)^ma^nb^o \mid k,l,m,n,o\in {\Bbb N},k\neq o,2l=n,m\ge 2 \}$
Replace $n$ by $2l$. We can now drop $n$ in conditions.
Replace $k \neq o$ by $k > o \text{ or } k < o$ (confused? $o$ is 'oh' not 'zero'). Apply tools for union. We work with $k > o$ here. Also $k>o$ iff $k=s+o$ and $s>0$ where $s$ is a new variable. Replace $k$ by $s+o$.
$L_1 =\{b^{s+o}a^l(bc)^ma^{2l}b^o \mid l,m,o,s\in {\Bbb N},s>0,m\ge 2 \}$
Some simple rewrites.
$L_1 =\{bb^sb^o a^l bcbc(bc)^m (aa)^{l}b^o \mid l,m,o,s\in {\Bbb N}  \}$
Now we see the nesting structure, and start building a grammar.
$S_1 \to TV$, $T\to bU$, $U\to bU \mid \varepsilon$ (see: concatenation and iteration here)
$V \to bVb \mid W$ (we generate $o$ $b$'s on both sides)
$W \to aWaa\mid X$
$X\to YZ$, $Y\to bcbc$, $Z\to bcZ\mid \varepsilon$
Example 3
$K =\{ a^kb^lc^m \mid l=m+k\}$
A first "obvious" rewrite.
$K =\{ a^kb^{m+k}c^m \mid m,k\ge 0\} = \{ a^kb^mb^kc^m \mid m,k\ge 0\}$
In linguistice this is called "cross-serial dependency": the interleaving $k,m,k,m$ (usually) strongly indicates non-contextfreeness. Of course $m+k=k+m$ and we are saved.
$K =\{ a^kb^{k+m}c^m \mid m,k\ge 0\} = \{ a^kb^kb^mc^m \mid m,k\ge 0\}$
with productions $S\to XY$, $X\to aXb\mid \varepsilon$, $Y\to bYc\mid \varepsilon$
Similarly $K'= \{ a^kb^lc^m \mid m=k+l\} = \{ a^kb^lc^lc^k \mid k,l\ge 0\}$
with productions $S\to aSc \mid X$, $X\to bXc\mid \varepsilon$

Final comment: these techniques help you come up with a candidate context-free grammar that will hopefully recognize your language.  A correctness proof may still be needed, to ensure that the grammar really works to recognize your language (nothing more, and nothing less).


What is the time and space complexity of Rete algorithm

finally i found what was needed, thought i wil share here for others who might need it.
http://reports-archive.adm.cs.cmu.edu/anon/1995/CMU-CS-95-113.pdf


Why is the Kleene star operator also called the Kleene 'closure' operator?

A set is closed under some operator if the result of applying the operator to things in the set is always in the set. For example, the natural numbers are closed under addition because, whenever $n$ and $m$ are natural numbers, $n+m$ is a natural number. On the other hand, the naturals are not closed under subtraction since, for example, $3-5$ is not a natural number.

The closure of a set $S$ under some operator is the smallest set containing $S$ that is closed under the operator. For example, the closure of the natural numbers under subtraction is the integers; the closure of the natural numbers under addition is just the natural numbers, since the set is already closed.

So, "Kleene closure" is not an alternative name for "Kleene star".  The Kleene star is the operator; the Kleene closure of a set is the closure of that set under the operator.


Closure properties of a non-regular language under complement?

Yes, non-regular languages are closed under complement as well.

Suppose the complement of L1 is a non-regular language. If L1 is regular, then "the complement of L1 is also a regular language", which is not true. Hence L1 cannot be regular.

More generally, suppose we have defined a collection of languages as myLanguages. Then

myLanguages are closed under complement $\Longleftrightarrow$ non-myLanguages are closed under complement

For example, we have

non-context-free languages are not closed under complement.
non-context-sensitive languages are closed under complement.
non-deterministic-context-free languages are closed under complement.


Categorising problems into complexity classes

Your reasoning seems correct, but you are missing a crucial step once the second bullet point is done with: You check that your problem is also complete for the class $C$ you have found for it. For instance, if you have a problem $P$ and show it is reducible to a complete problem in $\mathsf{PP}$, then you are not done yet. For all we know, $P$ could be $\mathsf{PP}$-complete, but it could also be in $\mathsf{NP}$, or $\mathsf{BPP}$, etc. Therefore, to finish classifying $P$, you should be able to find a class it is complete for—if possible; after all, there are classes which are not closed under (poly-time many-one) reductions—, or provide some good evidence why it could not be in a class which is known (or conjectured) to be strictly below $C$.

  If I cannot find a reduction and I do not have an algorithm, what is the "default" complexity class?

Assuming your problem is decidable, the "default" complexity class is $\mathsf{R}$, the class of recursive languages. Improving on this is only possible by producing an algorithm whose time complexity you can prove or, alternatively, proving a reduction to some other problem for which this is the case; that is, essentially what you wrote in your question. There is no such thing as a "class of problems which cannot be solved until we find an algorithm" in complexity theory; that would be the domain of computability theory (i.e., problems which are not known to be decidable).


Why does if A is a spanning tree which doesn't have $e_1$ then $A\bigcup\{e_1\}$ has a unique cycle?

In a tree, there is exactly one path between any pair of vertices. When you add edge e1 you close that unique path to form a unique cycle.


It will be HIT in the L2 cache as you have guessed it because L2 cache maintains a directory or a bit vector which tells in which of the private caches the modified state of the block is in. So when L1 of P0 requests it for the second time, L2 will supply the latest modified block.


Prove propositional formula is a tautology

Here is what the formula states:

  If $p$ implies $q$, then $p$ and $r$ imply $q$ and $r$.

To prove this, you would like to argue as follows. Assume $p$ implies $q$, and suppose that both $p$ and $r$ hold. Since $p$ implies $q$, then $q$ holds. Hence both $q$ and $r$ hold.

How exactly this proof is expressed depends on your proof system.


$k$-way merge but without an absolute order

Edit: You recently revised the question to clarify that you are allowed to hash items.  That changes the question: it lets us build much more efficient algorithms.

With this change, your question becomes: given $k$ partial orders, find a total order that is consistent with all of the $k$ partial orders.  This problem can be solved in linear time, i.e., in $O(n)$ time, where $n$ is the total number of items across all of the sublists.

Here's how to solve it.  We'll build a directed graph, where each item (in any sublist) is a vertex is the graph.  Traverse the sublists to extract all consecutive pairs of items that appear in any sublist.  If you have a < b in a sublist (i.e., item a immediately precedes b in some sublist), add an edge $a \to b$ to the graph.  (Notice that you can have a hashtable that maps the item a to the corresponding vertex $a$ in the graph, so this operation involves two lookups in the hashtable and then adding an edge: $O(1)$ time.)

Once you've built the entire graph, topologically sort it, and output the vertices in topologically sorted order.  That will be a valid output list that solves your problem.  If the topological sort fails and reports that the graph has a cycle, then your sublists are inconsistent and you should output an error.

This solves your problem in linear time, i.e., $O(n)$ time.

My original answer to your original question:
You don't list any requirements on what order the combined list elements must appear in.  Therefore, concatenating/interleaving all of the list items in an arbitrary order appears to meet all of the explicitly stated requirements.  If that's not an acceptable solution, you'll need to think through your requirements more carefully and then edit your question to state the requirements explicitly.

I suspect you meant to require that the elements in the combined list must appear in an order that is consistent with the order in each sublist, and any item should appear only once in the combined list.  If that's what you meant, then you can't do better than $O(n^2)$ time, where $n$ is the total number of items across all of the sublists: there's no way to avoid comparing each item of each sublist with each other.  (If there is any pair of items which you have not compared explicitly, you have no way of knowing whether they are equal or not: both are possible.)

It's easy to achieve an $O(n^2)$-time algorithm.  You simply compare each item to all other items, to first find all duplicated items (items that appear in more than one sublist).  Then, you do a straightforward $k$-way merge.  At each step of the $k$-way merge, you look at the head of each of the $k$ sublists and classify each of those $k$ items as duplicated or not.  If any of them are non-duplicated, you can remove it from the head of its sublist and append it to the combined list.  If one of them is duplicated, and all of its duplicates appear among these $k$ items, then you remove each of them from their corresponding sublists and append it to the combined list.  Repeat this until done.  If no items appears twice in any sublist, and if all of the sublists are sorted in a compatible way (e.g., you don't have a before b in one sublist but b before a in another sublist), then this process will never get stuck and will yield the desired output.

The running time of this algorithm is $O(n^2)$, and it's not possible to do better than that (assuming the only operation available on items is to test two items for equality), so this algorithm is optimal up to a constant factor.


Is there a function $t$ fulfilling $\mathcal{O}(0) \subset \mathcal{O}(t) \subset \mathcal{O}(1)$?

Yes, for example: $f(n)=\cases {0&$n\in\mathbb{N}_{even}$\\1&$n\in\mathbb{N}_{odd}$}$
This function is not in $O(0)$, since it has infinitely many $1$'s, but also $1$ is not $O(f)$ since it has infinitely many $0$'s.
To see more clearly why $1$ is not $O(f)$, consider any constant $c>0$ and any constant $n_0\in \mathbb{N}$. Then, if $1 \le c\cdot f(n)$ for any $n>n_0$, we will have that for any $n_0<n\in \mathbb{N}_{even}$, $1 \le c\cdot f(n) = c\cdot 0 = 0$ which is a contradiction. Hecne $1\notin O(f)$.
Therefore $O(0)\subsetneq O(f)\subsetneq O(1)$.
However, for computer science usages, as Pal GD said, we consider only monotonically increasing functions - in which case there is no such $f$.


The probabilistic method is typically used to show that the probability of some random object having a certain property is non-zero, but doesn't exhibit any examples. It does guarantee that a "repeat-until-success" algorithm will eventually terminate, but does not give an upper bound on the runtime. So unless the probability of a property holding is substantial, an existence proof by the probabilistic method makes a very poor algorithm.

In point of fact, probabilistic algorithms aren't actually constructive existence proofs, so much as they are algorithms to produce constructive existence proofs. The output is an object of the sort which it was meant to prove the existence of; but the fact that it will eventually yield one ("there will exist an iteration in which it yields an example — except with probability zero...") is not enough to be constructive; it will only be satisfactory to someone who already accepts that non-zero-probability-without-construction suffices for existence. Conversely, if you do have a good bound on the run-time, then there's in principle no excuse not to run it in order to actually produce an example. A good probabilistic algorithm still isn't a constructive proof, but a good plan to obtain a constructive proof.

Note that this idea, that a randomized algorithm is a proof strategy (as opposed to a proof in itself) to demonstrate an existential quantification, is not unlike the idea that induction is a good proof strategy to show a universal quantification (over the natural numbers). This analogy may seem compelling, as induction is essentially the heart of recursion as a computational technique. (For any positive integer $n$, if you want to decide whether $n^2$ is a sum of the consecutive odd numbers preceding $2n+1$, you can reduce this to investigating whether $(n-1)^2$ is a sum of the consecutive odd numbers preceding $2n-1$, and so forth.) Induction is essentially an algorithmic proof-strategy which we have elevated to a theorem, allowing us to have the knowledge without explicitly computing it each time. However, induction is accepted constructively because it is already an axiom(-scheme) of Peano arithmetic, and one which is independent of the other axioms. By contrast, there is no rule of inference or axiom which allows the probabilistic method to prove existence constructively, or to constructively prove that probabilistic algorithms produce existence proofs, or anything along these lines. You simply cannot prove that there are examples of a class of object from the fact that there is a probabilistic algorithm to construct it, unless you already accept that proposition, either as an axiom, or from other premises.

Of course, one might adopt a philosophical position intermediate to constructivism and the classical approach to existence, and say that what one wants is not constructions per se but construction-schema which are allowed to fail with any probability less than one; that would make any probabilistic construction "schematic", if not completely constructive. Where one wishes to draw the line, to say that they find an existence proof "satisfactory", ultimately depends on how much intuition (in a non-philosophical sense) they wish to gain from proofs.


Finite state automatons recognize regular languages. The advantage of regular languages is that it is usually trivial to express them formally.

FSA #1

$$L(M_1) = \left\{ a^kb^lc^m | k > 0, l \geq 0, m \in \{ 0, 1 \} \right\}$$

FSA #2

$$L(M_2) = \left\{ a^kb^lc^m | k > 0, l > 0, m \in \{ 0, 1 \} \right\}$$


Finding a subset of triplets of digits 0-9 such that each digit occurs 40 times in each position in the triplets

You could try using integer linear programming (ILP).  Use the following variables:

We have a variable $x_{ijk}$ for each triplet $ijk$, which is 1 if triplet $ijk$ is selected to be included in your set of 400, or 0 otherwise.
We have a variable $y_{ip}$ to count the number of times that digit $i$ appears in position $p$ among the selected triplets.

Now add constraints to capture all of your requirements:

We want to select 400 triplets: $\sum_{i,j,k} x_{ijk} = 400$.
We want each digit in each position to appear 40 times: $\sum_{i,p} y_{ip} = 40$.
We want the $x$'s and $y$'s to be consistent:

$$\begin{align}
  y_{i1} &= \sum_{j,k} x_{ijk}\\
  y_{j2} &= \sum_{i,k} x_{ijk}\\
  y_{k3} &= \sum_{i,j} x_{ijk}
  \end{align}$$

Finally, we require $0 \le x_{ijk} \le 1$ and $0 \le y_{ip} \le 1$ for all variables.

Now give the resulting system to an integer linear programming solver, and see if it can find a solution.

If it can't find a solution after a reasonable amount of time, your next step could be to find as small a subset as possible (not necessarily size 400, but hopefully not too much larger than 400).  Thus, replace $\sum_{i,p} y_{ip} = 40$ with $\sum_{i,p} y_{ip} \ge 40$, and instead of the constraint $\sum_{i,j,k} x_{ijk} = 400$, ask the ILP solver to minimize the objective function $\sum_{i,j,k} x_{ijk}$.  That will find a way to ensure each digit is presented at least as many times as desired, using as few trials as possible.


Event-based architecture (in the context of Distributed Systems)

A simple example of an event based architecture (in daily life) would be a postman sorting letters based on address. The “event” here is the arrival of new letters to sort.

If no letters arrive, the sorter will be idle, waiting for the letters to arrive. On the other hand if too many letters arrive at the same time, the sorter will stack those letters on his/her table and sort them based on their own speed.

The key takeaway here is the fact that the arrival of letters and sorting them is decoupled. The only bottleneck here is the size of the table on which the sorter can stack letters. The requirement is that all the letters should have an address.

The multiple producers of these letters (humans) can keep sending letters and be guaranteed the deliver of the letter (albeit not instantaneously). The consumers (sorter(s)) subscribe to the stream of letters and can sort/process them at their own speed.

This is impotant in distributed systems to do time intensive jobs that take a long time but don’t require instant results.

This allows your application to scale and be responsive independently of the time taken by these intensive jobs to complete.

A good example would be uploading video to youtube. You upload the video to youtube and youtube tells you that it will notify you when the video processing is complete.

In this scenario, your user facing application:
1) Accepts the uploaded video
2) Stores it in a location
3) Produces an event for consumers with details of video location

The consumer (a different server) would be listening for these events and do the video processing. After processing is complete, it would send a notification to the user.

Note: I don’t work with google. This is just an example of how I think it might work at a very basic level.


Shortest path visiting all nodes in an unrooted tree

Hint: Start from a source $s \in V$ to visit all vertices that $V$ is the set of vertices of the tree. All edges are visited twice except those which contribute to the longest path.

Then, the shortest possible path, visiting all nodes, is equal to $2 \times |E| - |P_{L}|$, where $|E|$ denotes the number of edges, and $|P_{L}|$ is the number of edges in the longest path. This can be achieved with time complexity $O (E)$.


Are Algebraic types just the combination of case classes and pattern matching?

Scala provides algebraic types and pattern matching in a way that is compatible with classes, but this is not what algebraic types are – it is Scala's realisation of the concept. Technically, pattern matching is not even needed for algebraic types; it just makes them must more convenient to use. One could instead use functions the pull apart the types. Early scheme's approach to ADTs would do just this.


How do you find out if the polygon lies to the right of a regular vertex?

I'm going to assume that your DCEL is counter-clockwise (ccw) oriented, meaning that if we traverse the list of half-edges incident the polygon's interior in order we make a counter-clockwise walk of the polygon. (This is standard.)

Let $v_i$ be your vertex, from the DCEL you can easily obtain $v_{i-1}$ and $v_{i+1}$, the vertices immediately preceding and following (resp.) $v_i$ in the ccw walk of the polygon. (The DCEL will have an edge $e_{i-1}$ with target $v_i$ and an edge $e_{i}$ with source $v_i$ both incident to the polygon $P$, and that $source(e_{i-1}) = v_{i-1}$ and $target(e_i) = v_{i+1}$.)

If $v_{i-1}$ is below $v_i$ (and $v_{i+1}$ is above $v_i$) then $P$ is to the left of $v_i$. Otherwise it is to the right. You can see this by drawing out the two possible cases. The point is that locally as you travel from $v_{i-1}$ to $v_{i+1}$ the polygon is on your left, so if you are traveling from a vertex above $v_i$ to a vertex below it, in your view the polygon is on your left, but in the "global" view, the polygon is on the right. However, if you are traveling from a vertex below $v_i$ to a vertex above it, then your view and the local view both have the polygon on the left. And by the definition of a regular vertex, those are the only two things we need to check.

Of course since you already know that one of $v_{i-1}$, $v_{i+1}$ is above and the other is below you only need to check for one. Something like, if $v_{i-1,x} < v_{i,x}$ then $P$ is left, otherwise right.

Here is a sketch:

I saw the code base you are using in your other posting on DCELs, so here is the code version:

First you will need to augment your vertex data structure to have fields for x and y:

struct vertex {
    struct half_edge *rep;  /* rep->tail == this */
    double x, y;
};

bool polygon_isleftof(half_edge *he) {
  return he->next->tail->y > he->tail->y;
}

By the way, when dealing with DCELs I have found that for many applications it is best to work with half-edges directly rather than vertices (in other words, if you want to pass a vertex to a function, just pass one of the half-edges for which it is a tail/source). That way you get two pieces of information: 1.) the vertex you are interested in and 2.) the face your are interested in. So in the code above my polygon_isleftof tells you whether the vertex which is the tail of he is to the right of the face which is incident to he. If I instead passed a vertex and a face the code would be much slower:

bool polygon_isleftof_slow(vertex *v, face *f) {
    //first we need to find a half-edge incident both f and v
    half_edge *walk = v->rep;
    //loop over all half-edges with tail equal to v:
    do {
        if (walk->left == f) break; //exit the loop if we find a half-edge incident f
        walk = walk->twin->next;
    } while (walk != v->rep);

    //If we didn't find a half-edge incident f and v, then return false:
    if (walk->left != f) {
        return false;
    } else {
        return walk->next->tail->y > walk->tail->y;
    }
}

Notice that in the first case, polygon_isleftof is $O(1)$ whereas in the second case polygon_isleftof_slow is $O(n)$. And since you are probably traversing the polygon using half-edges anyway, there is no reason not to just operate on half-edges and only access the vertices as needed in functions.


Computing childrens of ith node of a d-ary tree

The (traditional) binary heap (as e.g. in heapsort) is exactly your case, with $d = 2$; for 0-based arrays the children of $k$ are at $2 k + 1$ and $2 k + 2$. Analogously, in your case the children of $k$ are at $d k + 1, d k + 2, \dotsc, d k + d$.
The children of $0$ are at $1, 2, \dotsc, d$; children of $1$ start after that ($d + 1, d + 2, \dotsc, 2 d$), children of $2$ are at $2 d + 1, \dotsc, 3 d$, and so on. You should see the pattern here.


NP-completeness of scheduling to minimise tardy tasks with release times

Assume the new problem was polynomially solvable. Take any instance of the old problem and add release dates $r(t)=0$ for all $t \in T$. Then the new problem has a "yes" answer for the modified instance if and only if the old problem had a "yes" answer for the original instance. We have reduced the old problem to the new one, so the new one is at least as hard.

This reduction works for any scheduling problem if you (only) add release dates.


Does the word "efficient" usually refer to polynomial time or polylogarithmic time?

There is no one true answer.  It depends on context.  The most common context is one where polynomial-time is taken as more or less synonymous with efficient, so if you had no further context, I would certainly guess "polynomial time".  Polylogarithmic time is used only in very narrow contexts.

In general, if you think your audience might not be sure about the meaning, then I recommend you to define your terms.


Is there a strong argument to use shell sort over insertion sort on an array of 10 elements

It's an empirical question. First you need to come up with a probability distribution on arrays, for example the uniform distribution on all permutations of $1,\ldots,n$. For each $n$, you can measure the running time of both algorithms, and see which performs faster. The threshold 10 in reality depends on the implementation and the CPU, and is quoted only because it's a "nice" number, functioning as a rule of thumb.

So far I have assumed you're interested in minimizing the average case running time. If you're interested in the worst case running time, you'll have to run the algorithms on all permutations, which will quickly become infeasible.


About being able to sample a permutation of a finite set uniformly at random

Claim. Given access to finitely many samples of the uniform distribution over $\{1,\ldots,N\}$, you can sample uniformly from $\{1,\ldots,M\}$ iff $M \mid N^k$ (read: $M$ divides $N^k$) for some $k$.

Proof. Suppose first that $M \mid N^k$ for some $k$. Combine $k$ samples of $\{1,\ldots,N\}$ to get a uniform sample $x$ of $\{1,\ldots,N^k\}$, and return $x \pmod{M}$, which is understood to return a value in $\{1,\ldots,M\}$ rather than the more usual $\{0,\ldots,M-1\}$. There are exactly $N^k/M$ preimages of each $y \in \{1,\ldots,M\}$, namely $y,y+M,y+2M,\ldots,y+(N^k/M-1)M$. Therefore $x \pmod{M}$ is a uniform sample from $\{1,\ldots,M\}$.

Suppose next that using $k$ samples you can sample uniformly from $\{1,\ldots,M\}$. As before, we can think of the $k$ samples as a uniform sample from $\{1,\ldots,N^k\}$. Let $A$ be the preimage of $1$, that is the set of $x \in \{1,\ldots,N^k\}$ which cause the algorithm to return $1$. Since the algorithm returns $1$ with probability $1/M$, we must have $|A|/N^k = 1/M$ and so $|A| = N^k/M$, which can only happen if $M \mid N^k$. $\qquad\square$

Sampling a permutation on $M$ elements is the same as sampling a number in the range $\{1,\ldots,M!\}$. This is possible using finitely many samples from $\{1,\ldots,N\}$ if and only if $M! \mid N^k$ for some $k$.

This proof is quite elementary, so you can probably find many references, though none are really needed.


Proving a language (ir)regular (standard methods have failed)

This can be proven, but you need some nontrivial tools to do it.

Start with the set S = {0,3,5,6, ...} of non-negative integers having an even number of 1's in their base-2 expansion.

It is well-known that this set is "2-automatic"; that is, there is a finite automaton accepting exactly the base-2 expansions of elements of S.  Furthermore, it is well-known that this set is not ultimately periodic (that is, it is not true that there exists a period P such that after some point C, if x >= C is in S then so is x+P).  (If it were, then the associated Thue-Morse word 01101001... would be ultimately periodic, but it is known from Thue's 1912 paper not to contain any block repeated three times consecutively.)

Next, assume S is actually "3-automatic"; that is, there is an automaton accepting exactly the base-3 expansions of elements of S.  Then by a classic theorem of Cobham (Math. Systems. Theory 3 (1969) 186-192, this would imply that S is ultimately periodic.  But we have already seen it isn't.

You can find a lot more about these ideas in my book with Allouche, "Automatic Sequences".  Warning, though, our proof of Cobham is a bit flawed, and a corrected version by Rigo can be found online here:  http://arxiv.org/abs/0907.0624 .


Asymptotics of recurrence $f(x) = 8f(x/2) + O(1)$

The case $x^2 \le M$ has no effect on the asymptotic growth rate of $f$ since it is essentially telling you that $f(x) = \Theta(1)$ whenever $x$ is (at most) a constant.
Then you can use standard methods (e.g., the Master theorem) to show that $f(x) = \Theta(x^3)$.
Perhaps the following transformation will make this more evident.
Define $g(x) = \frac{f(\sqrt{M}x)}{M}$, then:
$$
\begin{align*}
g(x) &= \frac{f(\sqrt{M}x)}{M} = \begin{cases} \frac{8}{M} f(\sqrt{M}x/2) + \Theta(1) & \mbox{if }Mx^2 > M \\
1 & \mbox{if } Mx^2 \le M
\end{cases} \\
&=
\begin{cases} 8g(x/2) + \Theta(1) & \mbox{if }x > 1 \\
1 & \mbox{if } x \le 1
\end{cases}.
\end{align*}
$$
Since $g(x) = \Theta(x^3)$, you have $f(x) = Mg(\frac{x}{\sqrt{M}}) = \Theta(M \frac{x^3}{M^{3/2}} ) = \Theta(x^3)$.


The Hamming codes are optimal in the sense that among all codes with the same block length and minimal distance, they contain the most number of codewords. We know this because Hamming codes are perfect codes: their number of codewords matches the Hamming bound, which is an upper bound on the number of codewords in a code with given block length and minimal distance.


It is in NL.  Here is the outline of a possible proof:

If you already fix s′, you can check whether s′ satisfies your condition or not in NL.  Reachability is easy, non-reachability is by the Immerman–Szelepcsényi theorem, and taking the AND of two conditions is easy.
Because there are only polynomially many possibilities for s′, you can test these possibilities one by one until you find the right s′ or find out that no such s′ exists.  Alternatively, you can guess s′ by using nondeterminism.


Using SMT solvers to generate random solutions to given predicate

Let $\varphi(x)$ be the SMT instance, so the task is to find $x$ such that $\varphi(x)$ is true.

One approach is to fix a hash function $h$ that maps a value of $x$ to an element of some small set $S$.  Then, you randomly select a value $s \in S$, and ask your SMT solver to find a satisfying assignment for the formula $\varphi(x) \land h(x)=s$.

If you want to generate $k$ random satisfying assignments to $\varphi(x)$, you might choose $S$ to have size a bit bigger than $k$; that will probably suffice.

You probably want to make the hash function $h$ as simple as possible.  There is a tradeoff between a simpler hash function (easier for the SMT solver to find satisfying assignments to $\varphi(x) \land h(x)=s$) and a better hash function that mixes the bits better (leads to more random solutions $x$).  In practice, often surprisingly simple hash functions suffice.  For instance, sometimes your hash function can be chosen via the following simple procedure: pick a random subset of the variables in $x$, project to just those variables, and then hash those variables in some simple way.  The hash function itself can be a relatively simple function, e.g., a random linear function: for example, select a random boolean matrix and multiply it with the bit vector obtained from $x$, so that $h(x)=Mx$ for some boolean matrix $M$).

There may be other ways to do it, but this is one way that allows you to use an existing SMT solver, unmodified, as a black box.


What you forget is that all the mappings you use have to be
computable. When you state that matching cardinalities ensure the
existence of a mapping, that may be true, but the mapping is unlikely
to be computable, precisely because that would let you get a
contradiction with Rice theorem. In computability (at least for what I
know of it), everything is either finite or countably infinite. So existence of
mappings is usually not an issue. The problem is whether it is a
computable one.

To say it differently, there is certainly a mapping (actually
uncountably many) that associates precisely palindromic words with
total computable functions. But, given such a palindrom $w$, which the
mapping associates with a function $f_w$ there is no way you can
actually use such a mapping to get the result of applying $f_w$ to
some argument. You mapping does not give you any way of identifying
the function or computing with it. Your language has non computable
semantics.


This is an interesting question. Certainly worth asking.

The choice of a data structure is very much dependent on what you want
to do with it. A more costly sophisticated structure, no matter how
smart, is a bad choice if you can meet your need with something
cheaper in space or time.

As I was writing this answer, I discovered that the wikipedia article
on tries does discuss to a significant extent comparison of tries with other
data structures.

One advantage of binary search trees (BST) is that they keep ordered
lists, for some arbitrary order that can be tested.  Actually the
order is often used only to help organization and retrieval, but there
are applications where you want to actually access the elements of your
ordered subset following the order of elements.  BST will provide you
with such an order.

I do not see any obvious way of doing it with
tries for an arbitrary order (but I did not try hard). However, tries
do work with lexicographic order, and can be used for lexicographic
enumeration of the keys, using simply a preorder traversal of the
tree implementing it.

Similarly, asking for the current rank of an element in the set
represented by a BST , or accessing an element by its current rank is
fairly easy to implement in $\log n$ time (by keeping track of the
weight of subtrees).  It seems not so tractable on a trie, except
again if one is interested in lexicographic order, in which case the
solution is similar to that used for BST.

Another point to consider is cost of basic operations (insertions,
deletions, search). With a balanced BST it is done in $\log n$ time,
where $n$ is the number of elements. For a trie, the cost is linear in
the size of the element representation. It is hard to compare the two
kinds of cost, and one would think the choice is very much problem
dependent.  This also applies to such operation as access by rank, or
rank retrieval.

The cost of number representation in a BST or in a trie may also be an
issue, as a trie will represent each digit separately (up to some
optimizations). It is possible that, for very large numbers, expressed
with a large base, the trie representation would be a better choice. I
am not sure.

There is probably more to say. The conclusion is that it is probably
worth thinking whether tries can be used, but it may be actually limited.


Is it possible to determine if C=A+B faster than adding A+B in logical circuits

Consider computing $\overline{a_{n-1}\ldots a_0}+\overline{b_{n-1}\ldots b_0}=\overline{c_{n-1}\ldots c_0}$. If the last $(k+1)$-bits are correctly computed, then $c_{k+1}$ is correct if and only if
$$\big((a_k\wedge b_k)\vee((a_k\oplus b_k)\wedge \neg c_k)\big)\oplus a_{k+1}\oplus b_{k+1}=c_{k+1}.$$
That is because the first part, $(a_k\wedge b_k)\vee((a_k\oplus b_k)\wedge \neg c_k)$ indicates whether there is a carry-over. So you can check the correctness for each bit in parallel.

However, in theory both questions require $\Omega(\log n)$-depth bounded fan-in circuits. Good thing is, for the checking problem the $\log n$ part in the circuit depth is only for a $n$-bit $\textsf{AND}$, so I think it is a constant boost in the performance.


Worst time complexity for finding a median number for a list and array data structure

The term "data structure" typically refers to a way to organize/store data, and the operations to create, maintain, and access them.

The asker is probably expecting you to assume specific implementations, probably as given in the course, then come up with algorithms to access the median, and discuss their respective runtime cost.


What should we return when pattern matching on a Path constructor?

it matches the Path pos 0 == neg 0 and returns pos 1 -- say, matches a Path, but returns a normal integer

My understanding is that it matches points of path rather than path itself. This is why the matching is on posneg x (where x : I) rather than posneg itself.

Since paths can be seen as (special) maps from I, we can think of HIT constructors as just a special of regular constructors, i.e.

  posneg : I ↝ HitInt [i0 ↦ pos 0 ; i1 ↦ neg 0]

where if you ignore "special" properties of Interval, it looks like a regular constructor (in cubicaltt notation it already looks similar except that I is always treated specially).

  What's interesting is that, in Agda it'll fill pos 1 in the case body when I use Agda's proof-search.

It's the only way to satisfy constraints imposed by previous definitions (this works for both zero cases). In fact, Agda can correctly solve even two holes (in right order):

sucHitInt : HitInt → HitInt
sucHitInt (pos n) = pos (suc n)
sucHitInt (posneg i) = {!!}
sucHitInt (neg zero) = {!!}
sucHitInt (neg (suc n)) = neg n

  Why it's not returning a Path like  pos 1 (even this is not a member of the higher inductive family)?

Again, since we're matching on points rather than paths; for symmetry it's possible to imagine that case as equal to:

sucHitInt (posneg i) = (λ _ → pos 1) i

reading somewhat like "for all projections from I at i to path posneg we have projections from I at I to constant path (λ _ → pos 1)". This doesn't quite work in Agda (because typecheking lambda application directly isn't very well supported), however the following (with the same meaning) does:

sucHitInt (posneg i) = refl {x = pos 1} i

Finally, abusing notation, we could rewrite that as

(ap sucHitInt posneg) i = (refl {x = pos 1}) i

(where ap (from the HoTT book) corresponds to cong in typical Agda) and, getting rid of i from the both sides, recover path to path mapping.

PS: i'm new to cubical myself, so hopefully someone can correct or extend my answer


Probability that a random graph will remain planar after adding an edge

Let $S$ be the set of planar graphs on $n$ vertices, and let $E(S,\overline{S})$ be the set of edges between $S$ and its complement, that is, the set of pairs $(G,e)$ where $G \in S$ and $G \cup \{e\} \notin S$. The edge-isoperimetric inequality states that
$$
\frac{|E(S,\overline{S})|}{|S|} \geq \binom{n}{2} - \log_2 |S|.
$$
It follows that the probability that you're after is at most
$$
\frac{\log_2 |S|}{\binom{n}{2}-(3n-6)}.
$$
It is known that $\log_2 |S| = O(n \log n)$ (see for example Gimenez and Noy, The number of planar graphs and properties of random
planar graphs, and so we conclude that your probability is at most $O\left(\frac{\log n}{n}\right)$.

On the other hand, the same paper shows that with constant probability, a random planar graph has an isolated vertex. When this happens, there is $\Omega\left(\frac{1}{n}\right)$ probability to add an edge adjacent to it, leaving the graph planar. Hence your probability is at least $\Omega\left(\frac{1}{n}\right)$.


Difference between substitution, morphism, and homomorphism

Indeed morphism and homomorphism are the same in formal language theory. They are letter-to-string mappings $h:\Sigma \to \Delta^*$, and then extended to string-to-string mappings  $h:\Sigma \to \Delta^*$ in a morphic way: $h(\varepsilon) = \varepsilon$, and $h(xy) = h(x)h(y)$ for strings $x,y\in \Sigma^*$.

A substitution is a letter-to-language mapping, which is likewise extended to a string-to-language mapping. By identifying a singleton language $\{x\}$ to the string $x$, morphisms are seen as special case of substitutions.

A letter-to-letter morphism is sometimes called a coding.


Your problem is known as maximum weighted bipartite matching or the assignment problem, and has efficient algorithms such as the Hungarian algorithm.


Given a Turing machine $M$, we can construct another Turing machine $T$, which on input $1^n$ simulates $M$ for $\log n$ steps, and returns whether $M$ halted within these steps. The new Turing machine runs in linear time, and is equivalent to the constant time Turing machine which always returns "No" iff $M$ doesn't halt. Therefore program equivalence is undecidable even for linear time Turing machines.


Closure against the operator $A(L)=\{ww^Rw \mid w \in L \wedge |w| \lt 2007\}$

Since $|w| < 2007$, the number of strings like $ww^Rw$ is finite. So $A(L)$ is finite for all $L$ and is hence regular.


How to use Master Theorem with strange format of $b$ parameter?

Not every recurrence falls within the bounds on the master theorem. Your recurrence is an example. However, by unrolling your recurrence, we can come up with an explicit formula:
$$
T(n) = 6(n+1) + T(n-1) = 6(n+1) + 6n + T(n-2) = \cdots = \\
6(n+1) + 6n + \cdots + 6\cdot 2 + T(0) = \\
6(n+1) + 6n + \cdots + 6\cdot 2 + 6\cdot 1 = \\
6 \sum_{m=1}^{n+1} m = 6\frac{(n+2)(n+1)}{2} = 3(n+2)(n+1).
$$


Pumping lemma regarding {a^2k w | w ∈ {a, b}*, |w| = k}

In typical usage of the pumping lemma, you assume that the word you chose for pumping is written as $w=xyz$, with $x,y,z$ satisfying the conditions of the pumping lemma.

Then, in most cases, you reach a contradiction by saying that e.g., $xy^2z$ is not in the language. This is "pumping up", since you "add" copies of $y$.

In this case, however, you reach a contradiction by looking at the word $xz$ (i.e., $xy^0z$). So you are pumping "down", or subtracting copies of $y$.

The reason for this is that if you look at e.g., $xy^2z$, then you get a word of the form $a^{2p+k}b^p$, but this word might be written as $a^{2r} a^lb^p$ with $l+p=r$, so you would not reach a contradiction.


Sorting n weight disks with decision tree

I suspect that the question is looking for a non necessarily tight lower bound to the number of comparisons needed.
The decision tree needs to be able to return the correct sorted sequence no matter what the initial permutation of the elements is. Therefore, it must have at least $n!$ leaves (one for each output permutation). Each internal vertex in the decision tree represents a comparison has has $2$ children. This means that the height of the tree must be at least $\log_2 n!$. Since the height must be an integer, you can take the ceiling.
However no algorithm can attain this number of comparisons in the worst case for all values of $n$ (notice that the intended answer does not use the asymptotic notation).
Here you can find the number of comparisons needed to sort $n$ elements for some small values of $n$. For $n=15$, $\lceil \log 15! \rceil = 41$ but $42$ comparisons are needed.
To answer your second question, $\lceil n \log n \rceil$ is incorrect since it not a valid lower bound. For example, for $n=2$, $2 \log 2 = 2$ but $1$ comparison is sufficient. You are right in saying that $O(\log n!) = O(n \log n)$ but notice how the answers are not using the big-Oh notation.
Finally, you need the discs to be linearly ordered otherwise it doesn't make sense to compare them. Moreover the fact that the input elements are distinct allows you to consider a decision tree where the outcome of each comparison is binary and is either "greater than" or "smaller than".


Proof that regular languages are closed against taking the even-length subset

The language $Even = \{w\in\Sigma^{\ast}\mid \text{length of }w\text{ is even}\}$ is regular. user5507's answer demonstrates this with an NFA, and it's a basic exercise in most texts.

Then given that $L$ is regular, if we know that regular languages are closed under intersection for the purposes of the question, then the language $L'=L\cap Even$ is also regular.

If we're not allowed to use these closure properties, we can recapitulate the construction that gives the closure property (I'll just sketch it). Given a DFA $M_{L}$ for $L$ and a DFA $M_{Even}$ for $Even$, we can construct a DFA for $L' = L\cap Even$ that has a state space that is the product of the state spaces of $M_{L}$ and $M_{Even}$, with the follow transition rule: if $\delta_{L}(\sigma, q_{i}) = q_{j}$ and $\delta_{Even}(\sigma, p_{m})=p_{n}$ where $\sigma \in \Sigma$ and the $p$s and $q$s are states of the appropriate machines, then the product machine has a transition $\delta_{prod}(\sigma,(q_{i}, p_{m})) = (q_{j}, p_{n})$. Our accepting states are those states $(q_{i},p_{j})$ where $q_{i}$ and $p_{j}$ are accepting states in their respective machines.

That's the long an fiddly way around.

The second question depends on $L$, that is, if $L$ is not regular, then the intersection of $L$ and $Even$ may is not necessarily regular - the $w\in L$ in the definition is key.

EDIT: actually, reading vonbrand's answer, I misunderstood the second part. He is quite correct - the second language is the intersection of $L$ and $X=\{w\in\Sigma^{\ast}\mid \exists i \in \mathbb{N} \text{ such that } |w| = 2^{i}\}$ - not $Even$. So while what I said about $L \cap Even$ with $L$ not regular holds, $X$ isn't regular to begin with, so we get the same situation, but $L$ is regular and $X$ isn't.


What are the disadvantages of having many registers?

The disadvantage is higher latency per instruction.  Either you need to run the processor clock slower or you need to pipeline the register file, so each instruction will take more cycles.  (Pipelining the register file is difficult, and rarely done.)  A register file is a physical thing, thus must obey the laws of physics.  (In particular, that our universe has only three spatial dimensions, and that the speed of light is a constant.)  Suppose your register file is 2 dimensional (as all are today).  Then the register bits are typically arranged in a rectangle with width $b$ (where $b$ is the number of bits stored in each register) and height $N$ (where $N$ is the number of registers.)  (This assumes that the circuit to implement the bit is approximately square.)

Here's a picture of a 3-ported 4x4 register file that I found at http://gyan.fragnel.edu.in/~surve/COA/ISA/Images/Figure4.37.jpg:

Each time you read a register you need to propagate a read-enable signal to each bit of that register across the width of the array.  If the read-enable wires are buffered then
the delay to propagate a signal down the wire is proportional to the length of the wire.  (Neither the horizontal nor vertical wires in this diagram are buffered.  Buffering the vertical wires is actually hard, because that's a many-to-1 bus, not a 1-to-many point-to-point signal, so you may not be able to do that at all.  In the case that you can't buffer a wire, the wire will have a delay proportional to something like the square of the length of the wire.)

So at best a register file access is going to take time proportional to $O(b+N)$.  (That doesn't count the time for the decoder, and assumes that you somehow figure out how to buffer all the wires.)

To sum up: the more bits you are storing, the slower the storage.


Use binary search to find the smallest factor, divide and repeat.


If a language has a regular grammar, is it regular?

A regular language can be defined as "a language with a regular grammar". So, yes, the existence of a regular grammar for $L$ means that $L$ is regular. [Note 1]
That doesn't mean that every grammar for $L$ is regular. That doesn't matter for this purpose.
It's important to keep the distinction between languages and grammars clear. In general, we say that a language is X if it has at least one grammar which is X (deterministic, regular, context-free, etc.).
Sometimes, the categorization of grammars is finer (makes more distinctions) than the categorization of languages. A grammar can be left regular or right regular, but a language is simply regular: if it has a left regular grammar, it must have a right regular grammar, and vice versa. Similarly, a grammar might be LR(1), LR(2), etc., but this distinction doesn't apply to languages because if there is an LR(k) grammar for a language, there is also an LR(1) grammar.
This distinction is very important when discussing the relationship between different categories. Failing to make the distinction correctly leads to confusion, because the contexts are very different. For example, there is a simple linear-time algorithm which will tell you if a grammar is regular. However, there is no algorithm which can tell you whether the language recognised by an arbitrary context-free grammar is a regular language.

Notes

I believe the original definition of regular languages was based on Kleene's regular expressions. The concept of regular grammars comes from Chomsky's seminal work, in which he called them "Type 3 grammars". His 1959 paper which introduces this hierarchy of grammars (and, indirectly, of languages) contains the proof that Type 3 languages are the same as what he called "finite state languages" -- languages which can be recognised by a Finite State Automaton.
This equivalence leads some people to define "regular language" as "a language which can be recognised by a FSA", although that definition fails to justify the use of the word "regular". (It is the definition found in Michael Sipser's Introduction to the Theory of Computation, and also on Wikipedia, for example.)
It is also easy to show that the set of languages which can be described by a regular expressions (in Kleene's sense) is precisely the same as the set of languages which can be described with a regular grammar.


Are there problems that are polynomial-time equivalent to factoring composites?

I assume that you meant to consider the difference between $BQP$ and $NP$ rather than $P$ and $NP$. $P$ is primarily only defined using deterministic time bounded Turing Machines while $BQP$ is specific to bounded error polytime quantum computers.

Factoring is, of course, in $NP$ (function version being in $\mathcal{F}_{NP}$), so it should easily follow that anything polynomial time reducible to factoring is going to have a polynomial time verifier. If you were actually asking if any polynomial time verifiers share the same "hardness" as factoring, then the answer is: no idea. It would require making assumptions about whether or not factoring is in $P$.

I am afraid that I could not find a non-number theoretic set of problems that are known to be polynomial time reducible to factoring. Despite much study, the complexity of factoring is still very open. Knowing where it falls will provide many additional answers to your question. I'll go over what I have:

Two well known ones are computing Quadratic Residuosity and computing the Euler Totient, $\phi (n)$. The equivalence between factoring and Euler totient is very straight forward, especially to those that have ever looked into RSA.

A paper by Tibor Jager and Jorg Schwenk shows that the Quadratic Residuosity Problem and Subgroup Membership Problem are "generically equivalent" to factoring.

It is still open as to whether or not the Discrete Log Problem and the decision version of Composite Residuosity are also equivalent. Though, Pomykała wrote on the polynomial time reducibility of Discrete Log (composite moduli) to Factoring recently and presented a deterministic subexponential time algorithm for just that.

You may have a lot of success researching the Hidden Subgroup Problem. For finite Abelian groups, quantum computers have the advantage of being able to do this in polynomial time via Fourier transforms. Shor uses the fact that Factoring, Discrete Log, and some others are special cases of this problem.


Why are non-deterministic Buchi automata factorially succinct when compared to deterministic Rabin Automata?

This is Theorem 1.30 in the chapter "Omega-Automata" in the book "Automata, Logics, and Infinite Games: A Guide to Current Research" edited by Erich Grädel, Wolfgang Thomas and Thomas Wilke. They have a proof as well (and a literature referene to the original publication).

Note that instead of the nondeterminstic Buchi automaton having $n$ states, it needs to have $O(n)$ states to make the proof work. The problem is then defined slightly differently to make this precise.

Note that it is a bit confusing if you write "Buchi automata" and "deterministic Rabin automata" in the same question if the former are meant to be "nondeterministic Buchi automata". There is ample work both on deterministic and non-deterministic Buchi automata, so spelling out which variant is meant is important.


Definitions of: virtual address space, page size

Wikipedia defines a virtual address space as follows:

  In computing, a virtual address space (VAS) or address space is the
  set of ranges of virtual addresses that an operating system makes
  available to a process.

This definition is OK. However, I'll define the term "virtual address space" one word at a time.

  space

space is a mathematical term that generally means a set of things, where these things are potentially related in one or more ways.

  address

An address is generally an identifier for a thing, which is distinct from the thing itself. In this context, an address is a value that potentially identifies a physical device in the computer system. Typically, addresses are non-negative integers that identify memory locations that can hold data, and each address is represented as a constant number of binary digits.

  virtual

Virtualization means to create an interface for something that is different from its actual interface that is built with the thing. This is useful for many reasons such as managing a resource for multiple users or providing protection for a resource from being misused or corrupted.

Now let's put it all together. A virtual address space is a set of addresses created by the virtualization system (the OS) to allow an application to access system resources indirectly so that the system can control access to its resources.

  Virtual address space is the amount of bytes that can fit into RAM
  cells of all virtual addresses belonging to this virtual address space
  (virtual address space HAS MANY pages HAS MANY virtual addresses).

A VAS is not a single number (although it can be a set that contains a single address). Also a VAS is not memory itself; it does not store anything because it can't. Moreover, given only a VAS, you can only determine how many virtual addresses you have, but not how much memory you can use. you can have a 4 GB VAS, but zero physical memory locations. That's because of virtualization. That's what makes it virtual. It's up to the OS that creates it. Also the term "page" is independent from the term "virtual address space" in general. Although the OS can choose to partition the VAS into virtual pages, where each virtual page is a sub-set of the VAS.

  Page is a set of virtual addresses (and it maps to the frame - a set
  of actual physical RAM addresses).

Yes. Although a virtual page may not map to anything (invalid).

  Size of a page = amount of bits that can fit into this page. So, if
  the system is byte-addressable (meaning one RAM cell can hold 8 bits),
  page size is 8 * number of RAM addresses in a page.

Yes. When a virtual address space is said to be byte-addressable it means that each virtual address (an identifier) can identify an 8-bit resource (typically, physical memory cells). When a physical address space is said to be byte-addressable it means that each (valid) physical address (an identifier) does identify an 8-bit physical resource (typically memory cells).


Is subset sum problem with multiplicities NP-complete?

The problem can be solved in polynomial time.

If any of the $a_i$ are zero, then the answer is "yes" (you can set the corresponding $x_i$ to 1, and all other $x_j$ to 0).  So let's assume all of the $a_i$ are non-zero.

If all of the $a_i$ are strictly positive, then the answer is "no" (if $x_i$ is the one that's set to something non-zero, then $x_i>0$ and $a_i>0$, so $a_1 x_1 + \dots + a_n x_n \ge a_i x_i > 0$).  So we can assume at least one of the $a_i$ is strictly negative.

If all of the $a_i$ are strictly negative, then the answer is "no" (if $x_i$ is the one that's set to something non-zero, then $x_i>0$ and $a_i<0$, so $a_1 x_1 + \dots + a_n x_n \le a_i x_i < 0$).  So we can assume at least one of the $a_i$ is strictly negative.

If at least one of the $a_i$ is strictly positive and at least one is strictly negative, say $a_i>0$ and $a_j<0$, then the answer is "yes" (you can take $x_i=-a_j$, $x_j=a_i$, and set all other $x$'s to zero; then $a_1 x_1 + \dots + a_n x_n = a_i x_i + a_j x_j = -a_i a_j + a_i a_j = 0$).

These cases cover all the possibilities: at least one of the above cases must hold.  So, we obtain a polynomial-time algorithm for the original problem.

Credit: I got the key idea from Discrete lizard.


Finding the Range of Solutions for KSum Variation

Suppose that the value at location $i$ is $j$. According to the continuity of $k$-sums (mentioned in an answer to the linked question), the range of possible sums of values at locations $1,\ldots,i-1$ is $$(i-1)a + \binom{i-1}{2},\ldots,(i-1)(j-1) - \binom{i-1}{2}.$$
Similarly, the range of possible sums of values at locations $i+1,\ldots,k$ is
$$
(k-i)(j+1) + \binom{k-i}{2}, \ldots, (k-i)b - \binom{k-i}{2}.
$$
Therefore the range of possible sums of all $k$ values is precisely
$$
(i-1)a + \binom{i-1}{2} + j + (k-i)(j+1) + \binom{k-i}{2}, \ldots, \\
(i-1)(j-1) - \binom{i-1}{2} + j + (k-i)b - \binom{k-i}{2}.
$$
We want to find for which values of $j$, the value $s$ is in this range. We get the following inequalities:
$$
(i-1)a + \binom{i-1}{2} + \binom{k-i+1}{2} + (k-i+1)j \leq s, \\
(k-i)b - \binom{i}{2} - \binom{k-i}{2} + ij \geq s.
$$
Therefore the range of $j$ is
$$
\max\left(\left\lceil \frac{s-(k-i)b + \binom{i}{2} + \binom{k-i}{2}}{i} \right \rceil,a+i-1\right) \leq j \leq \\
\min\left(\left\lfloor \frac{s - (i-1)a - \binom{i-1}{2} - \binom{k-i+1}{2}}{k-i+1} \right \rfloor,b-k+i\right).
$$


Just an extended comment.

I think that before trying to find a reduction, you should try to better formalize the problem:

define exactly what the parameters of the problem are, formalize their constraints, and formalize the question;
try to simplify (or remove) the details;

For example:

If a group consist of 1 student, this conversation last 10 minutes. $\rightarrow$ it is equivalent to a group of two students, so you can remove it;
Timespan is 13.00-19.00 $\rightarrow$ in the other rules you use minutes, so convert the "timespan" to $T$ minutes;
try to think if a simplified version of the problem has a quick solution or it can be still hard (e.g. if the event last only one day rules 7 and 8 can be dropped)
express the rules with a math formula: e.g "if an elementary group $E$ of $n$ students talk with a high school group $H$ of $m$ students then the total time $TT$ required is $TT(E,H)=....$"; "the total max wait time $WT$ for group $E$ is $WT = ...$"

Furthermore there is a point that it is not clear (to me):

suppose you have an elementary school group $E$ having $n$ students that talk with a high school group $H$ having $m$ students; what is the total time required? (1) $5 * n$ (the talk is public) or (2) $5 * ( n / m)$ (each student of E talks with a single student of H). If the talk is public, then the number of students is redundant, and you can think only in terms of total time required by a school group.


The number of different regular languages

This is a summary of the paper On the Number of Distinct Languages Accepted by Finite Automata with n States. The paper provides relatively easy, yet far from tight, lower and upper bounds on the number of distinct languages accepted by NFA's. Their discussion on the number of distinct DFA's is very insightful, so I will also include that part.

The paper starts with a quite rigorous asymptotic for the number of distinct languages accepted by a DFA with $n$ states over a unary alphabet. This is done by observing under which conditions a given $n$-state unary DFA is minimal. In such cases the description of the automaton may be mapped (bijectively) to a primitive word, and the enumeration of such words is well-known and done with the help of the Möbius function. Using that result, bounds for non-unary alphabets, both in the DFA and in the NFA case, are proven.

Let's go into more detail. For a $k$-letter alphabet, define
\begin{align*}
 f_k(n) &= \text{the number of pairwise non-isomorphic minimal DFA's with } n \text{ states}\\
 g_k(n) &= \text{the number of distinct languages accepted by DFA's with } n \text{ states}\\
 G_k(n) &= \text{the number of distinct languages accepted by NFA's with } n \text{ states}
\end{align*}
Note that $ g_k(n) = \sum_{i=1}^n f_k(i)$. We start with $f_1(k) $ and $g_1(k)$.

Enumeration of Unary DFA's

A unary DFA $M = (Q, \{a\},\delta, q_0,F) $ with states $q_0,\dots, q_{n-1}$ is minimal iff

It is connected. Thus, after renaming, it the transition diagram consists of a loop and a tail, i.e. $\delta(q_i,a) = q_{i+1}$ and $\delta(q_{n-1},a)=q_j$ for some $j \leq n-1$.
The loop is minimal.
If $j \neq 0$, then either $q_{j-1} \in F $ and $q_{n-1} \notin F$ or $q_{j-1} \notin F $ and $q_{n-1} \in F$.

The loop $q_j,\dots, q_{n-1}$ is minimal iff the word $a_j \cdots a_{n-1}$ defined by
\begin{equation*}
 a_i = \begin{cases}
        1 \quad \text{if } q \in F, \\
        0 \quad \text{if } q \notin F
       \end{cases}
\end{equation*}
is primitive, which means it cannot be written in the form $x^k$
for some word $x$ and some integer $k \ge 2$.
The number $\psi_k(n)$ of primitive words of length $n$ over $k$-letter alphabets is known, see e.g. Lothaire,Combinatorics on Words. We have
\begin{equation*}
 \psi_k(n) = \sum_{d | n} \mu(d) k^{n/d}
\end{equation*}
 where $\mu(n)$ is the Möbius function. With the help of $ \psi_k(n) $ the paper proves exact formulas for $f_1(n)$ and $g_1(n)$ and shows that asymptotically (Theorem 5 and Corollary 6),
\begin{align*}
  g_1(n) &= 2^n \left(n-\alpha+O \left(n 2^{-n/2} \right)\right) \\
  f_1(n) &= 2^{n-1}\left(n+1-\alpha+O \left(n 2^{-n/2} \right)\right).
\end{align*}

Enumeration of DFA's

The next step is a lower bound for $f_k(n)$. Theorem 7 states that
\begin{equation*}
f_k(n) \ge f_1(n) n^{ (k-1)n} \sim n 2^{n-1}n^{(k-1)n}.
\end{equation*}
For a set $\Delta \subset \Sigma$ of an automaton $M$, define $M_{\Delta}$ as the restriction of $M$ to $\Delta$.
The proof works by considering the set $S_{k,n}$ of DFA's $M$ over the $k$-letter alphabet $\{0,1,\dots,k-1 \}$ defined by

Letting $M_{ \{0 \}}$ be one of the $f_1(n) $ different unary DFA's on $n$ states, and
Choosing any $k-1$ functions $h_i : Q \to Q$ for $1 \le i < k$ and defining $\delta(q,i) = h_i(q)$ for $1 \le i < k$ and $q \in Q$.

The observation is then that $S_{n,k}$ contains $f_1(n) n^{ (k-1)n}$ different and minimal languages.

Enumeration of NFA's

For $G_1(n)$ one has the trivial lower bound $2^n$, since every subset $\epsilon, a,\dots, a^{n-1}$ can be accepted by some NFA with $n$ states. The lower bound is improved slightly, yet the proof is rather lengthy.
The paper Descriptional Complexity in the unary case by Pomerance et al shows that $G_1(n) \le \left( \frac{c_1 n}{\log n}\right)^n $.
Proposition 10 shows that, for $k \ge 2$ we have
\begin{equation*}
 n 2^{(k-1)n^2} \le G_k(n) \le (2n-1) 2^{kn^2} +1.
\end{equation*}
The proof is quite short, hence I include it verbatim (more or less). For the upper bound, note that any NFA can be specified by specifying, for each pair $(q,a)$ of state and symbol, which subset of $Q$ equals $\delta(q,a)$ (hence the factor $ 2^{kn^2}$. We may assign the final states as follows: either the initial state is final or not, and since the names of the states are unimportant, we may assume the remaining final states are $\{1,\dots,k\}$ for $k \in [0..n-1]$. Finally, if we choose no final states, we obtain the empty language.
For the lower bound the authors proceed in a similar way as in the proof for the DFA case: Define an NFA $M=(Q,\Sigma,\delta,q_0, F)$ with $\Sigma = \{ 0,1,\dots,k-1 \}$, $Q=\{ q_0,\dots, q_{n-1} \}$ and $\delta$:
\begin{align*}
 \delta(q_i,0) &=q_{(i+1) \mod n} \quad \text{for } 0 \le i <n \\
 \delta(q_i,j) &=h_j(i) \quad \text{for } 0 \le i <n,\, 1 \le j < k
\end{align*}
where $h_j: \{ 1,\dots,n-1\} \to 2^Q$ is any set-valued function. Finally, let $F=\{q_i\}$ for any $i \in [0..n-1]$. There are $ 2^{(k-1)n^2} $ such functions and $n$ ways to choose the set of final states. One can then show that no two such NFA's accept the same language.


How to prove that there is a function index t so that t³ + t + 1 is an index of the same function?

This is just a special case of Rogers' fixed-point theorem which says that, for any total computable function $f$, there exists $t$ such that $\phi_t = \phi_{f(t)}$.


Unreachable Real Numbers - Randomness & Computability

In a nutshell: Printing a random non-computable real is a meaningless task, for precise technical reasons. The meaningful problem is to print non-computable numbers precisely identified by some unique property. But these cannot be printed by any program precisely because they are not computable. Using randomness in the hope of printing by chance the uncomputable
number you are interested in is impossible with a program, unless you use a physical random
phenomenon as randomness source (depending on physics, with probability zero, and without knowing whether you are succeeding).

I am not sure what you mean by a number that is not "reachable by
humanity".

The fact that there is an infinity of real numbers between two
integers does not imply that there are more real numbers than
integers (though there are more).

For example, there is an infinity of rational number between two
integers, but the number (cardinality) of integers and rational
numbers is the same. Actually, there is an infinity of rational
numbers between any two rational numbers, but it does not imply that
there are more rational numbers than rational numbers.

By the way, there is an infinity of rational numbers between any two real
numbers, but there are more real numbers than rational numbers.

That should at least tell you that determining which set is bigger is
not at all obvious, and is not related to the number of angels who can
dance between two numbers.

Then why are there more real numbers than integer? Here is one of the
proofs due to Cantor. The reals in the interval $[0.0, 1.0[$ are isomorphic
to infinite sequences of the symbols 0 and 1, which is their
representation in binary notation (by just adding a decimal/binary point in
front). If you consider any enumeration of these infinite strings, it
is always possible to define a string that is not in the enumeration,
by using for its $n^{th}$ symbol the opposite (1 for 0, and 0
for 1) of the $n^{th}$ symbol of the $n^{th}$ number of the
enumeration. This means that if you attempt to define a
one-one correspondance between the integers (used to enumerate) and the
reals (being enumerated) there are always reals that are not included
in the enumeration, which can be interpreted as implying that there
are more reals than integers.

This technique is a diagonalization proof, similar to the proof technique used for proving the
undecidability of the halting problem.

Now, as remarked in the question, any program texts can be read as an
integer, so that one may consider there are no more programs than
integers. This is why we may conclude that there are numbers that
cannot be computed by a program, hence cannot be printed (else, each real could be mapped to the integer corresponding to the
program that prints it.). But this
fast reasonning may not be so convincing, so lets get more into
details. and also consider an actual example.

Your printing device, assuming it does what you expect,
even if it started at the big bang, is only producing digits one by
one, and will at any time have produced only a finite number of
digits, say $n$. That only defines a rational number, and even if we
are actually printing some irrational number. Assuming we are using binary numbers,
if we have already printed $n$ digits, they correspond to a rational
number $x$, and all we know is that the number we ultimately print
will be in the interval $[x, x+2^{-n}[$. But this interval will always
contain an infinity of rational numbers, of computable real, and of
uncomputable reals. And this will remain so for any future value of $n$. Stating that you want to print an uncomputable
number, any  uncomputable number, is a meaningless endeavor.
It reminds me of people looking for the pot of gold at the foot of the rainbow.

The meaningful problem is not to write any uncomputable number, but to write a specific one,  identified by a specific property. Consider for example the binary real $h\in[0.0, 1.0[$ defined as follows: its $n^{th}$
digit is $1$ iff the Turing Machine with Gödel number $n$ halts on empty
input, and $0$ otherwise. This number is very precisely defined. But
if it were computable, we would have a way to decide the halting
problem. Hence, there is no algorithm, no program, that can enumerate the bits of
the real number $h$, and thus there is no way to print it.  And using random generators will not help.

Of course, it could be that some random generator, controlled by a
random physical process such as radioactive decay would produce
precisely that number (with a probability closing to zero as time
passes). But, at best:

1- you would have at any time only a rational number which is a prefix
    of the non-computable real you are interested in

2- you would most likely be unable to check wether your prefix is
    really correct

3- you would have no garantee that the next digit will still be correct.

But, even then, you must assume that the random generator uses some
physical "true" randomness source. Even randomly created, or
computing with whatever technique known or yet to be invented, no computer program can
print an uncomputable real number, such as the number $h$ defined above.  That
is a result of computability theory that no such program can exist.

Your only hope is that computability theory does not apply to
radioactive decay or some other such physical phenomena. But I know of no proof
either way. And it would not really help you in any meaningful way, because the probability of success is zero, and because you would have no way of knowing you are succeeding. Note that I cannot say "of knowing you have succeeded", because you never reach the end of that infinite process, so that any proof would have to be an on-going continuous process, which cannot be finitely defined for essentially the same reason a printing program cannot exist for an uncomputable number.


Why is the addition function exponential for k-bit integers providing only zero, equality and the successor functions?

The complexity of getting "the result of a + b" would indeed "be O(b) starting from a".

However, b is a log(b)-bit integer, and O(b) = O(2^(log(b))).


Recursive descent parser with backtracking for the grammar $S \rightarrow aSa\ |\ aa$

This is not much of an answer, but the parse trees do not fit the
normal comments.

Your grammar $S \rightarrow aSa\ |\ aa$ should parse the string
$aaaaaa$.

But the parse tree has the following form:

      S
     /|\
    / S \
   / /|\ \
  / / S \ \
 / / / \ \ \
a a a   a a a

or if you prefer this presentation, with the terminals on different
lines

     S
   / | \
  a  S  a
   / | \
  a  S  a
    / \
   a   a

I checked that the ABNF parser generator does not seem to work, but I
do not know how to trace what it does.

It indeed seems to recongnize the set  $\{a^{2^n}\ |\ n \ge 1 \}$ wich
is not what the grammar defines.

It is a bit surprising to have such an elaborate site around a buggy parser,
which furthermore uses a totally uninteresting parsing technique.

After a further look at it:

I think I found one source of the problem. The square brackets mean
optional.

So your grammar should be written either
S = "a" S "a" / "aa"
or S = "a" [S] "a". Then it seems to work correctly.

But the system is apparently lost when having twice the same rule in
different forms. I am not sure why.

I did not find a page explaining these syntactic issues for specifying
the grammar.

I still consider that buggy.


Prove that $\text{EF p}$ can't be written in LTL

There is a delicate point here, about the semantics of LTL vs CTL.

Given a formula $\psi$ in LTL, we say that it holds in a structure $K$ if every path in $K$ satisfies $\psi$.

In CTL, however, the path quantifiers are built in to the formula.

To make this more precise, you can think of LTL as the fragment of CTL* of the form $A\psi$, where $\psi$ doesn't contain any path quantifiers (i.e., it's in LTL).

Now, you suggest negating your formula, so you obtain $AG\neg p$. This formula is not an LTL formula, due to the quantifier $A$. But it does have an LTL equivalent, namely $G\neg p$.

However, if you try to negate back to CTL, the negation of the LTL formula is now $Fp$, but the semantic of LTL means that it is interpreted as $AFp$, whereas you wanted $EFp$.

To sum up, you just cannot express the path quantifier $E$ in LTL.

To prove that the formula $EFp$ does not have an LTL equivalent, consider (towards a contradiction) some equivalent LTL formula $\psi$, and take a structure that has two "branches" -- one with $p$ and one without (e.g., two states with self loops).
Since this structure satisfies the $EFp$, then it also satisfies $\psi$, meaning that every computation in it satisfies $\psi$. But now, if you remove one of the branches (the one with $p$), then $\psi$ is still satisfied (since you only removed computations). However, $EFp$ is not satisfies, so $\psi$ is not its equivalent.


Intuitive explanation of neutral / normal form in lambda calculus

I can reassure you that this property is not immediately self-evident. In trying to describe/enumerate the set of normal forms, the main observation required is the following:

Abstraction preserves normal forms: if $t$ is normal, than so is $\lambda x.t$.
Application does not preserve normal forms: if $t$ and $u$ are normal, $t\ u$ may contain a redex!

We want to characterize the normal forms for which we can not create redexes when performing applications. Obviously, this occurs iff $t$ is a $\lambda$-abstraction. In particular, we can take $u$ to be anything we want, so long as it is in normal form.

For $t$, we need either a variable or an application, itself already in normal form. This allows a convenient recursive definition for $t$, which we will call neutral:
$$t=x$$
or
$$t=t_1\ t_2$$
with $t_2$ any normal form, and $t_1\ t_2$ also in normal form, i.e. $t_1$ also a neutral term.

But this is exactly your definition of Neutral!

One can carry out this process further to characterize exactly the normalizing (resp. strongly normalizing) terms, if we furthermore allow weak head expansions.


maximal independent set on grid graph proof

As we define v′ if it is in T and is in S

I think you're misinterpreting the definition of $v$:

For each $v \in T$, define $v'=v$ if $v\in S$ or as its neighbor in $S$ otherwise

$v'$ is always defined; it's just a question of what it's defined to be. The above definition means that, if $v \in S$, $v'$ is defined to be $v$, and if $v \notin S$, $v'$ is defined to be $v$'s greater-or-equal-weight neighbour in $S$ (the existence of which was established in part 1a). Then $w(v) \le w(v')$ for each $v \in T$ by construction.
(This is the only way I see to parse the definition that makes grammatical sense, though I think it could be worded better, to prevent people reading "define $v'=v$ if $v\in S$" as a "parenthesised unit".)


Polymorphism restriction on lambda-bound variables in HM

Yes, you are restricting it too much. The second code is perfectly fine.

For the record, Haskell has no issue with your code:

> let myid = (\x->x)(\x->x) in (myid 'a', myid True)
('a',True)

and Ocaml as well works fine, after eta-expansion:

let myid y = (fun x -> x)(fun x -> x) y in (myid 'a', myid true);;
- : char * bool = ('a', true)

Eta expansion is needed in Ocaml, I think, because of the value restriction, where a binding is not generalized unless it is a function (let f x = ... instead of let f = ...). This restriction was needed to avoid some soundness issues with mutable variables -- remember Ocaml is not a "pure" language, and allows side effects everywhere.

Anyway, Hindley-Milner should generalize let f = (\x->x)(\y->y) in ... just fine. First, \y->y is given the monotype $\alpha\to\alpha$, where $\alpha$ is a fresh type variable. Then \x->x is given $\beta\to\beta$, with a fresh $\beta$. Then we type check the application, which succeeds and unifies $\beta = (\alpha\to\alpha)$. The resulting type for the application is $\alpha\to\alpha$. Since $\alpha$ is not present in the environment, it can be generalized so the we get
$f : \forall \alpha.\, \alpha\to\alpha$.

Bonus exercise: type check the following

# let myid y = (fun x -> x)(fun x -> x) y ;;
val myid : 'a -> 'a = <fun>
# myid myid myid true;;
- : bool = true


Approximation algorithms for NP-complete problems

It depends on the problems. Some NP-complete problems are in APX (can be approximated to some constant amount) and some are not. This shows that you cannot in general assume the existence of a transformation such as the one you mention; this is spelled out here.

A concept somewhat similar to what you mention is APX-hardness. First, some definitions. APX, as mentioned, is the class of problems approximable to some constant in polytime. PTAS is the class of problems which can be approximated arbitrarily well in polytime. A problem is APX-hard if there is a "PTAS reduction" (approximation-preserving reduction) from every problem in APX to that problem. One problem which is APX-hard is MAX-SAT.

A related definition is MaxSNP. This is a class of graph problems with the following property: there is a PTAS reduction from every problem in APX to some problem in MaxSNP.


the maximum value for which combination of merge sort and insertion sort works more efficiently than standard merge sort?

Don't forget that big O notation hides constants. We want $nk + n\log(n/k)$ to be at most $Cn\log n$ for some constant $C>0$. This means that $k + \log(n/k) \leq C \log n$, and so $k - \log k \leq (C-1)\log n$. You can check that this inequality holds (for some $C>0$) if and only if $k = O(\log n)$.


Multi objective optimization using genetic algorithm

Just define profit as a variable and maximize porfit as your singular objective. In general the objective will depent on multiple variables indirectly and the variables will usually also depend on each other. If this is not the case there are probably much more effective solutions than genetic algorithms.


Solving recurrences using substitution method

The complexity in your proof is that you have addition in you logarithm, and you need that complexity to go away. So lets get rid of that 34, by just making $n \ge 34$, so now

$$\log\left( \frac{n + 34}{2} \right) \le \log\left( \frac{n + n}{2} \right) = \log(n).$$

I am not sure why the book chose 68, but really its the same argument. If $n \ge 68$, then $n/2 \ge 34$. Thus

$$\log\left( \frac{n + 34}{2} \right) \le \log\left( \frac{n + n/2}{2} \right) = \log\left( \frac{2n + n}{4} \right) = \log\left(\frac{3n}{4}\right) = \log(n) + \log(3/4).$$


Prove, that $A^+\subseteq A^*$ where $A$ is a formal language

It seems you have hit the reasoning correctly:
A set $S$ is a subset of another set $A$ if $w\in S\implies w\in A$.
Since you are trying to show that $\forall w \in A^+ \implies w \in A^*$, you are proving that $ A^+ \subseteq A^*$.

One more legant way to formally do this is by finding a bijection between the two sets.
Since $|A^*|$ = $|\Bbb N|$ you need to prove that $|A^+|$ is a subset of  $|\Bbb N|$. So you need to find a Bijection (left to you since we dont do Homework for the OP's) from these two sets.
Note that there exists $2^{\aleph_0}$ such functions, so
 you have a large selection space :)


Understanding the binary and hexadecimal representations of UTF-8

Where the 21 bits come from: The idea of unicode is based on the Universal Coded Character Sets (short UCS). It's a concept for a 31bit character set ordered as a 4D hypercube where the first three dimensions use 8bit and the fourth uses 7bit. Per row there are $2^8$ characters. Per plane there are $2^8$ rows $=65.536$ characters. Per cube there are $2^8$ planes and there are $2^7$ cubes. Unicode decided to just use a mere 17 planes (the code space 0 - 10FFFF), which corresponds to the 21bits.

UTF-8 is a variable length encoding mostly used for encoding unicode. Variable length means that it uses 1 to 4 byte to represent a certain code point, depending on its number of significant bits.

The scheme looks as following:

1 byte: At most 7 significant bits. From U+0000 to U+007F.
Scheme: 0xxxxxxx.

2 bytes: At most 11 significant bits. From U+0080 to U+07FF.
Scheme: 110xxxxx 10xxxxxx

3 bytes: At most 16 significant bits. From U+0800 to U+FFFF.
Scheme: 1110xxxx 10xxxxxx 10xxxxxx

4 bytes: At most 21 significant bits. From U+10000 to U+10FFFF.
Scheme: 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx

In your example you have 12 significant bits and therefore the 3 bytes used for encoding.

For further details see https://en.wikipedia.org/wiki/UTF-8.


"The devil is in the details". Algorithms and programming, fortunately and unfortunately, needs the greatest attention to detail.
The part of code that are critical here are the following three groups of the code interleaved with comments. The first two lines of code is how to do the recursion. The middle one line of code is how to choose the pivot. The last two lines of code is how to determine the index that will be used by that first two lines of code to split the part of array between lo and hi.
#
# code skipped here
#
        quick_sort_hoare(A, lo, p)
        quick_sort_hoare(A, p + 1, hi)
#
# code skipped here
#
    pivot = A[lo]
#
# code skipped here
#
        if i >= j:
            return j

The above version, as in OP's post and as in Wikipedia, is correct.
However, as mentioned by OP, the above version with its middle line of code changed to pivot = A[hi] will run into an infinite loop if given an array of more than one element whose unique largest element is its last element. A simple example of such an array is $[0,1]$ or $[1,0,2]$.
When the Wikipedia page says "there are many variants of this algorithm, for example, selecting pivot from A[hi] instead of A[lo]", it means the following variant. On first look, nobody would expect this change of pivot would require code at two other places be changed. However, it is natural from the point of symmetry. The above version is NOT symmetric with respect to lo and hi. In fact, since only one splitting index is returned when two indices iand j crosses, there is no way to be symmetric! The only way to restore symmetry is creating a mirroring variant like below.
#
# code skipped here
#
        quick_sort_hoare(A, lo, p - 1)
        quick_sort_hoare(A, p, hi)
#
# code skipped here
#
    pivot = A[hi]
#
# code skipped here
#
        if i >= j:
            return i

The posted code as in problem 7.1 of CLRS's Introduction To Algorithms, third edition is correct, too, since it is the same as your code and the code in Wikipedia. In particular, it works correctly on their example, $[13, 19, 9, 5, 12, 8, 7, 4, 11, 2, 6, 21]$. I suspect that you missed the part e of that problem, "Rewrite the QUICKSORT procedure to use HOARE-PARTITION". The expected result of the rewrite will be a procedure that is just like your Python function quick_sort_hoare . In fact, that problem is written in great detail in order to prove its correctness. I would like to encourage you to go over that problem closely.


Difference between $\beta$-contracts and $\beta$-reduces in Hindley

Notation and terminology varies a little between authors, so you should check the definitions used by the author. When you ask such questions, you should quote the definitions.

The expression “$P$ $\beta$-contracts to $P'$” means that $P$ contains a subterm which is an application and $P'$ is the result of substituting the argument into the abstraction body. That is, there exist $C$, $M$, $N$ and $x$ such that $P = C[(\lambda x.M) \, N]$ and $P' = C[[N/x] M]$ where $[N/x] M$ means the term obtained by substituting $N$ for $x$ in $M$ and $C[\cdot]$ is a term with a hole. Thus

All terms of the form $(\lambda x.M) \, N \triangleright_{1,\beta} [N/x] M$ are $\beta$-contractions at the top of the term.
If $P \triangleright_{1,\beta} P'$ then $M \, P \triangleright_{1,\beta} M \, P'$ and $P \, M \triangleright_{1,\beta} P' \, M$ and $\lambda x. P \triangleright_{1,\beta} \lambda x. P'$. The contraction is sometimes said to happen “in a context”.

The expression “$P$ $\beta$-reduces to $P'$” means that there is a chain of $\beta$-contractions that goes from $P$ to $P'$. For example:

For any term, $P \triangleright_{\beta} P$ (a term reduces to itself in zero steps).
If $P \triangleright_{1,\beta} P'$ then $P \triangleright_{\beta} P'$: a contraction is a reduction in one step.
If $P \triangleright_{1,\beta} P'$ and $P \triangleright_{1,\beta} P'$ then $P' \triangleright_{\beta} P''$: a contraction in two steps.
etc.

In a nutshell, a beta contraction is one step, a beta reduction is any number of steps. Note that some authors use different terminology and might call one step a beta reduction and many steps “a chain of beta reductions” or “a $\beta^*$ reduction”.


Given graph G and vertices v and w can you non-deterministically walk the "least Hamiltonian path" from v to w, if it exists?

No.  There has to be a way to verify that your choices led to a correct choice, in polynomial time (with an ordinary deterministic computer).  Given a particular Hamiltonian path, there's no way to verify it is the least Hamiltonian path (in polynomial time).
The "space alien" stuff is just intuition, but if you want to know what it means in a precise way, you need to go to the formal mathematical definition.  My favorite definition of NP is the verifier-based definition.  With that definition, there is no obvious way to pick a short certificate that a polynomial-time (deterministic) algorithm can use to verify that a proposed solution to the problem is correct.


Linear Search Algorithm - Why allow a user to input a start and end index to LS?

Surely, it is not about correctness. It is only a slightly general version of linear search. This technique is not uncommon. Obviously the more general the procedure is, the more applicable it is.

Linear search is a little bit simple for an illustration. Let's look at quicksort@wiki that is declared as quicksort(A, lo, hi). This is because quicksort is a recursive procedure that needs to call itself over a sub-range of the array. Notice that quicksort also needs a partition procedure, which is declared as partition(A, lo, hi) instead of partition(A).

Another kind of examples is dynamic programming. Suppose that you want to compute the edit distance@wiki between two strings of $a$ and $b$, with lengths $m$ and $n$ respectively. What you are actually computing is $\text{Dist}(i,j)$ for $0 \le i \le m, 0 \le j \le n$.


Why register access bandwidth is higher then residing inside CPU cache?

There are slower and faster technologies for memory. And there are technologies for creating bigger or smaller amounts of memory. Obviously a technology that creates slower and smaller memory is useless. So of the useful technologies, the fastest one will always provide the smallest amount of memory, and the ones providing the biggest amount of memory will be the smallest.

Register memory is smaller than cache, therefore it's faster. It has nothing to do with technology, it is a basic economic principle. If the technology used for cache was faster, it would be used for registers.


A hash function is used to map a set of keys to a subrange of the integers (it is used as an index into an array, in the end). So it must be (assuming zero based arrays, as in  C), $h \colon \mathcal{U} \to [0, m - 1]$ if $\mathcal{U}$ is the universe of keys.


How to calculate the runtime of a following code?

If I understand correctly, that you denote $n$=list.length and are calculating amount of   "list[i] +=" operation. Then of course, as it is triple loop, then for $n$ times  fixed "i" from first loop you take $n$ times "j" from second loop and $n$ times "k" from most inner, third, loop. So operation "list[i] +=" will be fulfilled exactly $n^3$ times. Now knowing, that $n^3 \in O(n^3)$ you can state that complexity for whole snippet is $O(n^3)$ .


which neural network is good for predecting the value of strings

Assuming the strings are variable-length, a recurrent neural network would be a reasonable choice: either a LSTM or a convolutional network.


If a problem is in P solved via dynamic programming, is it also in NP?

Any problem in P is also in NP

A decision problem that's in P is also in NP, because you can give the verification logic like this: for yes instance x, use empty string as a certificate, and solve x in polynomial time. You get the result that it's yes instance (that's by definition of P) and that means verification is done in polynomial time.

Note that, the order written as $n^2 k^2$ doesn't simply mean the problem is in P (Check "Pseudo-polynomial time" in wikipedia.) For example, Knapsack problem can be solved by the dynamic programming and its order is $O(n W)$ where $n$ is the number of products and $W$ is the maximum weight for the knapsack. But $W$ is actually considered exponential of the input size and Knapsack problem is known to be NP-complete.


I got it on further thought. It is trivial. $\Sigma^* - P$ is $P'$, the complement of P and this is regular. I was unnecessarily concentrating on how $Q \subseteq P$ would play a role. It doesn't actually.


Turing Machines: decidability and bounds checking

I can construct a machine $D$ which on input $\langle M,w\rangle$ tells if $M$ moves its head past the right end on input $w$, $D$ accepts if the head does not move past the right end of input, and rejects otherwise. As configurations of length $|w|$ are finite if $M$ ever enters same configuration of length $ \le |w|$ accept. Or if it does not repeat such configuration at some point $M$'s head will move past $|w|$ tape cells. So yes your problem is decidable.


Number of instances of SAT (boolean satisfiability) problems of size N?

If you consider 3-Conjunctive Normal Form (3CNF) (every clause has exactly three literals) and you allow clauses with repeated variables, then it is easy to see that using $N$ variables the number of different 3SAT clauses is $(2N)^3$
($2N$ because every literal can appear unnegated or negated).

So the total number of distinct 3CNF formulas (without repeated clauses) is $2^{(2N)^3}$.

But be careful because the "size" of a 3CNF formula (e.g. considered as an input of a decision problem) is usually the size of its representation. For example, using alphabet $\Sigma = \{0,...,9,``,",-\}$
the 3CNF formula $(x_1\lor\bar{x}_2\lor x_3)\land (\lor x_2 \lor \bar{x}_3 \lor \bar{x}_4)$ can be represented with the string:

1,-2,3,2,-3,-4

and its length is 14.


Determine the worst-case complexity that allow you to conclude that a given array with n elements is not sorted

The minimum number of comparisons to tell whether an $n$-element array is sorted is indeed $n - 1$.
However, we don't have to sort the array to arrive to a conclusion.

Here is how to check an array $a$ in $n - 1$ comparisons.
Compare $a_0$ to $a_1$, compare $a_1$ to $a_2$, ..., compare $a_{n-2}$ to $a_{n-1}$.
If all comparisons result in "less or equal" outcome, the array is sorted.
If any comparison results in "greater" outcome, the array is not sorted.
Here, "sorted" means "the elements follow in non-decreasing order from left to right".

The harder thing is to prove that less comparisons won't be enough.
Sure, if we just followed the above checks but dropped the last one, we won't know whether $a_{n-2} \le a_{n-1}$ holds, so the array is sorted if it does but is not sorted if it doesn't.
But what if we compared some other $n - 2$ pairs?

One way to prove it is to establish and maintain some global characteristic of our knowledge about comparison results.
Namely, consider a graph where vertices are array indices: $0$, $1$, $2$, $\ldots$, $n-1$.
The edges of the graph will be the comparisons we make.

As we add our edges, let us track such global characteristic: the number of connected components in the graph.
Initially, it is $n$, same as the number of vertices.
Each edge either lies inside some component, or connects two different components, so the number of components drops by at most $1$ with each edge added.

In the end, after $n - 2$ edges, we will have at least $2$ connected components.
Let all comparisons for vertices $i < j$ so far result in $a_i \le a_j$, so that the result is still unknown.
Consider any vertex $u$ from one of them and any vertex $v$ from another, such that $u < v$.
If $a_u < a_v$, our array may still be sorted.
If $a_u > a_v$, it is not sorted.

Either of the above does not contradict any prior information about the array, so both are possible, which concludes our proof.
If that's unconvincing, we can construct the example arrays.
For the first case, simply let $a_i = i$, which is clearly a sorted array.
For the second case, let $a_i = i$ for all elements of the $v$'s connected component, and let $a_i = i + n$ for all other indices.
We can check that both arrays are consistent with our $n - 2$ comparisons, and for two vertices $u < v$, $a_u < a_v$ in the first case and $a_u > a_v$ in the second case.


How many 3-SAT expressions with up to N variables are satisfiable?

There is almost certainly no non-trivial formula that will tell you the number of solutions. By non-trivial, I mean something not of the form
$$
\sum_{x_1, \dots, x_n\in\{0,1\}} f(x_1, \dots, x_n)\,,
$$
where
$$f(x_1, \dots, x_n)=\begin{cases}1 &\text{if $x_1, \dots, x_n$ satisfies the formula}\\
0&\text{otherwise.}\end{cases}
$$

Note that if we have a formula $F$ (trivial or otherwise) that tells us how many satisfying assignments there are, we can decide 3-SAT just by computing $F$ and checking whether $F=0$ (unsatisfiable) or $F>0$ (satisfiable). This means that computing $F$ is NP-hard so, assuming that P$\,\neq\,$NP, $F$ is difficult to compute, which suggests that $F$ can't have any nice form.

In fact, $F$ is complete for the complexity class #P, which is essentially at least as hard as all of the polynomial hierarchy. This means that it seems to be quite a lot harder than "just NP-hard". Furthermore, we can't even approximately compute $F$ in any efficient way unless P=NP. Even being able to approximate $F$ with exponential additive error would allow us to distinguish between $F=0$ and $F>0$ and thus allow us to solve 3-SAT. For example, given a formula with $N$ variables and $F$ solutions, we can create a formula with $2N$ variables and exactly the same clauses (so variables $N+1, \dots, 2N$ aren't mentioned in the formula and can take any value). This formula has $2^NF$ satisfying assignments and being able to approximate that number strictly better than $\pm 2^{N-1}$ would allow us to tell the difference between $F=0$ and $F>0$.


At a hardware level, virtual memory means, essentially, a mapping from a virtual address space to a physical address space, the data structures and instructions to maintain them, and a facility to trap to the operating system if a mapping is not valid. This mapping is at the page level: a page maps to a page frame.

At the operating system level, we usually conceptualise a virtual address space as a collection of segments. A segment could represent part of a file which resides on secondary storage (e.g. disk). This could be program text, or a memory-mapped file. Or it could represent anonymous memory, that is, memory which is allocated by a process and may be swapped to secondary storage if not needed. Anonymous segments are often zero-fill, which isn't backed by physical memory until it is first used. Or it could represent a memory-mapped I/O area, or an operating system device, or an operating system data structure (e.g. the "u area" in Unix).

Segments can be shared between address spaces (e.g. after the Unix fork system call). They can be copy-on-write. And so on and so forth.

There are enough "things" that can be mapped which aren't really "memory" that you can't really say that virtual address space is only as useful as the amount of physical stuff that can be mapped to it.

One more thing: Another advantage of a large virtual address space is reduced external fragmentation. You see, the segments that comprise a virtual address space need to be allocated and deallocated just like anything else, and you can't really move them within the address space. So having a large virtual address makes it easier to allocate within it.


Why doesn't diagonalization require taking a limit?

Some diagonalization arguments might require limits to be able to nail down all the details (e.g. if they involve an infinite sum, or an infinite decimal expansion, which is formally just an infinite convergent sum of a certain kind), but they do not require limits in general.
The most popular diagonalization argument proves that $|\mathbb{N}| \neq |\mathbb{R}|$. Depending on how you've seen this, resolving some of the details might end up requiring limits because of the nature of $\mathbb{R}$. So let's look at a decidely discrete example of diagonalization instead:
Theorem $|\mathbb{N}| \neq |\{0, 1\}^\mathbb{N}|$
We take $\{0, 1\}^\mathbb{N}$ to be the set of all infinite sequences of ones and zeros (you can also think of it as the function space $\mathbb{N} \to \{0,1\}$). So for example, we could have the sequences $a = (0, 1, 0, 1, 0, 1, 0, 1, \cdots)$ such that $a_{2i} = 0$ and $a_{2i+1} = 1$.
Since this is a diagonalization argument, we proceed via contradiction. We first assume that it's possible to enumerate all elements of $\{0, 1\}^\mathbb N$ via some function $f$, so that for all $i \geq 0$, $f(i)$ is an infinite sequence of 0s and 1s.
We will construct an explicit infinite sequence which doesn't show up in the image of $f$, which proves that no such $f$ can enumerate all infinite sequences of 0s and 1s, which means that $|\mathbb N| \neq |\{0,1\}^\mathbb N|$ as desired:
$$
a_i \triangleq 1 - f(i)_i
$$
And now we can immediately see by construction that for each $i \geq 0$, $a \neq f(i)$, since if $a = f(i)$ then for all $k$, $a_k = f(i)_k$, but in particular for $k = i$ we have $a_i = 1 - f(i)_i \neq f(i)_i$. $\blacksquare$

This construction clearly doesn't involve any limits - all of the objects are discrete. The equivalent complete proof specifically for $\mathbb R$ might involve a limit or an (easy and automatic) proof of convergence for the construction of the real number $a$, but there's nothing particularly insightful about that step.