Methods to prevent overfitting I am aware of three approaches to prevent over-fitting of data when trying to model it on a neural net.

The first two approaches I know suggest to train on more data and employ bootstrap aggregating. The third approach is to use a model that has the right capacity, one that has enough to fit the true regularities but not the weaker/dubious regularities (the noise). However, I don't quite understand this 2nd approach. How do we create a distinction and choose a model that detects this? Can someone expand on the second approach? I am aware of ways to limit the capacity such as early stopping(which is self explanatory), penalty for peculiar weights, etc. But an explanation on why these specific methods limit the capacity to fit the right data but not the wrong one would be helpful.

When choosing a specific model, to which you will try to fit your data into, you must know something about the problem. There is no way around it, machine learning cant do this magic for us, we have to know something.

First, convince yourself why complicated models can cause overfitting. Suppose I'm trying to learn some real valued function $f$, and I'm given $n$ samples of the form $S=(x_1,y_1),...,(x_n,y_n)$. If i choose to model my data by some polynomial (of arbitrary degree) then for any set of samples $S$, i can find a function in my model with zero training error, although it is likely to have high generalization error (a degree $n$ polynomial passing through all points in $S$ can always be found, regardless of any structure of the points in $S$). Perhaps using polynomials of degree$ \le 3$ will be good enough to model my data (it doesn't suffer from the previous problem). Why 3? I don't know, this depends on the specific types of functions I'm trying to learn.

A more concrete example, suppose you want to learn what is the appropriate dosage of some medicine, and you are given samples of the form $(x_1,y_1),...,(x_n,y_n)$ where $x_i\in\mathbb{R}$ denotes the dosage, and $y_i\in\left\{\text{'good'},\text{'bad'}\right\}$ tells you whether the dosage $x_i$ worked (it can be too high or too low). Allowing your algorithm to choose some arbitrary function can result in strange outputs. For example if you received the samples $(1,\text{'bad'}),(2,\text{'good'}),(3,\text{'good'})$ then a function $f:\mathbb{R}\rightarrow\left\{-1,1\right\}$ which satisfies $f(1)=-1,f(2)=f(3)=1$, but is random everywhere else, is consistent with the samples. Such $f$ will probably have no indication on the true effect of the medicine. Now, I'm no doctor, but perhaps it is worth considering functions of the form:

$I_{a,b}=\begin{cases}
+1, & x\in [a,b] \\
-1, & \text{otherwise}
\end{cases}$.

When choosing to model my data using such functions (segments), i use my knowledge on how medicines work (there is some appropriate dosage interval, while large deviations to any side could be dangerous).


Run time of a Simple Recurrence Given the recurrence $T(n) = T(\sqrt{n}) + \theta(lglgn)$, provide an asymptotically tight bound on it's run time.

My solution was to let $m = 2\sqrt{n}$, which leads to the recurrence $S(m) = S(m/2) + \theta(lg(2lg(m) + lg4)) = S(m/2) + \theta(lglgm)$.

By case 3 of the master rule, this means that $S(m) \in \theta(lglgm)$, because $lglgm \in \Omega(m^{log_2 1})$.

Since $lglgm = lg(lg2 + 0.5lgn) \in \theta(lglgn)$, we have that $T(n) \in \theta(lglgn).$

The provided solution to this problem says that $T(n) \in \theta((lglgn)^2)$, could someone help me find my mistake?

The solution is on page 2 of the below PDF, problem 1-2(d):
https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/assignments/ps1sol.pdf

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

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

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

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


Modified Clique Problem We know CLIQUE and HALF-CLIQUE problems are NP-complete. Now consider the class of graphs (let's call it $\mathcal{G}_{2K}$) where a graph $G=(V,E)$ is a member of $\mathcal{G}_{2K}$ iff $G$ has two SEPARATE cliques $K_1$ and $K_2$ of size $\dfrac{N}{2}$ (where $|V| = N$). My speculation is that $\mathcal{G}_{2K}$ is in NP and the corresponding existential problem is NP-complete, but I can't find any reduction form any well-known NP-complete problem.

Hence the question is: Is $\mathcal{G}_{2K}$ in P or it's NP-complete?

The question I asked is equivalent to these two questions:
1. Given graph $G=(V,E)$ and integer $k$, can we partition the vertices into two disjoint cliques of size $k$ and $|V|-k$.
2. Given graph $G=(V,E)$ can we partition the vertices into two independent sets of size $k$ and $|V|-k$?

The problem is equivalent to deciding whether the complement graph of $G$ has a bipartition $(A,B)$ such that $|A|=|B|$. In order to check if such a bipartition exists, one can first compute an arbitrary bipartition $(A,B)$. If no such bipartition exists, we are finished. If it does exists, we must check whether we can flip single connected components of this bipartition (which mean all vertices in $A$ of a particular connected component are moved to $B$ and vice versa) such that we obtain a new partition where $A$ is equal to $B$. Using a dynamic programing approach similar to the partition problem, this can be decided in polynomial time. Thus the original problem is also in P and not NP-hard unless P equals NP.


RAW Data Hazard resolution Let's consider the following MIPS (using pipelined arch.) assembly code:

lw r1,0(r2)
sub r4, r1, r6
and r6, r1, r7
or r8, r1, r9

the r1 value used in the second and third instruction will not be ready to use  until the end of the 4th cycle of the pipeline, while the 2nd and the 3rd instruction need it at the 4th and 5th cycle respectively, i think for the 3rd instruction the problem can be resolved using bypass but for the 2nd instruction i am not sure ??
can anyone tell me how to avoid the RAW data hazard in this case ??

It depends on the context. From a computer architecture perspective, you can insert a hazard detection unit that inserts a bubble in the pipeline when it detects this condition. It's shown top/left-ish in this picture from Patterson&Hennessy:

The logic doesn't do anything unexpected, it detects the case that an instruction in the ID wants to read a register that a memory read in the EX stage will write to, the instruction from the ID stage is then killed and PC is "held" so the instruction will re-execute.

From a programmer perspective, suppose there is no hazard detection unit, just insert the NOP yourself.


Finding a Hamiltonian Path through the complete graph on 37 vertices: $K_{37}$ I'm planning on making a fiber art $K_{37}$ (like the one I laser etched with help: K37: The complete graph on 37 nodes, svg). To accomplish this, the plan is to construct 37 pegs equally spaced in a annulus made from wood and then to string yarn between them. Since $K_{37}$ is a complete graph, it has a Hamiltonian path. My knowledge of computational graph theory is nil, and I am aware that this is not exactly an easy problem (see wikipedia: Hamiltonian Path Problem, for instance)

It seems that you're trying to construct the graph $K_{37}$ from string and nails without cutting the string.  For this, you don't want a Hamiltonian path (a path that visits every vertex exactly once) but an Euler trail (a walk that visits every edge exactly once).

In the case of a complete graph, finding an Euler trail is trivial: start at any vertex and move from vertex to vertex without repeating an edge. As long as the last thing you do is returning to the initial vertex, you've created an Euler trail.  (This is essentially Fleury's algorithm except that checking you've not disconnected the graph is trivial for a complete graph.


Can we say that Zookeeper updates are ACD (ACID without the I)? Zookeeper is based on the Zab (which is slightly different to Paxos) system.

We can do Atomic locks on top of a Zookeeper cluster.

Zookeeper provides eventual consistency.

Zookeeper provides durability.

(I'm aware that Zookeeper sacrifices Availability for Consistency and Partition Tolerance - making it CP - but I'm not asking that question here. )

My question is: Can we say that Zookeeper updates are ACD (ACID without the I)?

Atomicity is not about being able to implement "atomic locks" or not.  Consistency as used in the CAP theorem (i.e. the C in CAP) is not the same thing as Consistency in ACID, and Consistency in CAP is way stronger than eventual consistency.  ZooKeeper is an ACID system and a CP system, albeit the ACID "C" is not doing much work here.

Atomicity means a "transaction" either completes entirely or not at all.  It's mostly orthogonal to concurrency.  If you had a system that was Atomic but not Isolated, transactions could see the intermediate results of other in-progress transactions regardless of whether those other transactions got rolled back or not. Meanwhile, a non-Atomic but Isolated system would not see any intermediate results of in-progress transactions, but failed transactions need not rollback their work, so the detritus of failed transactions would be visible to all. Atomicity alone would not allow you to implement atomic locks; Isolation is really the more important property for that though technically Atomicity is also required.

Consistency in ACID means maintaining integrity constraints.  ZooKeeper provides few such constraints, so this is accomplished more or less trivially.  Consistency in CAP refers to linearizability which is different than but related to Isolation.  Isolation refers to serializability.  Traditionally, (one-copy) serializability was effectively strict one-copy serializability which is the combination of serializability and linearizability, but serializability and linearizability are actually distinct (though similar looking) notions, neither implying the other.  ZooKeeper provides strict one-copy serializability (if you sync before every read), and thus it is both Isolated and Consistent in the CAP sense.


When estimating camera motion from the fundamental matrix, why can translation only be recovered up to scale using epipolar geometry? I was wondering once you have recovered the fundamental matrix F such that xFx' = 0. If you try to recover translation and rotation from F, I am told that this is possible only up to scale? Why so?

This can be seen intuitively as follows:

The fundamental matrix $\mathtt{F}$ can be written in terms of the epipolar matrix $\mathtt{E}$, in which case the epipolar constraint equation becomes:
\begin{align}
\mathbf{x}^{\prime\top} \mathtt{F} \mathbf{x} &= 0\\
\mathbf{x}^{\prime\top} \mathtt{K}^{\prime-\top} \mathtt{E} \mathtt{K}^{-1} \mathbf{x} &= 0,\\
\end{align}
where $\mathtt{K}, \mathtt{K'}$ are the intrinsic camera matrices of the two images corresponding to the points $\mathbf{x}, \mathbf{x'}$, respectively, and I have used $(\cdot)^{-\top} = (\cdot^\top)^{-1}$.

Now, we also know that the epipolar matrix has the form
\begin{equation}
\mathtt{E} = \mathbf{t}^\times \mathtt{R},
\end{equation}
where $\mathbf{t}, \mathtt{R}$ are the relative translation vector and the relative rotation matrix, respectively, between the two images. The operator $(\cdot)^\times$ turns a $3-$vector into a $3\times 3$ skew-symmetric matrix. Since $\mathtt{E}$ is $3 \times 3$, $\mathbf{x}$ and $\mathbf{x'}$ are $3 \times 1$ vectors represented in what we call homogenous coordinates. These have an equivalence property of $\mathbf{x} = (x_1, x_2, x_3)^\top = (\lambda x_1, \lambda x_2, \lambda x_3)^\top = \lambda \mathbf{x}$ for any $\lambda \neq 0$. If you want to convert a homogeneous point into their more familiar 2D image plane representation, you simply take the first two components and divide them by the third one.

This means that, if we replace all of this in the epipolar constraint and multiply the translation $\mathbf{t}$ by an arbitrary scale factor, we get the following:
\begin{align}
\mathbf{x}^{\prime\top} \mathtt{K}^{\prime-\top} (\lambda \mathbf{t})^\times \mathtt{R} \mathtt{K}^{-1} \mathbf{x} &= \mathbf{x}^{\prime\top} \mathtt{K}^{\prime-\top} \mathbf{t}^\times \mathtt{R} \mathtt{K}^{-1} (\lambda \mathbf{x})\\
&= \mathbf{x}^{\prime\top} \mathtt{K}^{\prime-\top} \mathbf{t}^\times \mathtt{R} \mathtt{K}^{-1} \mathbf{x}\\
&= \mathbf{x}^{\prime\top} \mathtt{F} \mathbf{x} = 0,
\end{align}
which leads to the original constraint. This shows there is an overall scale ambiguity. More precisely, the epipolar matrix (and the fundamental matrix) are homogeneous quantities too. This can be further verified by taking the SVD decomposition of $\mathtt{E}$: if it is a valid essential matrix, two of its singular values are equal, hence $\mathtt{E}$ has 5 degrees of freedom and not 6.


Why don't they use all kinds of non-linear functions in Neural Network Activation Functions? Pardon my ignorance, but after just learning about Sigmoid and Tanh activation functions (and a few others), I am wondering why they choose functions that always go up and to the right? Why not use all kinds of crazy input functions, those that fluctuate up and down, ones that are directed down instead of up, etc.? What if used functions like those in your neurons, what is the problem, why isn't it done? Why do they stick to very primitive very simple functions?

I am wondering why they choose functions that always go up and to the right? Why not use [...] ones that are directed down instead of up, etc.?

The activation function is applied to a weighted sum of the inputs of the neuron. Replacing a function that is "directed up" with one that is "directed down" is equivalent to changing the weights. There's no particular reason to prefer an increasing function to a decreasing one, it just happens to be the convention.

Why not use all kinds of crazy input functions, those that fluctuate up and down

In principle, you could. People are using the functions that work best. If somebody found a "crazy" activation function that yielded good results it would certainly get used. However, using a "crazy" activation function probably makes it much harder to train the network. Part of the reason why e.g. ReLU is popular is because its simplicity makes training easier.


Name for almost random memory distribution on the heap If I had a heap like the following: with blue blocks being occupied memory and white blocks being free memory

What is the general name given to the situation illustrated, where the free and occupied cells become distributed almost 'randomly'?

This is an exam question, I've tried searching online and through the provided slides but to no avail.

This is fragmentation.  See https://en.wikipedia.org/wiki/Fragmentation_%28computing%29 for a definition.  Fragmentation can happy on any kind of storage; most commonly it is discussed for persistent storage (e.g., in filesystems), but heap fragmentation can also happen, and that is what you are describing.  See also https://en.wikipedia.org/wiki/Memory_management (which discusses heap fragmentation).


How does a buffer overrun corrupt the return address? I got stuck on the following note while reading a paper about computer security:

The stack mixes program data and control data
– by overrunning buffers on the stack we can corrupt the return  addresses!

In fact, I didn't understand how a buffer overrun corrupts the return address within a stack frame. Also the use of the term buffers was not very clear to me - what do they mean?

When your code calls a function, the called function usually allocates memory for its variables, just before the memory where the return address is stored (the address of the caller).

Let's say you have an array int a[100], and a double variable x. The compiler may quite reasonably allocate memory for x either just before or just after the memory for a. In the first case, setting a [-1] = 100; a [-2] = 1000; will likely change x. In the latter case, setting a [100] = 100; a [101] = 1000; will do the same thing. Trying to store into an array, using an index that is too small or too large, is called a "buffer overflow".

Now if you store a [102] = 0; or a [103] = 0; then chances are that this overwrites the memory where the caller's return address was stored. And if the function tries to return, the processor will start running code at the address that you stored into a [102] and a [103] with all kinds of negative consequences.


Why are there two not operators in lambda calculus? From Wikipedia:

$\mathrm{true} = \lambda a. \lambda b. a$
$\mathrm{false} = \lambda a. \lambda b. b$
Because true and false choose the first or second parameter they may
be combined to provide logic operators. Note that there are two
version of not, depending on the evaluation strategy that is chosen.
$\mathrm{and} = \lambda p . \lambda q . p \, q \, p$
$\mathrm{or} = \lambda p . \lambda q . p \, p \, q$
$\mathrm{not}_A = \lambda p . \lambda a . \lambda b . p \, b \, a$   (This is only a correct implementation if the evaluation strategy is applicative order.)
$\mathrm{not}_N = \lambda p . p \, (\lambda a . \lambda b . b) \, (\lambda a . \lambda b . a) = \lambda p . p \, \mathrm{false} \, \mathrm{true}$   (This is only a correct implementation if the evaluation
strategy is normal order.)

I know what applicative order and normal order are (eager evaluation vs lazy evaluation of arguments to functions). But I don’t understand why the two nots don’t work in both of these evaluation strategies.

The lambda-calculus is confluent. All the terms involved are strongly normalizing (these boolean encodings only work on booleans; they could do anything if applied to a lambda-term that doesn't reduce to $\mathrm{true}$ or $\mathrm{false}$). So the choice of reduction strategy is not relevant.

When something looks weird or incomprehensible on Wikipedia, check the history. Sometimes things get deformed over successive edits, and sometimes an edit is just wrong. WikiBlame can be very useful for that.

The edit that introduced the distinction between two evaluation strategy is from September 2012. It has no edit description, its content doesn't make sense (it implies that call-by-value is not an applicative-order strategy), and even the author was clearly not sure what they wrote (they left a comment with an interrogation).

The bit about normal order was added in December 2013 which was part of a series of edits mainly to improve the formatting and the wording. It doesn't look to me like the editor meant to change the meaning of the article, but they were mislead by the previous edit.

Hopefully someone will soon edit this article to rectify it, ideally with references for both of the not functions.

Incidentally, the choice of reduction strategy does matter if you want to extend these functions outside the booleans. For example, if you want to have $\mathrm{if}\,b\,M\,N$ where $b$ is a boolean (a term that reduces to $\mathrm{true}$ or $\mathrm{false}$) and $M$ and $N$ are arbitrary terms, then this behaves differently depending on the evaluation strategy. With call-by-value, this only terminates if $M$ and $N$ terminates. With call-by-name, this terminates if whichever of $M$ or $N$ is selected terminates, and the one that isn't selected doesn't matter. This is the reason why if can be defined as a function in languages that use call-by-name or lazy evaluation such as Haskell, but it needs to be a special form in languages that use eager evaluation such as Lisp and ML.

Another case where the evaluation strategy matters is if you want to work on partial booleans, that is, terms that either reduce to one of $\mathrm{true}$ or $\mathrm{false}$ or don't terminate ($\bot$). For $\mathrm{not}$, the choice of evalation strategy doesn't matter: $\mathrm{not}\,\bot = \bot$ anyway. For an operator like $\mathrm{or}$, the evaluation order does matter: $\mathrm{or} \, \mathrm{true} \, \bot$ could be either $\mathrm{true}$ or $\bot$, and likewise for $\mathrm{or} \, \bot \, \mathrm{true}$. With eager evaluation, they're both $\bot$, but with left-to-right normal order $\mathrm{or} \, \mathrm{true} \, \bot \to \mathrm{true}$ while $\mathrm{or} \, \bot \, \mathrm{true}$ does not terminate. It's natural to wonder if there could be a more clever implementation of $\mathrm{or}$ that always picks its terminating argument regardless of the evaluation strategy. This problem is known as Plotkin's parallel or, and it's an important result in the theory of the lambda calculus that there is no such term. There is no way for a lambda calculus function to take two arguments and evaluate them “in parallel”, reducing them and stopping as soon as one of them terminates. The function can be weakly normalizing (it terminates in some evaluation strategies) but not strongly normalizing (there are evaluation strategies where it doesn't terminate). Thus the lambda calculus is said to be inherently sequential. It's a very nice model of sequential computation, but if you want to model parallelism or concurrency, you need other tools.


Tight bound on the number of divisors of n The inner loop of this pseudocode runs only for the divisors of n

for i=1 to n:
   if(n%i==0):
      for j=1 to n:
         Do something in constant time

If I can get a bound on the number of divisor of n(The condition in the if statement) then I can get its time complexity.Please Help ?

Assume your input is $n$. I also assume that you know that we measure the time complexity of an algorithm as a function of input length to this algorithm which is $\log_2{n}$ in this case. Then even the following simple loop would take exponential time (as a function of input size)

for i=1 to n:
   print "hi"
end

since it loops $n$ times, where $n = 2^{\log_2{n}} = 2^{\text{input size}}$.

More precisely, its running time (as Yuval Filmus commented) is roughly $O(nn^{1/{\log{\log{n}}}})$ which is still exponential. But since your algorithm is $O(n^2)$ it is pseudo polynomial (polynomial in the numeric value of the input, not input size).


What is the complexity of an in-place merge algorithm for forward iterators I have written an in-place merge algorithm for forward iterators. My goal was to write an in-place merge algorithm to merge two sorted parts of a singly linked list without allocating extra memory to perform the merge. However, I have no clue how to determine its complexity.

Here is the corresponding pseudocode algorithm; I tried to represent the concept of iterators in pseudo-code, but that's not really pretty. Basically, an iterator is an object that points to a value in a sequence of elements. The only operations usable with a forward iterator are the following:

Check whether two iterators point to the same value (= and ≠); just remember that two values can be equal without being the same.
Copy the iterator (let it = other_it), basically create another iterator that points to the same value.
Advance the iterator so that it points to the next value in the sequence (advance).
Access the value it points to, generally to read or write that value (value_of), <- is used to assign the values.
Get the iterator pointing to the next value in the sequence (next_iterator).

The following function uses the set of operations defined above to implement an in-place merge algorithm.

function inplace_merge(first: ForwardIterator, middle: ForwardIterator, last: ForwardIterator)

    while first ≠ middle
        if value_of(middle) < value_of(first)

            # first should be in the right partition
            let tmp = value_of(first)

            # Put right in place
            value_of(first) <- value_of(middle)

            # Look for the place where to insert tmp
            let current = middle
            let next = next_iterator(current)

            # Move everything smaller than tmp to the left
            while next ≠ last and value_of(next) < tmp
                value_of(current) <- value_of(next)
                advance current
                advance next
            end while

            # Insert tmp in the right place
            value_of(current) <- tmp
        end if

        advance first
    end while

This algorithm takes two sorted ranges [first, middle) and [middle, last) and reorders them to produce a sorted range [first, last). The function compare is used to compare the elements. The algorithm more or less works like this: whenever an element in the left range is greater than the first element of the right range, we replace the first element of the right range in the left range, then we move every element to the left until we find the place where to insert the element that was originally in the left range (I know, plain-text descriptions sound a bit cryptic).

What is the complexity of this algorithm, considering that the complexity is determined by the number of comparisons performed between value with <?

Your algorithm is very similar to insertion sort or selection sort. Here is some pseudocode which hopefully captures your algorithm:

inplace_merge(A[1,...,n], B[1,...,m])

C[1,...,n] = A[1,...,n]
C[n+1,...n+m] = B[1,...,m]
for i from 1 to n:
   if C[i] > C[n+1]:
     find position j in {1,...,m} such that C[n+j] < C[i] <= C[n+j+1] (where C[n+m+1]=∞)
     C[i], C[n+1,...,n+j-1], C[n+j] = C[n+1], C[n+2,...,n+j], C[i]
return C

The invariant is that at the end of each iteration, C[1,...,i;n+1,...,n+m] and C[i+1,...,n] are both sorted, and that the multiset of elements never changes.

Consider what happens when all elements in the array A are larger than all elements in the array B. In this case, j always equals m, and so the running time of each iteration is $O(m)$, and the total running time is $O(nm)$.

In contrast, the mergesort merging algorithm merges the two arrays in time $O(n+m)$, and should be preferred over your algorithm.


How does CPU actually retrieve data from memory when you call a variable in a programming language? As I have understood from all the internet sources I can get to, when you declare and initialize a variable in java, you are allocating this data, say an 8-byte float, in a particular memory cell in the RAM, with the address specified as the row and column number. Now, suppose I want to access this memory location and print the float out. As a programmer, I will clearly not write the binary representation of the memory location of this float for the CPU to process; rather, I will call the variable name I declared before. When this variable name got transformed into binary code and sent to the CPU, how does CPU know what memory location this variable is referencing to? I mean, for that to work, doesn't the memory location of the variable has to be stored directly on the CPU? Because if not, you will have to store the the memory location of the float at some memory cell as well; in other words, when you call the variable, you have to first get from the RAM what memory address is the variable representing and then use that information to go to the RAM to retrieve the float. However, for the CPU to get to the memory address of the memory address of the memory address of the float, it still either has to store it directly on the CPU or has to store it in the RAM, and the same story goes one recursively. What is really happening when you need to call a variable? How to the CPU know the memory address associated with the variable in the first place without referring to the RAM? Because if the CPU is referring to the RAM, then that means it has already gotten the memory address f

Your assumption that the variable is sent to the CPU is wrong. Every program must be compiled to some machine code (or it will be interpreted, but it roughly comes down to the same thing). The idea of compilation is to translate the human-readable code to a series of bits, which can then be read by the processor. In order to get an idea of what those series of bits do, you could also take a look at assembly which is actually not much more than an encoding of the instruction set of a CPU.

Now the trick is that the compiler builds a so-called symbol table where it keeps track of all variables that have been defined by the programmer(s). Once it knows about all of the variables, it also knows how much RAM it needs (not considering dynamic allocation of course) and thus can allocate a certain space in memory. All variables are then mapped to some piece of memory or if the compiler is smart enough, it might even map certain (temporary) variables only to registers on the CPU to save some memory (not completely sure about that last thing though). The compiler thus creates a series of bits where each variable is represented by the correct register- or memory-address and the cpu does not bother/know about any variables.

For dynamically allocated memory things get a bit trickier, but eventually it comes down to memory addresses being stored in variables which are handled by the compiler again.

I hope I understood your question correctly and did not spread too much nonsense (if I did, please correct me) as I am not an authority whatsoever in this region, but that is roughly my view on these things.


monotone min-3-sat polynomial algorithm? I know that 3SAT is npc but i wonder why my little algorithm won't solve this problem:

given positive 3SAT - meaning: each of the m clauses is a disjunction of 3 literals over the variables $x_1,\dots,x_n$ ($n$ variables) and each literal is a positive appearance of a variable (no $~x_i$).

for example: $(x_1 \lor x_3 \lor x_7) \land (x_5 \lor x_4 \lor x_2)$

What is wrong with this "greedy" algorithm?:

run through all left clauses and find the variable that appears in most of them (can be implemented by counters array..).
take this variable, give him truth assignment, remove all clauses which he appeared in, zero the counters array and do again the previous step.
stop when no clauses left.
it looks like this algo runs in $O(m^2n)$ time.

why isn't it not an optimal algorithm?

UPDATE:
Sorry for the vague question, The problem is probably called MIN 3SAT, which every literal is positive but you must find minimum integer k such that there exists a truthful assignment of the variables which sets k variables to TRUE.

UPDATE 2:
Can someone give me an example to why the greedy algorithm won't give the optimal solution?
I read what rus9348 wrote but I still can't figure why the greedy approch is not good..

3SAT is NP-complete.  Positive 3SAT (where all literals are positive) is in P, and thus presumably not NP-complete.  There is an even simpler algorithm for Positive 3SAT: set all variables to true.  That will always provide a satisfying assignment.

I can't comment on your algorithm  because it doesn't seem fully specified: you describe what order to make assignments to variables, but you don't describe how to choose a truth assignment for each variable.  (Should it be set to true?  to  false?  The question doesn't say.)


Probability that two elements are compared in randomized quicksort I am having an issue in a specific part of the randomized quick-sort analysis.

As per the randomized quick-sort algorithm the pivot is chosen from the given subset on which it is called from a random index, instead of just choosing a specific index each time.

Now suppose that we give an array of size say $n$ to our randomized quicksort algorithm.

Now I request to have a look at the proof of lemma-7.1 in the text given below. Now we have given an array to our algorithm which can be of any permutation of the elements, but in the paragraph just after the proof of $lemma-7.1$.

why is the author considering a sorted instance of our input array while doing the analysis?

Moreover if look at the text after equation $(7.2)$ where there have justified their logic of finding the probability that $z_i$ shall be compared with $z_j$ in our algorithm. Now in that they are considering the subset {$z_i$,...,$z_j$}. Isn't this case of comparison of $z_i$,$z_j$ getting too specific if we consider that specific subset only? I mean to say we are using randomized approach and the probability of comparison might be derived using a more broader look, such as a permutation of all possible cases or so.

That we are using a specific subset and that too sorted is not convincing as to how are we getting the correct probability for our algorithm...

     {z1,z2,...,zn} zi being the ith minimum element
            ^
            |
            ----------------------------------------------------
                                                                |
    --P(Zi is compared with Zj)                                 |
   |                                                            |
   |                                                            |
   |-----> We are considering                                   |
   |        Zij = {Zi,Zi+1,...,Zj} which is a subset of --------
   |
   |------ Aren't we considering a very specific case??

And the probability of $1/(j-i+1)$ -> total no. of elements in the
                                        subset is also fixed for
                                                specific $i$ and $j$

In considering the probability of comparison of $z_i$,$z_j$, the subset in which the two elements are there and which is to be partitioned can be anything(i.e composed of any possible element) and of any size (not just $j-i+1$)...

May be the randomization condition is actually taking everything in
account but I am not getting it. Please can you explain me the logic they are using to find the said probability and also please convince me that we are correctly finding the probability of comparison.

For reference i am attaching the corresponding pages of INTRODUCTION TO ALGORITHMS 3RD ED-- CLRS

The idea of the proof is to compute, for any two elements $x,y$ in the array, the probability that they are compared in the algorithm. This probability could potentially depend on the entire array. However, it turns out that you can compute it only given the order statistics of $x,y$, that is, their relative order in the sorted array. If you know that $x$ is the $i$th smallest element in the array and that $y$ is the $j$th smallest element in the array, then the probability that $x,y$ are compared is $\frac{2}{|j-i|+1}$.

This is not a special case – every element $x$ in the array is the $i$th smallest element, for some value of $i$. This is just the pertinent information that allows us to calculate the probability that $x$ and $y$ are compared.


What edges are not in any MST? This is a homework question. I do not want the solution - I'm offering the solution I've been thinking of and wish to know whether is it good or why is it flawed.

Consider a weighted undirected graph. What edges of it are not a part of any minimum spanning tree (MST)? This problem only makes sense when several edges have the same weight, otherwise the MST is unique.

My idea comes from Prim's Algorithm with a slight change. Let $S$ and $T$ be two sets of vertices the algorithm works with. Instead of adding the minimum edge from $S$ to $T$ on every step, look for the minimum edge and more edges of the same value going from $S$ to the vertex the minimum edge goes to. By doing that, (so I suppose) we will obtain a graph containing all the edges which appear in any MST. If this is right, I can simply XOR the edges list with the original graph edges list to find what edges are not in any MST.

A Google search for "edges not in MST" leads me to this question. The answer included in the question has already been found wrong, as OP said in the last comment. For future references, here is my solution to the question.
Let $G$ be a weighted undirected (finite) graph. An edge $e$ is called superheavy if it is the unique heaviest edge in some cycle. Here is a characterization of the edges that are not in any MST.
An edge is not in any MST if and only if it is a superheavy edge
The well-known "if" part, a superheavy edge is not in any MST, is proved in the cycle property of MST.
The "only if" part, any edge $e$ that is not superheavy is in some MST, is harder to prove. Let me introduce an algorithm and a lemma first.
The delete-heaviest-edge algorithm (DHE) on $G$ removes a heaviest edge in any cycle until no cycle remains. Just to be extra clear, there might be multiple heaviest edges in one cycle. The edge removed can be chosen to be any one of them.
Lemma: DHE is an MST algorithm. That is, the final graph at the end of DHE is an MST of the original $G$.
One proof of the lemma can be developed by adapting the proof at reverse-delete algorithm.
For another proof of the lemma, reader can check my post at the delete-heaviest-edge algorithm on graphs with edges of distinct weights, where I proved the special case where all weights are distinct. For the general case of a given run of DHE where all weights of $G$ are not necessarily distinct, we can perturb the weights of all edges of $G$ so that all weights are distinct and that each edge removed is the unique heaviest edge in the corresponding cycle. We can then repeat the given run of DHE on the perturbed $G$, resulting in the same spanning tree, which is also the MST of the perturbed $G$, since this is the proven special case of distinct weights. By making the perturbation arbitrarily small, we can see the total weight of the resulting MST can be arbitrarily near to the weight of a (or any) MST of the original $G$. Once we take the limit of perturbation going to $0$, we can see that original given run of the DHE must produce a spanning tree with the minimal weight. The lemma is proved.
Now let us prove the "only if" part. Suppose edge $e$ is not a superheavy edge. Let us start a particular run of DHE. We will adjust that run whenever necessary to avoid deleting $e$. Suppose $e$, as a heaviest edge in some cycle is removed in some step. Because $e$ is not superheavy, there is another heaviest edge, say $f$, in that cycle. Let us modify that step so that it removes $f$ instead of $e$. Continue to run the algorithm, alway avoiding removing $e$ as we just did. At the end of the algorithm, we must arrive at an MST thanks to the lemma, which contains $e$. Proof of the "only if" part is done.
Since an edge not in any MST means it is superheavy, any algorithm that finds all the superheavy edges will also finds all edges that are not in any MST.
Algorithms to find all superheavy edges
Here is a naive algorithm. Iterate over all edges. For each edge $e$, pick arbitrarily one of its two vertices. Starting from this chosen vertex, make a DFS or BFS along edges with weight lower than that of $e$, checking whether we have reached the other vertex of $e$ all along. Once we have, $e$ is superheavy. Otherwise we cannot at the end of the search, implying $e$ is not superheavy.

It often happens that there is a unique MST, for example when all edge-weights are distinct. We can use various algorithms such as Kruskal's algorithm or Prim's algorithm to compute that unique MST. The superheavy edges are the edges that are not in that unique MST.

Here is the efficient algorithm to find all superheavy edges in general cases. Its time-complexity is about the time-complexity to sort the edges by weights, or $O(m\log m + n)$, where $n$ is the number of vertices and $m$ is the number of edges. Its space-complexity is about $O(m+n)$.

Sort all edges in groups of increasing weights so that we have $$E=E_1\cup E_2\cup \cdots \cup E_r$$ and $$w_1<w_2<\cdots<w_r,$$ where $E$ is the edge set of $G$ and every edge in $E_i$ has weight $w_i$.
Let $H$ be a graph that has the same vertices as $G$ but without any edges. Track the connected components of $H$ by a disjoint-set data structure.
For $i$ from 2 to $r$ do the following.

Add all edges in $E_{i-1}$ to $H$.
For each edge in $E_i$, check whether its endpoints are in the same connected component of $H$. If yes, it is a superheavy edge.


Finding undirected cycles in linear time (triangulating graphs while minimizing degree) In the article ["Triangulating Planar Graphs While Minimizing the Maximum Degree"] by Kant and Bodlaender [1], Section 4 briefly mentions the extraction of elementary cycles (no repeating edges) from what I assume is an undirected graph $H$. It has the following to say:

$H$ is planar and bipartite.
...using a simple modification of Euler's technique to find an Eulerian cycle in a graph, we can extract the elementary cycles $C_\mathrm{elem}$ from $H$.
Thus $H - C_\mathrm{elem}$ consists of paths $P$ with disjoint begin- and endpoints.

In the proof section it mentions that extracting elementary cycles and disjoint paths can be executed in linear time, allowing the triangulation algorithm as a whole to do the same.
From what I understand, there are no algorithms that compute the simple cycles of an undirected graph in linear time, raising the following questions:

Which algorithm does "Euler's technique to find an Eulerian cycle" refer to? There seem to be several algorithms with varying performance.
What is the "simple modification" in question? The paper doesn't say, and I haven't been able to find anything on the net.

[1] G. Kant and H. Bodlaender, "Triangulating Planar Graphs While Minimizing the Maximum Degree". Information and Computation, 135:1(1–14), 1997. (Science Direct)

Which algorithm does "Eulers technique to find an Eulerian cycle" refer to?

It probably refers to the Hierholzer algorithm (wiki) which takes linear time.

The algorithm below is from the wiki article.

Choose any starting vertex $v$, and follow a trail of edges from that vertex until returning to $v$.
It is not possible to get stuck at any vertex other than $v$, because the even degree of all vertices ensures that, when the trail enters another vertex $w$ there must be an unused edge leaving $w$.
The tour formed in this way is a closed tour, but may not cover all the vertices and edges of the initial graph.
As long as there exists a vertex $u$ that belongs to the current tour but that has adjacent edges not part of the tour, start another trail from $u$, following unused edges until returning to $u$, and join the tour formed in this way to the previous tour.

  What is the "simple modification" in question?

Hierholzer algorithm aims to apply to Eulerian graphs which are (and should be) graphs with every vertex of even degree. In your problem, $H$ is not necessarily an Eulerian graph.

So it needs modifications: In step 1, the closed tour from $v$ to $v$ may not exist at all; and in step 2, you may not be able to start another trail from $u$, or you may not be able to return to $u$.

  Thus $H−C_{elem}$ consists of paths $P$ with disjoint begin- and endpoints.

This can be seen from Figure 7(b) in the paper.


If the difference between two oracles is negligible, is the difference between a PPT algorithm with these two oracles also negligible? We say a negligible function is a function $\epsilon(n):\mathbb{N}\rightarrow \mathbb{R}$ such that for every positive integer $c$ there exists an integer $N_c$ such that for all $n > N_c$,
$$\epsilon(n)<\frac{1}{n^c}$$
(From wikipedia)

Assume that two probabilistic polynomial-time algorithms $O_{1},O_{2}$ satisfy that
$$
\Sigma_{y \in \{\, 0,1 \,\}}\left\vert \mathrm{Pr}\left[ O_{1}(x) = y \right] - \mathrm{Pr}\left[ O_{2}(x) = y \right] \right\vert \leq \epsilon_{1}(n)
$$
for all $x$, where $\left\vert x \right\vert = n$ and $\epsilon_{1}$ is negligible.

Let $A$ be a probabilistic polynomial-time algorithm. Can we get that
$$
\Sigma_{y \in \{\, 0,1 \,\}}\left\vert \mathrm{Pr}\left[ A^{O_{1}}(x) = y \right] - \mathrm{Pr}\left[ A^{O_{2}}(x) = y \right] \right\vert \leq \epsilon_{2}(n)
$$
for all $x$? Where $\left\vert x \right\vert = n$ and $\epsilon_{2}$ is negligible.

Given $x$, define $p_1(x,y) = \Pr[O_1(x) = y]$ and $p_2(x,y) = \Pr[O_2(x) = y]$. Let
$$
\begin{align*}
\delta_x &= \sum_y [\max(p_1(x,y),p_2(x,y)) - \min(p_1(x,y),p_2(x,y))] \\
&= \sum_y |p_1(x,y) - p_2(x,y)| \\ &\leq \epsilon_1(n).
\end{align*}
$$
On the other hand,
$$
\sum_y [\max(p_1(x,y),p_2(x,y)) + \min(p_1(x,y),p_2(x,y))] = \sum_y [p_1(x,y) + p_2(x,y)] = 2.
$$
Therefore
$$
\sum_y \min(p_1(x,y),p_2(x,y)) = 1 - \frac{\delta_x}{2}.
$$
Consider now the following random process that generates two random variables $R_1,R_2$:

For every $y$, with probability $\min(p_1(x,y),p_2(x,y))$, generate $R_1=R_2=y$.
Otherwise (this happens with probability $\delta_x/2$):

For every $y$, with probability $\frac{p_1(x,y)-\min(p_1(x,y),p_2(x,y))}{\delta_x/2}$ generate $R_1=y$.
For every $y$, with probability $\frac{p_2(x,y)-\min(p_1(x,y),p_2(x,y))}{\delta_x/2}$ generate $R_2=y$.

This process is a coupling that generates two random variables $R_1,R_2$ with the following properties:

$R_1 \sim O_1(x)$.
$R_2 \sim O_2(x)$.
$\Pr[R_1 \neq R_2] = \delta_x \leq \epsilon_1(n)$.

Let us go back to your algorithm $A$, and suppose that it runs in time $T(n)$. Use the coupling above to generate two random variables $B_1,B_2$ with the following properties:

$B_1 \sim A^{O_1}(x)$.
$B_2 \sim A^{O_2}(x)$.
$\Pr[B_1 \neq B_2] \leq T(n) \epsilon_1(n) =: \epsilon_2(n)$.

Note that $\epsilon_2(n)$ is negligible. We have

$$
\begin{align*}
&\sum_y |\Pr[A^{O_1}(x) = y] - \Pr[A^{O_2}(x) = y]| \\ =
&\sum_y |\Pr[B_1 = y] - \Pr[B_2 = y]| \\ =
&\Pr[B_1 \neq B_2] \sum_y |\Pr[B_1=y|B_1 \neq B_2] - \Pr[B_2=y|B_1 \neq B_2]| \\ \leq
&\Pr[B_1 \neq B_2] \sum_y (\Pr[B_1=y|B_1 \neq B_2] + \Pr[B_2=y|B_1 \neq B_2]) \\ \leq &2\epsilon_2(n),
\end{align*}
$$
since given $\Pr[B_1=y|B_1=B_2] = \Pr[B_2=y|B_1=B_2]$.


Determining whether $L^*$ is a finite union of $L^n$ for unary regular $L$ Give an algorithm that, given an NFA over a one-letter alphabet, determines whether the language it generates has the property that for some $n$, $$ L^* = \bigcup_{k=0}^n L^k. $$

I need some tips how to solve that.

We can identify every unary regular language $L$ with the set $S = \{ n : 1^n \in L \}$. It is known that $S$ is eventually periodic, that is,
$$ S = A \cup (B + m \mathbb{N}) = A \cup \{ b + mn : b \in B, n \in \mathbb{N} \} $$
for some finite $A,B$ and $m \geq 1$.
Let us consider four cases:

Case 1. $S$ is empty. In this case, $S^* = S^0$.

Case 2. $S$ is finite and non-empty. In this case, $S^*$ is infinite but $S^0 \cup \dots \cup S^n$ is finite for all $n$.

Case 3. $S = B + m\mathbb{N}$ for some non-empty $B$ and $m \geq 1$. I claim that
$$
B^* \bmod{m} = (B^1 \cup \dots \cup B^\ell) \bmod{m}
$$
for some finite $\ell$. Indeed, if $i \in B^* \bmod{m}$ then $i \in B^j \bmod{m}$ by definition of $B^*$ for some $j \geq 1$ (when $i = 0$ we can take $j = m$), so we can take $\ell$ to be the maximum of the $j$'s. It follows that
$$
S^+ = \bigcup_{i \in B^* \bmod m} n_i + m \mathbb{N}, \text{ where } n_i \equiv i \pmod{m}, \\
S^1 \cup \cdots \cup S^\ell = \bigcup_{i \in B^* \bmod m} n'_i + m \mathbb{N}, \text{ where } n_i \equiv i \pmod{m},
$$
where $n'_i \geq n_i$. It follows that $S^* \setminus (S^0 \cup \cdots \cup S^\ell)$ is finite, and so $S^* = S^0 \cup \cdots \cup S^r$ for some finite $r \geq \ell$, since every element in $S^* \setminus (S^0 \cup \cdots \cup S^\ell)$ appears in some $S^j$.

Case 4. $S = A \cup (B+m \mathbb{N})$ for some non-empty $A,B$ and $m \geq 1$. Let $C = A \cup B$. As before,
$$
C^* \bmod m = (C^0 \cup \cdots \cup C^\ell) \bmod m
$$
for some finite $\ell$.
Since $B$ is non-empty, $(B+m \mathbb{N})^m$ contains some multiple of $m$, and so all large enough multiples of $m$. Assuming $\ell \geq m$, it follows that
$$
S^* = D \cup \bigcup_{i \in C^* \bmod m} n_i + m \mathbb{N}, \text{ where } n_i \equiv i \pmod{m}, \\
S^0 \cup \cdots \cup S^\ell = D' \cup \bigcup_{i \in C^* \bmod m} n'_i + m \mathbb{N}, \text{ where } n_i \equiv i \pmod{m},
$$
where $D \supseteq D'$ are finite and $n'_i \geq n_i$. It follows that $S^* \setminus (S^0 \cup \cdots \cup S^\ell)$ is finite, and so $S^* = S^0 \cup \cdots \cup S^r$ for some finite $r \geq \ell$.

Conclusion. The property $S^* = S^0 \cup \cdots \cup S^n$ holds for some finite $n$ unless $S$ is finite and non-empty. Given a finite automaton for $L$, this condition is easy to check (in linear time).


Solving T(n) = 2*T(n-1)+4 witht the Master Theorem I am wondering if there is a way to solve a recurrence time function with the master theorem if no $b$ exists. Like in this case.
$$ T(n) = 2\times T(n-1)+4$$


Red Black Tree clarification I am quite new to Red-Black trees, and therefore I am having a bit of difficult time trying to understand them.

One of the properties of the Red-Black tree is that every red vertex must have two black children, meaning one cannot have two consecutive red vertices.

Can someone explain to me why this is an essential property? What are the benefits of having such a property?

If you check the proof height-balancedness of red-black trees, you'll see that we essentially analyse the black-height $h_b$ of the tree which, by another important invariant, is the number of black nodes from the root to any leaf.

The property you cite then gives us the right half of

$\qquad\displaystyle h_b(T) \leq h(T) \leq 2h_b(T)$,

which allows us to carry over bounds on black-height to usual height.


improving java 8's implement to hash map using avl tree Java 8 got a new implement to hashmap (using a tree). I have understand that in the worst case, it may be O(n) for lookup.

Will changing this implement to an avl tree change this O(n) case to something better (without changing the other complexities)?

here are some notes on it:

  This map usually acts as a binned (bucketed) hash table, but
    when bins get too large, they are transformed into bins of
    TreeNodes, each structured similarly to those in
    java.util.TreeMap. Most methods try to use normal bins, but
    relay to TreeNode methods when applicable (simply by checking
    instanceof a node).  Bins of TreeNodes may be traversed and
    used like any others, but additionally support faster lookup
    when overpopulated. However, since the vast majority of bins in
    normal use are not overpopulated, checking for existence of
    tree bins may be delayed in the course of table methods.

  Tree bins (i.e., bins whose elements are all TreeNodes) are
    ordered primarily by hashCode, but in the case of ties, if two
    elements are of the same "class C implements Comparable",
    type then their compareTo method is used for ordering. (We
    conservatively check generic types via reflection to validate
    this -- see method comparableClassFor).  The added complexity
    of tree bins is worthwhile in providing worst-case O(log n)
    operations when keys either have distinct hashes or are
    orderable, Thus, performance degrades gracefully under
    accidental or malicious usages in which hashCode() methods
    return values that are poorly distributed, as well as those in
    which many keys share a hashCode, so long as they are also
    Comparable. (If neither of these apply, we may waste about a
    factor of two in time and space compared to taking no
    precautions. But the only known cases stem from poor user
    programming practices that are already so slow that this makes
    little difference.)

This page on Oracle's website says:

  The alternative String hash function added in 7u6 has been removed from JDK 8, along with the jdk.map.althashing.threshold system property. Instead, hash bins containing a large number of colliding keys improve performance by storing their entries in a balanced tree instead of a linked list. This JDK 8 change applies only to HashMap, LinkedHashMap, and ConcurrentHashMap.

"Balanced tree" typically means either an AVL tree or a red-black tree. I would expect red-black tree, since TreeMap is already implemented as a red-black tree, and this Stack Overflow answer agrees. In that case, using an AVL tree wouldn't change much because AVL trees and red-black trees have basically the same complexity characteristics: search, insertion, and deletion are all worst case $O(\log n)$.

If the worst case for lookup in Java 8 HashMaps is $O(n)$, I'm not seeing how it could be the tree's fault. The motive behind this change is that HashMap buckets normally use linked lists, but linked lists are worst case $O(n)$ for lookup. Ordinary binary search trees have pathological cases where they become $O(n)$, but red black trees are specifically designed to prevent these cases. In a HashMap with linked lists, if you have a really really awful hash function, you could end up with all the items hashing to the same bucket and get $O(n)$ lookup, but it seems like with this red-black tree scheme, even if all the items hashed into the same bucket, you should get $O(\log n)$ lookup.


Maximum single-precision floating-point format number According to this wikipedia article the maximum single precision is 7f7fffff. Can some explain me why it is (7f7fffff)16 and not (7fffffff)16?

(7f7fffff)16 = (0111 1111 0111 1111 1111 1111 1111 1111)2
(7fffffff)16 = (0111 1111 1111 1111 1111 1111 1111 1111)2

The second exponent is FF, which signals NaN according to Wikipedia, and so the highest exponent is only FE. This is verified by the following C code snippet:

unsigned int i = 0x7FFFFFFF;
float f = *(float*)&i;

If you print f you get nan.


3-SAT and Systems of Nonlinear Modular Equations How is the 3-SAT problem reduced to solving for a system of nonlinear modular equations?

I have read  https://stackoverflow.com/questions/4294270/how-to-prove-that-a-problem-is-np-complete in how to prove that a problem is NP complete?.  But how is this done for systems of nonlinear modular equations specifically?

In that question above, Albert S. lays out nice steps:

"In order to prove that a problem $L$ is NP-complete, we need to do the following steps:

Prove your problem $L$ belongs to NP (that is that given a solution you can verify it in polynomial time)
Select a known NP-complete problem $L'$
Describe an algorithm $f$ that transforms $L'$ into $L$
Prove that your algorithm is correct (formally: $x ∈ L'$ if and only if $f(x) ∈ L$ )
Prove that also $f$ runs in polynomial time"

In other words

1) Where can one find (in the literature or elsewhere) the algorithm $f$ that reduced SAT to the problem of solving a system of nonlinear modular equations originally, so that he or she can better learn about the time complexity of nonlinear modular equations or 2) Could anyone answer below how it is reduced?

Does SAT reduce to solving a system of problem q?

Problem q

Given the coefficients $a$, are there any integer solutions for $x$?  List them:$$a_n x^n + \dots + a_1 x + a_0 = 0 \pmod m$$

The answer depends on whether we're talking about a single equation, or a system of equations; and whether the modulus $m$ is prime or composite.

A single equation

When the modulus $m$ is prime, then you can find a solution to a single equation

$$a_n x^n + \dots + a_1 x + a_0 = 0 \pmod m$$

in polynomial time (if one exists) by factoring the polynomial $a_n x^n + \dots + a_0$ over the finite field $\mathbb{F}_m$.  When $m$ is composite, finding a solution is (in general) at least as hard as factoring $m$.  See e.g.,Is deciding if there's a solution to a single multivariate quadratic equation NP-hard?.

System of equations

That's the situation for a single equation.  In contrast, finding a solution to a system of (multiple of) these equations (in multiple unknowns) is NP-hard, regardless of whether $m$ is prime or composite.  There's a simple reduction, if $m$ is prime.  Each clause is translated to a nonlinear equation, e.g., $(x_i \lor x_j \lor x_k)$ translates to the equation

$$(1-x_i)(1-x_j)(1-x_k)=0 \pmod m.$$

As another example, $(\overline{x_i} \lor x_j \lor x_k)$ translates to

$$x_i (1-x_j)(1-x_k)=0 \pmod m.$$

Finally, for each variable $x_i$ we add the equation

$$x_i (1-x_i) = 0 \pmod m$$

to force $x_i$ to be 0 or 1 (this is unnecessary when $m=2$).

An extension of this idea works when $m$ is composite, too; if $m=pr$ where $p$ is prime, then multiply the left-hand-side of each equation above by the constant $r$.  This yields a system of nonlinear equations of degree 3.  If you want a system of nonlinear equations of degree 2, that is achievable too; translate the clause $(x_i \lor x_j \lor x_k)$ to the two equations

$$(1-x_i) (1-x_j) = 1-y_{i,j} \pmod m \qquad \qquad (1-y_{i,j})(1-x_k)=0 \pmod m$$

where $y_{i,j}$ is a new fresh variable (different for each clause).


Are neural networks inherently imperfect because they mimic an imperfect machine (human)? Neural networks are the base for all(most?) of the machine learning / deep learning algorithms/programs.

Humans don't have fixed algorithms to decide or do something. Initially, we don't know how a snake is supposed to look. We learn that from experience. But our learning is never perfect. Once in a while, we mistake a black wire lying on the floor for a snake. Or we mistake the snake for a wire.

Given that neural networks are using the same technique as humans, are they inherently imperfect? Surely, we can make the self-driving network much better than best human, but that is because it got much more experience(24x7) than the human. But can we guarantee it's perfectness?(mathematically, or at least by testing, enough to make people trust in the programs)

I have this question because of the moral implications ML programs bring. I guess this will cause a lot of problem in adopting these technologies, especially when human life is at stake(eg. surgeon, self-driving cars, self-flying jets) as humans would rather rely on an imperfect human than a lesser imperfect AI.

It's better to think of neural networks as inspired by human biology, not that they're using exactly the same mechanism.

The notion of "inherently imperfect" isn't well-defined, so the question isn't meaningful.  And, no, neural networks aren't always imperfect.  For instance, suppose the learning task was "label everything 0".  If you give a neural network a training set with one million examples, all of which have the label 0, then the neural network might well learn to output label 0 on all possible inputs.

As far as moral implications, it's not clear that it matters much why neural networks are imperfect; what's important is that they are often imperfect.  But moral implications are probably more a matter of the study of ethics and philosophy than the science of computing, so I'll leave that there.

Finally, I encourage you to avoid binary thinking.  Don't divide the world into "perfect" vs "imperfect".  An engineer would say that in practice nothing is perfect; it's all about degrees of imperfection.  One system might be good enough, or better than the reasonably available alternatives, even if it's not 100% perfect.


Best-Case Running Time For Binary Search Tree Insertion The notion of best-case running time is kind of ambiguous for me. According to wikipedia, the definition of best case running time is:

  The term best-case performance is used in computer science to describe the way of an algorithm behaves under optimal conditions. For example, the best case for a simple linear search on a list occurs when the desired element is the first element of the list.

According to this definition, the best case running time for BST insertion should be $O(1)$ [consider that we are inserting to the root node]. But different resources says different things, some claim that it is $O(\log n)$ [perfect balanced tree] and some others claim that it is $O(1)$ which one should I believe?

Both! That is, if you are lenient with what "best-case" means. The best-case is the input for respectively run¹ of an algorithm which minimises runtime (for a given size). I guess that some of your sources refer to (asymptotically) optimal BST implementations, either them or you mixing up the notions.

These are the facts:

For any (reasonable) binary search tree implementation, the best-case insertion time is certainly $O(1)$ (for all sizes): all nodes are in the root's right subtree, the one to be inserted belong in the left.
An optimal binary search tree implemenentation has worst-case insertion time in $\Theta(\log n)$; it is height-balanced (examples include AVL- and Red-Black-trees).

That's equivalent for deterministic algorithms; for nondeterministic ones you consider runs.


Universality of the Toffoli gate Regarding the quantum Toffoli gate:

is it classicaly universal, and if so, why?
is it quantumly universal, and why?

Toffoli is universal for classical computation (as shown by @Victor). However, Toffoli is NOT universal for quantum computation (unless we have something crazy like $P = BQP$).
To be universal for quantum computation (under the usual definition), the group generated by your gates has to be dense in the unitaries. In other words, given an arbitrary $\epsilon$ and target unitary $U$ there is some way to apply a finite number of your quantum gates to get a unitary $U'$ such that $||U - U'|| < \epsilon$.
Toffoli by itself is clearly not universal under this definition since it always takes basis states to  basis states, and thus, for example, it cannot implement something that takes $|0\rangle \rightarrow \frac{1}{\sqrt{2}}(|0\rangle + |1\rangle)$. In other words, it cannot create superposition.


Canonical infinitely ambiguous languages In an article I am currently reading the grammar

S → SS | a | ε

is being described as canonical infinitely ambiguous. The infinitely ambiguous part I have no problem recognizing, but does "canonical" mean? Does it mean "typical", "standard example" etc.?

I think your understanding the use of "canonical" here as "standard example" is correct; similarly, grammars for parenthesis matching or palindromes are canonical examples for context-free grammars, generally.


Quick Sort - First Element As Pivot I'm studying Quick-Sort and I am confused as to how it works when the first element is chosen as the pivot point.

I am trying to trace the first step in the Quick-Sort algorithm, to move the pivot (15) into its appropriate position.

Example: [15, -7, 22, 7, 21, 34, -13, 19]

My understanding:

15, -7, 22, 7, 34, -13, 19
#   ^                   ^

Move left-pointer to first element larger than the pivot. 1 comparison (move to 22).
Move right-pointer to first element smaller than the pivot. 1 comparison (move to -13).

15, -7, 22, 7, 34, -13, 19
#       ^           ^

Swap elements at the pointers (22, -13).

15, -7, -13, 7, 34, 22, -13, 19
#       ^           ^

Move left-pointer to first element larger than the pivot. 2 comparisons (move to 34).
Unable to move right-pointer to first element smaller than the pivot (cannot past the left-pointer.

15, -7, -13, 7, 34, 22, -13, 19
#               ^   ^

Swap elements at the pointers (34, 22).

15, -7, -13, 7, 22, 34, -13, 19
#               ^   ^

This is where I am stuck. My understanding is that the pivot should then be swapped with 22, but that doesn't seem correct?

How do I move the pivot (15) into its appropriate position?

Usually, a random pivot is selected and moved to the first location.
After swapping -13 and 22, your pointers should be on 7 and 34.

7 and 34 are correctly placed.
Also 7 and 34 are adjacent, so time has come to put the pivot in its correct place.

array looks like this

15, -7, -13, 7, 34, 22, 19

So now you know that all elements after 34 are greater than 15.
So swap the first element before 34 with the pivot.

So array looks like

7, -7, -13, 15, 34, 22, 19

Now all on left of 15 are lesser than 15 and all on right of 15 are greater than 15


Solve recurrence relation $T(n)=n^{1/5}T(n^{4/5})+5n/4$ I am trying to solve this recurrence relation - $T(n)=n^{1/5}T(n^{4/5})+5n/4$. I can't use the master's method and the recursion tree method because of that $n^{1/5}$ term.
We can write $$\frac{T(n)}n=\frac{T(n^{4/5})}{n^{4/5}}+\frac54$$
Now we can change variable $S(n)=\frac{T(n)}{n}$. So, we get $$S(n)=S(n^{4/5})+\frac{5}{4}$$
Then I used the recurrence tree method by taking $n=2^{(\frac{5}{4})^k}$. I got $S(n)=O((log_{5/4}(log_2 n))^2)$. So, $$T(n)=O(n(log_{5/4}(log_2 n))^2)$$
I don't know, the answer doesn't look right. Can anyone please help me out? If anyone knows the final answer please let me know, so that I can check.
Thanks!

Derivation
Lets consider $n = 2^{(5/4)^k}$. Now we can evaluate step by step:
$$ S(n) = S(2^{(5/4)^{k-1}}) + 5/4 = S(2^{(5/4)^{k-2}}) + 5/4 + 5/4$$
Notice that every time $k$ is reduced by one since:
$$\left(2^{(5/4)^{k}}\right)^{4/5} = 2^{(5/4)^{k}\cdot(4/5)} = 2^{(5/4)^{k-1}}$$
Thus we can denote $S(n)$ as (assuming $S(2) = 0$ as base case):
$$\sum_{i=1}^k 5/4 = (5/4)k $$
Now lets solve $n = 2^{(5/4)^k}$ for $n$. Apply $\log_2$ and then $\log_{5/4}$ on both sides: $k = \log_{5/4}(\log_2(n))$ and thus $S(n) = (5/4)\log_{5/4}(\log_2(n))$.

Test by plugging it in
You can simply plug your solution in to test it.
For $S(n) = S(n^{4/5}) + 5/4$ you can obtain $S(n) = (5/4)\log_{5/4}(\log_2(n))$ by the recursion tree method (as described above). Lets plug this into our recurrence:
$$S(n) = (5/4)\log_{5/4}(\log_2(n^{4/5}))+5/4 = (5/4)\log_{5/4}((4/5)\log_2(n))+5/4$$
And by the rules of logaritm:
$$S(n) = (5/4)\log_{5/4}(\log_2(n))+(5/4)\log_{5/4}(4/5)+5/4$$
Notice $\log_{5/4}(4/5) = -1$ and things cancel out:
$$S(n) = (5/4)\log_{5/4}(\log_2(n))-(5/4)+5/4 = (5/4)\log_{5/4}(\log_2(n))$$
Our expression for $S(n)$ fulfills the recurrence. Hence $$T(n)/n = S(n) \Rightarrow T(n) = (5/4)n\log_{5/4}\log_2(n)$$
A double logarithm looks scary but if often occurs when recurrences have the form $T(n) = aT(n^\alpha) +b$.


Does the conservative two phase locking protocol produce cascadeless schedules? Let us consider the following schedule :

\begin{array}{lcr}
\mbox{$T_1$} & \mbox{$T_2$}\\
\\
\mbox{lock-exclusive(a)}  \\
\mbox{lock-exclusive(b)}  \\
\mbox{read(a)} \\
\mbox{a=a+50} \\
\mbox{write(a)} \\
\mbox{unlock(a)} \\
\mbox{} & \mbox{lock-exclusive(a)}\\
\mbox{} & \mbox{read(a)}\\
\mbox{} & \mbox{a=a+50}\\
\mbox{} & \mbox{write(a)}\\
\mbox{} & \mbox{unlock(a)}\\
\mbox{read(b)} \\
\mbox{b=b+100} \\
\mbox{write(b)} \\
\mbox{unlock(b)} \\ \end{array}

Since in the schedule the lock on $a$ is released, it is possible for the transaction $T_2$ to acquire the lock on $a$. Now the transaction $T_2$ reads the value of $a$ which was written by transaction $T_1$. This implies that if the transaction $T_1$ aborts, the transaction $T_2$ must be aborted for consistency purposes. Does it mean that even though a conservative two phase protocol is used, the schedules may not necesssarily be cascadeless?

Yes, the conservative 2PL does not garantuee cascadelessness. Requesting all locks at the beginning of the transaction is used to prevent deadlocks.

If you want to prevent cascading rollbacks, you need to have a look at how the locks are released. There are two versions of the 2PL-Protocol that garantuee cascadeless schedules: the strong 2PL and the rigorous 2PL, which is even stricter.

Schedules that satisfy the strong 2PL may release read-locks at any time and all write-lock at the end of the transaction. Schedules that satisfy the rigorous 2PL may only release all locks at the end of the transaction.

Lets have a look at what happens to your schedule if you use the conservative and rigorous (or strong) 2PL.

\begin{array}{lcr}
\mbox{$T_1$} & \mbox{$T_2$}\\
\\
\mbox{lock-exclusive(a)}  \\
\mbox{lock-exclusive(b)}  \\
\mbox{read(a)} \\
\mbox{a=a+50} \\
\mbox{write(a)} \\
\mbox{read(b)} \\
\mbox{b=b+100} \\
\mbox{write(b)} \\
\mbox{unlock(a)} \\
\mbox{unlock(b)} \\
\mbox{} & \mbox{lock-exclusive(a)}\\
\mbox{} & \mbox{read(a)}\\
\mbox{} & \mbox{a=a+50}\\
\mbox{} & \mbox{write(a)}\\
\mbox{} & \mbox{unlock(a)}\\
\end{array}

Because $T_1$ is not allowed to do $\mbox{unlock(a)}$, $T_2$ can not request the lock and therefore can not start. $T_1$ continues until the end and releases its lock. Now $T_2$ can start.

You can also see here that a conservative, rigorous 2PL leads to a serial execution of Transactions that access the same variables.


Are CPU architectures biased towards procedural runtimes? Are there any changes that could be made to CPUs to make them perform better for concurrent runtimes like Rust?  For instance, are there changes to branch prediction implementations or cache sizes that would help concurrent runtimes?

I have the impression that current CPU designs might be optimized more for procedural runtimes like C.  If we were instead going to optimize for concurrent runtimes, how would CPUs look different?

For isntance, branch prediction was implemented based on generalizations drawn in research papers analyzing procedural codes. I'm wondering if the concurrency abstraction will add a significant working-set to the runtime that adversely impacts existing branch prediction algorithms. For example, predicting in a for loop is one thing, but when the target of the branch is always some new portion of memory (graphic, text, etc), it'll always be a cache miss, and there'll never be branch history for it-- because neither have touched it yet.

This is probably a silly question because the content, though it might always be in RAM, will be branched to an order-of-magnitude less than it'll be used (once it's been loaded to cache)...but still, there should be an observable temporal-boundary to the contexts stored in the cache and branch predictors in a procedural runtime, that would be manifest as an abstraction-boundary in a more parallelized environment.  So I'm wondering... Have these boundaries been observed?  Have any research papers have analyzed this?

Are CPU architectures biased towards procedural code over concurrent code; or are modern CPUs sufficiently general-purpose that a highly concurrent language doesn't suffer?

It is probably more the case that modern computer architectures are designed with the goal of improving the quality of code generated by compilers against a budget of cost in die area and power used. Runtime libraries are just a specific instance of compiled code that needs to be executed in an efficient manner.

For a very long time, the target language for most architectures has been the "C" language. This reflects the modest demands that that language makes on its hardware and the fact that it has become an almost universal systems programming language (Sorry Rust and Go, you have a long way to go to beat C).

A consequence of this seems to be that new languages are often defined in terms of their C equivalent semantics just so that they will avoid needing processor facilities that are likely to be absent on current computers.

The payoff for a processor that matches well with modern compilers is that code from those compilers runs well and the processor has at least a chance to be competitive. The cost of failure here dooms the processor before it can get started. Just two examples in the negative include the iAPX-432 and the Itanium, both by Intel. Both had a very poor relationship with their compilers (Ada and C respectively) with the failure of the products turning into a blame game between silicon and software.


Nearest neighbor search in latitude/longitude coordinates I have two sets of lat/long points, $A$ and $B$. For each point $a$ in $A$, I want to find the corresponding closest point (by Haversine distance) $b$ in $B$. I'd like to use a space-partitioning tree, but as far as I can tell, quadtrees and k-d trees are confined to working in Euclidean space. How can I efficiently do a nearest-neighbor lookup in spherical space?
One solution I've considered is projection into 3d space and then using an octree, but I'd prefer not to do that if a space-partitioning tree (or alternative algorithm) that works with spherical coordinates directly exists.

First things first, if this is really a geography problem, then you probably don't want to calculate distances on the sphere, but rather on the reference ellipsoid. But even then, the reference ellipsoid is close enough to a sphere that it works as an approximation, and then accurate distances can be computed as appropriate.
You've already worked out that if all you need is nearest neighbour on points, then using 3D distance as a proxy for great circle distance is probably the most efficient approach. To be honest, this is probably the best solution for your specific problem, but not if you had to do distance queries involving non-point geometry (e.g. "find me all lines within 200km of this point").
The usual practice for spatial indexing in GIS is to use some variant on a bounding volume hierarchy.
In Cartesian space, that would mean an R-tree, and in geographic space, you would use circles of a sphere or ellipsoid as the bounding volume shape. In the case of a binary tree index, you can use a great circle as the splitting criteria for each node.


Generate slice that contains element Suppose I have the array:

[2, 3, 4, 5, 6, 7, 8, 9]

Now based on few parameters:

current_item - currently selected item.
select_size - selection size, always odd.

I want to get a sublist of the list that follows the conditions:

current_item should be in middle of sublist if that is possible.
In case when there is not enough elements on left/right of the list, use the ones from right/left.

Examples:

list: [2, 3, 4, 5, 6, 7, 8, 9]
current_item: 5
select_size: 3

result: [4, 5, 6]

list: [2, 3, 4, 5, 6, 7, 8, 9]
current_item: 2
select_size: 5

result: [2, 3, 4, 5, 6]

list: [2, 3, 4, 5, 6, 7, 8, 9]
current_item: 8
select_size: 5

result: [5, 6, 7, 8, 9]

Let the index of the central item be $c$, and the length of the list be $2r+1$. We assume that the indices of the list are $0,\ldots,n-1$.

There are four cases to consider:

If $n > 2r+1$, then the results are undefined (per your post).
If $0 \leq c-r$ and $c+r \leq n-1$, then you just take elements $c-r,\ldots,c+r$.
If $c-r < 0$, then you take elements $0,\ldots,2r$.
If $c+r \geq n$, then you take elements $n-2r-1,\ldots,n-1$.

In the latter two cases, we are guaranteed to be within bounds since $n > 2r+1$.


Recurrences and Generating Functions in Algorithms Combinatorics plays an important role in computer science. We frequently utilize combinatorial methods in both analysis as well as design in algorithms. For example one method for finding a $k$-vertex cover set in a graph might just inspect all $\binom{n}{k}$ possible subsets. While the binomial functions grows exponentially, if $k$ is some fixed constant we end up with a polynomial time algorithm by asymptotic analysis.

Often times real-life problems require more complex combinatorial mechanisms which we may define in terms of recurrences. One famous example is the fibonacci sequence (naively) defined as:

$f(n) = \begin{cases}
   1 & \text{if } n = 1 \\
   0 & \text{if } n = 0 \\
   f(n-1) + f(n-2) & \text{otherwise}
  \end{cases}
$

Now computing the value of the $n$th term grows exponentially using this recurrence, but thanks to dynamic programming, we may compute it in linear time. Now, not all recurrences lend themselves to DP (off hand, the factorial function), but it is a potentially exploitable property when defining some count as a recurrence rather than a generating function.

Generating functions are an elegant way to formalize some count for a given structure. Perhaps the most famous is the binomial generating function defined as:

$(x + y)^\alpha = \sum_{k=0}^\infty \binom{\alpha}{k}x^{\alpha - k}y^k$

Luckily this has a closed form solution. Not all generating functions permit such a compact description.

  Now my question is this: how often are generating functions used in design of algorithms? It is easy to see how they may be exploited to understand the rate of growth required by an algorithm via analysis, but what can they tell us about a problem when creating a method to solve some problem?

If many times the same count may be reformulated as a recurrence it may lend itself to dynamic programming, but again perhaps the same generating function has a closed form. So it is not so evenly cut.

Generating functions are useful when you're designing counting algorithms. That is, not only when you're looking for the number of objects having a certain property, but also when you're looking for a way to enumerate these objects (and, perhaps, generate an algorithm to count the objects). There is a very good presentation in chapter 7 of Concrete Mathematics by Ronald Graham, Donald Knuth, and Oren Patashnik. The examples below are from these books (the mistakes and lack of clarity are mine).

Suppose that you're looking for the ways to make change with a given set of coins. For example, with common US denominations¹, the possible coins are $[1], [5], [10], [25], [100]$. To give ¢42 in change, one possibility is $[25][10][5][1][1]$; another possibility is $[10][10][10][10][1][1]$. We'll write $42 \langle [25][10][5][1]^2 \rangle = \langle [10]^4 [1]^2 \rangle$. More generally, we can write a generating function for all the ways to give change:
$$H = \sum_{h\ge0} \sum_{q\ge0} \sum_{d\ge0} \sum_{n\ge0} \sum_{p\ge0} [100]^h [25]^q [10]^d [5]^n [1]^p$$
In more technical terms, $H$ is a term in the space of power series over the five variables $[100], [25], [10], [5], [1]$. Define the valuation of a monomial in this space by
$$\langle [100]^h [25]^q [10]^d [5]^n [1]^p \rangle = 100 h + 25 q + 10 d + 5 n + p$$
Then the ways to give $v$ cents in change are the number of monomials whose valuation is $v$. We can express $H$ in an incremental fashion, by first writing down the ways $P$ to give change in pennies only, then the ways $N$ to give
change in pennies and nickels, and so on. ($I$ means no coin.)
$$\begin{gather*}
  P = I + [1] + [1]^2 + [1]^3 + \ldots = \frac{I}{I - [1]} \\
  N = (I + [5] + [5]^2 + [5]^3 + \ldots) P = \frac{P}{I - [5]} \\
  D = (I + [10] + [10]^2 + [10]^3 + \ldots) N = \frac{N}{I - [10]} \\
  Q = (I + [25] + [25]^2 + [25]^3 + \ldots) D = \frac{D}{I - [25]} \\
  H = (I + [100] + [100]^2 + [100]^3 + \ldots) Q = \frac{Q}{I - [100]} \\
\end{gather*}$$
If you want to count and not just enumerate the ways to give change, then there is a simple way to use the formal series we've obtained. Apply the homomorphism
$$S: \quad [1] \mapsto X, \quad [5] \mapsto X^5, \quad [10] \mapsto X^{10}, [25] \mapsto X^{25}, [100] \mapsto X^{100} $$
The coefficient of $X^v$ in $S(C)$ is the number of ways to give $v$ cents in change.

A harder example: suppose that you want to study all the ways to tile rectangles with 2×1 dominoes. For example, there are two ways to tile a 2×2 rectangle, either with two horizontal dominoes or with two vertical dominoes. Counting the number of ways to tile a $2 \times n$ rectangle is fairly easy, but the $3 \times n$ case quickly becomes nonobvious. We can enumerate all the possible tilings of a horizontal band of height 3 by sticking dominoes together, which quickly yields repetitive patterns:
$$\begin{cases}
  U = \mathsf{o} + \mathsf{L} V + \mathsf{\Gamma} \Lambda + \mathord{\equiv} U \\
  V = \substack{\mathsf{I}\\\strut} U + \substack{=\\\:-} V \\
  \Lambda = \substack{\strut\\\mathsf{I}} U + \substack{\:-\\=} \Lambda \\
\end{cases}$$
where the funny shapes represent elementary domino arrangements: $\mathsf{o}$ is no domino, $\mathsf{L}$ is a vertical domino on top of the left part of a horizontal domino, $\substack{\strut\\\mathsf{I}}$ is a vertical domino aligned with the bottom of the band of height 3, $\substack{\:-\\=}$ is a horizontal domino aligned with the top of the band plus two horizontal dominoes below it and one step to the right, etc. Here, multiplication represents horizontal concatenation and is not commutative, but there are equations between the elementary patterns that form variables in this power series. As before with the coins, we can substitute $X$ for every domino and get a generating series for the number of tilings of a $3 \times (2n/3)$ rectangle (i.e. the coefficient of $X^{3k}$ is the number of ways to tile a rectangle of area $6k$, which contains $3k$ dominoes and has the width $2k$). The series can also be used in more versatile ways; for example, by distinguishing vertical and horizontal dominoes, we can count the tilings with a given number of vertical and horizontal dominoes.

Again, read Concrete Mathematics for a less rushed³ presentation.

¹  I know my list is incomplete; assume a simplified US suitable for mathematical examples.²
²  Also, if it comes up, assume spherical coins.
³  And better typeset.


Algorithm for exploring a parameter space I have a research problem which has a general outline as follows:

I have a 2D parameter space, $(\alpha, \beta)$ which serve as initial conditions on some set of partial differential equations. Given values for $\alpha, \beta$ I can integrate this set of PDEs numerically to obtain a result in a 2D phase space $(x,y)$.

Now, suppose I want to work backwards and find the values of $(\alpha, \beta)$, which generate a particular $(x,y)$. I can see a general, crude algorithm as,

Choose a random $(\alpha, \beta)$
Integrate PDE to obtain $(x,y)$
Inspect how close to the desired result we are
Adjust $(\alpha, \beta)$.
Repeat

I feel like there must be a smart/fast way to do this. Can anyone point me in the direction of some algorithms/resources which may be able to accomplish this goal? Thanks

Problem statement: You have a function $f:\mathbb{R}^2 \to \mathbb{R}^2$ where you know how to compute $f$ but not $f'$.  Given $(x,y)$, you want to find $(\alpha,\beta)$ such that $f(\alpha,\beta)=(x,y)$.

One approach is to use mathematical techniques for black-box optimization.  Define $g:\mathbb{R}^2 \to \mathbb{R}$ by

$$g(\alpha,\beta) = \|f(\alpha,\beta)-(x,y)\|^2,$$

i.e., the squared L2-norm of how far off the answer is.  Then your goal is to find $(\alpha,\beta)$ that minimizes $g$. Such a minimum will be a solution to your original problem.

The minimization problem could be solved using gradient descent, Newton's method, or some other iterative method.

The iterative methods will often require you to be able to compute the gradient of this function.  The gradient can be computed in a black-box way by using

$${\partial g \over \partial \alpha}(\alpha,\beta) = {g(\alpha+\epsilon,\beta) - g(\alpha-\epsilon,\beta) \over 2\epsilon}$$

where $\epsilon$ is a sufficiently small number, and similarly for ${\partial g \over \partial \beta}$.

This method assumes that $f$ is a "nice" function: e.g., continuous and differential and doesn't change too quickly, if you make small changes to its inputs.


Primality testing algorithm Say, I would like to check a hypothesis concerning primes. Something like "there exists a prime between $n$ and $2n$ for every choice of $n$". I would like to run a code in MATLAB for choices of $n$ upto $2^{32}$ and then use that data and publish the conjecture in a journal.

The question is, what should I use to check primality. Obviously, AKS is an option but it is really really slow. I can use the in-built MATLAB function $isprime()$ which I think uses $10$ instances of Miller-Rabin. This will be way faster but the journal might reject this saying that Miller Rabin is probabilistic and that I should instead use a deterministicalgorithm since one exists.

What should I do? Use AKS? Go with MATLAB's inbuilt Miller-Rabin? Or look at other deterministic algorithms?

I don't think this is the best place to ask this. However I could not find where else to ask. Any suggestions?

A pragmatic answer: Use the Miller-Rabin test with 50 iterations.  The probability that a composite number will be wrongly declared prime by this test is at most $2^{-100}$ (see, e.g., here).  This is smaller than the chance of a cosmic ray causing a bitflip error that causes your program to output an erroneous result.  So, if you're not worried about cosmic rays, you shouldn't be worried about probabilistic algorithms.

An alternative: use any probabilistic algorithm to rule out composite numbers.  If the probabilistic algorithm claims the number is prime, use a deterministic primality test, or use a test that produces a primality certificate.  There are many such algorithms, and you can study the literature and find one which leads the best tradeoff between complexity of implementation vs speed on numbers of the size you care about.


Are there specific rules for programming languages applicable to Quantum Computers? What would be the requirements for programming languages that are used for quantum computers? Do standard procedural languages with their constructs be sufficient, and succinctly capture the computing capabilities of a Quantum Computer? To illustrate, languages such as Assembler would most likely be closest to the hardware, and the programmer programs to the Assemblers' specifications. CSP is an example of specification for concurrent processes. Are there any formalisms such as CSP for quantum computers, or even languages such as Assembly for quantum computers?

We probably don't yet know enough about the landscape of practical quantum computing devices to lay down the kinds of concrete specifications you're asking for. It also seems to me that there's a big gap between what Assembly Languages and a formalism like CSP brings to the table. So, this question probably has different answers at different levels of hardware and software abstraction.

What all that being said, "A Layered Software Architecture for Quantum Computing Design Tools" by Svore et. al lays out a framework that I believe cuts across what you're getting it.  It's simply a proposal though, not a specification per se.  The authors do lay out some of the challenges faced when designing quantum computing design tools and programming languages and I think address what you're looking for.  The previously mentioned Liquid language seems to be an an attempt and working off this framework.

From what I've seen, quantum programming systems typically to work by providing a universal set of elementary gates for quantum circuits and possibly some higher-level primitives for common quantum algorithm components like the Quantum Fourier Transform.  I believe Svore,  et. al. refer to this layer as Quantum Assembly. For example, the two-qubit CNot gate and arbitrary single qubit unitaries are universal for quantum computation. The ability to lay out circuits from these primitives would provide you with the ability to express an arbitrary quantum computation.

I'd hesitate to call this assembly in the sense that we know it from classical computing as it corresponds to a set of primitives from a low-level abstract model of quantum computation and not to an abstract or concrete instruction set.  Going back to my first comment, it's not clear that we're even sure what kind of quantum instruction set is best at this point.


Doesn't post-order traversal require subtrees to be evaluated separately? Consider this tree:

If I traverse it using post-order, I'd start at B (as it is the leftmost leaf) and that's where my misunderstanding begins. I know B is the first and A will be the last node in post order, as the rule is left-right-root. One of my university professors said the correct answer for the post-order traversal of a tree similar to the one above would be B, C, D, E, A, but in my understanding, it should be B, D, E, C, A.

Am I getting it wrong? Shouldn't I evaluate (C,D),(C,E) as a subtree and then go back to the parent tree?

You are right. You finish each sub-tree before printing that sub-tree's root node. The correct order is B, D, E, C, A


A hard $n$-fold integral Consider the $n$-fold integral
$$
J = \int_{\theta_1 \in I_1, \theta_2 \in I_2 \ldots, \theta_n \in I_n} d\theta_n\ldots d\theta_2 d\theta_1
$$

whose intervals are defined by
$$
\begin{align}
I_1 = [0,1] \\
I_i = [\max(c_i,\theta_{i-1}),1] , 2\leq i\leq n
\end{align}
$$

and the $c_i \in [0,1]$ are predefined rational constants. Given a rational $v\in [0,1]$,

  is deciding if $J=v$ NP-hard?

Informally , each $\max$ in the lower limits of the intervals leads to a two-way split in evaluating the integral, and thus to $2^{n-1}$ integrals that sum to $J$.

Your problem is a special case of the following: given a convex polyhedron defined by a set of linear inequalities, compute its volume.  I believe that problem has been studied in the literature.

For instance, for related work on computing the volume of convex polyhedra/polytopes, see the following:

Algorithm for finding the volume of a convex polytope
Computing the Volume of a Convex Polytope Using Interval Arithmetic
Polytope volume computation

There is probably lots more work out there that might be relevant, but maybe this gives you a start.  You might start by reading that work to see if there are any techniques you can adapt; and by doing a literature review with the above as an entry point into the literature.


Choosing a random edge with restrictions Given a bipartite graph $G = (V, U, E)$ such that $|V| = |U| =2^n$, one wants to sample an edge from $G$, uniformly at random, with the following operations:
1. One can sample $u \in U$ w.p $\frac{1}{|U|}$ ,or $v \in V$ w.p $\frac{1}{|V|}$.
2. There exists a polynomial time oracle, which can, given $u \in U$ (or $v \in V$), returns the degree of $u$ (the degree may be exponential in $n$).
3. The size of $E$ is unknown.
4. One can not test, given $u$ and $v$, if there is an edge between $u$ and $v$.
5. There is an oracle which can, given $u$, return $v$ such that $v$ uniformly chosen from the set of all neighbors of $u$.

If one has only polynomial time (in $n$) - is it possible to choose an edge uniformly at random? Is it possible to choose from a distribution close to uniform?

Without these restrictions, it would have been possible to choose $u$ w.p $\frac{deg(u)}{\sum deg(u)}$, and then choose $v$ u.a.r from the neighbors of $u$.

You can't.  Consider the bipartite graph with a single edge $(u_0,v_0)$, with $u_0,v_0$ randomly chosen at time of creation of the graph.  Then sampling from $U$ has only a $1/2^n$ chance to hit $u_0$ each time, and sampling from $V$ has only a $1/2^n$ chance to hit $v_0$ each time, so you need exponentially many samples before you can find that edge.

In particular, after making $q$ samples, there is at most a $q/2^n$ chance that you receive either $u_0$ or $v_0$.  Without sampling either $u_0$ or $v_0$ you have no hope of outputting the edge $(u_0,v_0)$.  So after polynomially many samples, there's only an exponentially small chance of outputting that edge.  Yet a correct algorithm must always output that edge every time.  So in general, there's no way to solve your problem, or even to output from a distribution close to the desired one.


What is the formal name for this algorithmic problem? I'm doing some work on a problem and I'm finding it difficult to research it with out the actual name of the problem, since the problem I'm working on gives it it's own abstraction.

The problem is this, Given a long straight road S is the set of the locations of houses down the road. For example S = [1,2,3] would be that houses are placed at 1km 2km and 3km from the end of the road.

We have radio towers that cover a range of 1km and we want to place radio towers at locations along the road so that all houses are covered using the minimum number of towers.

I already know the algorithm to do it, however I'm finding it difficult to understand the proof so would really like the formal name for this problem so that I can research it further.

This general form of problem is a facility location problem. The specific version you're asking about is a covering problem – you have a set of points (the houses) and you're trying to cover them with circles of some radius (the areas that get reception from each tower).


Is unconstrained quadratic programming NP-hard? I could not find the answer on the Internet. The case of  quadratic programming with constraints is already solved on this forum, see Transforming SAT to Quadratic Programming in polynomial time. But what happens if there are no constraints or if the only acceptable constraint is that the variables are non-negative?

1-IN-3SAT is an NP-complete variant of 3SAT in which the goal is to determine whether some assignment satisfies exactly one literal per clause. We can convert an instance of 1-IN-3SAT (even without the restriction on the number of literals per clause) to an equivalent instance of quadratic programming in which all the variables are constrained to be non-negative as follows:

For each variable $x_i$, the quadratic program has two variables $x_i^+,x_i^-$, constrained to be non-negative.
The objective is to minimize

$$
\sum_i (x_i^+ + x_i^- - 1)^2 + x_i^+ x_i^- + \sum_j (C_j - 1)^2,
$$
where $i$ goes over all variables, $j$ goes over all clauses, and $C_j$ is the sum of all literals in $C_j$: for example, if the $j$th clause is $x_1 \lor \bar{x}_2 \lor x_3$ then $C_j = x_1 + (1-x_2) + x_3$.

By construction the objective function is always non-negative. The first two summands are zero if the $x_i^\pm$ encode an assignment to the original variables, and the third is zero is this assignment satisfies exactly one literal per clause.

Without any constraints, the problem becomes easy. The law of inertia (which can be implemented efficiently) shows that up to a linear change of basis, we can assume that the quadratic to be minimized is
$$
\sum_{i \in A} z_i^2 - \sum_{j \in B} z_j^2 + 2\sum_k c_k z_k + M,
$$
where $A,B$ are disjoint. If $B$ is non-empty then the quadratic form is unbounded from below, so let us assume that $B = \emptyset$. If $c_k \neq 0$ for some $k \notin A$, then the quadratic form is also unbounded from below, so let us assume that the $c_k$ are supported on $A$. Therefore the quadratic is equal to
$$
\sum_{i \in A} [(z_i + c_i)^2 - c_i^2] + M,
$$
showing that the minimum is $M - \sum_i c_i^2$.

A third variant that can be considered is a homogeneous objective function with non-negativity constraints. This variant is also easy.

The law of inertia transforms the problem into that of minimizing
$$
\sum_{i \in A} z_i^2 - \sum_{j \in B} z_j^2
$$
under some arbitrary linear constraints.

Using linear algebra, we can check whether the linear constraints force $z_j = 0$ for all $j \in B$. If not, then the quadratic form is unbounded from below, so let us assume it is the case. Our quadratic form is thus positive semidefinite, and so convex optimization algorithms can be used to solve it (see Wikipedia).


How big is the capacity of a standard memory cell that the pointer is linking to? Often programming language lectures and references have an illustration of computer memory as an array composed of individual cells. Each cell has an address, which is effectively the pointer and can be used to access it. I learned that 32 bit systems will have 4 byte pointers and then got curious what the (standard) capacity of those cells (they are pointing to) was. The most discrete unit of memory is a Memory Cell, but with 1 bit capacity, this does not really fit the bill.

That depends on the underlying architecture. Most machines today use byte addresses, but machines that addressed words (i.e. 16, 18, 32, even 36 bits) were reasonably common. If I recall correctly, most RISC machines were unable to address anything but words (but gave addresses in bytes). At least, such an address caused the CPU to fetch both words and snip out and assemble the piece wanted.

What your favorite language does above the machine's intrincacies, ask them. Often they will refuse to handle pointers that aren't aligned at some "machine natural boundary", like the size of a C double, 8 bytes. Even on machines that have no penalty attached to non-aligned address acces.