You can use things like pair, proj ... as constants only. That works
very well conceptually. Nevertheless, there are reasons why
programming languages tend to use special syntactic forms for the like of
products:

Readability, e.g. ( M, N ) reads more natural than pair M N to
some.
For efficient reductions. It is possible to code the reductions for
pairs up in pure$\lambda$-calculus, but that's usually not as efficient.
Finally, you'd need a polymorphic typing system for this to work.

As an aside, the formalisation of logics in interactive proof assistants
like Isabelle is based on a similar idea, called logical frameworks.


Rotations: that arise in Computer Graphics and Robotics , through rotation matrices, Quaternions, etc.
 Cordics  for computing these functions on a Microprocessor / FPGA
 Transforms in Image Compression and elsewhere  , e.g. FFT computation in $O(n \log n)$ time
Anything to do with the interface between CS and Signal Processing
Pretty much anywhere in navigation and tracking, e.g. anything involving a GPS, IMU,etc.
Somewhat indirectly in  Computational Geometry (CG), in its application like in coverage & localization in wireless sensor networks.

.. to name a few! So if you want to really avoid trig functions, you should  learn CG :-)


Variation of the dining philosophers: is the standard solution still valid?

If the philosopher eats (holding both forks), drops the right fork and thinks for a while, and then drops the left fork to take a nap (or something similar), it is just the original problem: Each philosopher must ensure getting both forks without deadlock. Take a look at Allen B. Downey's "The Little Book on Semaphores" for in-depth discussion (this problem is hard!).


In general, no, on modern platforms, not everything is a hardware interrupt -- though you could imagine a platform where it is.

On some platforms, hardware interrupts are used for all input events (including, yes, pressing a key on a keyboard or moving a mouse).

However, interrupts come with some performance implications.  Therefore, in modern platforms, we often use a combination of interrupts and other I/O mechanisms.  We might use interrupts for some input devices, but other input devices might use memory-mapped I/O.  For instance, your Ethernet card might use memory-mapped I/O, to write incoming packets into a region of memory dedicated for this use.  Memory-mapped I/O can be combined with interrupts or with polling.

You can find more on interrupts, polling, memory-mapped I/O, DMA, and related topics in a good operating systems textbook.


Unless parentheses say otherwise, the customary precedence is ${}^*$ (like exponentiation), then concatenation (like multiplication), then union (like addition).

Your second example is the concatenation of starred expressions, so it does contain the empty string.


Deciding whether there exists a permutation of the entries of an $n \times n$ matrix that is magic

One approach is to use integer linear programming, and hope that an ILP solver will be able to find a solution.  This will probably still be exponential in $n$ in the worst case, but it might be faster than enumerating all $n!$ solutions.

Here's more detail.  Suppose we are given the integers $a_1,a_2,\dots,a_{n^2}$.  Let $M=(a_1+\dots+a_{n^2})/n$ be the magic constant of the magic square, so that every row, every column, and every diagonal needs to sum to $M$.  Define zero-or-one integer variables $x_{i,j,k}$, with the intended meaning that $x_{i,j,k}=1$ means that the number $a_k$ is placed in row $i$, column $j$.  Then we have the inequalities

$$\begin{align*}
&\sum_i a_k x_{i,j,k} = M\\
&\sum_j a_k x_{i,j,k} = M\\
&\sum_i a_k x_{i,i,k} = M\\
&\sum_i a_k x_{i,n+1-i,k} = M\\
&\sum_k x_{i,j,k} = 1\\
&\sum_{i,j} x_{i,j,k} = 1.
\end{align*}$$

Then any feasible solution to these linear equalities will represent a valid magic square, so you can feed this to an off-the-shelf ILP solver and hope that it finds a solution for you.  Probably it will fail (take forever) once $n$ gets large, but it might be effective if $n$ is small enough.


One way to help understand what's going on conceptually would be to draw a linear graph of what each of these functions mean.

So for example, say we're given a problem that tells us:

$g_1(n)=\Theta(lg(n))$

$g_2(n)=O(n^2)$

$g_3(n)=\Omega(n)$

we can make a quick sketch of where they could be in relation to each other.

With this visual, we can get an idea of possible candidates for these functions.

So let's bring it back to one of the questions you had trouble understanding:

  Let $f(n)=Θ(n), g(n)=Θ(n)$ and $h(n)=Ω(n)$. Then $h(n)+f(n)g(n)=?$

We know that $f(n)$ and $g(n)$ are both tightly bounded at $n$, so if you multiply them together, you'll clearly get $\Theta(n^2)$.

Now if we also add some function $h(n)$ that we know has a lower bound of $n$, the result must be $\Theta(n^2)+\Omega(n)$ which we can reduce to $\Omega(n^2)$, since an additional $...+\Omega(n)$ factor will be at its lowest value $n$ but there is no bound on how high this function can be (it could be anywhere from $n$ to $n^{1000}$ since there's no telling what an upper bound is), so we can conclude that it's $\Theta(n^2)+n=\Omega(n^2)$


Identifying and describing the language accepted by a Turing machine

A Turing machine implements an algorithm.
The algorithm can be implicit by an explicit definition of the language such as:
$M$ is a TM such that $L(M)=\left \{ x\in \Sigma^* \ | \ |x|\in \mathbb{N}_{even}\right \}$. Which is usually the case.
In other cases, you might have to understand a turing machine based on a state diagram, this will be a simple reverse engineering problem where based on some inputs you understand the algorithm (and then you can prove your assumption).
Generally, there is no fixed approach towards understanding the language a machine accepts.


In general terms, how could the Thompson Hack be implemented in Microcode?

In general, it certainly can not; this follows from Rice's theorem. That is, if you want to restrict the set of functions that are compilers in a meaningful way (one might also say that every function is a compiler).

In practice, you can of course inspect the sources of popular compilers and include heuristics in your malicious code that detect gcc, javac or any other known compiler.


How to balance the inflow and outflow of each vertex in a bipartite graph?

You can write a linear program. For each edge you have a restriction variable. You want to minimize the sum of the restriction variables. For constraints you want to have the sums of the differences between outgoing edges and the incoming edges (minus their restriction variables) to be smaller than a threshold that you choose.


Show that f(x,y)=x+y (with |x|=|y|) isn't a one way function

A function $f$ is one-way if given $f(z)$ for random $z$, it is hard to find an input $w$ such that $f(w) = f(z)$. So in order to show that $f$ isn't one way, you need to show that given $f(z)$ for random $z$, it is not hard to find an input $w$ such that $f(w) = f(z)$. Good luck!


Why do negative array indices make sense?

The array indexing operation a[i] gains its meaning from the following features of C

The syntax a[i] is equivalent to *(a + i).  Thus it is valid to say 5[a] to get at the 5th element of a.
Pointer-arithmetic says that given a pointer p and an integer i, p + i  the pointer p advanced by i * sizeof(*p) bytes
The name of an array a very quickly devolves to a pointer to the 0th element of a

In effect, array-indexing is a special case of pointer-indexing.  Since a pointer can point to any place inside an array, any arbitrary expression that looks like p[-1] is not wrong by examination, and so compilers don't (can't) consider all such expressions as errors.

Your example a[-1] where a is actually the name of an array is actually invalid.  IIRC, it is undefined if there's a meaningful pointer value as the result of the expression a - 1 where a is know to be a pointer to the 0th element of an array.  So, a clever compiler could detect this and flag it as an error.  Other compilers can still be compliant while allowing you to shoot yourself in the foot by giving you a pointer to a random stack slot.

The computer science answer is:

In C, the [] operator is defined on pointers, not arrays.  In particular, it's defined in terms of pointer arithmetic and pointer dereference.
In C, a pointer is abstractly a tuple (start, length, offset) with the condition that 0 <= offset <= length.  Pointer arithmetic is essentially lifted arithmetic on the offset, with the caveat that if the result of the operation violates the pointer condition, it is an undefined value.  De-referencing a pointer adds an additional constraint that offset < length.
C has a notion of undefined behaviour which allows a compiler to concretely represent that tuple as a single number, and not have to detect any violations of the pointer condition.  Any program that satisfies the abstract semantics will be safe with the concrete (lossy) semantics.  Anything that violates the abstract semantics can be, without comment, accepted by the compiler and it can do anything it wants to do with it.


Fastest way to check if prefix of small string is substring of big string

Why would you need to traverse the big string for each prefix? Let's say A = "Some short string". So you traverse string B, looking for the letter "S". If not found, then no prefix of A is contained in B. If found, you found the prefix "S", and start at that point searching for "So". And so on.


Give a Context Free Language, is the complement of this language always recursive(REC)?

We have $\text{CFL} \subset \text{R} \subset \text{RE}$. As you have mentioned, $\text{RE}$ is not closed under complementation, but $\text{R}$ is. Hence, the complement of a CFL is also in $\text{R}$ (though not necessarily another CFL).


Can a 32-bit processor work with a 64-bit size word?

Just what makes a processor a 32-bit processor?
And what would 64-bit word/32-bit halfword mean in the context?
There are processors allowing a single instruction to read more than one "memory cell", with documentation more or less readily available. The DEC VAX is notorious for having quad- and octaword accesses (a word being half the width of the general purpose registers (and data bus of early implementations)…).
There are processors with the width of the data bus smaller than a GPR. The Motorola 68000 was dubbed a 16-bit CPU - with 32 bit GPRs from the start. Then, the were Intel 8088, 68008 with a data bus a quarter in width compared to its GPRs, …
There are (memory) buses that allow locking of consecutive transfers.
There are buses and memory interfaces (on processing units as well as on memory devices) providing for burst transfers.


What does it mean that B-tree leaves carry no information?

So according to CLRS (quotations):

Any "satellite information" associated with a key is stored in the same node as the key
Leaf nodes have no children, so their ci fields [pointers to child nodes, added for clarification] are undefined
A common variant on a B-tree, known as a B+-tree, stores all the satellite information in the leaves and stores only keys and child pointers in the internal nodes

There was no mention about leaf nodes carrying no keys/information/etc...
So basically leaf nodes do carry keys in order to actually get the data you search for (just like all the other nodes), they just don't carry pointers to child nodes.
And why Donald Knuth wrote (according to Wikipedia and other sources) that leaf nodes "carry no information" is beyond me, maybe he was referring to a different variant of B-tree... I honestly don't know.


Using the product construction, given $M$ you can construct (in linear time) a DFA for the language $L'(M) := L(M) \cap \Sigma(\Sigma\Sigma)^*$. Using DFS/BFS, you can check whether $L'(M)$ is empty or not (you check whether some accepting state is reachable from the initial state) – $L'(M)$ is empty iff $M \in L$. The entire algorithm runs in linear time.


Rice Theorem - Problem to understand and apply it

From Wikipedia:

Let S be a set of languages that is nontrivial, meaning

there exists a Turing machine that recognizes a language in S,
there exists a Turing machine that recognizes a language not in S.

Then it is undecidable to determine whether the language recognized by an arbitrary Turing machine lies in S.

It's the language (determined by the TM) that has the property, not the TM itself. Your first condition is not needed at all, and the second condition should state
"$L(M_1')$ has the property, and $L(M_2')$ does not."
An example of application of Rice's Theorem might be the following statement. The set
$$S = \{<M> : \varepsilon \in L(M)\}$$ is undecidable. The corresponding TMs might be $M_1$ which only accepts $\varepsilon$ and $M_2$ which doesn't accept any words.
Your example is not correct since the property is trivial. $\emptyset \subseteq A$ for any set $A$, even an empty set.


Are there any stochastic models of non determinism in the rate of program execution?

There is work on estimating the worst-case execution time for code (sometimes called WCET analysis).  You can start with the Wikipedia article on the subject and use Google Scholar to find many research papers on that topic.

However, in traditional systems, the problem is not that the running time is random (well, that's one problem, but it's not the most serious one).  The more serious one is that the running time is unpredictable.  We can't even assign a probability distribution to it -- we have no basis for doing that.

For instance, in many garbage-collected languages, response time is unpredictable and real-time operation cannot be guaranteed.  The garbage collector might kick in at any point and pause your program for a very long time.  The point where that happens is not predictable, and the amount of time it will take is also not (usefully) predictable -- we can't even assign a stochastic model to it.

We can't really call the garbage collector random, as it might be triggered by some sequence of events that is in principle deterministic but is in practice too complex to model and thus is for all engineering purposes unpredictable.  You might be tempted to say "treat the time when garbage collection happens as random and uniformly distributed", but that's not valid.  For all we know, the garbage collector might kick in at the worst possible time.  Maybe there is some code that does a bunch of stuff (e.g., creating lots of short-lived objects and then immediately destroying all references to them) that tends to trigger the garbage collector, right before some other code that does something really time-critical (e.g., update flight control surfaces).  If you modelled the time of garbage collection as random, you would fail to recognize that the flight-control code might systematically fail at a higher probability than your stochastic model predicts.  All we can safely do is assume conservatively that the garbage collector might run at the worst possible time, and take essentially forever to do its job.  That renders worst-case execution time analysis impossible or unhelpful.

Similarly comments can be made about many other elements that make running time analysis hard, such as interrupts, caches, speculative execution, and so on.


Is it possible to constract Moore or Mealy machine with a different size of input and output?

Can you please suggest is it possible to do it with FSM (Moore or Mealy machine)

The machine you are looking for is called a finite-state transducer. They can be defined in either Moore or Mealy variants. For the Mealy variant (which I believe is more common), you have a finite state machine where the edges are labeled with output, and the initial states are also written as initial edges that can have associated output. (That is so that output can be produced on the empty input, if desired).

There are two types of finite-state transducers: one-way transducers and two-way transducers. The difference is that:

One-way transducers just read the input from left to right, like a normal state machine.
Two-way transducers have, for each edge, a label which says whether they move left, right, or stay still. The input tape also has start and end symbols: for example, the input 001 would be written $\triangleleft 00 1 \triangleright$. The machine has a special "halting" state. It moves back and forth on the input tape, reading symbols and producing output, until it is finished.

Two-way transducers are more expressive than one-way transducers.
For some of the tasks you listed, one-way transducers are enough, but all of them can be done with two-way transducers.

  copy 2 times: 11 -> 11011, 101 -> 1010101

This can be done with a two-way transducer. It reads the input, producing it as output, then goes back to the start of the tape, produces a zero, and reads the input again, producing it as output again.

  trim: 011100 -> 111, 000110 -> 11

A one-way transducer can do this. It only needs one state; then depending on the input symbol, it either produces output or produces no output.

  fill zeros by 1 between 1: 01000100 -> 01111100, 01010 -> 01110

A one-way transducer can do this. You should be in a different state depending on whether you want to fill the zeros, or leave them be, and then switch between these states whenever you encounter a 1.

  or should I switch to context free languages?

I hope not! Context free languages are much more complex and difficult to work with, and not necessary for the kinds of tasks you list.


I think you're confusing yourself by worrying about a worst case that likely won't happen.  Assuming each element of the stream comes randomly and independently from some distribution, then it is exponentially unlikely that the case you mention happens.

How do you train from a stream?  Easy: each time you see an example, you update the weights of the neural network following the rules of gradient descent, then throw away that example.  In this way, the weights of the neural network change over time, and you don't need to store any past examples.  Over time, as you've seen enough examples, this should converge to a neural network that performs about as well as possible on the data, assuming that all of the data in the stream comes from the same distribution.


Does this regular expression equal this automata?

In general, you can decide equivalence of regular expression and finite automaton using standard algorithms:

Construct an NFA from the regular expression,
Determinise and minimise both automata,
Check for equality (up to isomorphism).

These algorithms and proof that the minimal DFA of any regular language is unique (up to isomorphism) can be found in introductory textbooks.

If the underlying task is to "read off" a regular expression from an automaton, don't guess & proof but rather build the expression algorithmically to save time.


What is the difference between a simulator, emulator, and cross compiler?

Cross-development environment involve

a host computer (such as a PC) that runs the development tools,

a target computer (such as an embedded processor) that is where the code will eventually run.

A cross-compiler* generates the code that the target can understand, though compilation takes place on the host. The compiled code is sent to the target for execution.
An emulator is an ad-hoc piece of hardware that is able to mimic the behavior of the target, but is better suited for evaluation and testing.
A simulator is a software running on the host and able to mimic the behavior of the target without a physical target being present. Even though it runs on the host, it is able to execute the cross-compiled code.
A typical development scheme goes as follows:

cross-compile and debug with a simulator to obtain the correct functional behavior,

then cross-compile and debug with an emulator to check real-time performance and possibly interaction with real peripherals,

finalize the product on the real target.

*A compiler that compiles for the platform it runs on is called native.


How to represent circles in x-y coordinates

This answer considers two cases:

the overlapping relation between two disks, which is a very simple problem.
the ovelapping or covering of a disk by a set of other disks, which is somewhat harder in general.

Case of two disks

It is indeed a good idea to use center and radius to represent your
circles. However I think you are not thinking of circles, which are
closed planar lines formed of all points at a given distance $r$,
called radius, of a point $c$ called the center. The planar surface
enclosed by a circle, which also includes all points at a lesser
distance fron $c$ is called a
disk (also
spelled disc).

Regarding the various overlap situations for two disks, you have the
following test, assuming the two circles have radius $r_1$ and $r_2$
(assuming witout loss of generality that $r_1\geq r_2$), with their
centers at distance $d$ (computable from the centers coordinates,
thanks to Pythagoras):

$r_1+r_2<d$ : disks are disjoint, no overlap.
$r_1+r_2=d$ : disks are tangent externally, a single point of overlap.
$r1-r2<d<r_1+r_2$ : disks are partially overlapping.
$r_1-r_2=d$ : disks are tangent internally, total overlap of disk 2 by disk 1.
$d<r_1-r_2$ : disk 1 overlap totally disk 2.

There can be exact overlap of each disk by the other only when
$r_1=r_2 \wedge d=0$

Regarding the case of several disk, it is not clear whether you want
to see whether one distinguished disk is overlapped totally, partially
or not at all by the others, or whether you want to check that for
each disk with everyone of the others, or possibly something else. You should make that more precise.

Case of several disks

This is only a rough sketch, hopefully correct. Working out all details is a lot more work than can be included in an answer.

As suggested in the question, we can represent a disk $D$ by a
triple $(x,y,r)$ which gives the coordinates of the center, and the radius.

Now if you have a disk $D_0=(x_0,y_0,r_0)$ and a set of disks
$L=\{D_i\mid D_i=(x_i,y_i,r_i),\; i\in[1,n]\}$, your question, as
made more precise in a comment, is
how to check whether the disks of set $L$ together overlap partially,
totally or not at all the disk $D_0$.

First you want to make a list of the disks in $L$ that actually
overlap $D_0$. For that you can simply apply the above test to $D_0$ and
$D_i$ for every $D_i$ in $L$. You get a set $I\subseteq[1,n]$ of indices
such that D overlaps every $D_i$ for $i\in I$.

If this set $I$ is not empty, you know that $D_0$ is overlapped by $L$.

The question remains of a total overlap of $D_0$ by $L$.

For this, you create a new set $J\subseteq I$ by removing indices of
disks $D_i$ that are only externally tangent to $D_0$, overlapping it on
only one point.

If $J$ is empty, you had only tangential overlapping in a finite
number of point, but the set $L$ does not cover (fully overlap) the disk $D_0$.

If $J$ is not empty, then $L$ completely overlap $D_0$ iff it does it
with the disks $D_i$ such that $i\in J$. Tangential overlapping on a
single point cannot contribute usefully to overlapping a surface.

Now, all disks in $M=\{D_i\mid i\in J\}$ overlap $D_0$ on a fragment
of its surface.

If one disk in $M$ completely overlaps $D_0$, then we have an answer
of complete overlap. We can now assume it is not the case.

Then the problem is to find an orderly strategy to check whether the
disks in $M$ completely cover $D_0$. We will now use disks from $M$
one by one, removing them from M, to cover $D_0$. The strategy is in
choosing them.

We chose first a disk in M (which we remove from M), such that it is not
internally tangent to $D_0$, but intersect the edge circle of $D_0$. There
must be at least two such disks, else $D_0$ cannot be covered, as its
perimeter circle will nor be covered except for a finite number of
points.

We compute the two points where the two circles intersect. They define
two arcs, one on each circle, that delimit a surface yet to be covered
by the other circles. With respect to this surface, the arc belonging
to $D_0$ is convex, while the other is concave.

For simplicity and intuition, we call these intersections the angles
of the remaining surface. We call sides or edges the arcs between 2
angles that delimit the remaining surface to be covered.

We then chose one of the two angles, and look in M for another circle
covering this intersection. This new circle removes at least this
angle, and adds usually two new angles. We discuss this further below.

One remark is that the arcs coming from $D_0$ are always convex, while
the others are always concave. This is useful to visualize what can occur.

Then we repeat the same step, until there are no angles left, in which
case we have a covering of $D_0$, which is tested first, or until
there are no disk left in M that can cover a chosen angle, in which
case the overlap is incomplete.

To understand this we have to look at intermediate steps in more
details. During execution of the algorithm, we may have actually
created an uncovered curvy polygon with many angles. When we chose a
new disk $D_i$ to cover a chosen angle $A$, we may actually cover
several angles of the polygon, and the edges in between, so that we
actually reduce the number of edges.

So after choosing the disk $D_i$, we have to find the first edge on
both sides of the angle $A$ (not necessarily adjacent to $A$) that are
intersected by the circle bounding $D_i$. These two intersections, one
on each side, define two new angles and a new edge provided $D_i$, and
may replace several edges and angles. Hence the number of sides of the
polygon may be reduced rather than increased. It may be also that all
sides are covered, in wich case we have covered the whole disk.

There may be cases when the new disk will cut the curvy polygon into two
polygons, that will both have to be covered. To check for that, the
circle bounding the disk has to be checked for intersection with all
edges of the curvy polygon(s).

All this implies of course to keep an up-to-date description of the
curvy polygon and the relations between angles, edges and disks.
To keep correspondence between the relative positions of angles, if
they are listed counter-clockwise on the curvy polygon(s), then they
should be counter-clockwise on the circle of the disk $D_0$ and
clockwise on the disks from $M$.

There are quite a few details to be worked out, which I would not try
without at least checking an implementation. But I believe this basic
idea can be implemented.

From this analysis, I think the time complexity is $O(n^2)$, since
every steps considers a new disk, and has to look at intersections
potentially with all disks that have already been considered.

The extension to spheres is left as an exercise.


What is more effective, a do while or a while?

While and do while differ only in the first execution when condition is false. If you ignore this difference it boils down to the place of condition check, in while the condition is checked and if it is true the statements are executed. In the do while the condition check is executed after the block execution.

The code is exactly the same, with one line reordered.

If you want to do micro-optimisations please check whether these are worthy of your time. Compiler does really great job nowadays, unless it doesn't then change the compiler.

So under the hood they are equivalent.


How to check if two strings are permutations of each other using O(1) additional space?

Denote the arrays by $A,B$, and suppose they are of length $n$.

Suppose first that the values in each array are distinct. Here is an algorithm that uses $O(1)$ space:

Compute the minimum values of both arrays, and check that they are identical.
Compute the second minimum values of both arrays, and check that they are identical.
And so on.

Computing the minimum value of an array clearly uses $O(1)$ space. Given the $k$th smallest element, we can find the $(k+1)$st smallest element by finding the minimal value larger than the $k$th smallest element (here we use the fact that all elements are distinct).

When elements are allowed to repeat, we modify the algorithm as follows:

Compute the minimum values $m_{A,1},m_{B,1}$ of both arrays, count how many times each appear, and verify the $m_{A,1} = m_{B,1}$ and that the counts are identical.
Compute the minimum values $m_{A,2},m_{B,2}$ larger than $m_{A,1},m_{B,1}$ in the two arrays (respectively), and count how many times each appear. Verify that $m_{A,2} = m_{B,2}$, and that the counts are identical.
And so on.


Number of words of a given length in a regular language

Given a regular language $L$, consider some DFA accepting $L$, let $A$ be its transfer matrix ($A_{ij}$ is the number of edges leading from state $i$ to state $j$), let $x$ be the characteristic vector of the initial state, and let $y$ be the characteristic vector of the accepting states. Then
$$ s_L(n) = x^T A^n y. $$

Jordan's theorem states that over the complex numbers, $A$ is similar to a matrix with blocks of one of the forms
$$ \begin{pmatrix} \lambda \end{pmatrix}, \begin{pmatrix} \lambda & 1 \\ 0 & \lambda \end{pmatrix}, \begin{pmatrix} \lambda & 1 & 0 \\ 0 & \lambda & 1 \\ 0 & 0 & \lambda \end{pmatrix}, \begin{pmatrix} \lambda & 1 & 0 & 0 \\ 0 & \lambda & 1 & 0 \\ 0 & 0 & \lambda & 1 \\ 0 & 0 & 0 & \lambda \end{pmatrix}, \ldots $$
If $\lambda \neq 0$, then the $n$th powers of these blocks are
$$ \begin{pmatrix} \lambda^n \end{pmatrix}, \begin{pmatrix} \lambda^n & n\lambda^{n-1} \\ 0 & \lambda^n \end{pmatrix}, \begin{pmatrix} \lambda^n & n\lambda^{n-1} & \binom{n}{2} \lambda^{n-2} \\ 0 & \lambda^n & n\lambda^{n-1} \\ 0 & 0 & \lambda^n \end{pmatrix}, \begin{pmatrix} \lambda^n & n\lambda^{n-1} & \binom{n}{2}\lambda^{n-2} & \binom{n}{3}\lambda^{n-3} \\ 0 & \lambda^n & n\lambda^{n-1} & \binom{n}{2}\lambda^{n-2} \\ 0 & 0 & \lambda^n & n\lambda^{n-1} \\ 0 & 0 & 0 & \lambda^n \end{pmatrix}, \ldots $$
Here's how we got to these formulas: write the block as $B = \lambda + N$. Successive powers of $N$ are successive secondary diagonals of the matrix. Using the binomial theorem (using the fact that $\lambda$ commutes with $N$),
$$ B^n = (\lambda + n)^N = \lambda^n + n \lambda^{n-1} N + \binom{n}{2} \lambda^{n-2} N^2 + \cdots. $$
When $\lambda = 0$, the block is nilpotent, and we get the following matrices (the notation $[n = k]$ is $1$ if $n=k$ and $0$ otherwise):
$$ \begin{pmatrix} [n=0] \end{pmatrix}, \begin{pmatrix} [n=0] & [n=1] \\ 0 & [n=0] \end{pmatrix}, \begin{pmatrix} [n=0] & [n=1] & [n=2] \\ 0 & [n=0] & [n=1] \\ 0 & 0 & [n=0] \end{pmatrix}, \begin{pmatrix} [n=0] & [n=1] & [n=2] & [n=3] \\ 0 & [n=0] & [n=1] & [n=2] \\ 0 & 0 & [n=0] & [n=1] \\ 0 & 0 & 0 & [n=0] \end{pmatrix} $$

Summarizing, every entry in $A^n$ is either of the form $\binom{n}{k} \lambda^{n-k}$ or of the form $[n=k]$, and we deduce that
$$ s_L(n) = \sum_i p_i(n) \lambda_i^n + \sum_j c_j [n=j], $$
for some complex $\lambda_i,c_j$ and complex polynomials $p_i$. In particular, for large enough $n$,
$$ s_L(n) = \sum_i p_i(n) \lambda_i^n. $$
This is the precise statement of the result.

We can go on and obtain asymptotic information about $s_L(n)$, but this is surprisingly non-trivial. If there is a unique $\lambda_i$ of largest magnitude, say $\lambda_1$, then
$$ s_L(n) = p_1(n) \lambda_1^n (1 + o(1)). $$
Things get more complicated when there are several $\lambda$s of largest magnitude. It so happens that their angle must be rational (i.e. up to magnitude, they are roots of unity). If the LCM of the denominators is $d$, then the asymptotics of $s_L$ will very according to the remainder of $n$ modulo $d$. For some of these remainders, all $\lambda$s of largest magnitude cancel, and then the asymptotics "drops", and we have to iterate this procedure. The interested reader can check the details in Flajolet and Sedgewick's Analytic Combinatorics, Theorem V.3. They prove that for some $d$, integers $p_0,\ldots,p_{d-1}$ and reals $\lambda_0,\ldots,\lambda_{d-1}$,
$$ s_L(n) = n^{p_{n\pmod{d}}} \lambda_{n\pmod{d}}^n (1 + o(1)). $$


Your context-free grammar is just fine.  It is not actually necessary for the grammar to have a production with $S$ in its right-hand side.  In fact, a context-free grammar need not have any recursive productions or mutually-recursive productions, though the generated language in that case may be quite limited.  It is also not necessary to use any particular names for your nonterminals (e.g there is no need for $A$ to appear anywhere).


Origins of the numerical notation for types in type theory

This almost certainly derives from (finite) set theory. The cardinality of a finite set $S$, written $|S|$, is the number of distinct elements it has. For finite sets, we have the following relations: $$\begin{align}
|\emptyset| & = 0 \\
|1| & = 1 \\
|A\times B| & = |A||B| \\
|A\uplus B| & = |A|+|B| \\
|B^A| & = |B|^{|A|}
\end{align}$$
where $A\times B$ is the Cartesian product of $A$ and $B$, $A\uplus B$ is the disjoint union of $A$ and $B$, and $B^A$ is the set of functions from $A$ to $B$. The type theoretic constructions $A\times B$ (product types), $A+B$ (sum types), and $A\to B$ (function types) correspond to these set theoretic constructs. For example, finite sets form a model of the simply typed lambda calculus with products and sums where product, sum, and function types are interpreted as exactly the constructs on finite sets above. This correspondence is not general. There are many other models of the simply typed lambda calculus that will interpret these type constructions differently. Nevertheless, this is the archetypal example.

Category theorists often use similar notation but it is motivated the same way.

Another take on this is that these type operations (ignoring function types though their existence implies distributivity) make types into a commutative semiring up to isomorphism. Equations that you can prove in the theory of commutative semirings give rise to type isomorphisms.


Algorithm for cycle-detecting comparison

There is no pure way to detect cycles, where by pure I mean without caring about representation details such as object addresses. If you only allow examining data by comparing fields at base types, then there is no way to distinguish e.g. a cyclic list from a very long list. If you start examining

(1 2 3 4 5 6 7 8 9 10 11 …
(1 2 3 4 5 6 7 8 9 10 11 …

then maybe one of them is the list (1 2 3 4 5 6 7 8 9 10 11) and the other is (repeat (1 2 3 4 5 6 7 8 9 10 11) where (repeat cycle) builds a cyclic list that repeats its arguments — but you need to examine one more node to find the difference. Since the difference could be arbitrary far, there's no way to prove that two cyclic lists are equal.

The most practical solution is to compare object addresses to detect cycles. I expect that this is how most Scheme implementations do it. This requires some knowledge of how the garbage collector works, and specifically the ability to temporarily prevent it from relocating any object that is within the already-traversed part of the data structure. Locking GC moves might not hurt much, it depends on the GC technology: a mark-and-sweep GC doesn't need to move objects.

By the way, mark-and-sweep GC usually detect cycles by using a spare bit in the object. But that doesn't generalize well to arbitrary processing of arbitrary data structures.

If you're building your own data structure, as opposed to having to cope with arbitrary data structures like equal?, then a good approach is to not store cycles. Purely functional data structures typically don't have cycles in the first place since they can only create cycles with a statically-known structure which is not very useful. As with many problems in computing, this is solved by adding a level of indirection: instead of having the data structure contain a pointer chain that loops back to itself, have it contain references, i.e. the data structure is represented as some kind of map from identifiers from elements and nested data structures are stored using their identifier. When doing this, it's useful to perform hash consing, i.e., when applying a constructor, verify if the result is already referenced in the map and if so use the existing identifier rather than making a new one. This can save memory, and also processing time since traversal algorithms never need to handle the same data structure twice. In particular, with this trick, you can test equality of data structures by simply testing equality of identifiers.


Lambda Calculus - Call-by-name AND call-by-value reduction

You misunderstood call-by-value and are doing it backwards, i.e., you are substituting functions into arguments, instead of the other way around. Call-by-value and call-by-name both use the same rules of reduction, but in different places and in a different order.

In your case the call-by-value and call-by-name do not differ, because the arguments are already reduced.

Here is an example, where the difference matters. Reduce

(λpq.pqp)((λab.a)(λcd.d))

Note that this is different from your examples bacause of the extra parantheses that I put in.

Call-by-name:

(λpq.pqp)((λab.a)(λcd.d)) ➝
λq.((λab.a)(λcd.d))q((λab.a)(λcd.d)) ➝
λq.((λab.a)(λcd.d))q((λab.a)(λcd.d)) ➝
λq.(λb.(λcd.d))q((λab.a)(λcd.d)) ➝
λq.(λcd.d)((λab.a)(λcd.d)) ➝
λq.(λd.d)

Call-by-value:

(λpq.pqp)((λab.a)(λcd.d)) ➝
(λpq.pqp)(λb.(λcd.d)) ➝
(λpq.pqp)(λb.(λcd.d)) ➝
λq.(λbcd.d)q(λbcd.d) ➝
λq.(λcd.d)(λbcd.d) ➝
λq.(λd.d)

The difference is that in call-by-value you normalize the argument before you substitute it for the bound variable.


Why does floating point modulus exactness matters?

Note that inexact floating point implementation affect the weather.

There have been tests running weather predictions with the same inputs on different hardware and the predictions diverged. If you are running iterative algorithm then a small rounding difference here or there can result in a butterfly effect changing sunshine into rain.

The rounding rules in standards (IEEE 754, ISO/IEC 10967) have been carefully thought out so numeric algorithms behave predictable with the most accuracy and reproduce the same result every time. By not following the standard numerical algorithms designed for those rounding rules will break and iterative algorithms like weather predictions can even give a random result.

(and doesn't that say something about weather predictions? :)


The question in the title of your contribution "Can every context free language written as a intersection of another context free language and a regular language?" is the one you answer above, by taking $P=L$ and $R=\Sigma^*$.

However that is not the question you quote from your test: "If $L$ is a context free language, then there exists a language $P$ that is generated by a pure context-free grammar and a regular language $R$ so that $L=P\cap R$." This additionally requires $P$ to be pure context-free, that is, generated by a grammar that has no dictinction between terminals and nonterminals.

Let $G$ be a context-free grammar with alphabet $\Sigma$ (terminals and nonterminals) and terminal alphabet $\Delta$. As an ordinary context-free grammar the language of $G$ equals $L(G) = \{ w\in \Delta^* \mid S\Rightarrow^* w\}$. Interpreted as pure grammar it cannot "see" terminals and the language is $P(G) = \{ w\in \Sigma^* \mid S\Rightarrow^* w\}$. Or, $L(G) = P(G) \cap \Delta^*$, which gives the answer to your final exam.
The elements in $P(G)$ are usually called sentential forms.


Determining which recursive term is bigger if they share the same definition

Let $c_3 = \max(1,x,y,c_1+c_2)$. Then
$$
a_1 = x \stackrel{c_3 \geq x}\leq c_3^1
$$
and
$$
a_2 = y \stackrel{c_3 \geq y}\leq c_3 \stackrel{c_3 \geq 1}\leq c_3^2.
$$
Now suppose that $a_{n-2} \leq c_3^{n-2}$ and $a_{n-1} \leq c_3^{n-1}$. Then
$$
a_n = c_1 a_{n-1} + c_2 a_{n-2} \stackrel{\text{assumption}}\leq c_1 c_3^{n-1} + c_2 c_3^{n-2} \stackrel{c_3 \geq 1}\leq c_1 c_3^{n-1} + c_2 c_3^{n-1} \stackrel{c_3 \geq c_1+c_2}\leq c_3^n.
$$


Do modern operating systems use memory control blocks?

This is really a question about memory allocators and doesn't have much to do with operating systems. "Memory control block" does seem to be a DOS specific term for a node in a free list.  I'm not aware of any broadly used term for those nodes. They are usually just called "free blocks" or "unallocated blocks" or some such.

An operating system kernel usually has memory management concerns of its own.  A popular choice for Unix-like systems is slab allocation.  In Linux, there's a variation that is possibly the default nowadays called SLUB, and there is another option called SLOB which stands for "simple list of blocks" which does correspond to a free list approach.

At the lowest levels though, most popular, general-purpose CPUs organize allocation of physical memory with a page table. (More accurately, page tables manage the physical to virtual address mapping.) The kernel still must keep track of which pages of physical memory are allocated and to which process, but the page table structure makes this a bit less flexible. The main point being that pages come in fixed sizes which allows memory allocation techniques built on fixed sized blocks.  In particular, according to Wikipedia, Linux uses a zoned buddy allocator.

So the overall picture looks like this: at the lowest level you have an allocator to keep track of physical pages of memory; above that you have an arena-like allocator motivated by the fact that you often want to allocate many smaller-than-a-page objects and you obviously don't want to allocate a page to each; above that a programming language runtime may have its own memory allocator that may exploit details of the programming language to perform better; finally, an application may do some memory allocation of its own, often also using arenas but now usually motivated by time-cost issues like the costs of allocating/deallocating and data locality.


Whats an elegant way to tour a hypercube, in distance order:

For all $k=1, \dots, n$, you can easily generate all bit strings of length $n$ with exactly $k$ bits set.

The lexicographically smallest bit string has the $k$ ones in the $k$ least significant bits. If you interpret this string string as an integer, and it fits in a constant number of words, you can use bit tricks to find the next string in a constant number of operations.

See the section "Compute the lexicographically next bit permutation" here, and this answer for an explanation.


Is there a linear-time algorithm to determine if an array has duplicate entries that uses only constant extra space?

Suppose that your elements come from a domain of size $n^2$. Any algorithm using time $T$ and space $S$ corresponds to a branching program having depth $T$ and containing at most $T \cdot 2^S$ nodes. Theorem 6.13 of Time-space tradeoff lower bounds for randomized computation of
decision problems shows that
$$
T = \Omega\left(n \sqrt{\log \tfrac{n}{S + \log T}/\log\log \tfrac{n}{S + \log T}}\right).
$$
In particular, if $S$ is $O(\log n)$ (which corresponds to your $O(1)$ extra space, assuming you cannot modify the input) then $T = \Omega(n\sqrt{\log n/\log\log n})$.


Prove existence of different programs printing each other code

You maybe know the recursion theorem. It implies, that you can assume that you have a procedure called get_your_own_codeif your programming language is at least as powerful as a Turing machine.

Now do the following

Progr. A
w=get_your_own_code
print "print "+w

Note that some code is hidden in the subroutine of get_you_own_code. So we assume the complete source code is a string called source_code_of_A.

Progr. B
print source_code_of_A

Program A prints:

  print source_code_of_A

Program B prints

  source_code_of_A


Efficient data structures for building a fast spell checker

I've encountered same problem, but took different approach.
You can construct some kind of "hash" function, which will for similar word give same or near number.

Problem is, that function which will give "good" result for words with inserting/removing, will give "bad" for transition, and vice versa.
Example: map letters to numbers, similar letter to adjacent numbers, and just sum them for every letter in word.
Then create hash-tables with sets for each key and find intersection for word.

May be some results can be achieved if we look at "space" оf words. X for changing letter, Y for adding/removing, Z for transition, or something like that.

However this is only abstract ideas, I haven't enough time to implement them.


There are three equivalence classes, and this can be seen from the minimal DFA, which has three states. The equivalence classes are $\epsilon,0\Sigma^*,1\Sigma^*$. Indeed:

$\epsilon$ and $0$ are in different classes since $\epsilon 1 \in L$ whereas $01 \notin L$.
$\epsilon$ and $1$ are in different classes since $\epsilon \epsilon \notin L$ and $1\epsilon \in L$.
$0$ and $1$ are in different classes since $0\epsilon \notin L$ whereas $1\epsilon \in L$.
All words in $\{\epsilon\}$ are clearly equivalent.
All words in $0\Sigma^*$ are equivalent since $wz \notin L$ for all words $w \in 0\Sigma^*$ and all words $z$.
All words in $1\Sigma^*$ are equivalent since $wz \in L$ for all words $w \in 1\Sigma^*$ and all words $z$.


Howto formally go about proving that two LTL formulas are equivalent?

The semantics of LTL is (initially) defined with respect to infinite computations. So in that sense, two formulas $\psi_1,\psi_2$ are equivalent if for every computation $\pi$ it holds that $\pi\models \psi_1$ iff $\pi\models \psi_2$.

So in this sense - yes, you need the formulas to unwind the same set of computations.

The semantics is then extended to Kripke structures in the $ALTL$ model, meaning that a formula is satisfied in a structure if all its computations satisfy the formula. However, testing for equivalence should be done with respect to paths.

As for proving formally the equivalence of formulas: if this is an exercise, it will probably be easiest to analyze the formulas and prove that a path satisfies the first iff it satisfies the second. However, if you are handling complex formulas, then the best approach will probably be via nondeterministic Buchi automata, by testing the equivalence of the automata that correspond to the formulas. In practice, there are tools to do just that, but doing it manually may prove quite time-consuming (as the problem is PSPACE complete).


Fast algorithm for clustering groups of elements given their size/time

Finally I could devise a better algorithm by turning the problem upside down (ie, using bottom up construction instead of top-down).

In my OP algo, I first create a cluster and its groups, and then I walk through the whole files list until I could either fill completely the groups sizes, or there's no file in the files list small enough to fit.

Here it's the other way around: I walk through the files list, and for each file I either assign it to a group if it fits, or if it's too big I create a cluster and init it with this file. To do that, I continually maintain a list of groups sizes to fill, using insertion sort so that when I pick a file to organize, I just need to check its size against the first item of the "to-fill" list.

Here's the algorithm, running in O(n log(g)) (thank's to insertion sort or binary search trees):

For each file:
    - If to-fill list is empty or file.size > first-key(to-fill):
      * Create cluster c with file in first group g1
      * Add to-fill[file.size].append([c, g2], [c, g3], ..., [c, gn])
    - Else:
      * ksize = first-key(to-fill)
      * c, g = to-fill[ksize].popitem(0)
      * Add file to cluster c in group g
      * nsize = ksize - file.size
      * if nsize > 0:
        . to-fill[nsize].append([c, g])
        . sort to-fill if not an automatic ordering structure

Since it's running in O(n log(g)), the number of groups has little impact on the running time, contrary to the algo in the OP. Maybe it's possible to do better, but for now it is fast enough for me, since it can reasonably work on lists of 10M files under 20 seconds.

For those interested, here's a working implementation in Python (I used the sortedcontainers module for the sorted list, which runs in O(log(g)) instead of O(g) for insertion sort):

from collections import OrderedDict
from random import randint
from lib.sortedcontainers import SortedList

def gen_rand_fileslist(nbfiles=100, maxvalue=100):
    fileslist = {}
    for i in xrange(nbfiles):
        fileslist["file_%i" % i] = randint(1, maxvalue)
    return fileslist

def group_files_by_size_fast(fileslist, nbgroups, mode=1):
    '''Given a files list with sizes, output a list where the files are grouped in nbgroups per cluster.'''
    For each file:
        - If to-fill list is empty or file.size > first-key(to-fill):
          * Create cluster c with file in first group g1
          * Add to-fill[file.size].append([c, g2], [c, g3], ..., [c, gn])
        - Else:
          * ksize = first-key(to-fill)
          * c, g = to-fill[ksize].popitem(0)
          * Add file to cluster c in group g
          * nsize = ksize - file.size
          * if nsize > 0:
            . to-fill[nsize].append([c, g])
            . sort to-fill if not an automatic ordering structure
        '''
    ftofill = SortedList()
    ftofill_pointer = {}
    fgrouped = [] # [] or {}
    ford = sorted(fileslist.iteritems(), key=lambda x: x[1])
    last_cid = -1
    while ford:
        fname, fsize = ford.pop()
        #print "----\n"+fname, fsize
        #if ftofill: print "beforebranch", fsize, ftofill[-1]
        #print ftofill
        if not ftofill or fsize > ftofill[-1]:
            last_cid += 1
            #print "Branch A: create cluster %i" % last_cid
            fgrouped.append([])
            #fgrouped[last_cid] = []
            fgrouped[last_cid].append([fname])
            if mode==0:
                for g in xrange(nbgroups-1, 0, -1):
                    fgrouped[last_cid].append([])
                    if not fsize in ftofill_pointer:
                        ftofill_pointer[fsize] = []
                    ftofill_pointer[fsize].append((last_cid, g))
                    ftofill.add(fsize)
            else:
                for g in xrange(1, nbgroups):
                    try:
                        fgname, fgsize = ford.pop()
                        #print "Added to group %i: %s %i" % (g, fgname, fgsize)
                    except IndexError:
                        break
                    fgrouped[last_cid].append([fgname])
                    diff_size = fsize - fgsize
                    if diff_size > 0:
                        if not diff_size in ftofill_pointer:
                            ftofill_pointer[diff_size] = []
                        ftofill_pointer[diff_size].append((last_cid, g))
                        ftofill.add(diff_size)
        else:
            #print "Branch B"
            ksize = ftofill.pop()
            c, g = ftofill_pointer[ksize].pop()
            #print "Assign to cluster %i group %i" % (c, g)
            fgrouped[c][g].append(fname)
            nsize = ksize - fsize
            if nsize > 0:
                if not nsize in ftofill_pointer:
                    ftofill_pointer[nsize] = []
                ftofill_pointer[nsize].append((c, g))
                ftofill.add(nsize)
    return fgrouped
fgrouped2 = group_files_by_size_fast(fileslist, nbgroups)

def grouped_count_sizes(fileslist, fgrouped):
    '''Compute the total size per group and total number of files. Useful to check that everything is OK.'''
    fsizes = {}
    total_files = 0
    allitems = None

    for fkey, cluster in enumerate(fgrouped):
        fsizes[fkey] = []
        for subcluster in cluster:
            tot = 0
            for fname in subcluster:
                tot += fileslist[fname]
                total_files += 1
            fsizes[fkey].append(tot)
    return fsizes, total_files

if __name__ == '__main__':
    nbfiles = 10000000
    nbgroups = 10
    fileslist = gen_rand_fileslist(nbfiles)
    fgrouped = group_files_by_size(fileslist, nbgroups)
    fsizes, total_files = grouped_count_sizes(fileslist, fgrouped)
    print total_files
    print fsizes


What does the symbol "::" mean in computer science?

It is a delimiter between to parts of expression. You can think of it as notation for the English phrase 'such that'.
Read your formula as $`` \forall x\in K \text{ such that } x \longrightarrow x"$.


Initialize an array of pairs $T[i] = (x, c)$ containing all elements of $A$ and $B$. Let $x$ be the elements themselves, and $c = 0$ if the element came from $A$ and $c = 1$ if the element came from $B$. Then sort $T$ based on the $x$ values in ascending order.
Then the number of mistakes you'd get if you choose a value between $T[i]\text{.}x$ and $T[i+1]\text{.}x$ is:
$$\sum_{j=0}^i T[j]\text{.}c + \sum_{j=i+1}^n\left(1 - T[j]\text{.}c\right) = $$
$$(n - i) +\sum_{j=0}^i T[j]\text{.}c - \sum_{j=i+1}^nT[j]\text{.}c = $$
$$(n - i) +2\sum_{j=0}^i T[j]\text{.}c - \sum_{j=0}^nT[j]\text{.}c = $$
$$- i +2\sum_{j=0}^i T[j]\text{.}c - C$$
where $C$ is just a constant, which doesn't matter if you wish to minimize the quantity. So to find the optimal value:
S = 0
best = inf
best_i = 1
for 1 <= i <= n:
    S += 2*T[i].c
    if S - i < best:
        best = S - i
        best_i = i


Why %RSD of execution times, while sorting hundreds of arrays, is lower for larger arrays of random integers?

In the case of insertsort, the complexity (time) depends on the number of swaps performed during sorting. A kth element (k=1,2,3,...,n) in an array of size n, may require 0 to k swappings.

The execution time mentioned in the question depends on the sum of all the swaps performed during the sorting of a complete array.

Considering the random initialization of the arrays, the number of swaps performed for any kth element would be a random number bounded by the given range.

Now, If we consider the average value of the number of swaps per element (sum of all the swaps divided by the number of elements in the array), then, according to the law of large numbers, as the number of elements per array will increase this average will get closer to the expected value.

i.e., the variation in, the total number of swaps per array, among different arrays, will decrease.

Hence, the change (%RSD) in the execution times will also decrease.

--to be continued--


Wouldn't a Red-Black tree fix up after insertion mess up the BST ordering?

A correct implementation of red-black trees will maintain the BST ordering property. Whenever you add a node to the tree or delete a node from the tree you very carefully maintain this property. If you have to modify the structure of the tree then you do so in such a way that maintains the BST property.

I suggest you go carefully through the insertion and deletion pseudocode and verify that both operations maintain the BST property.


Is there a reason to NOT wrap preprocessor macros in parens?

#define PLUS +

3 PLUS 5

Any more questions?


What is the intuition behind the relationship between space and time for an algorithm?

A Turing machine moves the tape by one space per time unit. Worst case, if all moves were in the same direction, the space used would be exactly the same as the time used.


Placing items into compatible bucket types to find an optimal total value

You can formalize this problem as a minimum-cost flow problem.

You construct the graph as follows.

First construct a source vertex $s$ and a sink vertex $t$.
For each item $i$, add a vertex $u_i$ and add an edge from $s$ to $u_i$ with capacity 1 and with cost equal to the negation of the value of item $i$.
For each bucket $j$, add a vertex $v_j$ and add an edge from $v_j$ to $t$ with capacity equal to the capacity of bucket $j$ and with cost 0.
If item $i$ is compatible with bucket $j$, add an edge from $u_i$ to $v_j$ with capacity 1 and with cost 0.

Now you can use some polynomial time algorithm (for example, the cycle canceling algorithm) to find an integral solution of the minimum-cost flow problem. This integral solution then shows how you assign the items: if there is a flow 1 on $(u_i, v_j)$, then assign item $i$ to bucket $j$.


Confusing equivalence $\Phi(n,n)\downarrow \Leftrightarrow \text{HALT}(n,n)$

The function HALT is perfectly defined, it's just not computable - there is no program that computes it. Similarly, $\Phi(n,n) \downarrow$ is not a condition that can be computed by a program. The situation is asymmetric: if $\Phi(n,n) \downarrow$ then a program can verify that, but in the other case you're at loss. This is because HALT is recursively enumerable (partially computable).


One intention behind having a universe operator and a super-universe closed under it, is to give a type-theoretic version of large cardinal axioms known from set theory. An inaccessible cardinal is like a type-theoretic universe. The next interesting kind of cardinal is a Mahlo cardinal. Speaking intuitively, a Mahlo cardinal is one that has "a whole lot" of inaccessible cardinals below it. What would this be in type-theoretic terms? It ought to be some sort of a universe $U$ with lots and lots of universes in it. This is what Palmgren is addressing when he considers super-universes.

There is also a more practical side to having many universes. It is useful to have inductive-recursive types in type theory, for all sorts of purposes. But they let us define new universes, so the question is how many? To get a feel for what Palmgren is doing, instead of shooting for the super-universe right away, try the following sequence of constructions in Agda (using induction-recursion):

Define one universe $U_0$, containing (a code of) $\mathbb{N}$ and closed under $\Pi$ and $\Sigma$. This kind of universe corresponds to an inaccessible cardinal.
Define an operator $U$ which takes any type $A$ and defines a universe which contains (a code of) $A$ and is closed under $\Pi$ and $\Sigma$. This sort of universe operator is akin to Grothendieck's axiom of universes. How many universes can we get by repeatedly applying $U$, starting from $\mathbb{N}$?
To get even more universes, we postulate a super-universe $V$ which contains lots of universes, as follows:

$V$ contains $\mathbb{N}$, and is closed under $\Pi$ and $\Sigma$
Given (code of) a type $A : V$ and a family $B : A \to V$, there is a universe $U$, which is an element of $V$, it contains all types of the family $B$, and is closed under $\Pi$ and $\Sigma$.

How many universes does $V$ contain? Note that we can get a family $B : \mathbb{N} \to V$ such that $B(n)$ is the $n$-th universe, and so $V$ must contain a universe $U_\omega$ which contains all of these. And this is only the beginning!


Minimum number of shopping trips for a group of people to buy presents for each other

I can see how to reduce this problem to Graph Colouring, which gives you a tool for solving the problem (for small instances!), but not yet how to reduce in the other direction (which would establish NP-hardness).

The basic idea is to build a graph that contains a vertex for every purchase, and an edge between any two purchases that cannot occur on the same trip; we then look to group the purchases into the smallest possible number of groups ("trips"), such that no two purchases in the same group would conflict.  Specifically, if $G = (V, E)$ is the original directed graph in which an edge $uv$ indicates that person $u$ needs to buy person $v$ a gift, then create an undirected graph $H = (X, Y)$ in which there is a vertex $x_{uv}$ for each edge $uv$ in $G$ and an (undirected) edge $x_{uv}x_{vw}$ whenever $uv$ and $vw$ are both (directed) edges in $G$ (if $v$ buys some $w$ a gift during a trip, then no one can buy $v$ a gift during that same trip).  A vertex colouring of $H$ is a partition of the necessary purchases (vertices in $H$) into trips (colours) that don't conflict (share an edge), and a vertex colouring of minimum size takes the fewest possible trips.

It might be possible to go in the other direction (reduce Graph Colouring, or some other NP-hard problem, to your problem, and thereby establish its NP-hardness), by adapting a reduction from 3SAT to Graph Colouring (as, e.g., detailed on p. 10 of Jeff Erickson's notes), but I haven't attempted this myself.


Problems whose decidability status is unknown but known to be less hard than the halting problem

Assuming that by "less hard" you mean "reducible to", then any problem that is known to be in $RE$ but not known to be in $R$ satisfies this condition.

For example, take the PCP problem with 4 tiles, whose decidability is open. It is an easy exercise to reduce the problem (or any other problem in RE) to HALT.


Proving a language with equal occurences of ab, and cd is not a regular language using the Pumping Lemma

Ok I will split the answer into two parts, one for each of your questions \ concerns \ confusions:

Q: Are we allowed to use the pumping lemma if we chose a specific decomposition, or do we need to show for all decompositions?
A: The pumping lemma states, $\exists p.\forall w.|w|\ge p \rightarrow \exists x,y,z.w=xyz \land\text{ they are a valid decomposition }\land\forall k\in\mathbb{N}.xy^kz\in A$.
and you are trying to show the negation of this statement. as you can see, there is an "exists" sign before the "x,y,z" and therefore in the negation there will be a "for all" sign.
Thus, you MUST go over ALL possible decompositions in order to use the pumping lemma in this way.

Q: This doesn't work for $p=1$ but works for every other value of $p$. is this a problem?
A: no! its absolutely fine.
Say, for example, you know how to prove for $p=5$ and you don't know how to do $p=1$. define $w=(ab)^5(cd)^5$, and you know that $|w|\ge 5 \ge 1=p$. but since $|w|\ge 5$ and you know how to solve for $p=5$, you know how to deal with $w$.
This means that its enough to prove for some value of $p$ and all other values BELOW it will be automatically proved too!

Also, you are in the right direction. This is a good choice of a word, but you will need to work a bit more to show that every decomposition cannot be always pumped.
I hope this helped you a bit :)


Can we specify the pumping length while applying pumping lemma

The pumping lemma states that if $L$ is regular, then $\exists p.\forall w.\exists x,y,z. w=xyz \wedge$ they can be "pumped"

Thus to show that $L$ is not regular, we must show $\neg(\exists p.\forall w.\exists x,y,z. w=xyz \wedge$ they can be "pumped"$)$
which is equivalent to $\forall p. \exists w. \forall x,y,z.w=xyx\wedge($ all other requirements given in the lemma$)\rightarrow\exists.n$ they cannot be "pumped" n times

This shows us its nessecary to never assume what p is.

Furthermore, it explains why we need to find only one word (which depends on p).


CNF satisfiability with a bound on number of clauses

Here is an $n^{O(k)}$-time SAT algorithm: try all (at most $n^k$) ways how to select one literal from each clause, and accept whenever the selection is such that it does not include any contradictory pair (i.e., a literal and its negation). So, if $k$ is substantially smaller than $n$, you get a subexponential algorithm, and you should not be able to prove NP-completeness of such a restricted problem.


How to optimize Dijkstra's algorithm for a grid graph?

I am in love with Project Euler so that I am glad to see questions regarding it here. Be aware, however, that getting hints is somehow forbidden (note the italics :) ). The following is taken from the About page once you login:

I learned so much solving problem XXX so is it okay to publish my solution elsewhere?

It appears that you have answered your own question. There is nothing quite like that "Aha!" moment when you finally beat a problem which you have been working on for some time. It is often through the best of intentions in wishing to share our insights so that others can enjoy that moment too. Sadly, however, that will not be the case for your readers. Real learning is an active process and seeing how it is done is a long way from experiencing that epiphany of discovery. Please do not deny others what you have so richly valued yourself.

So I hope to provide a useful answer to your question while I honor the statement above ...

Regarding your first question the answer is No. There is nothing particularly interesting from the fact that you have a matrix. I see this more a matter of convenience for posting the problem than for finding the solution. I think I am not uncovering any interesting observation here since the same technique for solving this problem can be applied to arbitrary graphs.

Regarding your second question, you are right if you apply Dijkstra directly in a forward manner (ie., from the top left corner to the bottom right corner) but you have then a problem, and this is that the number of paths grows exponentially. Be sure that this problem can be solved in less than a second, ... So you should try something slightly different. Do not give up, I can see you are on the right path, so keep up pushing ...

And that's all I should say to respect the pleasure you'll get when solving this problem. Your "Aha!" moment :)

Hope this helps,


Is everything that is turing computable an element of NPSPACE?

So, if there is something that is turing computable, I know it is in NP (is that right?).

No!!! The time hierarchy theorem says that, for example, there are problems in $\mathrm{NEXP} = \mathrm{NTime}[2^{\mathrm{poly}(n)}]$ that aren't in $\mathrm{NP}$. And that there are problems in $\mathrm{2NEXP} = \mathrm{NTime}[2^{2^{\mathrm{poly}(n)}}]$ that aren't in $\mathrm{NEXP}$. And so on, ad infinitum.  In particular, this means that any $\mathrm{NEXP}$-complete problem is decidable but not in $\mathrm{NP}$.

To put it another way, there's no function $f$ such that every decidable problem can be solved in time (or space) $f(n)$, deterministically or nondeterministically.

In particular, there are perfectly reasonable decidable problems that aren't in $\mathrm{NP}$. For example, suppose you want to work with a graph on $n$ vertices. The graph is really large, so you can't store it. But, if I give you two vertices, it's easy for you to compute whether or not there's an edge between them (e.g., you can do that in deterministic polynomial time). Any problem that's $\mathrm{NP}$-complete when you're just given the full adjacency matrix as the input becomes $\mathrm{NEXP}$-complete when the graph is encoded in this way.


Chernoff bound when we only have a lower bound of expecation

You can use a coupling. Let $X = X_1,\ldots,X_n$, and suppose that $\Pr[X_i=1] = \beta_i$ (so $\beta := \mathbb{E}[X] = \sum_i \beta_i \geq \alpha$). Let $p = \alpha/\beta$, and define $\alpha_i = p\beta_i$. Let $Z_i \sim \mathrm{Bernoulli}(p)$, and define $Y_i = X_i Z_i$. Notice that $X_i \geq Y_i$ and that $\Pr[Y_i=1] = p\beta_i = \alpha_i$. If we define $Y := Y_1 + \cdots + Y_n$ then $X \geq Y$ and $\mathbb{E}[Y] = \sum_i \alpha_i = \alpha$, and so Chernoff's bound apply to $Y$, showing that $\Pr[Y \leq (1-\delta)\alpha] \leq e^{-\delta^2\alpha/2}$. Since $Y \leq X$, we conclude that
$$
\Pr[X \leq (1-\delta)\alpha] \leq \Pr[Y \leq (1-\delta)\alpha] \leq e^{-\delta^2\alpha/2}.
$$


Solving the recursive equation $T(n)=T(k)+T(n-k-1)+O(n)$

Consider the recurrence
$$
T(n+1) = \max_{0 \leq k \leq n} T(k) + T(n-k) + n+1, \qquad T(0) = 0,
$$
which is one formalization of the worst-case running time of quicksort. Let us show by induction that the maximum is attained at $k = 0$ (or $k = n$). We will show this while at the same time showing that $T(n) = \frac{n(n+1)}{2}$.
The base case, $n=0$, is clear. Now suppose that $T(m) = \frac{m(m+1)}{2}$ for all $m \leq n$, and consider $T(n+1)$. The function $T(k)$ is convex on the interval $[0,n]$ (we extend it to real values using the same formula), and so the maximum of $T(k) + T(n-k)$ is attained at $k=0$ (or $k=n$). Therefore
$$
T(n+1) = T(0) + T(n) + n+1 = \frac{n(n+1)}{2} + n+1 = \frac{(n+1)(n+2)}{2}.
$$
Instead of arguing using convexity, we can also argue directly:
$$
T(k) + T(n-k) = \frac{k(k+1) + (n-k)(n-k+1)}{2} =
\frac{n(n+1)}{2}-k(n-k),
$$
which is clearly maximized (uniquely) when $k = 0$ or $k = n$.


What's the fastest way to find the Kth smallest value in an unsorted list without sorting?

Use selection algorithm for linear time https://en.m.wikipedia.org/wiki/Selection_algorithm


an algorithm for detecting if noisy univariate data is constant or is sum of step functions

Every possible observation is consistent with a sum of step functions: one can use one step function per data point and fit any possible sequence of observations.  So, the question is not well-posed.  You'll probably need to impose some kind of restriction or prior on the set of sum-of-step functions you're willing to accept (e.g., a sum of at most 3 step functions).

If you make the question well-defined, it might be answerable  in a principled way using maximum likelihood.  Let $\mathcal{H}_0$ denote the set of constant functions, and $\mathcal{H}_1$ the set of sum-of-step functions you are willing to accept (e.g., with a limit on the number of step functions you're summing).  Let $\vec{x}$ denote the observed data.  Fix a probabilistic noise model.  Let $L(f)$ denote the likelihood of function $f$, i.e., the probability of observing $\vec{x}$ given that the true underlying function is $f$.  Let $L(\mathcal{H}_0) = \max \{L(f) \mid f \in \mathcal{H}_0\}$ and $L(\mathcal{H}_1) = \max \{L(f) \mid f \in \mathcal{H}_1\}$.  Then a maximum-likelihood decision rule would be: infer that the underlying data is constant if $L(\mathcal{H}_0) \ge L(\mathcal{H}_1)$, otherwise infer that the underlying data is a sum of step functions.

To implement this, you'll need an algorithm to compute $L(\mathcal{H}_0)$ and $L(\mathcal{H}_1)$, which will in turn depend on the noise model.  Computing $L(\mathcal{H}_0)$ is likely to be straightforward for reasonable noise models; e.g., if you assume iid Gaussian noise, then $L(\mathcal{H}_0)$ amounts to computing the average of the data points, choosing a constant function that is always equal to that average, and computing its likelihood.  Computing $L(\mathcal{H}_1)$ (assuming you have a restriction on the number of step functions you'll accept) is a little trickier but is doable using dynamic programming.

From a pragmatic perspective, you might also be interested in changepoint detection.


Why can't we simply put all of the RAM memory close physically to the CPU

Because that is not how geometry works. You cannot have everything close to the CPU, because the stuff that is close to the CPU is blocking the space close to the CPU, and thus other stuff has to be farther away.
Geometry works the same on the CPU as it does everywhere else: why don't all your neighbors live directly next door to you? Well, because your neighbors are taking up that space, so you simply can only have two direct neighbors. Everybody else has to live further away.
There are actually already 3-dimensional designs where the memory is stacked on top of the CPU, in order to be able to bring more memory closer to the CPU. But that only pushed the problem out, it does not solve it.
There is, however, a whole slew of other reasons, not just geometrical ones, why we have a memory hierarchy and not just a single flat memory. The main problems are that, in general, faster memory is also

more expensive,
more power hungry,
more complex, and
physically bigger (less dense).

That latter problem actually leads to an interesting optimization problem: as we said above, we can't have all the fast memory close to the CPU, because the space close to the CPU is limited. However, since slower memory is more dense, and thus takes up less physical space for the same memory capacity, you can actually put more slower memory close to the CPU than you can faster memory!
And even if you were to use only the fastest memory technology for all your memory, you quickly run into problems with the fundamental speed limit of the universe: the speed of light. As a general rule, our systems are designed in such a way that a single clock pulse must be able to propagate through the entire clock domain within a single clock cycle.
This means that no matter how close and how dense we pack our memory to the CPU, there comes a point where we cannot clock the memory with a high clock rate anymore. The further away we get, the lower the clock rate. But then it doesn't make sense to use the super-expensive, super-fast memory anymore, if we have to make it slower anyway. It makes more sense to use the cheaper, more dense, more energy-efficient memory.
And that is why the memory hierarchy exists: because the difference is not just speed, it is also cost, space, and energy. Here is an example of one possible memory hierarchy:

Registers (discrete flip-flops)
Level 0 Cache / µOP Cache (typically SRAM; per thread)
Level 1 Cache (typically SRAM; per core)
Level 2 Cache (typically SRAM; per core)
Level 3 Cache (typically SRAM; per die)
Level 4 Cache (typically SRAM; per module)
Local Main Memory (typically DRAM; per module)
Remote Main Memory (typically DRAM; "not this module")
SSDs (Flash; per node)
HDDs (magnetic; per node)
SAN (mix of SSDs and HDDs; per system)
Tape Library (per system)
Offsite Cloud Storage

Obviously, not all of these levels exist in all systems. This is an extreme example of a multi-core, multi-CPU, multi-node NUMA cluster with a separate storage network – my laptop doesn't have #6, #8, #10, #11, and #12, for example.
#8 only exists in so-called "NUMA" systems (Non-Uniform Memory Architecture), i.e. systems where not all RAM is "created equal". Typically, these are systems with a large number of CPUs, where it is not feasible to give all CPUs the same access to all of the RAM. Instead, the RAM is split into parts and typically one block of CPUs has direct access to one block of memory, and if it wants to access the rest of the memory, it typically has to talk to the CPU(s) that "own(s)" that block.
As a closing remark, I want to say that while the answers here have shown why your idea doesn't work, that does not mean that your idea is stupid! In fact, your idea is pretty much the Holy Grail of storage technology, and every couple of decades, a new technology comes along that tries to be fast, cheap, dense, energy-efficient, and ideally even non-volatile, at the same time, so that it can replace a large portion of that memory hierarchy.
However, as of today, none of those technologies have been able to live up to the hype, so to say: MRAM, FeRAM, T-RAM, Z-RAM, and many others. The latest entry being Intel's / Micron's 3D XPoint (better known under Intel's marketing brand Optane).


Prove that an infinite set is semidecidible

Here is a rough sketch.

If $M$ recognizes $C$, we can exploit $M$ to craft $N$ which enumerates the language of $M$, writing all its words on an output tape, clearly separated, in infinite time. For that, it suffices to exploit dovetailing to generate all the pairs $(w,k)$, where $w$ is a word and $k$ a natural. For each such pair, we run $M$ on $w$ for $k$ steps -- if $M$ accepts, we add $w$ to the output tape, otherwise we try the next pair.

Exploiting $N$ is then possible to define a total computable $f$ whose image is $C$.

For the other direction, given a total computable $f$, we can craft $M$ such that on input $w$ compares it to $f(0),f(1),f(2),\ldots$. In this way we can make $M$ recognize the image of $f$, i.e. $C$.


Is a push-down automaton with two stacks equivalent to a turing machine?

Two bits to this answer;

Firstly, the class of languages recognised by Turing Machines is not context sensitive, it's recursively enumerable (context sensitive is the class of languages you get from linear bound automata).

The second part, assuming we adjust the question, is that yes, a two-stack PDA is as powerful as a TM. It's mildly simpler to assume that we're using the model of TMs that has a tape that's infinite in one direction only (though both directions is not much harder, and equivalent).

To see the equivalence, just think of the first stack as the contents of the tape to the left of the current position, and the second as the contents to the right. You start off like so:

Push the normal "bottom of stack" markers on both stacks.
Push the input to the left stack (use non-determinism to "guess" the end of the input).
Move everything to the right stack (to keep things in the proper order).

Now you can ignore the input and do everything on the contents of the stacks (which is simulating the tape). You pop to read and push to write (so you can change the "tape" by pushing something different to what you read). Then we can simulate the TM by popping from the right stack and pushing to the left to move right, and vice versa to move left. If we hit the bottom of the left stack we behave accordingly (halt and reject, or stay where you, depending on the model), if we hit the bottom of the right stack, we just push a blank symbol onto the left.

For a full formal proof, see an answer to another question.

The relationship the other way should be even more obvious, i.e. that we can simulate a two-stack PDA with a TM.


How does the union of two machines which accept language of form $0^{mx+b}$ look like

It is written union of machines (I suppose here machine means finite automaton), but it is only an union of languages, i.e. the union of the languages accepted by said automata.
Indeed it should be finite otherwise it could be not regular. To prove this fact, for $k\in \mathbb{N}$, consider $L_k = \{0^{n(2k+3)},n\in\mathbb{N}\}$, and $L = \bigcup\limits_{k\in\mathbb{N}}L_k$. Then $L$ is the set of words over the alphabet $\{0\}$ that have a length which is the multiple of an odd number greater than $2$. That means that the complement of $L$ is $\overline{L} = \{0^{2^n}, n\in\mathbb{N}\}$. Since $\overline{L}$ is not even context-free, then $L$ cannot be regular.
$L = \{0^{2n}, n\in \mathbb{N}\}\cup \{0^{3n}, n\in\mathbb{N}\}$ satisfy the condition. To prove it, suppose $L = \{0^{an+b}, n\in\mathbb{N}\}$. Since $\varepsilon \in L$, then it means that $b = 0$. Since $0^2\in L$, it means that $a\mid 2$. Since $0^3\in L$, it means that $a\mid 3$. We conclude that $a\mid\text{gcd}(2, 3) = 1$, so that $a = 1$. Since it is clear that $L \neq \{0^n, n\in\mathbb{N}\}$ (because $0^5\notin L$ for example), $L$ is regular and not of the said form.
There seems to be a bit of misunderstanding about the variable $x$ here… And to be precise and avoid any mistake, you should write $\{0^{2x+3}, x\in\mathbb{N}\}$ instead of just $0^{2x+3}$. That way you will understand that $x$ is just a free variable and it does not matter how you write it.


Sure.  Such a function exists.  You have specified it.  Basically, you order the equivalence classes according first to number of vertices, and second by number of edges.  There are countably many graphs, so countably many equivalence classes, so they can be enumerated.  When you can enumerate them, they can be put into bijective correspondence with $\mathbb{N}$.

This function is computable, by enumerating all graphs with a certain number of vertices and edges.  e.g., for each $n:=1,2,3,\dots$, for each $m:=0,1,2,\dots,n^2$, for each graph containing $n$ vertices and $m$ edges, test whether it is isomorphic to any you have computed before, and use that to enumerate the graphs.  Of course, this will be a particularly inefficient algorithm.

In principle there is no known polynomial-time algorithm for computing graph isomorphism, so I would not expect a polynomial-time algorithm for $f$ (but this is not a proof; and it's still possible there might exist algorithms that are relatively efficient in practice).


What does Cellular Automata Pre-image problem actually means?

The way I understand it, the answer is your item #2.

That is, the specific CA is fixed (i.e., rule 90 or rule 110, or what ever), and given that fixed CA, one gives you a (sub)configuration, and asks whether there exists another configuration that leads to the input (sub)configuration within $K$ steps.

Indeed the description there (in the introduction of the paper) is very informal, but this is only because the
the problem is formally stated in section 3:

  CAP (CA Preimage problem):
  Given: A fixed CA $(Q,\delta)$ and a configuration substring $s$.
  Question: Is there a configuration substring $s_0$ such that $s_0 \vdash^{K} s$, where $K= |s|$?


Can maximum matching algorithms be used for maximum weight matching?

Ran Duan and Seth Pettie survey maximum matching algorithms in their 2014 paper Linear-Time Approximation for Maximum Weight Matching. In particular, Table III in their paper (page 5) lists algorithms for maximum weight matching in general graphs.


Better algorithm for aggregating data from various LDAP systems

Your algorithms seem fine.  I don't think you need better algorithms; I suspect what would help most is more on the engineering and implementation side.

At a high level, I would say that your design seems good enough as is.  If the primary objection is that it requires 20GB of RAM, well, buying RAM is a lot cheaper than spending a day of a software developer's time to implement a more memory-efficient solution.  So my primary advice would be to order some more RAM and call it good enough.

But if you still want to push on, I'll offer some other reactions...

Millions of users and groups is a fairly small data set.  20GB of RAM seems excessive for that.  Suppose there are 5M users, and each user is a member of 5 groups on average (say), and each group name is 10 characters long on average.  That corresponds to 50 bytes of data per user.  Add some overhead and round up and I'd estimate something like 80 bytes per user.  Yet your current data structure seems to be using 4KB per user.  That seems 50x too large; I would have expected something like 400MB would be sufficient.

Therefore, I'd suggest you do some memory profiling and look into why your in-memory store is taking up so much memory.  Perhaps you are using an unnecessarily inefficient data structure or hashmap implementation.  Keep in mind that you don't need to store the entire user object and group object (with all their attributes) in memory.  All you need to store in memory is the name of the user (a string) and the names of the groups they are in (a list of strings); the attributes can be stored in the database.  There are other techniques for reducing memory, such as sharding the data structure across multiple machines, but that hardly seems necessary or worth the effort.

Also, I wonder whether it's really necessary to run on multiple machines.  With only a few million users, I would have expected one machine to be more than adequate.  So if you care about the time to completion, you might want to look into that.  If you can do it on one machine, that will be simpler to implement, simpler to deploy, simpler to maintain, simpler to manage, and will reduce your stress about tying up 20GB of RAM on multiple machines.  I would have expected that the rate-limiting step is the number of LDAP queries you can make per second, so you could investigate what is keeping that down.  Perhaps you can have multiple threads making LDAP queries in parallel.  Perhaps you can reuse the same connection for multiple queries, to avoid connection setup and teardown costs.  Maybe you can run this on the same machine as the LDAP server to reduce network overhead.  Maybe you can think of some other speedups.

But overall, my guess is that this is a problem better solved by a beefier hardware rather than a software developer's time to optimize the code; and if you do want to improve the software, you're more likely to see gains from focusing on quality of implementation rather than algorithms.

Based on your comments, here is an alternative data structure that might save memory.  Assign each user and each group a unique integer ID (incremented by one for each new user/group).  Keep a mapping from name of user -> ID of user (with a hashtable) and a mapping from user ID -> user name (with an array); this is probably doable with 2-4GB, based on your numbers.  Do the same for groups; that's probably much less.  Then, keep a mapping from user ID -> array of group IDs that the user is in; that's probably doable with another 2-4GB.  All in all, I'd expect this could reduce your memory consumption to 4-8GB instead of 20GB.  You might be able to get further reduction by storing names in UTF-8 rather than UTF-16.


What is the best way to algorithmically sort physical boxes?

I'll analyze some basic strategies, show that always stacking is best in your model, and then discuss a more sophisticated strategy.

Analysis of basic strategies: never stack

The simplest strategy is one where you never stack boxes: when you pick it up, if it doesn't belong to a cage behind you, you put it back down where it was.  Heuristically, I expect the "never-stack" strategy requires an average of 7 seconds per box.  Not good.

Why?  We can model the number of times we pick up a box as a geometric distribution with parameter $0.5$; thus the average number of times you need to pick it up is 2.  You spend 3 seconds each time you pick it up, including the time to evaluate it; plus 1 second more to place it into the cage, for a total of $2 \times 3 + 1 = 7$ seconds.

I'm making an assumption here that might not be quite right... but it's probably in the ballpark.  Anyway, it suggests that "never stack" probably isn't a good strategy.

Analysis of basic strategies: always stack

The other extreme is to always stack boxes that can't be placed into the cage behind you.  I will assume that, as you specified in a comment, for each stacked box you perfectly remember what cage it belongs to, so once a box is stacked you never need to evaluate it again.

This strategy takes 5 seconds per box, which seems pretty good.  Why?  Look first at the boxes that end up getting stacked.  We've spent $1+2+1=4$ seconds for each box in the stack to move it into the stack, and we'll spend $1+1=2$ more seconds per box in the stack to move them all to their cage when it arrives, for a total of $6$ seconds per box.  50% of the boxes get stacked.  The total time per unstacked box is 4 seconds, and the total time per stacked box is 6 seconds, for an average time per box of $0.5 \times 4 + 0.5 \times 6 = 5$ seconds.

Not bad.  The great thing about always stacking is that you avoid ever evaluating any box twice.

If we think about it a bit more, it appears that "always stack" is the optimal strategy: it's not possible to lower the time per box any further.  Once you've picked up a box and know it doesn't belong into a cage behind you, what are your options?  You can either stack it or not.  If you stack it, it'll take only 2 seconds more to deal with that box in the future.  If you don't stack it, it's guaranteed to take at least 3 seconds more to deal with it again in the future, no matter what, maybe more (1 second to pick it up again, 2 seconds to evaluate it).  So given your assumption that you memorize the cage number of each stacked box, but don't memorize the cage number of boxes that you didn't stack and put back in their original place -- always stacking is optimal.

So what's wrong with always stacking?  Why wouldn't you always want to stack?    Stacking does have a cost.  It requires enough shelf space for all possible stacks.  If shelf space is limited, that might potentially be an issue.  Also in practice if you make the shelf too large, then that'll presumably increase the time it takes to pick up boxes and put them down somewhere else (since you have to walk further to reach the place where the stack belongs), so eventually that will be counterproductive.  Also, the more stacks you have, the more the burden on your memory (since you have to remember the cage number for each stack), which presumably isn't realistic once the number of stacks gets too large.

So perhaps we should consider "shelf space" or "number of stacks" as a limited resource as well, and consider whether we can construct a strategy that is almost as fast as always stacking, but doesn't require as many stacks.  With that motivation, I propose a more complicated strategy, next.

More sophisticated strategy: limited number of stacks

I'll describe a possible strategy where we try to achieve close to the same efficiency as always stacking, but with a limit on the maximum number of stacks we'll ever have.  This allows a tradeoff between shelf space vs time spent per box.

Divide the shelf into two zones, an arrival zone and a holding zone.  Divide the holding zone into 10 regions, labelled 0-9.  Each region can hold one stack, so at any point we'll have at most 10 stacks.  New boxes show up at the arrival zone.  I will assume that the cages are numbered sequentially (e.g., currently cages $i,i+1,\dots,i+5$ are behind you and cage $i+6$ will be the next to appear, and cage $i+7$ will be the next after that, and so on).

At each step, pick up a box from the arrival zone.  You can pick any one arbitrarily.  Evaluate it.  If it belongs to one of the cages behind you, put it there.  Otherwise, if it belongs to one of the next 10 cages to appear, put it into the holding zone.  Select the region corresponding to the last digit of the cage it belongs to.  For instance, if it belongs to cage 176, put it in the region labelled 6 of the holding zone.

When a new cage arrives, go to the corresponding region in the holding zone, pick up all of the boxes and place them into the cage.  There is no need to evaluate any of them -- you already evaluated them and know which cage they belong in.

In this way, each box gets evaluated only once.  It'll either be picked up once and evaluated and placed into its correct cage immediately (takes $1+2+1=4$ seconds), or picked up once, evaluated, moved to a new location, then picked up again and placed into the cage (takes $1+2+1+1+1=6$ seconds).  You said about 50% of the time a box can go into its correct cage immediately, so we should expect that the average time per box is $0.5 \times 4 + 0.5 \times 6 = 5$ seconds.

Now here's what I admit this is a little bit of a lie.  I oversimplified.  I assumed that if you pick up a package and it isn't in the cage behind you, then it will belong to one of the next 10 cages.  But what if it doesn't?  What if it belongs to a cage that won't appear until even further in the future?  This is the bad case.  In this bad case, all you can do in this strategy is put it back into the arrival zone.  Eventually, at some point in the future it'll be picked up again, and maybe then you can do something more productive with it.  The cost, though, is that this means occasionally a box will have to be evaluated more than once.

So in reality, the actual average time per box will be more than 5 seconds per box.  It might not be too much more.  But exactly how much more depends on how often you pick up a box and discover it belongs to a cage that won't appear for a long time (how often the bad case occurs).

Of course the number 10 (the number of regions in the holding zone) is arbitrary and can be tuned.  You can make it larger, to reduce how often the bad case arises; this will reduce the average time per box, at the cost of increasing the amount of shelf space you need.  Of course, in practice if you make the shelf too large, then that'll actually increase the time it takes to pick up boxes and put them down somewhere else, so eventually that will be counterproductive.  Alternatively, you can make that number smaller; this will reduce the amount of shelf space needed, at the cost of increasing the average time per box.

So I think this is worth a try.  Its effectiveness will depend on details of the distribution of when boxes arrived vs when their cage appears, which aren't specified in the question, but if you have data on that, you should be able to simulate this strategy and see how well it will work.

Second-level refinement of the above strategy

If you like this strategy, there is a refined version of it you could also consider.  The refined version is more complicated but might reduce time per box even a little further.  Divide the shelf into three zones, an arrival zone, a holding zone, and purgatory.  The holding zone is divided into 10 regions, labelled 0-9, as before.  Purgatory is also divided into 10 regions, labelled 0-9.

The scheme is exactly as before.  The only difference is what we do if you pick up a box and discover its correct cage is at least 10 cages into the future, but less than 100 cages into the future.  In that case, you put it into purgatory.  You place it into the region corresponding to the next-to-last digit of the cage it belongs to.  For instance, if you currently handling cages 112-117, and you pick up a box that belongs to cage 176, then you can't put it into the holding zone, but you can put it into purgatory; and you put it into the region labelled 7 of the purgatory.

Now, when a new cage arrives, do the same as before to move all boxes from the corresponding region of the holding zone into the cage.  Also, for every 10th cage that arrives -- in particular, when a cage arrives whose last digit is 5 -- go to the corresponding region in purgatory and sort all of those boxes into the cages or the holding zone.  About 60% of those boxes can be placed directly into a cage behind you, and the remaining 40% can go into the holding zone.

Again, there is nothing special about the numbers 10 here.  You can adjust the number of regions in the holding zone, and the number of regions in purgatory (they don't need to be the same number, either), to trade off shelf space vs time per box.  I don't know whether the extra complexity of this scheme will be worthwhile, but it's a natural extension to the idea above.


Insert into binary tree and keep it balanced

You can keep all leaves in a queue, and on insertion set the new node as a child for the q.front(), add the new node to the queue and check if the numbers of children of the node in front of the queue = 2 then pop the node out of the queue.
To remove a node you can swap the node you are removing and the last added node delete the last one (you should remove it from the back of the queue as well).

However, I would implement it as an array where a[0] is the root of the tree and a[i*2 + 1], a[i*2 + 2] are the children of a[i]. Inserting would be in this case to add an element to the back of the array and to remove an element you can swap it with the back of the array and pop the back of the arrray


Finding the lower bounds of an algorithm

Hint: The complexity is proportional to the number of reads from the array $A$.


Is there a better-than-brute-force algorithm to generate a graph whose relation is string edit distance=1?

In the worst case any such algorithm will work $\Omega(n^2)$ because your graph can have $\Omega(n^2)$ edges.

By the way, are you interested in some particular string metric?


Do white box methods for feature extraction exist for facial recognition?

For every feature $F$ you want to extract you need an algorithm extracts $F$.

the color histogram is good for color. For example if you need to extract eye color you need find eye in face (you can use open cv and see documentation) that is a 3 2D-matrixes for pixels(Red and Green and Blue filters) and if you find the histogram of these 3 matrixes you can use this histogram as eye color feature.

If you find face (with open cv) and extract the histogram, this feature isn't bad for skin color.

I think the heights and distances are not good features.

For finding face's shape HOG feature is good and also HOGColor


What is the big-o of the function 2 log(log n) + 3 n log(n) + 5 log(n)?

Starting with an analytical assessment of the function's terms, we'll first format all terms as similarly as possible to each other, in order to more easily compare with one another. To do so, all constants will be removed, leaving only the variable elements of each term. This is acceptable to do since we're ultimately seeking Big O classification, which typically sets all constants within its expression to a value of $1$.

$2log(log(n)) \geq log(log(n))$
$3n\: log(n) \geq n\: log(n)$
$5log(n) \geq log(n)$

Rewriting,

$\quad f(n) = log(log(n)) + n\: log(n) + log(n)$,

where

$\quad n \in \mathbb{N}$

Now, since each term varies only by their logarithmic arguments, we can establish an inequality by direct comparison of those arguments, resulting in

$\quad log(log(n)) \lt log(n) \lt n\: log(n), \forall n \gt 1$

Therefore, it follows that

$\quad f(n) \in O(n\:log(n))$


Bresenham's line drawing algorithm guarantees

Yes, Bresenham line drawing algorithm guarantees that endpoints are drawn.
The error accumulation is used for drawing and decreased after drawing a pixel, this is the core idea of the algorithm: incremental error is accumulated to avoid division operation, which is costly, but in this context it is something good and it doesn't mean that errors would damage continuity of line or lose endpoints.
The failure of Bresenham algorithm is technically possible only if floating point variable fails to add error, so $$deltaerr := abs(deltay / deltax)$$ is so small that $error := error + deltaerr$ would not increase $error$ at all, but if that happened, image is too big to fit on computer or some kind of clipping algorithm or bigger floating point variables are needed.
It is safe to assume that $\frac{deltay}{deltax} \le \frac{1}{2^{22}}$ is not going to happen.


How to analyze the lower bound of the horse racing problem using adversary argument?

Intuitively, the reason you need $7$ comparisons is that (1) you need $5$ comparisons just to see all the horses, (2) you need to compare all the first ranked horses to see which one is the fastest, (3) at this point you can't tell which is the second ranked horse.

Of course, this is not quite an adversary argument, and some work will be needed, though it is easy to use an adversary argument to show that (1) is correct: suppose that the strategy involves less than $5$ comparisons; then you don't see all the horses; so you can't tell whether the fastest horse is one of those you've seen or not. (Formally, if the algorithm states that a horse it's seen is the fastest, then you arrange for one of the one it didn't see to be the fastest; and vice versa in the other case.)

The same argument can be extended to show that $5$ comparisons are not enough: the only way that $5$ comparisons could be enough is by executing step 2 of your algorithm, and then you cannot tell which horse is the fastest. (I'll let you formalize that.)

I'll let you complete the argument and show that $6$ comparisons are also not enough.


If a greedy algorithm is not always optimal then a counterexample is sufficient proof of this.

In this case, take $\mathcal{M} = \{1,2,4,5,6\}$. Then for a sum of $9$ the greedy algorithm produces $6+2+1$ but this is not optimal because $5+4$ has fewer summands.