Induction to prove equivalence of a recursive and iterative algorithm for Towers of Hanoi

Let's start with reformulating the two solutions, following Wikipedia. We use A for the source peg, B for the auxiliary peg, and C for the destination peg.

Recursive algorithm

If $n > 1$, recursively move $n-1$ discs from A to B.
Move the $n$th disk from A to C.
If $n > 1$, recursively move $n-1$ discs from B to C.

Iterative algorithm

If $n$ is even, execute repeatedly until done:

Make a legal move between A and B.
Make a legal move between A and C.
Make a legal move between B and C.

If $n$ is odd, execute repeatedly until done:

Make a legal move between A and C.
Make a legal move between A and B.
Make a legal move between B and C.

(We terminate the algorithms whenever there is no legal move.)

We will prove that both algorithms coincide, using the fact that the recursive algorithm makes exactly $2^n-1$ moves, which can easily be proved by induction. The base case is $n = 1$. In this case, the recursive algorithm moves the disk from A to C, and this is also what the iterative algorithm does.

Suppose now that we have proved the claim for $n$. We will prove it for $n+1$. There are two cases to consider, according to the parity of $n$. Suppose first that $n$ is odd.

The first step in the recursive algorithm is to move $n$ discs from A to B. We know that this is the same as running $2^n-1$ steps of the iterative algorithm for odd many disks, with B and C switched. We observe that upon switching B and C, we exactly obtain the iterative algorithm for even many disks. Therefore the first $2^n-1$ moves made by the iterative algorithm coincide with what the recursive algorithm does (this is because at any step there is a move involving one of the first $n$ disks).

Since $2^n-1 \equiv (-1)^n-1 \equiv 1 \pmod{3}$, after executing $2^n-1$ steps, the next step in the iterative algorithm is to make a legal move between A and C, which is exactly what the recursive algorithm does. We can now rephrase the remaining operation of the iterative algorithm as repeatedly executing the following moves:

Make a legal move between B and C.
Make a legal move between A and B.
Make a legal move between A and C.

This is exactly what the iterative algorithm for odd many disks looks like after switching A and B. Therefore just as before, the following $2^n-1$ steps of both algorithms coincide. The same calculation as before shows that the next move to be considered in the iterative algorithm is the one involving A and B, but there are no disks on either of these pegs, so the iterative algorithm stops. This completes the proof for odd $n$.

The proof for even $n$ is very similar. The first $2^n-1$ moves coincide since switching B and C switches the two versions of the iterative algorithm. This time $2^n-1 \equiv 0 \pmod{3}$, so the next move to be considered by the iterative algorithm involves A and C, matching the recursive algorithm. We can rephrase the operation of the iterative algorithm henceforward as repeatedly executing

Make a legal move between A and B.
Make a legal move between B and C.
Make a legal move between A and C.

This is the same as the iterative algorithm for even number of disks with A and B switched, so the following $2^n-1$ moves coincide. The next move to be considered again involves A and B, which is impossible. This completes the proof.


On the minimum order of a maximal independent set in cycle graphs and path graphs

The smallest maximal independent set in a cycle or path of length $n$ clearly has size about $n/3$. This can be seen by inspection and certainly doesn't need anything like Turán's theorem.


Compute median in unsorted array in $\mathcal{O}(\log{}n)$ space and $\mathcal{O}(\log{}n)$ passes

The natural algorithm determines the $\log n$ bits of the median, MSB to LSB. Suppose that we have determined the $k$ MSBs of the median, $b_{m-1},\ldots,b_{m-k}$. Determine the number of integers in the array whose $k+1$ MSBs are $b_{m-1},\ldots,b_{m-k},1$, and use this to find the $(k+1)$th MSB of the median.

This algorithm uses $O(\log n)$ passes and $O(\log m + \log n) = O(\log n)$ space.


A many-one reduction is not a "proof-by-contradiction" per se, it is an application of a theorem. The theorem is:

  Let $L,L'\subseteq \{0,1\}^*$, and $L \leq_m L'$. Then, it holds that

  If $L$ is undecidable, then $L'$ is undecidable.
  if $L'$ is decidable, then $L$ is decidable.

I will omit the proof, there are plenty of resources where you can read up on it. You can view the statement $L \leq_m L'$ intuitively as "The language $L$ is easier to decide than the language $L'$". And that's what a reduction proof does. You show that one language (the hard, known one, like the halting problem $H_0$)  is easier to decide than a new, unknown language $L$. By showing $H_0 \leq_m L$ you've essentially shown (by application of the above theorem) that the halting problem is easier than $L$. Thus, $L$ cannot be decided.
So, to answer your questions:

$A \leq_m B$ means that the language $A$ is easier to decide than the language $B$.
To show hardness, you reduce "YOUR_HARD_LANGUAGE $\leq_m$ SOME_NEW_LANGUAGE". To show computability, you can reduce in the other direction, but usually it's simpler to just construct a TM that solves the given problem.
A reduction $L \leq_m L'$ takes an instance $x \in \{ 0,1\}^*$ and does the following with it: If $x \in L$, you make sure that the reduction $f(x) \in L'$. If $x \not \in L$, then the reduction maps $f(x) \not \in L'$. So - if you prove hardness, you transform a known hard problem into the unknown problem.
It is a contradiction in the sense of "If I could solve the new problem, then I can solve the hard problem, which cannot be, since it is proven to be hard". This contradiction is hidden in the Theorem above and you just slap it (implicitly) on every reduction you do.

I hope that helped. As I said, my main intuitive approach to reductions is "How could I use a new language $L'$ to solve an old, hard language $L$?".


Confused between 2 phase locking and 2 phase commit

These are two different things that have two different goals.

The two-phase locking protocol is designed to guarantee serializability for transactions that access concurrently a single, centralized database, using a locking mechanism. So its goal is to maintain the consistency of a centralized database, avoiding “bad” interferences among concurrent, different, transactions that operate on the same data.

Two-phase commit protocol, instead, concerns the execution of distributed transactions is a distributed database, and guarantee that a single distributed transaction, seen as “set of processes in a network system”, coordinates the work of those processes even in case of temporary system failures (for instance, in case of network failure). So the protocol has the objective of avoiding situations in which a certain transaction commit its operation is a node (that is in a part of the distributed database), but aborts in another node (that is in another part of the same distributed database).

Of course you can see both protocols as having the final objective is to maintain the “consistency” of the database, centralized in a case, distributed in the other. But this is really a generic point of view.


As you say, the state of an automaton is just an abstract, unstructured value. As such, you don't need a data structure per se: you just need a variable type that can store different values, such as an integer.


Why doesn't the binary fraction representation match the decimal fraction representation?

No, that's not how binary fractions work.
A decimal such as $0.13$ represents
$$0.13_{\mathrm{dec}} = 1\times 10^{-1} + 3\times10^{-2} = \frac{13}{100}\,.$$

Similarly, a binary fraction such as $0.1101$ represents
$$0.1101_{\mathrm{bin}} = 1\times 2^{-1} + 1\times 2^{-2} + 0\times 2^{-3} + 1\times2^{-4} = \frac{13}{16}\,.$$
$1101_{\mathrm{bin}} = 13_{\mathrm{dec}}$ but
$$0.1101_{\mathrm{bin}} = \frac{13}{16}\neq\frac{13}{100}=0.13_{\mathrm{dec}}\,.$$

Another way to see that you can't convert fractions into binary by forgetting that they're fractions is to note that $0.3=0.30$, but $3\neq 30$. So it can't possibly be that you convert $0.3$ in decimal to binary by saying "$3$ in binary is $11$, so $0.3$ in binary is $0.11$", since $0.3=0.30$ in decimal, so they should be equal in binary, too. But $30$ in binary is $11110$.


Yes, your thought is correct. The only missing part, as you pointed out, is whether or how we can create a CFL algorithmically for the intersection of a CFL with a RL.

If you take a close look at any proof for the fact that the intersection of a CFL with a RL is a CFL, you will find that the proof is constructive or can be made to be constructive easily, giving that there is an algorithm to construct the CFL for a given PDA. Here "constructive" means the same as "algorithmic". It is just by convention or history, we tend to use the word "constructive" instead of "algorithmic" to describe a proof.

You can check your textbook, or this and this.

Exercise. Is the following problem decidable?

  Given a context-free grammar $G$ and a regular expression $R$, is $L(G) \supseteq L(R)$?


Can/Do multiple processes run simultaneously on a multi-core system?

This question is more related to the difference between a thread and a process. Here is a hint: When it comes to kernel scheduling structures, the only thing the kernel looks at is threads, not processes.

A process is easier to understand as a group of threads. All processes have to have at least one thread, and it is that thread that is scheduled in the operating system, not the process.

So, with this understanding, in a dual core system with two processes each containing a thread each, there are two threads total that are scheduled on the two cores.


Is there any other computation theory besides the one in automata theory?

There is indeed computability-theory for non-discrete settings. This area is called computable analysis. A decent tutorial to computable analysis is here (if you have an institutional subscription, or can get it from a library):

https://link.springer.com/chapter/10.1007%2F978-0-387-68546-5_18

The tutorial focuses quite a bit on the case where we are computing with real numbers, or at least elements of metric spaces. Computable analysis can handle much more situations though. Roughly speaking, we probably have reasonable computability-notions for any kind of space appearing in ordinary mathematics.

It turns out that many concepts from the classical, discrete computability theory still apply, but topological aspects also become very relevant.


Checking whether at least n/2 + 1 elements of a set/vector are equal

I think there is an even better approach to your problem:

The element you are looking for will also be the median of the list. Find the median of the list using the Median of Medians algorithm. $O(n)$ complexity
Check if the median appears at least $n/2 + 1$ times on the list $O(n)$ complexity

So, the algorithm you're looking for runs in linear time.


How to partition a set into disjoints subsets each of given size?

When $s_j = 1$ for all $j$, the problem is the same as deciding whether a bipartite graph has a perfect matching. In the general case, we can solve it using maximum flow.

Set up a flow network with the following components:

A source $s$, a sink $t$, a vertex $S_j$ for each set, and a vertex $x_i$ for each element in the universe.
Connect $s$ to each $S_j$ with an edge of capacity $s_j$.
For each $x_i \in S_j$, connect $S_j$ to $x_i$ with an infinite capacity edge.
Connect each $x_i$ to $t$ with an edge of capacity $1$.

Now compute the maximum flow. If it equals $|U|$ then the instance has a solution. Moreover, you can extract the solution from a maximum integer flow.

The max flow min cut theorem also gives us a Hall-like criterion: a solution exists if for every set $X$ of elements,
$$ \sum_{j\colon S_j \cap X \neq \emptyset} s_j \geq |X|. $$
That is, if we sum the "capacities" $s_j$ for all sets $S_j$ that intersect $X$, then we need to get at least $|X|$. This is clearly a necessary condition, and the max flow min cut theorem shows that it is sufficient.


How to exclude all points adjacent to a given point from the feasible region of IP

You can't eliminate all points in $A(y) \setminus \{y\}$ without also eliminating $y$, as the conjunction of a bunch of linear inequalities always gives a convex region, and $A(y) \setminus \{y\}$ is non-convex.

Here I am assuming we're not allowed to introduce new variables.  If we're allowed to introduce new variables, there are many uninteresting ways to achieve it, by taking advantage of the fact that with integer variables you can express any logical predicate you like; however, it seems unlikely that this will be useful for anything in practice.


Is $\{\langle G,x\rangle \mid x\in L(G)\}$ context-free?

If your language were context-free, then by intersecting it with a regular language, we would deduce that the following language would be context-free:
$$
\{ \langle G,x \rangle \mid \text{$x \in L(G)$ and $G$ contains a single production $S \to w$} \}
$$
However, this is just the celebrated language $\{ ww : w \in \Sigma^* \}$ in disguise, which is known not to be context-free. It follows that your language (using any reasonable encoding) is also not context-free.


Max-Heap PriorityQueue to keep the k highest items and return them in descending order

If what you want is to keep the top $k$ items at all times what you need is a min-heap, not a max-heap. After every insert you should check if the length is longer than $k$, and if yes, pop.
If you use numbers as your priorities you can turn a max-heap into a min-heap by simply negating the priority.


Shortest path algorithm using Dijkstra with Fibonacci heap

I do not think you can take $|V| = 2009$ because you are saying that $|V|>2009$, which means that in the best case $V = 2010$ but it does not say anything about the worst case (which is what big oh notation is about). So you cannot say that $|V|$ is constant as is implied in your question.

The correct process would be this: $O(|E| + |V| log |V|) = O(|V|*10 + |V| log |V|) = O(|V| + |V| log |V|)$
The only assumpution you can make is that $|E| = |V|*10 = |V|$. Remeber that you should only get rid of a variable in asymptotic notation if it is equal to a constant.

You can safely assume that $|E| = |V|*10$ because in the worst case every node will have 10 edges as stated in your question.

According to your reasoning dijkstra algorithm will only need overall 2009 extractions from the heap because you are looking for 2009 nodes close to $s$. That is not correct because is not possible in the algorithm to know beforehand which will be the exactly 2009 nodes that are close, say for example that the cheapest node $c$ has a shortest path of length $k$ and $k > 2009$, where $k$ is the number of nodes in the shortest path. Dijkstra algorithm will need to transverse the previous nodes and that will require more than 2009 operations in the heap because you have to process the nodes to reach node $c$ first.

Example:

Suppose you do not want to find 2009 closest nodes but 4 and that our source vertex is $7$, so following your question there should be overall 4 operations to get the 4 closest nodes. Given the following graph:

When you start the algorithm node $7$ is pushed into the heap, then nodes $0,1,2,3$ are pushed, in this case the number of times the nodes are pushed is the same number of times the nodes are popped from the heap (which may not be the case), now, as the algorithm proceeeds it will push nodes $4$ and $5$ until it reaches $6$ which in fact, is the closest node to $s$, if the path to node $6$ would have been longer a bigger number of push/pops would have been done in the heap. In a extreme case between node $3$ and $6$ there may be 90 nodes so that number of operations must be done in order to reach node $6$ which totally exceeds $4$ which is what is stated in your question.

The assumption that for every node $i$ that is extracted from the heap after any node $x$ follows that $d(s,i) > d(s,x)$ (where is $d(u,v)$ is the cost of the shortest path from $u$ to $v$) is not correct, because is possible that in the future you may insert another node into the heap that has a smaller distance, in fact that is what makes dijkstra algorithm actually compute optimal paths.


The authors' goal is to rule out protocols that work for every possible input. Hence, in their proof by contradiction, they can assume that the protocol works correctly on every input.

The specification of an algorithm should include all constraints on the possible inputs. For example, binary search assumes that the input array is sorted. The specification of consensus protocols doesn't specify any constraints beyond the processes' inputs being binary.


Conventional regular expressions as they are commonly found in literature describe exactly the regular languages. Given a regular expression, you can therefore find an equivalent automaton, then find the linear grammar equivalent to such automaton and put it in any form you prefer.

On the other hand, "regular" expressions as they are implemented by most programming languages are not equivalent to the set of regular languages; several implementations allow you to describe languages that aren't even context-free.


What do complexity classes look like, if we use Turing reductions?

You can use $\mathsf{P}^{\Sigma^\mathsf{P}_i}$.
Some authors denote them by $\square^\mathsf{P}_i$
(similar to $\Delta^\mathsf{P}_i$ and
$\nabla^\mathsf{P}_i$ notations).
It's essentially the Turing closure of the polynomial hierarchy.
We have
$$\mathsf{P}^{\Sigma^\mathsf{P}_i}\subseteq \mathsf{NP}^{\Sigma^\mathsf{P}_i}=
\Sigma^\mathsf{P}_{i+1}\subseteq
\mathsf{P}^{\Sigma^\mathsf{P}_{i+1}}$$
Therefore
$\mathsf{P^{PH}} =
\sum_{i\geq 0}\mathsf{P}^{\Sigma^\mathsf{P}_i} =
\sum_{i\geq 0}\Sigma^\mathsf{P}_{i} =
\mathsf{PH}$.

If the polynomial hierarchy does not collapse all inclusions are strict.


Take a look at this post.
A general way to remove epsilon transitions is to transform the PDA into a CFG, then take this grammar and convert it back to a PDA. This will result an equivalent PDA that does not need epsilon transitions. Take a look here for the algorithms converting the PDA to CFG and back.


Can I simplify successive XOR operations?

Yes, there are ways to improve the efficiency greatly.

Let ${}_k{i}$ be the $k$-th digit of $i$ in binary representation, i.e., it is 0 if $\lfloor i/2^k\rfloor$ is even and 1 otherwise. For example, since $19=(10011)_2$, $_019=1$, $_119=1$, $_219=0$, $_319=0$, $_419=1$. In most programming languages,  ${}_k{i}$ can be computed as $(i\text{>>}k)\%2$.

Let us apply the power of summand splitting and rearrangement to inspect the contribution to the sum by the $k$-th digits in isolation.

$$\begin{aligned}
\text{total sum}
&=\sum_{\text{ row } i\,}\sum_{\text{ column }j\,} i \oplus j\\
&=\sum_{\text{ row } i\,}\sum_{\text{ column }j\,} \sum_{0\le k\lt u} ({}_k{i}\oplus {}_k{j})\cdot 2^k\\
&=\sum_{0\le k\lt u} 2^k\sum_{\text{ row } i\,}\sum_{\text{ column }j\,} {}_k{i}\oplus {}_k{j}\\
&=\sum_{0\le k\lt u} 2^k\left(\#\{\text{row }i\mid {}_k{i}=1\}\cdot \#\{\text{column }j\mid {}_k{j}=0\}\right.\ + \\
&\quad\quad\left.\#\{\text{row }i\mid {}_k{i}=0\}\cdot \#\{\text{column }j\mid {}_k{j}=1\}\right)
\end{aligned}$$

We can set $u=\lceil\log_2\max(m+1, n+1)\rceil$ or any integer such that $n,m\lt 2^u$, where $n$ is the number of rows and $m$ is the number of columns. If $m$ and $n$ are ints or longs in Java or C#, $u=63$ could be a good choice.

Now the problem is shifted to compute $\#\{\text{row }i\mid {}_k{i}=0\}$ and the like ones. We have
$$\begin{aligned}
\#\{\text{row }i\mid {}_k{i}=0\}
&=2^k\left\lfloor\frac {n-1}{2^{k+1}}\right\rfloor +
\min\left(n-2^{k+1}\left\lfloor\frac{n-1}{2^{k+1}}\right\rfloor,\ 2^k\right)\\
\#\{\text{row }i\mid {}_k{i}=1\}
&=2^k\left\lfloor\frac{n-1}{2^{k+1}}\right\rfloor +
\max\left(0,\ n-2^{k+1}\left\lfloor\frac{n-1}{2^{k+1}}\right\rfloor -2^k\right)
\end{aligned}$$
In terms of Java, they are, respectively,

((n-1)>>(k+1)<<k) + Math.min(1<<k, n - ((n-1)>>(k+1)<<(k+1))),
((n-1)>>(k+1)<<k) + Math.max(0, n - ((n - 1)>>(k+1)<<(k+1)) - (1<<k))

The time-complexity of the algorithm is about $O((\log n)^2)$


Is deciding if there's a solution to a single multivariate quadratic equation NP-hard?

For $\mathbb{R}$ (the real numbers), you can decide whether a single multivariate quadratic equation has any real roots or not, in polynomial time.  See https://cstheory.stackexchange.com/a/19858/5038.  There are some other answers to that question that partly address the case of other fields.

For $\mathbb{F}_2$ (the integers modulo two), you can decide whether there is a root in polynomial time.  See https://cstheory.stackexchange.com/q/37687/5038.

I don't know what the situation is for $\mathbb{Q}$ or $\mathbb{F}_{p^n}$.


Can the solution to a POMDP be found using linear programming?

What is known about the complexity of finding optimal policies for POMDPs indicates that solution by Linear Programming is not possible in the general case.
When the decision horizon is bounded (finite), finding optimal POMDP policies is PSPACE-hard (Papadimitriou and Tsitsiklis, 1987).
When the decision horizon is infinite and we are using e.g. the geometrically discounted rewards, finding optimal POMDP policies is unsolvable (Madani, Hanks, Condon 1999).
Linear Programming is solvable in polynomial time, and (efficient) reductions from the above PSPACE-hard and unsolvable problems to Linear Programming therefore are not believed to exist and do not exist, respectively.
Solution of POMDPs in sufficiently simple special cases is possible with LP, of course (like MDPs, which are fully observable POMDPs).


This answer is for the following version of the post:

Say I have an array sized $n$. A quicksort pivot is balanced when each side of the partition ends up with $n/c$ ($c$ is a fixed constant). Else, the partition in unbalanced.
In both these cases, partitioning takes $pn$ time ($p=O(1)$). Let's say I run quicksort and after one balanced pivot, I get $j$ unbalanced pivots. Is the runtime still $O(n\log n)$? I believe that it will be useful to use recurrences, but not sure how to set up from there.

The running time should still be $O(n\log n)$. Intuitively, the size of the array decreases by a factor of $c$ every $j+1$ recursion levels, so the total number of levels would be $(j+1)\log_c n = O(\log n)$. The work at every level is $O(n)$, for a total of $O(n\log n)$.
How would a recurrence look? We will have $j+1$ different functions: $T_j$ for the balanced levels, and $T_0,\ldots,T_{j-1}$ for the unbalanced levels. The recurrences are
$$
T_j(n) = \max_{n/c \leq m \leq n-n/c} T_0(m) + T_0(n-1-m) + pn, \\
T_i(n) = \max_{1 \leq m < n/c} T_{i+1}(m) + T_{i+1}(n-1-m) + pn.
$$
Actually solving the recurrences could be a chore, so it's better to formalize the intuitive argument outlined above.


Finding the spots furthest away from bad data

I am going to assume you want to maximize the "separation".  In particular, I'll say that a solution has separation $\ge s$ if every selected place is at least $s$ apart from any selected place, and if every selected place is at least $s$ away from any bad place.

Then this can be solved in $O(m \lg (m/n))$ time using binary search and a greedy algorithm, where $m = $ the data size.  I'll show how to determine whether it's possible to place $n$ stations achieving separation $\ge s$, in $O(m)$ time; then you can use binary search on $s$ to find the largest $s$ achievable.

To determine whether separation $\ge s$ is achievable, just use a greedy algorithm with a left-to-right scan.  Select the left-most place you can.  Then, scanning left to right, select the first place that can be selected (taking into account it has to be at least $s$ to the right of the one you previously selected, and at least $s$ away from any bad place).  Keep iterating.  When you're done, that gives you the maximum number of places that can be selected, subject to the requirement that you have separation $\ge s$.

Now you can use binary search from here.  If the number of places that could be selected was less than $n$, decrease $s$ and try again.  If the number of places that could be selected was greater than or equal to $n$, increase $s$ and try again.  There are at most $m/n$ possible values of $s$, so after $\lg (m/n)$ steps of binary search, this will terminate.  If you start the binary search at the smallest possible value of $s$, the running time will be $O(m \lg s)$.


How again do certain sorting methods use $o(n \log n)$ time?

Radix sort cannot be reduced to a comparison-based sort. If the alphabet is binary, then in some sense you are doing 2-way comparisons, since each bit is either 0 or 1. If there are $n$ numbers of width $w$, radix sort takes time $O(nw)$. Therefore as long as $w \ll \log n$, radix sort will be faster than any comparison-based sort.

What does the condition $w \ll \log n$ mean? If numbers have width $w$ then they are in the range $0$ to $2^w-1$. When $w \ll \log n$, there are less than $n$ possible numbers, so some numbers repeat. In this regime you can beat comparison-based sorting.

Another algorithm beating comparison-based sorting in the regime in which there are less than $n$ possible number is counting sort. Suppose that the domain is of size $m$. We initialize an array of size $m$, and count how many elements of each type there are. We can then unpack this histogram into the sorted array. This runs in time $O(n+m)$. If $m \ll n$ then this algorithm runs in optimal $O(n)$ time.

In both of these cases, the algorithms cannot be rephrased in the decision-tree model (try doing it!), and so aren't subject to the limitations of comparison-based sorting. No paradoxes here.


How can I teach computer science without using computers?

Asking how you can study computer science without computers is a bit like asking how you can study cosmology without telescopes. Sure, it's nice to be able to look at the things you're studying and it's often very helpful to be able to play around with things. But there's a whole lot you can do without access to a computer: in extremis, you could probably do almost all of a undergrad course with no computers.

In practical terms, access to computers helps reinforce a lot of what you learn in a computer science course. Programming courses are, obviously, much more natural with access to a computer. On the other hand, being forced to write code on paper does encourage people to think about their code and make sure it really works, rather than just running it through a compiler again and again until it compiles and then running trivial test cases again and again until the obvious bugs go away.

Topics that would be most natural without computers would be the more mathematical ones. All the background mathematics, such as combinatorics and probability. Computability, formal languages, logic, complexity theory, algorithm design and analysis, information and coding theory. Anything to do with quantum computation!


One example is consistent hashing. The usual scenario used for motivation is assigning files to servers. To avoid having too many files associated with a single server, you map $n$ files to $m$ servers via some hash function $h:[n]\rightarrow[m]$. Suupose you add a new server or that an existing server crashes, then you would have to rehash all the files to maintain functionality (this entails actual copying of the contents). One solution that avoids this is mapping each file and sever to the unit circle, and associating each file with the first server met when moving anticlockwise. If $h:[n]\cup[m]\rightarrow \left\{(\cos t,sin t)| 0\le t\le 2\pi\}\right\}$ satisfies SUHA, i.e. $h(i)$ is uniformly distributed on the unit circle when $i$ is uniformly distributed over $[n]\cup [m]$, then the expected number of files moved after a crash is $\frac{n}{m}$.


How to calculate the average depth of a binary tree?

You haven't stated which distribution of random binary trees you are interested in, but in many cases the answer is indeed $\Theta(\sqrt{n})$. See for example Flajolet and Odlyzko, The average height of binary trees and other simple trees.


By direct reduction, do you then mean a reduction that does not leave the graph-world and go back again? (that might be a very vague formulation, sorry). I do not think such a reduction exists. Of cause proving that it does not exist is not a simple matter, but at least I have not been able to find or think of one myself. But here's a couple of thoughts about why such a direct reduction is unlikely:

TSP is run on a fully connected graph with $n$ nodes and $n^2$ edges while HamCycle is run on a graph with $n$ nodes and $m < n^2$ edges (otherwise it would be trivial).
A solution to TSP must pass all nodes and contain no cycles and therefore must contain exactly $n$ edges. We could run HamCycle each on all possible paths of length $n$, starting from the one with the lowest edge-sum and continuing until we reach one that contains a Hamiltonian Cycle, but as there are ${{n^2}\choose{n}} = O(n^{2n})$ such possible paths, this would mean running HamCycle an exponential number of times. I can not see how you can avoid this.

You have most likely thought about this already, so this is mostly to say that you are not the only one who are not able to come up with such a reduction and I suspect that this may be because a reduction either has to be quite complicated or has to leave the graph-world somehow and go back again. Of cause there might exists a reduction that does leave the graph-world but is still simpler than going all the way through SAT, but I do not know of any such reduction.

I'm quite interested to see if anyone has a better answer to this.


Why do black-box deep learning algorithms produce better word similarities than cognitively plausible ones?

The short answer is that we don't know why current ML algorithms work well on a particular dataset, or why other ML algorithms don't.

Most researchers focus on finding ML algorithms that achieve high accuracy, regardless of how they achieve it.  Cognitive plausibility typically isn't a goal.

Generally, across much of computer science, our best methods often differ from how the brain works.  This is true for machine learning, for computer vision, for playing games like chess, and other tasks.  That could be viewed as an opportunity for improvement and a failure of our methods, or as an indication that the methods that will work best for computers might be different from the ones that our brains have evolved.  We just don't know.


Is SAT known to be non-context-free or even non-regular?

One possible encoding of SAT is as a string over the alphabet $\{x,\land,\lor,\lnot,0,1\}$ which encodes a satisfiable CNF. This language is not regular since intersecting it with an appropriate regular expression, we obtain the language semantically representing $x_i \land \lnot x_i$, which is essentially the language of squares $ww$, classically known to be non-regular. The same argument also shows that UNSAT is not context-free. It is highly likely that similar arguments (perhaps using fancier template formulas) would show that SAT is also not context-free.


Express a number with a combination of arithmetic operations and a single number

If you have any number at all, say $N$, then you can write it as $\frac 8 8$ followed by $N-1$ occurrences of $+\frac 8 8$.

The difficulty of the problem lies in finding short sequences of 8s that will work. The best known way is to enumerate all the possibilities.

For instance, with six 8s, write them out in a row and then insert operators between them and after them, to generate all valid reverse-Polish notation expressions which lead to a single result.

As well as the usual arithmetic operators, include a “concatenate” one which, immediately following two 8s, produces 88.

Enumerating all conceivable RPN strings is not hard: there can only ever be five dyadic operators. Filtering them to select just the valid ones is not hard either: probably the best way is to include that process in the process of evaluating each one.


dynamic pseudo-code for simplified coin changing algorithm

Given an integer $M>0$ and $n$ coins with integer values $v_1, v_2,\cdots, v_n$, where $M, n, v_i$ are positive, how can we determine if some of the coins can add up to $M$?

This problem is a common version of subset sum problem. There are many strategies to solve the problem.

Here is the pseudocode by dynamic programming that is about as simple as possible.

Let $s$ be an array of size $M+1$ with default value 0 and starting index 0. Let $s[0]=1$.
For $i$ from 1 to $n$, do:

For $j$ from 0 to $M$, do:

If $s[j]=1$, let $s[j+v_i]= 1$.

If $s[M]=1$, return yes. Otherwise, return no.

Here is an example to illustrate the algorithm. Let $M=7$. Coins are $1,3,3,5$.

$s=[1,0,0,0,0,0,0,0]$.
Here are $s$ at the end of each iteration.

$s=[1,1,0,0,0,0,0,0]$
$s=[1,1,0,1,1,0,0,0]$
$s=[1,1,0,1,1,0,1,1]$
$s=[1,1,0,1,1,5,1,1]$

return yes since $s[7]=1$

We can optimize the algorithm above in various ways.

We can stop the algorithm once we have found $s[M]=1$.
We can change $s$ to a double linked-list, whose elements are the realizable values in increasing order.
We can split the given array of values to two arrays of equal size or sizes with difference 1. Run the algorithm on each of two arrays. Check if we can select one number from each resulting array $s$ such that their sum is $M$, using two-pointer technique.
This last item means all other ways, as always.

Exercise. Adapt the algorithm so that it also tells the least number of coins used if the answer is yes.


If XOR of n distinct numbers is ANDed over one of the number, the result would be zero

It doesn't work, for example if x2 = 0 then xoredResult & x2 = 0 all the time no matter what else the set of numbers contains.

Or for an other example, the set { 1, 2, 3 } xors to zero (so it ANDed by any of its members, or even anything else, yields zero) but contains no repeated elements.


Is it possible to ever define $L(M)$ of a given Turing Machine, $M$?

In answer to your edited question,

  If we accept the definition $L(M)$ as the set of all strings a given Turing Machine $M$ can accept, when I ask can we construct it, in the simplest way I suppose I mean can we list all of the input strings $M$ accepts?

The answer is yes, we can. In technical terms, this asks whether the language accepted by a TM is recursively enumerable.

Here's how to produce the strings that $M$ accepts. Define an enumerator TM, $E$ that acts as follows:

Startup: decide on an enumeration of all possible input strings, $s_1, s_2, \dotsc$. For example, if the input alphabet was $\{0, 1\}$ the strings might be enumerated in order $\epsilon, 0, 1, 00, 01, 10, 11, \dotsc$. It's not hard to see how this could be accomplished. In particular, we could find, for every string $s_i$, the next string in order, $s_{i+1}$.
Then use what's known as a dovetail construction in your enumerator TM $E$:
$$\begin{align}
&\text{repeat for } i = 1, 2, \dotsc \\
&\quad\text{for } k = 1, 2, \dotsc , i\\
&\quad\quad\text{simulate }M\text{ on } s_k\text{ for } i\text{ moves}\\
&\quad\quad\quad\text{if } M(s_k)\text{ accepts}\\
&\quad\quad\quad\quad\text{output } s_k
\end{align}$$

It's not hard to see that every string $s_i$ accepted by $M$ will eventually be displayed (perhaps several times) by the enumerator TM $E$. In effect, we're running $M$ in (simulated) parallel on all possible strings $s_i$. Of course, the enumerator $E$ will run forever, but while it's running it will eventually produce any string in $L(M)$ in a finite time, which is just what you wanted.


Finding the Voronoi cell a point belongs to

I will consider this problem on a Voronoi diagram with $n$ sites and $m$ query points.
Generally, trapezoidal decompositions work nicely for point-location. However, as we here have a subdivision of convex cells, we instead can construct a triangulation of the Voronoi diagram in $O(n)$ that can answer point location queries in $O(\log n)$, which is in fact optimal$^*$. (The complexity for the triangulation is in terms of the edges, but this doesn't matter as the number of edges of a Voronoi diagram is it most $3n-6$).

So, if we are given a Voronoi diagram on $n$ sites and $m$ query points at once, this gives an $O(n+m\log n)$ time algorithm. It makes no difference when we get the query points, so this algorithm is also online in that sense.

It isn't very clear what would be provided if the sites would be 'online', as some edges will be removed and others added when adding sites. If the number of edges added and removed are given, there is a constant number of them and the triangulation can be updated in constant time, so the total running time would remain $O(n+m\log n)$.

Another approach that may not be as good in theory but might work better in practice is to use quadtrees: you can store the set of closest sites for every square in the tree and partition the squares until the size of all those sets is small enough. Then simply locate the square containing the query point and compare all sites in the set for that square to find the nearest site.

*: See the paper: Kirkpatrick, David. "Optimal search in planar subdivisions." SIAM Journal on Computing 12.1 (1983): 28-35.


Prove by Induction that $r_n$ is $O(\log_2(\log_2n))$

To prove $r_n = O(\lg \lg n)$ by induction on $n$, suppose $r_n \le c (\lg \lg n)$ is true for $n$ and consider $r_{n+1}$:

$$r_{n+1} = 1 + r_{\lfloor \sqrt{n+1} \rfloor} \le 1 + c(\lg \lg (\lfloor \sqrt{n+1} \rfloor)) \le 1 + c(\lg \lg \sqrt{n+1}) \\ = 1 + c(\lg (1/2\lg (n+1)) = 1 + c(-1 + \lg \lg(n+1)) \\ = 1-c + c(\lg \lg (n+1)) $$

Take $c = 1$.

If you don't stick to the mathematical induction, there is an easier method with less computation by "change-of-variable" (ignore the things of "taking floor"):

Take $m = \lg n$. Consider another sequence $s$ with $s(m) = r(2^{m})$:

$$r(2^{m}) = 1 + r(2^{m/2}) \Rightarrow s(m) = 1 + s(m/2) = \Theta(\lg m) \quad \text{(by the master theorem)}$$

Substitute $m = \lg n$ into the last equation, we have $r(n) = \Theta(\lg \lg n)$.


It seems you are right. The author probably takes as a standard definition the B+-tree where internal nodes are used as separators.

You should always be prepared for authors that deviate from standard definitions and naming conventions!


Why do AI researchers seem to think that consciousness is a computation?

Consciousness as a computation is not by any means a scientific fact.  Firstly because there's no universally accepted definition of consciousness.
General AI does not have either a widely accepted definition.  There are two hypothesis in relation to consciousness: Weak AI states that you can achieve AGI with the computational models that we know e.g. without "consciousness." Strong AI, on the other hand states that there's something beyond our known computational models that is needed to achieve AGI.
Neural networks as used in machine learning are modeled in biological nervous systems but I don't think anyone has claimed that consciousness or even AGI can be expected from their implementation.
Some proposed consciousness theories worth mentioning are:
Daniel Benett's: Consciousness is nothing special. It's an illusion that you have control of your own decisions.  He backs it up with some experiments that have been done where subjects think they have reached a given decision.  In the experimental setup, however, it's demonstrated that before the subjects confirm that they've taken their decision an external observer can already determine the decision that the subject will take.
Douglas Hofstadter's theory of consciousness is based on the idea that consciousness is an effect achieved through computational deep recursion.
However, as I mentioned in my first point, consciousness is not scientifically defined to be even possible to set up a proper experiment that could determine wether consciousness can be achieved through computation or not.


Did 'Eugene Goostman' really pass the Turing test?

There is no "official Turing test" so there's no concept of "officially pass[ing] the test". Turing described a methodology that one might use to evaluate artificial intelligences.  The organizers of the event that Eugene Goostman won implemented that methodology in a particular way and the program satisfied the criteria the organizers had chosen. In that sense, it passed the test.

Since there is no "official Turing test", it might be more appropriate to say that Eugene Goostman passed a Turing test or even passed a Turing-style test.  It's unlikely that the media would pick up on such subtleties, especially given Turing's fame and the idea of "the Turing test" in the public conscience.


Given two sequences of the same size, how many longest common subsequences can they have?

I understand the question as follows:

Given $n$. How many different longest common consecutive subsequences might two strings of length $n$ have at most?

If this is your question, than consider for example the string $a_1a_2...a_n$ with $a_i\ne a_j$ for $i\ne j$ and the reverse string $a_na_{n-1}...a_1$. The longest common subsequences of those strings are all subsequences of length $1$ $(a_1,a_2,...,a_n)$. Therefore, in your unrestricted question, the maximal number of different longest common subsequences of two strings of length $n$ is equal to the the maximal number of different subsequences with same length, which is $n$ for subsequences of length $1$.

If you restrict the question to strings over a given alphabet of fixed size, lets say $k$, the answer is much more difficult.


Realtime hardware/software versus PC software/hardware, how are these distinct and alike?

In general, the difference between "normal" and "real-time" is some sort of guarantee on the time it takes to complete job. In a normal system, usually you have no guarantees at all. Programs can get interrupted by other programs, the OS scheduler might not be completely fair, the processor does complicated things that alter the runtime between executions of the same code...

For most applications this does not matter.

Real-time systems are built such that one can guarantee that job X is always completed after at most Y seconds. This is important for example for the chip that decides when to deploy air bags--if that takes longer than expected, you're dead. To be able to give these guarantees you have to use special operating systems (or no operating system at all) that guarantees appropriate scheduling. It is also necessary to know a lot of details about the hardware you're using. Does your chip have a cache? What kind of replacement policy does it use? How many cycles does an addition take? Is that always the same number? What's the branch prediction algorithm? etc.

Many people confuse real-time systems with very powerful processors that can churn through data "in real time". But that's not (always) the case. The important thing is not how long it takes in absolute time, the important part is that it never takes longer than expected. There are trade-offs both in hard- and software between throughput (expected computation speed) and predictability (worst-case speed).


(Generally) How to specify asynchronous action with side effects using logic equations

One way to model your example is through program graphs. (See chapter 2 in Principles of Model Checking.) What you can do is model all() as one program, which synchronizes on action 'data' with another program that runs concurrently to all(), let's call it listen(). listen() will have an initial state where it waits until it can synchronize with the all() on action 'data'.

Once you have these two models (or more for bigger examples) you can interleave them, which is a construction that contains all the possible states. Program graph interleaving also preserves shared variables (so globalPacketCounter will be updated correctly) unlike interleaving on transition systems. Though I would be careful about them, since atomicity is not implicit in the models. You can read more about critical actions in section 2.2.2. of the book.

After interleaving of PGs you construct a transition system, which you can transform to a logical equation. And there you have it.


Judging from the wording of your question you are still confused about what it means for a grammar to be linear but I wont address that here. If you want to make the grammar smaller you could do the following: remove $Q_4$ from the right hand side of all production rules and remove all rules which start with $Q_4$. You can do this because $Q_4$ doesn't generate anything so it is effectively useless. Next, notice that $Q_1$ serves only to increase the number of $b$'s by one, so you can remove that, too. We can also do a similar trick to remove $Q_3$ as now all $Q_2$ does is give us one of the following strings by rewriting $Q_3$: $$aa, ac, ca, cc$$.

So the resulting grammar looks like this:

$$S \rightarrow aS | cS | bbQ_2$$
$$Q_2 \rightarrow aa | ac | ca | cc | bbQ_2$$.

I'm not claiming that this is the fewest number of non-terminals for this language, maybe you could/should prove that it is/isn't?


Why is $T(n)=3T(n/4) + n\log n$ solvable with Master Method but $T(n)=2T(n/2) + n\log n$ is not?

Let us use the master theorem as stated on Wikipedia. Consider a recurrence
$$
T(n) = aT(n/b) + f(n).
$$
There are several cases to consider:

If $f(n) = O(n^c)$ for $c < \log_b a$ then $T(n) = \Theta(n^{\log_b a})$.
If $f(n) = \Theta(n^{\log_b a} \log^k n)$ for $k \geq 0$ then $T(n) = \Theta(n^{\log_b a} \log^{k+1} n)$.
If $f(n) = \Omega(n^c)$ for $c > \log_b a$ and $f(n)$ is "reasonable" then $T(n) = \Theta(f(n))$.

In the third case, a function is "reasonable" if there exist $k < 1$ and $N$ such that for $N \geq n$, we have $af(n/b) \leq kf(n)$.

There are also extensions of the second case that handle all values of $k$:

If $f(n) = \Theta(n^{\log_b a} \log^k n)$ for $k > - 1$ then $T(n) = \Theta(n^{\log_b a} \log^{k+1} n)$.
If $f(n) = \Theta(n^{\log_b a} \log^k n)$ for $k = - 1$ then $T(n) = \Theta(n^{\log_b a} \log\log n)$.
If $f(n) = \Theta(n^{\log_b a} \log^k n)$ for $k < - 1$ then $T(n) = \Theta(n^{\log_b a})$.

Now back to your recurrences. The values of $a,b$ and $f(n)$ are:

$a=3$, $b=4$, $f(n) = n\log n$.
$a=2$, $b=2$, $f(n) = n\log n$.

In the first recurrence, $f(n) = \Omega(n^1)$, where $1 > \log_4 3$, and so, according to the third case of the master theorem, $f(n) = \Theta(n\log n)$ (you have to check that the function $n\log n$ is reasonable).

In the second recurrence, $f(n) = \Theta(n^1 \log^1 n)$, where $1 = \log_2 2$, and so, according to the second case of the master theorem, $f(n) = \Theta(n\log^2 n)$.


Sub language is not Turing-recognizable, or could it be?

This is something that confuses many students. The point here is that being subset of another language does not imply much about their difficulty of computation. You can always consider the trivial language $\emptyset$ and $\Sigma^*$ and any other language is between them w.r.t. set inclusion.

Therefore just knowing that a language contains or is contained in a easy to compute language doesn't say anything about the difficulty of computing it.


algoritm to convert a monoid into an automaton

Short answer. See the Cayley graph of the monoid as an automaton.

Details.
Let $L$ be a language recognised by a finite monoid $M$. Then
there is a morphism $\varphi:A^* \rightarrow M$ and a subset $P$ of
$M$ such that $L = \varphi^{-1}(P)$. Take the right representation of
$A$ on $M$ defined by $s \cdot a = s\varphi(a)$. This defines a
deterministic automaton $\mathcal{A} = (M, A, \cdot, 1, P)$. Now, a
word $u$ is accepted by $\mathcal{A}$ if and only if $1 \cdot u \in P$. Since
$1 \cdot u = \varphi(u)$, this condition means $\varphi(u) \in P$ or $u
\in \varphi^{-1}(P)$. Since $L = \varphi^{-1}(P)$, we conclude that
$\mathcal{A}$ recognises $L$.


Technique for converting recursive DP to iterative DP

This DP code is the bottom up solution of the problem. The key is that you start with smaller subproblems and then use these solutions to solve a bigger subproblem.

The data structure we use to store these results is actually holding results to different subproblems of the problem. For eg. let say we want to find a LCS for strings abcbdab and bacdba and let the data structure be a 2D array called cache[][].

The smallest problem is when first string has only a and second string has only b. Here nothing is common. So the LCS has a length of 0 and hence $cache[1][1] = 0$ (1-based indexing). A slightly bigger problem than this would be when first string is a and second string is ba. Here the characters match and hence $cache[1][2] = 1$.

So in this way you can see we can keep growing the problem incrementally and use the previous solutions to have a solution of a bigger size problem.

The reason why we are using minus is because we are just using solutions of subproblems of smaller size represented by smaller indexes in our solution array.

You should not relate recursive and bottom up solutions. There is no direct relation. They are totally different way to solve the same problem. Hence you should keep in mind that you have to solve smaller subproblems and store their results.

I hope this clears the doubt.


Why can't we mimic a dog's ability to smell COVID?

We can actually detect some diseases via smell, and the term to search for is olfaction.  The general problem is known as breath analysis.
However, the research into olfaction and machine learning is rather new (perhaps even surprisingly new).  As Lötsch et al. point out, little research (prior to the very recent research) on olfaction and machine learning has been performed, with a few exceptions:

Quantifying olfactory perception: mapping olfactory perception space by using multidimensional scaling and self-organizing maps, Mamlouk et al., Neurocomputing, 2003.
Relationships between molecular structure and perceived odor quality of ligands for a human olfactory receptor, Sanz et al., Chem Senses, 2008.
Diagnosis and Classification of 17 Diseases from 1404 Subjects via Pattern Analysis of Exhaled Molecules, Nakhleh et al., ACS Nano, 2017.
And the one mentioned above, Machine Learning in Human Olfactory Research, Lötsch et al, Chemical senses, 2019.

I don't know whether the problem in general is harder, but as you are touching  on in your question, the problem is much harder from a hardware perspective.  Where imaging only needs a simple camera, and hearing only need a simple microphone, to detect smell you need a so-called
as chromatography–mass spectrometry instrument. As the Wikipedia article mentions:

Breath gas analysis consists of the analysis of volatile organic compounds, for example in blood alcohol testing, and various analytical methods can be applied.

Here are some pointers from popular science that should assist you in getting into the literature:

Scientists Invent An AI That Can Smell 17 Diseases From Your Breath, Including Cancers

Innovative AI Breath Analyzer Diagnoses Diseases by “Smell”

AI is acquiring a sense of smell that can detect illnesses in human breath


Prove that $\texttt{prefix}(L)$ is regular

It appears that $prefix(L)$ is non-regular.

Let $L = \{0^n 1^n: n \ge 0\}$.  Then, $prefix(L)$, defined to be the set of all prefixes of strings in $L$, is the set of all strings that consist of zero or more $0$'s followed by at most the same number of $1$'s, i.e. $prefix(L) = \{0^n 1^m: m \le n\}$. Intuitively, the reason $prefix(L)$ is nonregular is that a machine that can check whether the number of $1$'s does not exceed the number of $0$'s must store a count of the number of $0$'s in the input seen so far, and so this language cannot be recognized by a machine with a finite number of states.

A formal proof that $L' := prefix(L)$ is nonregular is as follows.  Consider the subset $S = \{0^1, 0^2, \ldots, 0^p\}$.  Any DFA $M$ that recognizes $L'$ must take the inputs $0^i$ and $0^j$ $(i < j)$ to different states because $0^i 1^j \notin L'$ but $0^j 1^j \in L'$.  Hence, the machine $M$ contains at least $p$ states.  But $p$ was arbitrary. This proves there does not exist a DFA (with a finite number of states) recognizing $L'$.

This proof method requires us to find an infinite subset $S$ of pairwise distinguishable prefixes; see online about the Myhill-Nerode theorem.


I think the issue will be that, if we allow each vertex to be considered twice (once per incoming edge type), then we need some way to remember that if we have already visited one "flavour" of a vertex on the path from the BFS root so far, we must avoid visiting its other flavour further along the same path (since such a path would no longer be simple). This seems to entail keeping track of all, or at least all minimal (w.r.t. set inclusion) sets of vertices used on the path to each vertex considered in the BFS so far, which in the worst case would multiply time (and possibly space) requirements by a factor exponential in $|V|$.
Why is it not necessary to explicitly keep track of which vertices have been used in the usual Hopcroft-Karp algorithm for maximum matching in bipartite graphs, which considers each vertex only once? Because the BFS step used in that algorithm to find augmenting paths automatically ensures that all paths from the BFS root are shortest paths, and thus that they are all simple.


A problem about slicing and indexing in numpy in Python

When you slice a Numpy array, you get a special "slice" object, which holds pointers back into the array it was taken from. So if you do the same slicing operation twice, you'll get two different slice objects, which contain pointers to the same array in memory. (If you compare them using == instead of is, you'll see they compare equal, even though they're different objects.)

You can get the same effect with memoryviews, which are in the standard library. Each memoryview is its own object with its own address, but many memoryviews can point into the same data structure.


Why does Kadane's algorithm solve the maximum sub-array problem?

Suppose $A[1..N]$ is your array for which you want to find maximum sum sub-array. Construct $B[1..N]$ such that $B[j]=max (\sum A[k] \mid k \le j,k \ge i)$ ($i$ is some starting index for which B[j] is maximum). So it boils down to $B[j]=max(B[j-1]+A[j],A[j])$ (here I am assuming that empty sub-array isn't allowed in answer). And then find the maximum $B[j]$ for all $j \in [1..N]$. Now this can be done in constant space since we only need result of the previous iteration( for $j$ we need only $B[j-1]$) and the maximum sub-array sum which has occurred till now. Now compare these two ideas and you will get you answer.


A regular set is the same thing as a regular language. You haven't explained how to encode integers, but suppose you encode an integer in binary notation, MSB first; so each zero is represented as $0$, and all other numbers start with $1$. The set of even positive integers is the represented by the regular expression $1(0+1)^*0$ (why?), and so is regular. The set of non-negative integers divisible by $5$ is also regular, since there is a DFA that accepts it; the minimal DFA has $5$ states corresponding to the value of the current prefix modulo $5$, which is updated in the obvious way. I'll let you figure out the details.


Extracting the set of chains from a partial order

Yes there is, have a look at :

Chen, Yangjun, and Yibin Chen. "On the Decomposition of Posets." Computer Science & Service System (CSSS), 2012 International Conference on. IEEE, 2012.

and also this:

Daskalakis, C., Karp, R. M., Mossel, E., Riesenfeld, S. J., & Verbin, E. (2011). Sorting and selection in posets. SIAM Journal on Computing, 40(3), 597-622.


How to prove that knapsack has no competitive algorithm

Let's check the definition of a competitive algorithm, in your specific case. For simplicity, we assume that $W = 1$.
We can describe an algorithm for Knapsack as a sequence of functions $A_n\colon \mathbb{R}_+^n \to \{0,1\}^n$, describing which items are taken given their weights, which satisfies the following two properties:

The result fits inside the knapsack: for all $w \in \mathbb{R}_+^n$, if $x = A_n(w)$ then $\sum_{i=1}^n x_i w_i \leq 1$.
The algorithm is online: for all $w \in \mathbb{R}_+^n$ and $m \leq n$, if $x = A_n(w)$ and $y = A_m(w_1,\ldots,w_m)$ then $x_i = y_i$ for $i = 1,\ldots,m$.

The algorithm is furthermore $c$-competitive if:

For all $w \in \mathbb{R}_+^n$ and $o \in \{0,1\}^n$ such that $\sum_{i=1}^n o_i w_i \leq 1$, if $x = A_n(w)$ then $\sum_{i=1}^n x_i \geq c \sum_{i=1}^n o_i$.

(Your definition might put $c$ on the other side of the inequality.)

Suppose now that $A$ is a $c$-competitive algorithm, where $c > 0$, and let $N = \lceil 1/c \rceil + 1$, so that $cN > 1$.
Consider $w_1 = 1$ and $o_1 = 1$, which satisfies $o_1 w_1 = 1$. By Property 3, $x_1 = A_1(w_1)$ satisfies $x_1 \geq co_1 = c > 0$, and so necessarily $x_1 = 1$.
Now consider $w = 1,1/N,\ldots,1/N$, where there are $N$ many $1/N$'s, and $o = 0,1\ldots,1$, where there are $N$ many $1$'s. These vectors satisfy $\sum_{i=1}^{N+1} o_i w_i = 1$. Let $x = A_{N+1}(w)$. By Property 2, $x_1 = A_1(w_1) = 1$. By Property 1, $x_2 = \cdots = x_{N+1} = 0$. By Property 3,
$$1 = \sum_{i=1}^{N+1} x_i \geq c\sum_{i=1}^{N+1} o_i = cN, $$
which contradicts the choice of $N$. This contradiction shows that no $c$-competitive algorithm exists.

Here is how this proof would usually be presented. Consider any competitive algorithm. We start by presenting it an item of weight $1$. If the algorithm doesn't take the item, then we immediately end the stream, and so the algorithm is revealed to be $0$-competitive (comparing to the solution which does take the item). Otherwise, we present it $N$ more elements of weight $1/N$. The algorithm's knapsack is already full, so it cannot take them. Since instead it could have taken only the $N$ low-weight elements, this shows that the algorithm isn't even $1/N$ competitive. Since $1/N$ can be arbitrary small, we reach a contradiction.
Notice how this argument is much less formal and much more "intuitive", if not particularly shorter (though this is only an artifact of this particular argument being so simple). We usually present it in the latter form, keeping in mind that we could translate it in principle to the more formal form of the former proof. This is no different than the difference between written proof and completely formal proof in the sense of formal logic.


Undecidability of the language of all Turing Machines with repeat strings as their language

Imagine a fixed machine $M$ and a fixed string $w$ and then let $M'$ be the machine that on input $x$ simulates $M$ on $w$, and if that simulation halts then answers Yes if $x=ab$ and No otherwise.
How could you decide whether $M'$ belongs to your language? You would need to know whether $M$ halts on $w$! As in that case $L(M')=\{ab\}$ and otherwise $L(M')= \varnothing$.
Details up to you :)


How to model conditionals with first-class functions?

The usual encoding of booleans, due to Church, is

$$
{\sf true} = \lambda x. \lambda y. x
\qquad
{\sf false} = \lambda x. \lambda y. y
$$

Roughly, "true" is the function which takes two arguments $x,y$ (first takes $x$, then also takes $y$) and returns the first one. Instead, "false" returns the second one.

If-then-else is then encoded as applying an encoded boolean to the "then" and "else" branches. In this way, the boolean chooses the right value to return.

$$
{\sf if}\ b\ {\sf then}\ t\ {\sf else}\ e = b\, t\, e
$$

It is then easy to check the so-called "$\beta$" laws:

$$
{\sf if\ true\  then}\ t\ {\sf else}\ e
= {\sf true}\, t\, e
= (\lambda x.\lambda y.x)\, t\, e
= (\lambda y.t)\, e
= t
$$

and

$$
{\sf if\ false\  then}\ t\ {\sf else}\ e
= {\sf false}\, t\, e
= (\lambda x.\lambda y.y)\, t\, e
= (\lambda y.y)\, e
= e
$$

Essentially, these laws state what happens when you "construct" a boolean (using the constants $\sf true, false$), and then "destruct" it later on (using it in an $\sf if\ then\ else$).

Using functions in this way, one can write encodings for all the usual data types, like naturals, pairs, variants, lists, trees, etc.


First, notice that it is enough to compute how many elements in $a_1,\ldots,a_E$ are less than $X$. (Why?)

Second, assume for simplicity that $N$ is a power of 2. We partition $\{1,\ldots,N\}$ into intervals in $\log N$ ways: as a single interval of length $N$, two intervals of length $N/2$, four intervals of length $N/4$, and so on. We sort each of these. This takes time $O(N\log^2 N)$. (Why?)

Third, given $E$ and $X$, write $a_1,\ldots,a_E$ as a sum of $O(\log N)$ intervals  of the kind we sorted above (use the binary expansion of $E-1$). Find the correct count for each of them in time $O(\log N)$ by searching for $X$ in the sorted interval, and compute the sum.


Well, I don't know what you expect to get as an answer, but in the comments you already got that if you haven't seen them used is due to two reasons.

The main one is probably that maybe you haven't had the need to solve problems in which they are needed, yet, and
that the problems, like finding a solution of a system of polynomial equations. are more efficiently done by algorithms that target exactly that problem, like Newton's method. Groebner bases can end up with large degrees for systems with relatively few variables and degrees larger than one.

The usefulness of Groebner bases becomes clear once you study what they are. They are  a form in which to put a system of equations. The form is canonical once you fix a way to order monomials in several variables. If you have seen some commutative algebra, Groebner bases are a canonical set of generators of ideals in a polynomial ring $I\subset R=K[x_1,x_2,\ldots,x_n]$.
When you choose a convenient monomial order it happens that the form has the same property as the row echelon form for linear system of equations, that the equations have less and less variables until eventually (for a system that has finitely many solutions) the last equation is a polynomial in one variables. So, incidentally you get out of it a method to find all solutions by backward substitution. You find all solutions of this polynomial in one variable, by either Newton's method, or perhaps some method that finds them all roots at once. This gives you the possible values of one of the variables. Then you substitute these values in the previous equations and repeat the process with them. See here for one way to do these steps.
Example: For the system $$\begin{align}x^2+y^2-1&=0\\xy-4&=0\end{align}$$
you get $$\begin{align}4x+y^3-y&=0\\y^4-y^2+16&=0\end{align}$$
Try it with Singular, by inputting
// Define the ring R[x,y] of polynomials in variables x,y;
// and lexicographical ordering to order monomials.;
ring r = 0,(x,y),lp;
// The ideal generated by those two polynomials. ;
ideal I =(x^2+y^2-1,x*y-4);
// The same ideal, but now generated by its Groebner basis.;
ideal GI=groebner(I);
// Print it.;
GI;

As you see, Groebner basis is not an algorithm, but a form for a system, and its goal is not to find one solution, but to put the system in a form that helps compute properties of the set of solutions as a whole. Modulo technicalities, the set of solutions is called an algebraic variety. Problems that you might need to solve could be, for example,

What is the intersection of algebraic varieties? More explicitly, suppose you have a mechanical arm with both ends attached to two fixed points and having two or three elbows (joints). What are the positions that these elbows can be? It is an algebraic variety that can be described first as the intersection of the equations that you get by imposing the length of each segment of the arm and the condition on the fixed points at each end.

Parametrization of algebraic varieties. If the mechanical arm above had only one elbow, its positions would be a circle. Perhaps you know that $t\mapsto (\cos(t),\sin(t))$ parametrizes a circle, when $t\in[0,2\pi)$, but it could be better to get a rational parametrization, like $t\mapsto(\frac{1-t^2}{1+t^2},\frac{2t}{1+t^2})$, for $t\in[-\infty,\infty]$. Such parametrizations always exist. You compute them by an algorithm that uses Groebner bases among other things.

Maybe you need the inverse problem of (2), implicitization. You want a robot arm that can cut this shape that the design team chose for the silhouette of a car. They sure like their Bezier curves. They happen to be algebraic.

You want your computer to discover the proofs of all synthetic geometry problems that you did in high school. After sufficient squaring, the hypotheses and the thesis are polynomial equations. So, you only need to check that the first can reduce the latter to $0=0$. This a particular case of problem (1).


Using visible line segments to compute a visibility polygon

First, assume we already have a list $L$ with all segments in $P$ that are at least partially visible from $p$, ordered by the smallest angle $\theta$ such that a segment is visible from $p$ at angle $\theta$. (This can be done with a (angular) sweep line algorithm in $O(n\log n)$)

Now, observe that if a line from $p$ to some point on the segment $s_i$ in $L$ intersects some segment of $P$, it must intersect either $s_{i-1}$ or $s_{i+1}$ (be careful to wrap around the ends of the list), i.e. one of the neighbours of $s_i$.

Therefore, we can construct the visibility polygon as follows: iterate over all segments $s_i$ in $L$ and compute the visible sub-segment of $s_i$ using the segments $s_{i-1},s_{i+1}$. (call it $s_i^*$) Add it to your visibility polygon and then add the lines connecting the endpoints of $s_i^*$ with $s_{i-1}^*$ and $s_{i+1}^*$ to the visibility polygon (if they aren't already connected directly).


Proof for values of d with d:= ||L|| - N(L) with $d \in \mathbb{Z}$ and N(L) Nerode Index

In order to make the question nontrivial, you have to assume that $L$ is finite. You haven't specified what the alphabet is, so I will assume that the alphabet is arbitrary.
First, let us show that $N(L) \leq \|L\|+2$. We can construct a DFA for $L$ whose states consist of all prefixes of words in $L$, together with a failure state. This DFA contains an initial state (corresponding to the empty prefix), a failure state, and one state for every non-empty prefix. In particular,
$$
N(L) \leq 2 + \sum_{w \in L} |w| = 2 + \|L\|.
$$
In other words, $d \geq -2$.
Second, let us consider the language $L_\Sigma = \{\sigma : \sigma \in \Sigma\}$ over an alphabet $\Sigma$. The minimal DFA for this language contains three states, and so the value of $d$ for $L_\Sigma$ is
$$
\|L_\Sigma\| - N(L_\Sigma) = |\Sigma| - 3.
$$
As $\Sigma$ ranges over all possible alphabets, we obtain all values which are at least $-2$.


In a bloom filter, why does the optimal number of hashes *increase* with the number of bits in the filter?

This balances two considerations:

The more hash functions you have, the more bits will be set in the Bloom filter when you create the filter (because each element you insert causes up to $k$ bits to be set in the filter).  The more bits that are set, the higher the risk of false positives.
The more hash functions you have, the less likely that one of them triggers a false positive (because a false positive will be triggered only if all of the bit positions you inspect are set, and the number of bit positions you inspect is equal to the number of hash functions).

So, increasing the number of hash functions ($k$) has two effects, one of which increases the likelihood of false positives, and the other of which decreases the likelihood of false positives.  To figure out how to balance those two, you need to work through the math.

I suspect your intuition was missing the second factor, and once you take that into account the result will feel less absurd.

I agree that if you hold $k,n$ fixed and increase $m$, then the false positive probability will decrease.  But it would decrease even more if you held $n$ fixed and increased both $m$ and $k$ (due to the way the math works out, and due to the second consideration above).


Bulk-loading R-tree with data with extent

Yes, there is. It's called OMT, for Overlap Minimizing Top-down, and the first description of the algorithm can be found here: http://ftp.informatik.rwth-aachen.de/Publications/CEUR-WS/Vol-74/files/FORUM_18.pdf


What is the difference between variables and pointers?

Your question is interesting in several ways, as it requires careful
distinctions for several issues. But your vision seems to me to be
essentially correct. I did not read your reference before writing most
of this answer to avoid biasing my answer.

First, your statement Variables are symbolic names for memory
addresses, it is almost correct, but confuses the concept and its
usual implementation. A variable is actually just a container that can
contain a value that can be changed. Usually, this container is
implemented on a computer as a bock of memory space, characterized by
and address and a size since variables may contain object that
require representations with more or less information.

But I will consider mostly a more abstract point of view of the
semantics of languages, independently of implementation techniques.

So variables are just containers from an abstract point of view. Such
a container need not have a name. However, languages often have
variables that are named by associating to it an identifier, so that
uses of the variable can be expressed by the identifier. A variable
can actually have several identifiers through various aliasing
mechanism. A variable can also be a subpart of a larger variable: an
example is a cell of an array variable, which can be named by
specifying the array variable and the index of the cell, but could as
well be also associated with identifiers through aliasing.

I am deliberately using the word container that is somewhat neutral, to avoid invoking other words that may be semantically loaded technically. It is actually close to the concept of reference described in wilipedia, which is often confused with a memory address. The word pointer itself is often understood as a memory address, but I do not think that is meaningful when considering most high-level languages, and probably inappropriate in the discussion paper you refer to (though addresses can be used), as it is inappropriately referring to a specific implementation. However, it is appropriate for a language like C, which is supposed to be much closer to
implementation concepts and the machine architecture.

Actually, if you look at variables or values at the implementation
level, there may be several complex systems of indirection, of
"machine level pointers", but that are (and should be) invisible to
the user, so that the abstract point of view I develop can be valid.
For most programming languages, the user should not have to worry, or
even know, about implementation, as implementation can vary a lot for a given
language. This may not be true for some languages, such as C, that are
intentionally close to the machine architecture, as an advanced
substitute for assembly languages that are in almost direct relation
to explicit binary coding, but far too low level for convenient use in most situations.

What the user of a language should know, and sometimes it should be even less than
that, is what are values and associated operations, where they can be
contained, how they can be associated to names, how the naming system
works, how can new kinds of values be defined, etc.

So another important concept is identifiers and naming. Naming an
entity (a value) can be done by associating an identifier with a value
(usually in a declaration). But a value can also be obtained by
applying operations to other named values. Names can be reused, and
there are rules (scoping rules) to determine what is associated to a
given identifier, according to context of use. There are also special
names, called litterals, to name the values of some domains, such as
integers (e.g. $612$) or boolean (e.g. true).

The association of an unchanging value with an identifier is usually
called a constant. Litterals are constants in that sense.

"Value containers" can also be considered as values, and their
association with an identifier is a variable in the usual "naive"
sense that you have been using. So you might say that a variable is a
"container constant".

Now you might wonder what is the difference between associating an
identifier with a value (constant declaration) or assigning a value to
a variable, i.e. storing the value in the container defined as a
container constant.  Essentially, declaration may be seen as an
operation that defines a notation, that associate an identifier which
is a syntactic entity to some value which is a semantic entity.
Assignment is a purely semantics operation that modifies a state,
i.e. modifies the value of a container. In some sense, declaration is
a meta concept with no semantic effect, other than providing a naming
(i.e. syntactic) mechanism for semantics entities.

Actually, assignments are semantic operations that occur dynamically
as the program is executed, while declarations have a more syntactic
nature and are usually to be interpreted in the text of the program,
independently of execution. This is why static scoping (i.e. textual
scoping) is usually the natural way to understand the meaning of
identifiers.

After all this, I can say that a pointer value is just another name for a container,and a pointer variable is a
container variable, i.e. a container (constant) that can contain another
container (with possible limitations on the containing game imposed by
some type system).

Regarding code, you state [pointers] might indicate the entry point
to a section of code and can be used to call that code. Actually this
is not quite true. A section of code is often meaningless alone
(from high level or implementation point of view). From a high-level
point of view, code usually contains identifiers, and you have to
interpret these identifiers in the static context where they were
declared. But there is actually a possible duplication of the same
static context, due essentially to recursion which is a dynamic
(run-time) phenomenon, and the code can only be executed in an
appropriate dynamic instance of the static context. This is a bit
complex, but the consequence is that the proper concept is that of a
closure that associate a piece of code and an environment where the
identifiers are to be interpreted. The closure is the proper semantic
concept, i.e. is a properly definable semantic value. Then you can
have closure constants, closure variables, and pointers to closures,
which are containers that can contain another container containing a
closure.

A function is a closure, usually with some parameters to define or
initialise some of its entities (constants and variables).

I am skipping many variations on the uses of these mechanisms.

Closures can be used to define OO structures in imperative or
functional languages. Actually, early work on OO style (probably
before the name) was done that way.

The paper you reference, which I skimmed quickly, seems to be an
interesting one, written by a competent person, but possibly not an
easy reading if you do not have significant experience with a variety
of languages and their underlying computational models.

But remember: many things are in the eyes of the beholder, as long as
he preserves a consistent view. Points of view may differ.

Does this answer your question?

PS: This is a long answer. If you consider some part of it inadequate, please be explicit about which it is. Thank you.


Disadvantages to using simple step functions for activation in neural networks?

The disadvantage would be that your fitness landscape would look less smooth (a small change in your weights may result in a big change in the output or no change at all). This may affect the convergence speed of your GA, since small changes in the chromossomes may not produce differences in fitness, rendering it blind to some benefical changes.
If your problem is performance, I'd suggest to try the hard ReLU activation function instead of a sigmoid one.


How to draw an LTS based on the parallel process "|" in CCS Milner's logic?

The last LTS in your question is wrong. It should be a diamond-shaped graph, where on one side you perform action $a$ then $b$, and on the other you perform action $b$ then $a$, both sides leading to $\sf Nil$.

This is because the $a$ action is run in parallel w.r.t. the $b$ action, so we get all the possible "interleavings" between such events.

The fixed LTS you posted in the comments looks right, instead.


Log-Space Reduction $USTCON\le_L CO-2Col$

Let USTCON2 be the following problem: given a graph $G$ and two vertices $s,t$, decide whether there is a walk from $s$ to $t$ of even length. Let us show first that USTCON2 reduces to co2COL.

Given a graph $G = (V,E)$ and two vertices $s,t$, construct a new graph whose vertex set consists of two copies of $V$. For every $(a,b) \in E$, connect $a$ in the first copy to $b$ in the second copy, and $a$ in the second copy to $b$ in the first copy. So far the graph is bipartite. Now connect $s$ and $t$ in the first copy. The new graph is bipartite iff there is no path of even length from $s$ to $t$ in the original graph.

Now let us reduce USTCON to USTCON2. Given a graph $G = (V,E)$ and two vertices $s,t$, add two new vertices $x,y$, and edges $(s,x),(x,y),(y,s)$. There is a walk from $s$ to $t$ in the original graph iff there is a walk of even length from $s$ to $t$ in the new graph.


Let $g(i,j)$ be the gas consumed when travelling to destination $i$ with car $j$.

Guess the optimal order $\langle c_1, c_2, c_3 \rangle$ of cars (there are only $3! = 6$ possible permutations).

Define $OPT[i,j]$ as the minimum amount of gas needed for reaching the first $i$ destinations using cars $c_1, \dots, c_j$ in this order, with the constraint that each car must be used at least once. If no feasible solution exists then $OPT[i,j] = + \infty$.

According to the above definition, you have $$OPT[1,j] = \begin{cases}
g(1, c_1) & \mbox{if } j=1 \\
+\infty & \mbox{if } j>1
\end{cases}$$.

and, for $i=2, \dots, n$:

$$OPT[i,j] = g(i,c_j)+
\begin{cases}
OPT[i-1, j] & \mbox{if } j=1 \\
\min\{ OPT[i-1, j], OPT[i-1, j-1] \} & \mbox{if } j>1
\end{cases}.$$

The solution to your problem is $OPT[n,3]$, which can be computed in $O(n)$ time using dynamic programming.


Recurrence relation of quicksort depending on its pivot

When the 4th smallest element is always chosen as a pivot then the recurrence relation is
$$T(n) = T(n/4)+T(3n/4) + \mathcal{O}(n).$$

If we look at the recursion tree we will see that the left branch has $\log_4 n$ depth and the right has $\log_{4/3} n$ depth. At each step, until the leftmost branch terminates, the sum of levels is equal to $cn \in \mathcal{O}(n)$, for the remaining the levels the sum $\leq cn$. Therefore in the worst case calculation, if we assume all have depth $\log_{4/3} n$ and have $cn$ cost then the cost is;

$$c n \log_{4/3} \in \mathcal{O}(n\log n)$$


Relationship between MIPS (Million Instructions per second) and operating frequency of a processor

Only if you double the speed of everything. Which you can’t in practice.


How to shift a matrix by x rows and y columns in the most efficient way?

I could think of a time-efficient solution which is not good in terms of memory.

We will carry out duplication of the given array.

For eg.

Initial Array:

We can have 4 duplicate copies of the same array, each attached to form a huge square.

Big Array looks like:

Within this Big Array, let me call my result as the Result Array.

Initially, when we have no rotation involved, the result array looks like:

The Blue colored box represents the result array.

The top_left_index of the result array = (0, 0). [Image above]

After that, suppose we rotate 1 row, the blue colored box shifts down as follows:

The top_left_index of the result array = (1, 0). [Image above]

After that, suppose we rotate 1 column, the blue colored box shifts right as follows:

The top_left_index of the result array becomes = (1, 1). [Image above]

After that, suppose we rotate 1 row, the blue colored box shifts down as follows:

The top_left_index of the result array becomes = (2, 1). [Image above]

After that, suppose we rotate 2 cols, the blue colored box shifts right as follows:

The top_left_index of the result array becomes = (2, 3). [Image above]

This is how the entire logic works.

We just need to store the top left index of the blue box. Whenever asked for the result, we can display the elements of the blue-colored box.

So, the entire problem boils down to calculating the top left index of the blue box.

Time Complexity of changing the index: O(1)

Space complexity: O(n^2)

However, there exist corner cases that need to be handled. Once such corner case is as below:

Handling this corner case is not difficult. In case we feel that the resultant array's bounds are overflowing the boundary of the Big array, we need to reduce the value of our top_left_index such that the entire square fits in the array.
For eg.,

In the above image, the top_left_index (2,4) overflows the bounds of Big Array.

We simply reduce the overflowing index by the respective dimension of our original array and make it:

(2, 4 - 3 ) = (2, 1).

Now, things look beautiful again.


What does canonicity property mean in Type Theory?

There are potentially multiple ways of presenting canonicity (and I think complications depending on the theory). However, I think the simplest way to think about it is from the perspective of a programmer wanting to use the type theory to compute something. For instance, we might want to compute some natural number satisfying some specification we've come up with. So we define:

data ℕ : Type where
  zero : ℕ
  suc : ℕ → ℕ

These constructors we've used have meaning to us, and we want the answer to be written in terms of them. So, for instance, suc (suc (suc zero))) is a valid, meaningful result of our computation.

Canonicity says essentially that every closed computation of type ℕ we write is able to be reduced to such a meaningful numeral. Or, if we don't want to talk about 'reduction', it is "convertable" or "judgmentally equal" to such a numeral, or similar. But of course, if we're programmers, we probably want that convertability to eventually turn into reduction for at least some stuff.

The reason homotopy type theory (at least, at the time of the book) does not have this property is that there was no known computational behavior for univalence; it was just added to the theory as an 'axiom,' and you could then use it in ways where computations would just get stuck. So, in that situation, you can sometimes write closed terms of type ℕ that might look like

J (...) (ua ...) ...

But do not compute further than that, because J has no way of reducing when applied to ua .... So you can write terms that don't give you a meaningful answer.

A simpler example is, I think, also mentioned in that article. You can add some variety of excluded middle to have a 'classical' type theory. To do this, we can add an axiom like:

exm A : A + ¬ A

that says that every type either has a value or is empty. However, unless your types are quite simple, it is impossible to accurately decide such a thing, so this axiom will not be able to compute to either inl x or inr y, and case analysis on it will just get stuck.

This may not be a problem if you are just using type theory in a way analogous to formal logic. You can add axioms that get stuck, and add more axioms about the things that get stuck to prove specific things you desire, but those will also get stuck. For instance perhaps we could add:

uaId : ua id ≡ refl
uaAp : subst (λ A → A) (ua f) x ≡ f x

And so on. These will allow us to manually prove certain reduction rules, so that we can manually prove that some expression we've written is (according to our axioms) the same as some concrete number. However, for someone who desires to treat type theory more like executable mathematics that will automatically compute answers, canonicity is an important property.


Can this CFG be written into an equivalent LL(1) grammar?

The comment above is correct. What is referenced here is generally called a "first-follow set clash" and occurs when a non-terminal is nullable, and has non disjoint first and follow sets. You can try to remove these by substituing for the nullable non terminal (shown for your grammar below). However, this process might result in a loop. If that happens, your grammar can't be transformed to LL(1).

Note that . simply denotes esp.

S → a S b S
|   c S2 S
|   d S1 S
|   .
S1 →    a S b S1
|   c S2 S1
|   d S1 S1
|   c .
S2 →    a S b S2
|   c S2 S2
|   d S1 S2
|   d .

S2 =    S d. (uh-oh, we've gone in a loop here)
S1 =    S c.


Did I correctly prune this min-max search tree using alpha-beta pruning?

I once implemented this in common lisp and running my program on your tree tells me that the pruned nodes are the one you marked and also the rightmost leaf and its parent.  The output of the program gives $\alpha$ and $\beta$ values for each node (if you mark from A through X in a BFS manner, left-to-right.  Then O and J are pruned).

MIN: K     -INFTY    11        [v:11]
MIN: L     11        INFTY     [v:9]
MAX: E     11        INFTY     [v:11]
MIN: M     -INFTY    4         [v:4]
MIN: N     4         11        [v:13]
MAX: F     4         11        [v:13]
MIN: B     -INFTY    11        [v:11]
MIN: P     11        12        [v:12]
MIN: Q     12        INFTY     [v:8]
MIN: R     12        INFTY     [v:4]
MAX: G     12        INFTY     [v:12]
MIN: C     11        12        [v:12]
MIN: S     12        INFTY     [v:9]
MIN: T     12        13        [v:13]
MIN: U     13        INFTY     [v:1]
MAX: H     13        INFTY     [v:13]
MIN: V     12        13        [v:12]
MIN: W     12        13        [v:9]
MAX: I     12        13        [v:12]
MIN: D     12        13        [v:12]
MAX: A     12        INFTY     [v:12]
12
21
T


Complexity of class finding selection of entries in matrix

Let $U$ be the set of rows in the given matrix and $V$ the set of columns. For each $x$ at row $i$ and column $j$, add an edge between row $i$ and column $j$. You will have an (unweighted) bipartite graph $G=(U,V, E)$. The problem is to find a perfect matching, which is basically the same as find the maximum matching of $G$.
There are various algorithms that compute the maximum cardinality matching. For example, The Hopcroft–Karp algorithm runs in $O(\max(|E|\sqrt {|V|}, |V|^2)$.
So, we can say that the complexity class of the problem in the question is in $O(n^{2.5})$ since $|E|\le n^2$ and $|V|= 2n$.


what’s wrong with this quantum key distribution scheme?

No, not really.  The main problem with this protocol is that it is less practical than BB84.

Less practical

Bob is a benign party.  To measure a q-bit, you need to know what basis to measure it in before you can measure it (e.g., before you can measure a photon, you need to have your measurement apparatus set up in the appropriate basis).  Ordinarily, we'd like to measure it as soon as we receive it.  Your protocol doesn't allow that.

Your protocol requires Bob to receive the q-bit and then decide later what basis to use to measure it.  That means Bob will need some way to store the q-bit for later measurement.  There might be a way to do that (e.g., put the photon into a long delay loop), but it will probably increase complexity and expense.

It's not reasonable to expect legitimate parties to have to do that just to communicate.  And in any case, BB84 doesn't require parties to jump through those hoops.  So your scheme is less practical than BB84.

Side note on security:

With your protocol, it is important that step 4 (including Bob's confirmation) be over an authenticated channel.  Without that, there is a security problem.

BB84 provides the following security property: if the final reconciliation phase is done over an authenticated channel (not necessarily secret; it can be public communication; but it does need to be authenticated), and if the parties don't abort, then the resulting secret will be known only to Alice and Bob.  In particular, no adversary -- not even an active man-in-the-middle attacker -- can arrange to learn the secret.

Your protocol doesn't offer that guarantee, if step 4 happens over an insecure channel.  With your protocol, there's a trivial way that a man-in-the-middle can arrange to learn the secret, with zero chance of being detected.  When Alice sends the q-bits, the adversary Mallet intercepts and stores them.  Mallet then sends a confirmation that the q-bits were received to Alice (pretending that this came from Bob).  When Alice sends $y$, Mallet intercepts and learns $y$.  Now Mallet decodes all the q-bits using $y$, and learns $x$.  In the second phase, Mallet encodes $x$ into new q-bits and sends those q-bits to Bob (pretending they came from Alice).  When Bob responds that he has received them, Mallet sends $y$ to Bob (pretending it came from Alice).  Now Bob will decode his q-bits, obtain the same value $x$, send back some of the bits of $x$ to Alice, everything will match, and both Alice and Bob will think that they have obtained a secure key -- but Mallet actually knows that secret key, since Mallet has learned $x$.  This attack works even if steps 5 and 6 are done over an authenticated channel.

I suspect it suffices to require step 4 to also go over an authenticated channel (I'm not 100% sure; that would require proof; but it looks like it to me).


In the case $n\leq s<2n,dpw\geq n, 2n<dpw+s<(\phi+1)n$, a possible way of finding all soldiers wins is following this approach:

Have the soldiers attack only the castle in the first 2 days, then
once destroyed attack the defenders on the subsequent days. This
gives you the minimum number of days solution.
Have the soldiers attack the castle on the first day, then have
$n-1$ of the soldiers attack the castle on the second day and $1$ of
the soldiers attack the defenders on that second day. Finally
destroy the castle on the third day and let the soldiers battle it
out in the remainder of the days. This gives you the minimum number
of days solution+1 (if there is one).
Have the soldiers attack the castle on the first day, then have
$n-2$ of the soldiers attack the castle on the second day and $2$ of
the soldiers attack the defenders on that second day. On the third
day, the remaining soldiers but 1 attack the castle and the rest
attack the defenders. Finally on the fourth day the remaining
soldiers destroy the castle and let the soldiers battle it out in
the remainder of the days. This gives you the minimum number of days
solution+2 (if there is one).
etc
The basic idea of this approach is to consider the cases where the castle is destroyed on day 2, on day 3, on day 4, etc

For this to work well it would be useful to know not just the minimum number of days it takes for the soldiers to win but also the maximum number of days it takes. It might be possible to find this mathematically.

Also note that there are cases like this

solution 1 (3 rounds)

  start:'soldiers': 10, 'defenders': 0, 'castle-strength': 14

  round1:'soldiers': 10, 'defenders': 10, 'castle-strength': 4

  round2:'soldiers': 6, 'defenders': 4, 'castle-strength': 0

  round3:'soldiers': 6, 'defenders': 0, 'castle-strength': 0

solution 2 (5 rounds)

  start:'soldiers': 10, 'defenders': 0, 'castle-strength': 14

  round1:'soldiers': 10, 'defenders': 10, 'castle-strength': 4

  round2:'soldiers': 9, 'defenders': 11, 'castle-strength': 3

  round3:'soldiers': 4, 'defenders': 5, 'castle-strength': 0

  round4:'soldiers': 3, 'defenders': 1, 'castle-strength': 0

  round5:'soldiers': 3, 'defenders': 0, 'castle-strength': 0

i.e. there might be gaps (there is no solution in 4 rounds)


Does 1NF require that there can be no duplicate rows?

What was called 1NF in the past is considered nowadays part of the definition of the Relational Data Model itself: each attribute must be a single value, neither composed, nor repeated. When we talk about relations we assume implicitly this fact, since structures with non-flat attributes are not considered proper relations.

Note, however, that there exists alternative models, called non-1NF models or NRC which are based on the concept of relations with possibly other relations as values inside tuples (so it is a kind of Nested Relational Model). Such models, presented in the scientific literature but not implemented in commercial systems, are in some sense a sort of “bridge” towards the late object-oriented data model, that allow more complex kind of data (and that have a concept of association which differs from that of foreign key).

A different aspect is that relations are sets, and not multisets (that is they cannot contains duplicate rows). This is a basic principle of the Relational Data Model: we assume that a relation is just a set, stop. For more details, see this answer.

But you should keep in mind the these are mainly theorical aspects, useful when reasoning about relations, about languages to operate on them (for instance the Relational Algebra), and about theories developed on them (for instance the Normalization Theory).

In practice, however, things can be quite different: for instance in Relational Database Management Systems you can have “relations” without keys or unique attributes, so that they can have duplicate rows. Also, you can have composed data types for attributes of records, like arrays (or, worse, people sometimes put multiple values in an attribute maybe as a single string with commas separating the intended values).


Proof that class of languages accepted by DPDA by empty stack is not closed under union

Indeed, the requirement that the DPDA accepts by empty stack has some "severe" consequences.
Under the standard definitions, an automaton with empty stack is blocked from further computations, as normally one would pop a stack single symbol at each computational step. As a consequence DPDA languages by empty stack are prefix-free: if the accepted language contains a string $x$ then it will not contain any string $xy$ with $y\neq \varepsilon$.
Now the language $\{a,aa\}$ is an easy counterexample.


Algorithm which finds the maxmal solution that satisfies the following constraints

You want a solution $x$ such that

$$x \equiv b_i \pmod{a_i}$$

for all $i$.  By the Chinese remainder theorem, this is either impossible or it is equivalent to

$$x \equiv b \pmod{a}$$

where $a = \text{lcm}(a_1,\dots,a_n)$ and $b$ can be computed using the Chinese remainder theorem.  In other words, the solutions are all of the form $b$, $b+a$, $b+2a$, $b+3a$, etc.  From there it is easy to find the largest solution $x$ such that $x\le U$.


resource on translating imperative programs to functional programs

There probably are automated ways of doing it, but the result will be a unreadable mess. You have to understand what the imperative program is doing and rethink it as a functional program. Not easy.

The point is that many imperative algorithms have a recursive idea behind them (think binary search, mergesort, quicksort, any tree walking), there it is recognizing that starting point and write it functionally.

First rule I try to impress on my students: Programs aren't for the computer's consumption, they are principally for ḧuman understanding. Humans will have to write it, and modify it if it turns out wrong (be it a bug or a change in requirements). Today the human's time is much more valuable than the computer's (How much does a computer cost? How much does it's time cost, assuming a life of two years? Take any random program, how often will it have to be run to make up for your salary of a week, if that is what it takes to make it twice as fast?).


Merge Sort meaning of a bit part of code

Because of integer overflow, (l+r)/2 won't  actually compute the midpoint like we want in some special cases.  See
 https://stackoverflow.com/q/17358806/781723 and https://ai.googleblog.com/2006/06/extra-extra-read-all-about-it-nearly.html for details.


Time Complexity for Creating a Graph from a File

You forget that $O(|E|) \subset O(|E|+|V|)$ and $O(|E|+|V|) \subset O(|E|)$. Though It's actually $O(|E|\ln|V|)$, because checking if a vertex has been inserted is hardly $O(1)$.


Inline caching in not object oriented languages

As Gilles points out, it's not immediately obvious what the analogue of this would be in a non-object-oriented language. Below is one suggestion.

Let's say you have a function h :: (A -> B) -> C (this is using Haskell syntax). h is a higher order function and particularly it takes a function of type A -> B.  The definition of h will be something like:

h f = ... (f a) ...

h doesn't know what f will be so it must emit code for a call to an unknown function. Of course, if (h g) occurs in the code where g is a known function, the compiler may choose to inline h and then further optimize the inlined body of h with f now known.  This is just normal inlining.  We could also imagine a similar variation where we make specialized versions of h for some finite collection of functions A -> B and call the appropriate specialized version rather than inlining. (For GHC Haskell, this occurs with type classes via the SPECIALIZE pragma.) Neither of these are inline caching, though you could imagine a "static" version of inline caching that adds the appropriate guards and branches to specialized code if possible and otherwise falls back to generic code. I don't believe this is a particularly common optimization whether a language is functional or not. It's similar to rearranging branches to improve branch prediction though.

On the other hand, this optimization and inline caching in OO languages will both happen automatically with a trace-based JIT compiler.  If you view a first-class function as an object with a single method as many OO languages with higher order functions do, then inline caching will do this optimization.  That said, there aren't that many functional languages with a JIT compiler (tracing or otherwise) based implementation, particularly for a JIT compiler specifically geared to the functional language.  Two trace-based systems for functional languages described in the literature are Pycket for Racket, which is not a purely function language, and Lambdachine for Haskell. I'm not aware of any JIT compiler for a functional language that explicitly and specifically targeted this particular optimization.