Logarithmic guarantees for randomized search trees

Let's consider a different example: a hash table. While usually the hash function is fixed in advance, it is also possible for it to be chosen randomly when the hash table is initialized.

If we want to mount a Denial of Service attack on a hash table, we need to feed it many keys that hash to the same value. If the hash function is weak and known, then we can easily do it. If the hash function is weak and unknown, then it could be difficult or even impossible.

When the authors say that the priorities are kept hidden from the user, they mean that the randomness used in the data structure is not "public". In our hash table example, it means that the user of the hash table doesn't know which hash function was chosen. If the user knew the hash function then she could mount a DoS attack. If she doesn't, then such an attack becomes much more difficult.

In practice we don't necessarily think of the user as malicious; however, we want a guarantee on the running time which is independent of how the data structure is used. Suppose that we use a treap or a randomized BST in some algorithm, in a very specific way. If the algorithm has access to the randomness—for example, if it is fixed—then perhaps its specific access pattern results in bad performance. However, if the algorithm acts independently of the randomness, then bad performance only happens with small probability.


Remember what $O(\cdot)$ means. You don't need to do anything. Mergesort has a running time of $O(n\log n)$ which is already $O(n^2 \log n)$, $O(2^n)$ and $O(\text{any larger function you want})$.


What is the space complexity of function $f(x) = \sum_{i=1}^x g(i)$ where g(n) is O(n)?

Space complexity is about the maximum stack size, so this function uses $O(n)=O(\log(x))$ space. Your intuition about this is right: each call to $g$ uses and overwrites memory previously used by the previous call to $g$, so the stack grows to $O(n)$

Why the $\log(x)$ factor? If $g$ uses $O(n)$ memory for an $n$-bit input, then it uses $O(n)=O(|x|) = O(\log(x))$ memory for input $x$, which is of length $|x|=\log(x)$.


Subset sum algorithms, their time complexity

Your algorithm is very similar to exhaustive search. It is basically the following approach:

  In order to check whether some subset of $S$ sums to $n$, go over all $i \in S$ and check whether some subset of $S \setminus i$ sums to $n - i$.

The actual algorithm uses memoization and a few other optimizations. Its complexity is exponential in the size of $S$ (probably roughly $2^{|S|}$ in the worst case).


Generate random point inside a polyhedron

If you polytope is convex, this answer should work. Otherwise you can always do rejection sampling: Sample a point from the bounding box, check whether it's inside the polygon. That gets really slow for high dimensions and "unboxy" polytopes though, because the bounding box potentially has a huge volume compared to the region you're interested in.


Well, as the problem asks you to make a truth table, you should first make one (this is generally a good idea even if not asked explicitly). For your question, you can say assign two bits to input1, say $a$ and $b$, and two bits to the input2, say $x$ and $y$. Then you might say that if $a = 1$ and $b = 0$, input 1 is $2$.

Once you have the truth table (4 inputs, one output), you can get the corresponding boolean expression from the truth table in "sum-of-products" form. Basically, suppose for every entry where the output is 1, you form a "min-term" of the inputs. For example, say for 2 inputs $p$ and $q$, if output is $1$ when $p=1$ and $q = 0$, the min-term would be $p\bar{q}$. Get these min-terms for all inputs where the output is 1, and add them/OR-them together. This is because the output is 1 if and only if any one min-terms is true. You can read more here or here or here.

Now, once you have the boolean expression, you might want to minimize it - implement the logic using fewer gates. This is not asked in your question, but you might want to do it anyways. Karnaugh map technique, which you seem to already have read, is one technique. There is another called the Quine-McCluskey algorithm.

Once you have the boolean expression, you can generate the corresponding circuit mechanically. So, for each min-term, implement it using AND gates, and NOT gates. Connect all these to the input of a OR gate. For example, for something like $p\bar{q} + \bar{p}q$, $p\bar{q}$ means $p$ AND (NOT $q$). Do the same for the other min-term, and give them to the input of an OR gate. The above links also provide information and examples about this.

As for speed, you'll get faster with practice!


(Formal) Proofs of Node Centrality Properties

There are many papers dealing with the algorithmic aspects of these measures, with formal proofs, complexity analysis, and so on. However, I understand that this is not really what you are looking for.
There are only few formal works on their actual relevance for describing features of interest in practice.
Pagerank is a notable exception, though. Its connections to random walks, Markov chains, and matrices, as well as its wide use and mere features, make it a great metric for formal analysis. I particularly recommend the book Google's PageRank and Beyond: The Science of Search Engine Rankings, by
Amy N. Langville and Carl D. Meyer. It deals with many aspects, putting together practical concerns as well as theoretical analysis.
Node degree distribution is another important exception, although one may consider it too basic to be a valid answer here. Still, there are many formal works showing the importance of high degree nodes in random graphs that model real-world complex networks. See for instance our survey entitled Impact of random failures and attacks on Poisson and power-law random networks.


Increasing the weights of all edges in an undirected graph makes a minimum cut still minimum

Consider the following graph. The min-cut is $[s][a,b,c,d,t]$ with value 3. After the weights of all edges are increased by 1, the min-cut becomes $[s,a,b,c,d][t]$ with value 5.

It does not matter whether you are considering cuts with terminals or without terminals (if with terminals, the terminals are $s$ and $t$).


Variable Length Encoding of Integers Using a Modulus Algorithm

The first step is counting the number of strings of length $n$ in which no non-empty prefix is divisible by $3$. Surprisingly enough, these are given by Fibonacci numbers $F_n$ for $n > 0$ (exercise). I will show how to map the natural numbers to strings of these forms, from which your encoding will follow. Divide the natural numbers into parts of lengths $1,F_1,F_2,F_3,\ldots$. Using the formula $F_1+\cdots+F_n = F_{n+2}-1$, we see that numbers $m$ in the range $F_{n+1} \leq m < F_{n+2}$ will be encoded using strings of length $n$; additionally, $0$ will be encoded by the empty string. Given $m$, it should be straightforward to find $n$, for example using the Fibonacci recurrence or the approximate formula $F_n \approx \frac{1}{\sqrt{5}} \left(\frac{1+\sqrt{5}}{2}\right)^n$.

Suppose $m > 0$, and let $x = m - F_{n+1}$, so that $0 \leq x < F_n$. It remains to encode $x$ as a string of length $n$ in which no non-empty prefix is divisible by $3$. The idea is to interpret the recurrence $F_n = F_{n-1} + F_{n-2}$ accordingly. There are many ways of doing it, here is one. There are $F_{n-1}$ legal strings of the form $0s$, and $F_{n-2}$ legal strings of the form $1\alpha s$, where $\alpha$ is determined so neither $\alpha s$ nor $1\alpha s$ are divisible by $3$. We can encode the first $F_{n-1}$ values of $x$ using strings of the form $0s$, and the latter $F_{n-2}$ values of $x$ using strings of the form $1\alpha s$. To determine $s$ itself, we run this procedure recursively. The base case is the unique string of length $1$, namely $1$.

To illustrate the entire procedure, let us show how to encode $m = 7$. First we find that $F_5 = 5 \leq 7 < F_6 = 8$, and so $n = 4$ and $x = 7 - 5 = 2$. We write $F_4 = F_3 + F_2 = 2 + 1$, so that the encoded string is of the form $s_4 = 1\alpha_4 s_2$. The string $s_2$ itself is the encoding of $x - F_3 = 0$ of length $2$. Writing $F_3 = F_2 + F_1 = 1 + 1$, we see that $s_2$ has the form $s_2 = 0s_1$. The string $s_1$ itself is the encoding of $0$ of length $1$, which is $s_1 = 1$. Therefore $s_4 = 1\alpha_4 s_2 = 1\alpha_4 0s_1 = 1\alpha_4 01$. If $\alpha_4 = 0$ then $1001$ would be divisible by $3$, so $\alpha_4 = 1$ and the output is $1101$.


If two vertices point to one another in a directed graph, is the graph then considered cyclic?

Yes the graph is cyclic. It does not matter how many vertices are there. If a cycle can be formed then the graph is cyclic. You can even form a cyclic graph with one node. This cycle would be called a self loop.


"Business process" can also be applied.  Or you could call it "automated process" or "automated business process" or "software processing" or "service" or any of a number of other things.

In other words: these terms do not have a precise mathematical/technical definition.  So, define your terms, and use them consistently.  This is not a technical question (and this site is better-suited for technical questions, not terminology questions).


Find a schedule with lowest total penalty

This problem is called "minimization of total weighted flow time". It is very hard, especially when jobs cannot be preempted by the processor. Even when jobs can be preempted, it is NP-hard, so you cannot expect to have algorithms that construct optimal solutions efficiently.

If you are willing to accept non-optimal solutions, then there are efficient heuristics that find a solution of cost equal to $C$ times the optimal cost, for some large constant $C$, but they are not very practical (see the first link). A more practical approach might be to resort to a local search heuristic.


Regular expression for a language which doesn't look regular

The trick is to write $L$ as a different language. Let's consider the following similar language
$$ L' = \{ xy \in \{0,1\}^* : \#_0(x) = \#_1(y) \}, $$
where $\#_0(x)$ is the number of 0's in $x$.

I claim that $L' = (0+1)^*$. Indeed, let $w = w_1\ldots w_n$ be some arbitrary word, and define $\delta_w(i) = \#_0(w_1\ldots w_i) - \#_1(w_{i+1}\ldots w_n)$. The following properties are not hard to check:

$\delta_w(0) \leq 0$.
$\delta_w(n) \geq 0$.
$\delta_w(i+1) = \delta_w(i) + 1$ for $0 \leq i \leq n-1$.

This shows that $\delta_w(i) = 0$ for some $0 \leq i \leq n$, and so $w \in L'$.

Your case is very similar - I'll leave you to figure out the details.


I'm trying to understand why every language has an infinite number of TMs that accept it

The correct version of the claim states that every computable language is accepted by infinitely many Turing machines.
Indeed, if $L$ is computable, then there is a Turing machine $T$ that accepts it. Let $T_n$ be $T$ together with $n$ unreachable states. Then $T_n$ also accepts $L$, and the machines $T_n$ are all different from one another.


Synchronizing sequence and Synchronizable DFA

I think you are on the right track:

Consider two states $q_1,q_2$. We claim the following:

If there exists a word $w$ such that $\delta(q_1,w)=\delta(q_2,w)$, then there is such a word $w$ of length at most $k^2$.

The proof of this a standard shrinking argument: if such a word is longer than $k^2$, then during the runs from $q_1,q_2$, a pair of states repeats, and we can shrink $w$.

Now, since you assume the existence of a synchronizing word for all states, you can proceed to construct a word that synchronizes all the states, pair by pair.


Solve the recurrence $f(n+1)=f(n)^2,\, f(0)=2$

Hint, Consider the function $g(n) = \log_2 f(n)$


Optimal dividing of K people into N groups

Solution in pseudocode:

initialize collection of persons (e.g. an array):
    - each person itself is described by its position in collection
    - each person itself contains collection of positions (e.g. an array)
      that describe wished persons for the person to be grouped with
(example: persons = [[1,2], [0,2], [0,3], [0,2]])

initialize empty collection of groups (e.g. an array):
    - each group itself is described by its position in collection
    - each group itself contains collection of positions (e.g. an array)
      that describe grouped persons

initialize number of persons per group (example: 2)
initialize total group count to be number of persons divided by number of persons per group (example: 2)
initialize constraint c1 as: any group shouldn't exceed the number of persons per group
initialize constraint c2 as: group count shouldn't exceed the number of total group count
initialize constraint c3 as minimum required of wishes granted per person in any group, for the solution to be valid (example: 1)
[*]initialize dictionary of solutions, where key is a pair (persons, groups), and value is a solution or an empty value

call group(persons, groups)

procedure group(persons, groups):
    [*]if there is a pair (persons, groups) in dictionary of solutions
    [*] return that solution

    for each person (let's call it this-person)
        for each person among this-persons wishes (let's call it wished-person)
            if wished-person is already grouped in any of the groups
                if this-person can be grouped in the same group with wished-person, at the same time satisfying c1
                    set new-groups as groups with this-person grouped accordingly
                    set new-persons as persons without this-person
                else
                    nothing can be done with wished-person, so continue with the next wished-person
            else
                if both this-person and wished-person can be grouped in any group, at the same time satisfying c1 and c2
                    set new-groups as groups with this-person and wished-person grouped accordingly
                    set new-persons as persons without both this-person and wished-person
                else
                    nothing can be done with wished-person, so continue with the next wished-person

            if there are any other persons left in new-persons
                set possible-solution to recursive call, group(new-persons, new-groups)
                if possible-solution is not empty
                    [*]add item to dictionary of solutions, key is the pair (persons, groups), value is possible-solution
                    return it as a solution
            else if all the groups satisfy c3
                return new-groups as the solution

    [*]add item to dictionary of solutions, key is the pair (persons, groups), value is empty
    return empty value

The decision tree will exhaust all the possible paths towards the solution. However, if you use dynamic programming you can improve the performance by avoiding the execution of already known paths. The dynamic-programming part is marked with [*] in pseudocode.

You might further improve the performance by preferring least-popular persons over most popular when grouping.

Here's a Python implementation in case anyone needs it: https://repl.it/@OzrenTkalcec/Dividing-of-K-people-into-N-groups

Disclaimer: I'm not a data scientist, but I like to solve puzzles like this one :)

HTH


Building segment tree without adding extra elements to its size

A segment tree is not required to be full (which is what I believe you mean), however it will always be complete. That is, every level, except possibly the last, is filled.

Take a look at the structure and construction to see that it says nowhere that was must have $2^k - 1$ nodes in the tree. For example we may have $2^{k-1} < c < 2^{k}$ elementary intervals, making our tree non-full, but absolutely complete.

Example, let's say we have intervals:

$$I = \{[1, 5]^A, [2, 3]^B, [2, 8]^C, [4, 6]^D, [4, 10]^E, [5, 9]^F, [7, 8]^G\}$$

We then have the endpoints of the elementary intervals:

$$I' = \{1, 2, 3, 4, 5, 6, 7, 8, 9, 10\}$$

Now we construct a balanced tree with just the end points as leaves:

Next when we insert intervals to get:

This is fine. Adding in the extra elements is usually a convenience. This is mostly a convenience when using an array to implement the tree. For efficiency reasons, using an array is almost always preferable to an actual tree (Node) object because there is much less overhead. Arrays also make it easier/more natural to implement searching/insertion iteratively rather than recursively which decreases another factor of overhead. The sacrifice of adding at most $2x$ as many nodes is generally worth it. Asymptotically there is no difference.

Okay, so using an array is preferable, but why do we need $2^k - 1$ elements? If we have a full binary tree there is almost no edge case handling. Imagine in a recursive procedure we produced a tree like the one above. What would it look like in an array?

I'll show the two different proposals.

Our tree if we filled up the last layer and moved all elementary boundaries to leaves (leaves in red and the gradient shows least to greatest boundary, levels are different colored blue boundaries)

Our tree if we do not fill up the last layer and left leaves as is.

Clearly (1) should look more appealing, but it is also functionally more appealing. There is only one leaf level, so we need no conditional checking if we are at a leaf or not, we just check which iteration into the tree we are at. There are simply more checks to do per iteration and it is not worth it over filling in the final level. So you can do it, but I wouldn't.


Why is it not always possible to compute the centroid of feature vectors?

A metric space consists of a set $X$ of "points" and a metric $d\colon X \times X \to \mathbb{R}_{\geq 0}$ (giving the "distance" between any two points) which satisfies the following constraints:

Symmetry: $d(x,y) = d(y,x)$ for all $x,y \in X$.
Non-triviality: $d(x,y) = 0$ if and only if $x = y$.
Triangle inequality: $d(x,y) \leq d(x,z) + d(z,y)$ for all $x,y,z \in X$.

The definition of centroid doesn't make sense for a general metric space, since you cannot perform arithmetic on the elements of $X$.


Analyzing rules of articles in languages

A language is a result of a complex historical development. If the development were guarded by simple language generating rules it would've been different like some artificial languages such as the Esperanto language.

Many natural languages have nouns split into several categories. These categories are often referred to as the Gender. Though the link between the grammatical gender and the natural or biological gender is not always obvious.

In Slavic languages for instance the gender of a word can be guessed from the flection at the end of the word. E.g. in Russian "облако" (a cloud) is neutral, "-о" is the flection, and "зима" (the Winter) is femenine, "-а" is the flection.

In Old English the category gender did exist but was eliminated during the evolution towards the Modern English. In general all languages that stem from the Latin language inherited some form of grammatical gender (for more details see the discussion in Wikipedia).

When learning the language one has to memorize at least the words and there meaning. In learning languages that keep grammatical gender one has to memorize the gender as well. You can find the gender of a word in any German dictionary.

Look at the small letter f, m, or n, printed in italics next to the word.

E.g.

Bündel, n a bundle;

Bus, m a bus;

Tasse, f a cup;

That is "Das Bündel", and "Der Bus", and "Die Tasse".

When a comprehensive dictionary is available for a language with all the nouns annotated with their respective grammatical gender, I guess there is little space left for machine learning. It is much more easy to keep the complete dictionary in memory than to devise a set of rules that would always be prone to errors.


Where are 'Base & Bounds' registers located?

The values for base and limit must be stored in registers somewhere; it would be highly inefficient to read these from memory on every memory access.

The distinction between "CPU" and "MMU" isn't really an important one on the old Cray vector architectures, and also isn't really important today. This is more about older microprocessors where a "processor" lived on more than one die (e.g. the 68000 architecture which had an external MMU). Today, address translation is closely tied to the rest of the CPU. This actually made the news this week, since Meltdown uses the interaction between the MMU and instruction speculation as a side-channel attack against some Intel CPUs. But I digress.

The diagram is talking about Cray vector computers, so probably the best reference is to look at an old Cray manual.

So here is the Cray Y-MP EL (i.e. the "entry level" model) functional description document, and the description of the exchange mechanism in particular:

  Address Base and Limit Fields

  Four registers in the exchange package define a program's data range
  and instruction range anywhere in memory and allocate specific amounts
  of memory to each range. This memory allocation technique has two
  benefits. First, all programs are relocatable. When a program is
  written, the programmer does not need to know where in memory the
  instruction and data fields will be located. Second, each program can
  have its memory access restricted to certain parts of memory. A
  program can be halted if it tries to run an instruction outside of its
  allowed instruction range or if it tries to read or write data outside
  of its allowed data range. This is especially important where more
  than one program occupies memory at the same time; programs can be
  prevented from executing instructions or operating on data that
  belongs to other programs. The four registers are described in the
  following list.

  The instruction base address (IBA) register holds the
  base address of the user's instruction range. It determines where in
  memory an instruction fetch is made. This is done by adding the
  contents of the P register to the contents of the IBA register. The
  sum equals the absolute memory address for the fetch.
  The limit address (ILA) register holds the upper limit address of the
  user's instruction range. It determines the highest absolute address
  that can be accessed during an instruction fetch sequence. If this
  absolute address exceeds the limit, a program range error flag is set,
  which generates an interrupt.
  The data base address (DBA) register
  holds the base address of the user's data range. It determines where
  in memory a program's data field is located. This is done by adding
  the memory address generated by the instruction to the contents of the
  DBA register. The sum equals the absolute address for any memory read
  or write operation.
  The data limit address (DLA) register holds the
  upper limit address of the user's data range. It determines the
  highest absolute memory address that a program can use for reading or
  writing data. If this absolute address exceeds the limit, the memory
  reference is aborted. The operand range error flag is set, which
  generates an interrupt if the interrupt-on-operand range error bit is
  set.

Altering these registers is typically a privileged operation, in that it is reserved for supervisor-level code rather than user-level code. On Cray machines, these registers were set with an "exchange package", which is more or less the equivalent of a process control block, so it was presumably an operating system routine that set the registers when a task was run.

Now let's take a quick look at a modern architecture.

For Intel x86, this is called memory segmentation. The base and limit registers aren't accessed like normal registers, but are stored in a special data structure called a segment descriptor, which is loaded with the LGDT or LLDT instruction. The difference between the two is that the x86 architecture supports two descriptor tables: "global" and "local". Each process can have its own local table, which is used for features such as thread-local storage.

The situation changed completely with the advent of 64 bit CPUs. In 64-bit mode, segment descriptors are, for the most part, no longer used. There are two segment selectors, FS and GS, which support loading a base field using the model-specific register mechanism, as well as a special instruction called SWAPGS, the details of which are only important for operating system implementors. Note that these selectors have no limit field. Protecting memory from unauthorised access is handled using the paging mechanism, not segmentation limits.

This brings the Intel architecture in line with most other modern CPUs, such as ARM, which do not support memory segmentation.


The RNN construction of the paper is independent of training, because the weights are fixed and no learning occurs. The proof is based on how the encoding of the input output mechanism should be translated into an RNN so that it behaves the same as a Turing machine given the same input. They construct an RNN equivalent to a two-stack push-down automata, which can simulate any Turing machine. They also end up with a Turing complete universal processor net with 1058 units.

Training process is an approximation for a function, thus accuracy is always a parameter to decide on the computation time. Theoretically speaking, for a network with finite number of processors, and with weights and states represented with rational numbers (computable numbers), which is also a translation of a computable function (i.e. not a real random number generator for each sample), it should converge. Thus, the answer is yes.


PERT Chart exercise - is there enough information to solve?

I don't know if there is a standard method to identify which activity matches which arrow, but I was able to complete your PERT chart by examining a few possible cases, while filling the chart from left to right. Each case was accepted or rejected after a while. I found that the higher arrow matches B and the lower C. Note that if you try to match C with the higher arrow, (2,3), E will match with the (3,5) arrow but then you will face the problem that only one activity depends on E while there are two arrows starting from it that have to be filled. Otherwise, if you match (2,3) with B, (3,5) will match with D and then there are two acivities dependent from D as you wish. More uncertainties will raise but they are solvable by considering the different cases.

So the information provided are enough to solve the excersise. One possible typing error that I identify in the problem statement is that Q doesn't depend on K, L and P only, but it depeds on M too. That's why there are four arrows entering node 15 instead of three. Otherwise there is no lack of information and you can solve the problem as I described above.

A second way to solve the problem is to create the PERT chart based on the data written in the table by yourself. The graph that you will make will be isomorphic with the graph that you will get if you merge the nodes connected by dotted edges on the graph of the problem statement. So after that you will have to create an edge matching between the two graphs in order to find which activity matches which arrow on the given graph.

Both methods will lead to a correct solution, you can try them for practice.


Determining if a TM decidable or not, with limited information

A TM cannot be "decidable". What you are asking is whether the language that you describe is decidable.

Hint: the language $A_{TM}=\{<M,w>: M \text{ accepts }w\}$ is undecidable even if we restrict to TMs with a binary work alphabet. Try to reduce from this problem, by utilizing only the letters $\{a,B\}$ from $\Gamma$. Then, you can use $b$ only when you need it.

Please comment if you need further hints.


How to guess the value of $j$ at the end of the loop?

If you unfold the loop you get:

$$\text{val}( j)=n+n/2+n/4+ n/8 \ldots$$

In total you have $\log n$ terms.
See this post, how to evaluate the sum.


Minimum number of tree cuts so that each pair of trees alternates between strictly decreasing and strictly increasing

I'll describe two ways you could solve this problem.  Either works.  In some sense they are basically the same algorithm, just viewed from two different perspectives.

Dynamic programming algorithm

This can be solved in linear time with dynamic programming.  Let $d_i$ denote minimum number of $a_i,\dots,a_n$ that must be cut to produce an alternating sequence if you start in the downwards direction for the first pair (the pair $a_i,a_{i+1}$) and don't cut $a_i$, and $u_i$ the minimum number to produce an alternating sequence starting in the upwards direction if you don't cut $a_i$, and $u'_i$ the minimum number to produce an alternating sequence starting in the upwards direction if you do cut $a_i$.  Then you can write down a recurrence relation that expresses $d_i,u_i,u'_{i+1}$ in terms of $d_{i+1},u_{i+1},u'_{i+1}$, and you can evaluate it in $O(n)$ time using dynamic programming.

In particular, the recurrence relation is $u'_i = 1 + d_{i+1}$ and

$$d_i = \begin{cases}
\min(u_{i+1},u'_{i+1}) &\text{if }a_i>a_{i+1}\\
+\infty &\text{otherwise.}
\end{cases}$$

$$u_i = \begin{cases}
d_{i+1} &\text{if }a_i<a_{i+1}\\
+\infty &\text{otherwise.}
\end{cases}$$

Once you've computed all these values, the final answer for the minimum number of cuts needed for the sequence $a_1,\dots,a_n$ is $\min(d_1,u_1,u'_1)$.

Graph search

Alternatively, we can solve this by building up a suitable graph and then finding the shortest path in this graph.

Label a tree as a "peak" if in  it is higher than its neighbors in the final sequence, and a "valley" if it is lower than its neighbors in the final sequence.  The final sequence will alternate between peaks and valleys.  Here is the two key observations:

The optimal solution will never cut any tree that ends up as a peak.  (Any solution that involves cutting a peak will remain valid if you don't cut the peak, and that reduces the number of cuts by 1.)
In the optimal solution, you can assume without loss of generality that every tree that ends up a valley is cut down to the ground, i.e., to the minimum height.  (Any solution that involves cutting a valley only partway will remain valid if you cut it down to the ground.)

Since we want to find an optimal solution, we will consider only solutions that follow both rules.

Let $a_1,\dots,a_n$ be the sequence.  We will build a graph with $3n$ vertices.  Each vertex has the form $\langle i,t,c \rangle$ where $i \in \{1,2,\dots,n\}$ is an index that identifies a tree, $t$ indicates whether tree $i$ will be a peak or a valley in the final solution, and $c$ indicates whether tree $i$ is cut to the ground or uncut in the final solution.  We'll have an edge from one vertex to the next if they can be adjacent in a final solution.  Thus, we have the following edges:

$\langle i, \text{peak}, \text{no}\rangle \to \langle i+1, \text{valley}, \text{no} \rangle$, with length 0, for those $i$ where $a_i>a_{i+1}$
$\langle i, \text{peak}, \text{no}\rangle \to \langle i+1, \text{valley}, \text{yes} \rangle$, with length 1, for all $i$
$\langle i, \text{valley}, \text{no}\rangle \to \langle i+1, \text{peak}, \text{no} \rangle$, with length 0, for those $i$ where $a_i<a_{i+1}$
$\langle i, \text{valley}, \text{yes}\rangle \to \langle i+1, \text{peak}, \text{no} \rangle$, with length 0, for all $i$

Finally, find the shortest path in this graph from a start vertext to an end vertex, where the start vertices are those of the form $\langle 1, *, *\rangle$ and the end vertices are those of the form $\langle n, *, *\rangle$.  The length of this path will correspond to the minimum number of cuts needed in the optimal solution, and the path itself can be used to reconstruct the final solution.  This shortest path can be found in $O(n)$ time using breadth-first search (BFS) on the graph defined above.


Restricting longest path with 2-coloring to paths of at most constant length

If you want to check whether a graph has a path of length $c$, you can go over all ordered sequences of $c+1$ vertices, and check whether all the edges in the corresponding path exist. On a RAM machine, this is an $O(n^{c+1})$ algorithm. When $c$ is constant, this is polynomial time.


Finding prime factors of non-random key generator

So you have two numbers that:

both have two prime factors, and
you strongly suspect that they share a factor.

So one is $n_{1}=pq_{1}$ the other $n_{2}=pq_{2}$. What is their GCD?

   What happens when you apply Euclid' algorithm?


Continue on: Prove that $BPP^{BPP} = BPP$

Your BPP algorithm makes polynomially many queries to the BPP oracle, and assuming that all these queries are answered correctly, has error probability at most $1/3$, say.
In order to simulate this algorithm without appealing to the oracle, we replace each oracle call with the BPP algorithm itself. By repeating the BPP algorithm polynomially many times, we can reduce the error probability of each oracle call to $2^{-n}$, say. The union bound then implies that all oracle calls are answered correctly with probability $1-o(1)$, and so the entire algorithm has error probability at most $1/3+o(1)$, which suffices to put the language in BPP.


The question asks for a circuit which is given a sequence of bits, one in each round, and is supposed to output $1$ each time that the last $4$ bits form the subsequence $1101$; otherwise $0$ should be output. For example, if the input is $110110101$ then the output should be $000100100$. Naturally, the circuit will have to retain some memory.


Minimum set cover with incompatible sets

Your problem can be stated as a minimum weight maximal independent set problem.
Construction:
Construct a bipartite graph $G = (L,R,E)$, where the right partition $R$ corresponds to $\mathcal{R}$ and the left partition $L$ corresponds to $X$. An edge $(u,v) \in E$ iff an element $u$ is contained in the set $v$.
Let $G'$ be the updated graph obtained by adding edges within $R$ based on the incompatibility of vertices in $R$.
Furthermore, assign a weight of $\infty$ on each vertex of $L$ and weight $1$ on each vertex of $R$. Also, attach a new pendant vertex of weight $0$ to each vertex in $R$. Let $G_{w}$ be this new graph.
Now, your problem can be stated as finding minimum weight maximal independent set problem (MMIS) on $G_{w}$. It is a standard problem discussed here. Your problem has a feasible solution if and only if MMIS has a finite value. Also, your problem has a solution of size $k$ if and only if MMIS has a value $k$.
Correctness:
Suppose, a feasible instance of the independent set cover problem is $S_{1}, \dotsc, S_{k}$. Then, the maximal independent set contains vertices in $R$ corresponding to $S_{1}, \dotsc, S_{k}$ and pendant vertices corresponding to the remaining sets. It is easy to see that it is an independent set and it is also maximal. Moreover, the weight of the independent set is exactly $k$.
Similarly, you can prove the other direction, i.e., if there is a maximal independent set of value $k$, there is an independent set cover of size $k$.

Note: Instead of assigning $\infty$ value to the vertices in $L$, you can also assign some sufficiently large finite value, say $|\mathcal{R}|+1$. That will also work.


Are deterministic and nondeterministic Cellular Automata equivalent?

I think you should define precisely what you mean by equivalent, and
possibly what kind of CA you are willing to consider, with what
communication grid. So I will just assume the simplest interpretation.

Given that it is fairly easy to build deterministic cellular automata
with Turing power (even with a 1 dimemsional grid), and that according
to the current wisdom of the Church-Turing Thesis, we have little
chance to improve on that, my best bet is that non-deterministic
cellular automata cannot be more powerful than deterministic
ones. Given that adding non-determinism can only increase the
computational power, i.e. a deterministic automaton is a special case
of non-determinism, whe should not expect non-deterministic cellular
automata to be less powerful than deterministic ones.

Hence, in terms of computational power, deterministic and
non-deterministic cellular automata are equivalent.


Why don't people use Fermat's little theorem to check if number is prime?

Expanding on Karolis's answer, the probabilistic primality tests used in practices, the Miller-Rabin test and the Solovay-Strassen test, are both based on modifications of the test you suggest, also known as the Fermat primality test. (Same for the less common Baillie-PSW test.) The problem with the Fermat test is that it is fooled by some composites known as Carmichael numbers.

The Solovay-Strassen test replaces the test $a^{n-1} \equiv 1 \pmod{n}$ with the similar formula $a^{(n-1)/2} \equiv \left(\frac{a}{n}\right) \pmod{n}$. Here $\left(\frac{a}{n}\right)$ is a Jacobi symbol, which for prime $n$ and $a \nmid n$ is equal to $1$ if $a$ is a quadratic residue modulo $n$ (i.e. has a square root modulo $n$) and to $-1$ if $a$ is a quadratic non-residue modulo $n$. There is a GCD-like algorithm for computing the Jacobi symbol, which makes the test feasible. It can be shown that if $n$ is an odd composite, then at least half the $a$s fail this test.

The Miller-Rabin test relies on the (similar) property that $1$ has two square roots modulo a prime, but more modulo composites. The idea is to check that $a^{n-1} \equiv 1 \pmod{n}$ and $a^{(n-1)/2} \equiv \pm 1 \pmod{n}$. If $a^{(n-1)/2} \equiv 1 \pmod{n}$, then we check that $a^{(n-1)/4} \equiv \pm 1 \pmod{n}$. And so on. The test fails if for some $k$, $a^{(n-1)/2^k} \equiv 1 \pmod{n}$ but $a^{(n-1)/2^{k+1}} \not\equiv \pm 1 \pmod{n}$. It can be shown that if $n$ is an odd composite, then at least three quarters of the $a$s fail this test (and so less iterations are needed compared to the Solovay-Strassen test).


How to draw the heap for an array in Java?

Heap is an almost complete binary tree. So if you're planning to construct the tree you can just start by filling the values in the tree from top to down and left to right ie, proceed by filling nodes levelwise.
Arraylist or linked list doesn't matter here because both stored the level order traversal of the tree.
Ex. list.add(0), list.add(1), list.add(1), list.add(2), list.add(3), list.add(5)
                              0
                            /    \
                           1      1
                           / \     /
                         2   3  5


DFA that rejects $a^{23}$ but accepts $\{a^i|i\geq 24\}$

This is not possible. A DFA on a one symbol alphabet is a directed graph with out-degree 1. The walk one follows from the start state consists of a (possibly zero length) path followed by a cycle. As all sufficiently long strings are accepted, all states in the cycle must accept. If the DFA has at most 11 states, a walk of length 23 must be in the cycle, so it must accept.

More generally, if a DFA on one symbol rejects $a^n$ but accepts all $a^m$, $m>n$, then it must have at least $n+1$ symbols and start with a path of length $\ge n$, the $n$th state rejecting, followed by a cycle of accepting states of length $\ge 1$.


This problem is $\textrm{NP}$-hard by a reduction from (the decision version of) set-cover: given an integer $k$, a set of items $I = \{x_1, \dots, x_n\}$ and a collection $S = \{S_1, \dots, S_m \} \subseteq 2^I$ of subsets of $I$, decide whether there is a subset $C$ of $S$ such that $|C| \le k$ and $\bigcup_{S_j \in C} S_j = I$.

Given an instance of set-cover, we can reduce it to your problem as follows:

There are $n$ packages to be shipped. Each package has a unique combination of weight class and category. For simplicity you can think of all the packages being in same category but having different weight classes. I will denote by $W_i$ the weight class of the $i$-th package.
There are $m$ shipping companies. The $j$-th shipping company ships a package of weight class $W_i$, with $x_i \in S_j$, for a cost of $\varepsilon < \frac{1}{n}$ and a package of weight class $W_i$, $x_i \not\in S_j$, for a cost of $1$.
Pick $w = k$.

There is a set-cover of size at most $k$ iff the cost for shipping all the packages using at most $w$ companies is at most $\varepsilon n < 1$.

Indeed, given a set-cover $C = \{ S_{j_1}, \dots, S_{j_\ell} \}$ of size $\ell < k$ we know that $\bigcup_{i=1}^\ell S_{j_\ell} = I$, i.e., if we select the $j_1$-th, $j_2$-th, $\dots$, and $j_\ell$-th shipping companies, we can send each of the $n$ packages at a cost of $\varepsilon$.

On the other hand, if there is a way to send all the packages using at most $w$ shipping companies with a cost of at most $\varepsilon n < 1$ then, for each of the $n$ packages, there must be at least one selected company that ships it with a cost of $\varepsilon$. In other words the sets $S_j$ corresponding to the selected companies are a set-cover of size at most $w = k$.

Notice that any solution has either a cost of $\varepsilon n$ or a cost of at least $1$. Choosing $\varepsilon$ small enough shows that this problem is also inapproximable (in fact, if a shipping cost of $0$ is allowed, you can directly set $\varepsilon = 0$).


Try the CRC hash; it has this property.  You can also look at Merkle tree hashing.

See also https://crypto.stackexchange.com/q/24622/351, Which fingerprinting/hashing algorithms support compounding?, https://crypto.stackexchange.com/q/6497/351.


Applying Case 3 of Master Theorem to $T(n) = 9T(n/3) + n^3$

Your statement of the regularity condition has a typo: it suffices to show that there exists a constant $c < 1$ such that for large enough $n$,
$$
af(n/b) \leq cf(n).
$$
Substituting $a,b,f$, we have to show that for some constant $c < 1$,
$$
9(n/3)^3 \le c n^3.
$$
You take it from here.


Suppose that you have a graph and each vertex is colored with one of three colors, and let the set of different-colored vertices be $A, B, C$.
Now, try to find a triangle with one vertex from each partition.  For each vertex $a \in A$, try let $B_a$ and $C_a$ be $a$'s neighborhood in $B$ and $C$, respectively.  Now you only need to check if there is an edge from $B_a$ to $C_a$.  If there is one, you have your triangle, otherwise, you try another vertex from $A$.
Let us call this subroutine colorful_triangle(G, A, B, C).  Observe that it is not necessary that $A \cup B \cup C = V(G)$.

Let $G$ be the graph, $\chi$ the coloring and  $\pi$ a permutation of colors.
Let $\chi(i)$ be the set of vertices that received color $i$.
Now let $A = \chi(\pi(1))$, $B = \chi(\pi(2))$, $C = \chi(\pi(3))$.  Run the subrouting colorful_triangle(G, A, B, C).  If successful, continue with
$A = \chi(\pi(4))$, $B = \chi(\pi(5))$, $C = \chi(\pi(6))$, and so on.
If you at some point are unsuccessful, move on to the next permutation.


8.    while (the priority queue is not empty):
 9.        u ← delete-min from priority queue

10.        For each edge (u,v) ∈ E leaving u:
11.            If d(v) > d(u) + l(u,v):
12.                decrease-key of v to d(u) + l(u,v) in priority queue
13.                d(v) ← d(u) + l(u,v)

Consider the multi-set of all edges that appear on line 10, where $u$ goes through all vertices thanks to the line 9 inside the while loop. There are two cases.

The graph is undirected. Each of those edges must be incident to a vertex $u$. So each edge in the graph appears exactly twice.
The graph is directed. Each of those edges must have $u$ as its starting endpoint. So each edge in the graph exactly appears once.

So in total, the number of edges that appear on line 10 is either $2|E|$ with undirected graph or $|E|$ with directed graph. So the running time from lines 8, 10, 11, and 12 is $2mO(\log(n))$ or $mO(\log(n))$. That is, $O(m\log(n))$.

Had the line 10 been For each edge (w,v) ∈ E:, your analysis might have had a chance to be correct.


Determine if the language of words with same number of 1's and 2's is context-free or not

When it comes up to deciding if a language is context-free or not, I try the following 'roadmap' to come up with an answer.
$1.$ Try to make a CFG for the given language. If we can make a CFG, we have proved that the language is context-free.
$2.$ If step $1$ did not work out, there is a probabilty that the language is not context-free. So try proving that the given language is not context-free by the pumping lemma.
$3.$ If I fail to prove that language is not context-free, I probably failed to make a CFG so I start to make a PDA.
Remark: This is my way to (dis)prove context-free languages, there are many other ways to do this. So don't take this as a general step-by-step plan.
In your example, we need to (dis)prove $$L_2=\{w \in \{0,1,2\}^* : \text{$w$ has the same number of $1$'s and $2$'s}\}$$
So when we think of a CFG, we should consider that whenever we add a $1$, we should also add a $2$ (and vice-versa), as $|1| = |2|$. We also know that the language can be empty and that the number of $0$'s do not matter.
So
$$S \rightarrow \epsilon $$
$$S \rightarrow 0S$$
$$S \rightarrow 1S2S$$
$$S \rightarrow 2S1S$$
As we were able to make a CFG, we can say that the language $L_2$ is a CFL.


greedy algorithms - minimizing total payment

This answer is a hint.

Assume an optimal solution exists.  Order its choices so that they agree with your algorithm's choices for as long as possible; the order after this is unimportant.  If all of them agree, then your algo picked an optimal solution, so you're done!  If not, then at look at the first group of 3 where they disagreed.  Even though you don't know exactly what an optimal solution is, you know that one exists, and you can make changes to it -- e.g. swapping some books in its ordering -- to produce a new solution.

Can you think of a way to change it in such a way that (a) it now agrees with your algo for 1 more group of 3 and (b) its score didn't get worse?  If so, then clearly you could repeat this step until...  What happens?


Relation between semi decidable, undecidable and countable sets

Undecidable is simply the complement of decidable, as the name suggests: anything that is not decidable is undecidable. So the whole pink area of your diagram consists of undecidable languages.

All languages over finite alphabets are countable. For example, every string over alphabet $\{0,1\}$ is a natural number written in binary.1 Everything in your diagram is countable. We only ever consider finite alphabets; infinite alphabets aren't physically realizable because we can't store infinitely many distinguishable possibilities in a finite space.

1. A small problem is that $0$, $00$, $000$, etc. are all the number zero written in binary. So, instead, associate the binary string $xyz$ with the natural number $1xyz$ and now, every binary string represents a different natural number.


Need help to come up with definitive proofs with regard to Planar Graphs

Since all the degrees of regions are said to be 3, we can say $2e=3r$. I substituted this value into the Euler equation, $v-e+r=2$  and got my final answer as $2(v+2)$.

The final answer should be $2(v-2)$.

  Since I derived the value $r=2(v-2)$ which would always remaining even while incrementing $v$.

You are right that $r$, the number of regions will always remain even since $r=2(v-2)$. However, question 2 is asking you to prove "the number of tricolored regions is always even no matter how the vertices are colored.".

  I don't really understand the point of the Hint or maybe what exactly we have to prove here.

The hint is meant to give you a clue how to reduce the number of vertices.  The proof (or my proof) is quite easy and direct once you know it. I will let you figure out your proof.


How fast can all nth roots of an integer be computed?

Let's say n is very large, say around $2^{1000}$. In theory, you can calculate the k-th root of n by calculating $2^{(\log n) / k}$. Doing this for multiple k means you calculate $\log n$ only once, so you save some time here.

You will spend a large amount of time calculating say the first 50 roots because you need very high precision to calculate the root rounded down to the nearest integer. I can't see you saving any time by calculating multiple roots together.

The next roots are much easier to calculate. Then if k gets large, say 200, you will find that many roots rounded down are the same. Here you can make some savings by calculating for which range of integers k the k-th root of n will be between some integer r and r+1, and therefore the k-th root rounded down equals r. In this example there will be a few hundred k where the k-th root rounded down equals 2, for example.

But I think the first few roots (2nd, 3rd, 4th root) will take so much more time due to the high precision required, that the effort for the remaining roots will be much smaller. So I would say that you can save a little bit of time, but likely just a constant factor.

(Also, the effort may be bigger if the k-th root of n is very, very close to an integer, but that doesn't change the analysis. )


Quantum state probabilities and amplitudes - absolute value squared?

Using $\alpha^2$ doesn't make sense since you get negative or even non-real probabilities! The correct "recipe" is indeed $|\alpha|^2$. This also meshes well with the fact that the operations you are allowed to apply are unitary.


Give one example where it takes Non- deterministically exponential time to solve the problem?

There are problems that cannot be solved in polynomial time on a nondeterministic machine. Indeed, there are problems that cannot be solved on any Turing machine, such as the halting problem.

We know from the nondeterministic version of the time hierarchy theorem that there are things that can be done in exponential time on a nondeterministic TM that cannot be done in polynomial time.  That is, $\mathrm{NP}\subsetneq\mathrm{NEXP}$.

Wikipedia gives several examples of $\mathrm{NEXP}$-complete problems: these are examples of problems that are provably not in $\mathrm{NP}$.


Is there an algorithm for selecting best matching data in a data set given a set of parameters?

Assuming you don't have that many recipes, you could just go over all of them and choose the best $k$ (use a heap of size $k$). You should test the naive approach before looking for fancier approaches.

Otherwise, you could use a data structure supporting nearest neighbor search. These are hard to implement, but good implementations should be available in computational geometry libraries.


Without any additional information about your setting or requirements, an obvious first choice is some self-balancing binary search tree, such as a red-black tree. It allows you to insert and remove elements in $O(\log n)$ time, where $n$ is the number of elements.

Following a standard engineering approach, try it out first. If it doesn't meet your requirements, analyze your situation more carefully, and try something else.


Determining whether the language of a DFA is closed under reversal

For a language $L$, we define the reverse language $L^{\mathcal{R}}$ by
$$ L^{\mathcal{R}} = \{ x^{\mathcal{R}} : x \in L \}. $$
In words, $L^{\mathcal{R}}$ is obtained from $L$ by reversing all words.

It follows that $L = L^{\mathcal{R}}$ if and only if, for each word $x$, we have $x \in L \Leftrightarrow x^{\mathcal{R}} \in L$.


Is $L = a^{n}b^{n+m}c^{m} | n,m \geq 0$ a context free or a recursive language?

Here's a hint:

Could you make a grammar for $a^nb^n$, $n\ge 0$?
Could you make a grammar for $b^mc^m$, $m\ge 0$?
Could you make a production that concatenates the languages in (1) and (2) above?


What is the time complexity of the SGVB estimator?

Asymptotic running time analysis is not terribly useful for gradient descent used to train machine learning models.  In practical machine learning, we run gradient descent for some fixed number of epochs, e.g., 200 epochs; which takes time proportional to 200 times the size of the training set times the time per evaluation of the neural network.  That value 200 is arbitrary and set based on what achieves the best accuracy results, and there is little theoretical basis for choosing it.


Why is adding log probabilities faster than multiplying probabilities?

Also, the Wikipedia page (https://en.wikipedia.org/wiki/Log_probability) is confusing in this respect, stating "The conversion to log form is expensive, but is only incurred once." I don't understand this, because I think you would need to take the log of every term independently before adding. What am I missing?

If you just want to compute $P(A_1)\ldots P(A_n)$ once, then you are right. You will have to compute $n$ logarithms and $n-1$ additions, whereas the naive method requires $n-1$ multiplications.

However, it is very common that you want to answer queries of the form:

  Compute $\prod_{i \in I} P(A_i)$ for some subset $I$ of $\{1, \ldots n\}$.

In that case, you can preprocess your data to compute all $\log P(A_i)$ only once, and answer each query by doing $|I|$ additions.

  Finally, the justification that "computers perform addition faster than multiplication" is kind of vague. Is that specific to the x86 instruction set, or is it some more fundamental trait of processor architectures?

This is a broader question. In general it is (probably?) harder to compute multiplication than addition. Computing $a+b$ is linear in the size of $a$ and $b$ (using the trivial algorithm), whereas we currently don't know how to compute $a\times b$ with the same time complexity (check the best algorithms here).

Of course there is no definitive answer: for instance if you deal with integers only and you multiply by powers of $2$, then you should rather compare shift with add operations.

Nevertheless this is a reasonable statement on all common computer architectures: multiplication on floating-point numbers will be slower than addition.


Why are functional languages Turing complete?

In a nutshell:

What characterizes imperative programming languages as close to Turing
machines and to usual computers such as PCs, (themselves closer to
random access machines (RAM) rather than to Turing machine) is the
concept of an explicit memory that can be modified to store (intermediate results). It is an automata view of computation, with a concept of a
state (comprising both finite state control and memory content) that can change as the computation proceed.

Most other models are more abstract. Though they may express the
computation as a succession of transformation steps of an original
structure, these transformation are applied in a sort of intemporal
universe of mathematical meanings. This may preserve properties, such
as referential transparency, that may make mathematical analysis
simpler. But it is more remote from natural physical models that rely
on the concpet of memory.

Thus there are no natural functional machines, except in a larger sense
as explained below, since software is not really separable from
hardware.

The reference to Turing as the yardstick of computability comes probably from the fact that his model, the Turing machine was closest to this physical realizability constraint, which made it a more intuitive model of computation.

Further considerations:

There are many models of computation, which were designed to capture in
the most general possible way the concept of a computation. They
include Turing machines, actually in many different flavors, the
lambda calculus (flavors too), semi-Thue rewriting systems, partial
recursive function,
       combinatory logic.

They all capture some aspects of the various techniques used by
mathematicians to express or conduct computations. And most have
been used to some extent as the basis of some programming language
design (e.g. Snobol for rewriting systems, APL for combinators, Lisp/Scheme for lambda calculus) and can often be combined in diverse ways in modern programming languages.

One major result is that all these computation models were proved
equivalent, which lead to the Church-Turing thesis that no physically
realizable models of computation can do more than any of these models.
A model of computation is said Turing complete if it can be proved
to be equivalent to one of these models, hence equivalent to all of
them.

The name could have been different. The choice of the Turing machine
(TM) as the reference is probably due to the fact that it is probably
the simplest of these models, mimicking closely (though
simplistically) the way a human computes and fairly easy to implement
(in a limited finite form) as a physical device, to such an extent
that Turing machines have been constructed with Lego sets. The basic idea requires no mathematical sophistication. It is probably the simplicity and
realizability of the model that gave it this reference position.

At the time Alan Turing created his computing device, other proposals
were on the table to serve as formal definition of computability, a
crucial issue for the foundations of mathematics (see
Entscheidungsproblem). The Turing proposal was considered by the
experts of the time as the one most convincingly encompassing known
work on what calculability should be (see Computability and
Recursion, R.I. Soare, 1996, see section 3.2). The various proposals were proved equivalent, but Turing's was more convincing. [from comments by Yuval Filmus]

It should be noted that, from a hardware point of view, our computers
are not Turing machines, but rather what is called Random Access
Machines (RAM), which are also Turing complete.

Purely imperative language (whatever that might mean) are probably the
formalisms used for the most basic models, such as Turing machines, or
the assembly language (skipping its binary coding) of computers. Both
are notoriously unreadable, and very hard to write significant
programs with. Actually, even assembly language has some higher level
features to ease programming a bit, compared to direct use of machine
instructions. Basic imperative models are closed to the physical
worlds, but not very usable.

This led quickly to the development of higher level models of
computation, which started mixing to it a variety of computational
techniques, such as subprogram and function calls, naming of memory
location, scoping of names, quantification and dummy variables,
already used in some form in mathematics and logic, and even very
abstract concepts such as reflection (Lisp 1958).

The classification of programming languages into programming paradigm
such as imperative, functional, logic, object oriented is based of the
preeminence of some of these techniques in the design of the language,
and the presence or absence fo some computing features that enforce
some properties for programs or program fragments written in the
language.

Some models are convenient for physical machines. Some others are more
convenient for a high-level description of algorithms, it that may
depend on the type of algorithm that is to be described. Some
theoretician even use non deterministic specification of algorithms,
and even that cn be translated in more conventional programming terms.
But there is no mismatch problem, because we developed a sophisticated compiler/interpreter technology that can translate each model into another as needed (which is also the basis of the Church-Turing thesis).

Now, you should never look at your computer as raw hardware. It does
contain boolean circuitry that does very elementary processing. But
much of it is driven by micro-programs inside the computer that you
never get to know about. Then you have the operating system that makes
your machine appear even different from what the hardware does, On top
of that you may have a virtual machine that executes byte-code, and
then a high-level language such as Pyva and Jathon, or Haskell, or
OCaml, that can be compiled into byte code.

At each level you see a different computation model. It is very hard
to separate hardware level from the software level thus to assign a
specific computational model to a machine. And since they are all
intertranslatable, the idea of an ultimate hardware computation model
is pretty much an illusion.

The lambda calculus machine does exist: it is a computer that can
reduce lambda calculus expressions. Ad that is easily done.

About specialized machine architectures

Actually, complementing Peter Taylor's answer, and following up on
hardware/software intertwinning, specialized machines have been
produced to be better adapted to a specific paradigm, and had their
basic software written in a programming language based on that
paradigm.

These include

The Burroughs B5000 and its successors (1960s), that were adapted for
efficient implementation of recursion, represented at the time by
the language Algol 60.
The Western Digital WD/9000 Pascal MicroEngine, a machines based on
a microprogrammed bytecode specialied for the Pascal programming
language, in the early 1980s.
Several brands of Lisp Machines in the 1980s.

Fundamentally, these are also imperative hardware structures, but mitigated with
special harware features or microprogrammed interpreters to better
adapt to the intended paradigm.

Actually, hardware specialized for specific paradigms does not seem to
have ever been successful in the long run. The reason is that the
compiling technology to implement any paradigm on vanilla hardware
became more and more effective, so that specialized hardware was not
so much needed. In addition, harware performance was fast improving,
but the cost of improvement (including evolution of basic software)
was more easily amortized on vanilla hardware than on specialized
hardware. Specialized hardware could not compete in the long run.

Nevertheless, and though I have no precise data on this, I would suspect that these ventures left some ideas that did influence the evolution of machines, memories, and instruction sets architecture.


Prove or disprove that $NL$ is closed under polynomial many-one reductions

Let's prove the two directions separately. Suppose first that $\mathsf{NL}=\mathsf{P}$. In order to prove the statement, suppose that $B \in \mathsf{NL}$ and that there is a polytime many-one reduction from $A$ to $B$. Since $\mathsf{P}$ is closed under polytime many-one reductions and $B \in \mathsf{NL} = \mathsf{P}$, clearly $A \in \mathsf{P} = \mathsf{NL}$, proving the statement.

Suppose next that the statement is correct. Let $B$ be any non-trivial language in $\mathsf{NL}$ (for example, $B = \{\epsilon\}$), and let $A \in \mathsf{P}$ be arbitrary. Since $A \in \mathsf{P}$ there is a polytime function $f$ computing it. We can easily modify $f$ to a polytime reduction from $A$ to $B$ by fixing some YES instance and NO instance in $B$ (here we need that $B$ be non-trivial). The statement implies that $A \in \mathsf{NL}$. Since $A$ was arbitrary, we deduce that $\mathsf{P} \subseteq \mathsf{NL}$ and so $\mathsf{NL} = \mathsf{P}$.


Where can I find CS problem set resources?

i don't know how far along you are in your learning but I found that actually coding is the best way.
try Scratch. it is a graphical interface for code that jigsaws together only in ways that are syntactically correct so, as you have asked, you can learn to structure code and create anything you like without learning an actual language. it makes understanding simple coding very easy. Enjoy


All soldiers should shoot at the same time

The problem is known as Firing squad synchronization problem. The problem itself, is strictly related to finite state automata. Here, each soldier is a finite automaton; you know that the next state of each soldier depends on its current state and the current states of its two neighbors (except for the first and last soldier). The first soldier in this setting can be though of as the soldiers general who is in charge of starting the attack. The last soldier knows it is the last one. No global communication is available; however, a global clock can be used to synchronize the state transitions of the soldiers. The problem require designing a soldier automaton whose goal is for all soldiers to enter the "SHOOT" state on exactly the same clock tick. By the way, the problem can be solved in $\Theta(n)$ time for $n$ soldiers.


Why absence of surjection with the power set is not enough to prove the existence of an undecidable language?

Let us first recapitulate in which context the cited statement makes sense.

Let us restrict ourselves to the domain of (decision) functions in $\mathbb{N} \to \{0,1\}$ (a subset of all functions).
Every such function corresponds to one element of $\mathcal{P}(\mathbb{N})$ (see characteristic function).
There are countably many Turing machines (simple encoding).

By 1. and 2., there are uncountably many functions. Therefore, there are functions that have no corresponding Turing machine, that is they are not computable. There are simply too many functions; this is what is meant by "there is no surjection".

Now, there are only countably many finite sets in $\mathcal{P}(\mathbb{N})$(extension of Cantor's pairing function). Therefore, the same contradiction can not be derived when only considering finite sets.

If you add some infinite sets to your base set so it becomes uncountable, there is no reason to believe some of the finite sets were undecidable; you only know that there are some undecidable sets. In fact, all finite sets are decidable, so the culprits are always infinite sets.


$n^2$ processors can compare all ${n \choose 2}$ possibilities in constant depth, so yes it's in NC.


If a parser can parse a non-deterministic grammar, is the parser non-deterministic?

No, it doesn't mean that.  A non-deterministic algorithm is one that uses non-determinism.  You're not using non-determinism; your algorithm is completely deterministic.

Here's what's tripped you up.  You can recognize a non-deterministic grammar using a deterministic algorithm.  Similarly, you can recognize whether a word is accepted by a non-deterministic finite automaton (NFA) using a deterministic algorithm (e.g., simply convert the NFA to a DFA, then check whether the DFA accepts the word).  So, no, just because the grammar is non-deterministic does not mean that we should call your parsing algorithm non-deterministic.


When we say an algorithm runs in $O(\lg k)$ time, that is an asymptotic statement.  It means that there exists a constant $c$ such that when $k$ is sufficiently large, the running time is $\le c \lg k$.  It says nothing about what happens when $k$ is small.

In particular, if we say an algorithm runs in $O(\lg k)$ time, that doesn't necessarily mean that when $k=1$ the running time is 0.

The same kind of comment applies to your question as well.  No, it doesn't mean that the running time to sort an array where each element is at most one place away from its sorted position is $O(0)$.  Rather, the complexity of that task is $O(n)$.


Which data structure to use for accessing min/max in constant-time?

A basic data structure that allows insertion and deletion in time $\Theta(\log n)$ are balanced binary search trees. Their memory overhead is reasonable (in case of AVL trees, two pointers and three bits per entry) so millions of entries are no problem at all on modern machines.

Note that in a search tree, finding the minimum (or maximum) is conceptually easy by descending always left (right) starting in the root. This works in time $\Theta(\log n)$, too, which is too slow for you.

However, we can certainly store pointers to these tree nodes, similar to front and end pointers in double-linked linear lists. But what happens when the elements are deleted? In this case, we have to find the in-order successor (predecessor) and update the pointer to the minimum (maximum). Finding this node works in time $O(\log n)$ so it does not hurt deletion time, asymptotically.

You can, however, enable time $O(1)$ deletion of minimum and maximum by threading the tree, that is maintaining -- in addition to the binary search tree -- a double-linked list in in-order. Then, finding the new minimum/maximum is possible in time $O(1)$. This list requires additional space (two pointers per entry) and has to be maintained during insertions and deletions; this does not make the asymptotics worse but certainly slows down every such operation (I leave the details to you). So you have to trade-off the options given your application, that is which operations occur more often and which you want to be fastest.

Note that trees, as all linked structures, tend to be bad for memory hierarchies since they don't necessarily preserve data locality. If your sets are so large that they don't fit into cache completely, you should check out B-trees which are designed to minimise page loads. The above works with them, too.


Is induced subgraph isomorphism easy on an infinite subclass?

This question has been answered on cstheory.

Digest: Chen,Thurley and Weyer (2008) prove that this problem is $W[1]$-hard for every infinite class of graphs.


I am going to answer this question in two parts:
First,
Without reaching into the depths of communication, I want to mention that the data that humans do understand(such as this answer which I am typing) is classified under Layer 7 of the TCP/IP stack. This data gets converted into analog signals that travel over the wire, and any hosts connected to these wires translate these analog signals to electric signals. Electric signals have two states, 0 and 1, which we humans call binary format.
So any data on the wire would essentially be looked upon as a sequence of bits and bytes.

The IP address that you mention, is a component of the IP Protocol, and this protocol is used to carry packets end to end between two hosts on a network. So, the data would be added as a payload on top of an IP packet which contains a IP header. Any devices in between these two hosts which operate on Layer-3 of the TCP/IP stack(the network layer!) would use this header to process the packet. Similarly the end hosts would use this header to determine if the packet indeed was sent to them.
The IP protocol specifies the syntax and semantics of the IP Packet header, and as you might notice the size of the fields are fixed. Now any machine which is looking at a sequence of bits coming in (with the knowledge that it is receiving the IP header) can just read as many bytes as it wants to extract every field of the header. For example, given that the system knows where the IP header starts, the system could read the first 4 bits and understand that it would just read the version of IP packet.

Second,
The conversion that you mentioned, between binary and dotted decimal, is purely for representing data in human readable format(as the other answer mentions). Tools like Wireshark do this to show details of a packet(the internals of this are fascinating). So, you can choose whichever method to convert one form to the other, but the machines don't really need to do this at the level of the TCP/IP stack where it really matters.  The system doesn't really see it as a dotted decimal construct, but a data structure which consists of four 8 byte fields, (or two 16).

Hope this helps !


Connection between CPU address bus and max amount of RAM

A 12 bit address bus means the computer can access $2^{12}$ unique blocks of memory.  Unstated in the problem is the size of each block, and without that information you cannot determine the maximum amount of ram.

Bulat also points out that there are other tricks that could be played, such as multiplexing the address bus.  If the address was sent in 2 cycles rather than 1, then $2^{24}$ blocks could be addressed.

Lacking any other information, and recognizing that this is a homework/test question we can make a few assumptions.  The first is that we're not doing anything exotic like multiplexing the address bus.  In a test-question setting, it is highly likely that they would call a multiplexed 12 bit bus a "24 bit bus" instead unless you were on a chapter specifically dedicated to clever address bus tricks.

The second assumption we have to make is the size of the block.  Since it isn't specified, there are two common assumptions we could make.  The first is that it is byte addressable, meaning each byte can be addressed individually as its own block.  In that case, there's a maximum of $2^{12}$ bytes of memory addressable.  The other common assumption is that they are addressable by machine word.  If you are working in a chapter on 16-bit machines, it might be 16-bit blocks (2 byte), so there'd be a maximum of $2^{12}\cdot 2 = 2^{13}$ bytes.

Given it is a test question, and your teacher is not evil, I would assume the simplest answer is likely correct.  I'd assume 1 byte blocks, and no exotic trickery, yielding a best answer of $2^{12}$ bytes.  If I was facing this in an industry setting, I'd find the datasheets on the processor to determine the exact answer.


This is a project I've been thinking of venturing into for a few years now, and I was fortunate to have a very useful discussion about it at the time I started planning it with Chris Lattner (at the time, one of the main architects of LLVM, although better known these days perhaps for his work on Swift).

It does seem that there is a possibility of producing correctness proofs for a subset of C (or potentially C++) using LLVM.  There has already been some work done which would be useful:

As discussed in comments, memory safety is critical.  Without memory safety, type safety is essentially irrelevant.  A number of memory-safety related analyses and transformations have already been implemented for LLVM that could help.  These include:
"fat pointers", i.e. transformation of C style pointers into pointers into areas of defined size, in order to catch bound errors
a transformation applied to dynamic memory allocation that enables detection of use of pointers after they have been freed.  These two features are described in this paper.

For the subset of C programs that perform no type casts, applying these transformations may be adequate.  Of course, real C and/or C++ code often uses typecasts, and adding this facility is more challenging.  For performance sake, as many of these cases as possible must be caught at verification time rather than runtime, although in the end of the day the use of runtime type information and a dynamic casting implementation would be enough to allow for entirely safe C code.


The difference between absurd reasoning and contraposal reasoning

I've never heard those terms in the context of computer science.  When you mention "contraposal reasoning", I've never heard that term before, but I suspect that might be a reference to proving the contrapositive.  When you mention "absurd reasoning", I've never heard anyone use that specific phrase, but I suspect you might be referring to proof by contradiction, also known as reductio ab absurdum, which is Latin for reduction to absurdity.

These are general proof techniques. They're not specific to showing that a language is not regular.

General advice: I recommend that you try to avoid proof by contradiction.  It's a valid proof technique, but my experience is that it often leads beginners awry and causes them to make mistakes in the proof.  I recommend instead proving the contrapositive; it leads to more straightforward proofs where it is easier to avoid errors, and spot where you went wrong if you do make an error.


Count the number of Euler PATHs in directed graph?

You can actually come up with a formula for this. Let $\ell_0,\ell_1$ be the number of self-loops at $0,1$, and let $e_{01},e_{10}$ be the edges from $0$ to $1$ and in the other direction. We must have $|e_{01}-e_{10}| \leq 1$. If $e_{01} = e_{10}+1$ then the path must start at $0$; if $e_{10} = e_{01}+1$ then it must start at $1$; if $e_{01} = e_{10}$ then both are possible. We will count paths starting at $0$.

Given an Eulerian path starting at $0$, we can write it as
$$
L_0 E_1 L_1 E_2 \cdots E_m L_m,
$$
where $L_0,L_2,\ldots$ are collections of self-loops at $0$, $L_1,L_3,\ldots$ are collections of self-loops at $1$, $E_1,E_3,\ldots$ are $0\to 1$ edges, and $E_2,E_4,\ldots$ are $1\to 0$ edges. We can decompose this path into three components:
$$
E_1 E_2 \ldots E_m \\
L_0 L_2 \ldots \\
L_1 L_3 \ldots
$$
We can choose the first component in $e_{01}! e_{10}!$ ways, the second component in $\ell_0!$ ways, and the third component is $\ell_1!$ ways. It remains to choose a way of partitioning the latter two strings into their components. In order to count this, assume that $m$ is even (the case $m$ odd is very similar) and divide the original path differently:
$$
L_0 E_1 L_2 E_3 L_4 \ldots E_{m-1} L_m \\
L_1 E_2 L_3 E_4 L_5 \ldots E_{m-2} L_{m-1} E_m
$$
The first line contains $m/2$ "breakpoints" out of $\ell_0 + m/2$ symbols in total, so the number of ways of breaking $L_0L_2\ldots L_m$ into its $m/2+1$ parts is $\binom{\ell_0+m/2}{m/2}$. The computation is similar for the second line, once we remove the $E_m$ which must appear at the end; we get $\binom{\ell_1+m/2-1}{m/2-1}$.

I'll leave you the task of bringing everything together to one formula.


What is an upper bound of T(n) = 2 T(3n/10) + T(4n/10) + n

You can prove this using induction, but it will be messy. I'll show you a better approach below (unless you explicitly want to solve it  using induction).

Yes, the answer is $O(n \log n)$, which follows most easily using the Akra-Bazzi method. (This is a generalization of the better-known Master theorem, and is extremely useful for solving these types of recurrences.)

Clearly, the recursion satisfies the form from the statement of the Akra-Bazzi theorem: $g(x)=x$, and the constants $a_i$ and $b_i$ obviously satisfy the requirements.

In your case, $b_1=3/10$ and $a_1=2$; and $b_2=4/10$ and $a_2=1$. Thus $a_1\cdot b_1 + a_2\cdot b_2=1$, thus we take $p=1$. By the Akra-Bazzi theorem, the solution is $T(x) = O(x \cdot (1 + \int_1^x \frac{g(u)}{u^{p+1}} du))$. Because $p=1$ we are integrating the function $x/x^2=1/x$.

Since $\int_1^x \frac{1}{u} du = \log x$, we have that $T(x) = O(x (1 + \log x))$ which is $O(x \log x)$.

Using variable $n$ instead of $x$, we state this in more familiar notation: $T(n) = O(n \log n)$.

In fact, Akra-Bazzi gives us a stronger result that $T(n) = \Theta(n \log n)$, from which it immediately follows that $T(n) = O(n \log n)$. This is because $f(n) = \Theta(g(n))$ if and only if $f(n) = O(g(n))$ AND $f(n) = \Omega(g(n))$.


The nature of a position in this game depends only on $n \bmod{11}$. If $n \equiv 0,2,4 \pmod{11}$ then $n$ is a losing position, otherwise it is a winning position. You can prove this by induction by showing that (1) every move from a losing position leads to a winning position, (2) at every winning position one can move to a losing position. This can be checked by exhaustive case analysis:

$0 \bmod{11}$: moves lead to $5,6,10 \bmod{11}$, all winning positions.
$1 \bmod{11}$: removing 1 match leads to $0 \bmod{11}$, a losing position.
$2 \bmod{11}$: moves lead to $1,7,8 \bmod{11}$, all winning positions.
$3 \bmod{11}$: removing 1 match leads to $2 \bmod{11}$, a losing position.
$4 \bmod{11}$: moves lead to $3,9,10 \bmod{11}$, all winning positions.
$5 \bmod{11}$: removing 1 match leads to $4 \bmod{11}$, a losing position.
$6 \bmod{11}$: removing 6 matches leads to $0 \bmod{11}$, a losing position.
$7 \bmod{11}$: removing 5 match leads to $2 \bmod{11}$, a losing position.
$8 \bmod{11}$: removing 6 match leads to $2 \bmod{11}$, a losing position.
$9 \bmod{11}$: removing 5 match leads to $4 \bmod{11}$, a losing position.
$10 \bmod{11}$: removing 6 match leads to $4 \bmod{11}$, a losing position.

For completeness, the $g$ values are $0,1,0,1,0,1,2,3,2,3,2$ (and then they repeat).

Your strategy is as follows: if $n$ is a winning position you start, otherwise you go second. Then you follow the strategy outlined above, which is guaranteed to win.

This strategy can be computed mechanically using the Sprague–Grundy function $g$.


Writing programs with a block programming environment vs. Writing programs using high level prgramming language

Scratch is a Turing-complete language, so any problem that can be solved with computers can be solved using Scratch (just like Python or Java).  However, you would have to reduce the problem to one that can be solved with Scratch.

In application, Scratch can't do anything that you may be interested in as an engineer, such as hardware interfacing.


Splitting permutations into transpositions

One way to do it consists of two steps:

Find the cycle representation of the input.
Convert the cycle representation into a product of transpositions.

The first step is very similar to DFS. The second step is an exercise in permutation group theory.


Is a computer equivalent to a Turing machine or linear bounded automata?

A machine bounded by $\Theta(1)$ memory is a finite state automaton (As a matter of fact, proving that $\textsf{DSPACE}(\Theta(1)) = \textsf{REG}$ is a classical exercise).

We say that "Turing machines can do whatever computers can" because, as long as we keep in mind that real computers are subject to limitations in computational power, it's more useful to think of computers as imperfect implementations of a universal Turing Machine rather than perfect implementations of a finite state automaton.


Every grammar, by definition, generates a single, unique language.

The definition of "generating $L$" includes that $\overline{L}$ has to be not generated. That's obviously not the case for any proper subset of the "largest" generated language.

The definition has not been chosen without reason: using your approach, every formal language would be regular (as subset of $\Sigma^*$). That would not be a useful model at all.


Finding $k$ claws ($K_{1,3}$ bipartite graphs) in a graph?

Finding vertex-disjoint copies of a subgraph $H$ in a graph $G$ is known as Graph Packing.

You could use Divide and Color to find the claws in $O^*(4^k)$, also deterministically (look for Chen et al. construction of universal set for derandomization).


Are the Before and After sets for context-free grammars always context-free?

Yes, $\mbox{Before}(\beta)$ and $\mbox{After}(\beta)$ are context-free languages.  Here's how I would prove it.  First, a lemma (which is the crux).  If $L$ is CF then:

$\mbox{Before}(L,\beta) = \{ \gamma \ |\ \exists \delta . \gamma \beta \delta \in L \}$

and

$\mbox{After}(L,\beta) = \{ \gamma \ |\ \exists \delta . \delta \beta \gamma \in L \}$

are CF.

Proof?  For $\mbox{Before}(L,\beta)$ construct a non-deterministic finite-state transducer $T_{\beta}$ that scans a string, outputting every input symbol it sees and simultaneously searches non-deterministically for $\beta$.  Whenever $T_{\beta}$ sees the first symbol of $\beta$ it forks non-deterministically and ceases outputting symbols until either it finishes seeing $\beta$ or it sees sees a symbol that deviates from $\beta$, stopping in either case. If $T_{\beta}$ sees $\beta$ in full, it accepts upon stopping, which is the only way it accepts.  If it sees a deviation from $\beta$, it rejects.

The lemma can be jiggered to handle cases where $\beta$ could overlap with itself (like $abab$ -- keep looking for $\beta$ even while in the midst of scanning for a prior $\beta$) or appears multiple times (actually, the original non-determinisic forking already handles that).

It's fairly clear that $T_\beta(L) = \mbox{Before}(L,\beta)$, and since the CFLs are closed under finite-state transduction, $\mbox{Before}(L,\beta)$ is therefore CF.

A similar argument goes for $\mbox{After}(L,\beta)$, or it could be done with string reversals from $\mbox{Before}(L,\beta)$ , CFLs also being closed under reversal:

$\mbox{After}(L,\beta) = \mbox{rev}(\mbox{Before}(\mbox{rev}(L),\mbox{rev}(\beta)))$

Actually, now that I see the reversal argument, it would be even easier to start with $\mbox{After}(L,\beta)$, since the transducer for that is simpler to describe and verify -- it outputs the empty string while looking for a $\beta$. When it finds $\beta$ it forks non-deterministically, one fork continuing to look for further copies of $\beta$, the other fork copying all subsequent characters verbatim from input to output, accepting all the while.

What remains is to make this work for sentential forms as well as CFLs.  But that is pretty straightforward, since the language of sentential forms of a CFG is itself a CFL.  You can show that by replacing every non-terminal $X$ throughout $G$ by say $X^\prime$, declaring $X$ to be a terminal, and adding all productions $X^\prime \rightarrow X$ to the grammar.

I'll have to think about your question on unambiguity.


If pref(L) is regular, does that imply L is regular?

What you say doesn't make sense. How can you operate with a NFA for $L$ if you cant be sure that $L$ is regular?

Try to consider this language
$$L=\{ uu \mid u \in \Sigma^*\}$$
This language is not regular, it is not even context-free, which can be shown with the pumping lemma. I think from here you can continue by yourself. What is $\text{pref}(L)$?


Returning m greatest elements from k sorted array

Your idea works out. The idea is to maintain a heap of size $k$ which contains exactly one element from each array. For each array $A_i$, we maintain an index $p_i$ which keeps track of the position of the current element in the array. Initially, $p_i = n_i$, and we insert $A_i[n_i]$ into the heap.
We then repeat the following $m$ times:

Extract the maximum element from the heap.
If the extracted element belonged to $A_i$, then we decrease $p_i$ by one and insert $A_i[p_i]$ into the heap.

The initialization phase takes time $O(k)$, and the extraction phase takes time $O(m\log k)$, for a total of $O(k+m\log k)$. You can prove that the extracted elements are indeed the $m$ largest ones.


Why is subarray $A[p..k-1]$ empty when $k=p$?

It's a convention. One reason for the convention is that the length of an array $A[i..j]$ is $j-i+1$, so if $j=i-1$, we should get an array of length zero. Due to this reason, we sometime consider $A[i..j]$ to be undefined when $j < i-1$; in other cases, the issue does not arise, and $A[i..j]$ is just the empty array whenever $j < i$. In yet other cases, we do not want to allow empty arrays, and then $A[i..i-1]$ is undefined as well.

Since these conventions are not standard (indeed, they are conflicting), if one of them is used, it should be announced beforehand, or when it occurs.


Amortized analysis for disjoint sets' find-set(x) function (from CLRS)

The idea is actually quite simple. Just like in the book, let us assume that the find path consists of $s$ nodes. We disregard the root (because its potential doesn't change at all after the operation) and the node we upon which find_set is called (because it may have rank 0, which means its potential might not change). This leaves us with $s-2$ nodes.
Now, consider any node $z$ among the remaining $s-2$ nodes. As explained on pages 576-577 (I am using the 3rd edition), we have $0 \le \operatorname{level}(z) < \alpha(n)$. In other words, the level of $z$ must be between 0 and $\alpha(n) - 1$, inclusive. Indeed, it is the fact that we have
a finite number of options for the levels of the aforementioned $s-2$ nodes that will help us prove the assertion presented by the authors.
They say one example is worth a thousand words, so let's do one. Suppose we have 8 nodes between the root and the one upon which find_set was called. Suppose also that $\alpha(n)$ turns out to be $4$. Here's one possibility for the levels of the nodes, given in the order they appear in the find path:
$$ 2, 0, 1, 3, 2, 3, 1, 0 $$
The book claims that there are at most $\alpha(n)$ (4 in our case) nodes $x$ for which there doesn't exist a node y later in the path such that $\operatorname{level}(x) = \operatorname{level}(y)$. Take a good look at the sequence; you'll see that the claim holds for our example.
Now, the million dollar question. Why? Think about the last $\alpha(n)$ nodes. We could assign different levels to each one (as I have done for this example) so that none of them have a complementary node higher up the find path with the same level. However, that is the most we can have; every other node will now have some ancestor with the same level. Long story short, no matter how hard we try, we cannot have more than $\alpha(n)$ nodes without an ancestor of equal level; such a scenario would require more options for the level of a node than are available.
Put it all together, and it is evident that there exists another node with the same level down the line for at least $s - \alpha(n) - 2$ of the $s$ nodes, just like the book claims.
As for why the authors have found it unnecessary to provide an explanation for their claim, you are asking the wrong guy.


Generating all words of length $n$ avoiding $A^2$ and $B^3$

Instead of constructing a regular expression, it is better to construct a DFA, or rather, a DFA with some "missing transitions". The DFA has the following states:

$q_0$: initial state.
$q_A$: state after seeing one A.
$q_B$: state after seeing one B.
$q_{BB}$: state after seeing two Bs.

The transition function is
$$
\begin{array}{c|cccc}
& q_0 & q_A & q_B & q_{BB} \\\hline
q_0 & & A & B & \\
q_A & & & B & \\
q_B & & A & & B \\
q_{BB} & & A & &
\end{array}
$$
This is read as follows: when at row $q$, upon reading $\sigma$, move to the appropriate column, if any. If there is no appropriate column, we have reached the (invisible) sink state.

Using this, it is not hard to see that the number of words of length $n$ in your language is
$$
\begin{pmatrix}
1 & 0 & 0 & 0
\end{pmatrix}
\begin{pmatrix}
0 & 1 & 1 & 0 \\
0 & 0 & 1 & 0 \\
0 & 1 & 0 & 1 \\
0 & 1 & 0 & 0
\end{pmatrix}^n
\begin{pmatrix}
1 \\ 1 \\ 1 \\ 1
\end{pmatrix}.
$$
Calculation shows that for $n \geq 1$, the number of words of length $n$ in your language is
$$
\mathrm{round}(C \lambda^n), \text{where } C \approx 1.678735602594163 \text{ and } \lambda \approx 1.324717957244746.
$$
The eigenvalue $\lambda$ is also the unique real root of $x^3-x-1$.

A glance at the OEIS reveals that your sequence is A164001, and has the recurrence
$$
a_n =
\begin{cases}
n+1 & n \leq 3, \\
a_{n-2} + a_{n-3} & n \geq 4.
\end{cases}
$$
(The recurrence $a_n = a_{n-2} + a_{n-3}$ is of course related to the polynomial $x^3-x-1$ above.)


Why do we use $\Gamma$ to denote a TM's tape alphabet?

Following up on @PartialOrder's comment, while $\Gamma$ is not used in Chomsky & Schutzenberger or in Chomsky's 1962/1963 papers on PDAs, it is used in Ginsburg and Greibach 1966 as follows:

  A pushdown automaton (abbreviated pda) is a 7-tuple $M=(K,\Sigma,\Gamma, \delta, Z_0, q_0, F)$ where [...]

Here $K$ is the set of states and $q_0$ is the start state. $\Gamma$ is the finite nonempty set of auxiliary symbols. $F$ is the set of final states. $\Sigma$ is the finite nonempty set of inputs. Etc.

Nowadays we would call the set of states $Q$ if the start state is called $q_0$. I think this just indicates that not too much consistency and reason was required for these letter choices.

This is "original research" but I figure $\Gamma$ may just have been used since it is the first capital Greek letter (to indicate the same type as $\Sigma$) which looks distinctly greek (A and B looking Roman as well).


How to avoid getting stuck on local optimum, for genetic algorithms

It looks like you're dealing with premature convergence.

In other words, your population fills itself with individuals that represent the suboptimal solution and/or individuals that are (too) close to said solution.

The basic framework of a genetic algorithm is as follows:

P <- Population of size N with N random individuals.
evaluate fitness of all individuals in P
while (stopping criteria not met) {
    C <- empty Child set of size M
    while (size of C is not M) {
        parent1 <- select an individual from P
        parent2 <- select an individual from P

        child1, child2 <- combine parent1 and parent2 somehow.
        child1, child2 <- mutate children by chance
        evaluate fitness of child1, child2
        C <- C + child1 + child2
    }
    P <- combine P and C. (P remains size N)
}
return individual with best fitness

Note that the (e.g.) the size of the population/children doesn't have to be constant per se. Or you might combine a variable number of parents into a variable amount of children (e.g. a crossover between 5 parents resulting in 7 children). But I would keep it simple, at first.

As you can see, the main operators in a genetic algorithm are, in order

Selection: Select individuals from the population that will be combined. Examples: tournament selection, proportionate selection, truncation selection, ...
Crossover: Combine selected individuals (parents) to new indidivuals (children). Examples: one-point crossover, n-point crossover, uniform crossover, cut and splice, ...
Mutation: By chance, (don't) mutate an individual by changing the individual slightly.
Recombination: Somehow insert the children into the set of parents.
Examples: Add all children to the population, sort the thing by fitness and remove the worst individuals so your population is size N again; Sort your population and drop the worst M individuals and add all children; often the same techniques that are presented in the selection phase are used.

In your description, you're confusing multiple steps as if it were one (e.g. you skip the selection step but you incoorperate it in the crossover step). You also describe techniques as if it were a step of the algorithm (e.g. Elitism is a technique used in the recombination step to ensure that at least the best individuals don't die).

An example where premature convergence might/will occur is when you only select the best individuals as parents and only allow the best individuals survive (in the recombination step).

Some possible methods to resolve this:

Increase mutation rate. However, a mutation is usually a very random process. You would need 'pure' luck to escape the suboptimal solution.
Redesign your genetic operations. e.g. allow bad fitness individuals/offspring to survive the generation more frequently. It could be that you're currently selecting too much good individuals to survive. Don't let too much bad individuals survive though, or your algorithm will never converge to something good.
(...)

The goal is to tweek your genetic operations in such a way that in each next generation, the average fitness of your population has (preferably) increased while maintaining a big enough fitness variation. This is not easy.

There are several other methods to avoid premature convergence if the above doesn't help you out. I strongly recommend experimenting with altering your genetic operations first before doing this, however. Search terms: preselection, crowding, fitness sharing, incest prevention, ...


IEEE 754 addition wrong result floating point numbers

You forgot the implicit leading 1 in the mantissa. The mantissa is not 23 bits, it's 24 bits with a 1 as the leading bit.


I think your logic is valid, but not sound.
The problem is that the oracle $B$ is not what's in $BPP$. The question being asked about $B$ is what's in $BPP$.
When Scott Aaronson's paper "Quantum Lower Bound for Recursive Fourier Sampling" says

Green and Pruim [10] gave an oracle B for which $BQP \not\subset P^{NP}$. [...] while Green and Pruim’s problem is in BPP

the noun phrase "Green and Pruim’s problem" is not refering to $B$.
The Problem
The referenced paper "Relativized Separation of EQP from $P^{NP}$" defines a problem $L$.
The input to $L$ is a predicate $B$ and a range parameter $n$. The predicate $B$ accepts natural numbers between $2^n$ and  $2^{n+1}$, and returns either true or false for each. It is promised that $B$ will return true for either exactly $\frac{1}{4} 2^n$ of the allowed inputs, or else for exactly $\frac{3}{4} 2^n$ of them.
The output $L(B, n)$ is the classification of the relevant range of $B$ into the promised quarter-true or quarter-false categories.
The Separation
A $P^{NP}$ machine can't compute $L$ because $B$ has too many inputs to check. There's exponentially many spots to check (w.r.t. $n$), so eventually any accepting path must be leaving a huge proportion unchecked. An adversary can start with some arbitrary accepting input, simulate the proposed $P^{NP}$ machine to find out which inputs the machine checks on one path that accepts that input, then toggle inputs that that particular path didn't check to create a should-be-non-accepting input that fools the machine into accepting.
(Note: I implicitly assumed that $B$ could be inspected only by querying it. This fails e.g. if $B$ is provided as a circuit diagram. That's why $B$ will end up being our oracle.)
A $BPP$ machine can compute $L$ easily: just sample $B(x)$ at a random allowed $x$ and return that. The odds of getting it wrong are $\frac{1}{4}$, which is less than the typical-but-arbitrarily allowed $\frac{1}{3}$. You can sample more to make it more reliable.
A $BQP$ machine can also compute $L$, with the $BPP$ strategy.
An $EQP$ machine can use Grover's algorithm to solve $L$ with certainty. (Also works for BQP, but overkill.)
The Oracle
So we have a decision problem $L(B, n)$ that separates $P^{NP}$ and $BQP$, but relying crucially on the assumption that the machine is limited to querying $B$. Furthermore, we don't have enough input space to specify all of $B$'s outputs, and we can't use a compact representation like a program or circuit because that violates the only-querying-allowed assumption. Thus we're forced to cheat and give $B$ to the machine as an oracle.
This raises the issue of how to pick $B$. What if we picked a weak $B$, such as one where $L(B, n)$ is always $0$? Something that a $P^{NP}$ machine could be hardcoded into defeating? Fortunately we can get around that by choosing $B$ with diagonalization: iterate all $P^{NP}$ machines and use the $2^i$ to $2^{i+1}$ range of $B$ to defeat the $i$'th machine by the adversarial method I explained earlier.
Thus $B$ is an oracle that tells you something about how $P^{NP}$ machines try to query predicates, not an oracle about solving some problem in $BPP$. So it is not necessarily the case that $B \subset BPP$. It's probably not the case, actually, since computing a bounded version of $B$ involves simulating exponentially many $P^{NP}$ machines.


Proving that Pre(L) is regular using automatas: Should I prove that Pre(L) is the semantic of the new automata?

If you are unsure whether it is right, yes, you should prove it!  This is a good general principle. If you are unsure whether or why a particular step is correct, there's a good chance a reader will be unsure, too -- so prove it in more detail until there is no doubt.