Query all bounding boxes which contain a point

Use a 2-d segment tree. Assuming we have $n$ items, construction takes time $O(n \cdot \log^2(n))$ and each query takes $O(\log^2(n))$ time. These times become $O(n \cdot \log(n))$ and $O(\log(n))$ time, respectively, if we use fractional cascading and lowest-level interval tree. These are good times unless there is more problem structure.

The query is called "multi-dimensional stabbing query" or "point enclosure query".

Range tree involves finding points in a query range. Segment tree involves finding rectangles that contain a query point.

On an unrelated note, one might wish to use an R-tree with sort-tile-recursive (STR) bulk-loading. This leads to almost no overlap between bounding boxes for a node's children and the structure is balanced. If we are lucky (i.e. R-tree involves heuristics and we wish to avoid ties for each component), the structure is good for moderate number of dimensions because factor of $d \cdot \log(n)$ for time is lower than $\log^{\textrm{max}(d - 1, 1)}(n)$ (noting that $d \geq 1$). We take advantage of fact that use of R-tree does not involve cloning primitives. Also, nearest neighbor via heuristic can perform quite well with R-tree, which seems to be something that that excels at w.r.t. segment tree and range tree. Additionally, one might wish to for dynamic structure use an R*-tree or one might wish to for slightly more dimensions use an X-tree. The more dimensions one has, the more likely linear scan is more affordable via a kind of "curse of dimensionality".

Further, if one has only distances and no absolute locations, a metric tree will prove useful. Structures that assume rectangle primitives will be aided by fact that a point is a degenerate rectangle. A pair of points that act as opposite corners of a rectangle can be turned into one point via a "corner transformation" from Pagel 1993.

One strategy that may be used with R-tree is augmenting it with "look-ahead" and edge checks to get guaranteed theoretically acceptable time for a query such as point enclosure query. This is even when it seems an R-tree is designed specifically for this kind of query.

References

Pagel et al. - The transformation technique for spatial objects revisited (1993)


Is the difference between between an union and a product of two DFA lies in their accepting states?

Please use the terminology correctly. The union operation is an operation defined on sets. It does not make sense to speak of the union of two automata.

The product construction can be used to give a constructive proof that the class of regular languages is closed under union. But with minor modifications, the product construction can also be used to show that the class of regular languages is closed under intersection as well as under set difference.

Assume that we have two DFA $M_1 = (Q_1,\delta_1,\Sigma,q^1_0,F_1)$ and $M_1 = (Q_2,\delta_2,\Sigma,q^2_0,F_2)$. In the case of intersection, define the set of accepting states as

$$F = \{ (q_1,q_2) \mid q_1 \in Q_1 \wedge q_2 \in Q_2 \} $$

For set difference, define the set of accepting states as

$$F = \{ (q_1,q_2) \mid q_1 \in Q_1 \wedge q_2 \notin Q_2 \} $$


Have a look at this:
https://medium.com/machine-learning-bites/deeplearning-series-convolutional-neural-networks-a9c2f2ee1524

It's like this:
third dimension of input and filter must match!
So if you only have one of those yellow filters your output will be 6x6x1. But if you have let's say 42 filters then you'll perform 42 filter operations and your output will be 6x6x42.

Hope this helps ;)


Splitting a group of numbers into $k$ sorted groups

Your second idea seems to be close. Here is the actual algorithm (no random pivot is required):

Find the $i{n\over k}$'th order statistic for every $1\le i\le k$. This will take $O(n)$ each time for $k$ values: $O(nk)$.
For every such $i$, put all elements with values between the $i{n\over k}$'th and the $(i+1){n\over k}$'th order statistics in the $i$'th bucket. For each $i$ it would cost $O(n)$ and there are $k$ different values for $i$, thus total of $O(nk)$.

Both steps take $O(nk)$ and therefore the entire algorithm runs in $O(nk)$ as required
Hint for the second question: think how you can combine this algorithm with a coarse version of quicksort


Prove completeness of a language with Turing Machine

I program in Java a class Turing that takes the transitions table, the input value (to be calculated) and the initial state and simulate a Turing Machine

This is not enough. You still need to prove, that your class can simulate ANY Turing machine.

Normally to show Turing completness one will

Implement Universal Turing Machine in this language and
Show how unlimited tape is possible.

Of course unlimited tape is impossible in realistic hardware, but even for idealized translation model for languages like C, there are problems

Also I want to add one more clause: make sure that your language well-defined enough. It shall either have mathematical definition or clear formal translation model in language standard.


Smallest integer i stored as a float such that i+1=i

Standard “float” has a 24 bit mantissa (the highest bit doesn’t get stored because it is always 1). Therefore all integers that fit into 24 bits - all integers less than $2^{24}$ - can be represented exactly.

From $2^{24}$ onward only even numbers can be stored. So you take N = $2^{24}$, and carefully check what n+1 is according to the rounding rules.

BTW. It makes life a lot easier if you don't look at the exact bit representation of float, but just take it as "1 bit sign, 8 bit exponent, 23 bit mantissa + 1 implicit leading mantissa bit".


I wouldn't have said they were algorithms per se, more a collection of transformations.

If you want to get a theoretical viewpoint on monads, I'd suggest picking up a category theory textbook. You don't need to do "3 years of maths" to understand one, just some set theory (probably) and some dedication.

On the other hand, if you'd prefer a practical handle, I'd learn the Haskell programming language, which uses monads extensively to represent certain types of side-effects. "Learn You a Haskell" is very good. Try and avoid the infamous "monad tutorials" which inevitably over-simplify in order to produce an analogy. I think just reading the monad typeclass, then looking at examples is probably the best advice.


Expressing the language of squares as a concatenation of two languages

The answer depends on $|\Sigma|$. If $\Sigma$ contains a single letter then $L = (\Sigma\Sigma)^*(\Sigma\Sigma)^*$ can be written as a concatenation of two nontrivial languages.

Conversely, suppose that $|\Sigma| > 1$, say $a,b \in \Sigma$. Since $\epsilon \in L$, necessarily $\epsilon \in L_1,L_2$. This implies that all words in $L_1,L_2$ are squares, and in particular $a \notin L_1,L_2$. Since $aa \in L$, we must have $aa \in L_1$ or $aa \in L_2$. Without loss of generality, assume that $aa \in L_1$. We similarly get that $bb \in L_1$ or $bb \in L_2$. Since $aabb \notin L$, we must have $bb \in L_1$. Since $L_2 \neq \{\epsilon\}$, it must contain some non-empty word $w$. Hence both $aaw$ and $bbw$ are squares. However, this is impossible (why?), and we reach a contradiction.


In TensorFlow tutorials, why do they use only the first term of cross-entropy as the cost function?

Great question!  Actually, there's no contradiction.  The short version of the explanation is that those two equations look different because they are intended for slightly different scenarios -- but under the covers, they're actually much more similar than you might think.  Let me walk you through it, and hopefully by the end of this explanation you'll see how everything is consistent and why both equations are correct, in the particular context where they're used.

Cross-entropy loss for multi-class neural networks

When using neural networks for MNIST, we have 10 classes (one per digit).  The neural net has 10 outputs (i.e., 10 neurons at the final layer).  Call the outputs $\hat{y}_0,\hat{y}_1,\dots,\hat{y}_{9}$.  If you feed in an image $x$, the intended interpretation is that $\hat{y}_d$ is supposed to represent the neural network's estimate of the "probability" that the image is an instance of the digit $d$.

For the training set, we know what the desired output is.  Let's define $y_0,y_1,\dots,y_9$ to be the desired "probability distribution".  In particular, $y_d$ should be $1$ for the correct digit $d$ and $0$ for all other values of $d$.

With these definitions, the cross-entropy loss for a single instance $x$ is defined to be

$$C_x = - \sum_{i=0}^9 y_i \log \hat{y}_i.$$

(Notice that if the correct digit is $d$, then this value simplifies to $-\log \hat{y}_d$, since we have $y_d=1$ and $y_i=0$ for all other $i$.)

The empirical cross-entropy loss for an entire training set is the average of these values, over all of the instances in the training set:

$$C = - {1 \over n} \sum_x \sum_{i=0}^9 y_i \log \hat{y}_i.$$

That's the cross-entropy loss.  I think this is exactly what the Tensor Flow tutorial is computing.  (Side note: this is different from the equation you presented.  You were missing the inner sum over all 10 classes.  I suspect you might have misinterpreted the Tensor Flow code.  No biggy.)

You can also see how this generalizes to any number of classes: the sum over $i=0,1,\dots,9$ gets changed to a sum over all classes, however many of them there may be.

Cross-entropy loss for two-class neural networks

As a special case, suppose we have two classes.  In particular, suppose there are two classes and two outputs from the neural network (two neurons at the output layer).  Then the cross-entropy loss for a single instance (the inner sum) becomes just

$$C_x = - y_0 \log \hat{y}_0 - y_1 \log \hat{y}_1.$$

Normally we normalize $y_0,y_1$ to be a probability distribution, so $y_0+y_1=1$, and similarly for $\hat{y}_0,\hat{y}_1$.  As a result, we have $y_0 = 1-y_1$ and $\hat{y}_0 = 1-\hat{y}_1$.  So, for a two-class neural network, we have

$$C_x = - y_1 \log \hat{y}_1 - (1-y_1) \log (1-\hat{y}_1),$$

and the empirical loss for an entire training set is

$$C = - {1 \over n} \sum_x [y_1 \log \hat{y}_1 - (1-y_1) \log (1-\hat{y}_1)].$$

So far, so good.

Cross-entropy loss for two-class neural networks with a single output

Now if we have a two-class classification problem, it's not actually necessary for the network to produce two outputs.  Alternatively, we could build a network with only a single output $\hat{y}$.  We could interpret this single output value as "probability" that the input instance should be labelled as class 1.  It follows that the "probability" that the instance should be labelled as class 0 is $1-\hat{y}$.  So, if $\hat{y}>0.5$, we'll label the input as class 1; otherwise, we'll label it as class 0.  This is the architecture used in the first web page you link to.

How should we measure the cross-entropy loss for this network?  Well, just replace $\hat{y}_0,\hat{y}_1$ with $1-\hat{y},\hat{y}$ and everything goes through unchanged.

A slightly tricky thing is that we need to replace $y_0,y_1$ with something.  What should we replace it with?  I suggest we replace it with $1-y,y$, where $y$ is a value that indicates the desired output: if the correct label is class 1, then $y=1$, else $y=0$.  Notice how this all works out nicely: if the correct label is class 1, then we get the distribution $0,1$; if the correct label is class 0, we get the distribution $1,0$.

Now plugging into the equations above, we see that the cross-entropy loss for a single instance $x$ is

$$C_x = - y \log \hat{y} - (1-y) \log (1-\hat{y})$$

(since we decided that instead of $\hat{y}_1$ we now have $\hat{y}$, and similarly for $y_1,y$).

As a result, the empirical loss for an entire training set is

$$C = - {1 \over n} \sum_x [y \log \hat{y} - (1-y) \log (1-\hat{y})].$$

This exactly matches the formula found in the first link you gave.

Bottom line

See how it all lines up and is consistent?  Basically, the cross-entropy is a well-defined notion in information theory; there is only a single definition of the cross-entropy.  In information theory, the cross-entropy is defined in terms of two probability distributions.

To use this idea to construct a loss function for a neural network, we construct two probability distributions (one based on the actual outputs from the neural network, the other based on the desired outputs), and then we apply the information-theoretic definition.  The exact way of defining those two probability distributions will depend on the architecture of the neural network, and in particular, on the number of outputs from the neural network.  When you have slightly different architectures, you'll get a slightly different equation for the cross-entropy loss function.  But the underlying idea is exactly the same: we apply the same information-theoretic cross-entropy slightly differently, to distributions defined in a slightly different way, so the equations look different on the surface -- but they're actually not as different as they might seem.

I hope this helps!


In this problem, the input size at each level of recursion is reduced by a factor of 2. At our topmost level, we have $cn$ for some constant $c$, but in the second level? In picturing a tree, our top most level (our leaf node) has one child, $cn/2$. This child has a single child of its own: $cn/4$, and so on.

To get the time complexity for our recurrence relation, we have to sum up the work done in each layer of the tree. You state that each layer does $O(n)$ work, but this is where your mistake is. Each layer does half the work of the previous layer. Therefore we end up with the summation $\sum_{i=0}^{n}\frac{n}{2^i}$. This sum is asymptotically equivalent to $O(n)$. Therefore, the result you reached using the Master Theorem is correct.


If you want to go deeper into cryptography and number theory, then of course you start here: Neal Koblitz, A Course in Number Theory and Cryptography.


Are there real lexers that use NFAs directly instead of first transforming them to DFAs?

I see only two applications of using an NFA (or rather its power automaton without writing it down) instead of a minimized DFA:

Homoiconic languages, where you may want to modify your lexer frequently
Strange syntax that may blow up your DFA like

identifier := [a-z][a-z0-9_]*
indices := [0-9_]{1,256} //up to 256 times
var := identifier "_" indices | identifier

If you take the last rule as a precedence, your lexer has to check whether an identifier contains "_" within the last 256 symbols and shorten it in this case.


Point Location Problem in Polygon in Repetitive Mode for a Simple Polygon

First question:

By (my interpretation of the) definition, a "central point" exists if and only if the polygon is star-shaped; this condition can be tested in $Θ(n)$ time.  So the only thing you can do is run this algorithm, apply division wedge if you find a non-empty kernel, and apply another algorithm if you find an empty kernel.


7 is the least number of questions that you can ask to guarantee to find the treasure.

the idea of binary search

Every time when we ask a question, we try to reduce the maximum number of unit squares left to search as small as possible. That is, try to cut the number as nearly to a half as possible. This is the idea as binary search.

the binary search on a row or column of cells

Each unit square of the given grid is called a cell.

Whenever we are left with some number of cells that are contiguous on the same row or column, we can simulate binary search on those cells with questions on some $n$ by $n$ squares. For example, suppose the treasure is among the cells marked by "t".

$$\begin{array}{|c|c|c|c|c|}\hline
&&&&\\\hline
\phantom{t}&t&t&t&t\\\hline
&&&&\\\hline
&&&&\\\hline
&&&&\\\hline
\end{array}$$

We can ask whether the treasure is in the following square marked by the question marks.

$$\begin{array}{|c|c|c|c|c|}\hline
&&&&\\\hline
\phantom{?}&?&?&\phantom{?}&\phantom{?}\\\hline
&?&?&&\\\hline
&&&&\\\hline
&&&&\\\hline
\end{array}$$

If the answer is yes, then we have restricted the range to search to the two "$t$"-cells to the left; otherwise, to the two "$t$"-cells to the right. Continuing this way, we can accomplish binary search on a row of cells or on a column of cells.

the full scheme

First ask whether it is inside the 6 by 6 square at the bottom right corner.

If yes, ask whether it is inside the 4 by 4 square at the bottom right corner.

If yes, ask whether it is inside the 3 by 3 square at the bottom right corner.

If yes, ask whether it is inside the 2 by 2 square at the bottom right corner.

If yes, we have 4 unit square left. Ask another 3 questions to find it.
Otherwise, it must be at one of the following cells.
$$\begin{array}{|c|c|c|c|c|c|c|}\hline
&&&&&&&\\\hline
&&&&&&&\\\hline
&&&&&&&\\\hline
&&&&&&&\\\hline
&&&&&&&\\\hline
\phantom{t}&\phantom{t}&\phantom{t}&
\phantom{t}&\phantom{t}&t&t&t\\\hline
&&&&&t&&\\\hline
&&&&&t&&\\\hline
\end{array}$$
Now choose the following square to ask to determine whether it is on the top row of that 3 by 3 square except the top left cell. If yes, we are left with 2 cells on the same row; otherwise we are left with 3 cells on the same column. Now start binary search.
$$\begin{array}{|c|c|c|c|c|c|c|}\hline
&&&&&&&\\\hline
&&&&&&&\\\hline
&&&&&&&\\\hline
&&&&&&&\\\hline
&&&&&&?&?\\\hline
\phantom{t}&\phantom{t}&\phantom{t}&
\phantom{t}&\phantom{t}&\phantom{t}&?&?\\\hline
&&&&&&&\\\hline
&&&&&&&\\\hline
\end{array}$$
Otherwise, it must be at one of the following cells.
$$\begin{array}{|c|c|c|c|c|c|c|}\hline
&&&&&&&\\\hline
&&&&&&&\\\hline
&&&&&&&\\\hline
&&&&&&&\\\hline
\phantom{t}&\phantom{t}&\phantom{t}&
\phantom{t}&t&t&t&t\\\hline
&&&&t&&&\\\hline
&&&&t&&&\\\hline
&&&&t&&&\\\hline
\end{array}$$
Now choose the following square to ask to determine whether it is on the top row of that 4 by 4 square except the top left cell. If yes, we are left with 3 cells on the same row; otherwise we are left with 4 cells on the same column. Now start binary search.
$$\begin{array}{|c|c|c|c|c|c|c|}\hline
&&&&&&&\\\hline
&&&&&&&\\\hline
&&&&&&&\\\hline
&&&&&?&?&?\\\hline
&&&&&?&?&?\\\hline
\phantom{t}&\phantom{t}&\phantom{t}&
\phantom{t}&\phantom{t}&?&?&?\\\hline
&&&&&&&\\\hline
&&&&&&&\\\hline
&&&&&&&\\\hline
\end{array}$$

Otherwise, ask whether it is inside the 5 by 5 square at the bottom right corner.

If yes, inquire an appropriate square to determine whether it is on the top row of that 5 by 5 square except the top left cell. If yes, we are left with 4 cells on the same row; otherwise we are left with 5 cells on the same column. Now start binary search.
Otherwise, inquire an appropriate square to determine whether it is on the top row of that 6 by 6 square except the top left cell. If yes, we are left with 5 cells on the same row; otherwise we are left with 6 cells on the same column. Now start binary search.

Otherwise, ask whether it is inside the 7 by 7 square at the bottom right corner.

If yes, inquire an appropriate square to determine whether it is on the top row of that 7 by 7 square except the top left cell. If yes, we are left with 6 cells on the same row; otherwise we are left with 7 cells on the same column. Now start binary search.
Otherwise, inquire an appropriate square to determine whether it is on the top row of the original 8 by 8 square except the top left cell. If yes, we are left with 7 cells on the same row; otherwise we are left with 8 cells on the same column. Now start binary search.

Why cannot we succeed with less than 7 questions?

Since after the first question, one of the yes or no answer will leave us at least $\min(64-5^2, 6^2)=36$ cells to search. Each question can cut the maximal number of cells to search at most in half. Since $2^5=32 < 36$, we need at least another $5+1=6$ questions to guarantee success.

Open problem

Does the scheme above reach the minimum average number of questions, assuming the treasure can be in any cell with equal probability?

I believe it does. However, I am not able to obtain a complete proof as it is not clear how to reduce the many cases to a manageable level.

Exercise

What is the least number of questions to guarantee to find the treasure that is in one of the cells of a 7 by 7 grid?


How to interpret the execution of distributed computation from time-space diagram?

Yes, it is ambiguous, and it is ok. A single space-time diagram can be linearized (collapsed into a compatible sequence of configurations and events) in many ways, potentially an exponential number of ways. E.g. imagine that you have 1000 nodes, and each of them performs a local operation. Obviously there's 1000! different ways to linearize this, because there are no inherent causality constraints in this situation.

It is not true that events in an execution are totally ordered. They are only partially ordered, using the partial order given by causality constraints (most of which are "a message is sent BEFORE it is received"). There are many total orders compatible with this partial order.


Calculate storage requirements for a data set

There are two ways to interpret your dataset generating process. The first produces all even numbers between $2$ and your bound: $2$, $4$, $6$, $8$, …; the second produces all powers of $2$ between $2$ and your bound: $2$, $4$, $8$, $16$, … An integer $N$ requires roughly $\log_{256} N$ bytes to store. Therefore, if your bound is $N$, the first interpretation will take about
$$ \sum_{k=1}^{N/2} \log_{256} (2k) \approx \int_1^{N/2} \log_{256} (2x) \, dx \approx (N/2) \log_{256} N \text{ bytes}. $$
The second interpretation, assuming $N=2^m$, will take about
$$ \sum_{k=1}^m \log_{256} 2^k = \sum_{k=1}^m (k/8) \approx m^2/16 = 4(\log_{256} N)^2 \text{ bytes}. $$


Link utilization of sliding window protocol

Link utilitization is about the steady state, i.e., what happens when you send a lot of data... not what happens at startup (at the very beginning of the connection).

Imagine you have a humongous file to send.  It takes far more than 10 frames to send the entire file.  Calculate the total time to send the entire file.  Calculate the total transmission time for that file.  Now divide.

Try doing that calculation again.  I think you'll see that you get a  different answer.  For instance, try calculating what happens if you send a file that is 1000 frames long... or 10,000 frames long.  How long does it take to send the entire file?  What fraction of that was spent in transmission time, as opposed to waiting for acknowledgements?


Complexity of determining spanning bipartite graph

In answer to your comment:

  By maximum spanning bipartite graph I mean same vertex set as given graph and the maximum number of edges possible. Is the complexity $O(n^3)$ correct for this algorithm? If so it would solvable in P time.

No, that problem, also known as Bipartite Edge Deletion, or Edge Bipartization, is:

  Given a graph $G = (V, E)$ and an integer $k$, is it possible to delete at most $k$ edges $E'$ such that $G' = (V, E \setminus E')$ is bipartite,

which is NP-complete.

It happens to be "equivalent" to the "vertex deletion" version of the problem, which is also known as Odd Cycle Transversal.


Hint: Use the time hierarchy theorem which shows, for example, that $\mathsf{DTIME}(n^3) \subsetneq \mathsf{DTIME}(n^4)$.


How do you prove two languages are equivalent using the definition of acceptance?

I don't think you need to use induction, a simpler case analysis will suffice, along with a couple of central observations about the new DFA $f(M)$:

$q_{f}$ is the new start state,
$q_{f}$ is also an accepting state,
$\delta'$ is almost exactly the same as $\delta$ (in a very specific way of course), and
there's no transitions into $q_{f}$.

From this you can argue what happens on input $x$ in two cases:

$x = \varepsilon$, and
$x$ is anything else.


Can the output value be solved and/or written as Taylor expansion?

It is better to use as parameters maxDepth-currentDepth, n, k. Call the resulting function $f_k(d,n)$.

When $k = 0$,
$$
f_0(d,n) = \begin{cases}
n & d = 0, \\
f_0(d-1,f_0(d-1,n)) & d > 0.
\end{cases}
$$
You can prove by induction that the solution is $f_0(d,n) = n$.

When $k=1$,
$$
f_1(d,n) = \begin{cases}
n & d = 0, \\
f_1(d-1,f_0(d-1,n)) + f_0(d-1,f_1(d-1,n)) & d > 0,
\end{cases}
$$
which reduces to
$$
f_1(d,n) = \begin{cases}
n & d = 0, \\
2f_1(d-1,n) & d > 0.
\end{cases}
$$
The solution is
$$
f_1(d,n) = 2^d n.
$$
When $k = 2$, using the preceding formulas we get
$$
f_2(d,n) = \begin{cases}
n & d=0, \\
2f_2(d-1,n) + 4^{d-1} n & d > 0.
\end{cases}
$$
Unrolling the recursion gives
$$
\begin{align*}
f_2(d,n) &= 4^{d-1} n + 2\cdot 4^{d-2} n + 2^2 \cdot 4^{d-3} n + \cdots + 2^{d-1} n + 2^d n \\ &=
(2^{2d-2} + 2^{2d-3} + \cdots + 2^{d-1}+2^d) n \\ &=
(2^d+1)2^{d-1} n.
\end{align*}
$$
Let us approximate this by $2^{2d-1}n$.

When $k = 3$, the preceding formulas show that
$$
f_3(d,n) \approx
\begin{cases}
n & d = 0, \\
2f_3(d-1,n) + 2^{3d} n & d > 0.
\end{cases}
$$
Unrolling the recursion gives
$$
f_3(d,n) \approx (2^{3d} + 2^{3(d-1)+1} + 2^{3(d-2)+2} + \cdots + 2^{3(1)+d-1} + 2^d)n \approx \frac{4}{3} 2^{3d}n.
$$
Continuing in this way, we find that up to constants, if $f_k(d,n) = \Theta(2^{r_kd}n)$ then $r_{k+1} = \max_{1 \leq \ell \leq k} (r_\ell + r_{k+1-\ell})$ (except for the base cases $k \leq 1$). For example, we have
$$
\begin{align*}
&r_0 = 0 \\
&r_1 = 1 \\
&r_2 = 2 \\
&r_3 = 3 \\
&r_4 = 4
\end{align*}
$$
and so on. Indeed, induction shows that $f_k(d,n) = \Theta_k(2^{kd}n)$. With more effort, we could estimate the hidden constant.


"Definition of NP via relations and quantifiers; not via NTMs"

I think I just realized, after finding a similar problem online, that this is asking to simply show that ${\sf NP}$ is closed under union. Can anybody give any insight into whether or not this is a proper solution, or if I'm missing anything? I mostly understand my answer, but I don't really know what I'm doing with the $c$ and $d$ constants... I put them in there because I feel like I'm going to need to.

  This question is asking to prove that ${\sf NP}$ is closed under union. It is the same as asking if $L=L_{1}\cup L_{2}$ is in ${\sf NP}$.

  Since $L_{1}$ and $L_{2}$ are both in ${\sf NP}$, it follows that they both have polynomial time verifiers $R_i(x_i,y_i)$ that evaluate to true when $y_{i}$ is a valid certificate/witness for $x_i\in L_i$, where $i\in \{1,2\}$.

  To show that $L=L_1\cup L_2$ is also in ${\sf NP}$, we need to construct a polynomial-time verifier $R(x,y)$. The certificate $y=\langle y_1,y_2 \rangle$ for $L$ will be an encoding of the two certificates $y_1$ and $y_2$ in such a way that $R(x,y)$ evaluates to true when $\displaystyle\bigvee_{1\leq i\leq 2} R_i(x,y_i)$ evaluates to true.

  Given that $R_{i}(x_i,y_i)$ for $i\in\{1,2\}$ are polynomial time verifiers with running time $O(c_i|x_i|^{d_i})$ for some $c,d\in\mathbb{N}$, $R(x,y)$ will have a running time of at most $O(2\cdot max(c_i)|x|^{max(d_i)})$, which is still polynomial. Therefore, $L\in {\sf NP}$.


Finding the frequency of each unique value of an attribute in a relation (RELATIONAL ALGEBRA)


What is the mathematical principle of buddy algorithm?

The buddy algorithm is just treating your memory of size $2^K$ as a binary tree where the root is the entire memory, and each node of size $2^k$ has two children which are the two equal size subblocks of size $2^{k-1}$.

The buddy system restricts you to only splitting a node into its two children (which are then the two buddies), or taking two buddies and coalescing them into their parent.  This restriction is put in place entirely to enable the cute/ingenious trick of identifying your buddy by flipping the $k$th bit.

Other than being cute, there is very little to recommend buddy systems as memory allocators.  More general systems that allow you to coalesce with any neighbor, even if it's not your buddy, are slightly more expensive to compute per deallocation, but result in much less internal and external  fragmentation in practice.


Can a regular expression be any string from the language described by it?

Your question is unclear. However "a language (that has strings of infinite length)" cannot exist. By definition a language only contains words of finite length.
Let $\Sigma$ be a (finite) alphabet and $\epsilon$ denote the empty word.
A language is a subset of $\Sigma^*$, where $\Sigma^*$ is defined as $\Sigma^* = \cup_{i=1}^{\infty} \Sigma^i$, $\Sigma^0 = \{ \epsilon \}$, and $\Sigma^i = \{xy : x \in \Sigma^{i-1}, y \in \Sigma\}$ for $i>0$.
As you can see, a string of infinite length does not belong to any $\Sigma^i$ and therefore it belongs to neither $\Sigma^*$ nor to any of its subsets.


What is the advantage of heaps over sorted arrays?

$\small \texttt{find-min}$ (resp. $\small \texttt{find-max}$), $\small \texttt{delete-min}$ (resp. $\small \texttt{delete-max}$) and $\small \texttt{insert}$ are the three most important operations of a min-heap (resp. max-heap), and they usually have complexity of $\small \mathcal{O}(1)$, $\small \mathcal{O}(\log n)$ and $\small \mathcal{O}(\log n)$ respectively if you implement a min/max-heap by a binary tree.

Now suppose instead you implement a min-heap by a sorted (non-decreasing) array (The case for max-heap is similar). $\small \texttt{find-min}$ and $\small \texttt{delete-min}$ are of $\small \mathcal{O}(1)$ complexity if $\small \texttt{insert}$ is not required in your application, since you can maintain a pointer $\small p$ that always points to the minimum element in your array. When the minimum element is removed, you just need to move $\small p$ one step to the next element in the array.

Dealing with insertion in a sorted array is not trivial. Given a new element $\small e$, we can use binary search to locate its position in the array to insert it. But the point is that if you want to insert it there, you have to move a lot of old elements (can be $\small \mathcal{O}(n)$) around to make a vacancy for the new element to reside. This is quite inefficient for most applications. You may also choose to re-sort the array after an element is inserted, this requires $\small \mathcal{O}(n\log n)$ time however.

The last point, how you implement a data structure really depends on your application. NO single implementation is best for all cases. Analyze your application, find out the most frequent operations, and then decide the appropriate implementation.


Given a Turing machine , How to construct a efficient boolean circuit?

I'm not sure whether this can be done. However, using oblivious Turing machines, we can get a circuit of size $O(T(n)\log T(n))$. According to the proof sketch of Theorem 6.7 in the draft of Arora–Barak, given a Turing machine running in time $T(n)$ we can construct a Turing machine running in time $O(T(n)\log T(n))$ in which the head movements only depend on $n$. Such a Turing machine is known as an oblivious Turing machine. This means that you only need to update one specific cell per time step, and the result is a circuit of size $O(T(n)\log T(n))$ (details left to you).


Computation of normalized first derivative in discrete case

For the first part of your question, the significance is just to guarantee that the vector $(\hat{x}'_t,\hat{y}'_t)$ has length $1$. This means that it tells us in which direction $(x_t,y_t)$ is changing, but not by how much. For example, $(\hat{x}'_t,\hat{y}'_t)=(1,0)$ tells us that $x_t$ is increasing and $y_t$ is constant; $(\hat{x}'_t,\hat{y}'_t) = (-\sqrt{2}/2, \sqrt{2}/2)$ tells us that $x_t$ is decreasing, and $y_t$ is increasing at the same rate.

The second part isn't something I know about, so I'll leave that for somebody else.


(Un)Decidability of disjoint decidable and undecidable sets

Hint: Suppose you could decide $A \cup B$. Using an algorithm for deciding $A$ and an algorithm for deciding $A \cup B$, can you decide $B = (A \cup B) \setminus A$?


Proof by induction
Basis. All complete oriented digraphs with two vertices have Hamiltonian path - it's obvious.
Induction step. Let's assume that complete oriented digraph $G_{n-1}$ with $(n - 1)$ vertices contains Hamiltonian path $(s, ..., t)$ from vertex $s$ to vertex $t$. We'll show how to build Hamiltonian path for complete oriented digraph $G_n$, which is constructed from $G_{n-1}$ by adding a vertex $p$.
Case 1. The $G_n$ has an edge $(p, s)$. The Hamiltonian path in $G_n$ will be $(p, s, ..., t)$.
Case 2. The $G_n$ has an edge $(s, p)$. Then we need to scan the Hamiltonian path $(s, ..., t)$, trying to find an edge $(v_{i-1}, v_i)$, such that the graph $G_n$ contains edges $(v_{i-1}, p)$ and $(p, v_i)$. There are two subcases:
Subcase 2.1. We can find such a pair - then the new Hamiltonian path will consist of three parts - $(s, ..., v_{i-1})$, $(v_{i-1}, p, v_i)$ and $(v_i, ..., t)$.
Subcase 2.2. We can't find such a pair - it means, that all the edges from vertices on the path $(s, ..., t)$ to the additional vertex $p$ are oriented to this vertex. The new Hamiltonian path will be $(s, ..., t, p)$.


The book is correct, because $b\leq 2n$, so you visit no more than $3n$ nodes, which is $O(n)$, and $b\leq 2n$ because no node has more than two leaves. You correctly say that $b$ grows proportional to $n$, which is exactly the key.

Just for clarity, Big-Oh notation means "grows proportional to, ignoring constant factors" (roughly), which is why we say that $3n\in O(n)$, even though one is a multiple of the other, and $6n^2+3n+42\in O(n^2)$ and $42e^n\in O(e^n)$, for example.

(actually, $O(n)$ means, "is not more than $cn$". For "is proportional to $n$", use $\Theta(n)$ instead of $O(n)$).


I am having trouble understanding (and implementing) logistic regression for classifying into three classes

How do you apply the weight vector to the sample to get a classification out of it for 3 classes (not just two).

If you have $n$ possible classes then you must train $n$ logistic classifiers on your training data, with each classifier producing as output the probability that a given sample is a member of the class the classifier is trained to recognize.  Once training is complete, to classify a new sample you let all the trained classifiers try to recognize it and accept the judgment of the classifier that produces the highest probability value.  This is known as one-vs-all or one-vs-rest classification and is a standard way to use binary classifiers to do multiclass classification.

The weights are applied the same way in classifying new data as they are when you're training the classifier.  You have a weight vector $\theta$ containing coefficients that when combined with a sample's feature vector $x$ yield an hypothesis value.  For linear regression $\theta^T\negthinspace x$ (expanded: $\theta_0 + \theta_1x_1 + \theta_2x_2 +$ ...) yields the hypothesis value.  For logistic regression $\theta^T\negthinspace x$ is used as the exponent in the logistic function to produce the hypothesis value:

\begin{equation}
h_\theta(x) = \dfrac{1}{1 + e^{-\theta^T\negthinspace x}}
\end{equation}
$e$ is the usual natural log constant $\approx 2.71828$.

$h_\theta(x)$ is the probability that the sample $x$ is a member of class the classifier recognizes.  Compute $h_\theta(x)$ for each classifier and accept the verdict of the classifier that produces the largest probability value.

  How exactly do you find the weight vector for logistic regression (using either gradient descent or newtons method, whichever is easier)?

Gradient descent works the same way for logistic regression as it does for linear regression.  You're still trying to minimize the cost function by iteratively nudging the weights to better values using partial derivatives of the cost function.  The hypothesis function is different for logistic regression, but the way it is used in gradient descent is the same.  Once you've written code to do gradient descent for linear regression, you should be able to just plug in a different hypothesis function and have it work for logistic regression.

Pseudocode for one iteration of gradient descent:

newtheta := theta;
learning_rate := 0.01;
for k := 1 to n
   sum := 0
   for i := 1 to m
      sum := sum + (hypothesis(x[i], theta) - y[i]) * x[i][k];
   end
   nudge := sum * learning_rate;
   newtheta[k] := newtheta[k] - nudge;
end
theta := newtheta;

x is a matrix containing your training data, one sample per row.

y is a vector containing the correct classification prediction for each sample, 1 if the sample is in the class, 0 otherwise.

m is the number of samples.

n is the number of features.

The idea is that you would repeat this process until you reach some minimum and acceptable cost (error) over the training set.


How to prove the NP-completeness of the ``Exact-3D-Matching`` problem by reducing the ``3-Partition`` problem to it?

I think this reduction should work:

Given a 3-PARTITION instance: $n$ integers $a_1,\ldots,a_{3n}$ and a target sum $B$;
mark each integer with an unique identifier $\hat{a_i}$; then build a collection of 3-elements subsets $C_j = \{ \hat{a}_{i_1}, \hat{a}_{i_2}, \hat{a}_{i_3} \}$ such that $a_{i_1}+ a_{i_2}+ a_{i_3} = B$ and $i_1 \neq i_2 \neq i_3$ (the collection has $O(n^3)$ elements).

The original 3-PARTITION problem has a solution if and only if there exist an EXACT-3D-MATCHING $C_{j_1}, \ldots, C_{j_n}$ that covers $S = \hat{a}_{1}, \ldots,  \hat{a}_{3n}$.

For example given $A = \{5,4,3,3,3,2,2,1,1\}, B = 8$ we build:
$S = \{5a,4a,3a,3b,3c,2a,2b,1a,1b\}$ and the collection of 3-elements subsets:

C1  = { 5a, 2a, 1a }
C2  = { 5a, 2a, 1b }
C3  = { 5a, 2b, 1a }
C4  = { 5a, 2b, 1b }
C5  = { 4a, 3a, 1a }
C6  = { 4a, 3a, 1b }
C7  = { 4a, 3b, 1a }
C8  = { 4a, 3b, 1b }
C9  = { 4a, 3c, 1a }
C10 = { 4a, 3c, 1b }
C11 = { 4a, 2a, 2b }
C12 = { 3a, 3b, 2a }
C13 = { 3a, 3b, 2b }
C14 = { 3a, 3c, 2a }
C15 = { 3a, 3c, 2b }
C16 = { 3b, 3c, 2a }
C17 = { 3b, 3c, 2b }

An Exact-3D-MATCHING is given by:

C1  = { 5a, 2a, 1a }
C6  = { 4a, 3a, 1b }
C16 = { 3b, 3c, 2b }

that also uniquely identifies a valid solution for the original 3-PARTITION problem.


Direct and Associate Cache - Offset, Index, and Tag

An 8-kB (8192 bytes) direct-mapped cache has 16-byte lines.
The system has 64-bit addresses numbered from 0 on the right to 63 on the left.
Which bits are associated with the offset, index, and tag?

Since a cache line is 16-byte long, it can be represented with $\log_2 16 = 4 \text{b}$, which is the number of bits required for the offset field.
The number of lines in the cache are $\frac{8\text{kB}}{16\text{B}} = 512$.
The index maps these entire lines; therefore, $\log_2 512 = 9\text{b}$ are required.
The tag field gets the rest, that is, $64-9-4=51\text{b}$.

A 16-kB (16384 bytes) 4-way set associative cache has 8-byte lines.
The system has 64-bit addresses numbered from 0 on the right to 63 on the left.
Which bits are associated with the offset, index, and tag?

As before, $\log_2 8 = 3\text{b}$ for the offset field.
Since the cache is 4-way associative, the number of sets are $\frac{16\text{kB}}{4\cdot 8\text{B}}=512$, which, again, requires $9\text{b}$ for the index field.
Finally, the tag is $52$ bits long.


What is the loop invariant of the following function?

Try finding a loop invariant of the following form:
$$
f(x,y) \leq n < g(x,y).
$$

For example, when $y=0$ you could choose $f(x,y) = x$ and $g(x,y) = x+1$, and in the end you want this invariant to imply $b^y \leq n < b^{y+1}$.

To get some intuition, note that if $n = b^k z + w$, where $0 \leq w < b^k$, then after $k$ iterations, we have $x = z$. This can help you formulate the loop invariant.


Why can't every computation be expressed in the style of MapReduce?

In MapReduce you take a big computation and split it up into many small computations that are done in parallel and that don't depend on one another. That way you can use many cores and if one calculation fails, you don't have to redo the entire job, just that small task.

But if you have a problem that can't be broken down into sub-problems that are independent of one another or dependent on some global state, then you are stuck with doing one long big computation and lose the benefits of MapReduce.


One $O(n^k)$ algorithm requiring only one $O(2^n)$ computation (for all n instances) is P or NP

If the "thing" is polynomial-size, then it's in P/poly, a class that has been studied intensively, although this is a very interesting subclass of it which I don't believe been studied. If you have an algorithm that falls into this subclass, I believe theoretical computer scientists might be interested in it.

If the "thing" can be exponential size, then the "thing" could just be a table of all the answers for the instances of size $n$, so all algorithms in EXPTIME would fall into this class. And in fact, this class would be equal to EXPTIME, since the algorithm R followed by A is in EXPTIME.


Ok here's my attempt 2 which won't construct the sequence of moves, but it at least proves what the optimal number of moves is and gives an indicator of how to construct the sequence. I'm addressing the inverse problem of turning "σ(1)σ(2)…σ(n)" to "12…n" using the moves "insert the current leftmost element somewhere different in the array", but they are equivalent problems because if we choose a prefix $\sigma(1)\sigma(2)\ldots \sigma(i)$ and right-cycle it, then we can reverse that by choosing the $\sigma(i)$ (now the leftmost point) and inserting it at position $i$. Likewise rather than start from the identity, we end at the identity.

Let $\sigma(i^*)$ be the right most element that is the beginning of an inversion, i.e., there exists $j>i^*$ with $\sigma(i^*)>\sigma(j)$ (if none exists then no moves are necessary because $\sigma$ is the identity permutation). For instance in 1 3 2 4 that would be 3 since it starts the inversion (3,2). And in 4 3 2 1 that would be 2.

Observation 1:  $\sigma(i^*+1)\sigma(i^*+2)\cdots \sigma(n)$ is sorted.

We must move all elements on the left side of $\sigma(i^*)$ to the right side of $\sigma(i^*)$. This is because we must correct the inversion and that can't happen until we perform a move with $\sigma(i^*)$ itself, which can't happen until $\sigma(i^*)$ is "uncovered" on the left side. While performing these hops over $\sigma(i^*)$ we can maintain the invariant that everything to the right of $\sigma(i^*)$ is sorted; this is just insertion into a sorted array.

So the number of moves necessary $= i^*$, since we hop everything to the left of $\sigma(i^*)$, and lastly move $\sigma(i^*)$ to its correct index.

Concluding note: to actually find the indices, we could use an order-statistic tree initialized with all values to the right of $\sigma(i^*)$. When we jump $\sigma(1)$ over $\sigma(i^*)$ we insert $\sigma(1)$ into the tree and call rank($\sigma(1)$); the rank can be used to compute the insertion index. Repeat with $\sigma(2), \ldots$.


A text-classifier that explains its decisions

Although it performs poorly on text classification tasks, if you want a clear explanation of the classification reasoning, a decision tree would be your best option as it provides clear rules for how an instance is classified.  A trace of the tree would provide the determining values and by analyzing the instances close to the root node, you might even be able to determine which attributes where more significant in the classification.

Another option would be to use a Naive Bayes classifier, which performs better for text mining tasks and would give you a comprehensible evaluation scheme based on probabilities that you could use to generate the "why" you're looking for, even providing an indication of which attribute values were more important than others in making the determination.

Support Vector Machines, specifically Sequential Minimum Optimization (SMO), seem to work well with these tasks and likewise provide indication of the values used to make the classification in the form of attribute weights and support vectors, but I think you may have a harder time making explicit how these weights and vectors influenced the overall classification decision.

Good luck with your project! Sounds very interesting.


Why is the running time for BFS $O(b^{d+1})$?

This represents a difference between the kinds of problems the CS algorithms community usually uses BFS to solve, vs the kinds of problems the CS artificial intelligence community usually uses BFS to solve.

The algorithms community typically is focused on the case where we have a finite graph, and where we're going to run some algorithm that probably visits everything in the graph.  We measure the number of vertices ($V$) and the number of edges ($E)$, and the running time is measured in terms of these two parameters.  Also, the algorithms community usually analyzes the case where we run BFS until every vertex in the graph has been visited.  If this is the goal, and those are the parameters we care about, the running time to visit every vertex is indeed $O(V+E)$.

The artificial community typically considers a different scenario: we have an infinite or very large graph, and we're not going to visit all of it; we're going to visit only a tiny fraction of the graph, only as much as necessary until we can find one node with a particular property (a target node / goal node).  Think of the state space of a game like chess, or the 15-puzzle, or something like that.  In addition, in the cases that typically arise in artificial intelligence, usually the portion of the graph that we're going to visit looks sorta like a tree: each vertex has on average about $b$ edges leading out of it.  So in this situation, a bound like $O(V+E)$ is not helpful: it is a valid upper bound, but it is extremely loose -- the number of states (vertices) you actually need to visit might be much smaller than the total number of states (vertices) that exist.  So, in AI applications, we usually want a better estimate of the number of states visited.  That's what leads to the $O(b^d)$ estimate.

Both upper bounds are valid, in the situation where they apply.  But the two situations they're focused on are very different.  It's the same algorithm (BFS), applied in two different contexts... and because of some differences in the characteristics, it makes sense to measure its running time differently in the two settings.


What is the only condition that would cause the Insert operation of a dynamic data structure to return a “data structure full” error?

I think this belongs more to StackOverflow than here.

As for your question, nothing in reality is unlimited. Computers have finite memory, finite storage. Words have a fixed (usually 32 or 64-bit) length, which might overflow. Or there might be some other engineering decision that limits the size of these data structures. Unlimited anything only exist in textbooks.


Splitting a set of points in the plane evenly and sorting it

This is not so hard to fix. First, calculate the median $m$. Then calculate the number of points strictly left of the median $\ell$. Take all of them from Py, and take the first $n/2-\ell$ points whose $x$ value is $m$ (where $n$ is the total number of points). These form the first half, and the rest of the points form the second half.


Communication between hardware components

I think what you're asking is how two machines or components, which run at different clock speeds/phases, can communicate. The short answer is that the receiver synchronises to the sender.
In low-speed communication channels (e.g. I²C), this can be achieved with an explicit clock line. Essentially, the sender has a separate wire that is the transmission clock. This is also generally the way that things work with parallel busses (e.g. where you send 8 bits over 8 wires plus a clock).
This doesn't work as well at high speed, because a small difference in the lengths of two wires can cause signals to arrive at different times. It also doesn't work over channels where there you don't or can't have more than one "wire", such as radio.
If you only have one "signal" (be it a single pair of wires, single radio frequency, or what have you), you are in the domain of line coding.
In that case, the receiver can synchronise by looking for edges in the source signal. There is an agreed-upon clock rate, which neither end can reproduce perfectly. But if the sender sends the message 00101001, for example, every time the bit flips from 0 to 1 or 1 to 0, that is something that the receiver can synchronise to.
Exactly how to synchronise clocks is a question for electronics engineers, who can explain techniques like phase-locked loops to you better than I can. It's a little subtle because the receiver can detect edges, but ideally wants to take its sample from the half-way point between the leading edge and the trailing edge, so there has to be some kind of delay involved.
But what if there are no edges? If the transmitter wants to send a whole bunch of zeroes, how does the receiver synchronise then?
The way around this is to design a code which does have transitions. RS-232, for example, specifies that each byte begins with a start bit, and ends with one or more stop bits, and there is a zero between the two frames, so every byte effectively has the bits "101" between bytes.
Medium-speed channels where retransmission is not an option (e.g. digital broadcast, satellite/spacecraft communication, or recording media such as optical disks) will often use error-correcting codes to achieve the same effect. Not only do you get error correction, the extra redundancy gives plenty of opportunity for clock synchronisation.
And then, you get into physical problems to do with the fact that you're communicating over physical wires or physical radio signals.
Over wires, for example, it's desirable to design a code with approximately the same number of 0 bits and 1 bits, a property known as DC balance. Real pairs of wires will act like a capacitor at high speed, and so if you have (say) more 1's than 0's, they will retain a charge and hence resist sending 1's. An example of a code designed for this is 8b/10b, which is used in a lot of modern high-speed serial communications such as HDMI, SATA, Gigabit Ethernet, and USB 3.0.
See this question from electronics.SE for further details.
Radio communication (e.g. Wi-Fi and cellular telephony) has its own problems that I can't really cover here, even if I understood it all. You have to protect against the Doppler effect, destructive interference caused by reflections, and so on.


Yes, both your answers are correct. Note that the language under consideration is regular, see wikipedia.

The first grammar is equivalent to this regular expression:
$$r_1 = a(ba)^* \mid (ba)^+.$$

The second grammar is equivalent to this regular expression:
$$r_2 = (ab)^+a \mid b(ab)^*a \mid a.$$

It's easy to prove those regexes generate equal languages $L(r_1) = L(r_2)$.


Understanding an algorithm for the gas station problem

The problem is in the condition for the first argument to min() in Equation (4) on p. 7.  It's currently

c(v) <= c(u) and g < d[u][v]

but it should be

(c(v) <= c(u) or v = t) and g < d[u][v]

to force arrival at t to have no gas left.  (Just as with my explanation below for the bug in Fill-Row(u, q), we are never interested in the cost of gas at t.  And as with there, another way to fix the problem would be to overwrite c(t) with 0 at the start of the algorithm.)

Fixing this mistake (in the published algorithm), combined with adding in the missing edges as I describe below (your mistake :-P), should be enough to get everything working.

One thing you're missing is that the graph G must be complete (first sentence of section 2, p. 4) -- and if it's not complete, any missing edges must be added, with the weights found by taking minimum path lengths in the graph.  So e.g. in your example graph, there should be (among others) an edge from 1 to 3 with weight 8 (corresponding to the path via 2), so that in fact GV[3] = { 0, 2 }.

I'm not sure whether that will completely solve the problem for you, but it should help.

Separately, I think there's a bug in the Fill-Row(u, q) algorithm on p. 6: this algorithm should treat the case q=1 specially, but it doesn't.  I believe it could be fixed by changing

if c(v) <= c(u)

on line 3 to

if c(v) <= c(u) or q = 1

to force any final leg to arrive at the destination empty.  (Intuitively, we should always disregard the price of gas at the final destination, t.)  Another way around this would be to overwrite c(t) with 0 at the outset.


Turing Machine that always returns a blank tape

While the tape is infinite, the amount of characters written on it is finite at any given point in time.

As sasha indicates in their comment, we usually assume that the tape is initialized with a special blank character. Given a Turing machine, you can modify it so that whenever it visit a cell having the special blank character, it replaces it with some other blank character, which it treats the same as the special blank character. Now at any given point in time you can find the (finite) extent of tape which has been visited, and clear it if you wish.


Automatic softcore configuration based on intermediate representation (IR) compiler output

Soft cores are still intented to be able to run different applications and have a general purpose, with of course some new instructions or peripherals usefull for the needs of what will run on the FPGA.

When wanting to optimize only one application from a common software programming language to run on a FPGA, there are already some compilers trying to do this, like recently reconfigure.io which aims to use Go: https://reconfigure.io/

If the project doesn't need to be able to load and run new programs in a general way, you're better to not use a soft core as it will waste a lot of resources on your FPGA.

If for example you're using the LLVM IR representation of a software, you could effectively optimize a soft core for it, but it's losing the aim of a core to be able to run multiple programs efficiently. If you're intending to run only one program in an optimized way, generating an hardware description of it (like what you're doing by using languages such as VHDL or Verilog) will be more efficient.


What parameter of optimizations, like time solving, can be used to show a phase transition in NP-hard problems?

There is no contradiction. NP-hard does not mean "large instances can't be solved quickly", rather, it means "there is an infinite number of instances that are hard". Large instances can be easy while small instances can be hard - it's the structure that counts and not size. Put differently, if a problem is NP-hard, it is believed that there is no algorithm which runs in polynomial-time (and is correct) on every instance. It is perfectly possible to have algorithms that are fast on particular instances.
So perhaps you misunderstood what phase transition means. Nevertheless, if you want to learn more about it, remember that it is relevant only for random instances.


Myhill-Nerode equivalence classes of $\{1^n0^n\}$

I think it makes sense to answer your subquestions out of order.

  Why they don't write $[1^n0^m] = \{1^n 0^m | n,m \in N^+\}$

They're supposed to be equivalence classes. $[1^n0^m]$ would break up lots of classes, and duplicate lots of the states from line 3.

  What does the Exponent $n+i-1$ mean?

Firstly, $n+i-1 \ge i$, so there are at least as many $1$s as $0$s.

Secondly, $n$ is the parameter which defines the class.

So $\left[1^{\mathrm{l}}0\right]_{\equiv \mathrm{A}}$ is the set of states which need $0^{l-1}$ to reach the accepting state.


Given $n$ items with $k$ properties, construct a query that contains between $\frac {n} 3$ to $\frac {2n} 3$ items

You are missing a condition – no two elements have exactly the same set of properties. Consider for example the extreme case in which no item has any properties – any query will get either all elements or none of them. We can also assume that $n>1$.

A simple iterative procedure constructs such a query. Let the properties be $P_1,\ldots,P_k$.

Let $x_1$ be the setting of $P_1$ which maximizes the number of elements satisfying $P_1=x_1$.
Let $x_2$ be the setting of $P_2$ which maximizes the number of elements satisfying $P_1=x_1$ and $P_2=x_2$.
And so on.

Denote by $N_i$ the number of elements satisfying $P_1=x_1,\ldots,P_i=x_i$. Thus $N_0 = n$ and $N_k = 1$ (by the missing condition). Let $i>0$ bet the minimal index such that $N_i < 2n/3$ (such an index exists since $N_k=1 < 2n/3$). Thus $N_{i-1} \geq 2n/3$. By construction, $N_i \geq N_{i-1}/2 \geq n/3$. It follows that $n/3 \leq N_i < 2n/3$.


Checkers algorithm - find the best last move in the game given the positions of all pieces

Some hints since I can't comment: I'd suggest trying to rotate the board by 45 degrees. Then your problem essentially reduces to your queen going right/upwards. The rest can then be solved with Segment Tree or Treap.


Let me assume that you are asking about basic type inference for $\lambda$-calculus with parametric polymorphism a la Hindley-Milner (it's not entirely clear from your question). I would recommend the Types and Programming Languages textbook by Benjamin Pierce as a general reference for this sort of thing. In there you can look up parametric polymorphism and Hindley-Milner type inference. These are the buzzwords you should be Googling. And when you do, it should be easy to find many resources.

P.S. You should not reduce before type inference. You should just do type inference on the original terms.

Supplemental: to find out whether you're correct, and since you're going to do Haskell in your course, why not ask Haskell about the types?

GHCi, version 7.6.3: http://www.haskell.org/ghc/  :? for help
Prelude> :t \g -> \x -> (g x) x
\g -> \x -> (g x) x :: (t1 -> t1 -> t) -> t1 -> t
Prelude> :t \z -> \x -> x z
\z -> \x -> x z :: t1 -> (t1 -> t) -> t

Yup, you were correct.


Is there a limit on the length of queries for the oracle?

It seems that the usual definition, following Ruzzo, Simon and Tompa, is as follows. The oracle tape is write-only but has no space constraints. It is erased after each oracle call. In addition, if the machine model were non-deterministic (which is not your case), then the oracle calling process would have to be deterministic.


What's the most efficient way to print all paths from root to leaves in a directed graph?

In a directed graph with $n$ vertices there may be $(n-2)!$ different simple paths (paths without cycles) between any two vertices. Just consider a complete directed graph. So its running time is $O(n!)$ and hence it is impossible to solve the problem in $O(n\log{n})$.


Minimum number of edges for $n$ vertex graph to be connected

Likely they mean that if a graph has as at least $f(n) = {n-1 \choose 2}+1$ edges, then it is connected. For instance, $f(5) = 7$, and any 5-vertex graph is connected with 7 edges. However, as you observe, it would also be connected with a smaller number of edges (that is, with $n-1 = 5-1 = 4$ edges).


Difference between "sort" and "universe"

Sort is (typically, though see Pure Type Systems) a meta-level concept and universes are an internalization of a particular case of a sort.  The second chapter of Bart Jacobs' thesis covers a fairly general case of how sorts interact with a language.  I'll be roughly following that.

I'll use the terminology $T$ is a type of sort $s$ if $T : s$ and $e$ is a term of type $T$ if $e : T$, so terms are always "grandchildren" of some sort, and types are always "children".  $s$ is a sort if we can introduce variables of a type of sort $s$ into the context, i.e. $$\frac{\Gamma\vdash A : s}{\Gamma, x:A\vdash x:A}$$

If there were no dependencies between sorts, we could almost say a sort was an index into a collection of contexts, which leads to the notion of dependencies between sorts.  We say $s_2$ depends on $s_1$ when types of sort $s_2$ can contain terms of sort $s_1$, i.e. if $$\frac{}{\Gamma\vdash A:s_1\qquad \Gamma,x:A\vdash B:s_2}$$ then it can be the case that $x$ occurs free in $B$.  Without the dependency it would necessarily be the case that $x$ was not free in $B$.

That's all that is required to be a sort.  Many additional features can be specified such as the existence of function types of sort $s$ built out of other types of sort $s$.  One feature we can add (called axioms in Jacobs' thesis), is the fact that one sort is a type of another sort, i.e. $s_1 : s_2$.  This internalizes the types of sort $s_1$ as terms of sort $s_2$.  If we want to embed $s_1$ into $s_2$ so that terms of $s_1$ are terms of $s_2$, we can add what Jacobs calls an $(s_1,s_2)$-inclusion.

A universe is then a sort that is closed under all the operations in the language.  A hierarchy of universes means that we further internalize the types of every universe and have an embedding of each universe into (at least) the next higher universe.  Closure typically includes the following rule arising from dependent products: $$\frac{\Gamma\vdash A:\mathbb{U}_n\qquad\Gamma,x:A\vdash B:\mathbb{U}_n}{\Gamma\vdash(\Pi x\!:\!A.B) : \mathbb{U}_n}$$
For this to be interesting, $x$ has to occur free in $B$ meaning $\mathbb{U}_n$ depends on $\mathbb{U}_n$.  Cycles of dependencies between sorts are characteristic of dependently typed languages.

So a (hierarchy of) universe(s) is a (hierarchy of) sort(s) with a variety of additional features many of which imply additional dependencies.  For contrast, we can consider sorts (potentially in addition to a hierarchy of universes) that aren't universes (or at least aren't the universe, i.e. we could have multiple universe hierarchies).  One example is separating compile-time calculation from run-time calculation as in Higher-order ML.  In this we'd have a sort that represents compile-time terms in addition to a sort for run-time terms and a dependency allowing run-time terms to depend on compile-time terms.  Another example is Cloud Haskell's Static type constructor.  We can view it as part of a $(\square,*)$-inclusion where sort $\square$ classifies "static" terms which are terms which only depend on terms bound at the top level.


Proving $L = \{ w : w \neq w^R \}$ over $\Sigma = \{0,1\}$ is CFL

Use induction.

For instance:

Define $\mathcal{L}_i(G) = \{ w \in \mathcal{L}(G) \mid |w| = i \}$ for $i \in \{ 0, 1, 2, \ldots \}$.
Prove that for all $w$ and $i > 1$, $w \in \mathcal{L}_i(G)$ if and only if $\exists x \in \Sigma, v \in \mathcal{L}_{i-2}(G) : xvx = w$.


It's true that if you consider a long sequence of operation, it's possible to point at one operation and say "that one operation might take a really long time" (e.g., $O(n)$ time).  That's in some sense the essence of amortized analysis.  An amortized running time of $O(\log n)$ means that the average time per operation is $O(\log n)$, but it's still true that there might be a rare operation here and there that take much more (though it will be compensated by most operations taking less time).  Amortized running time bounds are only useful if you're willing to accept that limitation.

If you want worst-case running time bounds, then don't use a data structure that only offers amortized worst-case bounds; use a different data structure, one that offers worst-case running time bounds.  For instance, self-balancing binary search trees (like red-black trees, AVL trees, etc.) offer worst-case running time guarantees.  If amortized running time bounds aren't good enough, maybe splay trees aren't the data structure for you.


On satisfiability for 2-variable FOL being NEXPTIME-complete

Regarding your first question: I haven't read the paper, but I guess that the proof of the second lemma is by a polynomial time reduction from a generic $\mathbf{NEXPTIME}$-hard problem. This establishes $\mathbf{NEXPTIME}$-hardness. Membership in $\mathbf{NEXPTIME}$ is by the first lemma. Regarding the second question, your guess is correct.


Hint: Let the vertices be the digits $0,\ldots,9$, and let the given integers be the edges.


How to minimally extend a digraph such that all nodes are on a cycle?

Find all the strongly connected components (SCC) of the original
graph.
Replace each SCC by a single node - the resulting graph $G'$ will be acyclic.
Find all the sources and sinks in $G'$ - let $m$ will be a number of sources, and $n$ - a number of sinks.
Match sinks with sources using algorithm by Eswaran and Tarjan (see here), corrected by Raghavan (see here), then add $max(m,n)$ edges for all the matched (sink, source) pairs.
Replace each node, representing SCC, by this SCC.

This approach will give you a strongly connected graph provided that the original graph is connected. Your requirement to have all the nodes belonged to some cycle is more weak - for example, a set of SCC's, not connected at all or connected by single edges, satisfies your goal definition.

However, it's unclear if this more weak requirement will allow you to decrease the number of additional edges compared to the number of additional edges, given by the algorithm, described here.


Are intersection and union redundant? Possibility to get smaller output without negation?

Regarding the first question, as you have said in the comments, you can define a relational algebra intersection with other relational algebra operators. Anyway, relational-algebra union is usually considered a relational algebra basic operator (that cannot be defined with other relational algebra operators).
Regarding monotonicity, we say that a query is monotone if the results of the query increases with the size of the database. More formally, a query $q$ is monotone if and only if, for any given database states $D_1$, $D_2$, where $D_1 \subseteq D_2$, we have $q(D_1) \subseteq q(D_2)$.
For instance, a monotone query might be: "All departments with at least one employee". Indeed, if you have a database state $D_1$ with 1 department with at least one employee (e.g. 'MarketingDepartment'), you know, for sure, that any $D_2 \supseteq D_1$ will still bring you such 'MarketingDepartment', and possibly more (since $D_2$ might have more departments with at least one employee).
A non-monotone query might be: "All departments with NO employee". Indeed, if you have a database state $D_1$ with 1 department with no employee (e.g. 'MarketingDepartment'), you can build a database $D_2 \supset D_1$ where 'MarketingDepartment' $\not\in q(D_2)$. Indeed, in $D_2$ you can add some employee for the 'MarketingDepartment', making 'MarketingDepartment' not satisfy your condition.
In relational-algebra, non-monotonic queries are defined through the set-difference operator (in the previous case: Department $\setminus$ $\pi_{dept}$ Employee). If a relational-algebra query has no set-difference operator involved, it is mononote.


Need help understanding which values can be inserted into a specific node in a binary tree

Binary trees can serve many different purposes. They don't necessarily need to be in an ordering like such.

Note that below, I hid key parts of the solution. You can view them by hovering over with your mouse, but I encourage you to try to solve it using clues from my response without seeing the actual answer.

For your particular problem, it appears that the ordering of the tree is such that all nodes to the 'right' have a value greater than our root (global or local root, doesn't matter) and all nodes to the 'left' have a value less than our root.

With this in mind, $u$ must be greater than our root node, so

  $16$

is ruled out. Then, by taking $u$ to be our next (local) root node, $u$ must be greater than the maximum value of its left subtree and $u$ must be less than the minimum value of its right subtree. From this, we can see that

  $28 < u < 50$.

This rules out

   $24, 51, 58$.

Therefore, the answer to your problem is

  $36, 45, 49$


Finding the k-th smallest rational number efficiently

It is perhaps more natural to consider the set $S$. Let us further consider the case $A = B = n$ and the set $S \cap [0,1] = \mathcal{F}_n$, the $n$th Farey sequence; if we know $|\mathcal{F}_n|$ and can solve the problem for $\mathcal{F}_n$ then we can also solve it for the entire $S$. The set $\mathcal{F}_n$ has size $\Theta(n^2)$.

The fastest algorithm known for finding order statistics (i.e., the $k$th smallest element) in $\mathcal{F}_n$, due to Patrășcu and Pawlewicz, runs in time $\tilde{O}(n^{2/3})$. This is much slower than the complexity you're interested in, $O(\log n)$.

It is possible that considering the multiset instead of the set makes the problem easier.


Big O notation for finding duplicates in a list using binary search

I have two different points:

As for complexity of your algorithm I believe this still to be O(N*log N). Consider the first half of the checks. For each check you do a binary search over the list of the size at least N/2 so it is O(log (N/2)) but given that log (N/2) = log(N) + constant it is just O(log N). And you do at least N/2 such checks. So it is O(N*log N)
If your list is not sorted, just sorting it to use binary search will take at least O(N*log N) so this is the lower bound anyway. And if it is sorted, your algorithm is very inefficient. You can do it in just O(N) by comparing each 2 sequential elements in the list (duplicates obviously have to be next to each other in a sorted list).


Average prefix code length of every 4-sized frequency vector is bounded at 2

Hint: The code generated by Huffman's algorithm has the minimal average word length, and in particular is at least as good as any other code. Show that there is a "universal" code (of length $n=4$) whose average code length is exactly $2$ on any distribution.

The more general theorem states that the average word length for a code over an alphabet of size at most $2^a+b$ is at most $a + \frac{b}{2^a+b}$; to get the best bound for a specific $n$, write $n = 2^a+b$ with $a$ as large as possible. When $b=0$ there is even a universal code as in your particular case.


How To Best Learn About Algorithms In Depth

I learned about algorithms in a university course years ago. But if you are to do algorithms using a book, then you need a good one. Two books stand out for me as the way to get into algorithms:

The Algorithm Design Manual by Steven S. Skiena
Introduction to Algorithms by T Cormen, C Leiserson, R Rivest and C Stein

The first is perhaps more of a hands-on manual, whereas the latter is more like the bible, but with proof.

The strategy you could follow would consist of reading, doing the theoretical exercises, and then implementing as much as you can, focusing on algorithms/problems you find interesting or challenging or both.  Thus, try to cover all aspects of algorithms, not just implementing them. This will include studying their time and space complexity and proving their correctness. The study of algorithms is more than just implementing algorithms.

After you've gained enough experience, start specializing. If you become interested in Computational Geometry or non-blocking algorithms, for example, then start exploring books and research papers in this area.

Specialization is good, but it is also good to sample techniques from other areas, so reading broadly about algorithms (and implementing such algorithms) is a good way of maintaining a broad skill set.

EDIT:
After going through the introductory algorithms, you may consult books like Randomized Algorithms by Motwani & Raghavan or Approximation Algorithms by Vazirani. These books are a survey (and to some extent, a good learning exercise in mathematical techniques) in more advanced algorithm design techniques. They also broaden your insight into many other fields in CS like Graphs and Networks, Data Structure design and Optimization.


Is this method of proving non-regularity is equivalent to pumping lemma?

Here is how your method of proof works on the (regular) language $\{0^2,0^3,0^5,0^7\}$. I tried to construct a DFA for this language – the DFA accepting all strings, but while it accepts $0^2,0^3,0^5,0^7$, it also accepts other strings. What when wrong?

To prove that a language is not regular, we have to show that it is impossible to construct a DFA for it. Having tried and failed is not enough – maybe it's just difficult? For example, people believe that P$\neq$NP, but so far we haven't been able to prove this. Does this show that P=NP?

How, then, can we show that a language is not regular? One way is to construct the "canonical" DFA, and this leads to the Myhill–Nerode criterion (look it up). This method is complete in the sense that if a language is not regular, then you can prove this using this method.

Another technique is the pumping lemma, which is popular for historical reasons. The pumping lemma is not complete: there are irregular languages which satisfy the conditions of the pumping lemma, and so the pumping lemma cannot be used to prove that they are not regular.

There are other techniques as well, for example using closure properties of regular languages, or using structure theorems. Your specific language is a unary language (a language over an alphabet with size 1), and we have a complete structure theorem for these languages, which can be used to show that your language is not regular.


I just realized that my question is irrelevant to making the algorithm work.
I mixed the radial and angular atributes of the points and mistakably thought them to need to be based at the same origin, but that's just confusing semantics.
Actually, the radial origin decides on the order of insertion of points and if set correctly, ensures no new point will apear inside an existing triangle, and the angular origin only helps to find the projection of a new point on the envelope (frontier / convex-hull in the case of [2]), so the angular origin indeed needs to be inside the seed envelope, but the radial origin need not. Moving the angular-origin inside the seed envelope will affect the actual progression of the algorithm, but will not affect correctness.

This makes things a lot easier - taking arbitrary point of the set, or somewhere in the plane and find the 2/3 points closest to it will work in general position, but it may result in a colinear triplet.
Following [2] and taking a point from the set, its nearest neighbour, and a 3rd point that creates the smallest circumcircle with them will always work as this is a delaunay triangle (nearest-neighbours are always delaunay edges, and the 2 triangles based on this edge have to create an empty circumcircle, so one of them has to be the smallest) which makes the circumcircle empty of other points, so using its origin as the radial origin is correct.

To do this for integers, we may take the second approach and round the result (checking for super-edge-cases), or take the first approach which is more straight forward for integer radial origin, and restart if we find a colinear triplet, or when the triangle is too obtuse to contain an integer point in its interior.
The last condition is only for making the algorithm fully integral (e.g for machines wihout Floating Point Arithmetics), but using precalculated float pseudo-angles [3] (avoiding use of slow atan2) and comparing them later in the binary search (tree), might be faster than using fully integral orientation test by demand.

pseudo-angles


Find the bounding box of the polygon.  Find all corner points within the bounding box.  Iterate over the resulting corner points, test each one to see whether it is within the polygon, and if not, throw it away.

Or, implementing your own code to do corner point detection.


How to find i-th root of n whose remainder is the smallest?

You want to write $n$ as $b^x + r$ with $x,r \ge 0$ and $b \in \{2, \dots, 2^{31} - 1\}$.

Since you're asking for the asymptotic complexity and the base $b$ is in a set of constant size, you can just focus on a single value of $b$.
The exponent is then $x = \lfloor \log_b n \rfloor$ and can be found using $O(\log \log n)$ operations (search for the first $y$ such that $b^y > n$ by trying $b, b^2, b^4, b^8, \dots$, where each term is the product of the previous term by itself, then binary search for the last $x \in \{y/2, \dots, y\}$ such that $b^x \le n $).

The above procedure already gives you $b^x$, from which you can compute $r = n - b^x$. Return the triple $(b, x, r)$ that minimizes $r$.

If the time of each arithmetic operation is constant, the above requires $O(\log \log n)$ time. If each arithmetic operation takes logarithmic time in the value of its operands, then the complexity is $O(\log n \cdot \log \log n)$.


How do you produce a CNF from a circular graph with colouring?

The easiest way is to solve the more general problem for (undirected) graphs and an arbitrary number of colors. Given a graph $G = (V,E)$ and a set of colors $C$, the formula has variables $x(v,c)$ for every vertex $v \in V$ and every color $c \in C$. There are clauses of three kinds:

For each vertex $v$, there is a clause $\bigvee_{c \in C} x(v,c)$.
For each vertex $v$ and each pair of colors $c,d \in C$, there is a clause $\lnot x(v,c) \lor \lnot x(v,d)$.
For each edge $(v,w)$ and each color $c$, there is a clause $\lnot x(v,c) \lor \lnot x(w,c)$.

In words, these clauses state that:

Vertex $v$ gets some color.
Vertex $v$ gets at most one color.
Vertices $v,w$ (which are connected) don't get the same color.


Where is the problem in this proof that deciders are no stronger than LBAs?

You seem to be mixing some concepts. Over an empty input alphabet, there are no decision problems, so as a model, Turing machines with empty input alphabets are not interesting.
It is true that the problem of deciding whether a given TM accepts the empty word is interesting (and undecidable), but it's not the same thing as having an empty input alphabet.
So the "reductions" you describe are not exactly reductions in the formal sense, just some translations between models.
As for a concrete problem with your argument: first, an LBA runs on a fixed portion of the tape which is prescribed by the input length. If you have an empty input, the LBA is not allowed to touch the tape, so it can't really do anything. An LBA doesn't just mean that the space is linear in the input. So you can't manually add the "m" input cells. This breaks your argument.
But also note that the definition of the function $f(x)=x+m$ is a bit strange, since on an empty input alphabet, you always have $x=0$.


In the RAM machine model, operations on "machine words" cost $O(1)$, where a machine word has width $O(\log n)$ bits, $n$ being the length of the input (in bits). This reflects the instruction sets of real world CPUs, as mentioned in the other answers.

While the RAM machine model makes sense for many algorithmic tasks, it is not a good fit for large integer arithmetic, since in practice the machine word is fixed while the integer length is growing. Instead, one usually measures bit operations. Shifting an $m$-bit integer by $c$ bits takes $O(m+c)$ bit operations.

These issues are explored in a paper of Martin Fürer, the inventor of the fastest known integer multiplication algorithm (which is also the fastest known integer division algorithm).


Parallized algorithm for getting the frequencies of numbers in an array

It is common problem in parallel computing. Many parallel framework have "reduction operator" for such processing. Idea is simple.
Use separate local copies of F[A[i]] in each threads. Calculate frequency in parallel for each sub-array block in parallel. Now since each thread is updating only its local copy of frequency array F[A[i]], no mutex is required. After the completion of all threads, join all the per thread F[[A]] array's into a single application array, i.e., reduce. You will get almost O(n/p) time complexity. The actual time complexity will depend on Size of your array (larger, the better) and the number of threads (creating and joining threads takes time).


Satisfiability where each clause contains almost all variables

Suppose every clause contains all but c variables. I think the problem is in $P$, which I believe can be seem from your example with $c=0$. In your case, every clause "forbids" exactly one satisfying assignment. Suppose we have $n$ variables, then the formula is satifiable when there is at least one satisfying assignment that remains, and thus, when not all $2^n$ possible assignments are forbidden.

I believe we can generalize this idea: keep a list of all such "forbidden" assignments: for each clause, add the $2^c$  assignments it forbids to the list (the opposite of the clause, with all possible extensions to the missing variables).  If in the end, the list contains all $2^n$ assignments, the formula is unsatisfiable. Else, it is satisfiable

Note that this is polynomial time, if there are $m$ clauses, the list contains at most $2^c \cdot m$ forbidden assignments.


How do we pick and switch hash functions from a universal family?

You need to decide what sort of resilience you are expecting from your hash function. While it is true that once picked, your hash function does not change (and in a sense "the rest of the family doesn't exist") but you're ignoring the crucial part of picking the function at random.
Suppose that $\mathcal{H}\subseteq U^{[m]}$ is a universal family, $h$ is chosen uniformly at random from $\mathcal{H}$, and is subsequently used to hash elements from $U$ into $m$ cells via chaining. This guarantees that regardless of what is the current content of the table, if the load factor is $\alpha=n/m$, then for every $x\in U$ (note the worst case analysis, as opposed to the average case analysis in the simple uniform hashing case) the expected search/insertion time for $x$ is $O(\alpha)$, where the expectation is taken over the initial choice of $h$ (this is the only place where randomness occurs). This remains true regardless of how many operations were done since the initialization, the random choice of $h$ guarantees low expected search time for all inputs.
Switching might come to mind if you are looking for robustness against certain types of adversaries. If the entire problem was handling a user giving you inputs and hashing them to a table, then everything's fine. This changes if you are looking at the problem of an adversarial user with more access, say e.g. that he might learn the hash value of some elements (which happens in real world attacks based on response time analysis). In that case, the adversarial user might be able to recover $h$ and then send you tailored inputs that will cause high search time. This relied on the adversary having a richer interface than just being able to send arbitrary values (which alone, as we saw above, can't cause problems). Now you're entering the world of cryptographically secure hash functions, and here some switching mechanism might be of use. This requires an entirely different formalization, and to say something interesting about parameters such as switching intervals we need to be clear about what sort of robustness we want to achieve.


What's the worst case complexity of Robert W. Floyd's cycle detection algorithm?

In this answer, I show that $x_i = x_{2i}$ iff $i \geq \mu$ and $i$ is a multiple of $\lambda$. In particular, this will happen for some index $i$ in the range $\{\mu,\ldots,\mu+\lambda-1\}$. This shows that the algorithm runs in time $O(\mu + \lambda)$.


Potential method for dynamic binary search

What about this potential function

$$\Phi = \sum_{i=0}^{k-1} n_i \cdot 2^i \cdot \left((k-1) - i \right),$$

where $k = \lceil \lg(n+1) \rceil$ (please check the details related to the stuff of $\lg$ and $\lceil \rceil$).

That is, each element in "depth" $n_i (i = 0, \cdots, k-1)$ has its "individual potential" $(k-1) - i$. The intuition is the higher the element is, the more potential it has and the higher price you pay to move it down (until the bottom). The whole potential of the data structure at any state is the sum of the potential of its all elements.

With this potential function, the amortized cost for the insertion of an element which does not cause any merge (i.e., the element is inserted into the empty subarray $A_0$) is

$$\hat{c} = 1 \quad (\text{actual cost for creation}) + (k-1) \quad (\text{increment of the potential function}) \\ = k = \lceil \lg(n+1) \rceil.$$

On the other hand, the amortized cost for the insertion of an element which causes $t$ merges is (please check the computation):

$$\hat{c} = 1 + \sum_{i=1}^{t} 2^t - (\sum_{i=0}^{i=t-1} 2^i (t-i)) \quad (\text{the potential decreases}) \\ = (2^{t+1} - 1) - (t(2^t-1) - (2^t t-2^{t+1} +2)) \\ = t + 1 \le k = \lceil \lg(n+1) \rceil.$$

Therefore, the amortized cost for each insertion is $O(\lg n)$.

Explanation for the decrement of the potential function $\sum_{i=0}^{i=t-1} 2^i (t-i)$:
First, each subarray $A_i,i=0,⋯,t−1$ contains $2^i$ elements. Secondly, each element in $A_i$ will be moved down to the $t$-th level subarray $A_t$, decreasing its potential by $t−i$, i.e., from $(k−1)−i$ to $(k−1)−t$. Summing them up, we obtain the total decrement of the potential function.


B+ trees, like all B-tree variants, are typically page-structured. A page size is chosen (which is a multiple of the disk page size and the CPU's page size). Each node or leaf is a page in size. Organising the tree this way eliminates external fragmentation.

We pay for it with internal fragmentation.

Each node and leaf can have a variable amount of data stored inside it. So for if a node is not full, some of that page is unused. When we say that a B+ tree has 67% occupancy, this means that 1/3 of the allocated space is unused memory at the end of pages.


An acyclic graph, usually known as a forest, is a collection of disjoint trees. It is only a tree if it is connected. Since trees are 2-colorable (for the same reason you mention), it follows that forests are also 2-colorable.

It is also possible to reduce the general case to the connected case: given a forest, you can join the different connected components to form a tree. The resulting tree is 2-colorable, and the same 2-coloring is also valid for the original forest.


Is there a term for these "descendancy" subgraphs of directed acyclic graphs?

Kind of. But we're going to use the usual computer sciency way of describing this, using the language of binary relations.

You're probably already familiar with binary relations, like equality $=$, less-than-or-equal-to $\le$, subset $\subseteq$, and so on. In general, a binary relation $R$ over a set $X$ is a subset $R \subseteq X \times X$. If $(x,y) \in R$, we denote this as $xRy$.

If $\forall x \in X, xRx$, then $R$ is reflexive. The relations $=$ and $\le$ are reflexive, but $\lt$ is not.

If $\forall x, y, z \in X, xRy\,\wedge\,yRz \Rightarrow xRz$, then $R$ is transitive. Plenty of relations are transitive, including all of the ones given above. If $x \le y$ and $y \le z$, then $x \le z$.

Given a relation $R$, the reflexive transitive closure of $R$, denoted $R^*$, is the smallest relation $R^*$ such that $R \subseteq R^*$, and $R^*$ is reflexive and transitive.

Interpreting your graph as a binary relation (since the edges don't really seem to matter to you, you're only interested in the set of vertices), this is exactly what you want: $xR^*y$ if and only if $y$ is a "descendant" (by your meaning) of $x$.

When looking at the literature, you will need to know one more piece of notation: the transitive closure of $R$, denoted $R^+$, is the smallest relation $R^+$ such that $R \subseteq R^+$, and $R^+$ is transitive. Algorithms for computing the transitive closure and the reflexive transitive closure are related, since they differ only by the "diagonal" entries: $R^+ \cup \left\{ (x,x)\,|\,x \in X \right\} = R^*$.

There are several standard algorithms for computing the RTC of a relation. If the relation is dense, in the sense that it's feasible to represent it as a bit matrix, the Floyd-Warshall algorithm is one of the fastest practical algorithms; its run time is $\Theta(|V|^3)$ in theory, but the inner loop is quite fast on real hardware given that it it a bunch of bit vector manipulations.

For sparse relations, see Esko Nuutila's thesis, which contains a very good survey as well as some more recent algorithms.


Function to generate longer bit-sequence from shorter sequence with certain properties

Let $\pi$ be a random permutation on $\{1,\ldots,1024\}$, and let $K$ be a random bit string of length 1024 bits. The following mapping seems to satisfy your needs (with probability close to 1):
$$
A \mapsto \pi(A^{32} \oplus K).
$$
In particular, changing $b$ bits of $A$ will result in changing $32b$ bits of the result.

If you are OK with changing more than 32 bits, then you can take a random sparse affine function, that is the function whose $i$th bit is an XOR of a small number of bits of $A$ chosen at random, XORed with a random bit.


I'm not entirely sure if I understood the question the way it was intended, but what computers do is that they operate on electricity, so they don't have two discrete logical values $0$ and $1$ per se. What they do have is electricity with voltage, and they are made to operate as if there were two logical values $0$ and $1$ if the voltage at a gate is below a certain threshold (for $0$; for example, below 0.5mV) or above another threshold (for $1$, for example, above 2.5mV) with a reasonable distance between those two threshold values. Anything in between will give the processor undefined behaviour.

What processors then do is operate on the logical values $0$ and $1$ that were abstracted from the continuous voltages. The hardware implements functions using boolean logic, meaning functions of the kind $\{0,1\}^n \to \{0,1\}^m$. For an introduction to how these things are implemented in hardware, see for example the material found here. It starts out with boolean logic, and by chapter 4 p. 3 everything needed to build an adder (meaning a circuit that implements addition) has been explained. It's a total of 23 pages to read until then, so you can decide if you would like to spend the hour or two it takes to read through it (and another hour to reread for understanding).

The circuits that don't have a way to store values are called combinational circuits, and those are used to implement the most basic functions in hardware (for example, addition, multiplication, logical operations like OR, AND, XOR for binary vectors). Circuits that can store values are called sequential circuits, and they utilize techniques where the input of gates are interdependent, and the circuits have well defined stable states. For an introduction to that, see for example here. Don' be disappointed if you can't quickly grasp that - I for one had a bit of trouble with comprehending sequential circuits initially.

For a small summary on how circuits are built from the elemental building blocks called transistors, see for example here. It only summarizes the working of transistors without all the electromechanics that go into it. Basically a transistor has a source (input) where we can apply a voltage, a gate where we can apply a voltage to control whether the input is inverted or not, and a drain (output). Depending on what type of transistor we use, the gate allows transmission from source to drain if we apply a $0$ (for nMOS transistors) or a $1$ (for pMOS transistors) to the gate.

Note that all of this is actually not computer science related, it's electrical engineering. If you would like to find out more about circuits in depth, I would advise you to ask on electronics.SE.


Are all language over $\Sigma= \{0\}$ decidable?

A language over $\{0\}$ is any subset of the set S of all strings consisting of a finite number of 0s. S is countable, the set of all subsets of S is uncountable.

Any decidable language must be decided by some algorithm. The set of algorithms, no matter how you describe it, is countable, not uncountable. Therefore some subsets of S (actually almost all) are not decidable.


What is the advantage of Randomized Quicksort?

If the input array is distributed uniformly at random then (as you noted) there is no difference between always picking an element at a fixed position (for example the middle one as you suggest) or picking an element chosen at random.

If however your input array is not really in random order (which happens to be the case in  almost all practical scenarios) then one needs to either "preshufle" the array in order for the elements in it to be placed in random order, or (equivalently) always take a random element as a pivot. This ensures the partitioning phase of quicksort partitions the arrays into sub-arrays of almost equal size and hence that the expected running time remains $O(n\log n)$

So your confusion appears to come from the fact that somehow you assume a sorting algorithm can (in practice) expect the input array to always be randomly distributed.


standard sequential algorithm with polylog runtime?

Where each operation is $ O\left(\log^kn\right)$ amortized/expected; I don't know if necessarily $\Theta\left(\log^kn\right)$:

Dynamic graph connectivity algorithms

Poly-Logarithmic Deterministic Fully-Dynamic Algorithms
for Connectivity, Minimum Spanning Tree, 2-Edge,
and Biconnectivity (PDF)
Dynamic graph connectivity in polylogarithmic worst case time (PDF, slides)
Fully Dynamic 2-Edge Connectivity Algorithm in
Polylogarithmic Time per Operation (PDF)
Lists of connectivity problems

Maintaining Dynamic Sequences under Equality Tests
in Polylogarithmic Time (PDF)
Distances and point-sets:

Maintaining the miminal distance of a point set in polylogarithmic time (PDF, $O\left(\log^2n\right)$, Smid)
New techniques for some dynamic closest-point and farthest-point problems ($O\left(\log^D n\right)$ Supowit)
New Techniques For Exact And Approximate Dynamic Closest-Point Problems (PDF, Kapoor, Smid, $O\left(\log^D n \log \log n\right)$, though cites others with just $O(polylog)$)
TOPP 63: Dynamic Planar Nearest Neighbors, lists 3 papers with data structures that have operations that run in $O\left(log^k n\right)$ time
Point location algorithms,
Monotone subdivisions, without fractional cascading, query-time is $O\left(\log^2 n\right)$
Best known algorithms for point-location in higher-dimensions ($\gt 2$) have a trade-off; $O\left(\log n\right)$ query-time has large memory requirements that make them unscaleable. Reducing the memory requirements (for example to $O\left(n\log n\right)$ results in query-times of $O\left(\log^k n\right)$

Efficient Partition Trees (PDF, Matousek, $O\left(\log^2 n\right)$ insertion time)
An Implicit Data Structure For The Dictionary Problem That Runs In Polylog Time (Munro, $O\left(\log^2n\right)$)

There are also many algorithms with polylogarithmic factors; $\tilde {O}(\cdot)$ is notation that is used when hiding polylogarithmic factors. So $O\left(n\log^k n \right)\in\tilde {O}(n)$.


How can I get O(1) prepend on a random-access list?

A deque with growing arrays provides the operations you need in (amortized) constant time. Reversing a deque is simple, you don't move data around, you just switch the meaning of prepend and append and massage the index for at and update.

But you don't seem to want to reverse the list anyway.


You can do this for 13 bits, or 15 bits etc, etc.. there is nothing stopping you.

The reason you jump to the next word size is because of the computers hardware. If a register has 8 bits and you are only using 6 bits, the register STILL has 8 bits.

You can design a system with 13 bit word size, and it will still work the same.


Operating System: Performance of Demand Paging

CPUs keep in special purpose caches recently addressed page table entries. Entries are usually named "TLB = Translation Lookaside Buffer"

We have 3 cases :

The page is in TLBs and the access is allowed (no write in read-only areas, no user access in supervisor pages, etc...). The delay to access the TLBs is usually hidden through pipelining. The access time depends on whether data is in caches or not. Can be less than 1ns on current high performance CPUs.
The page is not in TLBs. The CPU must find a way to update the TLBs. Some do it with simple hardware mechanisms, others use exceptions and let software do the work. In both cases, one or more memory accesses to pages tables is needed. 8ms is far too much for such operations which have a huge impact on CPU performance. This is not really "page faults"
The page may be in the TLBs, or not, but there is a real "page fault", for example the memory accessed has been swapped to disk, or not yet initialized, or the applications has a bug... The operating system will need to do complex thing to correct that, loading memory and updating page tables, or killing the applications... 8ms seems a reasonable delay for some of these operations.


How to understand the mathematical constraint of potentials?

I suspect there's some misunderstanding about the definition/meaning of $a_{ij}$.  The time to complete task $i$ depends only on $i$ (not on $j$), so it wouldn't make sense to use notation like $a_{ij}$ for the length of task $i$: we'd instead expect to see only the index $i$, but not $j$, appear in that notation.

I suspect you'll probably need to go back to your textbook or other source on scheduling and look for a precise definition of the notation that it uses.  If your textbook doesn't define its notation, look for a better textbook.

As far as the constraint $t_j - t_i \le a_{ij}$, that is expressing that $t_j$ should start at most $a_{ij}$ seconds after $t_i$ starts.  So, it'd make more sense for $a_{ij}$ to be a permissible delay that expresses the maximum time you can wait to start task $j$, once task $i$ has been started.


In Lbest PSO, how is the local best position in a neighbourhood defined?

In general option b) is how a Lbest PSO is implemented.

This makes sense, as the Lbest particle is meant to be the social influence, and from an optimization perspective you would utilize the best candidate solution information from you neighborhood, which would inherently be the best of the pbest positions.


Multiple Knapsack Problem with Set of Admissible Balls

This is NP-hard by reduction from 3-dimensional matching (3DM): turn each triple $\{a, b, c\}$ into a valid pair $\{a, b\}$ of balls for bin $c$, and add a large number of balls that don't belong to any valid pairs (so that if they go in a bin, they must be the sole occupant). The optimal solution will then hold $k+m$ balls ($k$ bins with 2 balls each and $m-k$ bins with 1 ball each), where $k$ is the largest size of any 3DM for the original input.


Complexity class for NP with access to a DP oracle

You have not found explicit mention of it because it is the same class as $\Sigma_2 = \textbf{NP}^\textbf{NP}$. $\Sigma_2 \subseteq \textbf{NP}^\text{DP}$ holds because any $\textbf{NP}$ query can be poly-time (many-one) reduced to a SAT query, which, in turn, can be cast as a DP query (by setting $\varphi_2$ to a trivially unsatisfiable formula). Conversely, $\Sigma_2 \supseteq \textbf{NP}^\text{DP}$ because any DP query can be answered by two (adaptive) SAT queries.