What is the time complexity of memory allocation assumed to be?

what would the worst-case complexity be if it didn't have to copy over $n$ items? If it only needed to allocate a buffer with size $O(n)$ when resizing, would that be considered to run $O(1)$ or $O(n)$ time?

This depends on what you mean by "allocate a buffer with size $O(n)$" and how much time that takes. Unfortunately, there isn't a standard answer for that. It boils down to how you model "allocating a buffer", and your assumption about the time complexity of that operation.

You could assume that allocating such a buffer could be done in $O(1)$, or you could assume that this takes $\Theta(n)$ time. It depends on the system you're trying to model:

The operating system will generally overwrite memory that has previously been used by another process with all zeros to avoid leaking information from one process to another. Thus, allocating a size-$n$ buffer will take at least $\Omega(n)$ time due to this initialization procedure.
If you are working in a very low-level setting (for instance assembly programming), "allocating a buffer" might you mean grabbing a pointer to the top of the heap and then incrementing that pointer by the number of elements you want to allocate. You could reasonably model this as an $O(1)$ operation.
If you are, for instance, working in C and initialize a buffer by calling malloc, then there is generally no guarantee about the complexity of this operation. It might take $O(1)$ time, $O(n)$, $O(n^2)$, exponential time or even fail to allocate the buffer at all (out of memory). On the other hand, specialized implementations of malloc (such as TLSF) might come with guarantees.

Thus, depending on the implementation, the operation "allocating a buffer" should be modeled as having a different time complexity. If you are working in a purely theoretical setting (without any underlying implementation), then you have to make an assumption. Assuming it takes $O(n)$ time is more reasonable than assuming it would take $O(1)$ time (since more real-world systems will be able to meet the former assumption than the latter), however, any assumption, if clearly stated is valid. It is even possible to reason about totally unreasonable assumptions (for instance, you could assume that you could copy over $n$ items in $O(1)$ time) for the sake of argument.


Proving the language of words with equal numbers of symbols non-context-free

It is known that the intersection of a context-free language with a regular language is context-free. If EQUAL were context-free, so would be its intersection with $a^*b^*c^*$, which is the well-known non-context-free $\{a^nb^nc^n : n \in \mathbb{N}\}$.


Finding the complexity of a recursive method

You have to analyze the circumstances in which your algorithm makes a recursive call. That is, when is  not done true? Well, your it's true whenever your algorithm is required to make a swap in one of its passes over the array (one of the while loops). To analyze the total worst case running time, determine the maximum number of recursive calls, and add up the total work in each of these calls. In some recursive algorithms, the amount of work in each recursive call might be different. Is that the case in your algorithm?


Hexadecimal notation is just a shortcut writing one hexadecimal digit instead of four bits. For example 1A is exactly the same as 00011010. So eight hexadecimal digits give you the same as the binary32 format.

What you describe may be that someone takes one sign bit, 2 hex digits for the 8 bit exponenent, and 6 hex digits for the 23 bit mantissa. That would be possible but a bit misleading.


Is a Knapsack Problem with only Color Constraints NP-Complete?

So, items have only 2 parameters:

Color. I assume that each item has one color ("one of C colors"). If not, this problem is probably $\mathsf{NP}$-hard.
Price.

Now we need to pack a knapsack to maximize the price. Knapsack can have at most $k$ colors.

Algorithm:

For each color count the total price of items that are colored by color $C_i$. Call these values $P_i$. Takes linear time.
Find $k$ maximal values of $P$. Takes polynomial (linear?) time. Can be done using sorting.

This is the answer.


How hard is this constrained $n$-rooks problem?

This problem can be solved in polynomial time, using bipartite matching.

For a bipartite graph with $n$ vertices on the left, corresponding to the $n$ rows, and $n$ vertices on the right, corresponding to the $n$ columns.  Include an edge from $i$ to $j$ if $C(i,j)=1$, i.e., if you're allowed to place a rook in the $(i,j)$ square (in the $i$th row and $j$th column).  Now check whether there exists a perfect matching of this bipartite graph.  This can be done in polynomial time using standard algorithms.

Notice that there exists a perfect matching if and only if there exists a way to place the rooks so they are non-attacking.  Each edge in the matching corresponds to a place where a rook should be placed.  Two rooks can attack each other only if they share the same row or the same column.  A matching cannot have two edges that share the same left-vertex (same row) or same right-vertex (column), which means that any matching containing $n$ edges corresponds to a way to place $n$ rooks so they don't attack each other.


If you want to detect anomalies, my suggestion would be to build a classifier to classify individual frames of the video to determine whether that frame contains an anomaly.  You'll need to categorize what you count as an "anomaly" and arrange for labelled data in your training set.  But then you can extract all 6800 frames from the training videos, label each frame, and train a classifier on that training set of 6800 images.  At this point the problem is the same as building a classifier on individual images.  Then, given a test video, you apply the classifier to each frame to determine whether any of its frames contain an anomaly, and aggregate those results somehow (e.g., report the video as anomalous if the number of anomalous frames exceeds some threshold).


Substituting two different identifiers with the same identifier in Coq - why does this work?

it looks like we are assuming l2 doesn't change in the induction case.
  But when we later apply it with l2:=l1, we are breaking this
  assumption.

No. If we regard l1 to be a value which is repeatedly decreased in the induction proof, note that we let l2 to be equal to the initial value of l1 -- such value will not change in the induction steps. In other words: the value of l1 will decrease, but l2 will always be the initial value of l1.

We can even compare it with recursion in programming:

# pseudocode
def f(x, y):
   if x==0: return baseValue
   use f(x-1, y)
   return something

Just because f(x, y) is defined by induction on x, it does not mean that later on we can't call f(a, a) where both arguments have the same value a.


Min path cover problem in Cormen et.al. question about notation

The graph $G'$ has $2n+2$ vertices. We give them the names $x_0,\ldots,x_n,y_0,\ldots,y_n$ to make it easy to refer to them. So $x_i,y_i$ are just names of vertices. They have no value, and do not refer to anything. In that regard, they are akin to indeterminates.
What might be confusing you is the existence of a different graph $G$, which has $n$ vertices. The vertices $x_i,y_i$ are just vertices – they are not variables referring to vertices of $G$. The "value" of $x_i$ is just $x_i$.


Undecidability of the following language

You can construct a recognizer that simply simulates M on w and then simulates M on $w^R$. This will halt in finite time for all  that are in A (by definition), and then you can accept if the first simulation accepted and the second rejected. That suffices for the language being recognisable (recursively enumerable).

I'm not sure what you mean by "how does the machine know what's $w$ and $w^R$ ?" w is part of the input  pair, and w^R is easily generated from it. The way you've defined the language A, you don't have to worry about guessing which is the one that M should accept and which is the one it should reject. But if the language was  such that either M accepts w and rejects in finite time w^R or M rejects w in finite time and accepts w^R, then it's still easy. You do the same thing and accept if exactly one of the two simulations accepts, without caring which one.

I don't actually know a "standard" proof that $A$ is undecidable. But to prove your new language undecidable, I'd make a decider for A_TM that on input  produces M' that rejects all other input than w and behaves as M on w. M' definitely rejects $w^R$ in finite time, so  will be accepted by the decider for your language iff M accepts w. I imagine to prove $A$ undecidable you do the same thing but make M' accept all other strings, so it definitely accepts $w^R$ and accepts w iff the hypothetical $A$ decider accepts.


What does it mean to have a continuous action space w.r.t. to reinforcement learning?

When you're driving of your car and you turn the wheel, is that a discrete or a continuous action?  It's continuous, because you can control how much you turn the wheel.  How much do you press the gas pedal?  That's a continuous input.  This leads to a continuous action space: e.g., for each positive real number $x$ in some range, "turn the wheel $x$ degrees to the right" is a possible action.


How to convert DFA to regular expression using arden's rule

Your equations are wrong; your solution works for the reversed arrows. You should be solving the following system:
$$
q_0 = (b+c)q_0 + aq_1 + \epsilon \\
q_1 = cq_0 + aq_1 + \epsilon
$$


How to get Loop invariants to prove program is correct in Hoare logic

By definition, an invariant of while guard do c is a property I for which {I && guard} c {I} is a valid Hoare triple.

In your case, it is enough to prove the validity of what you wrote in the body, namely

{x == A^i && i != N}//Invariant and Guard
x = x * A;
i = i + 1;
{x == A^i} //invariant

This can be done using the rules for assignment and composition. Usually, it's best to proceed backwards, from the bottom of the code block, recovering the (weakest) precondition in the process.

{x == A^i && i != N}
{x*A == A^(i+1)}
x = x * A;
{x == A^(i+1)}
i = i + 1;
{x == A^i}

We now get two Hoare assertions one after the other at the top. This means that we proved the validity of

{x*A == A^(i+1)}
x = x * A;
i = i + 1;
{x == A^i}

when we actually need instead

{x == A^i && i != N}
x = x * A;
i = i + 1;
{x == A^i}

For that, we can exploit the weakening rule (AKA "Pre-" or "PrePost" rule). Such rules simply states that we need to prove the implication between the topmost assertion and the other one. Concretely, we need to prove the implication

(x == A^i && i != N)
   ==>
(x*A == A^(i+1))

which trivially follows by arithmetic.


What is the relation between pure mathematics, applied mathematics and Cellular Automata?

The definitions given in Wikipedia are trying to convey a very abstract concept by means of examples, which, to my taste, isn't satisfactory.

Thus, before answering this question we'd need to ask ourselves why are there two in the first place.  And if there is a real need for two, then:

  How is mathematics (both pure and applied) possible?
  -- Immanuel Kant

History

The answer to the first question appears to be very involved.  In European tradition, the question goes back to Plato's distinction between the ideal and the concrete.  These roughly translate into analytic and synthetic in modern philosophical language.  Plato ultimately believed that mathematics is discovered rather than constructed, but this still puts mathematics in the realm of ideal due to Plato believing that only the ideal actually exists, and that the concrete is but an imperfect reflection of the ideal.  This was in stark contrast to the existing tradition of viewing mathematics as a practical skill of measuring and counting.

Since that time on, multiple attempts were made to either unify both, or to define one in terms of the other, or to completely dismiss one of the two.  Ultimately, in the beginning of the 20'th century the argument boiled down to the ability of defining the classical mathematics.  This split the philosophy of mathematics into logicism (with Frege as its forerunner), formalism (with Hilbert as its advocate) and psychologism (intutionism), the idea advanced by Brouwer.  Somewhat under-represented here are the universalist views held by Klein (no good online quotes, sorry).  The later is the view that synthetic and analytic truth are the same, and that when a seeming contradiction arises, it is probably because we either don't have a proper observation technique, or that we don't have a proper mathematical explanation for the observation.

The Problem

It all boils down to the question of what is truth, and are there different kinds of truths?  I will first give an example of the problem and then discuss it.

Stating that

$$
    \textit{bachelors are males}
$$

Imposes a restriction that the interpretation of "bachelors" must be a subset of the interpretation of "males", but this restriction doesn't result from logical construction of the sentence, rather it is our experience (and the reasoning non-included in this sentence) that all bachelors we've seen so far, and are likely to meet in the future will be male.  This is an example of synthetic truth.  While in this example it may look like it could be possible to resolve the problem by adding more logical predicates, the problem is in fact unresolved as of now.  More generally, this can be seen as the disparity between material implication and "real" implication.

Using material implication, typically denoted as $\implies$ we can obtain:

$$
\textit{water is wet} \implies \textit{sky is blue}
$$

And while the sentence is true in a pure logical sense.  From the perspective of non-logical, or extra-logical reasoning it is false, since the perceived properties of water have no immediate impact on the perceived color of the sky.

Lewis was, perhaps, the first to notice and try to address this general problem by creating more restricting logical systems.  Another way to approach this problem, and the stance taken by many contemporary philosophers is laid out in Two Dogmas by Quine.  To quote the later:

  Physical objects, small and large, are not the only posits. Forces are another example; and indeed we are told nowadays that the boundary between energy and matter is obsolete. Moreover, the abstract entities which are the substance of mathematics -- ultimately classes and classes of classes and so on up -- are another posit in the same spirit. Epistemologically these are myths on the same footing with physical objects and gods, neither better nor worse except for differences in the degree to which they expedite our dealings with sense experiences.

Put simpler: "pure" mathematics is just a convenience, a make-believe thing that doesn't have any factual content and has no bearings on what truth is.  Surprising as it may sound, we still use the terminology in its pre-Quinean sense.

Finally

When forced to define abstract and applied mathematics, I'd say that:

Applied mathematics is pure mathematics restricted to the synthetic truth.  I.e. the kind of mathematics that can be verified by experimentation.
Pure mathematics is the art of discovery of patterns.  The parallel between art and mathematics is not new, and, in fact, Hardy, the iconic pure mathematician holds that:

  I am interested in mathematics only as a creative art.

Your question

So, having dealt with preliminaries :) to answer your question!

Pure mathematics can find more than one interesting aspect of cellular automata to study.  There are so-called "free objects" in mathematics - those possess only one interesting property which defines them.  CA isn't one of those.  It is a whole area of research, so any example of its treatment in pure mathematics will not be exhaustive.  One such (non-exhaustive!) example is to represent this particular CA as a function in domains being CA's input and output, and study the function's behavior in the usual way (answering questions about totality, bijection etc.)
Pascal's triangle can be a subject of applied mathematics as you can easily build a physical model for it and convince yourself of the calculation that you do by means of counting the elements of the model.  Since, at least from my perspective, applied mathematics is the restricted version of pure mathematics, this means that regardless of your ability to build a physical model, this is still valid pure mathematics.

PS

The views expressed above are certainly biased and don't represent the absolute majority of the people involved in this field.  You would benefit a lot from reading literature dealing with subject matter.


Finding nearest of a list of points on Euclidian plane to a given reference point

You can build a 2d binary search tree for the points in $L$ and then have closes-point queries done in expected $O(\log n)$ time: (see this presentation by Robert Sedgewick, pp.26-27). However, the worst-case time is still $O(n)$. An example of the worst-case input is the situation when all the points from $L$ lie on a circle and $R$ is the center of that circle.


The purpose of a hash in this scenario to be able to uniquely identify an entity.   It's not strictly unique, only probabilistically unique.

Hashes are not reversible functions, so your client can't know the data that was encoded with it.  It could be guessed by brute force and maybe some know attacks to the hash assuming the type/format of data is known, but in principle is not reversible).

So process A (system or organization) A can work with the facts of the entity uniquely identified by the hash without knowing the personal identity value.  Process A can then pass the processed information back to process B, that knows the personal identity value and then can combine the information given to Process A and the information it already has and carry out another processing.

The advantage in this case from a security perspective is that you have less security issues as process A (system or organization) will never has access to that personal identity.  Even if A is hacked, the personal data is safe*.


Firstly the $t<d$ condition, applies to either the row or the column codes on their own. So you know that a single error in each row or column can be detected since $d=2$.

Given 3 errors overall for the array, consider the decompositions of errors into distinct rows. Clearly

$3=3$,
$3=2+1$, or
$3=1+1+1$

are the only possibilities.

In case 3 the column parity checks can correct these errors separately so we're done.

In case 2 the single error can be corrected on its row, and the remaining two errors on a single row, can be corrected  by the parity check in the corresponding column.

In case 1 all 3 errors are on one row, so by definition they are on 3 distinct columns and can be corrected by the parity check in the corresponding column.

So the array code can correct 3 errors.


Prove that a sequence of increasing find operations on a splay tree takes $\mathcal{O}(n)$ time

Here is a helper fact.

(Simple cost of splaying) Let $c(v)$ be the time it takes to find an element $v$ in a splay tree. There exists a constant $c_0$ independent of the splay tree and $v$ such that $c(v)\le c_0d(v)$, where $d(v)$ is the depth of $v$.

Here is the sketch of a proof.

There are two tasks that contribute to $c(v)$.

To locate $v$ by going from the root downwards to the $v$, which takes at most $c_1d(v)$ time for some constant $c_1$.
To splay $v$ to the root. It takes each splay operation of zig, zag, zig-zig, zag-zag, zig-zag, zag-zig some constant time to move $v$ nearer to the root by 1 or by 2, splaying $v$ to the root takes at most $c_2d(v)$ time for some constant $c_2$.

Let $c_0=c_1+c_2$. Proof is done.

  Suppose we have a splay tree and a sequence of Find operations, where the elements we are searching for are in increasing order. Then the total time necessary to run the sequence is $O(n)$, where $n$ is the number of nodes in the tree.

Let $v_0, v_1,\cdots, v_m$ be an array of elements in increasing order.

It takes $O(n)$ to find $v_0$ (including splaying $v_0$ to the root).

What about finding the remaining $m$ elements?

Finding $v_1$ when $v_0$ is at the root takes at most $c_0d_{v_0}(v_1)$ time, where $d_{v_0}(v_1)$ is the depth of $v_1$ in the splay tree with $v_0$ as the root. Note that splay tree is a binary search tree, $d_{v_0}(v_1)$ is at most one one more than the number of elements between $v_0$ and $v_1$ exclusively.
Finding $v_2$ when $v_1$ is at the root takes at most $c_0d_{v_1}(v_2)$ time, where $d_{v_1}(v_2)$ is at most one one more than the number of elements between $v_1$ and $v_2$ exclusively.
$\vdots$
Finding $v_{m}$ when $v_{m-1}$ is at the root takes at most $c_0d_{v_{m-1}}(v_m)$ time, where $d_{v_{m-1}}(v_m)$ is at most one more than the number of elements between $v_{m-1}$ and $v_m$ exclusively.

So, the total time necessary to run the sequence of finding $v_1, v_2,\cdots,v_m$ is at most $c_0d(v_0, v_m)$, where $d(v_0, v_m)$ is at most one more than the number of elements between $v_0$ and $v_m$ exclusively, i.e., $d(v_0, v_m)\le m\lt n$.

So the total time necessary to run the sequence of finding $v_0, v_1, v_2,\cdots,v_m$ is at most $O(n) + c_0n$, which is $O(n)$ still.


Compilation is only a process of converting your code to assembly language. To achieve this task there is no need to interact with OS kernel.

If you also mean linking, interaction with OS is again not a requirement. However, if certain optimizations, or naming conventions and versions are involved, linking might access operating system information. Still, again no code is executed in the kernel level.


Image segmentation generates inclusions and is not smooth

If I understand correctly, you need to use erosion and dilation morphological filter.
To ged rid of inclusion, like below ring finger, blob detection would be helpful, to detect small blob and erase it (meassure its area and decide based on that).
As for continuity, simple blur after errosion helps to get it smoother, if effect is too small, then use contour trace and smooth it via curves (RDP algorithm, convert it to Catmull-Rom or B-spline and smooth it from here). If you take curves approach, take the contour and discard rest, it automatically solves component inclusions.

The inclusion in index finger is too big to be handled by erosion and dilation, as it may change geometry too much.  Fast idea is to generate circles of estimated radius (you know from scale or further detection that finger should be say 40px wide), so circles should push contour of finger, standardizing it's size). With curves, it is quite simple to handle checking distance to "parallel" wall.

Another approach is to take skeleton and draw fingers yourself, but this requires separate palm handling.


Why is the OS design able to reduce power consumption?

Common CPUs that go into smartphones, laptops and even desktop PCs have a variable clock rate. When the scheduler detects that it has idle time, it can reduce the clock rate, and increase it again if there are more processes competing for CPU time.

CPUs optimized for battery-powered devices tend to be composed of many functional components that each have their own clock (example: ARM Cortex A8). When one component is idle, the operating system can turn it off (or reduce its clock), which saves power. For example, on many multicore CPUs (such as the ones in high-end mobile devices), each core can be turned on or off separately. ARM is particularly good at this game, which is one of the reasons why most smartphones have ARM CPUs.

Varying the clock rate or turning off the clock of electronic components is known as power management. It tends to be a complex part of writing and optimizing an operating system for a battery-powered device, with many dependencies on the exact hardware model.

What goes for the CPU goes for peripherals too. The backlit display is a major consumer of power on a smartphone, for example, followed by the radio. The CPU operating system may play a role in power management of peripherals; secondary chips also runs their own firmware which performs power management as well.

Applications have their part to play in keeping power consumption down: they must allow the operating system to do its thing. The worst thing an application can do is polling — running a loop like while (not_ready()) {}. Even introducing a small delay as in while (not_ready()) {usleep(100);} doesn't help as it doesn't allow enough time for the processor to go into low-power mode, or if it does, each unfruitful wake up means wasted energy. Thus the operating system APIs must be designed so that applications never need to poll, but can instead subscribe to some kind of event mechanism and remain idle until they are notified of a relevant event. Applications in turn need to take advantage of such mechanisms, so the design of the whole software stack has an impact on power consumption.

You can get some information about what's responsible for your PC's power consumption with Intel's Powertop utility. Smartphones typically have a way to see how much power applications have been consuming as well. Accounting for power consumption by application precisely is difficult: if a component wakes up for two applications, the wake-up time may be accounted to one of them somewhat arbitrarily or to neither; peripherals' power consumption are also not always be easily tracked to the application responsible.

A RAM chip doesn't know which of its bits store data of an active process, so it can't be turned off selectively in this manner. A process's power consumption isn't related to the amount of memory that it uses (except inasmuch as the RAM accesses consume power, but re-using the same memory or using different RAM areas makes no difference with respect to power consumption).


computationally efficient linear index to index pair mapping

For a given $m \in Q$, we need to find the biggest $n \in R$, such that $\frac{n(n+1)}{2} \leq m$. Hence, the first element will be $n$ and the second elemnet is $\lfloor m - \frac{n(n+1)}{2} \rfloor$. Now, the question is how can we compute $n$ efficiently? Fortunately, it can be computed by testing some constant numbers and the specified pair will be $(n, \lfloor m - \frac{n(n+1)}{2} \rfloor)$ for a given number $m \in Q$.


Transform 2D range query matrix into segment tree to make memory usage lower

You could use a quadtree or kD-Tree. They are multidimensional indexes (your case only needs 2D) that perform insertion, deletion and window queries (rectangle defined by two coordinates) in $O(log (n))$.

In your case you would simply insert all coordinates/cells with '1' into the quadtree/kd-tree. Then you can perform a window query that returns all '1' in a given rectangle. For example, to define a '1' at $(3,7)$:

KDTree<Boolean> tree = new KDTree<>(2); //2 dimensions
tree.put(3, 7, 1); //You could ommit the '1', since all entries will have a '1'.

To perform a query between $(1,1)$ and $( 4,6)$:

Iterator<Entry> iter = tree.query(1,1,4,7);

The iterator contains a sequence of Entries, where each entry has coordinates and a value, such as '1'. The example should return exactly one Entry for $(3,7)$. The syntax will differ between implementations, but they should all be similar.

Be aware that this is only useful if $N$ is large and $P$ is small, because there is some storage overhead.

There are example implementations all over the web, also referenced from the Wikipedia pages. I also have my own Java implementations here, however, they are implemented to work with any dimensionality and take any Object as values so they are a bit overkill if you just use 2D and only store boolean 1/0.


Run Length Encoding Compression With Nested Level

Yes.  The Sequitur algorithm could be viewed as doing more or less what you've asked for.

For instance, Sequitur would encode abababcabababc to the grammar

S → WW
T → ab
U → TT
V → UT
W → Vc

You can think of this as having your form. V is basically an encoding of 3(ab).  W is basically an encoding of 3(ab)c.  WW is basically an encoding of 2(W).  So, the final grammar is equivalent to 2(3(ab)c) -- it is just a different way to write it.  Sequitur writes the output as a context-free grammar, instead of using your notation, but its grammar is equivalent to the answer you were hoping for.

Here is the sequence of steps that Sequitur would use to reach that result.

First, we have the grammar

S → abababcabababc

The first digram encountered is ab, so it replaces that with a non-terminal:

S → TTTTcTTTc
T → ab

Then this becomes

S → UTcUTc
T → ab
U → TT

and then to

S → VcVc
T → ab
U → TT
V → UT

and then to

S → WW
T → ab
U → TT
V → UT
W → Vc


does a DFA converted from NFA always contain 2^Q states?

The answer to the question depends on its precise meaning.

  when converting an NFA to DFA, we create sub-sets of states in the NFA. does it mean that every DFA-converted-from-NFA contain 2^Q states?

Yes, when applying the standard construction for DFA constrution the new automaton obtains a state set $2^Q$, the power set of $Q$, containing all subsets of original state set $Q$. This construction will always yield a deterministic automaton of that size even when the original automaton is deterministic.

  or if some sub-sets are unreachable then they are not included in it?

That touches on the difference between the "formal" construction and the more "practical implementation" that is usually taken. In the latter version we only take the states that are reached during construction. Technically, we just determine the connected component that includes the initial state (where we start the construction).

In the figure we see a NFA (with three states) and the DFA using the standard subset construction with eight states (formal interpretation) or four states (omitting the gray states not reached). (PS. I forgot to mark the final states in the gray part)


The fastest algorithm for intersection of two sorted lists?

Hwang and Lin's Algorithm (A simple algorithm for merging two disjoint linearly-ordered sets (1972) by F. K. Hwang , S. Lin) is the reference on how to merge (or intersect) ordered lists of unequal sizes with (possibly) fewer comparisons.  It works by calculating a stride from the ratio m/n and doing the comparison against that element in the larger list; for instance if m/n = 4 it will compare the fourth element of the larger list against the first of the other, and either eliminate all 4 elements or do a binary search within them for the correct insertion/intersection point.

It neatly covers the continuum from merging equal-sized lists with the usual algorithm to merging a list of one element into a list of n with a single binary search.


Standard construction of a (co-c.e.) immune set

Let us follow the standard construction by Emile Post from his famous 1944 paper (see section 5) introducing reducibilities in computability theory.

The standard example of an immune set is as follows. Consider the set
$$P = \{\langle m, n\rangle \mid n > 2 m \land n \in W_m \},$$
where $\langle {-}, {-}\rangle : \mathbb{N} \times \mathbb{N} \to \mathbb{N}$ is an acceptable pairing function. There is a computable selection function $f$ for $P$, i.e., a partial function $f$ such that: for every $m \in \mathbb{N}$, if there is $n \in \mathbb{N}$ such that $\langle m, n \rangle \in P$ then $f(m)$ is defined and $\langle m, f (m) \rangle \in P$. (Why does such an $f$ exist? Exercise!)

Observe that $f$ is defined at infinitely many values. Indeed, there are infinitely many $m \in \mathbb{N}$ such that $W_m$ is infinite, and at least at all of those $f(m)$ is defined.

Now let $S$ be the image of $f$, i.e.,
$$S = \{n \mid \exists m \in \mathbb{N} . f(m) = n\}.$$
We claim that the complement $I = \mathbb{N} \setminus S$ is immune:

Because $f(m) > 2 m$ for every $m$ at which $f$ is defined, the set $I$ is infinite. Indeed, among the numbers $0, 1, \ldots, k$, at most $k/2$ can be enumerated by $f$, so at least all the rest will be in $I$.
Suppose we had an infinite c.e. set $U \subseteq I$. There is $m$ such that $U = W_m$. Because $U$ is infinite, $f(m)$ is defined, hence $f(m) \in W_m = U \subseteq I$. On the other hand, by the definition of $I$ we also have $f(m) \in S \not\in I$, a contradiction. Therefore $U$ cannot be infinite.

The intuition behind the construction

Here is an informal explanation of $I$. The set $I$ has to satisfy two opposing conditions:

$I$ must be large enough (infinite).
$I$ must not be too large (for every infinite $W_m$, it has to avoid an element of $W_m$).

If we only cared about the first condition, we would take $I = \mathbb{N}$. If we only cared about the second condition, we would take $I = \emptyset$. But the two conditions work against each other.

Our first atempt could be this: for each infinite c.e. set $W_m$, pick an element $f(m) \in W_m$, let $S = \{f(m) \mid \text{$W_m$ is infinite}\}$ and let $I = \mathbb{N} \setminus S$. Then we satisfied the second condition, since $f$ enumerated one element of each infinite $W_m$, and we avoided all of those. However, there is no guarantee that $I$ is large enough – what if $S = \mathbb{N}$?. We can do better by making sure that

$f$ is computable so that $I$ will end up being co-c.e.
force $f$ to pick ever larger elements, so that we can be sure that it skips lots of numbers, which then end up being in $I$.

We achieve both of these with our constuction.

Let me finish with an interesting observation. In the effective topos, an immune set is an example of a subset of $\mathbb{N}$ which is neiter finite nor infinite.


Stable matching problem is greedy or Dynamic?

If you consider the Gale–Shapley algorithm, it takes a greedy approach.

By the definition of Wikipedia:

  A greedy algorithm is an algorithmic paradigm that follows the problem
  solving heuristic of making the locally optimal choice at each stage
  with the hope of finding a global optimum.

The Gale-Shapley Algorithm does exactly that. At each step, the 'proposers' take a greedy decision of selecting the best partner (locally optimal choice) that was not yet proposed.


Is a function looking for subsequences of digits of $\pi$ computable?

Note that $f$ can be the constant $1$ even if $\pi$ is not a normal number. (In French we say if $f$ is constant that $\pi$ is a nombre univers. I don't know the corresponding term in English)

For what it's worth: it could be, in the following way:

Proving $f$ is computable would not necessarily imply the resolution of the open question whether $f$ is constant or not. For example you can build $g$ that is computable but such that the constantness of $g$ is equivalent to Goldbach's conjecture.

Of course that does not even begin to answer your question, but it's likely open to me.


Is $\{ 0^p1^q0^r \mid p \neq r \}$ context-free?

The mistake in your proof is that the pumping lemma says that such a division (w=uvxyz) exists.
So in order to say $L_2$ is not context free, you have to show that for every division, you get a contradiction.

In your example we can use this division:
$u=01, \, v=00, \, x=\epsilon, \, y=\epsilon , z=\epsilon$
So for every $n \geq 0$:
$uv^nxy^nz=01(00)^n \in L_2$


This is plainly wrong. The set of all Java programs that always terminate is not recursively enumerable (essentially the halting problem), and so can't be generated by any grammar.

Ambiguous context free grammars are hard to parse efficiently, compiler writers prefer unambiguous grammars (or use tricks in the parser to bypass ambiguities). If the underlying grammar is ambiguous, chances are that the attributed grammar won't give a unique meaning either.

A context free grammar is called ambiguous if there is a string generated by the grammar with two different derivation trees. Context sensitive grammars don't have any similar description of the derivation that is independent of the order of productions applied, so ambiguity doesn't make sense for them.


In cache-oblivious algorithms, how is recursive reduction of data performed?

From the paper entitled "Cache-Oblivious Mesh Layouts" (Yoon et al):

The cache miss ratio function (CMRF), pl, is a function that relates
the cache miss ratio to an edge span, l. The CMRF always lies within
the interval [0;1]; it is exactly 0 when there are no cache misses,
and equals 1 when every access results in a cache miss. We alter the
layouts using a local permutation that reorders a small subset of the
vertices. The local permutation changes the edge span of edges that
are incident to the affected vertices (see Fig. 3).

The data granularity is repeatedly reduced in software until the "atoms" are small enough to fit cache. The lower bound on data structure granularity is reached as soon as the cache miss ratio reaches zero: beyond this point, further reduction becomes unnecessary. For any given target environment, at runtime, we proceed to reduce the size of data set atoms until they are small enough that the miss ratio reaches zero.
This (often recursive) reduction / linearisation is explored in the MIT OCW lessons on Cache Oblivious algorithms (this lesson and the following one).
Perhaps other approaches exist(?), but it makes sense to me that an algorithm oblivious to block size B would use this sort of approach, in general.


Error-correction code for transmission only with bit-flipping from 0 to 1

This is not possible.  There's no free lunch. You are looking for a compression scheme that is guaranteed to compress 32 bits down to less than 32 bits.  That's not possible in general, unless you have prior knowledge that lets you rule out some of the possible 32-bit values.

In particular, if you want to send 32 bits of information, and all $2^{32}$ possibilities are equally likely, and errors are not allowed, you'll have to send at least 32 bits over the communication channel.  This is a basic theorem of information theory.  No amount of error-correcting codes will get you past this.

If you want to avoid this, you'll either need prior knowledge on the 32-bit value (e.g., to rule out some as impossible, or less likely than others), or you'll need to accept lossy compression (where the recipient's received string might not exactly match what the sender wanted to send).


Why was primality test thought to be NP?

To start, any decision problem with a witness verifiable for a "yes" answer in polynomial time is in NP.

$\bullet$ The problem 'Is $p$ composite?' has a witness $k$, and it can be tested in polynomial time whether $k$ divides $p$, therefore is in NP.

$\bullet$ The problem 'Is $p$ prime?' has a polynomial certificate (which can be found here), therefore is also in NP.

Now, your complexity analysis is not correct. If your input is a number $p$, then the input size is $\log (p)$, since you need $log(p)$ bits to represent it. Therefore, $n=\log(p)$ and $\sqrt{p}=\frac{1}{2} \log(p)$ bits. So the time required (in respect to $n$) checking all the numbers up to $\sqrt{p}$ will be $2^{\frac{1}{2}n}$, and is in fact exponential in terms of input size $n$.

The question "Where exactly does the Primality problem lie" has been answered in the link here


According to Goldberg's post on the Fortnow–Gasarch blog from 2012, the best algorithm for unit capacity networks is the Karzaon/Dinic/Even–Tarjan algorithm, which runs in time $O(\min(n^{2/3},m^{1/2})m)$ time. The post came after Orlin's $O(nm)$ algorithm. Goldberg and Rao extended this result to any constant capacity (their running time is linear in the logarithm of the maximal capacity).

There is a more recent line of work which gives an approximation to the maximum flow in time $O(m^{1+o(1)})$, but this doesn't make use of any bound on the capacities.


Regular languages closed under quotients with arbitrary languages

The (right) quotient of $R$ by $B$ is the language
$$
  RB^{-1} = \{x \in A^* \mid \exists y \in B,\ xy \in R\}
$$
and indeed, if $(Q, A, \cdot, q_0, F)$ is the minimal DFA of $R$, then $RB^{-1}$ is accepted by the automaton $(Q, A, \cdot, q_0, S)$, where
$$
S = \{q \in Q \mid \exists y \in B\ \ q \cdot y  \in F\}.
$$
On the other hand, let $R/B =  \{x \in A^* \mid \forall y \in B\ \ xy \in R\}$. Then one gets
$$
  R/B = \bigcap_{y \in B} \{ x \in A^* \mid xy \in R \} = \bigcap_{y \in B} Ry^{-1}
$$
Since $R$ is regular, there are only finitely many distinct languages of the form $Ry^{-1}$, and each of it is regular. It follows that $R/B$ is also regular.

This gives a proof that the languages $RB^{-1}$ and $R/B$ are regular for any $B$. However, if you want to find effectively an automaton accepting these languages, this is a different story and you may need to identify which of the right quotients  $Ru^{-1}$ are of the form $Ry^{-1}$ with $y \in B$, a question that might be undecidable, depending on $B$ and $R$...


Can I encode a graph in a unary alphabet

As you mention in your question, everything that can be coded in binary (that is, every countable set) can also be encoded in unary. Arrange all binary strings in some order, say
$$ \epsilon, 0, 1, 00, 01, 10, 11, \ldots. $$
Let $w_i$ be the $i$th string in this order. You can convert from binary to unary by mapping $w_i$ to $1^i$ and vice versa.

You mention that you are worried that this encoding is not efficient. From the perspective of complexity theory, this is not so clear, since if your representation is very large, then it is fair to allow you a lot of time to encode and decode it. In formal terms, for a representation of length $n$, you should be able to encode and decode in time polynomial in $n$.

Consider the example of graphs. In order to encode a graph in unary, you first encode it in binary, say using $m$ bits. Then you output $1^n$ for some $n \approx 2^m$. You can easily compute the output in time polynomial in $n$. Going the other way around, you can convert $1^n$ to the corresponding binary string $w_n$ in time polynomial in $n$ as well, and decoding the binary representation only takes time polynomial in $m = O(\log n)$.


CCS process for a drink dispenser with two different prices

You can easily profit from warfare that way:

$$ M \stackrel{\mathrm{def}} =
  c.(
    d_{\text{tea}}.\bar e_{\text{tea}}.M
    + r.\bar b.M
    + c.(
      d_{\text{coffee}}.\bar e_{\text{coffee}}.M
      + r.\bar b.\bar b.M
    )
  )
$$

note that you have to press refund to get a tea if you put too many coins. If you don't want that, you can adapt it (or maybe set up a (finite is enough) counter) :

$$ M \stackrel{\mathrm{def}} =
  c.(
    d_{\text{tea}}.\bar e_{\text{tea}}.M
    + r.\bar b.M
    + c.(
      d_{\text{coffee}}.\bar e_{\text{coffee}}.M
      + d_{\text{tea}}.\bar b.\bar e_{\text{tea}}.M
      + r.\bar b.\bar b.M
    )
  )
$$


Is the set of pairs of TMs at least one of which accepts the empty word semi-deciable?

Rice's second theorem can be used to show for some sets that they are not semi-decidable, but not the opposite.

In order to show that this set is semi-deciable, just follow the definition and construct a semi-decider.

   Idea: Simulate both $M_1$ and $M_2$ on $\varepsilon$ simultaneaously using dovetailing. If either one halts and accepts, stop simulating and accept.


Imagine a system S1->S2->S3(final).

DFA transition rules are (S1,a,S2) and (S2,b,S3).
Moore machine rules are (S1,(a,1),S2) and (S2,(b,2),S3).

For the input 'ab',

DFA will output 'ab'->TRUE
Moore machine will output 'a'->1, 'b'->2.

As you can see, DFA doesn't output at each stage. Independent of the input length, you have one output. However, for the Moore machine, size(input)=size(output). Since the input-output relations differ, you cannot conclude that a DFA is a Moore machine.


What is the depth of a complete binary tree with $N$ nodes?

Consider how a complete binary tree of height $h$ is constructed, one vertex at the root level, two at the first level below the root, four at the second level below, and so on, until  the $h^{th}$ level, which has at least one vertex, but at most twice as many as the previous level. Note that the number of vertices at each level is a power of two (excluding the last, which is a special case). Then we have:
$$
1+\sum_{i=0}^{h-1}2^{i} \leq n \leq \sum_{i=0}^{h}2^{i}
$$
Using the identity that the sum of the first $k$ powers of two is $2^{k+1}-1$ we get:
$$
1+2^{h}-1 \leq n \leq 2^{h+1}-1\\
2^{h} \leq n \leq 2^{h+1}-1
$$
and hence
$$
2^{h} \leq n < 2^{h+1}
$$

Taking the base 2 logarithm:
$$
h \leq \log n < h+1
$$
So we can conclude
$$h = \lfloor\log n\rfloor$$
As $\log n$ is bigger than $h$, but less than the next integer $h+1$.


Does it make sense to talk about the complexity of non-computable functions (such as the Halting problem)?

Computational complexity studies the computational resources required to decide problems in some particular model of computation. Because of this, it makes no sense to talk about the complexity of a problem that is not computable in the model of computation you're talking about.  Or, to put it the other way around, it only makes sense to talk about the computational complexity of the halting problem with respect to models of computation in which that problem is computable.  For example, you could talk about the complexity of recursively enumerable problems using Turing machines with an oracle for the halting problem as your model of computation.

The proof you link to does not show that the halting problem is in NP. It shows that the halting problem is NP-hard, which just means that every problem in NP is polynomial-time reducible to the halting problem.


Process graphs and finding infinite processes

As you propably know, a process (in terms of process algebra like CSP) can consume an input and will the behave like another process (unless it is a process that does not accept input, usually called STOP).

You can construct a graph where the nodes are the processes and the outgoing edges the input that the node can consume, directed to the node (process) that gives the new behaivior. If such a graph contains a directed path back to a starting node (i.e., a circle), you have an infinite process.

Finding a circle in a graph is a standard problem in graph theory and is usually done by DFS.

A good introduction to CSP is Tony Hoare's Book on that subject, what is easy to read also for beginners. (However, Hoare does not use the term "process graph" but talks only on "graphs".) The standard text book for CCS is Milner's "Communication and Concurrency" published by Prentice Hall.


The following grammar is unambiguous yet generates a non-regular language:
$$ S \to aSb \mid \epsilon $$


A possible technique to generate random tilings is:

Represent all possible solutions as a Zero Suppressed BDD (see for example The Art of Computer Programming volume 4, chapter 7.1.4, or this page). Every way to place any piece on the board corresponds to a variable in the ZDD. The constraints are that every tile is covered exactly once, which can be done by making an "exactly once"-ZDD for every tile, and then intersecting all those ZDDs. An "exactly once"-ZDD is easy to make, it's a single chain of nodes where a constrained variable (a piece-placement that covers this tile) corresponds to a node with a HI branch to TOP and a LO branch to the next node, and an unconstrained variable has both LO and HI going to the next node.
For each node in the ZDD, count how many solutions it leads to. Runs in time proportional to the size of the ZDD (not the number of solutions) if memoization is used.
Then, top down, randomly choose between the two children of a node using the ratio of solution counts as threshold. That would uniformly choose a random solution from the space of solutions. Runs in time proportional to the number of variables (depth of the ZDD).


Karp hardness of searching for a matching cut

You can reduce the problem without cardinality constraint to the problem with cardinality constraint.

For an instance $G=(V,E)$ of the problem without cardinality constraint, simply add $m>|V|/2$ isolated edges as well as $2m$ new vertices. Now there is a matching cut in the old graph if and only if there is a matching cut of size $m+1$ in the new graph.

Edit: One can also add an edge $(u,v)$ for each newly added edge $(u,x)$ and a fixed vertex $v$ in the previous graph to make $G$ connected. The conclusion is the same.


Amortized analysis of resizing array implementation of a stack

They include the initialization of the new array.
From page 207 of the text:

Q. Does int[] a = new int[N] count as N array accesses (to initialize entries to 0)?
A. Most likely yes, so we make that assumption in this book, though a sophisticated compiler implementation might try to avoid this cost for huge sparse arrays.


Median of medians: bound on pivot position

You missed the recursive step of this recursive algorithm.

For the sake of discussion, assume you want to find the 99th smallest element of the initial 125 elements. Here 99 is just an arbitrary number between 1 and 125.

After you have got the first batch of medians below,
$$[3\,\,3\,\,3\,\,\infty\,\,\infty,\,\,6\,\,6\,\,6\,\,\infty\,\,\infty,\,\,9\,\,9\,\,9\,\,\infty\,\,\infty,\,\,12\,\,12\,\,12\,\,\infty\,\,\infty,\,\,15\,\,15\,\,15\,\,\infty\,\,\infty]$$
you are supposed to apply the same algorithm to find its median, $m_1$, its actual real median instead of an approximate median.

When you get the second batch of medians, $$\begin{bmatrix}3&6&9&12&15\end{bmatrix}$$
you are supposed to apply the same algorithm to find its median, $m_2$. In fact, we have reached the base case of the recursion. So we just use some simple routine to get its median, $m_2=9$.

Using 9 as the pivot, we will find in the second batch of medians, two elements that are smaller than 9, 3 and 6. Going back to the first batch of medians, we will then skip three 3's and three 6's and two 9's, 3+3+2=8 elements in total. That is where the 30% comes from: $8 \ge 25 * 30\%$. We also find $12\gt9$ and $15\gt9$. Going back to the first batch of medians again, we will skip $[\infty,\infty]$, $[12,\infty,\infty]$ and $[15,\infty,\infty]$, another 8 element in total. That is where the 70% comes from. Now it is time to run the same algorithm again to find the median $m_1$ as the median of the remaining $25-8-8=9$  elements,
$$[\infty\,\,\infty\,\,\infty\,\,\infty\,\,9\,\,12\,\,12\,\,15\,\,15]$$

$\cdots, \cdots, \cdots$ (rounds of recursions omitted)

Finally, we find that $m_1=15$ (the first 15). Using 15 as the pivot, we will find in the first batch of medians, $3<15$, $6<15$, $9<15$ and $12 < 15$. Going back to the initial 125 elements, we will skip three [1,2,3], three [4,5,6], three [7,8,9], three [10,11,12] and one [15, 15], 3*3*4+2=38 elements in total. That is again where the 30% comes from: $38 \ge 125 * 30\%$.  We will apply the same algorithm to find the ultimately wanted element as the $99-38=61$-th smallest element of the remaining $125-38=87$ elements. Why can we skip those 38 elements? Because each of one of them is not greater than $m_1$, which is no greater than the 38 elements on the big side. Together with the fact $38 + 99 \ge 125$, we know the 99-th smallest element must be one of the remaining elements.

Hopefully, I have given enough explanation to show where you have gone wrong. Hopefully, you will appreciate the ingenuity and subtlety of this algorithm of median of medians more.

For more analysis, you may want to check the beautiful visualization page of the algorithm. You may want to read wikipedia. You can also read CLRS, edition 4, section 9.3, "Selection in worst-case linear time" and its accompanying exercises, whose analysis on the pivot and the recurrence relation is more rigorous and comprehensive.


Here is the definition of cross-entropy for Bernoulli random variables $\operatorname{Ber}(p),\operatorname{Ber}(q)$, taken from Wikipedia:
$$
H(p,q) = p \log \frac{1}{q} + (1-p) \log \frac{1}{1-q}.
$$
This is exactly what your first function computes.
The partial derivative of this function with respect to $p$ is
$$
\frac{\partial H(p,q)}{\partial p} = \log \frac{1}{q} - \log \frac{1}{1-q} = \log \frac{1-q}{q}.
$$
The partial derivative of this function with respect to $q$ is
$$
\frac{\partial H(p,q)}{\partial q} = -\frac{p}{q} + \frac{1-p}{1-q} = \frac{(1-p)q-p(1-q)}{q(1-q)} = \frac{q-p}{q(1-q)}.
$$
This is exactly what your third function computes.
I'm not sure what your second function computes. Also, there is no reason to expect that the partial derivative with respect to one variable will be the same as the partial derivative with respect to another variable.


A Turing Machine that Doesn't Move to the left

If you only allow moving right (and no external memory), all your TM "knows" about the input already seen is the finite amount of information in its state. I.e., it can't do more than a finite state automaton.


DP Knapsack Problem With Categorical Constraint

An alternative approach you could try: solve a knapsack problem for each category separately, then combine those solutions.

You'll probably find it more rewarding to work out how to do that on your own, but if you want a more detailed hint:

   For each category and each total weight $w$ and each integer $t$, compute the maximum enjoyment you can have by using at most $t$ books from that category and where the total weight is at most $w$.

 For instance, for each $w,t$, you'll compute the maximum enjoyment you can have by selecting at most $t$ fantasy books (and no science fiction or classic books) of weight at most $w$.  Then do the same for science fiction, and the same for classic books.

 Then, combine these three results.  I'll let you work out how to combine them.


Which algorithm to detect errors in 32bit data with 8bit parity

Think of your message as seven 5-bit numbers $x_2,\ldots,x_8 \in \{0,\ldots,30\}$. This gives you $7\log_2 31 \approx 34.68$ message bits. Calculate $x_1 = -\sum_{i=2}^8 ix_i \bmod{31}$, so that
$$
\sum_{i=1}^8 ix_i \equiv 0 \pmod{31}.
$$

It is easy to check that every single symbol error is detected, since $31$ is prime.

Now suppose that $x_i$ and $x_j$ are switched, but the equation above still holds. Then $ix_i + jx_j \equiv ix_j + jx_i$, and so $(i-j)(x_i - x_j) \equiv 0$, implying that either $i = j$ or $x_i = x_j$.


Something I don't understand about Genetic Algorithms

Generally speaking, evolutionary algorithms stop well short of trying to model real biology, and this is one example of something that occurs in nature but not in commonly used evolutionary algorithms.

Instead, we tend to use a system where all individuals have only one value for each gene, and they're all "active". Replication, mutation, and recombination are considered to be atomic operations with no concern given to any intermediate stages. Consider the simplest case of a binary encoding. You might have two parents, A and B, as

A = 0101101001
B = 1001010010

To do crossover, we simply create an offspring by choosing exactly one parent for each bit in the offspring to copy from. We can formalize this a bit with something called a mask -- a bit string where a 1 indicates that we choose the value from A and a 0 indicates we choose from B. Thus, one point crossover might have a mask like

M = 0000001111

with our parents A and B, we would then get a child C as

A = 0101101001
          ^^^^
B = 1001010010
    ^^^^^^
C = 1001011001

So here, the offspring C has gotten copies of the first six genes of parent B and the last four of parent A, but at no point do we consider the process by which chromosomes would be copied in a biological system. We simply allocated a new variable and did a memory copy to instantaneously duplicate parts of the parents.

If we want to mutate the offspring, we might simply pick a bit at random and flip it. Again, we don't worry about biology here and how mutations actually occur in nature. We just define mutation to be the flipping of a single bit in memory and do it.

One point crossover is about the simplest thing you could do, but essentially all commonly used methods look similar in that the child gets a single value for each position and no explicit notion of binding or connection to the parents is considered. We don't really think of crossover in terms of chromatids -- we just directly copy allele values using some well-defined (but probably not biologically plausible) crossover operator. So there's never any question of which allele values are active -- they all are.


Prove Undecidability: TM M enters each of its states on Input W?

Hint. We can assume that a Turing machine has exactly one halting state. If a TM visits all of its states, it certainly visits the halting state. Now figure out a way to modify Turing machines so that, if they do halt, they cycle through all their states just before doing so. This gives you a class of TMs that visit every state if and only if they halt.


The alternative definition that you attribute to your professor is wrong, as your counterexample clearly shows.

I hope your professor actually said something else and you misunderstood him/her!


Can this system of polynomial equations be solved in polynomial time?

Let us denote the unknowns by $x_1,\ldots,x_n$, and the coefficients by $c_1,\ldots,c_n$. For a polynomial $P(x)$, we denote
$$
[P(x)] = \sum_{i=1}^n c_i P(x_i).
$$
We are given the values of $[1],[x],\ldots,[x^n]$, from which we can calculate $[P(x)]$ for every polynomial of degree at most $n$. In particular, we can compute, for each $j \in \{1,\ldots,n\}$, the value
$$
\left[ \prod_{k \neq j} \frac{x-k}{j-k} \right] = \sum_{i\colon x_i=j} c_i.
$$
To complete the solution, we need to solve several SUBSET-SUM instances, which possibly interact.

Conversely, we can encode SUBSET-SUM using your equations. Given a set of positive coefficients $c_1,\ldots,c_n$ summing to $C$ and a target $S$, we encode a solution using $\{1,2\}$-valued variables (where $1$ represents a value in the subset summing to $S$), and can compute $[x^k] = S + (C-S)2^k$. These numbers satisfy
$$
[x^k(x-1)(x-2)] = [x^{k+2}-3x^{k+1}+2x^k] = \\
(S + (C-S)2^{k+2}) - 3(S+(C-S)2^{k+1}) + 2(S+(C-S)2^k) = \\
(1-3+2)S + (4-6+2)(C-S)2^k = 0.
$$
Therefore the argument above shows that every $\{1,\ldots,n\}$-valued solution is actually $\{1,2\}$-valued. Therefore a solution to your problem exists if and only if the SUBSET-SUM instance is a Yes instance.

When all coefficients $c_i$ are equal, the argument above allows us to calculate directly the number of $x_i$'s equal to $j$. Let us take your example: $[1] = 3$, $[x] = 6$ and $[x^2] = 14$. Denoting by $y_j$ the number of $x_i$'s equal to $j$, we compute
$$
\begin{align*}
y_1 &= \left[ \frac{(x-2)(x-3)}{(1-2)(1-3)} \right] = \frac{[x^2-5x+6]}{2} = \frac{14-5\cdot6+6\cdot3}{2} = 1, \\
y_2 &= \left[ \frac{(x-1)(x-3)}{(2-1)(2-3)} \right] = [-x^2+4x-3] =
-14+4\cdot6-3\cdot3 = 1, \\
y_3 &= \left[ \frac{(x-1)(x-2)}{(3-1)(3-2)} \right] = \frac{[x^2-3x+2]}{2} =
\frac{14-3\cdot6+2\cdot3}{2} = 1.
\end{align*}
$$


What set of primitive operations are assumed to be constant time in complexity analyses?

It depends on the "model of computation".  The model of computation specifies things like what can be done in a single step and what operations are available.  There are different models of computation, each of which can sometimes lead to a slightly different running time.

If the model of computation makes an important difference and the paper is being careful, it will usually mention which model of computation it is working in.  Sometimes we don't care about the difference (or the difference is negligible) and then the model of computation might not be mentioned.

So, your model of computation could specify that pointers and integers (large enough to hold numbers in the range $[0,N]$) fit in a single word and can be accessed in $O(1)$ time.  Or, it might specify that this takes $O(\log N)$ time and space.  A circuit-centric model of computation might count the number of gates in a circuit needed to do the computation.  There are many others.

One example of a model of computation is the RAM model.


How to use a logistic regression classifier to estimate the confidence of a rule?

From context, I'd guess that the logistic regression classifier is used to predict the probability that a particular word is a LAT.  This looks equivalent to predicting the probability that the fired rule was correct to flag that word as a LAT.  This seems to make sense given the context.


What if p and q are not distinct in RSA Crypto System? What could go wrong?

The security of RSA relies on the fact that the best known way to compute $\phi(n)$ is to prime factorize $n$. For $n=pq$, where $p$ and $q$ are large, distinct primes, this is very hard. If instead $n=p^2$, then one could quickly find $p$ by calculating a square root. Then one could calculate $\phi(p^2)=p^2-p$ and break the encryption completely.


The error in your argument is the claim

  Nothing is known a priori about the function $f$, (...) so it is necessary to plug in all $2^n$ values.

, which is simply false. I will demonstrate why it isn't necessary to plug in all possible values and sketch how to arrive at an $O^*((2^k-1)^{n/k})$  time algorithm, where $k$ is the number of clauses. $O^*$ 'hides' poly-logarithmic factors, so for fixed $k$, this would be an $o(2^n)$ algorithm.

A key idea is this: If we wish to satisfy some clause of $m$ literals $l_1 \vee l_2 \vee \dots\vee l_m$ by assigning truth-values, then there are $2^m-1$ ways to do this, as exactly one of the assignments does not satisfy the formula. This means we in fact do not have to test every assignment (for this clause).

Not doing a single test seems like a trivial improvement. However, by recursively applying the procedure to only check at most $2^k-1$ assignments, we get a running time $T(n)$ for which we have $T(n)= (2^{m_i}-1)\cdot T(n-m_i) + O^*(n)$, where $m_i$ is the number of elements of the $i$-th clause. So, $T(n) = (\Pi_{i=1}^l (2^{m_i}-1))T(0)+l\cdot O^*(n)$, where $l$ is the number of clauses. This gives the result $T(n)=O^*((2^k-1)^{n/k})$.

Of course, our improvement still yields a rather unpractical algorithm, but there are other tricks you can apply. To learn more, these slides by William Gasarch are a good read. (The title states 3-SAT, but most methods can be generalised to $k$-SAT)


Is the following langauge in $P$ or $NPC$

Hint: Take a valuation $v$ satisfying less than half of the clauses. What about $\bar{v}$ the valuation such that $\bar{v}(x)=\neg v(x)$?


Efficient algorithm to fulfil a set of coordinate constraints

The simplest approach (in terms of programming effort) might be to try using an existing graph layout tool.  Those solve a related problem: given a graph with distances on the edges, try to find the best layout to draw the graph on the plane.  You can treat your problem as an instance of the graph layout problem: we have one vertex per point, and for each pair of points $v,w$ with distance bounds $[\ell,u]$, we create an edge $v \to w$ with length $(\ell+u)/2$.  However, this does have some limitations: typical graph layout algorithms try to get the distances between vertices correct, but also try to avoid edges that cross each other; whereas in your case you don't care about crossings.  So, your problem might be easier.

Another possibility is to apply the ideas used for graph layout to your problem.  There are several algorithmic techniques for graph layout.  For instance, you could use a spring-based model, where you have a spring between each pair of vertices that have a distance bound, and the spring tries to keep those pair of vertices a suitable distance apart.

A third approach is to use black-box mathematical optimization.  Introduce an objective function $\Phi$ which, given a set of locations for the points, calculates a penalty value (how "badly" the arrangement violates your constraints), and then try to find an arrangement that minimizes $\Phi$.

For instance, suppose for each pair $v,w$ of points, you have a lower bound $\ell_{v,w}$ and an upper bound $u_{v,w}$.  You could define

$$\Phi(x_1,\dots,x_n) = \sum_{i,j} \frac{[||x_i - x_j||_2 - (u_{i,j} + \ell_{i,j})/2]^2}{(u_{i,j} - \ell_{i,j})^2},$$

and then use some optimization technique to find an arrangement $x_1,\dots,x_n$ that minimizes $\Phi(x_1,\dots,x_n)$.  For instance, you could try using hillclimbing, gradient descent, or other convex optimization methods.  This approach might be sensitive to the initial values for $x_1,\dots,x_n$, so you might want to repeat it multiple times with different random choices for the initial value, and take the best result.

Finally, you could try using simulated annealing.

The latter two approaches can be easily adjusted to incorporate angle constraints, simply by modifying the objective function appropriately to add a term that penalizes angles that differ from the desired value.


Order of growth definition from Reynolds & Tymann

The paragraph is wrong. Unfortunately, it looks exactly like the kind of thing that a student who does not understand the material would write as an answer to an exercise. This sort of nonsense has no place in a textbook. Make no sudden movements. Put the book down. Step away from the book.

  We say that the "order of growth" of the sequential search algorithm is n. The notation for this is $T(n)$.

No. $T(n)$ is the notation for a function called $T$, which takes an argument called $n$. That function could be used to mean anything whatsoever. There is something of a tradition of writing recurrence relations for the running time of programs in the form, e.g.,
$$\begin{align*}
T(1)&=k\\
T(n)&=T(n-1)+\log n \quad\text{for }n>1
\end{align*}$$
But $T$ is not an "order of growth", here: it is a specific function defined through a recurrence relation. And you cannot just write "$T(n)=\text{blah}$" and expect people to read your mind and know that the function $T$ denotes the running time of some algorithm.  $T$ here stands for time.

  We also say that an algorithm whose order of growth is within some constant factor of $T(n)$ has a theta of NL say. "The sequential search has a theta of $n$."

This has obviously been mangled. I think the authors intended to write something like,

  We also say that an algorithm whose order of growth is within some constant factor of $T(n)$ has a theta of $\boldsymbol{n}$ and we say, "The sequential search has a theta of $n$."

But, please, we do not say "has a theta of $n$," just as, if $h$ is your notation for height, you wouldn't say "John has an $h$ of 180cm." It's just not a correct form of words. We actually say, "The running time of the algorithm is theta $n$ (or theta of $n$)." Note in particular, that $\Theta$ is a tool for talking about mathematical functions, not algorithms. Theta doesn't mean that the running time is something; rather, it's something you can use to talk about the running time.

"NL", by the way, denotes the complexity class nondeterministic logspace, which makes no sense at all in the position it appeared in the original quote.


How do contemporary processors differ from a pure von Neumann architecture?

Well I think I may have answered my own question, the specification just wanted to know how it differs from the pure von Neumann architecture. It differs as contemporary processors use a mixture of architectures from Harvard and von Neumann for many reasons (mainly cost) and where speed advantages outweigh the complexity costs.

Contemporary processors use a mixture of both von Neumann and Harvard architecture, which differs from a pure von Neumann architecture by using von Neumann architecture for the main memory to the CPU and Harvard for the control unit and caches.


Is the Shakespeare Programming Language Turing complete?

In that page, the snippet

Juliet:
 Am I better than you?

Hamlet:
 If so, let us proceed to scene III.

essentially means

if (Juliet > Hamlet) goto Scene III

This can be used to implement while loops. In pseudo syntax:

Scene II:
if (Juliet > Hamlet) goto Scene III
... some statements here
goto Scene II
Scene III:
... more statements here

is essentially equivalent to

while (Juliet <= Hamlet) {
   ... some statements here
}
... more statements here


Karger's algorithm: why does every vertex have degree at least the number of edges crossing a min cut?

You pretty much have the answer in front of you.

For any vertex $v$, the cut $\left(\left\{v\right\},V\setminus\left\{v\right\}\right)$ has $\text{deg}(v)$ crossing edges.

If there exists a vertex $v$ with degree $<k$, then its corresponding cut has less than $k$ crossing edges, contradicting the minimality of $(A,B)$.


Hint: Consider the standard multiplication scheme. Suppose that we compute the sum column by column, starting with the LSB. How big is the carry we have to remember?

Comment: Multiplication is actually in NC1 (hard) and even in TC0 (harder).


What fragment of Martin-Löf dependent type theory can be expressed using generic types in Java?

There are a lot of misconceptions here. To begin, MLTT doesn't have subtypes, so Java is not going to simply be a fragment of it. It does not require dependent types to make either of the types you gave. A dependent type system doesn't need to have a "type" of types (a universe) in general  (MLTT does have universes though), nor do you need dependent types to express those types. In a system like the polymorphic lambda calculus/System F, you can say $\forall T.T\times(T\to T\to T)$.  Java doesn't have any equivalent to Type. A dependent type without an analog as a polymorphic type would be something like e.g. $\prod_{n:\mathsf{Nat}}\mathsf{Matrix}(n,n+1)$ or $\prod_{b:\mathsf{Bool}}\mathsf{if}\ b\ \mathsf{then}\ \mathsf{Nat}\ \mathsf{else}\ \mathsf{Bool}$.

It makes more sense to consider Java a fragment of System $\text{F}_{<:}$ which is not a dependent type system at all. Even then it is a rather weak fragment of it. There's a variant of System F called System F$\omega$ which supports full type level functions, essentially lambda at the type level (not to be confused with type-lambdas which relate the value and type levels and System F already has). Neither Java nor Haskell can do this.  The only type level "functions" either (standard) Haskell or Java can make are compositions of uninterpreted functions. There is no computational behavior at the type level. Java is further restricted because it doesn't have (nor need) a kind system because it lacks higher-kinded types.  That is, you can't have a type level "function" with "type" (i.e kind) $(\mathsf{Type}\to\mathsf{Type})\to\mathsf{Type}$ for example. This is why you can't make methods that operate over arbitrary monads in Java. Returning to just System F, System F has arbitrary rank types. This means you can nest $\forall$ as deeply as you like — you can use it freely. Neither Java nor Haskell (without extensions) supports this. I believe both of them can indirectly capture some higher rank types, but neither can express the type of Haskell's $\mathsf{runST}$ which requires extensions and is $\forall a.(\forall s.\mathsf{ST}\ s\ a) \to a$.

So Java is more expressive than the rank-1 types as captured by the Hindley-Milner type system but far less expressive than System $\text{F}_{<:}$. It doesn't support any form of dependent typing. Featherweight Java as introduced in Featherweight Java: A Minimal Core Calculus for Java and GJ by Igarashi, Pierce, and Wadler provides a simplified, idealized calculus specifically geared toward Java.  There is almost certainly a paper that directly compares/reduces Featherweight Java to System $\text{F}_{<:}$. The upshot is Java's type system is not even remotely close to the power of MLTT. In terms of the lambda cube, ignoring subtyping, Java would be somewhere on the edge between $\lambda\!\!\to$, the simply typed lambda calculus, and $\lambda2$, System F. MLTT (or specifically the Calculus of Constructions) is $\lambda\text{P}\omega$, the corner opposite of $\lambda\!\!\to$. So describing Java in terms of MLTT would first require ignoring everything that made MLTT different from System F$\omega$ and then ignoring nearly everything that made System F$\omega$ different from System F.


Trying to understand how the first Hadamard gate in Deutsch–Jozsa algorithm works

After studying the maths behind it, I realized that a linear algebraic expression for a quantum state may not appear to be intuitive at first sight (or prehaps it is only to the not mathematically gifted ones like myself).

Apparently, this is how the expression in the Wikipedia page is derived:

$$\begin{align} &\frac{\left|0...0\right\rangle + \left|0...1\right\rangle + \left|1...1\right\rangle}{\sqrt2 ... \sqrt2} \cdot \frac{1}{\sqrt{2}} (\left|0\right\rangle - \left|1\right\rangle)\\ =&\sum^{n}_{x=0}\frac{1}{\sqrt{2^n}} \left|x\right\rangle \cdot \frac{1}{\sqrt{2}} (\left|0\right\rangle - \left|1\right\rangle) \\=&\sum^{n}_{x=0}\frac{1}{\sqrt{2^{n+1}}} \left|x\right\rangle \cdot (\left|0\right\rangle - \left|1\right\rangle) \\ =&\frac{1}{\sqrt{2^{n+1}}} \sum^{n}_{x=0} \left|x\right\rangle (\left|0\right\rangle - \left|1\right\rangle) \end{align}$$

Now this explains why it is alright to have the four $\frac{1}{\sqrt{2^{3}}}$ probability amplitudes above, which is indeed just the product of $\frac{1}{\sqrt{2^{2}}}$ and $\frac{1}{\sqrt{2}}$.

$\frac{\left|0...0\right\rangle + \left|0...1\right\rangle + \left|1...1\right\rangle}{\sqrt2 ... \sqrt2} \cdot \frac{1}{\sqrt{2}} (\left|0\right\rangle - \left|1\right\rangle)$ sure feels like we are having a superposition state within a superposition state (I'm not sure if that is the correct way to interpret it). And this is probably what makes an entangled system so magical when it comes to computation.


Given a regular grammar $G$, $L(G) = \Sigma^*$ is decidable?

By the "iteration operation" you probably mean the Kleene closure of the language. In the case of the language is $\Sigma^*$ its Kleene closure is clearly equal itself. But you do not provide detailed explanation about how to use this fact to decide whether $L(G) = \Sigma^*$. However, you could solve the problem as following:

Solution 1: Convert the regular grammar into the corresponding DFA and take the complement of the DFA. The complement of a DFA accepting all strings has not accept state. So you can decide by checking whether or not it has an accept state.

Solution 2:  Convert the regular grammar into the corresponding DFA and minimize it. If this DFA accepts $\Sigma^*$ then the minimal DFA has only one state which is the accept-state. So you can decide by checking if the minimal DFA has only one state which is accept-state .


Modifications to speed up the AKS primality proving

There are a number of modifications, but none of the improvements I'm aware of will get it remotely close to the speed of ECPP or APR-CL.  For random 100-digit primes, the times for the fastest codes I'm aware of are:

246 days (estimated)  AKS v6 paper
45 hours (estimated)  AKS Bernstein + Voloch + Bornemann
2.6 hours  AKS Bernstein theorem 4.1
0.042 seconds  APR-CL (WraithX 1.1)
0.04 seconds  APR-CL (Pari/GP 2.7.0)
0.029 seconds  ECPP (ecpp-dj 1.03)
0.20 seconds ECPP (Primo 4.1.0 single thread)

At 500 digits, ECPP and APR-CL are in the 9-15 second range.  AKS would take years, albeit we could trivially parallelize or distribute it.

I haven't seen anything that gives better improvements than Bernstein's 2003 paper while not being a complete rework such as adding randomization.  The growth rate in practice comes out to $O(\log^{6.03} n)$ (there's almost certainly more than 0.03 variance in measurements, but the point is that it's very close to the ideal exponent of 6).  Ricky points out that Lenstra Jr. and Pomerance are still actively publishing theoretical improvements, tightening the proven exponent.

The time taken at more than very small input sizes is almost entirely in the congruence test.  There really should be very little time spent selecting the 'r' and 's' parameters, though it's possible to see it be non-trivial.  For the congruence tests, Bernstein has a paper describing some of the methods that can be used to speed this up, and the implementations shown above use binary segmentation in GMP, as he suggests.  You can see the implementation I used for timing at https://github.com/danaj/Math-Prime-Util-GMP/blob/master/aks.c, with various algorithms available.

There isn't any reason to use AKS in practice at any input size, given open source implementations of more efficient algorithms, not to mention Primo for use on large inputs.  ECPP gives certificates as well, which is a huge advantage.


It's possible to replace recursion by iteration plus unbounded memory.

If you only have iteration (say, while loops) and a finite amount of memory, then all you have is a finite automaton. With a finite amount of memory, the computation has a finite number of possible steps, so it's possible to simulate them all with a finite automaton.

Having unbounded memory changes the deal. This unbounded memory can take many forms which turn out to have equivalent expressive power. For example, a Turing machine keeps it simple: there's a single tape, and the computer can only move forward or backward on the tape by one step at a time — but that's enough to do anything that you can do with recursive functions.

A Turing machine can be seen as an idealized model of a computer (finite state machine) with some extra storage that grows on demand. Note that it's crucial that not only there isn't a finite bound on the tape, but even given the input, you can't reliably predict how much tape will be needed. If you could predict (i.e. compute) how much tape is needed from the input, then you could decide whether the computation would halt by calculating the maximum tape size and then treating the whole system, including the now finite tape, as a finite state machine.

Another way to simulate a Turing machine with computers is as follows. Simulate the Turing machine with a computer program that stores the beginning of the tape in memory. If the computation reaches the end of the part of the tape that fits in memory, replace the computer by a bigger computer and run the computation again.

Now suppose that you want to simulate a recursive computation with a computer. The techniques for executing recursive functions are well-known: each function call has a piece of memory, called a stack frame. Crucially, recursive functions can propagate information through multiple calls by passing variables around. In terms of implementation on a computer, that means that a function call might access the stack frame of a (grand-)*parent call.

A computer is a processor — a finite state machine (with a huge number of states, but we're doing computation theory here, so all that matters is that it's finite) — coupled with a finite memory. The microprocessor runs one giant while loop: “while the power is on, read an instruction from memory and execute it”. (Real processors are much more complex than that, but it doesn't affect what they can compute, only how fast and conveniently they do it.) A computer can execute recursive functions with just this while loop to provide iteration, plus the mechanism to access memory, including the ability to increase the size of the memory at will.

If you restrict the recursion to primitive recursion, then you can restrict iteration to bounded iteration. That is, instead of using while loops with an unpredictable running time, you can use for loops where the number of iterations is known at the beginning of the loop¹. The number of iterations might not be known at the beginning of the program: it can itself have been computed by previous loops.

I'm not going to even sketch a proof here, but there is an intuitive relationship between going from primitive recursion to full recursion, and going from for loops to while loops: in both cases, it involves not knowing in advance when you'll stop. With full recursion, this is done with the minimization operator, where you keep going until you find a parameter that satisfies the condition. With while loops, this is done by keeping going until the loop condition is satisfied.

¹  for loops in C-like languages can perform unbounded iteration just like while, it's just a matter of convention to restrict them to bounded iteration. When people talk about “for loops” in theory of computation, that means only loops that count from 1 to $n$ (or equivalent).


How to improve my these specific math skills?

I find it surprising and unfortunate that you didn't get to study algorithms and discrete math more in your university studies. As you seem to have realized, a person can know how to code, but without math, won't be able to solve really interesting problems.

Unfortunately there is no "Learn all algorithms you'll ever need in 21 days for dummies" book. There are hundreds, possibly thousands, of algorithms—even more if you also consider data structures—and it just isn't possible for anyone to know them all. There are no shortcuts to algorithms and math, something which has frustrated me numerous times too. All you can do is throw yourself in and let the knowledge slowly build up.

I would recommend getting yourself a good book on algorithms—my choice would probably be Steve Skiena's The Algorithm Design Manual since it assumes less math background than the more popular Introduction to Algorithms—and a good book on discrete math, of which there are several. I've heard good reviews of Concrete Mathematics but haven't read it as it's a little pricey. Sometimes books use the term "discrete math" in confusing ways; make sure the one you get covers at least graph theory, recurrence relations, Boolean algebra, basic set theory, basic combinatorics, and basic probablity, as those are the most vital topics for a software developer. A book on statistics and probablity, like this one, freely available online and written by a professor from my university, wouldn't go amiss either. And both linear algebra and abstract algebra are useful surprisingly often; I like Gilbert Strang's Linear Algebra and its Applications and Charles Pinter's A Book of Abstract Algebra for these topics.

Of course, just buying these books isn't enough, even if you then proceed to read them. Doing every exercise is a decent start, though probably too dry. I would do exercises until I had drilled down the basics. To really get into these topics, you have to work on problems that use them, which aren't really as hard to find as they might seem. A simple spell checker might calculate Levenshtein distance to suggest corrections for a misspelled word, which allows you to practice dynamic programming. Games and simulations have all sorts of uses for graph algorithms; I implemented the Floyd-Warshall Algorithm in Javascript for a game once, and Dijkstra's Shortest Path algorithm and A* are widely used in games. Project Euler is a great source for number theoretic and combinatorial algorithms. Also make sure not to neglect data structures; try solving some problems that revolve around sets or maps in a lower level language (C, C++, or Java) and implementing your own skip list or red-black tree or hash set. Although these data structures are often available in libraries, the concepts you learn by implementing them are widely applicable (e.g. I never would have understood the Rabin-Karp Algorithm without knowing about hash tables, because it uses hashing, in addition to number theory).

The great thing about this is that not only will you learn algorithms, you'll also get better at coding, and get more familiar with your chosen programming language, by being forced to solve unfamiliar problems. If there's some feature of your language that you've always wanted to use and never been able to, these kinds of exercises are a great way to do that too; I first really dug into Java generics while working on a problem about binary trees.

Finally, just remember that you don't have to know every algorithm off the top of your head. The Hungarian Algorithm in the question you linked is a special purpose algorithm for linear algebra. It's not something most programmers ever have to deal with. Contests do not reflect reality in that way. A contest might expect you to have memorized obscure algorithms and be able to implement them from scratch without any references in a short period of time. When you encounter problems in the wild, it's much more vital that you can clearly state the problem, identify what kind of technique or approach might be helpful, and do research to find something that can solve your problem. In my opinion, it's much more important to look at a problem about matrices, be able to think "This problem is about matrices. I should look at some linear algebra algorithms. Those are probably in a book about numerical algorithms", and then be able to find the Hungarian Algorithm and implement it, than it is to memorize that algorithm and be able to code it off the top of your head.


Imperfection in randomness in VLC shuffle playlist - why?

This is just speculation, but perhaps what VLC is attempting is to simulate... perfect randomness. That is, each song is picked uniformly at random, independently of previous songs. According to the coupon collector problem, if you have $n$ songs in your list and want to hear all of them, you will have to wait for roughly $n\ln n$ songs to be played. By that time, the average song will have been heard $\ln n$ times.

The problem seems to be not in VLC, but rather in the random experiment that VLC is trying to simulate. VLC is not trying to shuffle your playlist and play it through. Rather, it seems to just pick a new random song each time, regardless of the past.


Can an alphabet be extended in a reduction proof? (with sample problem)

A (computable) reduction from problem P to problem Q is a (computable) function that takes an instance of P to an instance of Q. In your case $P=\mathcal{E}^c$ and $Q = L^c$. So your reduction is "legal" (that is, conforms to the definition of reduction) if it takes an instance of $\mathcal{E}^c$ to an instance of $L^c$. That's all a function has to do in order to be a reduction.

(In principle there is no such thing as an instance of a problem – every string over the appropriate alphabet is an instance. But let's ignore this small issue.)


If $f(x) = O(x^n)$ then $f(x)^m = O(x^{nm})$. Indeed, $f(x) = O(x^n)$ means that $f(x) \leq Cx^n$ for some $C>0$. Therefore $f(x)^m \leq C^mx^{nm}$, and so $f(x)^m = O(x^{nm})$.

On the other hand, it is not true that $(g(x) + h(x))^m = g(x)^m + O(h(x)^m)$. For example, suppose that $g(x) = 2$ and $h(x) = 1$. Then it is not the case that $3^m = 2^m + O(1)$.

What is true is that $(g(x) + h(x))^m = O(g(x)^m + h(x)^m)$. Indeed, if $g(x) \leq h(x)$ then $$(g(x) + h(x))^m \leq (2h(x))^m = 2^m h(x)^m = O(h(x)^m) = O(g(x)^m + h(x)^m), $$
and similarly in the other case.

(Throughout this answer, $m \geq 1$ is a constant. The first part holds for any constant $m \geq 0$.)


Proving that a language satisfies the pumping lemma condition

The language is regular since it is the language of the regular expression $(aa)^*(bb)^*$.

Every regular language satisfies the conditions of the pumping lemma – this is precisely the statement of the pumping lemma! So one way to show, from first principles, that this language satisfies the conditions of the pumping lemma would be to just repeat the proof of the pumping lemma.

However, in this case we can show this more directly. We will show that the pumping lemma holds with a pumping constant of $p = 2$. Suppose that $w = a^{2i} b^{2j} \in L$. Note that $|w| \geq 2$. We consider two cases:

Case 1: $i \neq 0$. In this case, we can break $w$ in the following form: $x = \epsilon$, $y = a^2$, $z = a^{2(i-1)} b^{2j}$. We have $w = xyz$, $|xy| = 2 \leq p$ and $y \neq \epsilon$. For every $n$, $xy^nz = a^{2(i-1+n)} b^{2j} \in L$.
Case 2: $i = 0$. In this case, $j \neq 0$. We break $w$ into $x = \epsilon$, $y = b^2$, $z = b^{2(j-1)}$. The rest of the proof is very similar.


Your terminology is incorrect.  Amdahl's law is a way of estimating performance of a parallel program.  It is not a "programming model".  Amdahl's law says that if there is a computation, part of which is $M$ sequential (not parallelizable) instructions and part of which is $N$ instructions which could be parallelized, and you have $P$ processors, then the shortest computation time you can hope for is:
$$ M + \frac{N}{P}. $$

So the speedup with $P$ processors is:
$$ \frac{M+N}{M+\frac{N}{P}}. $$

Which, in the limit as $P \gg N$ goes to
$$ \frac{M+N}{M} = 1 + \frac{N}{M}. $$

The takeaway message is simply that you shouldn't fool yourself.  $N/M$ is much more important than $N/P$.


Bakery algorithm: what is the choosing[] boolean array for?

choosing[i] is true while number[i] is being updated to be larger than all the other values in the number array — the new ticket value that the thread is taking. In the body of the for loop, the code first waits for choosing[j] to be false, which indicates that thread number j has chosen its ticket for this round. If thread j goes on executing while thread i hasn't entered the critical section yet, then number[i] won't change, so:

If thread j is still in the same round and hasn't finished the critical section yet, then number[j] is the result of a max computation which may or may not have taken the current value of number[i] into account, depending on the interleaving of the execution of threads i and j.
If thread j is in the remainder section then number[j] is 0.
If thread j has begun a new round then its number[j] is the result of a max computation that took the current value of number[i] into account, thus number[j] > number[i].

In the first case, threads i and j are running their for loop concurrently; only one of them will win the (number[j],j)<(number[i],i) comparison and proceed into the critical section, and the other will wait for the winner's number value to become acceptable again. In the second case, thread j is not competing for the critical section. In the third case, thread j has a higher number and will wait in its own for loop while thread i hasn't reset its number[i] value.

The choosing array works around the lack of atomicity in the computation of number[] values. If it was removed, then you could have two threads computing the same value concurrently and each finding that it had the smaller value at the point of testing. This could happen with as little as two threads (I use the notation k.tmpX to designate local storage of the thread k):

initially: number[1] = number[2] = 0

thread 1                                   thread 2
//choosing[1]=true
1.tmp1 = number[1]
1.tmp2 = number[2]
                                           //choosing[2]=true
                                           2.tmp1 = number[1]
                                           2.tmp2 = number[2]
                                           number[2] = max(2.tmp1,2.tmp2)+1 = 1
                                           //choosing[2]=false
                                           //while (choosing[1]) {}
                                           while (number[1]≠0 &&
                                                  (number[1],1)<(number[2],2)) {}
                                           critical section ...
number[1] = max(1.tmp1,1.tmp2)+1 = 1
//choosing[1]=false
//while (choosing[2]) {}
while (number[2]≠0 &&
       (number[2],2)<(number[1],1)) {}
critical section ...
                                           critical section ...

The two threads computed the same ticket number. The bakery algorithm uses the thread number to determine the priority in this case. However, thread 2 decided to  the critical thread while thread 1 was still preparing, whereas thread 1 saw the new ticket number of thread 2 when deciding whether to enter the critical section but had computed its own ticket number based on thread 2's old ticket number. So thread 1 incorrectly entered the critical section.

The choosing array solves this problem by preventing thread 2 from entering the critical section. Since thread 1 is computing its ticket number at the time thread 2 is preparing to enter the critical section, thread 2 will block on while (choosing[1]) {}, after which it will see the updated value of number[1] and allow thread 1 to enter the critical section first, while thread 2 waits on while (number[1]≠0 && (number[1],1)<(number[2],2)) {}.


Hint from "Introduction to the Theory of Computation" by Michael Sipser (bible of theory of computation):
"We construct $M$ from $M_1$ and $M_2$ (the two original DFAs). To keep track of both simulation with finite memory you need to remember the state that each machine would be in if it had read up to this point in the input. Therefore you need to remember a pair of states...."
Initial states:
The start state will be a state constructed from the two original start states, i.e
$(x_1,y_1)$
Transitions:
What happens with input $a$?
Let's examine the two original automata:
$x_1$ can transition to $x_2$
$y_1$ can transition to $y_3$
Due to these facts we make the transition $\delta((x_1,y_1),a) = (x_2,y_3)$.
Final/Accepting states:
Any state pair $(x_i,y_j)$ where $x_i$ was an accepting state in automata 1, or $y_j$ was an accepting state in automata 2, i.e any state where $x_2$ or $y_2$ is mentioned.
One consequence is that the state we created a transition to i.e $(x_2,y_3)$, will be an accepting state.


Show that problem of Shortest-Path in digraph is in NL

The difficulty here is how to check using non-deterministic logarithmic space that there is no path from $s$ to $t$ of some length $\ell$. We cannot just go over all possible paths of length $\ell$ since in order to do this we will need to "remember" $\ell$ vertices, whereas we are only allowed to remember $O(1)$ vertices (since each vertex takes up $\Theta(\log n)$ space).

If we want to check that there exists a path of length $\ell$, we can simply guess the path vertex-by-vertex and check that it leads from $s$ to $t$; this only requires counting up to $\ell$, which takes logarithmic space (since we're only interested in $\ell < n$). But it's not so clear how to check that there doesn't exist a path of length $\ell$ – what would be a witness for that?

The solution is to use the technique of inductive counting, invented for the proof of the Immerman–Szelepcsényi theorem, which states that NL=coNL. This is what the solution uses.


Why is Brent's Cycle Detection method faster at finding a Linked List cycle than Floyd's Cycle Detection method?

The performance of cycle-finding algorithms depends on two parameters $m,n$. Here $n$ is the length of the cycle, and $m$ is the initial position of the cycle. For example, consider the sequence
$$ 2, 3, 5, 6, 5, 6, 5, 6, \ldots $$
Here the cycle is $5,6$ and so $n = 2$. The first index of the cycle (assuming $x_1 = 2$ and so on) is $m = 3$.

We assume that the sequence is generated by repeatedly applying some function $f$. We measure the complexity of cycle-finding algorithms by the number of applications of $f$.

According to Brent's paper, the complexity of Floyd's algorithm is between $3\max(m,n)$ and $3(m+n)$, and that of Brent's is at most $2\max(m,n) + n$, which is always better than $3\max(m,n)$.

A perhaps more meaningful comparison is what happens in the average case. In this case we assume that $f$ is a random function on a universe of size $N$ (the starting point doesn't matter in this case). Knuth showed that the expected running time of Floyd's algorithm is roughly $3.0924\sqrt{N}$, whereas Brent's algorithm runs in expected time roughly $1.9828\sqrt{N}$, as worked out in Brent's paper.

For more details, take a look at Brent's paper and the references therein.


Clarifying $\sum_{h=0}^{\lfloor lg(n)\rfloor}\lceil\frac{n}{2^{h+1}}\rceil O(h)=O(n\sum_{h=0}^{\lfloor lg(n)\rfloor}\frac{h}{2^h})$ in BUILD-MAX-HEAP

Since $h \leq \lfloor \lg n \rfloor$, we have $2^h \leq n$, and so $n/2^{h+1} \geq 1/2$. Therefore
$$
\left\lceil \frac{n}{2^{h+1}} \right\rceil \leq
\frac{n}{2^{h+1}} + 1 =
\frac{n}{2^{h+1}} + 2 \cdot \frac{1}{2} \leq
\frac{n}{2^{h+1}} + 2 \frac{n}{2^{h+1}} = 3 \frac{n}{2^{h+1}}.
$$
(In fact, if you are more careful then you can replace $3$ by $2$.)
More generally, if $x \geq c > 0$ then $\lceil x \rceil  = O(x)$, where the hidden constant depends on $c$.


Boolean Algebra Simplifying complex equation

Whenever you are faced with two Boolean expressions $f,g$ on $n$ variables and wish to know whether they are equivalent, there is a simple algorithm you can apply:

  Go over all $2^n$ possible truth assignments, and check whether $f$ and $g$ have the same truth value on each.

While this is infeasible for large $n$, in your case $n = 4$, so there are only 16 many truth assignments to check; in fact, you could even do this by hand, though it might be less error-prone if you programmed it.

Using this approach, you should be able to tell whether your simplification is valid.


Here is a rough sketch of an iteratively improving algorithm that I believe should work pretty well while minimizing the number of queries we do. It can also immediately start finding paths and slowly improve the paths it finds as it goes.

The first step is to evaluate every edge (if you wish to improve initial accuracy, evaluate every edge $k$ times) and use Dijkstra's to find the shortest distance $d_v$ from every vertex $v$ to the target vertex. This forms our initial belief of the graph.

Our goal is to find an accurate $\mu_e$ average weight for each vertex, but we want to be most certain about our precision "near" what we believe to be the optimal path(s). We do this by repeatedly finding a path from the start vertex to the target, in a probabilistic fashion, by repeating the following procedure:

If we are currently at vertex $v$ we have a choice from some edges. We currently believe that each edge has weight $\mu_e$, and when we take that edge we would get to vertex $w$ with remaining (believed) distance $d_w$. We consider this a multi-armed bandit problem, where choosing edge $e$ going to vertex $w$ would have cost $\mu_e + d_w$, and we want to minimize cost. We use this to probabilistically choose an edge, we query its weight, we update $\mu_e$ and $d$ with this new weight and then move to $w$.

As we keep repeating the above process we will balance exploration of the graph with exploitation automatically due to the multi-armed bandit.