Why are complex numbers needed to define qubits? I have started learning about quantum computing, and I have been told that you can forget about the physics and think of qubits as a natural generalization of the notion of bit. According to this view, one should think about a qubit as a generalization of a bit, where the states $0$ and $1$ are in superposition; there is "a little bit of $0$ and a little bit of $1$".
This is all fine, I think, but if I were to model this formally, I would model a qubit as a real probability coefficient $\alpha \in [0,1] \subseteq \mathbb{R}$, representing the amount of $0$ in my qubit (thus $1-\alpha$ being the amount of $1$). Instead, in quantum computing you define a qubit as
$$\alpha_0|0\rangle + \alpha_1|1\rangle$$ where $\alpha_0, \alpha_1 \in \mathbb{C}$, and $|\alpha_0|^2 + |\alpha_1|^2 = 1$.
Given that complex numbers rarely appear in classical computer science, this seems an odd design choice if we are to approach quantum computing from a purely theoretical computer science point of view. I assume that the reason for complex numbers showing up here is that they are strictly necessary in quantum mechanics, but this is quite unsatisfactory of an answer for a theoretical computer scientist. My questions are two:

Is there an intuitive, non-physics way, of justifying these complex numbers?
Is it maybe that restricting to real numbers as coefficients yields a computational model equivalent to classical probabilistic Turing machines (in terms of efficiency)?

I would appreciate references where I could find more about the definition of qubits from a purely TCS point of view.

You can run any standard quantum algorithm on a real-amplitude quantum computer with one additional qubit and only constant-factor slowdown (or perhaps linear-factor slowdown considering loss of parallelism) by replacing each $a{+}bi$ in your unitary matrices by $\big(\begin{smallmatrix}a&-b\\b&a\end{smallmatrix}\big)$. Likewise, you can simulate a quaternionic quantum computer on a standard quantum computer with one additional qubit by replacing $a{+}bi{+}cj{+}dk$ with $\big(\begin{smallmatrix}a+bi&-c+di\\c+di&a-bi\end{smallmatrix}\big)$. So these models are all polynomially equivalent.
I doubt that there's a good non-physical argument for the appearance of complex numbers. In physics they're related to the duality between zeroth and first derivatives of position in harmonic oscillation (the same reason that complex numbers are used in modeling AC circuits), and that duality doesn't exist in the discrete quantum circuit model. Another argument from physics is that in Lagrangian QM the amplitude of a transition is $\int e^{iS(γ)} \, \mathrm dγ$ (where $γ$ ranges over "histories"), and there doesn't seem to be anything you can sensibly replace $i$ with in the real case. But this model, where each history contributes an amplitude with the same absolute value but a different phase, only works because of cancellation of nearby histories, and there aren't any "nearby" histories in the quantum circuit model.


Polynomial time reductions between two problems I have two sets $A$ and $B$, I want to reduce $A$ to $B$ and $B$ to $A$.

Formulas consist of a finite set of variables $\mathcal{V}$. An assignment $\sigma$ assigns truth values to each variable in $F$. When writing $F(\sigma)$ for an assignment $\sigma : \mathcal{V} \rightarrow \{0, 1\}$ I refer to the application of the assignment to formula $F$ (truth values are assigned to variables in $F$ according to $\sigma$).

Set A contains all unsatisfiable propositional formulas $F$:

$A := \{F \in \mathcal{F}\ | \  \forall \sigma: \mathcal{V} \rightarrow \{0,1\}. \sigma(F) = 0 \}$

Set B contains all propositional formulas which evaluate to the same truth value for an assignment $\sigma$ and its opposite $\overline \sigma$ (this condition must hold for all assignments):

$B := \{F \in \mathcal{F}\ | \  \forall \sigma: \mathcal{V} \rightarrow \{0,1\}. \sigma(F) = \overline\sigma(F) \}$

Let $A \subseteq \Sigma ^*$, $B \subseteq \Gamma ^*$ and $f: \Sigma ^* \rightarrow \Gamma ^*$.
By reduction I mean finding a total and computable (in polynomial time) function $f$ such that $\forall w \in \Sigma ^*.w \in A \iff f(w) \in B$ which can be abbreviated by $A \leq B$.

How to do the reductions $A \leq B$ and $B \leq A$? After the reductions are done, does that imply that problems $A$ and $B$ are equally difficult?

You can reduce from $B$ to $A$ by setting $f(F) = (F \neq F^{'})$ where $F^{'}$ is $F$ with every variable replaced with its negation. Equally, you can reduce from $A$ to $B$ by setting $f(F) = F$, because every variable assignment, and its negation, will be false.


Tasks in which recursion is either the fastest or only way to produce a result I've just finished studying recursion at university. One thing that stood out for me however was that in both the lectures and in the practical we completed, all the tasks we were asked to do could be performed faster, and in less code, using iterative means.
This was something the lecturer confirmed.

Could somebody please give me some examples of situations when recursion is a better solution than iterative techniques? Additionally, are there any situations in which recursion is the only way to sole a problem?

There are no questions which can only be solved with recursion. This is because they can be solved with Turing machines, which don't use recursion.

The set of problems which can be solved with a TM are exactly the same as the ones which can be solved with recursion (or its formal model, the Lambda Calculus).

In particular, if you want to simulate recursion iteratively, the way to do this is to use a data structure called a stack (which simulates the call stack for functions).

As for algorithms that can be solved better using recursion, there are tons. I'm surprised that your recursive versions were longer, as recursion usually leads to less code. This is one of the reasons haskell is gaining popularity.

Consider the algorithm quicksort, for sorting lists. In rough pseudocode, it's as follows:

function quicksort(list)
    if length(list) <= 1
        return list
    pivot = first element of list
    lessList = []
    equalList = []
    greaterList = []
    for each element in list:
        if element < pivot, add to lessList
        if element == pivot, add to equalList
        if element > pivot, add to greater list
   sortedLess = quicksort(lessList)
   sortedGreater = quicksort(greaterList)
   return sortedLess ++ equalList ++ sortedGreater

where ++ means concatenation.

The code isn't purely functional, but by dividing the list into different parts, and sorting each sublist recursively, we get a very short $O(n\log n)$ sort.

Recursion is also very useful for recursive data structures. Often times you'll have a traversal on trees, of the following form:

function traverseTree(tree)
    if (tree is a single node)
        do something to that node
    else, for each child of tree:
         traverseTree(child)


Can I speed up Insertion Sort by using a tree for finding insertion positions? I want to implement an insertionSort-algorithm. Let's say I have these pseudocode.

function insertionSort(F)
  for i <- 1 to n - 1 do
    j  <- findInsertPosition(F, i, 0, i - 1)
    insert(F, i, j)
  end for
end function

Now I want to implement the findInsertPosition function. Say I give this function my list, which is an array, and change this array into a tree, so that I can search iteratively in this tree for my element.

Would my complexity for the whole code be still maintained in $O(n \log n)$?

Would my complexity for the whole code be still maintained in $O(n \log n)$?

Let's check where we're coming from: Insertion Sort runs in time $\Theta(n^2)$ (worst and average case) if you implement findInsertionPosition (fIP) with a simple loop that scans the array.

Second, let's check what we can possible achieve. Assume that fIP runs in time $O(1)$. We still get $\Theta(n^2)$ since insert alone takes times linear in i in each iteration (worst and average case), adding up to $\Theta(n^2)$.

Third, why use a tree? You can easily achieve running-time logarithmic in i for fIP (for a total of something in $\Theta(n \log n)$) by using binary search. That would still be dominated by the cumulative cost of insert, of course.

If you did use a tree, it would make the most sense to not throw it away between iterations; fIP would be obsolete. You would effectively have sorting by creating a search tree (which we don't really call Insertion Sort) but, yes, that would have running-time in $\Theta(n \log n)$, provided you use a balanced search tree.

In summary, no, it does not make sense to try and tweak Insertion Sort by using search trees.


What is a brief but complete explanation of a pure/dependent type system? If something is simple, then it should be completely explainable with a few words. This can be done for the λ-calculus:

  The λ-calculus is a syntactical grammar (basically, a structure) with a reduction rule (which
  means a search/replace procedure is repeatedly applied to every occurrence of a specific pattern until no such pattern exists).

  Grammar:

Term = (Term Term) | (λ Var . Term) | Var

  Reduction rule:

((λ var body) term) -> SUBS(body,var,term)
    where `SUBS` replaces all occurrences of `var`
    by `term` in `body`, avoiding name capture.

  Examples:

(λ a . a)                             -> (λ a a)
((λ a . (λ b . (b a))) (λ x . x))     -> (λ b . (b (λ x x)))
((λ a . (a a)) (λ x . x))             -> (λ x . x)
((λ a . (λ b . ((b a) a))) (λ x . x)) -> (λ b . ((b (λ x . x)) (λ x . x)))
((λ x . (x x)) (λ x . (x x)))         -> never halts

While somewhat informal, one could argue this is informative enough for a normal human to understand the λ-calculus as a whole - and it takes 22 lines of markdown. I'm trying to understand pure/dependent type systems as used by Idris/Agda and similar projects, but the briefer explanation I could find was Simply Easy - a great paper, but that seems to assume a lot of previous knowledge (Haskell, inductive definitions) that I don't have. I think something briefer, less rich could eliminate some of those barriers. Thus,

Is it possible to give a brief, complete explanation of pure/dependent type systems, in the same format I presented the λ-calculus above?

Let's have a go. I'll not bother about Girard's paradox, because it distracts from the central ideas. I will need to introduce some presentational machinery about judgments and derivations and such.

Grammar

  Term   ::=   (Elim)   |   *   |   (Var:Term)→Term   |   λVar↦Term

  Elim   ::=    Term:Term   |   Var   |   Elim Term

The grammar has two mutually defined forms, "terms" which are the general notion of thing (types are things, values are things), including * (the type of types), dependent function types, and lambda-abstractions, but also embedding "eliminations" (i.e. "usages" rather than "constructions"), which are nested applications where the thing ultimately in the function position is either a variable or a term annotated with its type.

Reduction Rules

  (λy↦t : (x:S)→T) s   ↝  t[s:S / y] : T[s:S / x]

  (t : T)  ↝  t

The substitution operation t[e / x] replaces every occurrence of the variable x with the elimination e, avoiding name capture. To form an application that can reduce, a lambda term must be annotated by its type to make an elimination. The type annotation gives the lambda-abstraction a kind of "reactivity", allowing application to proceed. Once we reach the point where no more application is happening and the active t : T is being embedded back into the term syntax, we can drop the type annotation.

Let's extend the ↝ reduction relation by structural closure: the rules apply anywhere inside terms and eliminations that you can find something matching the left-hand side. Write ↝* for the reflexive-transitive (0-or-more-step) closure of ↝. The resulting reduction system is confluent in this sense:

  If s ↝* p and s ↝* q, then there exists some r such that p ↝* r and q ↝* r.

Contexts

  Context   ::=     |   Context, Var : Term

Contexts are sequences which assign types to variables, growing on the right, which we think of as the "local" end, telling us about the most recently bound variables. An important property of contexts is that it's always possible to choose a variable not already used in the context. We maintain the invariant that the variables ascribed types in the context are distinct.

Judgments

  Judgment   ::=   Context ⊢ Term has Term   |   Context ⊢ Elim is Term

That's the grammar of judgments, but how to read them? For a start, ⊢ is the tradional "turnstile" symbol, separating assumptions from conclusions: you can read it informally as "says".

  G ⊢ T has t

means that given context G, type T admits term t;

  G ⊢ e is S

means that given context G, elimination e is given type S.

Judgments have interesting structure: zero or more inputs, one or more subject, zero or more outputs.

INPUTS                   SUBJECT        OUTPUTS
Context |- Term   has    Term
Context |-               Elim      is   Term

That is, we must propose the types of terms in advance and just check them, but we synthesize the types of eliminations.

Typing Rules

I present these in a vaguely Prolog style, writing J -: P1; ...; Pn to indicate that judgment J holds if premises P1 through Pn also hold. A premise will be another judgment, or a claim about reduction.

  Terms

  G ⊢ T has t   -:   T ↝ R;   G ⊢ R has t

  G ⊢ * has *

  G ⊢ * has (x:S)→T   -:   G ⊢ * has S;   G, z:S !- * has T[z / x]

  G ⊢ (x:S)→T has λy↦t   -:   G, z:S ⊢ T[z/x] has t[z/y]

  G ⊢ T has (e)   -:   G ⊢ e is T

  Eliminations

  G ⊢ e is R   -:   G ⊢ e is S;   S ↝ R

  G, x:S, G' ⊢ x is S

  G ⊢ f s is T[s:S / x]   -:   G ⊢ f is (x:S)→T;   G ⊢ S has s

And that's it!

Only two rules are not syntax-directed: the rule which says "you can reduce a type before you use it to check a term" and the rule which says "you can reduce a type after you've synthesized it from an elimination". One viable strategy is to reduce types until you've exposed the topmost constructor.

This system is not strongly normalizing (because of Girard's Paradox, which is a liar-style paradox of self-reference), but it can be made strongly normalizing by splitting * into "universe levels" where any values which involve types at lower levels themselves have types at higher levels, preventing self-reference.

This system does, however, have the property of type preservation, in this sense.

  If G ⊢ T has t and G ↝* D and T ↝* R and t ↝ r, then D ⊢ R has r.

  If G ⊢ e is S and G ↝* D and e ↝ f, then there exists R such that S ↝* R and D ⊢ f is R.

Contexts can compute by allowing the terms they contain to compute. That is, if a judgment is valid now, you can compute its inputs as much as you like and its subject one step, and then it will be possible to compute its outputs somehow to make sure the resulting judgment stays valid. The proof is a simple induction on typing derivations, given the confluence of -->*.

Of course, I've presented only the functional core here, but extensions can be quite modular. Here are pairs.

  Term   ::=   ...   |   (x:S)*T   |   s,t

  Elim   ::=   ...   |   e.head    |   e.tail

  (s,t : (x:S)*T).head ↝ s:S

  (s,t : (x:S)*T).tail ↝ t:T[s:S / x]

  G ⊢ * has (x:S)*T   -:   G ⊢ * has S;   G, z:S ⊢ * has T[z / x]

  G ⊢ (x:S)*T has s,t   -:   G ⊢ S has s;   G ⊢ T[s:S / x] has t

  G ⊢ e.head is S   -:   G ⊢ e is (x:S)*T

  G ⊢ e.tail is T[e.head / x]   -:   G ⊢ e is (x:S)*T


Crossover method for genetic algorithm I got an amount of numbers, they are shuffled and represent the individuals.
For example (3,1,3,2,5,22,5) is one individual or (22,3,1,3,5,5,2).

Mutation is done quite easy by permutation within an individual.

The problem is to find a crossover method between 2 individuals, in which the quantity of the values stay the same(for the above example 2 times 3, 2 times 5, 1 time 22 and so on). I searched a lot on it but only found crossover methods for either unordered / ordered lists. Those for ordered lists seemed promising but they require that every value only occur ones.

Do you know a method to solve this problem or got an idea for altering an crossover for ordered list method like PMX?

You can choose a random threshold $t \leq n$ such that the first $t$ of the first individual is taken and then you take the rest from the other individual, so in your case, if $t = 4$, your new individual is $(3,1,3,2,22,5,5)$.  As Richerby clarifies below, you take the first $t$ elements from the first individual and put the remaining $n-t$ elements in the order they appear in the second individual.

Making sure that you take the correct number is done by simply counting using a hashmap.  Below, correct_count is a map from an element in an individual to the number of times it occurs, ind1 and ind2 are the two individuals you're trying to crossover.

correct_count = {}
for x in ind1:
    correct_count{x} += 1

t = random(n)
new_ind = ind1[0:t]
count = {}
for a in new_ind:
    count{a} += 1
for x in ind2:
    if count{x} != correct_count{x}:
        new_ind.append(x)
        count{x} += 1


Measuring difference between two sets of neural network weights? Suppose that we take a neural network of a given topology, and run it through two training processes, obtaining two different sets of converged weights at the end of the training.

What is a good way to measure the difference between the two sets of weights?

If this were a curve-fit where the parameters were largely orthogonal, we could simply treat the parameters as a cartesian space and compute the length of the vector difference between the sets.

However, the weights in a neural network are often not at all orthogonal.  There are trivial redundancies, in that we can reorder nodes within a layer, or multiply the input weights to a given node by a constant factor and the output weights by its inverse.  Even if we remove these by putting the weights in some canonical form (normalizing and sorting them, for instance), I can't see any reason to assume that we won't have plenty of remaining non-orthogonality.  As a result, two sets of neural-network weights that have a large vector-difference length may be essentially equivalent in practice.

An alternate conceptual approach would be to numerically integrate the difference between the output values over the entire input space, but for typical neural networks this space has high enough dimension for such an integration to be intractable.  So we'd need to do some sort of sampling-based approach, which introduces more handwaving about whether it's a meaningful measure.

Is there any existing consensus on what's a good measure?  Or, for that matter, any existing practice for what other researchers have used?

One way to compare two neural networks is to compare how similar their predictions are, on typical instances.

Ideally, we'd like to compute the expected value of this similarity, taken over the distribution on instances.  However, as you say, the input space is high-dimensional, so the integral is hard to compute.  Also, the distribution on instances typically isn't known in any analytical or useful form.

Therefore, the standard trick is to estimate this expected value, using sampling.  We draw a sample of instances, compute the similarity of the predictions from the two networks on each instance, and take the average of those similarity values.  If the sample is large enough, this should be a good approximation to the expected value (to the integral).  So, you'll set aside a separate validation set, and then compute the average similarity between the two networks' predictions on this validation set.

I can formalize this more precisely.  Let $f,g$ be the two classifiers.  Suppose there are $k$ classes.  Assume you are using a softmax layer at the output of the neural network.  Then the output of a classifier $f$ on instance $x$ is a $k$-vector $f(x)$ whose $i$th component can be interpreted as the probability that $x$ has class $c$ (as predicted by the classifier).  So, we want some way to measure the similarity of the two $k$-vectors $f(x),g(x)$, i.e., the similarity of those two probability distributions on the $k$ classes.  You can use any distance metric or similarity measure on probability distributions.

Let $d(\cdot,\cdot)$ represent a distance measure on two distributions (or, more generally, a dissimilarity measure -- it need not be a metric).  Ideally, we'd like to compute $\mathbb{E}[d(f(X),g(X))]$ where the expectation is taken with respect to a random variable $X$ that is distributed according to the input distribution on instances.  To approximate this, we compute

$$D = {1 \over n} \sum_{j=1}^n d(f(x_j),g(x_j)),$$

where $x_1,\dots,x_n$ is a validation set that is held out and set aside for this purpose.  The validation set should be separate from the training set.

You can now instantiate $d$ with any distance measure on distributions of your choice.  Some reasonable choices include: KL divergence, or the Jensen-Shannon divergence (a symmetric version of the KL divergence);  total variation distance; earth mover's distance; or a very simple measure where $d(u,v) = 1$ if $\arg\max_i u_i \ne \arg\max_i v_i$, else $d(u,v)=0$ (i.e., compare whether both networks predicts the same class as the most likely class).

This approach is suitable if you want to measure how similar the predictions of the two neural networks are, without regard to their internal weights -- i.e., treating them as a black box.  I don't know how to compare how similar their internal structure is; there are probably many non-trivial transformations to networks that compute essentially the same thing, but with very different-looking weights.


Comparing floating-point numbers as integers In the article http://floating-point-gui.de/errors/comparison/, a method for comparing floating-point numbers is suggested:

There is an alternative to heaping conceptual complexity onto such an apparently simple task: instead of comparing a and b as real numbers, we can think about them as discrete steps and define the error margin as the maximum number of possible floating-point values between the two values.
This is conceptually very clear and easy and has the advantage of implicitly scaling the relative error margin with the magnitude of the values. Technically, it’s a bit more complex, but not as much as you might think, because IEEE 754 floats are designed to maintain their order when their bit patterns are interpreted as integers.

So instead of some complex variant of abs(b - a) < ε, we interpret a and b as integers and find abs(b - a) < ε(steps(a, b)) where ε is somehow variable with regards to the density of floating-point numbers in the vicinity of a and b. But how exactly?
Also, does this method really alleviate checking for NaNs and Infs? Or are some of these "heaps of conceptual complexity" inevitable if you want a solid, generic method of floating-point comparison?
The following C code produces 1677722:
#include <stdio.h>

int main(int argc, char *argv[])
{
    double x, y, z, a, b;
    int steps;

    sscanf("0.1", "%f", &x);
    sscanf("0.2", "%f", &y);
    sscanf("0.15", "%f", &z);

    a = x + y;
    b = z + z;
    steps = *(int*)&b - *(int*)&a;

    printf("%d\n", steps);
}

Edit: Rephrased so the word "discrete" is not misused. Rewrote "steps(a, b) < ε(a, b)" into "abs(b - a) < ε(steps(a, b))" to indicate that it may still just be floating-point operations, but that ε is chosen variably.

There are a few fine tricks in the IEEE P754 format, which allows the use of integer operations for comparisons, or for rounding... It is useful for hardware implementations, for CPUs without an FPU, for some optimized libraries that need fast comparisons...

Caveats:
- The sign bit (MSB) must be handled separately.
- NaNs must be checked.

When comparing 0, denormals, normals or infinites of the same sign, integer comparisons work for floating point numbers.


How to evaluate relations in a DAG? To begin with: what I know of computer science is what friends have told me and what I've read on Wikipedia. Please correct me if I'm using some term wrongly, or if there is something I can clarify.

Let's say I have a directed graph. I want my computer to look at it, and see whether x > y, y > x, or if the relationship between x and y is unknown.

Linear graph

If the graph looks kind of like this it's an easy task:

Just let a = 4, b = 3, c = 2, and d = 1. I can evaluate if a > c by comparing 4 and 2, and the result will be correct.

Tree graph

Now it gets interesting.

Here we have a tree graph. This kind of hierarchical data is discussed by Bill Karwin in these slides, which outlines four different ways of storing hierarchical data in a relational database. You can see a summary table on slide 69. Of these, the "nested sets" model looks like the one I'd prefer.

Directed acyclic graph (DAG)

Now, what if we have a directed acyclic graph?

All of the models described by Bill Karwin above work only if each node has at most one parent. In this graph, and more complex variants of it, any given node can have any number of parents (and any number of children).

My question is: how can I store a DAG in a normal relational database (such as MySQL) so that I can query the database for the relationship between two given nodes?

Excellent question.  This is known as the problem of answering reachability queries in a graph, and in particular, in a directed acyclic graph (dag).  Basically, you want to know whether y is reachable from x by following edges in the graph -- that's known as a reachability query.  (And symmetrically, you also want to know whether x is reachable from y -- that's a second reachability query.)  Answering reachability queries efficiently is challenging: there are good algorithms for trees, but dags are harder.

One approach is to do a depth-first search from x and see if y is reachable.  However, in the worst case you might end up traversing the entire graph; the worst-case running time is $O(V+E)$.  That's fine if the graph is small, but might take an uncomfortably long time if the graph is large.  So there's been a lot of work on determining whether or not you can do some preprocessing or precomputation on the graph to make it easier to later answer reachability queries more efficiently than that.  If the graph is static (doesn't change), this is known as the reachability problem in dags; if the graph is also changing, then this is known as the dynamic reachability problem for dags.  These problems have been studied in both the CS theory and the databases communities.

Here are some resources to get you started in learning about the state of the art on this problem:

https://cstheory.stackexchange.com/q/37074/5038
https://cstheory.stackexchange.com/q/25298/5038
https://cstheory.stackexchange.com/q/21503/5038
https://cstheory.stackexchange.com/q/5176/5038
https://cstheory.stackexchange.com/q/18787/5038
https://cstheory.stackexchange.com/q/14343/5038
An incrementally-condensed transitive-reduction of a DAG, with efficient reachability queries

Finally, note that MySQL is a relational database, which is intended for relational data -- i.e., data in a tabular structure.  I believe there are also graph-based databases, intended for data with a graph structure.  I don't know much about that subject, but it's possible they might have built-in support that eases some kinds of queries and computations on graphs.


Runtime of the optimal greedy $2$-approximation algorithm for the $k$-clustering problem We are given a set 2-dimensional points $|P| = n$ and an integer $k$. We must find a collection of $k$ circles that enclose all the $n$ points such that the radius of the largest circle is as small as possible. In other words, we must find a set $C = \{ c_1,c_2,\ldots,c_k\}$ of $k$ center points such that the cost function $\text{cost}(C) = \max_i \min_j D(p_i, c_j)$ is minimized. Here, $D$ denotes the Euclidean distance between an input point $p_i$ and a center point $c_j$. Each point assigns itself to the closest cluster center grouping the vertices into $k$ different clusters.

The problem is known as the (discrete) $k$-clustering problem and it is $\text{NP}$-hard. It can be shown with a reduction from the $\text{NP}$-complete dominating set problem that if there exists a $\rho$-approximation algorithm for the problem with $\rho < 2$ then $\text{P} = \text{NP}$.

The optimal $2$-approximation algorithm is very simple and intuitive. One first picks a point $p \in P$ arbitrarily and puts it in the set $C$ of cluster centers. Then one picks the next cluster center such that is as far away as possible from all the other cluster centers. So while $|C| < k$, we repeatedly find a point $j \in P$ for which the distance $D(j,C)$ is maximized and add it to $C$. Once $|C| = k$ we are done.

It is not hard to see that the optimal greedy algorithm runs in $O(nk)$ time. This raises a question: can we achieve $o(nk)$ time? How much better can we do?

The problem can be indeed viewed geometrically in a way that we would like to cover the $V$ points by $k$ balls, where the radius of the largest ball is minimized.

$O(nk)$ is indeed quite simple to achieve but one can do better. Feder and Greene, Optimal algorithms for approximate clustering, 1988 achieve a running time of $\Theta(n \log k)$ using more clever data structures and further show that this is optimal in the algebraic decision tree model.


regular expression: sum of positive fixed point decimal numbers I need help with this exercise.

Indicate the regular expression for the following Languages. Explain your  expression in one sentence and indicate the basis form of the alphabet. Indicate also every assumption you make.

i) Sums of positive fixed-point decimal numbers. The following Strings should exist in the Language:

e.g: 3.14 or also 3 + 4.2 + 7 + 1

I have a couple more exersices that are pretty similar but I guess if I get to understand this exercise I could try to do the others faster.

I appreciate the help in advance.

The idea is to identify the different kind of subexpression you have, and the regular expression should write itself.

Here you have a non-empty sum of decimal numbers, so the "outside shape" is $E=N(+N)^*$, where N is an expression for decimal numbers, and "+" is the symbol for addition.
Now we just have to detail N: it is a non-empty sequence of digits, with possibly one dot, which does not start with $0$ and does not end with $0$ if there is a dot.
For short let write D=0+1+2+...+9 the expression for 1 digit. here the "+" is the one from regular expression, meaning Union, not the addition symbol.
Also, the first digit should not be 0, and if there is a point, the last one should not be 0. So let's P=1+2+...+9 the expression for nonzero digits

We are now ready to write N:
N=PD*+PD*.D*P+0.D*P
It means that either we don't have a dot, and then we can end with 0, or we have a dot, and then we cannot ened with 0. There is also a special case for numbers like $0.345$.

By substituting the letters with their explicit expressions, you get the full explicit one for E.


Minimum cardinality graph partition that removes specific edges I have a computational problem that I want to solve. I'm not sure if it has already been studied in literature, or if so under what name. I'd appreciate any pointers to literature or suggestions for an algorithm.
Input: A connected, undirected graph G = (V, E) in which certain edges are labelled "bad".
Output: The minimum cardinality partition of V such that 1) all of the induced subgraphs of the partition are connected, and 2) none of the induced subgraphs contains a bad edge.
Thanks!

Try to look at what happens when all the edges are bad edges.
What would the question be if I asked:

Can you partition the graph into three partitions, e.g. red, green, blue, such that for every edge, the "color" of the endpoints of each edge is "chromatic".

(Let's also make the graph into a complete graph by adding "good" edges between every non-adjacent vertices.)


d-ary heap implementation vs Fibonacci heap implementation Dijkstra performance comparions Let's say that Dijkstra’s algorithm with the priority queue using a d-ary heap.  if adjusting d,  we can try to achieve the best runtimes for the algorithm with d being $\sim |E|/|V|$.

Then for a fixed $|V|$, what is the largest possible ratio between this runtime and the runtime of Dijkstra using a Fibonacci heap?  Where knowing the Fibonacci heap: delete_min = $O(\log |V |)$, insert/decrease_key = $O(1)$ (amortized) and $|V|$ × delete_min + $(|V | + |E|) $ x insert $= O(|V|\log|V|+|E|)$.

On the other hand, d-ary heap implementation : delete_min = $O(\dfrac{d \log|V|}{\log d})$, insert/ decrease_key =$O(\dfrac{\log|V|}{\log d}$), and |V | × delete_min + (|V | + |E|) × insert  =  $O( (|V|·d+|E|)\dfrac{ \log|V|}{\log d})$.

As trying to follow a provide solution, but I am not sure why it reduces to $O(\dfrac{\log|V|}{\log |E|/|V|})$, in the case 1 where |E| dominates, so Dijkstra with Fibonacci heap is $O(|E|)$. How can we get the ratio as $O(\dfrac{\log|V|}{\log |E|/|V|})$ while Dijkstra with d-ary heap is $O( (|V|·d+|E|)\dfrac{ \log|V|}{\log d}$)?

The crux is right there in the first paragraph of the post.

  Let's say that Dijkstra’s algorithm with the priority queue using a $d$-ary heap. We can achieve the best runtimes for the algorithm with $d$ being $\sim |E|/|V|$.

As you have pointed out, the time-complexity of Dijkstra with $d$-ary heap is $O\left((|V|\cdot d+|E|)\dfrac{ \log|V|}{\log d}\right)$. Substituting $|E|/|V|$ for $d$, we see the best time-complexity of Dijikstra with d-ary heap is $O\left((2|E|)\dfrac{\log|V|}{\log|E|/|V| }\right)=O\left(\dfrac{|E|\log |V|}{\log |E|/|V|}\right)$.

In the case 1 where $|E|$ dominates, the ratio of the best time-complexity of Dijkstra with $d$-ary heap to $O(|E|)$, the time-complexity of Dijkstra with Fibonacci heap is $\dfrac{\log|V|}{\log |E|/|V|}$ (ignoring some constant factor), which takes its maximum value when $|E|$ takes its minimum value, $|V|\log |V|$. Hence we get the ratio $\dfrac{\log|V|}{\log\log|V|}$.


Length of strings accepted by DFA Problem: Given a DFA $D$, find all possible lengths of strings accepted by the $D$.

It makes sense that these lengths can be represented as $a_i+kb_i$. What might be the algorithm to find all such pairs $(a_i, b_i)$?

Take your DFA and change each of its input symbols into a single symbol, say $a$. Now of course your automaton no longer is deterministic, but lengths are preserved. Then make the automaton deterministic again. The form of the new DFA is that of a initial linear path leading to a loop. This is because of the single letter restriction.

The accepting states in the initial linear path are the finite component of the language, of lengths that do not repeat. The accepting states in the loop represent the $a_i$ for your construction. The length of the loop is the single $b$ in the $a_i+kb$ representation.


Contamination in Atomic Broadcast in crash stop failure model I'm reading several papers about different broadcast algorithms. Most of them are designed for crash stop model but they also consider contamination scenarios.

  For example for a Causal Atomic Broadcast when a faulty process
  fails to delivers messages in order and then starts broadcasting other
  messages based on its inconsistent state which causes inconsistent
  state in other correct processes.

The above is just an example why a specific process could have such a weird behavior although our failure model is crash stop. Follwoing paper describes it more.

  A Modular Approach to Fault-tolerant Broadcasts and Related Problems.
  V. Hadzilacos and S. Toueg, Distributed Systems, 97-145, 1993.

See here section 3.11 (page 22) for more sophisticated example. This is really confusing to me. Why do we don't consider this type of failure as byzantine failures? In crash stop model a single failure should result in a crash. A faulty process can NOT continue to run without crashing. What am I missing?

I think you are confusing the failure model with the correctness goals of a protocol.

A failure model specifies what kinds of things can go wrong (i.e., what kinds of failures the protocol is designed to deal with and promises to be able to handle).
A correctness goal describes what properties the protocol promises to provide (i.e., what properties it needs to achieve, to qualify as correct).

We then analyze whether a particular protocol meets a particular correctness goal in a particular failure model.  For example, protocol might achieve the correctness goal in one failure model but not in another.

Example of failure models include crash-only; or Byzantine failures; or others.  See Sections 2.3 and 2.6 for examples of kinds of failures.  A failure model would specify which of those failures are in scope (and thus, implicitly, which are out of scope).

An example of a correctness goal is "Causal Broadcast" or "Atomic Broadcast" or "Causal Atomic Broadcast".  For instance, the correctness goal that we call "Causal Broadcast" is that the protocol must ensure Causal Order for all delivered messages (see Section 3.3 of the paper you mention).  There might be a protocol that achieves Causal Order in the presence of crashes but not in the presence of Byzantine failures.

With that understanding, Section 3.11 of your paper starts out with an example of a failure that can be problematic.  That's a type of failure that isn't just a crash.  Yes, it could be considered an instance of a Byzantine failure.  However, it is also a more specific type of failure; one can articulate a more specific failure model that is more constrained than arbitrary Byzantine failures, but broader than just crashes, and which includes that failure as the sort of failure that can occur.  It may be useful to think about what is achievable in that intermediate failure model.  There are more failure models in the world than just "crash stop" and "Byzantine".


Complexity of brute force primality test in the number of digits I'm wondering how to express the complexity of a brute force primality testing algorithm in the number of digits the number under test has. The brute force algorithm just checks whether $n$ is prime by checking if there is a number $k$ from $2 \leq k \leq \lfloor\sqrt{n}\rfloor$ that cleanly divides $n$. How would I go about expressing the complexity of this algorithm in the number of digits $n$ has?

My initial thought would be that in the worst case we would have to check every number $k$ $2 \leq k \leq \lfloor\sqrt{n}\rfloor$ and $n$ is very close to $10^p$ where $p$ is the amount of digits in $n$. So this would give us at least an upper bound of $\mathcal{O}(\lfloor\sqrt{10^p}\rfloor)$. Is my thought process correct?

In the worst case we would have to check every number $k$ $2 \leq k \leq \lfloor\sqrt{n}\rfloor$ and $n$ is very close to $10^p$ where $p$ is the amount of digits in $n$. So this would give us at least an upper bound of $\mathcal{O}(\lfloor\sqrt{10^p}\rfloor)$

You are on the right track. The upper bound $\mathcal{O}(\lfloor\sqrt{10^p}\rfloor)$ is pretty good.

We can simplify the formula a little bit and strength the result a little bit.

Proposition. The number of integers between $2$ and $\sqrt n$ (inclusively) is $\Theta(10^{\frac p2})$, where $p$ is the number of digits of $n$ in base 10.

Proof. Since $p$ is the number of digits of $n$ in base 10, we know $10^{p-1}\le n<10^p$. The number of integers between 2 and $\sqrt n$ is $\lfloor\sqrt n\rfloor-1$. I will leave the rest of the proof to you.


decision trees and numeric attributes I have been reading a book about Decision Trees and it caught my attention the following part:

  In case of numeric attributes, decision trees can be geometrically
  interpreted as a collection of hyperplanes, each orthogonal to one of
  the axes

I tried to look for information about this in Internet, but I did not find anything. To what the author refers in this point?

Each vertex in a decision tree is associated with a question of the form "$x_i < c$?" (or "$x_i \leq c$?"), where $x_i$ is one of the input and $c$ is a constant. The decision whether to go left or right then depends on which side of the hyperplane $x_i = c$ the input is located.

The possible hyperplanes which come up this way are not arbitrary – they are orthogonal to one of the axes; the hyperplane $x_i = c$ is orthogonal to the $x_i$ axis. An example of a different hyperplane, which cannot occur, is $x_1 - x_2 = 0$.


"Famous logicians have made embarrassing errors here," a line from SICP. What is this referring to? Here is the context (Structure and Interpretation of Computer Programs, section 1.1.8, under heading "Local names"):

  A formal parameter of a procedure has a very special role in the procedure definition, in that it doesn't matter what name the formal parameter has. Such a name is called a bound variable, and we say that the procedure definition binds its formal parameters. The meaning of a procedure definition is unchanged if a bound variable is consistently renamed throughout the definition.

At the end of that last line, there is a footnote (26), which says:

  The concept of consistent renaming is actually subtle and difficult to define formally. Famous logicians have made embarrassing errors here.

What or who is the text referring to? Why would defining "consistent renaming" be hard, which logicians have made errors trying to define this, and what were those errors?

This is a partial answer: I have no idea about which errors or people SICP is referring to. I can only provide some hints about "why" variable renaming can be painful to handle precisely.

First of all, it does seem trivial to define. For instance, we can rename bound variables in indexed sums

$$
\sum_x e = \sum_y (e\{y/x\})
$$

where $e$ is any expression, and $e\{y/x\}$ denotes the syntactic replacement of each $x$ with $y$. Trivial, right?

Well, if we blindly apply the rule above, we get

$$
\sum_x (x+y) = \sum_y (y+y)
$$

That's not good. We need to add the requirement "$y$ does not occur in $e$", or we get a name clash.

Now, consider this correct renaming

$$
\sum_x \sum_y (x+y) = \sum_x \sum_z (x+z)
$$

if we want to rename $x$ into $y$, by the rule above we can do it on the right hand side, but not on the left hand side. That's inconvenient, since the two differ only by a renaming, so they should be handled in the same way.

A typical approach here is to resort to redefining $e\{y/x\}$ as "capture-avoiding substitution", and relax the requirement "$y$ does not occur in $e$" and use instead "$y$ does not occur free in $e$".

We then define free occurrences:

$$
free(x)=\{x\}
\qquad free(e+t) = free(e)\cup free(t)
\qquad free(\sum_x e) = free(e)\setminus\{x\}
$$

Finally, capture avoiding substitution:

$x\{t/y\}$ is $t$ if $x=y$, and $x$ otherwise.
$(e+e')\{t/y\} = e\{t/y\} + e'\{t/y\}$ (easy case)
$(\sum_x e)\{t/y\} = ??$

The last case is painful. If $x=y$, the substitution is no-op, since we want it to affect free variables only, and $x$ is bound. So the result is just $\sum_x e$.

If $y\neq x$, we would like to say that $(\sum_x e)\{t/y\} = \sum_x (e\{t/y\})$. This however is wrong, in general, since if $x$ occurs free in $t$ we get a capture.

Sigh. So, we let $z$ to be the "first" variable which is 1) not $y$, 2) not free in $t$, and 3) not free in $\sum_x e$. Here, "first" means that we need to well-order the set of variable names (e.g. by picking a bijection between names and naturals). Then, we finally let
$(\sum_x e)\{t/y\} = \sum_z (e\{z/x\}\{t/y\})$.

I hope I got it right. (My first attempt was wrong, by the way)

Some authors consider more cases, but the result is the same "up to renaming".
The choice of the "first" $z$ does not really matter above: any such $z$ would work fine, and lead to the same result (again, up to renaming).

Now, finally, we have a sound definition of renaming ($\alpha$-conversion) and capture-avoiding substitution of a free variable. Above, I considered sums, but they apply to all binders (e.g. $\lambda x$ in the lambda calculus, function definitions in many PLs, etc.).

Now, imagine having to deal with this intricate definition every time we want to prove something in PL theory. We could, but we do not want to. It's boring, tedious, error-prone, clutters the proof and provides no insight to the reader. For this reason, many PL authors simply skip the details by saying (or even taking as granted!) that terms are to be taken "up to variable renaming", that all bound variables are assumed distinct from whatever they need to be distinct from, that we assume the "Barendregt convention", or something to the same effect.

To be brutally honest, this is cheating in proofs. We could also add "wink wink, nudge nudge, say no more!" in the same spirit. We essentially ask for mercy and tell the reader: "look, this is boring, I do not want to do it, you do not want to read it -- we both know that, with a huge effort, we could rewrite this proof to include all the details".

Technically, it is possible to exploit this shortcut to prove a false statement. The experienced proof reviewer, however, knows what is "morally fine" and could made perfect (with great effort), and what is suspicious. The latter could include something which depends on the actual choice of bound names (so we are not really working "up to" as promised!). In those cases, the review will ask for more details, so that (s)he can be convinced.


Algorithm for maximum independent set in trees While studying the dynamic programing algorithm for the maximum independent set problem in trees I thought about the following simple alternative algorithm. I tried to prove it's correctness but I do not know how to attack the proof.

The algorithm iteratively finds a two vertices $u,v$ of the tree which have maximum distance among all pairs of vertices, puts $u$ in the independent set and removes $u$ and its neighbor from the tree. This procedure is continued until no more vertices are in the tree.

Does anybody have an idea how to prove that this indeed yields a maximum independent set?

Lemma. Every tree $T$ with at least three vertices has a maximum-cardinality independent set which includes all its leaves.

Proof. Let $I$ be a maximum-cardinality independent set containing the greatest number of leaves of $T$ of all such independent sets. Suppose that $v\notin I$ for some leaf $v$ of $T$ and let $w$ be $v$'s unique neighbour. If $w\notin I$, then $I\cup\{v\}$ is independent, contradicting the supposed maximality of $I$. Otherwise, $w\in I$ but $I' = (I\setminus\{w\}) \cup \{v\}$ is an independent set of the same cardinality as $I$. Since $T$ has at least three vertices, $w$ has degree at least two, so is not a leaf. Therefore, $I'$ contains one more leaf than $I$, again contradicting the choice of $I$. $\square$

Now we can see that the algorithm proposed in the question produces a maximum-cardinality independent set because it actually mimics a particular set of choices by the dynamic programming algorithm. Let $v$ and $w$ be vertices in the tree at maximal distance (which must, of course, be leaves). By the lemma, there is a maximum-cardinality independent set that includes both of these vertices. Therefore, we can pick either one to add to our independent set.

Note that there is a slight wrinkle in the algorithm as presented in the question. Suppose $v$ and $w$ are at maximal distance in $T$ and we decide to add $v$ to our independent set.  We delete $v$ and its neighbour $v'$ from $T$. However, if $v'$ had degree at least three, we have disconnected the tree.  This is OK because, by maximality of the distance from $v$ to $w$, all but one of the neighbours of $v'$ must have been leaves, so all but one of the components of $T-\{v,v'\}$ are isolated vertices. But these isolated vertices must also be added to the independent set and deleted from $T$.  If they are not, then $d(v'',x)=\infty$ for any isolated vertex $v''$ and any other vertex $x$. Thus, the algorithm would be entitled to add any vertex $x$ to the independent set at the next step, which is not guaranteed to lead to a maximum-cardinality independent set (and, indeed, might disconnect the graph even more when we delete it and its neighbours).


Number of planar graphs, given an embedding I want to find an upper bound on the number of planar graphs with $n$ vertices, assuming that we are given some embedding for those vertices beforehand. In particular, Im interested in either showing for every embedding there is $2^{o(n\log(n))}$ planar graphs, or showing that there exists an embedding with $2^{\Omega(n\log(n))}$ different planar graphs.
I know that without fixing embedding there is $2^{\Theta(n\log(n))}$, but my question differs from it since we fix an embedding beforehand.
I believe that still there is an embedding with $2^{\Omega(n\log(n))}$, but I couldn't prove or disprove it. Here is an attempt I made to try and calculate the number of planar graphs for some embedding I believed would be "hard", but it didn't work out as expected.
Thanks in advance!

Pach and Wenger proved in their paper Embedding planar graphs at fixed vertex locations that if $p_1,\ldots,p_n$ are $n$ different points on the plane, then every planar graph on $n$ vertices $v_1,\ldots,v_n$ has a planar embedding in which $v_i$ is found at position $p_i$.


Steps that guarantee exiting a maze Given a 2-dimensional maze where you can give 4 commands "move up/down/right/left". Knowing the maze but not where the person is, how to find the minimum sequence of commands that guarantees exiting the maze?  I'm looking for a single sequence of commands that will work no matter where in the maze you start from.

Assume that if our partner is given the "move right" command when there's a wall on the right, he will simply stay where he is.

In other words, we're given a maze, and we must choose a sequence of commands.  Then, our partner will be placed somewhere in the maze and will follow the sequence of commands we've chosen in advance.  We want this sequence to ensure our partner will escape, no matter where our partner was initially placed.  Note that the allowable commands do not have any conditional statements, so they cannot follow a different sequence depending on your partner is.

Is there a polynomial-time algorithm to construct such a sequence, given a description of the maze?

Yuval Filmus mentions this is a special case of a synchronizing word problem, and might be related to universal traversal sequences.  I also found a paper that seems relevant:

The Simultaneous Maze Solving Problem.  Stefan Funke, André Nusser, Sabine Storandt.  AAAI 2017.

Unfortunately for general graphs this appears to be a unsolved problem, but I'm wondering if there might be a good algorithm for this specific case.   I came up with a candidate approach: Label every position with the number of minimum steps it requires to exit, and keep track of every agent in the maze. It might be possible to do a A* search this way.

An algorithm that always works is: Put the left hand on the wall, and continue that way to the exit. Can't guarantee shortest path (to do so, you need to know the maze, at least partially, and be able to look forward. Check out the $A^*$ (A-star) algorithm, it was originally designed for just such tasks).


Solving the recurrence T(n) = 4T(n/4) + n log n with the iterative method I'm trying to solve

$$ T(n) = 4T(n/4) + n \log_{10}n.$$

I'm having trouble with Iteration Method near the end.
As far as I went, I obtained the General Formula as:

$$4^kT(n/4^k)+n\log n+\sum (n/4^k)\log(n/4^k)$$

And trying to get the moment when it finishes iterating:

$$(n/4^k)=1$$
$$n=4^k$$
$$\log_4n=k$$

And here I get stuck. I know I have to substitute $k$ with $\log_4n$ but after that I'm lost. Can I get a bit of help with explanation of every step?

Here are some more details:

Swapped $\log_4n$ on all $k$:
$$4^{\log_4n} T(n/4^{\log_4n})+n\log_2n+\sum_{n=0}^{\log_4n}n\log n$$

From logarithm rules of $a^{log_an} = n$, it ends like this:
$$(n)(1)+n\log_2n+\sum_{n=0}^{\log_4n}n\log n$$

I'm not sure how to express the sum in $n$, but as you can see already, it is $O(n\log_2n)$, and with the Master Theorem, you obtain the same result $O(n\log n)$.

Your "General Formula" is incorrect.  The third term (with the sum) is incorrect.  It should be $n$ rather than $n/4^k$.

Make the suitable correction through the rest of your answer, and use the fact that

$$\sum_{k=0}^{\log_4 n} n \log_{10}(n/4^k) \le \sum_{k=0}^{\log_4 n} n \log_{10} n$$

and you should be able to get an upper bound from there.  (The final sum is easy to evaluate as every term is the same.)


Shortest path between any origin to any destination through some way stations How can one find the shortest path between any one of the origins to any one of the destinations through a number of way stations on the way using Dijkstra algorithm?

You can visit those way stations in any order. There will be multiple origins and multiple destinations, but a path from any origin to any destination will suffice as long as it's the shortest.

Unless I'm misunderstanding the problem, you can't solve this with any simple modification to Dijkstra's because it's NP-complete.

Given an arbitrary graph, call every node a "waystation", then add start/finish nodes that are fully connected. Now running the solver for your problem will solve TSP on the original graph.


Grammar generating specific language Construct a context-sensitive grammar that generates L:

L = {a^n b^m c^k|k>n, k>m}

I believe my productions should go along this lines:

S-> ABCC
A-> a|aBC|BC
B-> b|bBC
C-> c|Cc
CB->BC

The idea is to start with 2 c and keep always one more c, and then with C->c|Cc ad as much c as i want.
How can my production for C remember the numbers of m and n.

Hint. Can you figure out a regular grammar such that for any $k, m, n$ with $k > n$ and $k > m$, there is a word in its language with that number of a, b and c (in any order)?

Hint. Did you know that you can sort with a context sensitive grammar? See an example for inspiration.


A variation of the baseball elimination problem I suppose you are all familiar with the baseball elimination problem (it is about determining whether some team with particular number of points can finish in the first place, when there are still such and such games to be played by other teams).

The rules there are rather simple - the winner gets a point, while the loser gets nothing. But what if we changed those rules, so that the loser would get -1 point for each game lost. Could it still be brought down to the max-flow problem then? I've been thinking about this, but there's no way to do that in my opinion.

I am not familiar with the baseball elimination problem, but nevertheless, if you can solve the original problem, then you can solve the new problem. Here is why. For each game that a team has to play, deduct 1 from its score. Instead of awarding it 1 point if it wins, award it 2 points. It still gets 0 if it loses. This moves us closer to the original problem.

In order to get the original problem as stated, we divide all scores by 2, converting the 2 point award to a 1 point award. This reduces the new problem to the original one, which you already know how to solve.


CFG for $\{a^i b^j : 2 i<j\}$ So I have a question:

Give a CFG for $\{a^i b^j : 2 i<j\}$

And this is my approach:

$S\to AB$

$A\to aAb\mid \varepsilon$

$B\to b \mid bB$

A confirmation, or correction, along with how you tested(and tips for testing future of my problems) will be greatly appreciated thanks.

You can derive $aabbb$ which is not in the language, so your grammar is wrong.

How did I find this? I observed that $A \Rightarrow^* a^ib^i$ and $B \Rightarrow^* b^j$ for all $i \geq 0$, $j > 0$. It's clear that this is wrong, and I looked for the smallest counter-example.

You need to ensure that more than double as many $b$'s as $a$'s are generated.


Computing Hamming Distance Between Binary Vectors Consider the following problem:

Input: We are given a set $S$ of $n$ binary vectors. A binary vector is of the form $(b_0, b_1, ... b_n)$, where $b_i \in \{0, 1\}$. Therefore, there are $n$ vectors of size $n$.

Output: For each vector in $S$, we would like to (efficiently) compute a list of binary vectors from $S$ whose Hamming distance is within some predefined constant $c$.

Output (alternative): Find the pair of vectors with minimum Hamming distance.

Clearly, the above can be done in $O(n^3)$ by computing the Hamming distance pairwise between each vector in S ($\frac{n*(n+1)}{2}$ pairwise combinations and $O(n)$ to compute the Hamming distance). However, I am looking for something more efficient, since $n$ can take large values (say, $n=10^6$).

To speed up the computation, one could use some form of hashing, where we place the binary vectors into $N$ buckets, where every vector in the $i^{th}$ bucket contains exactly $i$ ones. This could work, but in my particular case, one could expect that all binary vectors have approximately the same number of ones, so not much would be gained from such hashing. One could also look to perform some sort of compression on binary vectors and perform Hamming distance computation on the smaller compressed vectors as a bound on the distance, but I suspect there are better approaches.

Another hashing approach would be to subdivide the space into hypercubes and place each vector in one of the cubes. I believe similar approaches are used in physics simulations, where space would be divided in a number of 2D- or 3D-cubes and then compute the interaction of elements within cubes and neighboring cubes.

I have seen variations of the above in many applications, but I am not sure what is the name of the problem or how to efficiently compute the solution. It is worth noting that in my particular case the solutions does not need to be "exact", that is, there can be some errors in the output as long as "most" of it is correct. The main issue seems to be how to avoid computing the distance between vectors that are clearly far apart.

(The structure of the binary vectors in $S$ can be diverse. In some cases, there are few bits set in each vector, while in other cases the vectors can be dense. For the sparse case, the Hamming distance computation can get greatly sped up, but the bottleneck is the $\frac{n*(n+1)}{2}$ comparisons that need to be made.).

You say in the comments that we might have $c \approx 15$ or so. There should be very efficient algorithms in this case, using locality sensitive hashing.

For example, here is a simple LSH.  Randomly choose a set of about 10,000 indices (out of the 1,000,000).  Hash each vector by computing some standard hash of the 10,000 bits in those positions (ignoring the other 990,000 bits entirely).  Store all the vectors in a hashtable using this hash.  Now look for all pairs of vectors that have the same hash.  This can be done by storing all the vectors in a hashtable using this hash and looking at all collisions within a single hash bucket, or by sorting the hashes and looking at adjacent pairs.

Suppose the pair of vectors $b_i,b_j$ are at distance $\le 15$.  Then with probability about 0.86, they will agree in the selected 10,000 positions and thus have the same hash.  In other words, about 86% of the pairs of vectors at distance $\le 15$ will be found in this way.

Now you can repeat this multiple times to ensure you find all of the pairs, with high likelihood.  If you repeat this about 10 times with a different random set of indices each time, then only about $10^{-8}$ of the pairs that are close will be missed.  If you repeat it 100 times, each close pair has only a $10^{-85}$ probability to be missed.  That probability is so low it can be safely ignored: essentially, all close pairs will be found.

The running time is $O(n^2)$: $O(n)$ time to compute each hash, and then you do that $n$ times for $n$ different vectors.  In practice it might be even faster than that if you can take advantage of the fact that most of the bit positions are ignored during the hashing.


Different Classes of NP I was solving problems related to P and NP where I encountered the following problem:

Given a standard definition of NP,
 if x belongs to L then there exists y such that |y| <= |x|^d and A(x, y) = 1;
if x does not belong to L then for every y with |y| <= |x|^d we have A(x, y) = 0.

1. what is the new class formed when we don't include the second statement?
2. what is the new class formed when we don't include the first statement?
I am well versed with the definitions of P and NP but unable to figure out how to determine these new classes.
 Any help in understanding these concepts would be appreciated.

Here is a big hint to help you solve the problem:

 Can you give an example of a language that is in this class?  Can you give an example of a language that is not in this class?


Topological sort, but with some fixed values I'm working on a problem similar to topological sorting, but with an additional constraint: I want to order the nodes by assigning a positive integer index to each, and, in additional to the relative constraints the graph defines, some nodes have a predefined index assigned.

That is, the input is a set of nodes $V$, a set of relative constraints each of the form $X_a < X_b; a \in V, b \in V$, and a set of absolute constraints $X_a = i, i \in \mathbb{Z}^+$.

The output is a map $X$ such that $X_a \in \mathbb{Z}^+$ for each $a \in V$, and all relative and absolute constraints specified in the input are satisfied. The values $X_a$ need not be unique; it's acceptable that $X_a = X_b$ given $a \neq b$, so long as all the specified constraints are satisfied. If no such $X$ exists, the output is an error value.

Not sure what to search for; does such an algorithm exist? If not, is there a good way to map this problem to a known problem? I'm working on it, too, but just wanted to see if this set off any lightbulbs for anyone in the community before I go too deep :)

(In case this helps, I'm working on a solver to manage the z-indexes of my web application.)

There's a natural algorithm:

Arbitrarily pick any vertex all of whose predecessors have already been labelled; call it $v$.
If $v$ is constrained to have a specific index, label $v$ with that integer.  Otherwise, pick the smallest integer greater than all of the labels on the predecessors of $v$, and label $v$ with that integer.
If at least one vertex remains unabelled, go to step 1.

This is an adaptation of Kahn's algorithm for topological sorting, and it can be implemented so it runs in linear time.

The crucial thing that makes your problem feasible is that the labels don't need to be unique.  If the labels need to be unique, I suspect the problem becomes much harder; at least, this algorithm doesn't work, and a generalization of the problem becomes NP-hard.


Float type variable uncertainty I developed an image processing software and I need to do a numerical analysis of it, considering the error propagation associated to its operations and the uncertainty of float type variables caused by the inherent rounding up that happens with this type of variables.

Considering the IEEE 754 standard the machine epsilon for the float type variables is 1.19e-07. From what I understood, this value is the distance to the nearest representable float.

I did some testing to find if this is true by adding a float value to this epsilon as such: x + epsilon == x. This notion does not hold for every value of the float range, which is understandable since great values of floats have more uncertainty associated with them caused by the rounding and the limited number of bits used to represent them.

My question is what is the uncertainty associated to a float value in such a way that (x + y) || (x - y) == x being the float value x and the float uncertainty y.

It might be my lack of knowledge about the english language but I can not seem to understand the literature about this topic.

If someone could be as detailed as possible can you explain me the error in a simple operation such as the following?

float result = valA * 0.587f + valB * 0.331f;

If I knew the uncertainty of a float type variable this error could be simply calculated with this formulas, right?

The number 1.19e-07 is the difference from 1.0 to the next larger representable floating point number. Single precision floating numbers have the form $x = ± 2^k m$, where k is a small integer, and 1 ≤ m < 2 is a multiple of $2^{-23}$.

If you calculate a result x, and $2^k ≤ x < 2^{k+1}$, then x will be rounded to the nearest multiple of $2^{k-23}$, with a rounding error up to $2^{k-24}$.

Don't think of floating-point arithmetic to have "uncertainty". It gives a perfectly fine well-defined result, just not the one you might have wanted.

As far as your table is concerned, it doesn't make any sense to me, but I am very confident that there is no square root involved when you try to find upper bounds for floating point errors.

To analyse floating point errors: Multiplication and division may add the relative errors of their inputs, and then another rounding error is added (unless you can prove the result is exact, for example multiplying by 2.0). Addition and subtraction may add the absolute errors of their inputs, and then another rounding error is added (unless you can prove the result is exact, for example subtracting x-y where x/2 ≤ y ≤ 2x.

For tightest bounds, you analyse the error depending on the input values, and you can also improve the error by arranging operations in the right order.


Calculating Floating point Operations Per Second(FLOPS) and Integer Operations Per Second(IOPS) I am trying to learn some basic benchmarking. I have a loop in my Java program like,

float a=6.5f;
int b=3;
for(long j=0; j<999999999; j++){
       var = a*b+(a/b);
    }//end of for

My processor takes around 0.431635 second to process this. How would I calculate processor speed in terms of Flops(Floating point Operations Per Second) and Iops(Integer Operations Per Second)? Can you provide explanations with some steps?

PS:I have already asked this question in StackExchange but did not get any answer.

It really depends on the optimizer. If you compile it with optimization, it might get rid of the loop, and then it will take rather less than 0.431635 seconds. Otherwise, it seems like you have four to five floating point instructions per iteration (including int to float conversion, once or twice, depending on the optimizer), so $4\cdot10^9$ or $5\cdot10^9$ in total. Divide this by 0.431635 to get your FLOPS, which will be around $10^{10}$, or 10 GFLOPS.


Which address bits are used for set selection/tag check in a cache? If

  Capacity = 24 KiB Associativity = 6 Line Size = 32 B

As far as I know:

$$Capacity = Associtivity * Line Size * Sets$$

so
$24576 = 32 * 6 * Sets$

$Sets = 128 = 2^7$

thus 7 least significant bits are needed to identify set number.

Am I doing it correctly?

Your result is almost correct.
The number of sets is indeed 128.
But 128=2^7
And 7 bits are required to identify a set...


Programs to circuit conversion Suppose we have an algorithm for a decision problem with $n$ bit inputs that runs in $DTIME[f(n)]$ is there ways to convert to circuits of $O(f(n))$ size with AND, OR and NOT gates?

How about when we go from circuits to programs?

The Cook–Levin theorem shows how to construct a circuit of size $f(n)^{O(1)}$. I'm not sure what's the best exponent.

The opposite direction is impossible, since circuits of size 1 can compute the following language:
$$ \{ w : \text{the $|w|$th Turing machine halts on the empty input} \}. $$
More generally, circuits of size 1 can compute any language in which the answer depends only on the length of the input.


Optimal assignment of +-1 values to vertices in a graph Let $(V, E)$ be a simple connected undirected graph, $f: V \to \{-1, +1\}$, and $g: E \to \{-1, +1\}$. The function $g$ is completely defined by $f$, while $f$ is something we get to choose. The only thing we know about $g$ is that negating $f(v)$ causes $g(e)$ to negate whenever the edge $e$ is adjacent to vertex $v$, and that there are no other changes to $g$. The problem now is to choose $f$ to maximize $\sum_{e \in E} g(e)$. Is there are an efficient algorithm to solve this problem?

You may assume that the graph is of some specific form which includes trees as a proper subset. If the graph is a tree, then it is easy to come up with an efficient algorithm for this problem, starting from the root and moving towards leaves.

This is the maximum cut problem.

The function $g$ can be given explicitly as $g(\{u, v\}) = H_{\{u, v\}} f(u) f(v)$ for some $H \in \mathbb{R}^{E}$. Each choice of $f$ divides the vertices into two sets $V_+ = \{x \in V : f(x) = +1\}$ and $V_- = \{x \in V : f(x) = -1\}$. The  set of edges connecting $V_+$ and $V_-$ is the cut-set $C = \{\{v_+, v_-\} \in E: v_+ \in V_+ \text{ and } v_- \in V_-\}$. The term to maximize is

$\sum_{e \in E} g(e) = \sum_{e \in C} g(e) + \sum_{e \in E \setminus C} g(e) = \sum_{e \in E} H_e + 2 \sum_{e \in C} (-H_e)$

This is maximized by a maximum cut $C$ under edge-weight $-H_e$ for each edge $e$.

When there are both negative and positive weights, it is known that max-cut is NP-hard in general (min-cut is equivalent to max-cut with weights negated). In contrast, max-cut (min-cut) problem with non-positive (non-negative) weights has an efficient general algorithm.

Using knowledge of the structure of the graph may provide an efficient algorithm. It is easy to come up with an $O(n)$ algorithm when the graph is a tree, where $n$ is the number of vertices. For planar graphs, there are algorithms which solve max-cut in $O(n^{3/2} \log(n))$ time.

Useful search terms include submodular function and Ising spin glass model.


Solving linear programming problem with mixed type of constraints I have a query in solving the problem below:
An automobile company has two factories. One factory has 400 cars (of a certain model)
in stock and the other factory has 300 cars (of the model) in stock. Two customers order
this car model. The first customer needs 200 cars, and the second customer needs 300 cars.
The cost of shipping cars from the two factories to the customers is shown:

Customer 1
Customer 2

Factory 1
\$ 30
\$ 25

Factory 2
\$ 36
\$ 30

How should the company ship the cars in order to minimize the shipping cost?
I am confused about how to proceed with this problem. I have considered the slack variables $x_3$ through $x_6$, and conversion of the minimisation problem to a maximisation one, and got:
$\text{Maximise Z}=6x_1+5x_2-16200$
$\text{subject to, }x_1+x_2+x_3=400$
$~~~~~~~~~~~~~~~~~~~-x_1-x_2+x_4=-200$
$~~~~~~~~~~~~~~~~~~~x_1+x_5=200$
$~~~~~~~~~~~~~~~~~~~x_2+x_6=300$
$~~~~~~~~~~~~~~~~~~~x_1, x_2, x_3, x_4, x_5, x_6 \ge 0$
However, when I start with the dual simplex method, I cannot get an entering variable, since the $C_j-Z_j$ values of the first iteration are all $\gt 0$.
How do I solve this using simplex and/or dual simplex? Any help is appreciated.

You first need to transform this into normal form. Depending on how you learned it, you need to transform all constraints to the form $a\ge b$, or $a\le b$, where in $a$ you have variables and in $b$ only constants.
Transform $=$ into $\le$ and $\ge$ and from there you can easily transform this into normal form


Find and prove a linear algorithm that identifies all cycles and the length in a graph where each vertex has exactly one outgoing edge Consider a directed graph on n vertices, where each vertex has exactly
  one outgoing edge. This graph consists of a collection of cycles as
  well as additional vertices that have paths to the cycles, which we
  call the branches. Describe a linear time algorithm that identifies
  all of the cycles and computes the length of each cycle. You can
  assume that the input is given as an array A, where A[i] is the
  neighbor of i, so that the graph has the edge (i, A[i]).

I kind of have an idea of how to approach the algorithm but have no idea what to do with the proof of my algorithm. So far I'm thinking of marking the vertices I have traversed, and every time a vertex points back to the ones that I've traversed I count one cycle and move on to the next unvisited vertex.

Edit: what I ended up writing

For all element i of A:
    If i has not been visited (not in the map)
        Store the index i as key and order of traversal as value in a map
        Add i to an array
        Get A[i] as neighbor j
        While j is not in the map (not visited)
            Store the j as key and order of traversal as value in a map
            Add j to an array
            j’s neighbor becomes j
        Endwhile
        If resulting index j is not already part of a confirmed cycle
            Store array into confirmed cycle set
            Get j’s order of traversal of from map as o
            Output length of cycle by deducting o from array length
            Output part of the array that is the solution
            Store array from index array.size() - o to the end into solution set
        Endif
    Endif
Endfor

Unfortunately, your algorithm is not correct.
Let us call a directed graph where each vertex has exactly one outgoing edge a unique-outgoing graph.
What does a unique-outgoing graph look like?
It consists of some directed tree and some directed cycles, all of which are disjoint except that every root of the trees is also a vertex of some cycle. Or, it looks like a collection of directed cycles with some directed trees attached to them.

Here is an illustration,  which corresponds to the array $[5, 12, 3, 10, 9, 2, 3, 14, 14, 7, 2, 14, 5, 11, 4]$. There are two connected components in that graph. One component has the cycle of vertices 2, 3, 10 with two attached trees, the tree with vertices 2, 5, 0, 12, 1 and the tree with vertices 3, 6. The other component has the cycle of vertices 4, 9, 7, 14 with one attached tree, which has vertices 14, 8, 11, 13.
A simple algorithm
Here is the pseudocode, which is about as simple as possible.
Input: Array $arr[0], arr[1], \cdots, arr[n-1]$, such that the graph has the edge $(i, arr[i])$.
Procedure:

$round\leftarrow 0$.
Create array $first\_visited$ of $n$ zeros, where $first\_visited[i]$ will record the round at which $arr[i]$ is first visited. No element is visited at round 0.
Loop $i$ from 0 to $n-1$:
If $first\_visited[i]$ is 0:

Increase $round$ by 1.
$index\leftarrow i$
Loop the following as long as $first\_visited[index]$ is zero, i.e., $arr[index]$ is not visited.

$first\_visited[index]\leftarrow round$
$index \leftarrow arr[index]$

Now $first\_visited[index]$ must be non-zero.
If $first\_visited[index]$ is equal to $round$, a new cycle has been found! Record (or output) the cycle as well as its length by chasing the elements starting from $index$. Otherwise, do nothing.

When we run the algorithm on the aforementioned array, we will visit

0, 5, 2, 3, 10, 2 in round 1. The cycle 2, 3, 10 of length 3 will be recorded.

1, 12, 5 in round 2.

4, 9, 7, 14, 4 in round 3. The cycle 4, 9, 7, 14 of length 4 will be recorded.

6, 3 in round 4.

8, 14 in round 5.

11, 14 in round 6.

13, 11 in round 7.

Basically, the algorithm loops over all elements from index 0 to $n-1$. From each unvisited element, it makes an inner loop where it chases the next element via its outgoing edge, until it reaches a visited element. Each inner loop constitutes a round of chasing, during which each newly-visited element will be associated with the number of rounds happened so far.
The algorithm runs in $O(n)$ time with $O(n)$ space.
On your algorithm

I'm thinking of marking the vertices I have traversed, and every time a vertex points back to the ones that I've traversed I count one cycle and move on to the next unvisited vertex

You have got the basic idea. However, a new cycle might not be found when a vertex points back to a vertex that has been traversed, even if it is not part of any confirmed cycles. For example, consider the moment when your algorithm have visited 0, 5, 2, 3, 10, 2, 1, 12 and then 5 again. Vertex 5, although revisited, is not part of any cycle.
To ensure that a new cycle will be found when you revisited a vertex, the first visit to that revisited vertex must happen after the visit to the vertex i in your algorithm. That is why the variable $round$ is introduced in the above algorithm, which is, in fact, the only critical difference between the two algorithms.

Exercises
Here are a couple of exercises that help prove the above algorithm is correct.
Exercise 1. Show that there is exactly one cycle in each connected component.
Exercise 2. Prove the following invariant of the above algorithm. At the start of step 3.1, all visited vertices and edges so far form a unique-outgoing graph.


Algorithm for fewest number of moves with artificial minimum I asked a question recently, but I need to be able to add an artificial minimum number of steps that can be larger than the Dijkstra minimum.

To summarize, I built an undirected graph with edges representing possible moves of 1's, 10's, 100's, etc to get from one value to another.

public static UndirectedGraph<int, IEdge<int>> GetMinimumMovesGraph()
{
    var graph = new UndirectedGraph<int, IEdge<int>>();
    // load a graph that handles bases of 10's up to 10,000
    for (int i = 0;i <= 10000; i++)
    {
        for (int j = i+1; j <= 10000; j++)
        {
            // only add edges if difference is base of 10
            if (j - i == 1 || j - i == 10 || j - i == 100 || j - i == 1000)
            {
                graph.AddVerticesAndEdge(new UndirectedEdge<int>(i, j));
            }
        }
    }
    return graph;
}

So, the minimum distance from 46 to 121 is 8 steps/moves:

add 100 (146) - 1 move
subtract 10 (136) - 1 move
subtract 10 (126) - 1 move
subtract 1 five times (121) - 5 moves

Let's say the minimum number of steps through the graph has to be greater than 8 e.g. 10, 15, etc.

For example, a game application could stipulate that you must move at least 11 times in the problem above, so a possible answer could be:

all steps above (8 moves)
add 1 - (9)
subtract 1 - (10)
add 1 - (11) (we're at the minimum number of moves here, but we're at 122)
subtract 1 - (12) (correct answer)

So, these "dummy" moves are allowed, but aren't there scenarios where simple dummy moves may outnumber a shorter path to the answer?

I think I found an Eppstein implementation in C# that should give k-shortest paths, but can anyone explain the meaning of the vertices with two letters? e.g. What does the vertex "A,E" mean, and how can it have a single edge between "B,I"?

g.CreateEdges("A,E", "B,I", 20, "alpha");

What if I had to specify an odd or even number of moves?

Can this be done with the existing graph, or is there another graph structure that would support it? Weights, directions? Could I build the graph differently to describe the criteria e.g. not adding edges until certain number of edges exist back to the source, but then I would need Dijkstra on every iteration at build time

We construct a directed graph $G'$ with $V'=V \times \{0, \dots, k\}$ when $k$ is the lower bound on the path length.
For every edge $uv$ in $E$ and $i<k$ we add $(u,i)(v,i+1)$ and $(u,k)(v,k)$ to $E'$.

Now we search for a shortest directed path from $(s,0)$ to $(t,k)$ in $G'$ to find the shortest path from $s$ to $t$ in the original graph $G$.

The digraph $G'$ has $(k+1)n$ vertices and $(k+1)m$ edges. Hence, the running time is still polynomial

Searching for the shortest odd (or even) path works similarly. Indeed I think that any regular (as in NFA recognizable) constraint on the path can be solved like that.

Edit:
Note that the second entry in the tuples stays the same. To be more precise, consider any path $P=v_0v_1…v_kv_{k+1}…v_n$ on $G$ with length $≥k$. Then there is a corresponding path $P'=(v_0,0)(v_1,1)…(v_k,k)(v_{k+1},k)…(v_n,k)$ on $G'$.
Similarly, every path on $G'$ induces a path on $G$.


Random sampling in a polygon I would like to sample a uniformly random point in a polygon...

If sample a large number they'd be equally likely to fall into two regions if they have the same area.

This would be quite simple if it were a square since I would take two random numbers in [0,1] as my coordinates.

The shape I have is a regular polygon, but I'd like it to work for any polygon.

https://stackoverflow.com/questions/3058150/how-to-find-a-random-point-in-a-quadrangle

Triangulate the polygon
Determine in which of the triangles the point should lie (weights triangle areas)
Sample the point in the triangle as explained in this post


How does a wifi password encrypt data using WEP and WPA? How does the password that we enter (to connect to a wireless network) encrypt the data on the wireless network?

Through my reading I am not sure if the password that we enter is the same as the passphrase. If that is right then how can the passphrase generate the four WEP keys?

I understand how the four keys work in WEP and how they encrypt the data. Also, I know how WPA's keys encrypt the data but the only thing I have to know is:

  what is the benefit of the password that we enter to get access to the network, and how does this password help in encrypting the data?

WEP uses the stream cipher $RC4$ for confidentiality and the CRC-32 checksum for integrity. All data frames sent by a router in a WEP protected network are encrypted. When a router sends a packet, the following steps are executed.

The router picks a $24$-bit value called the initialization vector $IV$.
A new $IV$ is used for every packet.
The $IV$ is prepended to the key (password you enter) and
forms the per packet key $K$.
A CRC32 checksum of the payload is produced and appended to the
payload. This checksum is called an Integrity Check value ($ICV$).
The per packet key $K$ is fed into the $RC4$ stream cipher to produce a
key stream $X$ of the length of the payload with checksum.
The plaintext with the checksum is XORed with the key stream and
forms the cipher text of the packet.
The cipher text, the $IV$ and some additional header fields are used
to build a packet, which is now sent to the receiver.

Weaknesses of WEP and why to choose WPA

An $IV$ size of $24$-bits provides only $16$ million different key streams for a given WEP key. If the $IV$ is reused, the key stream for a given $IV$ is found and hence an attacker can decrypt subsequent packets that were encrypted with the same $IV$ even without knowing the WEP key.

Since there are only $16$ million $IV$ values, how the $IV$ is chosen makes a big difference in the attacks based on $IV$. As explained above, some implementations choose $IV$s randomly and some are assigned sequentially. With a randomly chosen $IV$, there is a $50\%$ chance of reuse after less than $5000$ packets and if assigned sequentially, collisions are inevitable if the values are re-initialized.

WEP’s integrity check field is implemented as a CRC-32 checksum, which is part of the encrypted payload of the packet. However, CRC-32 is linear, which means that it is possible to compute the bit difference of two CRCs based on the bit difference of the messages over which they are taken. In other words, flipping bit ‘$n$’ in the message results in a deterministic set of bits in the CRC that must be flipped to produce a correct checksum on the modified message. An attacker can therefore change a bit in an encrypted message and know which bit of the encrypted $ICV$ will change as a result.


Serial communication and parity bit I was revising Computer Science and I got these two doubts to which I've found contradictory answers on Google:

In a serial communication which bit is sent first?
When using a parity bit with ASCII is it set on the LSB or MSB?

Logically thinking I thought the answers should be 1- MSB first and 2 - set on LSB. Am I right?

Thanks in advance.

Gabriele

You may find contradictory answers because there are many kinds of serial communication protocols. Some are LSB first, some are MSB first.

For example, for the old RS232 standard and siblings, the LSB is transmitted first, and the parity may be transmitted after MSB. The MSB is usually the 7th bit or the 8th bit.
The parity is not part of the source data and is not weighted, so this is not really a MSB.

Another serial protocol, CAN, used in many automotive or other embedded applications, uses MSB first.

Some have more complex interpretations, mixing LSB- and MSB- first for data and CRC, mixing the order of bytes and the transmission order of bits. Example : IP over Ethernet : Big endian data, LSB-first bits, reversed CRC.


PDA with more than one initial state I'm wondering if PDAs with more than one initial states are also accepting context free languages.

If found that question on this site about NFAs and would like to know if this answer is also valid for PDAs if one defines a new single initial state and connects this with the former initial states using  $\epsilon : \epsilon \to \epsilon$ transitions?

PDAs that are allowed to have more than one initial state (let's call them PDAIs) are computationally equivalent to conventional PDAs:

Trivially, every conventional PDA can be considered as a PDAI that happens to have one initial state.
Every PDAI can be converted to an equivalent PDA with the process you describe.

So yes, PDAIs accept exactly the context free languages.


If X is in NP then $\overline{X}$ is in NP. True, false or "we don't know"? Why? If X is in NP then $\overline{X}$ is in NP.
True, false or "we don't know"? Why?

The answer is unknown.
If $X\in NP$ and $\bar X\in \mathcal{NP}$ than by definition it's a so called "co-NP" problem ($X\in \mathcal{coNP}$). It's still an open problem if $\mathcal{NP} = \mathcal{coNP}$.
An example:
Some problems are known to be in coNP. E.g. to decide if two number $n,m$ have a common divisor $>1$. This problem is in $\mathcal{NP}$ because there exists a polynomial verifier to check if a "proof" that some $n,m$ have common divisor $>1$ exists. The verifier accepts e.g. a number $p$ if $p>1$ and $p|n \land p|m$ the verifier accepts the proof. Now lets show that the complement of this language is also in $\mathcal{NP}$. We need to construct a verifier that accepts a proof that two numbers don't have a common divisor $>1$. You might notice that this is a bit more difficult but it can be done. The verifier accepts the prime factorization of $n$ and $m$ and checks that these are really the prime factorization of $n$ and $m$ and then that they don't have a common element.
Now try SAT...
Now if you take e.g. the $SAT$ problem and you try to find a verifier for $\overline{SAT}$ you have to find an algorithm that can given a certain proof verify that a boolean expression does not have a solution in polynomial time. If you think about it this is quite tricky (some how you have to deduce from the proof that none of the exponentially many variable assignments is valid) and it's currently not known whether $SAT\in \mathcal{coNP}$.


Number of ways n can be written as sum of at least two positive integers I found a solution in Python for this problem, but do not understand it. The problem is how many ways an integer n can be written as the sum of at least two positive integers. For example, take n = 5. The number 5 can be written as

4 + 1
3 + 2
3 + 1 + 1
2 + 2 + 1
2 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1

Here's a solution for given $n$.

# zero-based array (first index is 0)
ways = [1, 0, ..., 0] (n zeroes)

for i in 1, ..., n-1:
    for j in i, ..., n:
        ways[j] = ways[j] + ways[j-i]

print ways[n]

This solution is elegant and efficient, but unfortunately, I do not understand the logic. Can someone please explain the logic of this solution to the problem? Is there a way to make this algorithm easy to understand?

Let us denote the array ways after $t$ iterations of the outer loop by $w_t$. The recurrence implemented by the code is
$$
w_0(n) = \begin{cases}
1 & \text{if } n = 0, \\
0 & \text{if } n > 0.
\end{cases} \\
w_t(n) = \begin{cases}
w_{t-1}(n) & \text{if } n < t, \\
w_{t-1}(n) + w_t(n-t) & \text{if } n \geq t.
\end{cases}
$$
You can prove by induction that $w_t(n)$ is the number of representations of $n$ as a sum of natural numbers between $1$ and $t$ (without regard to order). (This is also the number of representations of $n$ as a sum of at most $t$ natural numbers.)

The code returns $w_{n-1}(n)$, which is the number of representations of $n$ as an arbitrary sum of natural numbers, other than the representation $n$.

As an aside, if you allow the trivial representation then you get the partition function. Using Rademacher's asymptotic formula, the partition function can be computed in time $\tilde O(\sqrt{n})$, much faster than your $\Theta(n^2)$ algorithm.


Worst case $O(n \ln n)$ in place stable sort? I am having trouble finding good resources that give a worst case $O(n \ln n)$ in place stable sorting algorithm.  Does anyone know of any good resources?

Just a reminder, in place means it uses the array passed in and the sorting algorithm is only allowed to use constant extra space.  Stable means that elements with the same key appear in the same order in the sorted array as they did in the original.

For example, naive merge sort is worst case $O(n \ln n)$ and stable but uses $O(n)$ extra space.  Standard quicksort can be made stable, is in place but is worst case $O(n^2)$.  Heapsort is in place, worst case $O(n \ln n)$ but isn't stable.  Wikipedia has a nice chart of which sorting algorithms have which drawbacks.  Notice that there is no sorting algorithm that they list that has all three conditions of stability, worst case $O(n \ln n)$ and being in place.

I have found a paper called "Practical in-place mergesort" by Katajainen, Pasanen and Teuhola, which claims to have a worst case $O(n \ln n)$ in place stable mergesort variant.  If I understand their results correctly, they use (bottom-up?) mergesort recursively on the first $\frac{1}{4}$ of the array and the latter $\frac{1}{2}$ of the array and use the second $\frac{1}{4}$ as scratch space to do the merge.  I'm still reading through this so any more information on whether I'm interpreting their results correctly is appreciated.

I would also be very interested in a worst case $O(n \ln n)$ in place stable quicksort.  From what I understand, modifying quicksort to be worst case $O(n \ln n)$ requires selecting a proper pivot which would destroy the stability that it would otherwise normally enjoy.

This is purely of theoretical interest and I have no practical application.  I would just like to know the algorithm that has all three of these features.

You can write an in-place, stable mergesort. See this for details. In the author's own words:

  A beautiful in place - merge algorithm. Test it on inverted arrays to understand how rotations work. Fastest known in place stable sort. No risk of exploding a stack. Cost: a relatively high number of moves. Stack can still be expensive too. This is a merge sort with a smart in place merge that 'rotates' the sub arrays.  This code is litteraly copied from the C++ stl library and translated in Java.

I won't copy the code here, but you can find it at the link or by checking the C++ STL. Please let me know if you would like me to try to provide a more detailed description of what's going on here.


decidability of artificial intelligence Not sure whether this is the correct place to post the question. some of my terms might not accurate.

currently AI is used for classification, inference, and so forth, is AI problem decidable? for example, given a dataset, prior/constraints and neural network, whether it can recognize a pattern (properly accuracy greater than some lower bound) is decidable? I understood the decidable problem is searching in a finite space. In terms of Machine learning techniques, the parameter space is finite, can I say it is decidable?

Also, Many problem solved by machine learning is quite different with traditional problem which has an algorithm, but machine learning problem doesn't have an algorithm format. And therefore, it is undecidable

Finally, for many proved math theorem, let's say the bound in some constrained problems (ex: Shannon limit in communication). Can I say such problem (constrained problem exists bound) is decidable, since people could find an algorithm (or math formula) to define limits.

For a problem to be approachable using what we presently call "AI methods", it has to be, at least theoretically, also solvable using "regular" methods (writing a set of instructions that solves it, line by line). Thus, decidable.

AI systems may create effective algorithms whose operation no human can understand. Also, by using AI methods we may find solutions to new problems, by accident, or discover that problems are decidable. These things do not contradict the affirmative above.

An algorithm exists that solves the problem.


What languages does a (1-way) quantum finite state automata recognize? Sorry if this is well known, but most of the research is paywalled.

So far I know that it is a subset of the regular languages, but I cannot seem to find any (available) research which pins it down.

Thanks!

Quantum finite automata (QFAs) are quantum counterparts of the usual finite automata.

In [1] it is shown that 1-way QFAs recognize a proper subset of the regular languages:

Proposition 6: Let $L$ be any language recognized by a 1QFA with bounded error. Then $L$ is regular.

Proposition 7: The language $L = \{a,b\}^*a$ cannot be recongized by a 1QFA with bounded error.

However in [2] :

... Our first results consider relations between 1-way QFAs and 1-way reversible automata.
Clearly, a 1-way reversible automaton is a special case of a QFA and, therefore, cannot
recognize all regular languages. It is a natural question whether 1-way QFAs are more
powerful than 1-way reversible automata. Interestingly, the answer depends on the accepting
probability of a QFA. If a QFA gives a correct answer with a large probability (greater than
7/9), it can be replaced by a 1-way reversible automaton. However, this is not true for 0.68...
and smaller probabilities.

Then, we show that QFAs can be much more space-efficient than deterministic and even
probabilistic finite automata. Namely, there is a 1-way QFA that can check whether the
number of letters received from the input is divisible by a prime p with only $O(\log p)$ states
(this is equivalent to $\log \log p$ bits of memory). Any deterministic or probabilistic finite
automaton needs p states ($\log p$ bits of memory). We think that this space-efficient quantum
algorithm may be interesting for design of other quantum algoritms as well....

For a quick introduction see:

[1] Attila Kondacs and John Watrous, On the Power of Quantum Finite State Automata;
[2] Andris Ambainis and Rusins Freivaldsy, 1-way quantum nite automata: strengths, weaknesses and generalizations;
[3] Abuzer Yakaryilmaz and A. C. Cem Say, Unbounded-error quantum computation with small space bounds;
[4] Andris Ambainis and Abuzer Yakaryilmaz, Superiority of exact quantum automata for promise problems;
[5] Cristopher Moore and James P. Crutchfield, Quantum Automata and Quantum Grammars;
[6] Andris Ambainis, Quantum Finite Automata.


How to prove that a language is not context-free using pumping lemma I'm trying to prove that that language isn't a context free:

$ L = \{ w11w \mid w\in \Sigma^* = \{0,1\}\}$

I succeed to prove that $L = ww$ isn't context free, but not the language above.   What am I doing wrong?

Here is the simplest way. Suppose that your language were context-free, and consider its intersection with $0^*(10)^*110^*(10)^*$. Applying further simple manipulations, you reach the language $\{a^nb^mc^nb^m : n,m \geq 0\}$, which is known not to be context-free.

If you insist on using the pumping lemma, perhaps you can get inspiration from this argument.


Calculating the set field of associative cache In this example:

Assume a system’s memory has 128M words. Blocks are 64 words in length
and the cache consists of 32K blocks. Show the format for a main
memory address assuming a 2-way set associative cache mapping scheme.
Be sure to include the fields as well as their sizes.

The following is supposed to be the solution:

Each address has 27 bits, and there are 7 in the tag field, 14 in the
set field and 6 in the word field.

I understand how the word field was calculated (2^6 = 64), but I don't understand how is the set field 14?.
Shouldn't the answer be 8?
Block size is 64 words, to find the number of sets we divide total number of blocks 32K by set size which is 64*2=128B (multiply by 2 since it's 2-way), my calculation should be correct, am I missing something?

32KB/(64*2)B = 32KB/128B = 256 = 2^8
(Which implies that we need 8 bits for the set field)

The memory has $128$M words = $2^{7+20}$ = $2^{27}$ words. Hence it needs needs $27$ bits for address space.

Each block has $64$ words, so the block offset = $2^6$ words. So Block offset field can be represented by $6$ bits.

Number of lines in the cache = $\frac{Cache Size}{Block Size}$ =Number of blocks = $32$K blocks = $2^{5+10}$ = $2^{15}$ blocks.

Number of sets in the cache = $\frac{Number of Lines}{Set Associativity}$ = $2^{15}$ blocks / $2$ blocks per set = $2^{14}$ sets. Hence number of bits to represent set field = $14$ bits.

Number of tag bits = $27 - (14+6) = 7$ bits.