How a 10GB network can copy 1TB data in 2 hours?

You have just done the calculation with the raw data to be transferred and not taken into account of the overhead of transferring data using networking protocols across any particular  network. Almost no networking technology transfers data without an overhead because there is the need for addressing the data, routing the data, dealing with the reliability of the network and so forth.
If we assume a layered packet-switching protocol network, such as the internet, we have many layers, each with its own overhead. Each overhead adds more bytes to the data to be transferred.
Physical Layer Overhead
 Datalink Layer Overhead
 Network Layer Overhead (IP)
 Transport Layer Overhead (TCP)
 Application Layer Overhead
 The file
 The data

Getting a large amount of data from one place to another reliabily on a packet-switching network has quite a large overhead.


how to defend against DOS caused by SYN cookies?

Computing syncookies requires taking a hash of the server and client's IPs and ports... These hashes may not be inexpensive esp if they are to be cryptographically secure. One way to DOS the syncookie code is to make so many requests that the CPU of the server is exhausted.  I believe that Linux uses a less expensive (and not cryptographically secure) hash function, so this is less of an issue.

You could probably also spoof sender IP and use syncookies to be sent to a victim. But that is not that useful/ interesting.


How does the number of clauses affect the difficulty of a 3-SAT problem?

In general, there is no connection. An instance with a "small" number (say a few thousands) of clauses can be very difficult to solve in practice, while an instance with a "large" number (say several millions) of clauses is easy. It's the structure that matters, not the number of clauses.

For random 3-SAT, you can have a look at the satisfiability threshold.


Algorithm to sort n numbers from 0 to $n^m$ in $\mathcal{O}(n)$? where m is a constant

The reason of your confusion is that the computational model under which the algorithm is run is not specified.

Assuming you are allowed to perform arithmetic in $\mathcal{O}(1)$ time$^*$, then the $\mathcal{O}(mn)$ bound is correct. The reason is that you don't need to explicitly make base conversions. Since radix sort only ever compares digits of numbers, it is sufficient to provide a way to compare arbitrary digits in $\mathcal{O}(1)$ time$^{**}$; it is not hard to convince yourself that given an integer $x$, the $i$-th digit from the right in the base $b$ representation of $x$ is exactly:

$\qquad x/b^{i-1} \ \% \ b$

where $\%$ is the modulo operator.

Under more stringent conditions on arithmetic (such as classical random access machines or constantly-bounded Word-RAMs), both taking the modulo and division by a constant are operations that take logarithmic time, changing the running time of radix sort accordingly.

$^*$ For example, with a Word-RAM model with $w \ge \log n$.

$^{**}$ Notice that this is consistent with practice. If you have any sense, you would set $b$ to be a power of two in an implementation.


In a Bayesian network, a variable is independent from all the variables given its Markov blanket (except of course the variables in the Markov blanket).

However, the Markov blanket is not the minimal set that renders two variables independent.

Also note that a variable may be independent of some variables in the Markov blanket, given another set of variables (think about the case of a spouse in the network).

By the way, I think that this problem has been solved already (if you refer to the problem of identifying the minimal set that renders two variables independent).

Edit: Check this out: http://www.cs.iastate.edu/~jtian/r254_min_separator.pdf
They show how to find a minimal d-separating set in a given Bayesian network.


A Myhill-Nerode type characterization of the regular languages using fooling sets?

Your conjecture is refuted by the language $\{ 0^n : \text{$n$ is not a power of $2$}\}$. Let $\{(x_i,y_i) : i \in \mathbb{N}\}$ be an infinite fooling set for this language. We can identify $x_i,y_i$ with integers. These pairs have to satisfy the following conditions:

$x_i + y_i$ is not a power of $2$.
For each $i \neq j$, either $x_i + y_j$ is a power of $2$ or $x_j + y_i$ is a power of $2$.

Color $\mathbb{N}^2$ with two colors according to whether $x_i + y_j$ is a power of $2$ or $x_j + y_i$ is a power of $2$, where $i < j$. Ramsey's theorem shows that without loss of generality we can assume that for all $i < j$, $x_i + y_j$ is a power of $2$.

If $x_i = x_j$ for $i < j$ then $x_j + y_j$ is a power of $2$, contradicting (1) above. Similarly, if $y_i = y_j$ for $i < j$ then $x_i + y_i$ is a power of $2$, contradicting (1) above. Thus all $x_i$ are distinct and all $y_j$ are distinct.

Assume without loss of generality that $x_1 < x_2$. Let $x_1 + y_3 = 2^a$ and $x_2 + y_3 = 2^b$. Choose $j$ so that $y_j > 2^b$. Let $x_1 + y_j = 2^c$. Then $2^c < x_2 + y_j < 2^c + 2^b < 2^{c+1}$, and we obtain a contradiction.


Why do we use several bits instead of a single bit for storage of objects in Bloom Filters

Consider Bloom filters in which $k$ hash functions are used. If we look up a value which is in the filter, then we always conclude that it is indeed in the filter. Things are more complicated when we look up a value which is not in the table; we could erroneously conclude that it were in the table.

Suppose the filter is of size $n$, and $m$ values were put into the table. So roughly $km$ positions are set to $1$. If we look up a value which was not put in the filter, then assuming that the hash locations corresponding to it are random, the probability that we erroneously conclude that it is in the filter is
$$ \left(\frac{km}{n}\right)^k. $$
The correct value of $k$ thus depends on the expected $m/n$. Suppose that $m = n/10$. Then we have the following error probabilities:
$$
\begin{array}{c|l}
k & \text{error probability} \\\hline
1 & 0.1 \\
2 & 0.04 \\
3 & 0.027 \\
4 & 0.0256 \\
5 & 0.03125
\end{array}
$$
So in this setting the error probability is minimized for $k = 4$. Since $k$ also effects the running time, we might as well choose $k = 3$ for these parameters, for which the error probability is almost as good.


Why do functions containing `await` need to be `async`?

The async annotation changes the way the body of the function is interpreted. Now you can clearly infer that if the body contains await, it must be async, but there are a couple of reasons why it makes sense to require an annotation.

The primary reason is, frankly, likely clarity. C# popularized this syntax and is a language that emphasizes declaring intent. My understanding (from vague recollections of blog posts) is that the C# designers view the fact that they didn't do a similar thing for generator syntax (i.e. yield) as a mistake or at least unpleasant compromise. Note that in JavaScript you do need to indicate a function is a "generator function" in much the same way as async. At any rate, both async/await and yield lead to dramatically different semantics, and you probably want to be clear that that is intended and understood. (A minor factor for C# was to make the await keyword contextual to avoid backwards compatibility issues.)

As a more technical reason, async and JavaScript's function* change the behavior of a function even if you don't use await/yield. In C#, an async method with no await will run synchronously, but it will still package up the result in a Task object. Similarly, in JavaScript, a generator function with no yield still returns an empty Iterable rather than undefined. If the async/function* aspect was inferred from usage of await/yield, then in these cases you would need to explicitly create a Task or Iterable. This isn't so bad in C# where the type system will require this, but in JavaScript there's a much greater chance for uncaught errors. Regardless, it's also bad for exploration since commenting out a line of code might dramatically change the behavior and type of the function.


How to show that the language made up of strings with nlogn 0s is not regular with the pumping lemma?

(Dense-length lemma for regular languages) Let $R$ be an regular language that has infinitely many words. Then there exists a number $d$ such that for any word in $R$, there is another word such that the difference of the lengths of both words is less than $d$.

The above lemma says, basically, the lengths of words in a regular language cannot be too sparse anywhere. It can be proved easily using the pumping lemma for regular languages.

Let us take a look at $L$. The lengths of its word are $\{n\lceil\log_2 n\rceil \,\mid n\in \Bbb{N}-\{0\}\}$. When $n$ goes larger and larger, the lengths become sparser and sparser because of the factor $\lceil\log_2n\rceil$. In fact, if $n>2^d$, $m>2^d$ and $n\not=m$, then $\left|n\lceil\log_2n\rceil-m\lceil\log_2m\rceil\right| > d$. So $L$ cannot be regular because of the above lemma.

Exercise 1. Prove the dense-length lemma for regular languages.

Exercise 2. Prove the dense-length lemma also holds for context-free languages that have infinitely many words.

Exercise 3. Does the dense-length lemma hold for context-sensitive languages?


Complexity of finding a perfect matching in directed graphs

You can find the maximum matching in all three cases in polynomial time.  It follows that it's possible to check whether there exists a perfect matching and, if so, to find one.

Finding a maximum matching in an undirected graph can be done in polynomial time.  It is not known (or likely) to be NP-hard.  See https://en.wikipedia.org/wiki/Matching_(graph_theory)#Algorithms_and_computational_complexity.

If you define the problem according to option 1, then finding a maximum matching in an undirected graph $G$ is equivalent to finding a perfect matching in the corresponding undirected graph (where you just ignore the edge directions) -- and thus can also be done in polynomial time.

If you use option 2, then the following algorithm can be used to find a maximum matching in polynomial time:

Given a directed graph $G=(V,E)$, construct a weighted undirected graph $G'=(V,E')$ with edge set defined as follows:

If $G$ has an edge $v \to w$ but not its reverse $w \to v$, add $(v,w)$ to $E'$ with weight 1.
If $G$ has an edge $v \to w$ and also its reverse $w \to v$, add $(v,w)$ to $E'$ with weight 2.

Find the maximum-weight matching in $G'$, i.e., the matching whose weight is maximized.
Now turn this into a set of edges in the original directed graph.  If this process selected an edge $(v,w)$ and $G$ contains both $v\to w$ and $w\to v$, add both to the matching in $G$.  If it selected an edge $(v,w)$ and $G$ contains only one of $v \to w$, $w\to v$ but not the other, add the one you can.

This runs in polynomial time and finds the maximum matching in $G$.

A simpler way to check whether $G$ has a perfect matching (i.e., one that covers all the vertices) is to construct the undirected graph $G'$ (you can ignore the weights) and check whether $G'$ has a perfect matching.


Use the pumping lemma to prove that the following language is not context free

Consider the following Context Free Grammar $G$:

$S \rightarrow aSdd\  |\ X\ |\ \epsilon$
$X \rightarrow bXc\ |\ \epsilon$

The language $L(G)$ generated by $G$ corresponds to the set of all the strings $\{\epsilon, add, aadddd, ..., bc, bbcc,..., abcdd, abbccdd,...\}$.
More generally, it corresponds to $ \{ a^{n}b^{m}c^{m}d^{2n} | n,m ≥ 0 \}$.


Show that,with the array representation for sorting an n-element heap, the leaves are the nodes indexed by n⌊n/2⌋+1,⌊n/2⌋+2,…,n

So, basically in heap representation, $LEFT(i)$ refers to the index of $i's$ left child. What we want to show is that index $⌊/2⌋+1$ is a leaf and is not a middleware node which can be proved if we could show the index of the left child is larger than the number of elements in the heap.

On the other hand, $LEFT(⌊/2⌋+1) = 2(⌊/2⌋+1) = 2⌊/2⌋+2 $ and with removing those brackets around the $n/2$ we can show that it is larger than $2(n/2-1)+2 = n$.


Decidability of languages with dfa/turing-machines

The easy and immediate way to see this is to note that the language of strings of length at most $k$ is finite, therefore it is regular. Regular languages are closed under complementation (just switch the accept and reject states), so your language of strings of length greater than $k$ is also regular.


Prove that a set A is semi-decidable if and only if there is a polynomial time relation R(x,y)

For $R(x,y)$, $x$ is where $M$ is a TM, $y$ is the accepting configuration of $M$. Is this a polynomial-time relation?

Yes that is the right idea. Except $y$ should be a sequence of configurations that starts in the initial configuration and ends in the accepting configuration.

To see why this works, we have to consider the running time of the TM that accepts $R(x, y)$. First the TM looks at the input $x$, and then it looks at the sequence of configurations $y$. The sequence of configurations looks something like a table:

Tape at time 0: x1 x2 x3 .... xn 0 0 0 0 0 .... 0
                ^HEAD, state q0
Tape at time 1: x1 x2 x3 .... xn 0 0 0 0 0 .... 0
                   ^HEAD, state q1
Tape at time 2: x1  1 x3 .... xn 0 0 0 0 0 .... 0
                       ^HEAD, state q2
...

and so on. So how does our TM check if this is in $R(x, y)$? We should check to make sure that the initial configuration has $x$ on the tape. How long will this take? And then we should check that $y$ is a valid sequence of configurations of according to the transition behavior of $M$. How long will that take? Finally, we need to check that the last configuration in $y$ is accepting. How long will that take?


Why isn't it necessary to store an integer part of significant in IEEE754 floating point notation?

There are two tricks used here.

The first trick is to realise that any number can be expressed with a single whole digit and a fractional part by modifying the exponent.

eg:

  = 435.32 * 10^3
  = 43.532 * 10^4
  = 4.3532 * 10^5

  = 0.00453 * 10^1
  =  0.0453 * 10^0
  =   0.453 * 10^-1
  =    4.53 * 10^-2

The second trick is to notice that this single whole digit is never zero. So when the number is expressed in binary (0, 1) that digit must always be 1.

Therefore if we mandate that the number is stored in binary, and the exponent is always adjusted to express the number as a single whole digit and a fractional part, the whole digit can be optimised away as it never varies. This leaves just the sign, exponent, and fractional parts of the number to encode.

That being said (as pointed out in the comments), the IEEE754 standard does include "denormalised" numbers which as you might guess do not have a leading implied 1, but are instead lead by an implied 0.

These numbers have the smallest possible exponent making these values truly tiny. The point of presuming a zero here is to allow the storage of even smaller values than could have otherwise been expressed.

Essentially it is a compromise, by altering the rule for the smallest possible exponent a series of even smaller numbers with reducing precision can be stored. The cost for this is that numbers at the 2^smallest-exponent cannot be accurately stored.


How to express time complexity when the exponential "e" comes into play?

It depends on whether you're talking about $O$ or $\Theta$. The notation $O$ indicates that the complexity is "this much or smaller", and the notation $\Theta$ indicates that the complexity is "this much, no more or less".

The complexity of $0.15 e^{0.05 n}$ is $\Theta(e^{0.05 n})$. The complexity is not $\Theta(e^n)$, because $e^n$ grows faster than $e^{0.05 n}$ does (the ratio between the two increases without bound).

It is, in fact, true that $0.15 e^{0.05 n}$ is an $O(e^n)$ function, but this isn't a good description of the complexity, in much the same way that "more than a thousand people live in China" is not a good description of the population of China.

What this comes down to is that you should state the complexity as $\Theta(e^{0.05 n})$ or as $O(e^{0.05 n})$.


Data structure for selection of K elements and taking sum

First, note that for any $a$, since XOR is associative:

$$(a \oplus b) \oplus b = a \oplus (b \oplus b)$$

Since $b \oplus b$ is $0$ and $0$ is neutral for XOR, we get that:

$$(a \oplus b) \oplus b = a \oplus (b \oplus b) = a \oplus 0 = a$$

In other words, there is no point performing XOR operation more than twice, for any $a$ with any $Q$. You can either XOR once, or not XOR at all (XOR twice)

Now, suppose you have an array $A$. Prepare the array $B$ as an array of the difference between $A$ before and after we XOR it:

$B_i = \max\{0, A_i \oplus Q - A_i\} $ (Since performing XOR on $A_i$ twice yields $A_i$, we can also choose $A_i$ itself).

Preparing $B$ takes $O(n)$.

Increasing the sum of $A$ is now equivalent to selecting the $Z$ XORS that their sum - difference is greatest, which is equivalent to selecting $Z$ max elements from $B$.

For that, there's a better solution than sorting ($O(n\log n)$):

Select the $Z-th$ largest element of $B$ using selection algorithm
Sweep $B$ and save any element that is larger than the $Z-th$ largest element

The indices of the elments chosen in $B$ determine both the elements of $A$ you select, and the XOR performed (or not performed). In total, it took $O(n)$ time.


Reducibility: Show that SUBSET SUM is reducible to the following problem A

You can consider the numbers $x_i$ as signed integers representing how much each person owes (if the number is positive) or how much each person needs to receive (if the number is negative). Then you have $\sum_{i=1}^n x_i = 0$ and the goal is to make all numbers $0$.
Notice that you can always settle debts with at most $n-1$ checks:
pick an $i$ such that $x_i>0$ and move $x_i$ from $i$ to an arbitrary $j \neq i$.
Delete $x_i$ (now $0$) from the instance. You are left with another instance of the same problem in which you need settle debts between $n-1$ people. Repeat recursively until you are left with only one person (in which cases no transactions are needed).
Suppose now that you can partition the set $\{x_1, \dots, x_n\}$ into two non-empty sets $S_1$ and $S_2$ such that $\sum_{x \in S_1} x =0$ (and hence $\sum_{x \in S_2} x = 0$). Then you can solve $S_1$ and $S_2$ separately using at most $|S_1|-1 + |S_2|-1 = n-2$ checks.
The converse is also true: if you can balance debts using at most $n-2$ checks, then you can partition $\{x_1, \dots, x_n\}$ into non-empty $S_1$ and $S_2$ with $\sum_{x \in S_1} x = \sum_{x \in S_2} x = 0$.
To see this, build the graph $G=(V,E)$ in which $V=\{1, \dots, n\}$ and there is an undirected edge $(i,j)$ if $i$ and $j$ exchange at least one check. Since $|E| \le n-2 = |V|-2$, the graph $G$ has at least $2$ connected component. If $C$ is a connected component then the sum of the integers $x_i$ such that $i \in C$ must be $0$. Let $S_1 = \{x_i \mid i \in C\}$ and $S_2 = \{x_1, \dots, x_n\} \setminus S_1$.
This shows that you can reduce the variant of partition in which the sum of the integers is $0$ (and you need to find a non-trivial partition) to your problem.
To see that this variant remains $\mathsf{NP}$-hard, consider an instance of partition $\{y_1, \dots, y_n\}$ in which each integer $y_i$ is positive, and add two additional integers $y'$ and $y''$ with $y'=y''= -\frac{1}{2}\sum_{i=1}^n y_i$.
Clearly, any non-trivial partition $A,B$ of $\{y', y'', y_1, \dots, y_n\}$ must place $y'$ in $A$ and $y''$ in $B$, or vice-versa, showing that the sum of the elements in $A \cap \{ y_1, \dots, y_n\}$ is $\frac{1}{2}\sum_{i=1}^n y_i$ (and the same holds for $B$). Conversely, given any partition $A,B$ of $\{y_1, \dots, y_n\}$, the partition $A \cup \{y'\}$, $B \cup \{y''\}$ is a solution to our variant.


The expression $10.\overline{1}$ should be interpreted as follows:
$$
1 \cdot 3^1 + 0 \cdot 3^0 + (-1) \cdot 3^{-1} = 3 - \frac{1}{3} = \frac{8}{3}.
$$
The interpretation of balanced base $b=2d+1$ is the same, with the digits ranging from $-d$ to $d$.


How to prove the language of Turing machines that run at most $4|x|^2$ steps is not recursive?

Preparation

Since we are talking about the exact number of steps run by a Turing machine (TM), a fixed formal definition of TM is in order. This answer assumes the popular definition of a one-tape Turing machine as in Hopcroft and Ullman (1979, p. 148).

Let $N(w) \downarrow$ denote $N$ on $w$ halts eventually. Let $N(w) \uparrow$ denote $N$ on $w$ never halts.

You have done the initial analysis correctly, pointing out a reasonable solution could be constructing a reduction $\overline{H_{\text{TM}}}\le_mL$. That is, for a TM $N$ and a word $w$, we should construct a Turing machine $M_{N,w}$ such that
 $$N(w) \uparrow\  \Leftrightarrow\  \langle M_{N,w}\rangle\in L.$$

For simpler notation, we will write $M$ to mean $M_{N,w}$.

Outline of the construction

Basically, we will let $M$ on input $x$ simulate $N$ on $w$ for $|x|$ steps. In case when $N$ on $w$ halts eventually, we will let $M$ run forever when the input is long enough.

Detailed explanation

The basic intuition is that $M$ will have to simulate $N$ on $w$ in some way since the only way to find whether $N$ on $w$ halts eventually is to run $N$ on $w$.

The first problem is the input to $M$ can be any word, which has probably nothing to do with $w$. On the other hand, how long $M$ may run depends on the length of the input.

Here is a simple approach. We will let $M$ compute how long the input is but ignore the actual content of the input otherwise. Moreover, $w$ will be encoded in the specification of $M$ so that $M$ will be able to put $w$ on the tape, which can be treated as the input to the simulated $N$.
The next problem is how to ensure $\langle M\rangle\in L$ if $N(w) \uparrow$. Assume $N(w)\uparrow$.

For short input, $M$ cannot be running too long for $\langle M\rangle$ to be in $L$.

The idea to prevent $M$ from running too long is simple. $M$ will halt once it has done reading the input if the input is not long. More specifically, let $M$ have state $s_0$, $s_1$, $\cdots$, $s_{t}$ for some $t$ where $s_0$ is the start state. When $M$ in state $s_i$ reads a cell, it halts if the cell means the end of input. Otherwise it advances to the next cell, updating its state to $s_{i+1}$. So, on every input $x$ of length at most $t$, $M$ will halt in $|x|+1$ steps, which is less than $4|x|^2$ steps.

Note that we can set $t$ to an arbitrary positive integer.

Also note that the action above will be performed regardless of whether the input is short or not, since $M$ doesn't know whether the input length is less than or equal to $t$ beforehand.
The next problem is how to prepare $M$ for simulating $N$ on $w$ once it has reached state $s_t$, which will happen if $|x|>t$.

$M$ should store the length of input while erasing the input. Here are the details.

First it goes back to the start of the input. We will refer this cell as $S$.
Write 0 to the left of $S$.
Switch direction to erase the first symbol of the input.
Switch direction to change 0 to 1.
Switch direction to erase the first symbol of the remaining input.
Switch direction to change 1 to 10, which is 2 in binary representation.
Switch direction to erase the first symbol of the remaining input.
Switch direction to change 10 to 11, which is 3 in binary representation.
And so on until $M$ passes the end of the input, at which time the non-blank symbols to the left of $S$ is the length of the original input in binary representation.
$M$ goes back to $S$. Switch direction to write $w$ on the tape. Switch direction to go to $S$.

All 10 items above can be done by $M$ in $c(x)<|x|^2+O(|x|)$ steps for input $x$. We can set $t$ to be large enough so that $c(x)+|x|+1<\frac32|x|^2$ for all input $x$ with $|x|\gt t$. The "$|x|+1$" at the left hand side of the inequality comes from the previous item.
How should $M$ simulate $N$ on $w$ as well as maintain the number to the left of $w$ on the tape so that $M$ will not be running too many steps?

Thanks to the number $|x|$ to the left of $w$ on the tape, we can let $M$ simulate $N$ on $u$ for $|u|$ steps and then halt. Note that at the end of item 2.2.10, $M$ should be in a state that corresponds to the start state of $N$. The head of $M$ is on the top of $S$, which is the first of the cells whose content is $w$. Now we let $M$ loop the following.

Read the current symbol.
If the current symbol is the last binary digit of that number, it means the simulated $N$ is supposed to read a blank symbol. So, let $M$ move all symbols to its right one cell to the right as well as setting $S$ to the blank symbol at last. Now $M$ should be on top of $S$, a blank symbol. Let $M$ read $S$, the (new) current symbol.
Simulate $N$ on the current symbol. Mark the (new) current symbol.
Move to the left of S. Decrease the number by 1.
If the number is 0, break the loop. Otherwise, go back to the marked symbol and start a new round of the loop.

This stage, stage 3 can be done in at most $\frac52|x|^2$ steps.

In summary, $M$ will run at most $4|x|^2$ steps regardless whether $|x|\le t$ or $|x|\gt t$, as long as $N(w)\uparrow$.
The last problem is how to ensure $\langle M\rangle\notin L$ if $N(w) \downarrow$.

$M$ must always be run as specified in item 2 above since $M$ does not know whether $N$ on $w$ will halt eventually or not beforehand. However, what $M$ should do is not specified at the moment when the simulated $N$ on $w$ halts. That will happen when the length of the input to $M$ is larger than the number of steps $N$ will have run before halting. Well, in that case, we will let $M$ just loop forever, which ensures that $\langle M\rangle\notin L$.

Exercises

Exercise 1. Explain that the reduction above can be algorithmic. In particular, the value of $t$ in item 2.2 can be determined algorithmically.

Exercise 2. Explain why $L_{2019}=\{M\mid M$ $\text{is a TM and for all}$ $x\in \Sigma^*$, $M\text{ on }x$ $\text{runs at most}$ $\max(2019,\dfrac{|x|^2}{2019})$ $\text{ steps}\}$ is also undecidable.

Exercise 3. Show that $\{\langle M\rangle\mid M$ $\text{is a TM that halts in }$ $O(n^2+1)\text{ steps where}$ $n$ $\text{ is the length}$ $\text{ of the input}\}$ is undecidable.


an algorithm linear according to Big-O notation reduces the size of the problem by a constant amount at each step

I don't think that's really true. It seems to me that all you're doing here is observing that a discrete linear function changes by a constant amount at each step and wondering if that's connected to the fact that the derivative of a continuous linear function is constant. That doesn't have much to do with what linear-time algorithms necessarily do.

Since algorithms are intrinsically discrete and calculus is intrinsically about continuous properties, I'm not aware of any real relationships between them. One might occasionally use calculus, e.g., to bound a sum by an integral or in tricks like
$$
\begin{align*}
\sum_{i=1}^k in^i &= \sum_{i=1}^k (i+1)n^i - \sum_{i=1}^k n^i\\
 &= \sum_{i=1}^k \frac{\mathrm{d}}{\mathrm{d}n}n^{i+1} - \sum_{i=1}^k n^i\\
 &= \frac{\mathrm{d}}{\mathrm{d}n}\sum_{i=1}^k n^{i+1} - \sum_{i=1}^k n^i\,,
\end{align*}$$
but I doubt that's the sort of application you had in mind.


Can the human brain be considered Turing complete?

Let's do this in order:

We do not say "another Turing complete language's algorithm" because "language's algorithm" is at best a confusing phrase. You might have meant "language's interpreter" but we cannot tell. It would be better to say "a programming language is Turing complete if it can emulate another Turing complete programming language". Note however that this is a circular condition, you need to get started somewhere. The place to start is Turing machine, of course. So: a language is Turing complete if it can be simulated by Turing machines and can simulate Turing machines. We would still have to precisely explain what "simulate" means here.
Languages such as C, C++ and Java are not "considered" Turing complete. They are Turing complete.
I deny that "all algorithms are by necessity formulated in our brains". For instance, a machine learning algorithm can come up with a new algorithm. Or perhaps an algorithm can be discovered by exhaustive search. Aliens could land and propose a new algorithm for sorting an array. Be that as it may, even if you are correct and all algorithm are formulated in our brains, your conclusion still does not follow. The following situation is in principle possible:

human brains are devices which spew out algorithms, i.e., they produce code to be executed, but
human brains are not capable of running such code

In the extreme case a human brain could be nothing but a device which mindlessly produces all possible algorithms. One can in fact build a machine which does this, but this machine would not be Turing complete.
Regarding a brain simulating a processor, I highly recommend that you read Turing's original paper, keeping in mind that in 1936 "a computer" was a person performing computations. Turing machines were designed to capture the mental abilities of humans performing calculations!
I take issue with your claim that a machine cannot simulate a brain. You have provided no evidence for this, and it seems in principle possible that a sufficiently powerful machine would simply simulate everything that is going on in a brain. It may seem complicated, but so far as we know, the laws of physics do not prevent this possibility.


Min-coin change problem with limited coins

Let $N(t,S)$ be the least number of values from $S$ which sum to $t$. The basic recurrence is
$$
N(t, S \cup \{s\}) = \min(N(t,S),N(t-s,S)+1).
$$
I'll let you work out the details.

This recurrence leads to an efficient algorithm only if we are allowed to run in time polynomial in $t$.

If we think of $t$ encoded in binary, then this algorithm runs in exponential time.

Indeed, the very related SUBSET-SUM problem is NP-complete.


Maximum number of matched vertexes in a one-to-many bipartite graph

Since your problem is exactly the set packing problem, it is NP-hard. However, you only have $n = 20$ bidders, so you can solve it using a simple exponential algorithm:

For every item $i$, build the subset $B_i$ of bidders that bid for it. You can represent this subset for example as a bitmask. You know that for all $i$, every subset $S \subset B_i$ with $|S| > 1$ can not be a subset of the solution.
For all $B_i$, enumerate all of its "forbidden" subsets of size > 1 and store them. Avoid revisiting already stored subsets by using recursion and memoization, by canceling the bits one after another.
Go through all subsets of bidders. For every set, check whether it has a a forbidden subset. You can use the same recursive algorithm as in step 2.

Note that if you only enumerate subsets of size 2 in step 2, you have reduced your problem to an independent set problem in a graph with $n$ nodes, so you can apply any other more efficient algorithm to it.

Runtime: $O(n \cdot (2^n + m))$, with $m$ being the number of items and $n$ being the number of bidders. With a good independent set algorithm you can get something like $O(m \cdot n^2 + 1.3^n)$


Determining the particular number in $O(n)$ time and space (worst case)

Here is an idea for a simple algorithm; just count all occurrences!

Find $m = \max A$. -- time $\Theta(n)$
"Allocate" array $C[0..m]$. -- time $O(1)$¹
Iterate over $A$ and increase $C[x]$ by one whenever you find $A[\_]=x$. If $C[x]$ was $0$, add $x$ to a linear list $L$. -- time $\Theta(n)$
Iterate over $L$ and find the element $x_e$ with $C[x_e]$ even. -- time $O(n)$.
Return $x_e$.

All in all, this gives you a linear-time algorithm which may use (in the sense of allocating) lots of memory. Note that being able to random-access $C$ in constant time independently of $m$ is crucial here.

An additional $O(n)$ bound on space is more difficult with this approach; I don't know of any dictionary data-structure that offers $O(1)$ time lookup. You can use hash-tables for which here are implementations with $O(1 + k/n)$ expected lookup time ($n$ the table's size, $k$ the number of stored elements) so you can get arbitrarily good with linear space -- in expectation. If all values in $A$ map to the same hash value, you are screwed.

On a RAM, this is implicitly done; all we need is the start position and maybe the end position.


Unclear logic notation for PFX program rules

The "fraction"-style notation is an inference rule in natural deduction style.  See What is this fraction-like "discrete mathematics"–style notation used for formal rules?.

$v_1,\dots,v_n\vdash \cdots$  means "in the environment $v_1,\dots,v_n$, such-and-such is true".  (It's not an "or", and it doesn't mean "implies".)  See What does ⊢ mean in operational semantics?.

I recommend finding a good textbook on programming language semantics, and reading it.  It will give you some background that will help you understand that notation.  It's probably too much to explain all of that in a single answer here.


Does weak consistency allow reordering of events?

Weak consistency rather appears in distributed systems where changes to variables have to be transmitted via the network.
Before a synchronization there is no guarantee to the visibility of write operations.
On P2 the W(x)1 could arrive before W(x)2 and on P2 W(x)2 could arrive before W(x)1.


NFA corresponding to the regular expression α = (a*b | ϵ) (b*(a | ϵ))

I think the inner pair of parentheses is out of place - without this pair of parentheses, we get the regular expression
$$\alpha=(a^*b|\epsilon)(b^*a|\epsilon),$$
which seems to satisfy $L(\alpha)=T(M)$... can anyone confirm this? (Sorry, I'm a beginner.)


Balance groups based on average, element constraints and size

This is a combinatorial optimization problem.  It is NP-hard (it is easy to see it is as hard as the partition problem).  Consequently, you should not expect any general problem that is efficient, scales to large problem sizes, and always returns the optimal answer.

Instead, you probably will want to use some kind of heuristics.  One approach worth considering is to use integer linear programming or some variant of it.  If your objective function is minimize the spread between largest group average and the smallest group average, then the problem can be encoded as an instance of integer linear programming (ILP) and then you could use an off-the-shelf ILP solver.  If your objective function is to minimize the standard deviation of the group averages, then the problem can be encoded as an instance of integer quadratic programming (MIQP) and then you could use a MIQP solver.  You might want to run them for a limited amount of time and use the best solution found within that time period, rather than run as long as needed to find the exact optimal solution.

The encoding of the problem as integer programming is tedious but fairly straightforward.  You introduce zero-or-one integer variables $x_{i,j}$, with the intended meaning that $x_{i,j}=1$ means that the $i$th item is assigned to the $j$th group.  (When you have multiple elements of the same color, treat them all as a single item with the same value of $i$; they just add more than one to the number of elements in that group.)  Then the number of elements in the group is a linear function of the $x$'s, and the group average of each group is a linear function of the $x$'s, so you can write down constraints for these to be a valid solution as linear inequalities.


(reference) Where can I learn more about I/O operations in OS?

It is pretty complex because there are several layers between the actual hard-disk and the software implementation of sockets. In today's x86 computers, the actual hard-disk is read using the Intel's AHCI controller which is a PCI device. All SATA plugs on your motherboard are directly connected to the AHCI. The AHCI will control the hard-disk and present a complex interface to software so that it can read/write to/from the hard-disk.
The best way to learn those things is to write an OS yourself. Get the basics of bootloading then write a minimal OS and this knowledge will come by itself over time. The MCFG ACPI table informs software of the address of the beginning of the PCI configuration space. Then you can scan PCI buses (more often only bus 0 for home computers). On bus 0 you can have up to 32 devices which can each have up to 8 functions. The function is what the device actually does. Each function of each device will have a configuration space which allows to get more information on the function. It will present class IDs and subclass IDs will allow to identify the different devices. As stated on osdev.org (https://wiki.osdev.org/AHCI).

An AHCI controller can be found by enumerating the PCI bus. It has a class id 0x01 (mass storage device) and normally a subclass id 0x06 (serial ATA). The vendor id and device id should also be checked to ensure it’s really an AHCI controller.

Once you found an AHCI on the PCI bus, you can look at the specification of the AHCI for implementing a driver: https://www.intel.com/content/www/us/en/io/serial-ata/serial-ata-ahci-spec-rev1-3-1.html. This spec really covers what you need to implement an AHCI driver.
Blocking versus non-blocking I/O is a software construct. Blocking I/O waits for the data buffer to be filed while non-blocking I/O will return immediately if there are no data ready. Non-blocking I/O expects you to call the read again so that you can get a full buffer. It isn't this complex for hard-disks while for network it is very complex. Basically, the AHCI is a DMA device (since it is PCI compliant and PCI devices are DMA in nature since they have access to RAM bypassing the CPU). I never implemented a driver for it but the AHCI will be triggered by a command and, once the command is completed, will trigger an interrupt on a certain vector using the MSI-X capability of PCI devices. The MSI-X capability allows to specify a vector to trigger on command completion.
I think this answer is a good starting point for you on what to read and what to do. I doubt there will be a good book on this matter for you to read. You should implement an AHCI driver and socket layer above this driver to really understand how it works under the hood. The socket layer is a POSIX specification that you can find on internet.


A hangman variation: determining a string by guessing substrings contained in it

This problem can be solved with O(n * s) queries, where n is the input length and s is the alphabet size. First, determine some single character substring by trying all possibilities. Then extend that into a length 2 substring by trying to append characters to it. Continue extending the string by appending until it's not possible anymore. If it's not possible to append anymore and the length is not n, do the same strategy but prepending. In this way you reach the length n substring in n steps that each take at most s queries.


DFA for a language that accepts the addition of multiple of 2 and multiple of 5

All natural numbers are expressible in the form $2x+5y$, except for $1,3$. You can check this directly, of use the solutino of the Frobenius problem for two denominations. Therefore another way to write your language (assuming the alphabet is $\{a\}$) is
$$
\overline{\{a,a^3\}}.
$$
You can construct a DFA for this language using 5 states, that count up to 4 and then saturate.

If you want to implement the constraint $2x+5y$ directly as an NFA (which is more economical for larger values of $2,5$), then you construct the following NFA:

States: $q_0,a_1,b_1,b_2,b_3,b_4$.
Initial state: $q_0$.
Final states: $\{q_0\}$.
Transition function:
$$
\begin{array}{c|cccccc}
q & q_0 & a_1 & b_1 & b_2 & b_3 & b_4 \\\hline
\delta(q,a) & a_1,b_1 & q_0 & b_2 & b_3 & b_4 & q_0
\end{array}
$$

In words, there is a 2-cycle and a 5-cycle sharing a vertex $q_0$, which is also the initial state and the unique final state.


Reduction from Independent Set with fixed vertex to Independent Set

As I understand, your problem is a decision problem defined as such:
Independant set with fixed vertex (ISFV):

Input: a graph $G = (V, E)$, a vertex $u \in V$, an integer $k$.
Question: is there an independent set of size $k$ containing $u$?

Independent set (IS) is defined as:

Input: a graph $G = (V, E)$, an integer $k$.
Question: is there an independent set of size $k$?

Suppose you can solve ISFV. Then you can solve IS by running ISFV for each $u\in V$ and checking if the answer is yes for any $u\in V$. Since there are a polynomial number of vertices, the reduction is indeed polynomial.
Another way to do it is to construct the graph $G' = (V\cup\{u\}, E)$ (adding a vertex with no other edge), and check ISFV with $G'$, $u$ and $k + 1$, since the vertex $u$ can always be added to an independent set.


Select the maximum number of links to satisfy per-link constraint. How to prove is NP-hard?

Even when each entry of G is in {0,1}, that is W[1]-hard by reduction from independent set:

$\mathbf{G}$  =  adjacency matrix + identity matrix    and    $\tau = 2$    and    $0 < \epsilon < 1/\hspace{.02 in}2$    .


Recurrence relation of the coin change problem

For that recurrence to make sense, $V$ can only be the array that contains the coin values; that is, $V=\{C_1, C_2, ..., C_m\}$.

Whenever confronted with a new dynamic programming problem, you should always try to understand how optimal solutions are structured in terms of optimal solutions for smaller subproblems (cf. optimal substructure). This will help you come up with the recurrence relation. Note that, in dynamic programming, you take the solution for one or more subproblems (initially, the base cases) and extend them, repeating this extension iteratively until, eventually, you reach the solution for the original problem.

In the coin change problem (using your notation) a subproblem is of the form solution[i][j], which means: you can make change for $j$ cents using the first $i$ coins from $V$. How have we arrived at this optimal solution (i.e., how have we extended a previously solved subproblem)? We may have brought one more coin from $V$ into the picture. How does this new coin extend the previous solution? Well, there are two possibilities: we have used this coin to make change or we haven't. We must add up these two cases (since both of them represent valid ways to make change):

Case 1 (the coin is not taken): when coin $i$ is not taken, the number of ways to make change for $j$ is exactly the same as it was before coin $i$ was even considered; that is, solution[i-1][j].
Case 2 (the coin is taken): when coin $i$ is taken, your are spending its value; therefore, you must substract the value $C_i$ to $j$. Now, the number of ways to make change is solution[i][j-v[i]] *.

The final recurrence is obtained by adding up these two cases:

solution[i][j] = solution[i-1][j] + solution[i][j-v[i]]

Observe that case 2 is not applicable when $j$ is smaller than the value of the $i$th coin (that is, when $j < C_i$), hence the distinction in the third and fourth lines of your recurrence.

Footnote:

* It will be v[i-1] if the array starts at index 0.


Difference between Time-sharing computers and computers which use Round Robin scheduling algorithm?

No, they are not equivalent, but you are right to note a similarity.

Yes, a time sharing computer is one in which the computer switches between different processes.  The schedular is the part of the operating system that determines when to switch between processes, and which process to switch to.   A round robin scheduler is one particular type of scheduling strategy that could be used in a time sharing computer, but there are other possible scheduling strategies as well.


What is shell expansion in programming language theory?

Shell languages and scripting languages have specific features adapted to the context of their use. Such features may not exists in that form in more classical programming languages as they would not be inappropriate for their context of use.

A shell language has to assist the user and make him productive in an interactive context, often for commands that are executed only once and then forgotten. Syntactic preprocessing of commands for common needs, use of abbreviation, and such, is part of the interactice help provided.

Programming languages must be often more explicit, more verbose and less context dependent, as they live long and have to be maintained, which requires them to be very readable by a variety of people. Hence, in the context of a programming language, these fonctionalities may be used, but have to be explicitly called as subprograms applied to the concerned data, rather than be implicit in the shell preprocessing of a command to be executed on the spot.


Prove that a and b commute if and only if they are powers of the same word

If $ab=ba$ then the word $w = ab$ satisfies $R^{|a|}(w) = w$, where $R$ is the right-rotation operator, and $R^{|a|}$ just applies this operator $a$ times. Since $R^{|w|}(w) = w$, Bezout's identity implies that $R^{(|a|,|w|)}(w) = w$, where $g = (|a|,|w|)$ is the greatest common divisor of $|a|$ and $|w|$. Since $g \mid |w|$, we see that $w = z^{|w|/g}$ for some word $z$ of length $g$. Since $g \mid |a|$, we see that $a = z^{|a|/g}$ and $b = z^{|b|/g}$.


Polynomial kernelization for Set Splitting

I understood the question as "select a subset of size $2k$ from $F$ such that (there exists coloring for $F$ $\iff$ there exists coloring for the subset)".
As you've said, you can remove all singleton and empty sets. The remaining sets have at least $2$ elements. You can show that any $2k$ such sets suffice.
Select $2k$ arbitrary sets with at least two elements. We assume that they have exactly $2$ elements (it's the worst case; the analysis is easy to modify for more than $2$ elements). We use the probabilistic method. For each element, we select the color randomly, and we compute the expected number of sets that have both colors.
We show that the expected number of sets with both colors is $k$. Note that this is an expectation over all random colorings. Therefore, there must exist a coloring that gives the value greater or equal to the expectation, i.e. $\ge k$, as required.
Let $\{S_i\}_{i=1}^{2k}$ be the selected sets.
For each set $S_i$ we introduce indicator variable $I_i$, which equals $1$ when the set $S_i$ has both colors, and $0$ otherwise.
The expectation above equals $\mathbb E[\sum_{i=1}^{2k} I_i] = \sum_{i=1}^{2k} \mathbb E[I_i]$.
For set $S_i = \{x_1, x_2\}$, with probability $\frac 12$, $x_1$ and $x_2$ have different colors. Therefore, $\mathbb E[I_i] = \frac 12$, and the required expectation is $2k \cdot \frac 12 = k$.


Let us start with a solution using $n$ processors and then we optimize the solution to use $O(n/\log n)$ of them.
Assume first that $n$ is a power of $2$, i.e. $2^k$ for some $k \in \mathbb{Z}$. Imagine a perfect binary tree where the leaves are the elements of the array. In each step we will process one level of the tree in a bottom up manner, where for each node in the tree we will compute the minimum of all elements contained in the leaves of its subtree and write this minimum in the node.

In the first step each node represent one element and hence is the minimum of it self. Now in each further step we go one level up in the tree, half of the processors retire and the other half, each will be responsible for one node. Note that the minimum of leaves in a subtree rooted at some node, is the minimum between the minimum of elements in its right subtree and the minimum of elements in its left subtree. Hence, a processor responsible for a node $M$, it only compares the numbers written on the left child and the right child of this node and write the minimum between them in this node.
When we reach the top of the tree, we will have exactly one processor that will compare the values written in both children of the root and write the minimum of them in the root.

Since the depth of a perfect binary tree of $2^k$ leaves is exactly $k$, the algorithm finishes in $\log n$ steps. Since we started with $n$ processors and the number of used processors kept cutting down, $n$ processors are enough for the whole job.

Now assuming $n$ is not a power of two, then there is a $k$ such that $n < 2^k < 2n$. Try to prove this claim as an exercise. Now using this claim, given an array of $n$ elements, we can use $2n$ processors to build an array of $2^k$ elements in constant time by adding very large numbers to the array (adding numbers equal to the first number of the array suffice since we are looking for the minimum) and run the algorithm as described above.

Now we optimize the number of processors using a preprocessing technique. Assuming we started with $c \cdot n/ \log n$ processors for some constant $c$ (2 is enough here). Let us start by completing the array into a power of two as above and cut the array into chunks, each of size $\log n$. We will have at most $O(n / \log n)$ of them. Each processor can find the minimum in a chunk sequentially in $O(\log n)$ time. Let us build a new array $A'$ of length $O(n / \log n)$, where the processor responsible for the $i$-th chunk writes the minimum in the $i$-th position of the array. We end up with an array of size $O(n / \log n)$ and with $c \cdot n / \log n$ processors we can proceed as above in $O(\log(n/\log n) = O(\log n)$ steps.

In total we get an algorithm with $O(\log n)$ time and $O(n / \log n)$ processors.


Intuitive way to understand "Run-Length Encoding"

"Run" doesn't mean "execution". It means "sequence of identical things", as in "the football team had a run of wins."

So the intuition is simply that it's more efficient to say "ten $a$'s" than "$aaaaaaaaaa$".


Is a finite Solomonoff learner worse than human learning?

Your suppositions are wrong.  A finite Solomonoff learner can learn the all-1's string.  There does exist a learning algorithm that can output a program for the all-1's string.

Consequently, this example does not demonstrate that Solomonoff learners are necessarily worse than a human being.  They might be; but this example doesn't prove that.

For instance, consider the following learning algorithm: if the inputs is all-1's, then output a program that only outputs 1's (e.g., 10001011 in your example), otherwise do something arbitrary.  This is a trivial algorithm, but it demonstrates that there does exist a learning algorithm that can learn that sequence.  In other words, you've given an example of an input sequence that both a human can learn and a finite Solomonoff learner can learn.

What you might have shown is that if we restrict the learner to a very limited amount of memory, then the learner might not be able to learn some things that a human can.  But that's a rather uninteresting conclusion.  Of course we know that if you severely restrict the memory of the computer, that limits what it can compute.  For instance, if we limit the memory of the algorithm to only 7 bits, then the algorithm must act like a finite-state machine with at most 128 states, which severely limits the patterns it can find.  A human can learn sequences that can't be recognized by a finite-state machine with 128 states.  That's not surprising, and doesn't really have any interesting implications for whether finite Solomonoff learners are worse than human learning.

There's no point in comparing a human to a computer algorithm that has been massively handicapped.  To make the comparison interesting, you must allow the computer algorithm to have reasonable access to the resources that any computer would have; otherwise you have trivialized the question.  This means allowing the computer learner a non-trivial amount of memory.  And once you do that, the learner no longer has any difficulties with your sequence.

There are other issues in your post.  If you are assuming that the only possible approach is to try all possible algorithms until you find one that works, that's not the case.  More seriously, the problem of "given a sequence, find the elegant program for it" is not computable, so if you require the learner to find the shortest possible program, you've created an impossible problem.  Finally, where you say that "According to Kolmogorov complexity, the length of the elegant program is independent of the Turing machine implementation.", but that's not correct.  What is true is that changing the universal Turing machine will change the length by only a constant... but if you care about constants, that might be important.


Are there improvements on Dana Angluin's algorithm for learning regular sets

In his answer  on cstheory.SE, Lev Reyzin directed me to Robert Schapire's thesis that improves the bound to $O(n^2 + n\log m)$ membership queries in section 5.4.5. The number of counterexample queries remains unchanged. The algorithm Schapire uses differs in what it does after a counterexample query.

Sketch of the improvement
At the highest level, Schapire forces $(S,E,T)$ from Angluin's algorithm to have the extra condition that for a closed $(S,E,T)$ and each $s_1, s_2 \in S$ if $s_1 \neq s_2$ then $row(s_1) \neq row(s_2)$. This guarantees that $|S| \leq n$ and also makes the consistency property of Angluin's algorithm trivial to satisfy. To ensure this, he has to handle the results of a counterexample differently.
Given a counterexample $z$, Angluin simply added $z$ and all its prefixes to $S$. Schapire does something more subtle by instead adding a single element $e$ to $E$. This new $e$ will make $(S,E,T)$ to be not closed in Angluin's sense and the update to get closure with introduce at least one new string to $S$ while keeping all rows distinct. The condition on $e$ is:
$$\exists s, s' \in S, a \in \Sigma \quad \text{s.t} \quad row(s) = row(s'a) \; \text{and} \; o(\delta(q_0,se)) \neq o(\delta(q_0,s'ae))$$
Where $o$ is the output function, $q_0$ is the initial state, and $\delta$ the update rule of the true 'unknown' DFA. In otherwords, $e$ must serve as a witness to distinguish the future of $s$ from $s'a$.
To figure out this $e$ from $z$ we do a binary search to figure out a substring $r_i$ such that $z = p_ir_i$ and $0 \leq |p_i| = i < |z|$ such that the behavior of our conjectured-machine differs based on one input character. In more detail, we let $s_i$ be the string corresponding to the state reached in our conjectured machine by following $p_i$. We use binary search (this is where the $\log m$ comes from) to find an $k$ such that $o(\delta(q_0,s_kr_k)) \neq o(\delta(q_0,s_{k+1}r_{k+1})$. In other words, $r_{k+1}$ distinguishes two states that our conjectured machines finds equivalent and thus satisfies the condition on $e$, so we add it to $E$.


Lazily computing a random permutation of the positive integers

Yes.  Use a block cipher with a small block size.  This is extremely efficient and requires extremely little state.

A block cipher is a map $E : K \times X \to X$ such that, for every $k \in K$, $E(k,\cdot)$ is a permutation on $X$ (a bijective function $X\to X$).  Moreover, if $k$ is chosen uniformly at random, then $E(k,\cdot)$ acts in a way that is computationally indistinguishable from a function chosen uniformly at random from all permutations on $X$.

Thus, a simple solution is to let $X$ be the set of possible values of an unsigned integer, e.g., $X=\{0,1,2,\dots,2^{64}-1\}$, let $x$ denote a counter ($x \in X$) and $k$ a random key.  The state of your pseudorandom generator is $x$ and $k$.  When you want a new random number, you output $E(k,x)$ and then increment $x$.  This requires very little memory, is extremely efficient, and is provably good (if the block cipher is secure, which is a reasonable assumption given the state of modern cryptography).

You can find information on how to build a block cipher with a small block size here:

Format Preserving Encryption (on Wikipedia)
Can you create a strong blockcipher with small blocksize, given a strong blockcipher of conventional blocksize? (on crypto.SE)
Is it possible to generate a secure permutation F over 32-bit integers even if F(0) … F(n) is public knowledge? (on crypto.SE)
Can I create a fixed length output from a fixed length input? (on crypto.SE)


Syntax of a Pushdown Automata transition function

The rule, in English, can be rendered roughly as follows:

  If the machine is in state $q$, and $S$ is the topmost stack symbol, the machine may do either of the following things without consuming any input: it may remain in state $q$ and replace $S$ with $aaB$; or it may remain in $q$ and replace $S$ with $bbA$.

A good way to think about PDAs and transitions is to reason about configurations. The configuration of a PDA consists of the following information: the state, the unread input, and the contents of the stack. Indeed, this makes the transition function (almost) a (partial) function from configurations to (sets of) configurations.

$q$ is the state;
$\lambda$ is used to indicate that the current symbol may be input symbol, and that the input should not be reduced as it normally would after a transition;
$S$ gives the topmost stack symbol, which is the only part of the stack contents the PDA can see.


What happens when time slices are too short or too long?

A context switch between two tasks takes a certain amount of time. Let's say that there are two runnable tasks on a particular system. Each context switch will take about the same time, say 0.1ms. If there is a context switch every 10ms, then each task is left to run for 9.9ms, then out of every 1ms period, 99% is spent running the tasks and 1% is spent in context switches. If we increase the frequency of context switching to be every 1ms, then context switches waste 10% of the time. In the extreme case, if we increase again to have a context switch every 0.1ms, then the whole processor time is spent in context switches, there is no time left to run the applications.

Thus, for performance, it is best to have context switches as rarely as possible. This increases the time that is available to actually run applications. However, if context switches are too rare, then there is a delay before an application can react to an external event. This is not a problem for a purely computational program, but it is a problem for a program that does input/output. For example, the frequency of context switches is only once per second, then computational tasks don't waste time, but a network server may take up to one second to reply (or more if there are more than two tasks), an interactive program may take up to one second to react to a keypress, etc.

Thus the operating system scheduler must find a balance between computational performance and reactivity. Sophisticated schedulers try to find out which tasks are computational and which ones are I/O-bound, and give I/O-bound tasks shorter but more frequent time slices and give computational tasks longer but less frequent time slices.


Assuming n and k to be non-negative,
$n\leq n+k$ and $k\leq n+k$. Hence,$\max(n, k) \in \mathcal{O}(n+k)$.
Next, $n+k≤2\max(n,k)$. Hence, $\max(n,k)\in\mathcal{\Omega}(n+k)$.
Hence, we get that $\max(n,k)\in \mathcal{\Theta}(n+k)$.


Mistake in Karp's paper on NP-Complete problems?

To cite the blog post:

  For arguments sake, lets say that in Karp's classic paper Reducibility Among Combinatorial Problems, where he proves 21 problems NP-compete, he made a mistake on 0-1 programming.

That is, the blog author does not state that there is a mistake. It is just a gedankenexperiment.

That is, of course, not to say that there is none.


Given 5 curves, find the maximum total you can get for each possible level

It's easy to achieve $O(n^4)$ running time: iterate over all possible values of $a,b,c,d$, set $e=n-a-b-c-d$, compute $C_a+C_b+C_c+C_d+C_e$, and keep the best one found so far.

You can achieve $O(n^3)$ running time and $O(n^2)$ space with a meet-in-the-middle algorithm:

Step 1. Create an empty hash table.  For each $d,e$ such that $d+e\le n$, add an entry to a hash table keyed on $d+e$ mapping to the value $C_d+C_e$; if it already has an entry for the key $d+e$, replace the existing entry if $C_d+C_e$ is larger than whatever was previously there, otherwise do nothing.  (Save the value of $d,e$ whenever you update the entry, too.)

Step 2. For each combination $a,b,c$ such that $a+b+c \le n$, look up the key $n-a-b-c$ in the hash table.  This gives you $d,e$ that maximizes $C_d+C_e$, subject to the requirement that $d+e=n-a-b-c$, i.e., that $a+b+c+d+e=n$.  Now compute $C_a+C_b+C_c+C_d+C_e$.  Keep the best combination you ever see.

You can achieve $O(n^2)$ time and space by keeping Step 1 above and replacing Step 2 with

Step 2'.  For each combination $a,r,s$ such that $a+r+s=n$, look up the key $r$ in the hash table to find $b,c$ such that $b+c=r$ and look up the key $s$ in the hash table to find $d,e$ such that $d+e=s$.  Compute $C_a+C_b+C_c+C_d+C_e$ and keep the best combination you ever see.  You can iterate over all such combinations $a,r,s$ by iterating over $a,r$ such that $a+r \le n$, then setting $s=n-a-r$.  There are $O(n^2)$ such combinations of $a,r,s$, and this algorithm does $O(1)$ work per combination, so the total running time is $O(n^2)$.


What would be the classification of R according to paradigms?

Scripting language

I once heard the following definition of what a scripting language as at some conference. Namely, if its main purpose is to orchestrate components that exist in their own rights outside of the language. Consider a theatre script - it orchestrates actors who all exist independently of the script. Bash scripts and batch files (the latter article even has a section entitled "Other Windows scripting languages") are prototypical representatives of a scripting language according to the given definition, because they are completely useless if you couldn't invoke external tools or commands like grep, ls or cd.

The most important part of this definition is the "to orchestrate components that exist in their own rights outside of the language" bit. At the end of the day, all computer languages (no coined term AFAIK) allow you to orchestrate components, thereby creating more new and complex components. However, in a programming language you mainly orchestrate library functions that only exist because the programming language exist.

Having said that, I would consider R a multi-paradigm programming language, where multi-paradigm includes at least the procedural paradigm and object-oriented paradigm.

Imperative paradigm

As a last remark: imperative programming includes both aforementioned paradigms and is different from declarative programming. An imperative language focuses on the "how to do things" and consists of more or less directly executable steps, whereas a declarative language focuses on the "what to achieve". As an example, consider sorting a list. An imperative program what consists of a procedure/method that moves elements around and thereby sorts the list, and each single instruction can be executed in a sort of obvious way. A declarative program would consist of a description of the property "sorted", but how to "execute" the property is not at all obvious. If you are interested in the differences, have a look at Quicksort implemented in Java and Prolog (among others).

What Wikipedia says

Addressing a comment by @vonbrand and in support of my reply to that comment, here are a couple of quotes from Wikipedia:

The first line in the article on Perl describes Perl as a

  Perl is a high-level, general-purpose, interpreted, dynamic
  programming language.

but in the second paragraph you find

  Perl was originally developed by Larry Wall in 1987 as a
  general-purpose Unix scripting language to make report processing
  easier.

It is similar for Python, where the first paragraph is

  Python is a general-purpose, interpreted high-level programming
  language whose design philosophy emphasizes code readability. Its
  syntax is said to be clear and expressive. Python has a large and
  comprehensive standard library.

In the second paragraph you'll find

  Like other dynamic languages, Python is often used as a scripting
  language, but is also used in a wide range of non-scripting contexts.

which, I think, supports my comment given below quite nicely.

Furthermore, the article about scripting languages defines

  A scripting language or script language is a programming language that
  supports the writing of scripts, programs written for a software
  environment that automate the execution of tasks which could
  alternatively be executed one-by-one by a human operator.

and then goes on as follows, where the first sentence is, in my opinion, the most important one

  Scripting is usually a property of the primary implementations of a
  language, rather than a language per se, although many languages are
  not very suited to this kind of implementation. For example, C++
  interpreters do exist, but C++ is generally not considered a scripting
  language for two reasons: these implementations are rarely used, and
  the time required to write program in C++ would be far greater than
  the time required to write an equivalent script in a language like
  Python.


Scheduling algorithm with defined starting intervals and processing times

For this particular problem, you have an evident solution. If you work only in seconds, you have GCD(5min, 8min) = 60s. Moreover the sum of the required times of opening is $3\times 5 + 3 \times 10 = 45 s$.

Thus, you can assign to each valve an offset in the 60s period without any risk of collision. Then, you can decide independently for each valve for each 60s period if you actually use the assigned slot or not. That is to say one every 5 periods for valves 1, 2, 3 and every 8 periods for valves 4, 5, 6.


Bob has to find Alices hidden gold by questioning yes/no questions

Consider any strategy for Bob. For each item $v_i$, let $x_i$ be binary string composed of the answers that Alice gives to all questions (0 is No, 1 is Yes). You can check that $x_i$ is a prefix code. If $p_i$ is the probability of item $v_i$, then the optimal strategy is the one that minimizes
$$ \sum_i p_i |x_i| $$
over all prefix codes $x_i$ (every prefix code can be translated back to a strategy).

Huffman gave an algorithm which finds the best strategy. The cost $T(V)$ of this strategy satisfies
$$ H(V) \leq T(V) < H(V) + 1. $$
If all $p_i$ are of the form $1/2^j$, then $T(V) = H(V)$, and otherwise $T(V) > H(V)$.

Huffman's strategy is "bottom-up", whereas the strategy that you describe is "top-down". It is not optimal in general, but (if you implement halving properly) it is guaranteed to have cost at most $T(V) + 1$, even with an arbitrary ordering of the weights.

(Since you haven't described your halving strategy, I cannot describe an example in which Huffman coding beats your strategy.)

While prefix codes cannot in general reach the entropy exactly, they do reach the entropy in the limit when solving many instances at once. That is, suppose that Alice is actually hiding $N$ items, each chosen according to $V$. Huffman's algorithm produces a strategy whose cost per item is less than $H(V) + 1/N$. In the limit $N\to\infty$, you do get $H(V)$.


Inference and Unification algorithm provided to a Unification graph of two expressions

Yes, your solution and process are correct, assuming that alpha and beta are variables. It might help to rewrite your terms in a more uniform way, e.g.

T1 = *(list(int), list(alpha))
T2 = *(alpha, beta)

Here, a term always satisfies the grammar:

Term ::= Constant
       | Variable
       | Func "(" Term+ ")"

Furthermore, it might clarify things to think of the unification process as taking a third argument: a substitution in which the two terms are to be unified. This substitution is simply an association between variables and terms, and it provides a context in which to resolve variables. Additionally, the unification process results in either a failure (if the terms do not unify in the substitution), or a substitution which both indicates success and provides a way to construct a "most general unifier".


What is the asymptotic bound for $1n + 2(n-1) + 3(n-2) + ... + (n-1)2 + n$?

We can lower bound the sum roughly by
$$
\sum_{i=1}^n i(n+1-i) \geq \sum_{i=n/3}^{2n/3} (n/3)^2 \geq (n/3)^3.
$$
This shows that it is $\Omega(n^3)$. Since each summand is at most $n^2$, the sum is also $O(n^3)$.

We can also compute the sum explicitly:
$$
\sum_{i=1}^n i(n+1-i) = (n+1) \sum_{i=1}^n i - \sum_{i=1}^n i^2 = (n+1) \frac{(n+1)n}{2} - \frac{n(n+1)(2n+1)}{6} = \frac{n(n+1)(n+2)}{6}.
$$
This expression equals the binomial coefficient $\binom{n+2}{3}$, and we can prove this bijectively. The binomial coefficient counts triples $(a,b,c)$ of elements satisfying $0 \leq a < b < c \leq n+1$. Notice that $1 \leq b \leq n$, and this corresponds to summation over $i$. Given $b$, we have $b$ choices for $a$ and $n+1-b$ choices for $c$.


Acceptance of empty string by nondeterministic automaton

You're confusing the concept of the empty string $\varepsilon$ with the concept of an $\varepsilon$-transition.

The empty string $\varepsilon$ is just the string with no characters.  The presence of a $b$-transition from $q_1$ to $q_2$ means that the automaton can move between those two states by reading character $b$ but the presence of an $\varepsilon$-transition from $q_1$ to $q_3$ doesn't mean that it moves by reading the character $\varepsilon$. Rather, it means that the automaton can (but is not forced to) move from $q_1$ to $q_3$ without reading any input at all.

So, when this automaton has no input, it can either remain in state $q_1$, which is accepting, or move to $q_3$, which isn't.  Since it can reach an accepting state, it accepts.


Huffman tree generation if the frequency is same for all words

Yes. When creating a Huffman tree, if you ever find you need to select from a set of objects with the same frequencies, then just select objects from the set at random - it will have no effect on the effectiveness of the algorithm.

Of course, one might question why you're bothering to build a Huffman tree if you know all the frequencies are the same - I can tell you what the optimal encoding is.


How to generate tree variants of a tree using recursion?

The outline is: You start the function-call at the root vertex. For every child-vertex, you find all permutations of its sub-tree. Then you you find all combinations of these permuations of the children's sub-trees, and for each of them do all permutations of the child-vertices themselves.
The recursion happens where you need the permutations of the sub-trees of the children.
The exit-condition is the call on a leaf.

Set<Tree> perm(vertex x):
    if x is leaf:
        return x
    Let C be the set of all children of x.
    Set<Tree> result <- emptySet
    For all different combinations of perm(c) from the vertices c of C, now called comb:
        For all permutations p of C:
            add to result the graph you get with comb and p.
    return result


Maximum Independent Set of special Directed Graph

The type of graph you are describing is identical to the one encountered in Pollard's rho algorithm. Connected components of your graph are cycles with directed trees feeding into them (possibly none). It follows that it suffices to solve your problem for such graphs.
The first step is to compute, for each directed tree, the maximum size of an independent set, depending on whether the root is included or not. Denote the maximum size of an independent set in the first case by $\alpha_+(T)$, and in the second case by $\alpha_-(T)$, and let $\alpha(T) = \max(\alpha_+(T),\alpha_-(T))$. If $T$ is a single vertex then $\alpha_+(T) = 1$ and $\alpha_-(T) = 0$. If $T$ is composed of a root and subtrees $T_1,\ldots,T_d$, then $\alpha_+(T) = \alpha_-(T_1) + \cdots + \alpha_-(T_d) + 1$, and $\alpha_-(T) = \alpha(T_1) + \cdots + \alpha(T_d)$.
Now suppose that we have a cycle of length $\ell$, and let $T_1,\ldots,T_\ell$ be the directed trees whose roots are the vertices of the cycle (the trees could be single vertices). Let $\alpha_{\pm_1,\pm_2,i}$ be the maximum size of an independent set in $T_1,\ldots,T_i$ which contains the root of $T_1$ according to the first $\pm$, the root of $T_i$ according to the second $\pm$, and which doesn't contain two adjacent roots. First, $\alpha_{\pm,\pm,1} = \alpha_\pm(T_1)$, and $\alpha_{\pm,\mp,1} = 0$. Second, $\alpha_{\pm,+,i+1} = \alpha_{\pm,-,i} + \alpha_+(T_{i+1})$ and $\alpha_{\pm,-,i+1} = \max(\alpha_{\pm,+,i},\alpha_{\pm,-,i}) + \alpha_-(T_{i+1})$. Finally, the maximum size of an independent set of the entire component is $\max(\alpha_{+,-,\ell},\alpha_{-,+,\ell},\alpha_{-,-,\ell})$.


What other than programming does a computer science degree usually involve?

A computer science education, among answering a lot of "how?" questions, also covers areas whose purpose is to answer most of the "why?" questions. Those are, in my opinion, the most important, mind-opening and motivating for a future computer scientist with a programming background:

Logic
Computer Architecture
Computability
Complexity
Machine Learning and Artificial Intelligence (which are very closely related and are a part of applied math, which you mentioned. These are of great importance on today's market)

see comments for more examples.

Those will give your programming skills a major boost, enrich you with deeper understanding of what's behind the lines of code and thus give you a great advantage when applying for a future job in this area.

Should you study computer science if you are now interested only in programming? I think absolutely yes. You will not lack programming courses for sure, so that's a plus already. Also, you will learn many more interesting things about programming that maybe you haven't yet encountered to figure out that you are interested in them.


Solving the graph colourability problem in polynomial time if the equivallent decision problem is in $P$

Hint: If there is a valid coloring in which vertices $x,y$ get the same color then the graph resulting from merging $x,y$ into a single vertex has the same chromatic number. Otherwise, you can add an edge between them (if it doesn't already exist). Either way, the graph "simplifies" (either the number of vertices decreases, or the graph gets closer to a clique).


How does a dual core microprocessors run so many programs?

It's great that you're curious. A simplified explanation follows with a few links to delve into:

All of the programs running in parallel is actually an illusion that is created by the OS.

Even if we have a uniprocessor system, the OS can still achieve the same thing.
For multiple programs running on the system, OS creates separate processes.
Separate processes could then time-share the processor(s) available.

Since a processor is very fast (gauged by frequency), it can switch back and forth among multiple processes that may be active in a particular time period (we're talking about the span of time in microseconds/milliseconds). Overall, this gives the user an illusion that the programs are running in parallel. This technique is called Multi-tasking.

Now, adding more processors(let's say one in your case) allows the OS to also use the processors in parallel. In this case, let's say the OS chooses to run half of the programs on one processor and the other half on another processor (in reality, it's a little more complex). Individual processors are still used by the running processes in a time-sharing fashion but since there are two processors, overall the performance of your running programs improve. Using multiple processors in parallel is called Multi-processing.

Although the definitions can be a little confusing, this overall implementation idea remains the same.


How to show a language is regular through creating DFA

As with any automaton, the states need to encode all the information you need to decide whether or not to accept the string you've read so far. In this case, that means that number of $0$s and $1$s that you've seen. Except you can't quite do that, because that would require infinitely many states. However, if you look more closely at the definition of the language, you'll see that you don't need to know the exact number of $0$s and $1$s: for example, if you've seen six $1$s, that's the same as seeing seven, or a million.

Once you've worked out what the states are, work out what the transitions between them are. You'll find that you have a trap state, without needing to figure out what it should have been. Trap states occur "naturally", whenever you've seen enough of the input to be able to say, "I don't care what else I see: I'm rejecting this string!"


Chomsky hierarchy is primarily a hierarchy of grammars, not of
languages. As stated in Wikipedia:

  The Chomsky hierarchy (occasionally referred to as
    Chomsky-Schützenberger hierarchy) is a containment hierarchy of
    classes of formal grammars.

Type 3 grammars are characterized by the fact that they have to have
only left linear rules (i.e., productions), or only right linear rules,
plus possibly an empty rule for the initial non-terminal symbol. For
any language, both forms exist.

A rule is left linear iff its right hand side (RHS) is composed of a
terminal symbol, possibly preceded by a single non-terminal.

A rule is right linear iff its right hand side (RHS) is composed of a
terminal symbol, possibly followed by a single non-terminal.

(There are small variants of these definitions, allowing for a
terminal string of any length, instead of a single terminal)

When the language is not finite, some of the rules are necessarily
recursive. But a left linear rules that is recursive is necessarily
left recursive. Hence the grammar is not LL(1).

Hence some type 3 grammars, even with the strict definition above, are
not LL(1).


Estimating size of state space search problem

So lets take an 8 queens problem. Intially the size of state is 64C8 where 64 is the number of squares in a chess board and 8 is the number of queens that can be placed.
Now lets say, you can only put one queen in each column so that's only 8 squares available. This reduces the branching factor from 64 to 8. Now the size of state is 8C8 only.
Now lets say, you can only use 2 queens instead of 8. This reduced the depth from 8 to 2. So in this case instead of being 8 queens , now it's going to be a 2 queens problem. So that changes the size of state from 8C8 to 8C2. Cheers man.


Hardness
The problem is strongly $NP$-hard so there likely is no fast algorithm solving it.
Consider the 3-Partition problem wherein we are given $3n$ distinct integers $x_1,\ldots, x_{3n}$ and an integer $T$ such that $T/4< x_i< T/2$ and asked to decide whether we can group the $3n$ integers into $n$ groups of $3$ integers with sum equal to $T$ for each triple.
We create an instance of the problem with $4n$ tasks, $3n$ of those tasks having length $x_i$ (one for each $1\leq i\leq 3n$) and $n$ tasks having length $T$.
There exists a solution with no idle time if and only if the 3-Partition instance is solvable. Clearly, if there is a solution to the 3-Partition instance there is a solution to the task planning instance: just have the helper do the length $T$ tasks and have us handle the other tasks in groups of 3 (each with length exactly equal to $T$).
Conversely, in any solution with no idle time, the helper cannot do any task of length less than $T$. If we start the helper on some task with length less than $T$ (i.e., some length $T/4< x_i< T/2$), we must find tasks to do ourselves with length exactly equal to $x_i$. However, no task other than $i$ itself has length $x_i$ (since all the integers $x_i$ are distinct) and for any two integers $x_j,x_k$, $x_j+x_k > T/2 > x_i$.
Thus, in any solution with no idle time, all the tasks done by the helper are of length $T$. The tasks we do ourselves during each task done by the helper must then form a solution to the 3-Partition instance.
Heuristic/approximation
Clearly the idle time cannot be approximated (since it is already hard to decide whether it is non-zero). There is however an EPTAS for the makespan.
Consider the algorithm that always assigns the longest job to the helper, and then fills out the schedule of the master by considering jobs in order of decreasing length and assigning each job that still fits (so that the length of master's schedule does not exceed that of the helper). Repeat this process with the remaining jobs untill all are scheduled. We call a single job done by the helper together with a set of jobs done by the master a "round".
This yields a solution with idle time of at most $L_\textrm{max}$ where $L_\textrm{max}$ denotes the length of the longest job. To see this, note that if during a round the master is idle for $\epsilon$ units of time, $L_\textrm{max}$ decreases (in the set of remaining jobs) by at least $\epsilon$: if there was a job longer than $L_\textrm{max}-\epsilon$ the master would have done that job and obtained a shorter idle time.
Suppose that the sum of all job lengths is $1$ and let $\epsilon < 1$. If $L_\textrm{max}\leq \epsilon$, the above procedure returns a $1+2\epsilon$-approximation (since the optimal solution has makespan $\geq 1/2$). Otherwise, consider the jobs with length $\geq \epsilon$ of which there are at most $1/{\epsilon}$ (long jobs). Consider also the jobs with $\epsilon <$ length $\geq \epsilon^2$ of which there are at most $1/{\epsilon^2}$ (medium jobs). The remaining jobs (with length $<\epsilon^2$) are called short.
We now, by brute force, enumerate all schedules with the following properties: all long jobs are scheduled, and possibly some medium jobs are scheduled and every round contains at least one long job. For each such schedule, we greedily fill any idle time the master may have with short jobs (so that the master does not work longer than the helper in any round). This is the first phase schdule. We then schedule the remaining short/medium jobs according to the previous greedy algorithm. This is the second phase schedule.
The idle time in the second phase is at most $\epsilon$ (since $L_\textrm{max}< \epsilon$). We now need to bound the additional idle time (over that in an optimal solution) in the first phase.
Take an optimal schedule. If the helper does a short job while the master does a long one, swap the jobs done by the helper and the master -- this does not change the makespan. Delete all short jobs from the schedule and all rounds containing only short/medium jobs. Assume the solution obtained by our approximation algorithm is based on this (modified) schedule, which will be part of the brute force enumeration (so our approximate solution will be at least as good as one obtained from this schedule).
If there are no short jobs in the second phase, then it is easy: We know that the medium jobs scheduled in the second phase do not need to be scheduled together with any long job in an optimal solution. In an optimal case they would be scheduled with at most zero idle time, and the greedy algorithm adds at most $2\epsilon$ extra idle time. We also have not increased the makespan of the brute-force schedule, so it must be optimal.
If there are any short jobs in the second phase, the first phase has at most $1/\epsilon$ rounds (because every round contains a long job) and no phase has more than $\epsilon^2$ idle time for the master (since otherwise we could have scheduled some of the remaining short jobs). Thus the total idle time for the master is at most $\epsilon$. In rounds were the helper has idle time, note that this round is unmodified from the original optimal schedule (since the master would not start a new job if the helper was idle). Thus, the additional idle time, over that of an optimal schedule, is at most $\epsilon$ (from rounds in which the master is idle; the rounds in which the helper is idle do not contribute any additional time).
An interesting question is what happens if the master is impatient and always starts a new job instead of having the option to wait for the helper to finish.


Data structure for counting bits set on a table

If one of the operations is much more common, you could use an array of bits resp. of counts, so the common operation can be done in $O(1)$ at the cost of the other operation taking $O(n)$.

If you can't make such an assumption, then I don't think there is anything better than the $O(\log n)$ of the BIT.


You can use Fibonacci hashing, namely

$\qquad h_F(k) = k \cdot \frac{\sqrt{5} - 1}{2} - \left\lfloor k \cdot  \frac{\sqrt{5} - 1}{2} \right\rfloor$.

For $k=1,\dots,n$ you get $n$ pairwise-distinct numbers (about) evenly spread in $[0,1]$. By scaling to $[1..M]$ and rounding (down), you get about evenly spread numbers in that interval.

For example, these are $h_F(1), \dots, h_F(200)$ scaled to $[0..10000]$ (left original sequence, right sorted):

This is an instance of what Knuth calls multiplicative hashing. For $w$ the computer's word size, $A$ some integer relatively prime to $w$ and $M$ the number of addresses needed, we use

$\qquad h(k) = \left\lfloor M \left( \bigl( k \cdot \frac{A}{w}\bigr) \mod 1 \right) \right\rfloor$

as hashing function. The above follows with $A/w = \phi^{-1} = \frac{\sqrt{5}-1}{2}$ (make sure you can compute it with a sufficient precision). While this also works with any other irrational number besides $\phi^{-1}$, it is one of only two numbers that lead to the "most uniformly distributed" numbers.

Find more in The Art of Computer Programming, Volume 3 by Donald Knuth (chapter 6.4 from page 513 in the second edition). In particular you'll find why the resulting numbers are pairwise distinct (at least if $n \ll M$) and how to compute the inverse function if you use natural $A$ and $w$ instead of $\phi^{-1}$.


Approximation factor preserving reduction

That looks right.  The only exception I can think of is problems where there isn't an optimal solution, but just a sequence of ever-better solutions converging to, but never attaining, some optimum.  Though actually, even then, if the optima weren't the same, it should be possible to find some solution in between the optima, which would arrive at a contradiction.  So it seems what you say should still hold, unless I'm also missing something.


Efficient algorithm for getting from 1 to n with 3 specific operations

Find the shortest path from $1$ to $n$ on an appropriate graph on vertices $\{1, \dots, n\}$.  This approach will work whenever it's guaranteed that intermediate values in the calculations will lie within some bounded range.


Determining whether a change in an memoized algorithm will improve the performance

Intuitively I understand that the reason why the function became less efficient is because it avoids solving the right subproblem sometimes, which means that it also memoizes less cases, which in turn makes it perform more work.

This is impossible. Not solving and memoizing a subproblem can never make the algorithm slower. Either the subproblem will never be needed (in which case not memoizing it only saves work) or it will turn out to be necessary after all, in which case we would have to compute it. However, the worst case is only that we do not save any time: if we skip the computation now, we might have to do it in the future, but this is not more work than doing it now.

The optimization you've done will never cause more work to be done on computing subproblems. Thus, the only reason it could make the algorithm slower is if the optimization itself is expensive to compute. It seems likely either score or base_score are very slow methods, and your optimization causes them to be evaluated an additional time. You might be able to speed it up by storing base_score and score(left_solution) in a temporary variable.


You can reduce from $3$-coloring.
Given an instance (graph) $G=(V,E)$ of $3$-coloring, create a tri-graph $G'=(V', E')$ by transforming each edge $e=(u,v) \in E$ to a tri-edge $(u,v,z_e)$ in $G'$ (where $z_e$ is a new vertex).
A 3-coloring $c : V' \to \{1,2,3\}$ of $G'$ induces a $3$-coloring of $G$: simply color $v \in V$ with color $c(v)$.
A 3-coloring $c : V \to \{1,2,3\}$ of $G$ can also be transformed into a $3$-coloring of $G'$ by coloring each vertex $z_e$, where $e=(u,v) \in E$, with the unique color in $\{1,2,3\} \setminus \{c(u), c(v)\}$.


Paging - access less than a page of memory

You are confusing paging and memory allocation.

Paging is used to implement virtual memory: Your logical address space is divided into pages, and each page can be mapped to a physical address in RAM, or can be assigned to some location in your backing store. Because the computer has to keep track of how each page is used, we make the pages reasonably large to avoid having an unreasonably large number of pages.

malloc doesn't care about pages at all. It assumes that some portion of your logical address space is available for allocating memory. It doesn't care how this logical address space is mapped to RAM or backing storage. It just takes four bytes from your logical address space and keeps track that this memory is used. If  - by coincidence - all but 100 bytes of a page had been used by malloc (which malloc doesn't know about and doesn't care about), and you called malloc to allocate another 200 bytes, you would likely get the last 100 bytes of that page and the next 100 bytes of the next page. malloc doesn't care.

Paging also doesn't care about malloc, it only cares about reading and writing data.


Show how lack of universe levels would create contradiction in homotopy type theory (in Agda)

The problem is not specific to homotopy type theory. In type theory in general, if there is a type of all types, then every type is inhabited. This was shown first by Girard who encoded the Burali-Forti paradox in type theory.

A simplification of the paradox was found by Hurkens. Here is Agda code for it, and here is Coq code.


Distributed systems according to Lamport?

My interpretation of this quote is that if we consider the whole distributed system as a black box containing multiple local processors, then when we send input requests to this box, the whole box moves to another state even though we don't know what that next state is (particularly in non-deterministic state machines), but we are sure that there's no inconsistent interpretation within the box.

Actually input requests could be thought of as an external node that does atomic broadcast to all internal nodes (within the box). This type of broadcast ensures us that all internal nodes receive messages in the same order, so all local state machines move to their next states. If we define state of the whole system as a set of all internal local states, so whenever we receive an atomic broadcast (i.e. input request), our system's state moves to a next state depending on the order of messages that all internal nodes agree on. Hence, each different order leads us to a non-deterministic destination (the next state) in the state machine of the whole system.

Therefore, total ordering is sufficient to model a distributed state machine. However in some applications some more properties might be needed, for instance, FIFO ordering, causal ordering, etc.


How to calculate the average of x numbers?

Instead of giving an answer, I will try to paraphrase the steps, I hope this will help you solve your homework.

Identify the problem: What is the input? What is the output?
Comprehend the problem: Can you write a formula for the problem, that relates input to the output? What is the formula for the average of x numbers?
Identify different alternatives to solve the problem: How can you implement that formula? As a closed-form function? With an iterator? Solving recursively?
Selecting the best alternative to solve the problem and why: Which one did you select in step 3, and why?
Construct a list of instructions that allows to solve the problem: Write the pseudo-code about how you can actually implement the solution you selected on step 3.
Evaluate the solution: Is it working? How well is it working? Are there any conditions that it is not working? What are they? How long does it take to produce an answer?

I hope that you are actually stuck and these explanations can guide you. Else I will regret my decision to help someone that actually looks for a ready-to-jump-on solution for his homework.


Proof of equality with destructuring let...in

You can destruct not only on variables, but on expressions like f n as well. So, this will get you a solution:

Lemma foo : forall n, f n = (let (x, y) := f n in (x, y)).
  intro n.
  now destruct (f n).    (* or destruct (f n). reflexivity. *)
Qed.


Yes, it is correct.  Yes, it is efficient: your implementation for left-shift requires only four basic operations (i.e., about four instructions), and your implementation for right-shift requires only three basic operations.


Given a set of 2D vectors, find the furthest reachable point

Suppose you knew the direction $\hat{d}$ of a longest vector sum. Then finding a subset of vectors that should be included in the longest-vector sum is trivial:

Include $v$ when the dot product $v \cdot \hat{d} > 0$.
Exclude $v$ when $v \cdot \hat{d} < 0$.
There won't be a $v$ where $v \cdot \hat{d} = 0$, unless $v=0$, because that contradicts $\hat{d}$ pointing towards a longest vector sum.

Now consider what happens if we vary $\hat{d}$ away from the optimal direction to get $d^\prime$. The sum-along-directions stays constant... until we turn so much that one of the dot products $v \cdot d^\prime$ switches sign. That only happens when $d^\prime$ is perpendicular to a $v$.

Since we're working in 2-d, we can think in terms of angles instead of directions. We have a function $f(\theta)$ that adds up all vectors $v$ even-slightly-aligned with the angle $\theta$. And we know this function only changes values when $\theta$ is perpendicular to one of the vectors $v$. And we know there are at most $2n$ such critical angles.

Ah.

Algorithm

Make a list of all the critical angles where $f(\theta)$'s value changes due to $\theta$ being perpendicular to a $v$. Sort the list. Find a maximizing $\theta$ by sampling $f$ at the midpoint between each contiguous pair of critical points (remembering to include the midpoint where the angles wrap around). Use that $\theta$ to recover a best set of vectors.

By adjusting the total as vectors cross in and out of alignment, instead of recomputing it every time, the algorithm will run in time $O(n \log n)$ with the most expensive step being the sorting of the critical points.

Here's some quick and dirty pseudo-code. WARNING: THIS CODE WAS WRITTEN BY HAND WITHOUT BEING RUN OR TESTED. IT WILL CONTAIN BUGS.

import math

def dot(u, v):
    return u[0]*v[0] + u[1]*v[1]

def vec_sum(vecs):
    t = [0, 0]
    for v in vecs:
        t[0] += v[0]
        t[1] += v[1]
    return tuple(t)

def vectors_along(vec_set, angle):
    d = (math.cos(angle), math.sin(angle))
    return [v for v in vec_set if dot(d, v) > 0]

def transitions(vecs):
    # compute (critical-angle, vector, entering-vs-leaving) tuples
    results = [(t % (2*math.pi), v, b)
               for v in vecs
               for (t, b) in [(math.atan2(v[0], -v[1]), True),
                              (math.atan2(-v[0], v[1]), False)]]
    return sorted(results, key=lambda e: e[0])

def longest_subset(vecs):
    best_angle = None
    current_total_vec = None
    best_norm = 0
    for transition, vec, entering in transitions(vecs):
        # TODO: If two transitions are less than 0.00001 apart this fails
        # TODO: In particular, equal/opposite vectors cause equal transitions.
        angle = transition + 0.00001
        if current_total_vec is None:
            current_total_vec = vec_sum(vectors_along(vecs, angle))
        else:
            current_total_vec += vec * (1 if entering else -1)
        current_norm = dot(current_total_vec, current_total_vec)
        if current_norm > best_norm:
            best_norm = current_norm
            best_angle = angle
    return vectors_along(vecs, best_angle)

Higher Dimensions

This idea works quickly in 2d, but in 3d the boundaries that add/remove a vector from the along-direction sets are great circles instead of points. So everything gets more complicated and more expensive there and continues to get more complicated as you go to higher dimensions.


How to recognise the number of errors that can be detected and corrected of a large set of codewords (k) each having a specified number of bits (n)?

There are $2^{10}$ binary strings of length $10$. We can partition them into pairs $x_1\ldots x_90,x_1\ldots x_91$. Since your code contains more than $2^9$ codewords, it will contain at least one such pair. Hence the minimum distance of your code is only $1$.


Hash functions producing uniform outputs

What are the quadratic residues in $\mathbb{Z}_{10}$? What about the cubic residues? What are the orders of $[11]$ and $[12]$ in the group $(\mathbb{Z}_{10}, +)$?

A brief solution follows.

For the sake of clarity, we rename the four functions $a, b, c, d$. Let's analyze their range. Because of the closure properties of the modulo operation, we may do so in the ring $(\mathbb{Z}_{10}, +, \cdot)$. We will prove that $a, c, d$ have a range that is a strict subset of $\mathbb{Z}_{10}$, and can not therefore be uniform, while $b$ is a permutation of $\mathbb{Z}_{10}$.

Since we are working over a finite ring, we could compute each of the functions on each element of $\mathbb{Z}_{10}$ and prove our claim by exhaustion. Even though that's probably what the exercise wanted you to do, and what you should fall back on if you don't understand what follows, a true gentlemen never does that. Let's work out a more elegant way.

To begin with, we observe that $a(i) = i^2$ cannot be injective, and therefore, by piegonhole, not even surjective modulo any $m > 2$ as $[1] \neq [-1]$ but $[1]^2 = [1] = [-1]^2$. This also rules out $c$, since $[11] = [1]$ in $\mathbb{Z}_{10}$.

$d$ has to go as well; this stems from the more general fact, which I leave for you to prove, that if $\gcd(k, m) \neq 1$ then $f(i) = ki$ cannot be injective modulo $m$. (Hint: use the Bezout identity).

Now all is left is to prove that $b(i) = i^3$ is a permutation of $\mathbb{Z}_{10}$. First of all, we observe that the ring $\mathbb{Z}_{10}$ is isomorphic to the direct sum of $\mathbb{Z}_5$ and $\mathbb{Z}_2$. Since $b$ is clearly a permutation of $\mathbb{Z}_2$, if we prove that it's also a permutation of $\mathbb{Z}_5$ we are done. But $5$ is prime, so $i^3 \equiv i^{-1}$, which proves our claim.