Rearrange pixels to maximize visually distinguishable pattern

This will not be an algorithm in the usual sense. It's a bunch of heuristics that you may find useful. The main difficulty comes from the undefined nature of the phrase "visually similar".

If I understand your question correctly. You have a few separate problems:

Defining what pairwise "visual similarity" is

You are looking for a function $S$ of two vectors to the interval $[0, 1]$. I imagine that you want it to ideally satisfy the following:

$S(\vec{x}, \vec{x}) = 1$, which means that a vector is most visually similar to itself.
$S(\vec{x}, \vec{y}) = S(\vec{y}, \vec{x})$, which means that measuring similarity between $x, y$ does not depend on their order.
$S(\vec{1}, \vec{0}) = 0$, which means that the most unsimilar vectors are the all-ones-vector and all-zeroes-vector.

Even with these restrictions you have a lot of choices. You can just count the number of matching pixels, but a one pixel shift in the image could give you maximum mismatch even if the images are visually very similar.

One simple heuristic that may suffice is counting all matching pixels. Then adding the number of $2\times2$ squares having a matching number of ones (sliding the comparison over all possible sub-squares), ..etc. You can try giving less weight to bigger squares. If you normalize by the maximum value you get (which is computed by comparing an image to itself). You get a value from 0 to 1. It's clear that this satisfies the assumptions above and captures similarity better than just comparing pixels.

These ideas are just examples of what you can do. If you experiment a bit, you can find some interesting $S$'s that capture your personal notion of visual similarity.

Deciding what you want to maximize for the data set.

Now assuming you have such an $S$, the question becomes what do you want to optimize. For a column (resp row), you can compute the sum or the median or the minimum (resp maximum). You can try to maximize the average column similarities minus the average row similarities or something of that sort.

Again, for an abstract $S$ that is not perfectly defined, you need to try different options and see what works best. As a guideline, optimizing for median vaguely means you optimize the common case, while allowing for outliers.

Quickly computing a permutation on $[1 \dots 64]$ that maximizes this quantity.

For some choice of $S$ and a choice of optimization criterion, it is extremely unlikely that you will find an efficient algorithm that finds the permutation optimizing that criterion. As you noticed in your question, the number of permutation grows very quickly with the size of the image.

One common heuristic that works quite well and is really easy to code, is local search. The idea is:

// Obj(p) is the criterion to be maximized.
opt = null
for t trials:
  p = random permutation
  for s steps:
    p' = copy p
    randomly swap two (or three) elements of p'
    if Obj(p') > Obj(p): p = p'
  if Obj(p) > Obj(opt): opt = p

This usually works well in practice. You have the knobs s and t that control the running time, you can even run the different trials fully in parallel. Increasing them usually yields better and better results. t controls the number of "starting points" for the search, which s controls the depth of the search. Again, you will need to experiment a bit.

Hope this helps.


Big O analysis for problem where number of items searched is unknown

Big-O gives the upper bound function of any analysis. For an algorithm you could represent all (Worst, Average, Best) cases in Big-O notation.

In your case,

Worst case: The required element is not present in the array (or is the last element of the array) : O(M)
Best case: The element is found in the first position itself: O(1)
Average case: Average of all possible case, i.e., the average time complexity of the cases where the element could be found at each possible position:

$$
\begin{align}
 = \frac{(1 + 2 + 3 + ... + M)}{M} \\
 = \frac{M(M + 1)/2}{M} \\
 = (M + 1)/2\\
= O(M)
\end{align}
$$

The average case is what you're looking for, which again O(M) only.


What will happen if input is larger than required in a NFA

An NFA accepts a string $w$ if it has an accepting computation. An accepting computation is an expression of the form
$$
q_0 \stackrel{x_1}{\to} q_1 \stackrel{x_2}{\to} q_2 \to \cdots \to \stackrel{x_m}{\to} q_m
$$
where:

Each $x_i$ is either a single letter or $\epsilon$.
$x_1 x_2 \ldots x_m = w$.
For every $1 \leq i \leq m$, $q_i \in \delta(q_{i-1}, x_i)$.
$q_0$ is the initial state, and $q_m$ is an accepting state.

If there are no accepting computations for $w$, then the NFA doesn't accept $w$.

The string $1001$ has no accepting computation. In contrast, the string $1111$ does have an accepting computation:
$$
q_1 \stackrel1\to q_1 \stackrel1\to q_2 \stackrel1\to q_3 \stackrel1\to q_4
$$
Therefore the NFA does accept $1111$.

Another way to define the language accepted by an NFA is through the possible states function. We define $\delta(q,x)$ to be the set of possible states that the NFA is in when it reads the word $x$. You can define $\delta(q,x)$ inductively. The NFA accepts $x$ if $\delta(q_0,x)$ contains an accepting state, where $q_0$ is the initial state. For example, in the case of $1001$,

$\delta(q_1, \epsilon) = \{ q_1 \}$.
$\delta(q_1, 1) = \{ q_1, q_2 \}$.
$\delta(q_1, 10) = \{ q_1, q_3 \}$.
$\delta(q_1, 100) = \{ q_1, q_4 \}$.
$\delta(q_1, 1001) = \{ q_1, q_2 \}$.

Since neither $q_1$ nor $q_2$ are accepting states, the NFA doesn't accept $1001$. In contrast, for the word $1111$ we have:

$\delta(q_1, \epsilon) = \{ q_1 \}$.
$\delta(q_1, 1) = \{ q_1, q_2 \}$.
$\delta(q_1, 11) = \{ q_1, q_2, q_3 \}$.
$\delta(q_1, 111) = \{ q_1, q_2, q_3, q_4 \}$.
$\delta(q_1, 1111) = \{ q_1, q_2, q_3, q_4 \}$.

Since $q_4$ is an accepting state, the NFA accepts $1111$.


Difference between a turing machine and a finite state machine?

The major distinction between how DFAs (Deterministic Finite Automaton) and TMs work is in terms of how they use memory.

Intuitively, DFAs have no "scratch" memory at all; the configuration of a DFA is entirely accounted for by the state in which it currently finds itself, and its current progress in reading the input.

Intuitively, TMs have a "scratch" memory in the form of tape; the configuration of a TM consists both of its current state and the current contents of the tape, which the TM may change as it executes.

A DFA may be thought of as a TM that neither changes any tape symbols nor moves the head to the left. These restrictions make it impossible to recognize certain languages which can be accepted by TMs.

Note that I use the term "DFA" rather than "FSM", since, technically, I'd consider a TM to be a finite-state machine, since TMs by definition have a finite number of states. The difference between DFAs and TMs is in the number of configurations, which is the same as the number of states for a DFA, but is infinitely great for a TM.


What are the reasons for and against using normalized floating point?

Binary IEEE format include both normal and denormal ('subnormal') numbers. The purpose of subnormals is to avoid a gap between the smallest normal numbers and zero larger than the smallest difference between consecutive normal numbers.

This gap make generate instability in some calculations dealing with small numbers,...
Denormal have a performance and/or complexity cost in software and hardware. Sometimes denormals are not handled or a fast mode is provided where all denormals are considered as zero.

(Here is an historical perspective from William Kahan, one of the original creators of the P754 format: https://people.eecs.berkeley.edu/~wkahan/ieee754status/754story.html)


A binary code is a set of vectors in $\mathbb{F}_2^n$ for some $n$.
Presumably the context in which you encountered this construction is a motivation for it. It's a particular case of a more general construction known as a Cayley graph, though perhaps this particular case has a specific name. You are right that all arithmetic is done in $\mathbb{F}_2$.
There are several NP-complete problems related to codes; Madhu Sudan has an entire lecture on these. One of them is, given a generator matrix for a linear code, determine the minimum weight of a non-zero codeword (i.e., the minimum distance).


Are there problems that are DSPACE(O(1)) complete?

YES, there are.

At the beginning of "Andreas Krebs, Klaus-Jörn Lange: Dense Completeness. Developments in Language Theory 2012: 178-189"[Section 6], it is stated that some REG languages with a non-solvable monoid are complete for $\mathrm{NC}^1$ under $\mathrm{DLOGTIME}$-uniform $\mathrm{AC}^0$ reductions. The section goes on to state that a REG language is either in $\mathrm{AC}^0$ or its syntactic monoids are non-aperiodic.

Complexity Zoo states that REG is contained in $\mathrm{NC}^1$.

So, some REG language is complete for the class itself. This is non-trivial.


Construct Turing Machine which accepts the language $ww$

Here is a sketch for how a deterministic machine might work:

place a marker in front of the input.
go through the input, checking if the length is even. If not, reject.
place a marker behind the input.
going back and forth, move the markers towards each other until they meet in the middle.
as long as the halves are nonempty, compare and erase their first letters and reject if not equal.
accept.


Using secure multi-party computation, there exists a polynomial-time protocol for this problem.

The functionality is

$$F_i(r_1,r_2,r_3)=((r_1 \ne r_2) \lor (r_2 \ne r_3) \lor (r_1 \ne r_3), (r_i = r_{i+1}) \land (r_i \ne r_{i-1})).$$

In other words, in the ideal world, participant $i$ flips a coin to get $r_i \in \{0,1\}$ and sends it to the trusted third party; they receive $F_i(r_1,r_2,r_3)$ back, and the first bit of the result indicates whether to repeat or not and the second bit indicates whether to pay.

It's a powerful theorem from the cryptographic literature that there exists a protocol for any functionality, with computational security and running in polynomial time.  Thus, there exists a protocol for this problem, too.  It will be secure as long as no more than 1 of the 3 participants are malicious.

See https://en.wikipedia.org/wiki/Secure_multi-party_computation and a good textbook on theoretical cryptography.


No, $f$ need not be a NDTM.  To prove a problem is NP-complete by reducing another NP-complete problem to it requires only a Karp reduction, which is a polynomial-time deterministic reduction.  So $f$ would live in the complexity class FP.


How many segments a process can have in operating system employing Segmentation for memory management

A process can only access 6 segments simultaneously through CS, SS, DS, ES, FS, and GS registers on an x86 and x86-64 machines.

These registers point to an entry in the segment descriptor table that the operating system manages. If OS uses a multi-segment memory model then that table can have an arbitrary size thus allowing a process to access a theoretically unlimited number of segments. (Intel 64 and IA-32 Architectures
Software Developer’s Manual 3-6 Vol.3)


Turing machine different accepting states

Of course, a Turing machine can transition to a given state from as many other states as you like. Machines used in halting problem reductions usually have an "infinite loop" state that only transitions back to itself, and many other states that transition into that one.


Understanding A Recursive Definition of CL-Terms in Combinatory Logic

Here are some considerations that could have been used to sort of "derive" the (f) rule:

it is natural to define our type of conversion recursively;
the general case when the body of "$\lambda$" is an application $(UV)$ needs to be addressed;
we certainly would like to get $[x].([y].([z].xz(yz)))$ converted into  its corresponding combinator $\mathsf{S}$.

Using the above we get an intermediate version of the (f) rule:

$$[x].UV \equiv A([x].U)([x].V),$$ where some closed CL-term $A$ is to be determined. The position of $A$ is chosen so that the subsequent "calls" of the (c) rule would be possible, or all three positions could be tried in turn.

$$\begin{array}
([x].([y].([z].xz(yz)))) &\equiv [x].([y].A([z].xz)([z].yz)) &\text{rule (f)}\\
                       &\equiv [x].([y].(A x) y)           &2 \times \text{rule (c)}\\
                       &\equiv [x].Ax                      &\text{rule (c)}\\
                       &\equiv A                           &\text{rule (c)},
\end{array}$$
hence $A = \mathsf{S}$ and the final version of the (f) rule
$$[x].UV \equiv \mathbf{S}([x].U)([x].V).$$

Note that the above is not a "real derivation", it's just some informal speculations, which I hope can help you to build up some intuition about that conversion.


design of self-loops and final states in fsm

Your original automaton is fine, it accepts the singleton $\{ab\}$. Here is a pictorial representation:

In the above automaton it's implicit that given a state and a letter for which there is no arrow going out of that state, then the automaton "crashes". If you want to be complete, you can add a dead state that absorbs strings that don't belong in the language. Here is the complete automaton:

If you add self-loops at 1 and/or 2, you will change the language that the automaton accepts. Look at this:

The self-loop at 1 labeled with $b$ changes the language to $\{ab, bab, bbab, bbbab, \dots\}$.


For a direct mapped cache the general rule is: first figure out the bits of the offset (the right-most bits of the address), then figure out the bits of the index (the next-to right-most address bits), and then the tag is everything left over (on the left side).

One way to think of a direct mapped cache is as a table with rows and columns. The index tells you what row to look at, then you compare the tag for that row, and if it matches, the offset tells you which column to use.  (Note that the order you use the parts: index/tag/offset, is different than the order in which you figure out which bits are which: offset/index/tag.)

So in part (a) The block size is 1 word, so you need 0 offset bits (because $2^0=1$). You have 16 blocks, so you need 4 index bits to give 16 different indices (because $2^4=16$).  That leaves you with the remaining 28 bits for the tag.  You seem to have gotten this mostly right (except for the rows for "180" and "43" where you seem to have missed a few bits, and the row for "181" where you interchanged some bits when converting to binary, I think).  You are correct that everything is a miss.

For part (b) The block size is 2 words, so you need 1 offset bit (because $2^1 = 2$).  You have 8 blocks, so you need 3 index bits to give 8 different row indices (because $2^3=8$).  That leaves you with the remaining 28 bits for the tag.  Again you got it mostly right except for the rows for "180" and "43" and "181".  (Which then will change some of the hits and misses.)


Boosting algorithms: Confusion between "weak classifiers" versus "number of boosting rounds"

I went back to the original paper from the literature by Schapire (http://www.cs.utah.edu/~piyush/teaching/brief_intro_boosting.pdf) and it does sound like a weak classifier is the output of a boosting round. Consider how the output of the overall classifier is $$H(x)= \text{sign}\left(\sum_{t=1}^T\alpha_th_t(x)\right)$$ which is expressing a threshold for the sum of $T$ weak classifiers.


Error lower-bound for an algorithm for vertex cover

Fix a star graph of $c + 1$ vertices. A star graph is a vertex connected to all other vertices in the graph (a universal vertex called the center), and all other vertices are pairwise not adjacent. Here is a visual example. $c$ is the center of the star.

Now an optimal solution is to pack the center of the star. The size of this solution is equal to 1. For each edge, suppose our algorithm packs the other end of the edge (the non-universal vertex), then we need to pack all vertices of the graph except for the center and hence, we need to pack $c$ different vertices. In total we get $|B_0| = C |OPT|$ for any arbitrary but fixed value of $c$.

Note
A simple modification of the algorithm yields a derandomized approximation algorithm with answer size at most twice as large as the optimum. It goes as follows: if both endpoints of the edge are not in $B_0$, then add both endpoints to $B_0$ and iterate.

The reason why this works is simple. The edges, who get their endpoints added for a maximal matching and hence, we add twice the number of vertices in a maximal matching to the cover. Note that the size of a matching in a graph is a lower-bound on the size of a minimum vertex cover and hence, we add at most twice many vertices as the size of the minimum vertex cover.


What is the difference between Multiprogramming and Multitasking

They are more or less synonymous. Multiprogramming is more used when one CPU is involved, that is being switched from a process to the other, processes which are residing in memory simultaneously. Along came threads, and it wasn't switching between programs anymore...
Processors, particularly the intel line, had the mechanisms for true multitasking (timer interrupt, privileged instructions) since at least the 80286. The M68000 used in the very first Mac was a processor with full-fledged multitaking capacities. This isn't a recent development in architectures. Note that the very first time shared systems swapped the user's programs in and out, and thus weren't really multiprogramming in the sense of having several programs in memory at the same time.
The idea is to have several programs residing in memory simultaneously, so that when one yields the CPU (by finishing or by waiting) there are others ready to use the CPU, thus increasing CPU utilization (and as you can consider each CPU burst to be preparing for a use of I/O, increase overall usage). This gives better thoughput (important in batch systems).
Along came time sharing, several interactive users connected to the machine. Same idea, keep their programs around but switch among them fast enough so they have the ilusion of "having a computer to themselves". Requires a timer that interrupts the CPU to avoid monopolization.
On personal machines there was not much incentive to run several programs at a time, at least initially (one user in front of a severely limited machive didn't expect much). As machines grew, a way of working around this and allowing several programs at a time without changing the operating system much was "cooperative multitasking", in that every program is suposed to yield periodically to the operating system to select another one to run. As the program doing this is in full control, it can select to do this when nothing could get messed up by others. Needless to say, a program "forgetting" to fullfil its duty to yield gets an interesting boost in performance... early Mac systems worked this way, and for the above reasons this didn't last too long. On embedded systems with no or only rudimentary operating system, and a tightly controlled set of programs running, this is certainly an attactive option.


Efficient way to find key points on spline to approximate it with line strip

A simple approach would be to take a dense sample of points on the spline (i.e., more than you need), and then apply the Ramer-Douglas-Peucker polyline simplification algorithm to get rid of as many of them as possible. Note: Unless you generate the point sample in some clever way (e.g., with density proportional to the local curvature), this isn't guaranteed to recover sharp bends perfectly.
According to that Wikipedia page, the straightforward implementation takes $O(n^2)$ time in the worst case for $n$ points, though there is also a more complicated version due to Hershberger and Snoeyink that takes just $O(n \log n)$ time in the worst case.


How can I do an optimization problem that involves finding a sequence?

Graph search

I recommend you formulate your problem as a graph search problem.  Each vertex represents a state of the system.  The state of the system lists the number of units you currently have and the number of each producer you currently have (e.g., "20 units, 1 A, 3 B's, and 0 C's").  You add an edge $s \to s'$ if you can get from state $s$ to state $s'$ in a single step.  The start state is "0 units,  0 A's, 0 B's, 0 C's".  The goal states are all states with 1000 units.

You can now use breadth-first search to find the shortest path from the start state to a goal state.

For better performance, use A*.  It's not too hard to construct a consistent and admissible heuristic that always underestimates the distance to the goal state.

As long as the number of producers is not too large, I expect this to be pretty efficient.

Greedy algorithm

It might be possible to build a greedy algorithm for your problem.

Consider a simplified variant where you are not allowed to sell producers you own, and where the number of units you have is allowed to go negative (you can still buy a producer even if it would put you in debt).  This has an efficient greedy solution.  In particular, consider the decision problem variant: given $t$, determine whether there exists a sequence that gets you to the goal within at most $t$ seconds.  This can be answered greedily.

Consider our first action.  We have $k$ options for actions: "buy $P_1$", "buy $P_2$", ..., or "buy $P_k$".  Note that it's always advantageous to make all your producer-buys as early as possible; there's no point in waiting.  Assume that for producer $P_i$ we have base cost $b_i$ and production $p_i$.  If we buy $P_i$, the net profit from that purchase (over the entire $t$-second time window) is $(t-1) p_i - b_i$.  So, for your first action, choose the action with largest net profit.  Now, for your second action, we have the same problem, except that $t$ is one smaller, so we can continue iteratively.  After $t$ seconds, we check whether the resulting sequence has reached a goal state.

[You can also consider a kind of exchange operation, where you compare "buy $P_i$ then $P_j$" to "buy $P_j$ then $P_i$".  You'll find that the decision rule for making that choice is as follows.  Associate to the action "buy $P_i$" a 'profit foregone if we defer buying $P_i$' value of $0.1 b_i + p_i$.  Determine which of $P_i$ or $P_j$ has lower 'profit foregone', and then choose to do that one first.]

You could check whether you can generalize this analysis to the case where you're allowed to sell producers and where you're not allowed to let the number of units owned go negative.  It looks a little tedious, so I'll leave the case analysis to you.


Is there a faster algorithm for constructing the adjacency list of this graph?

Since the relation is transitive, in the worst case you have $\frac{|V|(|V|-1)}{2}$ edges and so, if you want to add all edges of the graph in the list, you cannot achieve better than $O(|V|^2)$

PS: This problem is similar to an Algorithm project in my University, what a coincidence! ( ͡° ͜ʖ ͡°)


Language containing all unambiguous grammars

The language $L$ clearly exists — you just defined it!

It’s not hard to check that your language is co-r.e., that is, you can enumerate ambiguous grammars. Since it’s not recursive, it cannot be r.e.


Huffman code optimal substructure property

Your teacher are proving:

  Lemma: If $T'$ is optimal for $C' = C \setminus \{ x, y \} + \{ z \}$, then $T$ is optimal for $C$.

Once you have this lemma, you can prove the correctness of Huffman algorithm by mathematical induction on the cardinality of the alphabet $|C|$.

Base Case: The base case of $|C| = 2$ is trivial.
Inductive Hypothesis: Suppose Huffman algorithm is correct for any $|C| < n$.
Inductive Step: Consider the case of $|C| = n$. According to Huffman algorithm, you reduce the problem to constructing $T'$ on $C'$ where $|C'| = n -1$. By inductive hypothesis, $T'$ is optimal for $C'$. By the lemma above, $T$ is then optimal for $C$.


What is the best algorithm for image comparison in terms of speed?

I want to avoid changes due to light effects

A similarity measure based on binary descriptor can deal with this issue since it designed for multimodal images.

Also, you can try correlation coefficient since it cloud be used for real-time applications. for more information visit this page. Hence this algorithm in Matlab as a function called corr2 to find the degree of similarity between 2 images.


Start with a clique on the vertices $A,B,C,D$.
Connect $A,B$ to a new vertex $a$.
Connect $B,C$ to a new vertex $c$.
Connect $a,c$ to a new vertex $b$.
The vertex $b$ is the only one of degree 2, so your algorithm will start by adding $a,c$ to the vertex cover. The remaining graph consists of the clique $A,B,C,D$ and the isolated vertex $b$, so the algorithm will add 3 more vertices, ending up with a vertex cover of size 5.
In contrast, the 4 vertices $A,B,C,b$ cover all edges.


No, Gale-Shapley optimizes a different set of criteria; see https://en.wikipedia.org/wiki/Stable_marriage_problem.  It maximizes the men's happiness, which doesn't necessarily maximize the total happiness sums.  It is easy to come up with counterexamples by taking any stable marriage solution where some woman doesn't get her first choice -- say, Alice's first choice is Bob, but she isn't assigned to Bob in the assignment output by Gale-Shapley -- and then making Alice's affinity towards Bob be some enormous number, far larger than all other affinities.

I don't know if it can be solved in polynomial time.  Without the stability requirement, it's an instance of the assignment problem.  With the stability requirement added on, I don't know whether it can be solved in polynomial time.


SVM optimization objective: why are we maximizing $\frac{1}{\|w\|}$?

Let's slightly rewrite the condition you give: the quantity
$$ \frac{W^T \cdot X_i + W_0}{\|W\|} \mp D $$
is non-negative for $X_i$ in the first class (with $-D$), non-positive for $X_i$ in the second class (with $+D$). Now suppose $\lambda > 0$. Then the quantity
$$ \frac{(\lambda W)^T \cdot X_i + (\lambda W_0)}{\|\lambda W\|} \mp \lambda D $$
satisfies the same properties as before; in fact the two sets of inequalities are equivalent. Therefore we can assume without loss of generality that $\|W\| = 1$ (choose $\lambda = 1/\|W\|$), and so the quantity in question becomes
$$ W^T \cdot X_i + W_0 \mp D, $$
where we are promised that $\|W\| = 1$. Now divide everything by $D$ to get another quantity satisfying the same properties:
$$ (D^{-1}W)^T \cdot X_i + (D^{-1}W_0) \mp 1. $$
Maximizing $D$ is the same as minimizing $D^{-1} = \| D^{-1} W \|$, which is the same as maximizing $1/\|D^{-1} W \|$. Now imagine that instead of $W,W_0$, you were optimizing over $W'=D^{-1}W,W'_0=D^{-1}W_0$; for each choice of $W',W'_0$ you can recover $D = 1/\|W'\|$ and so $W,W_0$, which shows that both problems are equivalent. In these terms, you want the following quantity to satisfy the required properties:
$$ W'^T \cdot X_i + W'_0 \mp 1. $$
Under these conditions, you want to maximize $1/\|W'\|$.


Proving the loop invariant for a simple program in Hoare logic

Your invariant, together with the negation of the loop condition, is not strong enough to imply your postcondition. Try adding an additional conjunct to the invariant which, together with $\neg\ i<10$, implies $i=10$ (the $j=-1$ part then follows from $i+j=9$).


Hamming error correction with non-uniform error correction capability

The topic you want is Unequal Error Protection (UEP) codes. There are a number of constructions in this area and a google scholar search yields quite a few hits.

Intuitively, imagine partitioning your code into disjoint point clouds, where cloud centres are chosen by the more important bits, thus intra-centre distance is high, hence those bits are more robust to noise.

Some references:

On linear unequal error protection codes, B Masnick, J Wolf - IEEE Transactions on Information Theory, 1967.

Multilevel codes for unequal error protection
AR Calderbank, N Seshadri - IEEE Transactions on Information Theory,  1993.

A more information theoretic perspective is the Borade et al paper here on the arXiV.

Lastly, Prof. Lloyd Welch published a nice paper on "Codes correcting selected error patterns", which I can't seem to find a reference to.


It looks like you could be more careful. "For x=9, the graph says that the probability is 0.20 approx." In fact, the graph says that probability is slightly less than 0.12.

Here is the relevant quote from the article on hyperloglog

This is a plot of probability of having x leading zeros, with 1024 distinct items. You can see that the probability peaks at around x = 10, as expected - but the distribution is quite wide, with x = 9, 11 or 12 being at least half as likely as x = 10. (The distribution peaks 0.5 units higher than expected, so this implies that 2k will overshoot by a factor of 20.5, or about 1.4. This shows up as a correction factor later.)

The probability of having exactly $x$ most leading zeros with 1024 terms is the difference of the probability of have no more than $x$ leading zeros and the probability of have no more than $x-1$ most leading zeros.
$$ P[x] =
\left(1-\left(\frac12\right)^x\right)^{1024}
-\left(1-\left(\frac12\right)^{x-1}\right)^{1024} $$
In particular, the probability of exactly 9 most leading zeros $P[9]\approx 0.1169$.
Here is a Python program that computes the probabilities shown in the above graph.
P = [0] * 23
for x in range(1, 23):
    P[x] = (1 - 0.5 ** x) ** 1024 - (1 - 0.5 ** (x - 1)) ** 1024
for x in range(4, 23):
    print(x, round(P[x], 4))

Here is its output.
4 0.0
5 0.0
6 0.0
7 0.0003
8 0.0178
9 0.1169
10 0.2326
11 0.2388
12 0.1723
13 0.1037
14 0.0569
15 0.0298
16 0.0153
17 0.0077
18 0.0039
19 0.0019
20 0.001
21 0.0005
22 0.0002

By the way, thanks for mentioning such a nice article that explains the hyperloglog algorithm that counts approximately using only $\log\log N$ bits. $\log\log N$ is arguably underestimating, since more powerful hash functions are needed as $N$ grows, which need more space to compute. Even if we add the space used by the has function, hyperloglog algorithm is amazingly ingenious in several ways.


How to prove the existence of a number which cannot be written by any algorithm?

As Sebastian indicates, there are only (infintely but) countably many programs. List them to create a list of programs. The list is (infinitely but) countably long. Each program generates one number in R. From that we can create an (infinite but) countable list of numbers in R. Now we can apply Cantor's diagonal argument directly to prove that there still must be other numbers.

By the way if the algorithm has (finite) arguments, you can just rewrite that as a "longer" list of programs where each program doesn't have any arguments.

With regard to your comment "What if real numbers are allowed as argument", then the question's premise is wrong: all numbers in R can then be generated. If someone finds a number, say 皮 and claims it cannot be computed, we have the following "algorithm":

func(number):
    return number

and call func(皮)


Confusion about reduction of $L=\{w_i | M_i\text{ halts on }w_i\}$ to Halting Problem or Diagonalization language?

I want to reduce $L$ (stated above) to the Halting Problem in order to say that L is recursively enumerable

So far, so good.

  but not recursive just like the Halting Problem

Here we have a problem. Reducing $L \leq_m HALT$ does not prove that $L$ is not recursive. Actually, all recursive languages reduce to $HALT$!

  but is it enough to say that if I can solve the Halting Problem then I can solve $L$

No, this is not a may-one reduction argument. Indeed, if you can solve $HALT$, then you can also solve its complement. This however, does not imply that the complement is r.e., otherwise we would get that $HALT$ is recursive.

You need to define a (total recursive) reduction function from $L$ to $HALT$.

Then you need to prove that $L$ is not recursive. For that, you could prove the opposite direction $HALT \leq_m L$, constructing a reduction function from $HALT$ to $L$.


Populating a vector of numbers to expose an error in a function implementation

Multilinear polynomials
If you're willing to use probabilistic methods, I suggest using a randomized algorithm for polynomial identity testing.
You want to test whether $f(x)=g(x)$ holds for all $x$, where $f,g$ are multilinear oolynomials.  This is an instance of the polynomial identity testing problem.  There are effective randomized algorithms for polynomial identity testing.
To make this answer self-contained, I'll give you a brief overview of a reasonable algorithm.  First, randomly pick a large prime $p$.  Next, randomly pick $x=(x_1,\dots,x_n)$, with each element $x_i$ chosen uniformly at random modulo $p$.  Finally, check whether $p(x)\equiv g(x) \pmod p$.  If no, then you know that your implementation is faulty.  If yes, then your implementation has a good chance of being good.  (In particular, a faulty implementation that computes some other multilinear polynomial has a low probability of going undetected, thanks to the Schwartz-Zipple lemma.)  You can repeat this procedure multiple times for stronger guarantees.
This procedure assumes you can inspect the code of the algorithm and verify that it computes a multilinear polynomial, which seems to be something your question proposes that we can assume.  If you have a complete black box and you have no knowledge whether it computes a multilinear polynomial or not, you can't get strong guarantees that $f$ will be correct everywhere: for instance, your implementation $f$ might be correct on all but one input where it is special-cased to outputs the wrong answer.
More general cases
You might be interested in the theory of self-testing, pioneered by Blum, Luby, Rubinfeld and further developed by others.  See, e.g., the following seminal paper:
Self-Testing/Correcting with Applications to Numerical Problems.  Manual Blum, Michael Luby, Ronitt Rubinfeld.  Journal of computer and system sciences, 47(3), 549-595.
They generalize your idea by considering testers that invoke the program-under-test multiple times; by allowing probabilistic tests, where there is a chance we fail to notice problems, but this probability can be controlled or bounded; and by allowing for self-correction, where we use the possibly-faulty program as a subroutine to construct an output that will be correct with high probability.  Nonetheless, despite these generalizations, the class of functions that we know how to build efficient self-testers for is fairly limited, and we don't know how to do it for arbitrary functions.


Universality of $(+, \oplus)$ over $\mathbb{Z}_2^n$

Nope.  For instance, you can't express the function $f(x)=x>>1$.  In general, the least-significant bit of $f(x)$ depends only on the least-significant bit of $x$.  You can prove that by structural induction, using the following two properties: $(a \oplus b) \bmod 2 = (a \bmod 2) \oplus (b \bmod 2)$ and $(a + b) \bmod 2 = (a \bmod 2) + (b \bmod 2) \bmod 2$.


How to define whitespace for certain rules but else ignore it

I think you're approaching this the wrong way. Writing spaces is better handled as a problem of parsing, not of defining your grammar. That is, your grammar should only concern itself with lists of 'tokens' and your parser is concerned with transforming text into 'tokens' properly.

In a sense, whitespace is something the grammar should be completely unaware of. Whitespace can be useful for your parser to determine whether something is one or two tokens, but I doubt that you want to consider whitespace as a token by itself.


What parts of a programming language can't be defined using Regular Expressions?

Grammars and regular expressions are both ways to describe a language. Grammars are far more powerful. Context-free grammars are restricted grammars, with less power; regular grammars are further restricted context-free grammars, with less power again.

Regular grammars can describe exactly all regular languages, that is, all languages that can be described by regular expressions.

(Side note: this is only true for the regular expressions taught in computer science, which only use concatenation, union and Kleene star. In programming practice, extended types of regular expressions tend to be used with much more power.)

Regular grammars can be recursive, but only in a very restricted way:

each right hand side of a rule has at most one nonterminal
that nonterminal is either always at the end of a rule (for right-regular grammars) or always at the start (for left-regular grammars)

In your example:

<variable> ::= <letter> | <variable> <letter> | <variable> <digit>
<letter> ::= a | b | c | ...
<digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

the first rule isn't regular, but it only contains one recursive nonterminal: <letter> and <digit> both generate a finite set of strings. Hence, we can expand them into the rule to yield the equivalent set of rules

<variable> ::= A | B | ... |
               <variable> A | <variable> B | ... |
               <variable> 0 | <variable> 1 | ...

which is (left-)regular.

Hence, a regular expression for <variable> exists:

(a | b | c | ...)(a | b | c | ... | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9)$^*$

There are, in fact, straightforward algorithms for converting regular expressions to regular grammars and vice versa.

So context-free grammars can only generate non-regular languages by containing either right-hand sides with material on both sides of a nonterminal, for instance,

 <block> :== { <statements> }

or rules with multiple "recursive" nonterminals (i.e. of which more than one generates an infinite language).

If they do contain such rules, the language described may still be regular, and it can be really hard to figure out whether it is (it is undecidable).

However, we weren't looking at a grammar and trying to see whether it describes a regular language; we were looking at a language and trying to see whether it is regular.

A general rule I think you may find most useful in practice is to determine whether you can decide whether an utterance (in the case of a programming language: a program) belongs to the language by scanning it from left to right while never remembering more than a constant amount of information.  The syntax is regular if and only if you can do this.

In practice, you usually see two forms of recursion in languages:

a construct may contain another construct repeated an arbitrary number of times: this is regular;
a construct may contain occurrences of itself nested (that is, with some form of brackets to indicate the nesting) arbitrarily deeply: this is not regular, but context-free.

To take C as an example:

a block opens with a { character, followed by arbitrarily many (possibly empty) statements, separated by ;, and ends with }: this is regular, except that
a statement may itself be a block; thus, blocks can be nested inside blocks arbitrarily deeply: this is not regular.

JSON isn't a regular language for the same reason.

It isn't regular because the { and } brackets must match up, and while scanning from left to right, it isn't possible to determine this unless you somehow keep track of how many more { brackets you've seen than } brackets, and this count can be arbitrarily high: no constant amount of information can contain it.

Granted, in practice, you will rarely see C programs or JSON structures with blocks nested more deeply than, say, MAXINT times; but in theory, you may, which makes C syntax and JSON syntax non-regular.

I hope this gives you some intuition on how to distinguish regular from non-regular context-free languages in practice. It must be added that many requirements on the syntax of programming languages aren't even context-free: for instance, requiring variables to be defined before they are used is not.


Halting (on empty input tape) for an infinite subset of all Turing machines

is EVEN undecidable? How can you prove its undecidability?

It depends entirely on the enumeration that you use. E.g. one could make an enumeration that maps all Turing machines that halt with 1000 steps to an even index and all others to odd indices. Then EVEN is still an infinite set but decidable.
However a simple way to prove EVEN undecidable (assuming your enumeration is anything sane) is to show that for every Turing machine T there exists a machine T' that has an even index but identical behavior. You can do this by adding unreachable states, or useless extra transitions, etc, as long as it switches the parity of the enumeration.

What about other infinite subsets of TMs (for which we ask whether they halt on an empty input tape)? Would this problem still be undecidable or does that depend on the subset?

Entirely depends on the subset. See the example above, "the set of all Turing machines that halt within 1000 steps" is infinite, and trivially decidable. Other examples could include any mapping from infinite families of functions that you know that halt to Turing machines. All you need is an injective mapping - you don't need to decide behavioral equivalence.


First let's see how we arrive at the solution. Let's try expanding it:
$$\begin{align}
T(n) & = T(n^{\frac{1}{2}}) + \Theta(\lg \lg n)\\
& = T(n^{\frac{1}{4}}) + \Theta(\lg \lg n^{\frac{1}{2}}) + \Theta( \lg \lg n)\\
& = T(n^{\frac{1}{4}}) + \Theta(\lg 2^{-1} \lg n) + \Theta( \lg \lg n)\\
& = T(n^{\frac{1}{4}}) + \Theta(\lg \lg n - 1) + \Theta( \lg \lg n)\\
& = T(n^{\frac{1}{4}}) + 2 \cdot \Theta( \lg \lg n)\\
& = T(n^{\frac{1}{8}}) + 3 \cdot \Theta( \lg \lg n)\\
& \vdots\\
\end{align}$$
At this point you should see every time we recur we do $\Theta(\lg \lg n)$ work. So if we recurse $k$ times then total time is $\Theta(k \lg \lg n)$. Now we just need to find this $k$.

$k$ will be equal to how many times we can take the square root before resolving to a base case. Let's assume our base case is $2$, and all $n$ are of the form:
$$n = 2^{2^k}$$
We then can take the square root of $n$ exactly $k$ times before reaching $2$. This is because every time we take the square root of $2^{2^k}$, we cut the exponent in half, e.g. $\sqrt{2^{2^k}} = 2^{2^{k-1}}$. This clearly results in taking the square root $k$ times, or more formally $\log_2 \log_2 n$ times. Therefore we reach the conclusion that the total time is:
$$ T(n) = \Theta((\lg \lg n)^2)$$

With that being said this issue seems to be with your domain transformation. Going from $T(n)$ to $S(m)$, you're essentially saying a function of the form $T(n) = T(\sqrt{n}) + \Theta(f)$ is equivalent to a function of the form $S(m) = S(\frac{m}{2}) + \Theta(f)$ because after the domain transformation you can kinda abuse $\Theta$ notation to remove a lot of non-arbitrary values.

For more on domain transformations to solve recurrences check the notes 5.2 here.


How are two layer feed-forward neural networks universal?

I think they are talking about the universal approximation theorem which states that given a continuous function $f$ over an n-dimensional input vector $\vec{x}$, then a neural network with a single hidden layer can approximate $f(\vec{x})$ arbitrarily closely.


Applying Akra–Bazzi with an unbounded number of summands

Quoting from Wikipedia, the Akra–Bazzi method applies to recurrences of the form
$$
T(x) = g(x) + \sum_{i=1}^k a_i T(b_i x + h_i(x))
$$
where $a_i,b_i$ are constant, $a_i>0$, $0<b_i<1$, $g$ is polynomially bounded, and $h$ is "sublinear enough".
Your recurrence is not of this form, so you cannot apply the Akra–Bazzi method. It could be that the techniques used to prove the Akra–Bazzi theorem also apply to your case, but you will have to look at the proof.

Notice that
$$
f(n) - f(n/3) = \sum_{i=1}^{\log_3 n} f(n/3^i) - \sum_{i=1}^{\log_3 (n/3)} f(n/3^{i+1}) = f(n/3),
$$
and so $f$ satisfies the recurrence
$$
f(n) = 2f(n/3).
$$
In particular,
$$
f(n) = 2^{\log_3 n} f(1) = n^{\log_3 2} f(1).
$$
(Throughout, we are assuming that $n = 3^k$.)


How does the hardware of a while loop work?

Vladislav is right, but there is more that can be said.

A loop means running some code, and then running it again.  An if just conditionally branches to two different bits of code.  If one of those bits of code can jump back to the earlier code, or to the if itself, then you can get a loop.  So you need something that can jump somewhere else.  A goto is one command that does that in some languages.  You have to have a way to naming or identifying where the jump is to, though, even if it's just by a line number.

Another way to implement a loop is with recursion.  To do that, you need to be able to name procedures or functions or targets, and then embed the call to the named code in one of the branches of the if.  (In tail-recursive languages such as Common Lisp and Scheme, this can be as efficient as a loop in some circumstances.)

In both cases, it's crucial that there be a way of referencing earlier code, and jumping into it.  If you don't have that, an if won't be enough.  (But see below.)

You could do without the named code if you knew that your while "loop" didn't need to perform more than $n$ iterations.  Then you just expand the loop explicitly:

run my code
if something is true then stop
else run my code
     if something is true then stop
     else run my code
     if something is ....

However, naming isn't actually required in order to loop without just writing the same code repeatedly.  You can do it with recursion, as noted above, but it's possible to define a recursive function using a Y combinator.  This is probably not very efficient, and if your language evaluates eagerly, as most do, it's kind of a mind-twister at first (it's simpler in with certain kinds of delayed evaluation), but it works, and it's cool.  (My favorite source for the complicated version that most languages need is The Little Schemer by Friedman and Felleisen; you can probably find the simple version in any book on lambda calculus.  That's the version described in the Wikepedia page, so maybe that's enough.)

In answer to the title of the question, in hardware there has to be some jump to a location--probably the same location--that causes the same code to be executed repeatedly--or some way of getting the same code to start running in the CPU, such as rewriting the stack.  Others will be able to say more about this.

(It would be appropriate if the Y combinator function was named after Paul Graham's Y combinator company, since the company is named after the function.  Graham's book on lisp On Lisp discusses recursion without naming, but very briefly, in an endnote on pages 387-388.)


Consider the triangle graph with unit weights - it has three vertices $x,y,z$, and all three edges $\{x,y\},\{x,z\},\{y,z\}$ have weight $1$. The shortest path between any two vertices is the direct path, but if you put all of them together you get a triangle rather than a tree. Every collection of two edges forms a minimum spanning tree in this graph, yet if (for example) you choose $\{x,y\},\{y,z\}$, then you miss the shortest path $\{x,z\}$.

In conclusion, if you put all shortest paths together, you don't necessarily get a tree.


What is an efficient way to calculate the biggest system of disjunct sets?

This answer assumes that the sets in $\tilde{\mathcal{M}}$ have to be pairwise disjoint (as currently stated, you are requiring them to have empty intersection, which is a monotone condition).

The decision version of your problem is NP-complete, by reduction from independent set. Given an graph $G = (V,E)$, construct a set system with a set $S_x$ for each vertex $x \in V$, and an element $e$ for each edge $e \in E$. The set $S_x$ contains all edges incident to $x$. A family of sets is pairwise disjoint iff the corresponding vertices form an independent set.

We can also go in the other direction, following one of your suggestions. Given a set system, construct a graph in which each vertex corresponds to a set, and two vertices are connected if the sets intersect. A solution to your problem is the same as an independent set in the graph.


Understanding expected time bound for unsuccessful search in R-way tries

search in a binary search tree is log base 2 of N. Now you have a R-nary tree, so the running time would be log base R of N.


I would suggest looking at Geoffrey Seward Smith's dissertation

As you probably already know, the way the common type inference algorithms work is that they traverse the syntax tree and for every subexpression they generate a type constraint. Then, they take this constraints, assume conjunction between them, and solve them (typically looking for a most general solution).

When you also have overloading, when analyzing an overloaded operator you generate several type constraints, instead of one, and assume disjunction between them, if the overloading is bounded. Because you are essentially saying that the operator can have ``either this, or this, or that type." If it is unbounded, one needs to resort to universal quantification, just as with polymorphic types, but with additional constraints that constrain the actual overloading types. The paper I reference covers these topics in more depth.


Hiring one person out of n -- rank and probablity

When people are interviewed following a random arrival order, the probability of candidate $i$ being hired is $\frac{1}{i}$. This follows from the fact that, assuming a random order of arrivals, for each $i$ the group of initial $i$ candidates is random, so that the $i$-th candidate has probability $\frac{1}{i}$ of being chosen which happens if he/she is better qualified than the previous $i-1$ candidates.

Now instead of considering a random order on the arrivals, impose your own order, based on ranks: the first candidate is the less qualified, and the last one is the one which is the best overall. In this case, if the group is made of $n$ candidates, numbering them from $0$ to $n-1$ you get for the $i$th candidate a probability of being hired which is $\frac{1}{n-i}$, since candidates are now arriving on the basis of their ranks, and the $i$-th candidate is always better qualified than the previous $i-1$.

This is why you want to permute the group of candidates: so that no particular input elicits the worst case behavior associated to the permutation in which candidates are sorted by rank.

CLRS explains how this minor modifications allows you to hire, on average, $O(\lg n)$ candidates instead of $n$ in the worst case. Note that this is only a probabilistic guarantee: nothing prevents the pseudorandom generator, if you are really unlucky, from generating the permutation corresponding to the candidates sorted by rank. But we do not expect this to happen frequently: the probability of generating the bad permutation is only $\frac{1}{n!}$ which, for large $n$, is very low.


How did it happen that Algol 60 was an improvement on its successors?

I always felt like the reason is expressed by Alan Kay in his OOPSLA 1997 keynote, when he talks about Dijkstra's paper. I am not taking sides here but the tension expressed there seems to be prevalent in politics of CS, when it comes to Europe vs America. Algol represents European way of doing CS, and really most of the code was written in America. So no one really wrote any big system in Algol, thus it died.

But, I am an outsider to both cultures so, take this with a huge grain of salt. Also I know that Algol 60 designers included American computer scientists as well. All in all, this is just how I feel about it, no strong arguments here.


Big O space complexity of this isAnagram method

You probably expected the following answer.

Everyone of your friends is correct from her/his own perspective.

All you need to realize is that complexity analysis depends on lots of assumptions. In many cases, those assumptions have been defined beforehand or different assumptions will not not affect the end result of time-complexity analysis and space-complexity analysis. So people usually do not even mention those assumptions, especially in situations where the assumptions are stated or illustrated beforehand such as at the start of a chapter or a course. However, from time to time, situations arise where those assumptions are unclear, debatable, missing or even plainly invalid. Once you have made it clear what are the assumptions, including the model of computation used, there should be no real conflict.

Let us check each perspective raised in the question.

"The space complexity is $O(k)$", where "$k$ is the number of unique characters in firstWord". This observation points out the basic quantity in space usage.

"It's basically just an $O(1)$ space complexity", which make sense if we assume the input come from a vocabulary with a bounded number of characters. This is consistent with (almost?) all natural languages, whose number of characters are bounded while words or strings can be created as long and as many as we wanted, if only for the purpose of playing IsAnagram. Note this proposition can be seen as the previous proposition applied to refined but very common situations.

"It should be $O(m)$", where "$m$ is the length of the first word". There is hardly any argument against the correctness of this more relaxed bound, although it may seem not as tight as other bounds.

"On average, for any given character, there are $m/k$ occurrences of that character in the string and the size of a value $m/k$ in computer space is log(m/k) therefore, a tighter big $O$ is $O(k\log(m/k))$". This bound is based on the sharper observation that a number consists of many bits. Instead of counting the number of numbers used, it counts the number of bits used. (To prove that bound is correct, a dose of non-trivial math is needed.) The positional number system is about the optimal system to represent integers in term of space usage in this world, a fact that is reflected in the $\log$ factor. It can hardly considered anywhere near the physical truth without that factor. This line of reasoning is interesting as it indicates a more realistic model of computation than the more-commonly-used models of computations as implied in virtually every tutorial for elementary complexity analysis ([1], [2], [3]), where any integer is considered occupying a unit of space for the sake of simplicity and uniformity. Those common models include the family of register machines that includes counter machine and random-access machine. That is why we rarely see that $\log$ factor showing up in most complexity analysis. Unless required explicitly, we usually ignore that factor in space-complexity analysis and time-complexity analysis on our daily programming.
On the other hand, that factor has to be taken into consideration, for example, in the bit by bit analysis of the Turing machines (Why do we reject Turing machines that use space less than the log of the length of the input?).

You might insist asking, which answer makes sense most? Well, even though I might have my personal preference, a single choice will appear opposite to the whole point of this answer. Each and every one of them is valid under their respective assumptions and useful in different situations. Of course, if you are in an exam, do remember the default assumptions in your course!

As you must have noticed, I have inserted time-complexity in this answer. That is because we could have similar contention over the time-complexity of many algorithms. The usual resolution will be the same: state the assumptions clearly and we can happily accept each other's view, even though we might feel less comfortable with others' perspectives.


Integer Programming - packing wolves and sheep

I would approach it in the following way:

Suppose that I have the following sets:

$A$ - the set of all type of animals, i.e. $A = \{\text{wolf},\text{sheep}\}$
$B$ - the set of all possible bins. $B = \{B_1, \ldots, B_{n_B} \}$

Suppose I have the following parameters:

$c$ - a 1-dimensional matrix of the size of $A$, indicating the number of animals, per type that exist. Example: $c = \{2,3\}$ would mean that there are 2 wolfs and 3 sheeps.
$n_B$ - the number of bins available.

And suppose I have the following variable:

$M$ - is the integer matrix $A \times B$ that represents the number of animals per bin. Rows are animals, columns are bins. $M(\text{wolf},B_1) = 2$, for example, would mean that there are 2 wolfs in bin $B_1$.

So, for example, the following matrix:

$$
       M = \left[
 \begin{array}{ccc}
         2 & 1 & 0 \\
         0 & 0 & 1 \\
 \end{array}
\right]
$$

would indicate that there are 2 wolfs in $B_1$, 1 in $B_2$ and 1 sheep in $B_3$.

Your model would be:

$$
\begin{align}
& \text{Minimize}
& & U = \sum_{i = 1}^{n_B} 1 & \text{such that} \sum_A M_{ab_{i}} > 0 \\
& \text{subject to}
& & \sum_A M_{ab} \leq 2 & \forall b, \\
&&& \prod_A M_{ab} = 0 & \forall b, \\
&&& \sum_B M_{ab} = c_a & \forall a, \\
\end{align}$$

where $a$ is an element of $A$ and $b$ an element of $B$ and $b_i$ is the element of set $B$ at position $i$.

The OBJECTIVE FUNCTION U is the sum of all bins that are actually being used, and it is this sum that you want to minimize. There might be more elegant ways of defining that, but this is what I could think at the moment. Essentially you would count all bins that contain at least one animal - $\sum_A M_{ab_{i}} > 0$ represents that. In GAMS Programming language, I could represent this as what they call a dollar sign condition ($), check the language you are using to see how to impose this condition to the equation.

The FIRST CONSTRAINT indicates that there can be a maximum of 2 animals per bin - it translates to the following equations:

$$
\begin{align}
& M_{\text{wolf},B_1} + M_{\text{sheep},B_1} \leq 2 &\text{(rules for bin $B_1$)} \\
& M_{\text{wolf},B_2} + M_{\text{sheep},B_2} \leq 2 &\text{(rules for bin $B_2$)} \\
... \\
& M_{\text{wolf},B_{n_B}} + M_{\text{sheep},B_{n_B}} \leq 2 &\text{(rules for bin $B_{n_B}$)} \\
\end{align}$$

The SECOND CONSTRAINT limits the type of animals that can be put together - there can only be animals of one type in the bin, so that $M_{\text{wolf},B_1} \cdot M_{\text{sheep},B_1} = 0$, etc.

The THIRD CONSTRAINT limits the number of animals to be put in the bins to the number of animals available.


The DPDA could be constructed by adding explicit states and dropping too permisive epsilon transition.

I will denote accepting state by paranthesis around the name.

$(q_0, \epsilon, Z, (q_f), Z) \text{ accept empty string}$
$((q_f), a, Z, q_a, a)\text{ add initial a (or after cancellation occurs)}\\
((q_f), b, Z, q_b, b)\text{ add initial b (or after cancellation occurs)}\\
(q_a, b, a, q_a, \epsilon) \text{ even out two symbols}\\
(q_b, a, b, q_b, \epsilon) \text{ even out two symbols}\\
(q_a, \epsilon, Z, (q_f), Z) \text{ accept, it happens only with empty stack}\\
(q_b, \epsilon, Z, (q_f), Z) \text{ accept, it happens only with empty stack}\\
(q_a, a, a, q_a, aa)\text{ add another a to stack}\\
(q_b, b, b, q_b, bb)\text{ add another b to stack}$


If the number of locations (e.g. points or regions) are finite, naively, you can say that these locations are my states and you can directly use a DFA with an alphabet containing UP, DOWN. But you already said it's impracticable for your case.

Then, let's look into where the number of locations is infinite or simply too many. Basically, in this case, you need to recognize that the sequences UP-DOWN, UP-UP-DOWN-DOWN, UP-UP-UP-DOWN-DOWN-DOWN ... etc. are equivalent because equal number of UP and DOWNs gets you back to the starting point. This is the classical example of non-regular languages. Therefore I suggest you looking into other automata such as counter machines if they are sufficient to capture your intentions.


3SUM problem solution on the basis of cubic function and a line?

Consider the problem of finding whether the list $a_1,\ldots,a_n$ contains $d$ points summing to $S$. We assume that these points are all distinct.

Let us suppose that the $d$ points $a_{i_1},\ldots,a_{i_d}$ do sum to $S$. All of these points are roots of the polynomial
$$
(x-a_{i_1})(x-a_{i_2})\cdots(x-a_{i_d}) = x^d - Sx^{d-1} - P_{d-2}(x),
$$
where $P_{d-2}$ is a polynomial of degree at most $d-2$; the point is that we know that the coefficient of $x^{d-1}$ is $-S$, since (in this case) it equals the negative sum of the roots.

In view of this, we are motivated to consider the points $p_i = (a_i, a_i^d - Sa_i^{d-1})$. If $a_{i_1},\ldots,a_{i_d}$ sum to $d$ then the points $p_{i_1},\ldots,p_{i_d}$ all lie on the polynomial $y = P_{d-2}(x)$ of degree at most $d-2$ (we have seen that above).

Conversely, suppose that there exist $d$ points $p_{j_1},\ldots,p_{j_d}$ which all lie on a polynomial $y = Q_{d-2}(x)$ of degree at most $d-2$. This means that these points satisfy
$$
a_{j_t}^d - Sa_{j_t}^{d-1} = Q_{d-2}(a_j), \text{ for $j=1,\ldots,d$}.
$$
Stated differently, the values $a_{j_1},\ldots,a_{j_d}$ are all roots of the polynomial
$$
Q = x^d - Sx^{d-1} - Q_{d-2}(x).
$$
Since $a_{j_1},\ldots,a_{j_d}$ are all distinct (by assumption) and a polynomial of degree $d$ has at most $d$ roots, we conclude that $a_{j_1},\ldots,a_{j_d}$ are all the roots of $Q$, which means that
$$
Q = (x - a_{j_1}) (x - a_{j_2}) \cdots (x - a_{j_d}),
$$
implying that $S = a_{j_1} + \cdots + a_{j_d}$, as before.

Summarizing, the $d$ values $a_{i_1},\ldots,a_{i_d}$ sum to $S$ if and only if the points $p_{i_1},\ldots,p_{i_d}$ lie on a polynomial of degree at most $d-2$. Stated differently, there are $d$ values summing to $S$ if and only if there are $d$ points lying on a polynomial of degree at most $d-2$.

This criterion should be contrasted with the fact that every $d$ points lie on some polynomial of degree at most $d-1$.


A language $L$ is decidable if there is an algorithm that halts on every input, says Yes if the input belongs to $L$, and says No if the input doesn't belong to $L$.

The language of all binary representations of prime numbers is decidable since there is an algorithm that decides whether an integer is prime. You can probably code such an algorithm yourself in your favorite programming language. There are a few added complications - you need to parse the input, and you need to handle arbitrarily large integers - but intuitively these are not hard to address.

Similarly, the language consisting of only the empty string is decidable, since an algorithm can examine the string and check whether it is empty or not.

The real challenge is proving that some problem ins't decidable. The main techniques are are diagonalization and reduction. Roughly speaking, proofs by diagonalization construct an input that every potential algorithm fails to address, using some kind of self-reference. A good example is the halting problem, much information on which is available online. Proofs by reduction show that if you could decide your problem X then you would be able to decide some other problem Y which is already known to be undecidable.


An LL grammar is a grammar that can be parsed by an LL parser. An LL parser is a parser which parses input from Left-to-right and constructs a Leftmost derivation of the sentence. (https://en.wikipedia.org/wiki/LL_grammar).

The explanation is still a bit confusing, so it's easier to think of it that by looking at only a portion of the input string, we can predict exactly which production rule to apply.

In the grammar you've given: $L(aa^*ba) \cup L(abbb^*)$

which has the production rules:

$$S \rightarrow aAba | abbB$$
$$A \rightarrow aA | \lambda$$
$$B \rightarrow Bb | \lambda$$

this grammar is the union of all strings which start with either an arbitrary amount of $a$'s or an $ab$.

Remember what I mentioned earlier about LL grammars parsing strings from left to right, and that we'd be able to predict which production rule to use by looking at a portion of the input string? This specific grammar satisfies these properties, and is therefore LL.

Let's look at an example:

Say we're given the strings $aaaaaba$ and $abbbbb$. Starting from the left, how many input characters must we read to see which production rule to use?

The answer is two.

All strings in the grammar $L(aa^*ba) \cup L(abbb^*)$ start with an $a$, and if the second character of the input string is also an $a$, then we must use the production

$$S \rightarrow aAba$$

and if the second character is a $b$ then we must use the production

$$S \rightarrow abbB$$

The only basic concept to keep in mind when dealing with LL grammars is whether or not you can accurately predict which production rule to use when only looking at a portion of the string.

I hope this helped, and if I either missed something or didn't explain sufficiently please feel free to correct me.


Let $\Sigma = \{a, b\}$ and $L = \{aa, bb\}$. Use set notation to describe $\overline L$

You already got your answer in the comments: both the solutions provided solve the task. The only thing in which they differ is from which angle the attempt to solve the task. The author one goes from an empty set and adds only words that satisfy the given constraints (bottom-up approach). Yours goes from the set of all possible words and removes the ones that do not satisfy the constraint (top-down approach).
I would say his is more accurate IF you are not allowed to use $L$ or $\Sigma$, as it is often the case in exercise text books.


Partitioning a graph with specific constraints

It suffices to be able to identify case B, since a graph satisfies case A if, and only if, its complement satisfies B.

A graph satisfies case B if, and only if, it is composed of components of size $n_1, \dots, n_\ell$ and there is some set $S\subset \{1, \dots, \ell\}$ such that $\sum_{i\in S} n_i = \sum_{j\notin S} n_j$.  (If $n_1 + \dots + n_\ell$ is odd, this is impossible, so include a fake component of size $1$.)

This is the set partition problem.  Bad news! It's NP-complete.  Good news!  It's not strongly NP-complete and we're encoding the numbers $n_i$ in unary. This means that the pseudopolynomial algorithms described on the Wikipedia page are actually polynomial-time algorithms in your context.  By checking the algorithms carefully, you can probably avoid the "fake component" trick.


Words generated by CFG whose parse tree contain even number of $X$

Add a new terminal $x$ to the alphabet, and replace $X$ with $xX$ in the right-hand side of all productions. Denote the corresponding context-free grammar by $G'$, and let $h\colon A \cup \{x\} \to A^*$ be the homomorphism erasing $x$. Then your language is $$ h(L(G') \cap A^*(xA^*xA^*)^*). $$
Since the context-free languages are xlosed under homomorphism and intersection with a regular language, it follows that your language is context-free.


Understanding Property Testing with a toy example

The problem is, given a string of length $n$ over $\{0,1\}$, to distinguish the following two cases:

The string is entirely 0.
The string is $\epsilon$-far from being entirely 0, i.e., has at least an $\epsilon$-fraction of 1s.

The proposed algorithm tests $S = 2/\epsilon$ positions, and returns (1) if all positions were 0. If the original string consisted of 0s then this algorithm always returns (1) correctly, and otherwise it makes a mistake with probability $(1-\epsilon)^S \leq e^{-2}$.

We choose $S = 2/\epsilon$ in the first step so that the error probability is constant, in particular less than $1/3$. If you want a different error probability, you'll choose a different value of $S$.


Why do we not combine random number generators?

Sure, you can combine PRNGs like this, if you want, assuming they are seeded independently.  However, it will be slower and it probably won't solve the most pressing problems that people have.

In practice, if you have a requirement for a very high-quality PRNG, you use a well-vetted cryptographic-strength PRNG and you seed it with true entropy.  If you do this, your most likely failure mode is not a problem with the PRNG algorithm itself; the most likely failure mode is lack of adequate entropy (or maybe implementation errors).  Xor-ing multiple PRNGs doesn't help with this failure mode.  So, if you want a very high-quality PRNG, there's probably little point in xor-ing them.

Alternatively, if you want a statistical PRNG that's good enough for simulation purposes, typically the #1 concern is either speed (generate pseudorandom numbers really fast) or simplicity (don't want to spend much development time on researching or implementing it).  Xor-ing slows down the PRNG and makes it more complex, so it doesn't address the primary needs in that context, either.

As long as you exhibit reasonable care and competence, standard PRNGs are more than good enough, so there's really no reason why we need anything fancier (no need for xor-ing).  If you don't have even minimal levels of care or competence, you're probably not going to choose something complex like xor-ing, and the best way to improve things is to focus on more care and competence in the selection of the PRNG rather than on xor-ing.

Bottom line: Basically, the xor trick doesn't solve the problems people usually actually have when using PRNGs.


Prior to step (c) there are 7 units flowing from $v_1$ to $v_2$. The augmenting path pushes 8 units of flow from $v_2$ to $v_1$: 7 of these cancel the existing flow from $v_1$ to $v_2$, and 1 unit now flows from $v_2$ to $v_1$.

More generally, the residual network shows you how much flow you can push in each direction. The edge $v_2 \to v_1$ has a capacity of 11, so you can push up to 11 (=7+4) units in this direction.


Is there a reasonable and studied concept of reduction between regular languages?

Barrington, Compton, Straubing and Thérien showed, in their paper Regular languages in $\mathsf{NC^1}$, that if the syntactic monoid of a regular language contains a nonsolvable finite group then the language is $\mathsf{NC^1}$-complete with respect to $\mathsf{AC^0}$-reductions (these are reductions computed by polynomial size, constant depth circuits with unbounded fan-in). Barrington's theorem implies that all regular languages are in $\mathsf{NC^1}$, and so such regular languages are complete for the set of regular languages under $\mathsf{AC^0}$-reductions.

Since we know that $\mathsf{AC^0} \neq \mathsf{NC^1}$ (for example, the parity function is in the latter but not in the former), regular languages in $\mathsf{AC^0}$ cannot be complete. For example, the language $a^*b^*$ isn't complete. Similarly, $\mathsf{AC^0}[p] \neq \mathsf{NC^1}$, showing that the language $(aa)^*$ isn't complete.

The simplest example of a language which satisfies the condition above is the language of all words over $S_5$ (the symmetric group on 5 elements) which multiply to the identity. The syntactic monoid of this language is $S_5$, which is a nonsolvable finite group. The slightly smaller alternating group $A_5$ would also work.


How a NTM guessing depends on the input?

Suppose that the input has length $n$, and suppose that the machine already knows $n$. In order to non-deterministically choose a number from 1 to $n$, it performs the following algorithm:

Choose $m = \lceil \log_2 n \rceil$ bits non-deterministically, and interpret them as a number $x$ from $0$ to $2^m-1$.
Increase $x$ by one.
Reject if $x > n$.

The first step is implemented by a loop.


Proving a certain primitive recursive function exists

The function $g$ interprets $k$ as two inputs $k_1,k_2$. It runs $f(n,k_1)$ for $k_2$ steps, returns whatever $f$ does if $f$ halts, and returns $0$ otherwise.


How to represent calculable real numbers?

A number is obtained from natural numbers using addition, subtraction, multiplication, or division if and only if it is rational. You can store rational numbers as pairs $(p,q)$ of integers, which represent the number $p/q$ (so $q \neq 0$). You can further assume that $p,q$ are mutually prime.

Libraries implementing rational numbers using arbitrary-precision integers are available, for example GMP.


Matching algorithm, match pairs: what would be the right way to do it?

This isn't sorting: it's matching. The vertices of your graph are the data rows and there's an edge between two vertices if the two rows are compatible for pairing (e.g., have no difference bigger than 3, or whatever criterion you want to use).  You're looking for a maximum matching, i.e., a biggest-possible pairing between compatible rows.

It's unclear in your question but you might instead want to define a weighted graph where the weight of an edge is the amount of compatibility (e.g., rows that are very close have a high weight, rows that aren't so close have a low weight, rows that are incompatible have no edge, as before) and compute a maximum-weight matching.


Computing gaussian kernel for image blurring

Your function is used to compute 2D kernel, which you should normalize, otherwise if the sum of used weights is higher than $1$ your image gets lighter, when it is smaller it gets darker. You should not normalize vectors, because you apply 2D kernel, so normalized 1D vectors will not help.

The operation that you perform is convolution, not correlation, which in common meaning would try to measure how similar is the part of image to given kernel.


Reduction of Circuit Satisfiability to CNFSAT

The exponential blowup when converting circuits to conjunctive normal form is avoided by introducing new variables to represent the output of each sub-circuit plus a simple set of rules represent each sub-circuit and force their output into the variables (see Tseitin transformation).  The size of the resulting CNF formula is linear to the size of the circuit, and grows linearly as the circuit size is increased.


Calculation of Inorder Traversal Complexity

In order to analyse the time complexity of a tree traversal you have to think in the terms of number of nodes visited. If a tree has $n$ nodes, then each node is visited only once in inorder traversal and hence the complexity is $O(n)$.

Here, the input is in terms of number of nodes in the tree and the hence the complexity.

The notion that each recursive call is $T(n-1)$ is wrong. Let say we have a tree that has three children to the left of root and three children to the right of root. So n = 7. Now when you visit root then you have two paths. One to left which has 3 children and one to right which also has 3 children. But $7-1 \neq 3$. Hence this notion of 2 recursive calls of $T(n-1)$ is wrong.

It totally depends on the structure of the tree. In worst case a tree may degenerate to linked list  (a skew tree having children on only one side either left or right) and we know well that traversal of linked list is $O(n)$, for a list of n elements. Hence, also the worst case is $O(n)$.


If I have sources and sinks of a DAG can I find the minimum number of edges to be added to make it Strongly Connected?

Assuming there are no isolated vertices in the graph you only need to add $max(|\mbox{sources}|,|\mbox{sinks}|)$ edges to make it strongly connected.

Let $T = \lbrace t_1,\ldots,t_n\rbrace$ be the sinks and $\lbrace s_1,\ldots,s_m \rbrace$ be the sources of the DAG. Assume that $n \le m$ (the other case is similar). Consider a bipartite graph $G(T,S)$ between the two sets defined as follows: $G(T,S)$ has an edge $(t_i, s_j)$ if and only if $t_i$ can be reached from $s_j$.

Let $M$ be a maximal matching in $G(T,S)$. Without loss of generality assume that $M$ consists of $k$ edges: $\lbrace (t_1, s_1), (t_2, s_2), \ldots, (t_k, s_k) \rbrace$. In the original DAG $G$, add directed-edges $\lbrace (t_1\rightarrow s_2), (t_2\rightarrow s_3), \ldots, (t_{k-1}\rightarrow s_k),(t_k\rightarrow s_1)\rbrace$. It's easy to see that by adding these edges, the vertices induced by $M$ are strongly connected in $G$.

Now consider the remaining vertices in $G(T,S)$. Because $M$ is maximal, each vertex in $S-M$ (resp. $T-M$) should be connected to a vertex in $T$ (resp. $S-M$). So we pair up the remaining vertices arbitrarily, say $\lbrace (t_{k+1}, s_{k+1}), \ldots, (t_n, s_n)\rbrace$ and add the corresponding directed edges in $G$. For each remaining source vertex source $s_i$ ($i$ belongs to $\lbrace n+1,\ldots, m\rbrace$ we add the edge $(t_1\rightarrow s_i)$ in $G$. Thus the total number of edges added is $max(|\mbox{sources}|,|\mbox{sinks}|)$.


A (rather technical) answer, where star-operator is replaced by least fixed point (equivalent to recursive formulation as in CFG) is given by our cstheory cousins: Does there exist an extension of regular expressions that captures the context free languages?

The author (Neel Krishnaswami) of that answer does not know an original source of his construction, but a later comment by Tim Schaeffer refers to the 1973 book Formal Languages by Arto Salomaa. In chapter VI.11 Salomaa introduces regular-like expressions. That book might not be in your possession, but in turn refers to A characterization of context-free languages, Journal of Computer and System Sciences, 1973, by Jozef Gruska, which is open access.

The operator Gruska considers is the following, I loosely quote from his paper. Let $\sigma$ be a symbol and $L,L_1$ be languages.
The $\sigma$-substitution of $L_1$ into $L$, denoted by $L \overset{\sigma}{\uparrow}L_1$ is defined by

$$ L \overset{\sigma}{\uparrow}L_1 = \{ x_0 y_1x_1 \dots x_{k-1} y_k x_k \mid x_0 \sigma x_1 \dots x_{k-1} \sigma x_k\in L, \text{no $\sigma$ in }x_i, y_i\in L_1 \}.$$

After noting that he operation $\overset{\sigma}{\uparrow}$ is associative one defines the $\sigma$-iteration as

$$ L^\sigma = \{z \mid z\in L \cup L\overset{\sigma}{\uparrow}L \cup L\overset{\sigma}{\uparrow}L\overset{\sigma}{\uparrow}L \cup \dots \text{ does not contain an occurrence of } \sigma \}.$$

Note that if we have only a single variable, like $S\to aSbS \mid \lambda$ then this substitution closure $\{aSbS, \lambda\}^S$  is indeed the language generated by the grammar.


The word RAM is a model of computation in which basic operations operate on words. For example, adding two words costs $O(1)$ in this model. In algorithms class, it is often tacitly assumed that basic operations on indices and on data cost $O(1)$. For example, consider the following program for computing the maximum of an array:

calculate-max(A, n):
max = A[1]
i = 2
while i <= n:
  if A[i] > max:
    max = A[i]
  i = i + 1

This program is usually assumed to run in $O(n)$. This means that the following operations should all cost $O(1)$:

Assignment of data points (max = A[1], max = A[i])
Assignment of indices (i = 2, i = i + 1)
Comparison of indices (i <= n)
Comparison of data points (A[i] > max)
Arithmetic on indices (i + 1)

In order to accommodate this in the word RAM model, we need to assume that words have length at least $\Omega(\log n)$, since this is the length of indices such as i above. Usually words of length $\Theta(\log n)$ are enough for performance of an algorithm in the word RAM to match its performance as perceived by the algorithm designer. Therefore the most common word RAM model is the logarithmic cost word RAM, in which words have length $\Theta(\log n)$ (the constant doesn't matter since it only affects the running time by a constant factor).

The only remaining question is – what is $n$? It is usually assumed that $n$ is such that the input is $n$ words long. This definition is a bit circular (since the length of a word depends on $n$), but usually works out nevertheless.


Finding an element in an unsorted array equal to its rank in $O(n)$ time

You can preprocess the array to transform all negative numbers to $0$, and to transform numbers greater than $n$ to $n+1$. This transformation does not change the result because negative numbers and numbers greater than $n$ is not able to equal to its rank. This transformation only costs $O(n)$ time.

Now you can do counting sorting with $O(n)$ time.


As @babou indicated, there's no algorithmic way to produce a CFG from a description of a CFL, meaning that the problem is more art than science. There are, though, some idioms that turn out to be useful in practice.

Idiom 1. First, ignore the condition $i,j,k\ge 0$ for the moment, since that condition usually turns out to be easy to express in a grammar.

Idiom 2. See if the language can be expressed as the union or concatenation of simpler languages (intersection and complement are of less help, since CFLs aren't closed under these operations). In your case, the or in your original statement is a clue. Express your language as the union of simpler languages:
$$
\{a^ib^jc^k\mid i\ne j\}\cup\{a^ib^jc^k\mid, i\ne k\}
$$

Idiom 3. If you have an inequality, as you do here, note that we can express the $i\ne j$ condition as another or, namely $i\ne j\Longleftrightarrow (i > j) \lor (i< j)$, so
$$
\{a^ib^jc^k\mid i\ne j\}=\{a^ib^jc^k\mid i>j\}\cup\{a^ib^jc^k\mid i<j\}
$$
Idiom 4. Separate the problem into concatenated pieces if possible. For this example, we note that the $a^ib^j$ part will have nothing to do with the $c^k$ part, so we might start out grammar with the production $S\rightarrow TU$, where $T$ will generate the $a^ib^j$ and $U$ will generate the $c^k$ part. The latter is easy, and now we fill in the omission in idiom 1, writing $U\rightarrow cU\mid \epsilon$ (since if the requirement had been, say, $k>0$ we could just use $U\rightarrow cU\mid c$).

Idiom 5. Now what to do with the $a^ib^j$ part, where $i>j$? Simple, write it as $a^na^jb^j$ for some $n>0$. To get an arbitrary number of a's in front, we can use $T\rightarrow aT$. Eventually we'll stop generating a's and will switch to the matching a's and b's, using yet another variable $V$, so we'll have $T\rightarrow aT\mid aV$.

Idiom 6. Finally, to generate a matching number of a's and b's we work from the inside out, placing one of each on the ends, so we'll have $V\rightarrow aVb\mid \epsilon$. This is very common when dealing with CFLs.

Finally, then, we have the grammar for one part of our language:
$$\begin{align}
S&\rightarrow TU\\
T&\rightarrow aT\mid aV\\
U&\rightarrow cU\mid\epsilon\\
V&\rightarrow aVb\mid\epsilon
\end{align}$$
Of course, we still have a lot of work to do, but the rest is largely of the same form. Yes, it is complicated; all I can offer is that it gets easier with practice. Eventually, you might get to the stage where you'll often say "I've seen a problem like this before; maybe I can do something similar".


A problem about master theorem and recursion

Taking $n=2^k$, we have
$$T(n)=2T\left(\frac{n}{2}\right)+f(n)=\\=2\left[2T\left(\frac{n}{2^2}\right) +f(n)\right]+f(n)=2^2T\left(\frac{n}{2^2}\right)+2f(n)+f(n)=\\=2^3T\left(\frac{n}{2^3}\right)+2^2f(n)+2f(n)+f(n)=\cdots=2^kT(1)+f(n)[2^{k-1}+\cdots+1]=\\=2^kT(1)+f(n)(2^k-1) = nT(1)+f(n)(n-1)$$
Now we have 2 cases: 1. $T,f$ are defined only for $2$s powers and 2. $T,f$ are defined on $\mathbb{N}$.

Considering non negative functions, condition $T \in O(f)$    gives
$$ f(n)(n-1) \leqslant T(n) \leqslant C f(n)$$
which is impossible for any below boundedness for $f$.

If we demand $T$ defined on $\mathbb{N}$, then we come to necessity to define $T\left(\frac{n}{2}\right)$ which can be filled by OP.


Which data structure can be used to determine most experienced person in a shift?

Let $s_i$, $e_i$, $x_i$, be the shift start time, shift end time, and experience of the $i$-th worker.
For each worker define the following two events:

A shift-start event is a triple $(s_i, 0, i)$.
A shift-end event is a triple $(e_i, 1, i)$.

Collect all events in an array $E$ and sort it in increasing order (lexicographically). This requires $O(w \log w)$ time.
We will process these events in order. Maintain a pointer $p$ to the next event in $E$ to process. Also maintain a priority queue $Q$ that supports deletions (an implementation using a binary heap suffices). Initially $Q$ is empty.
For each hour $t$ of the day, in increasing order, do the following:

Scan $E$ by advancing $p$ to find all (shift-start) events of the form $(t, 0, i)$. For each such event, add key $i$ with priority $x_i$ to $Q$.
Look at the key $j$ at top of $Q$ (in constant time). Report $j$ as the most experienced worker at time $t$.
Scan $E$ by advancing $p$ to find all (shift-end) events of the form $(t, 1, i)$. For each such event, delete key $i$ from $Q$.

This requires $O(w)$ space to store $E$ and $Q$, and at most $O(n + w \log w)$ time since there are $2w$ insertions/deletions into/from $Q$, each of which requires $O(\log w)$ time.


Primary clusting in linear probing coliision resolution: there can only be one cluster/block, right?

For single key, there is only one block. But as it grows, it may reach the next cluster, making this cluster much larger:

aaaa.bbbb...

Here aaaa is cluster for "a" key, and bbbb is cluster for "b" key. Once you fill the first "." entry with data, clusters are combined. Now the next item for "a" key will be inserted after bbbb, so find() operation need to search the entire cluster:

aaaaabbbba..

There are techniques such as Robin Hood hashing which keeps all keys sorted by the position of the first entry where they can be stored, so the same data will build the following table:

aaaaaabbbb..


Merging two splay trees whose ranges may overlap in $O(\log N)$

No, you cannot merge two splay trees whose ranges may overlap in  $O(\log N)$, where $N$ is the total number of nodes. You may have to move at least $\Theta(N)$ nodes in general or average situations.

It contains no information at all when we know "whose ranges may overlap". The ranges of any two splay trees may overlap.

It contains no information at all when we know all elements of A are not necessarily smaller than all elements of B. That is the same as all elements of A are not necessarily larger than all elements of B.


Allocating flows in a network while avoiding a particular node

Flows with more than one "thing" flowing are known as "multicommodity flows".

The basic definitions assume that every thing can flow through every vertex and edge. However, the standard way of solving these problems is linear programming and you could easily modify the normal multicommodity flow program to deal with your situation, just by substituting zero for the appropriate variables.


What is the complexity of determining Satisfiability of a CNF containing both Horn and Dual Horn clauses?

3-CNF formulas contain a mixture of only Horn and dual-Horn clauses.  3-SAT, the Boolean satisfiability problem over 3-CNF formulas, is known to be NP-complete.  So it is unlikely that the satisfiability of such formulas can be decided in polynomial time.


Undecidability of TMs recognizing a decidable language

Given a machine $A$, construct a machine $M$ which on input $x$, acts as follows: run $A$ on the empty input, and if it ever halts, run the Turing machine encoded by $x$ on the empty input.

If $A$ halts on the empty input then the language $M$ recognizes is the halting language, while if $A$ doesn't halt on the empty input then the language $M$ recognizes is the empty language.


Why does Karger's algorithm work "with high probability"

Lets say that the algorithm succeeds if it produces a min cut. First, it is proved that a single run of the algorithm succeeds with probability $\Omega(n^{-2})$, i.e. with probability $\ge \frac{c}{n^2}$ for some $c>0$.

This is, of course, very bad. For large $n$ our success probability converges to zero. However, if we run it independently $k$ times, then our failure probability is now $\left(1-\frac{c}{n^2}\right)^k$ (we choose the minimal cut obtained from the $k$ runs, in order to fail finding the cut in this manner we must fail every time). Finally, we have:

$\Pr\left[\text{failure}\right]\le \left(1-\frac{c}{n^2}\right)^k\le
e^{-\frac{kc}{n^2}}$, taking $k=n^2\log n$ we get:

$\Pr\left[\text{failure}\right]\le e^{-c\log n} = \frac{1}{n^c}$, which converges to zero, as apposed to our failure probability after a single run of the algorithm.


When you solve the longest increasing subsequence problem in its original formulation, you are finding the longest sequence $i_1,\ldots,i_\ell$ such that
$$
a_{i_1} < \cdots < a_{i_\ell} \\
b_{i_1} < \cdots < b_{i_\ell}
$$
This holds even if you shuffle the indices. Since the object you are maximizing is symmetric in the $a$s and $b$s, you will get the same length in both cases.


Ehrenfeucht-Fraïssé games, possible mistake in example

Spoiler wins the $3$-move EF game by picking $a_1$, $a_2$, $a_3$ in any order. You can confirm this by observing that there is a formula of quantifier rank at most $3$ that is satisfied by $A$ but not by $B$, namely:

$$
\exists x\exists y\exists z \ .\  x\neq y \wedge y \neq z \wedge z \neq x \wedge r(x, y) \wedge r (y, z) \wedge r(z, x)
$$

where $r$ is the adjacency relation. Since $A$ has $3$ vertices and $B$ has $4$, Spoiler will also win any $k$-move game for $k\ge 4$, probably the question meant to ask about the $2$ and $3$-move games respectively, instead.


Is there an undecidable finite language of finite words?

Yes, there is a need for $L$ to be infinite in order to be undecidable.

To add up on the answers of Raphael and Sam, you should think about "decidable" as things that a computer-program can solve. The program required is very simple, it just needs to output "Yes" for elements in $L$, or otherwise, say no.

So the more "complex" $L$ is, the longer the program you are required to write. In other words, the longer the program you run, you can check more things... So if someone gives a language $L$ which is finite, say $L=\{ a_1, a_2, \ldots, a_n\}$, you can write the following program:

if INPUT = $a_1$ output Yes;
if INPUT = $a_2$ output Yes;
...
if INPUT = $a_n$ output Yes;
output No;

Now, if some one gives you a larger $L$ (yet finite), you will just write a longer program. This is always true, and any finite $L$ will have it's own program. The only "interesting" case is what happens when $L$ is infinite - your program cannot be infinite.

The issue of "undecidability" is even more interesting: its those (infinite) $L$'s that have no program that works correctly for them. We know that such languages must exists since there are way more (infinite) languages $L$ than the number of programs of finite (but unbounded) length.


Create a turing machine for log base 2 of n

The value of $\lceil\log_2(n)\rceil$ is more or less equal to the number of bits in the binary representation of $n$ (except if $n$ is a power of 2).
You can then imagine a Turing Machine with an input tape (on which is written the number), a work tape and an output tape. First, you need to convert your unary number on the input tape, into binary on the work tape. This can be done with a simple incrementation Turing Machine (you can decide on the side of the least significant bit, but imho left is easier). Then, you need to count the number of bits in the binary number, and write a $1$ for each bit counted. You can use an additionnal state, to detect is the number is a power of 2 (a $1$ followed only by $0$).
This machine can be reduced to two tapes by replacing bits by $1$ on the work tape (except maybe for the last one which needs to become $\#$ if $n$ is a power of $2$). It can be further reduced to one tape by using the read part of the tape to write the binary number (and another symbol than $\#$ to replace the $1$ which are read).
Let's be more formal:
I consider a Turing Machine $(Q, \Sigma, \Gamma, \delta, q_0, q_f, \#)$ where $Q$ is the set of states of the TM; $\Sigma = \{1\}$ is the input alphabet; $\Gamma = \{0, 1, \\\$, \#\}$ is the work alphabet ($\\\$$ is a symbol to separate the input and the output), $\delta$ is the transition function, $q_0\in Q$ is the initial state, $q_f \in Q$ is the final state and $\#$ is the blank symbol. The Turing Machine I imagined is composed of 13 states, it may be possible to do better. Here is the detail on each state (to understand how the TM works) :

$q_0$: initial state
$q_1$: I have read only one $1$ in the input
$q_2$: I have read only two $1$'s in the input
$q_3$: I am reading another $1$ in the input ($q_1$ and $q_2$ make it easier to separate the input and the output)
$q_4$: I am returning to the most left to increment the binary representation
$q_5$: I am incrementing, and there is still a carry
$q_6$: I have finished incrementing, I return to the input to read $1$'s
$q_7$: I have finished reading completely the input, I am returning to the most left to transform the binary representation of $n$ into unary representation of $\lceil\log_2 n\rceil$
$q_8$: I am replacing $0$'s by $1$'s without having seen a single $1$
$q_9$: I am replacing $0$'s by $1$'s having seen a single $1$
$q_{10}$: I am replacing $0$'s by $1$'s having seen at least two $1$'s (therefore $n$ is not a power of $2$)
$q_{11}$: I have concluded that $n$ is a power of $2$, so the last $1$ must be replaced by $\#$
$q_f$: final state

Here is the detail of the transition function, state by state. The first column is the current state of the Turing Machine, the last 4 correspond to the read tape symbol. Each box is given as a triple $(\alpha, q, d)$ where $\alpha$ is the symbol written on the tape, $q$ is the next state and $d$ is the direction of the head shift.

State
$0$
$1$
$\\\$$
$\#$

$q_0$
-
$1, q_1, \rightarrow$
-
$\#, q_f, \rightarrow$

$q_1$
-
$1, q_2, \rightarrow$
-
$\#, q_{11}, \leftarrow$

$q_2$
-
$\\\$, q_3, \rightarrow$
-
$\#, q_{11}, \leftarrow$

$q_3$
-
$\\\$, q_4, \leftarrow$
$\\\$, q_3, \rightarrow$
$\#, q_{7}, \leftarrow$

$q_4$
$0, q_4, \leftarrow$
$1, q_4, \leftarrow$
$\\\$, q_4, \leftarrow$
$\#, q_{5}, \rightarrow$

$q_5$
$1, q_6, \rightarrow$
$0, q_5, \rightarrow$
$1, q_6, \rightarrow$
-

$q_6$
$0, q_6, \rightarrow$
$1, q_6, \rightarrow$
$\\\$, q_3, \rightarrow$
-

$q_7$
$0, q_7, \leftarrow$
$1, q_7, \leftarrow$
$\#, q_7, \leftarrow$
$\#, q_8, \rightarrow$

$q_8$
$1, q_8, \rightarrow$
$1, q_9, \rightarrow$
-
-

$q_9$
$1, q_9, \rightarrow$
$1, q_{10}, \rightarrow$
-
$\#,q_{11},\leftarrow$

$q_{10}$
$1, q_{10}, \rightarrow$
$1, q_{10}, \rightarrow$
-
$\#,q_f,\leftarrow$

$q_{11}$
-
$\#, q_f, \rightarrow$
-
-

Here is a simulation of this TM : http://turingmachinesimulator.com/shared/eikrrbjoiz


Minimum vertex cover algorithm with linear programming

Consider the graph
  2-4---7
 /  |\ /|
1   | × |
 \  |/ \|
  3-5---6

Setting $x_1,x_2,x_3,x_6$ or $x_7$ to 0 gives your LP a value of 4, while setting $x_4$ or $x_5$ to 0 gives your LP a value of 5. However, if you set $x_1=0$, you will finally get a vertex cover of size 5, while the optimal vertex cover is of size 4.


If we give the input $<U, <M,w>>$ to the Turing machine U, it will simulate the Turing machine U on input $<M,w>$. The behavior of the simulated machine U on input $<M,w>$ is to simulate the Turing machine $M$ on input $w$. So it seems like the behavior would still be a Turing machine that simulates $M$ on input $w$. At least two questions need further clarification:

How is the input $w$ encoded? If we have a requirement that only input where "$<$" and "$>$" are "perfectly matched" is allowed, then we can just copy the input "w" unmodified between $<M,$ and $>$. This is the strategy used by Tcl, which can be surprising if you are not used to it. Otherwise, you have to encode the input "$w$" suitably, which can mean that you have to escape "$<$" and "$>$", as well as the escape character itself. In this case, the "$w$" in $<U,<U,<M,w>>>$ is quite different from "$w$" itself, because it has been encoded multiple times. For example the escape character "\" might have turned into "\\\\\\\\".
What exactly do we mean by "simulate"? The most important aspects of a simulation of a Turing machine is whether it halts or not. If the Turing machine M halts, it is (or can be) also important which output it leaves on its tape. If the machine M doesn't halt, we need to be careful how to define the output of the machine. For simplicity, let's assume that either the machine has a dedicated output tape, or that we don't care for the output in case the machine never halts. The output should never be encoded like the input, but directly match the original output.

What about the efficiency of the simulation? A good simulation would have only a constant offset in memory consumption and a logarithmic factor (logarithmic in the input to $U$) in runtime (->multi-tape Turing machine is assumed here). Both properties seem to be conserved by applying $U$ to itself, so you still have an efficient simulation of $M$ on input $w$ if you apply $U$ (repeatedly) to itself.


Faster way of calculating how many ways can $2n$ elements be paired?

There is one algorithmic improvement if $n$ is large and you want to express this number for example as a decimal or binary number without any rounding errors: Let's say you have $n$ equals one billion. You will do about 500 million multiplications, and if you do this in a straightforward way, you will multiply various numbers from 1 to a bit over 4 billion digits by some small number. Multiplying an $n$ digit number by a small number takes $O(n)$ steps, so your product all in all takes $O(n^2)$ steps.

It's faster if you calculate 250 million products of up to 9 digit numbers giving 250 million 18 digit numbers, then 125 million products of 18 digit numbers giving 36 digit numbers and so on, until finally you multiply two numbers of 2 billion digits each. Multiplying $k$ digit numbers can be done in $O (k \log k)$ instead of $O (k^2)$, and therefore the total work is $O (n \log^2 n)$.

A completely different improvement for large $n$ is to use the Stirling approximation $n! \approx n^n \mathrm{e}^{-n} (2\pi n)^{1/2}$, and substitute that in the formula in Yuval's comment. Obviously that gives an approximation only.


How does a predictive coding aid in lossless compression?

Huffman coding, as usually applied, only considers the distribution of singletons. If $X$ is the distribution of a random singleton, then Huffman coding uses between $H(X)$ and $H(X)+1$ bits per singleton, where $H(\cdot)$ is the (log 2) entropy function.

In contrast, predictive coding can take into account correlations across data points. As a simple example, consider the following sequence:
$$
0,1,2,\ldots,255,0,1,2,\ldots,255,\ldots
$$
Huffman coding would use 8 bits per unit of data, whereas with predictive coding we could get potentially to $O(\log n)$ bits for the entire sequence.


CFG for all strings of a’s and b’s that contain a different number of a’s and b’s

In fact, your grammar is correct and clean!

Here is how your grammar generates $abbab$.

$$S\Rightarrow B\Rightarrow EB\Rightarrow^* abB
\Rightarrow abbE\Rightarrow^* abbab $$

Exercise. Show your grammar is correct.


The insertion order is relevant for the height of the tree.
Inserting (in this order) 1,2,3,4,5,6,7,8 gives a tree of height 3, while inserting these keys in the order 1,3,4,6,7,8,2,5 gives a tree of height 2.

In order to create a tree of minimal height, you can place the keys with ranks $\lceil \frac{n}4\rceil$, $\lceil \frac{n}2\rceil$, and $\lfloor \frac{3n}4\rfloor$ in the root, partition the remaining keys accordingly into the subtrees and apply the this recursively to each of the subtrees. Depending on the number of keys, you may have to shift a few keys around between leaves and their parents to make sure that all leaves are at the same level.