title: What is running time of an algorithm?

text:
# Question
Title: What is running time of an algorithm?
What do we mean by running time of algorithms? when we say running time of bubble sort is O($n^2$), what are we implying? Is it possible to find the approximate time in minutes/seconds from the asymptotic complexity of the algorithm? If so, how ?

# Answer
> What do we mean by running time of algorithms?

Depends on who is talking. It can mean everything from actual time in seconds to execution count of some asymptotically dominant instruction. Things get muddied further by widespread overuse of Landau notation.

Also, one typically distinguishes at least worst, average and best case.

> when we say running time of bubble sort is $O(n^2)$, what are we implying?

Here we use that the actual running time is in $\Theta$ of the execution count of an asymptotically dominant operation. We can rigorously show that Bubblesort takes $\Theta(n^2)$ comparisons (in fact, we can get the *exact* number for worst-, best- and average case), that all other operations happen only $O(n^2)$ often, and thus the real running-time has to be in $\Theta(n^2)$ as well.

That assumes that our machine model (usually RAM) and the real machine differ only by constant factors (unknown to us). If you analyzed formally on the TM model, you could not carry over Landau bounds as easily. In general, converting between (reasonable) models can add a polynomial factor.

> Is it possible to find the approximate time in minutes/seconds from the asymptotic complexity of the algorithm?

No, not at all. Assuming that by "asymptotic complexity" you mean a Landau bound on the runtime function $T$,

1. you only know the behaviour of T for $n \geq n\_0$ for *some* $n\_0$ that may be larger than anything you ever see in inputs;
2. you only know the behaviour up to a constant factor $c$;
3. you only know the type/degree of the leading terms but lower terms can be significant (i.e. the absolute error of your bound can tend to infinity, even if you have a tight estimate of the constant factor of the leading term).

Even if you *knew* $n\_0$, lower-order terms and all constant factors,

1. these bounds are usually not tight and
2. the analysis gives you the execution of some operations, not actual time.

The only way to use formal analysis for predicting actual running times is

1. analysing the execution counts for *all* statements,
2. analysing up up to small error terms, and
3. know how many (nano)seconds each statement takes.

Sometimes we can do 1. and 2. but 3. is very, very tough for real machines -- which is why everybody in TCS analyses on clean machine models.
> 8 votes

# Answer
Asymptotic complexity is not used to find actual running times of algorithms but as a comparison tool to find out which algorithm is more efficient. When you say $Algorithm\_1$ is O(nlogn) as opposed to $Algorithm\_2$ which is O($n^2$) you simply mean $Algorithm\_1$ is a better algorithm in terms of run time complexity.

Now coming to your question about finding actual time taken here's a possible solution.
Say your algorithm's running time is approximated as a function of the form T(n)=a$n^2$, now you know beforehand that T(100)=10 seconds. Hence you substitute T(100) and get $a\*10000=10$, or $a=1/1000$.
Now you want to find out the running time when the i/p size is 200(say). You just substitute 200 in T(n)=$1/1000$\*$a^2$ and get the required time in seconds.
> -2 votes

---
Tags: algorithm-analysis, terminology, runtime-analysis
---


# Question
Title: Why does 9 qubit Shor code have distance 3?
Distance of a Stabilizer code($S$) is defined by minimum weight of an element in $N(S)-S$ .

Why 9 qubit Shor code has distance 3?

Is there a way to directly see $N(S)-S$ from $S$?

# Answer
> 1 votes
Another way to see this is by using $$\frac{N(S)}{S} \cong P\_k $$ Here $k=1$ and we actually know that $\bar{X}=ZZZZZZZZZ$ and $\bar{Z}=XXXXXXXXX$ also we know $S$ and thus we know $N(S)$

Hence we can directly find distance by "minimum weight element in $N(S)-S$"

# Answer
> 1 votes
Distance 3 means that an error operator acting on 3 qubits maps a valid code-state to another valid code-state. For the Shor code, an example would be a simultaneous phase flip on the 1st, 4th and 7th qubits ($Z\_1Z\_4Z\_7$).

You can easily check that $Z\_1Z\_4Z\_7∉S$, but that it commute with $S$, hence is part of $N(S)$.

---
Tags: quantum-computing
---


title: Is this some kind of hashing?

text:
# Question
Title: Is this some kind of hashing?
Say I have $n$ vectors $\\{ z\_i \in \mathbb{R}^D\\}\_{i=1}^n$ (where $n$ is very large and hence I can't do any calculation which scales as $n$) and I want to create $n$ vectors $\\{x\_i \in \mathbb{R}^d \\}\_{i=1}^n$ with $d$ as small as possible, such that $\forall i,j \<z\_i,z\_j\>$ is either very close to $\<x\_i,x\_j\>$ OR w.h.p $ \<z\_i,z\_j\> = \<x\_i,x\_j\>$.

* Is there a standard answer known for this - by maybe using hashing?
* One possible way might be to either deterministically or randomly from some distribution pick some $D-d$ coordinates and drop those coordinates from each $x\_i$ to get the corresponding $z\_i$ such that for each pair on either side either the inner-product is well approximated or is equal with high-probability over the way the coordinates are sampled. Is such a way of sampling known?

---

For the second option one other way to think would be to pick an unit magnitude gaussian vector at random $g \in \mathbb{R}^d \subset \mathbb{R}^D$ and to define $x\_i$ as the projection of $z\_i$ along $g$. Then indeed one has that $\mathbb{E}\_g\[ \<x\_i,x\_j\>\] = \<z\_i,z\_j\>$.

But can this above be shown to be true with high concentration or be derandomized?

# Answer
I think your "possible way" is a known variant of "locality sensitive hashing", which is what you're looking for, I suspect.
> 1 votes

---
Tags: optimization, machine-learning, computational-geometry, hash, hashing
---


title: Simple pseudorandom split of data

text:
# Question
Title: Simple pseudorandom split of data
I want to split my data into $n$ approximately equal parts. Which simple hash functions will ensure that the number of $x$ with $h(x)\equiv i\pmod{n}$ is approximately equal for each $i$?

# Answer
Assuming the number of data points is much larger than the number of buckets:

The theory answer: any universal hash function will suffice to ensure that the parts are roughly similar in size (on average, in expectation, over the random choice of hash function).

The pragmatic answer: any hash function that provides roughly equidistributed outputs is likely to suffice. Thus, any hash function that doesn't suck will normally be fine in most cases (e.g., as long as the inputs aren't adversarially chosen and as long as the hash function doesn't have serious problems).
> 2 votes

# Answer
I do not think there is such a hash function unless the number of input points is much larger than $n$, or much smaller than $n$, or your hash function is constructed based on your data.

If your input data has the same size as the number of buckets, then with high probability, one of your buckets will have $0$ elements in it and one will have $\Theta(\log n/\log \log n)$.

According to "Balls into Bins - A Simple and Tight Analysis", something similar happens even when the number of items is as small as $n/\log^c n$, for any $c$.

If you see all of your data ahead of time, you can pick a hash function $g$, use it to make a open-addressed hash table, then let $h(x)$ be defined as the location of $x$ in the hash table you made with $g$, but storing this hash table requires $\Theta(n)$ space and it does not work to hash values that it hasn't seen before.
> 2 votes

---
Tags: hash
---


# Question
Title: Does the SIFT feature be calculated in the original image or the corresponding octave(s)?
1. Given there are 4 octaves(the 1st octave is the original image, the 2nd octave is half size of the original image, and so on.), does SIFT calculate the keypoint's orientation in the original image or the octave the keypoint extracted from?

For example, there is a keypoint found in the 3rd octave. Does SIFT calculate its orientation in the original image or in the 3rd octave (one fourth of the original image size)
2. Similar to 1st question, does SIFT calculate the keypoint descriptor in the original image or the octave the keypoint extracted from?

# Answer
> 1 votes
1. The orientation of a keypoint should be computed on the original image, smoothed accordingly to the scale of that keypoint. Luckily we already have the Gaussian pyramid at our disposal, so we can simply select the closest level of this pyramid and compute the orientation there. In other words, if you detect a keypoint in the 3rd octave, then you compute its orientation in the 3rd octave of the *Gaussian pyramid*.
2. And the same for descriptors.

---
Tags: algorithms, image-processing, computer-vision
---


# Question
Title: Prove that TM does not decide this language
So my problem is how can I show that this TM does not decides this language.

$$L = \\{a^nb^nc^n\ |\ n \geq 0\\} $$

It might be a basic problem and seem silly to you but still I do not know how to prove that this TM does not halt for any input

# Answer
> 0 votes
The easiest way is to provide a counter example, i.e.

* some $w \in L$ that $M$ does not accept, or
* some $w \not\in L$ that $M$ accepts.

There are two ways to find such.

1. Understand how $M$ works and use this to find such $w$ directly.
2. Try *all* strings in some order, e.g. lexicographically, until you find such $w$.

Note that if $L \subseteq L(M)$ or $L(M) \subseteq L$, only *one* of the two types of counterexamples exist.

---
Tags: formal-languages, turing-machines, automata
---


# Question
Title: Insertion sort with pairs of numbers already in order
I am currently attempting to work out the number of comparisons that is done by insertion sort when the elements are already in sorted pairs, for example

$$4,5,22,23,1,2,19,20, \dots$$

Currently working to solve for the worst and average case number of comparisons done when a sentinel is used.

For worst case where each pair is out of order, what I've worked out is that the pattern for comparison goes $1 + 3 + 3 + 5 + 5 ... + n + n$, leading to a summation

$$\sum\_{n=2}^{n/2}(2n-1)(2)$$

and I solved it to $(n^2+4/2) - 3 - (n-2)$.

Does this look about right? I'm now having trouble attempting to solve for the average case. Any idea how to go about this? Thanks for any help

# Answer
> 1 votes
Insertion Sort is one of the algorithms which only swaps adjacent elements if they are out of order. Therefore, it's performance is intimately tied to the number of *inversions* in the input; see e.g. here for a detailed explanation.

Observe that in your class of inputs, the maximum number of inversions is not $n(n-1)$ as in the unrestricted case, but one less for each pair of elements. Since there are on average $\Theta(n^2)$ many inversions in random permutations, you'll have as many in your ordered-pairs permutations, assuming uniform randomness, because you lose at most linearly many in each.

For the details, find an analysis of Insertion Sort that rests on the number of inversions (e.g. in a good textbook) and change the numbers; the calculations should mostly remain the same.

# Answer
> 0 votes
Insertion sort is $\Theta(n^2)$ in the average case. For your kind on input, consider all elements in odd places. You can simulate an insertion sort on these elements by looking at what insertion sort is doing on the entire array. This simulation loses some constant factors, but this still shows that on average you get $\Omega(n^2)$ comparisons. Since you have a matching worst-case upper bound, you get that on average, insertion sort takes $\Theta(n^2)$ on your special arrays.

---
Tags: algorithms, algorithm-analysis, runtime-analysis, sorting
---


title: CPU and GPU differences

text:
# Question
Title: CPU and GPU differences
What is the difference between a single processing unit of CPU and single processing unit of GPU?
Most places I've come along on the internet cover the high level differences between the two. I want to know what instructions can each perform and how fast are they and how are these processing units integrated in the compete architecture?
It seems like a question with a long answer. So lots of links are fine.
In the CPU, the FPU runs real number operations. How fast are the same operations being done in each GPU core? If fast then why is it fast?
I know my question is very generic but my goal is to have such questions answered.

# Answer
This are not Real numbers as $\mathbb{R}$, but at this point - CPU has double precision floating point numbers, GPU very low number of units processing them, floats on GPU are *halfs*.
This is due to graphics (this was the main goal before parallel processing), where results are rounded to display, so speed vs accuracy tradeof went that way.
GPU core frequencies are smaller than CPUs, number of operations is very limited on GPU (boosted by video decoder), and there is a huge difference in branch prediction - CPU has very long and complex prediction, while GPU just recently got it added.

Single core on GPU: it is Streaming Multiprocessor (there are about 4 - 16 per card), it includes cuda cores (which is about 32-64), and they work in lock-step, so it differs from CPU threads (not locked).

It is hard to compare like this, but in short - single core on GPU is still parallel unit working slower than CPU core, less memory, registers and instructions than CPU, with very short branching prediction and preferable *half* floats, nowadays normal floats but having about one-two processing units for double precision, some time ago integer operations were slower on GPU (not onlu by frequency) - but this changed recently.

The same operation on floats - they are slower on GPU than CPU due to frequency.

You might be interested in AMD architecture, Nvidia architecture and Intel architecture to compare instructions set and hardware differences further.
> 2 votes

# Answer
A GPU (graphics processing unit) is designed for accelerating images and graphics in computer systems. It's designated in parallel architectures and efficient algorithms with hundreds to thousands of homogeneous cores that speedup data processing (for graphics and images traffic patterns) in parallel and get it done faster and more efficient than a general-purpose CPU. For example, NVidia is one of the leaders in GPU processors manufacturing. As my best knowledge, NVidia has announced its Tesla K40 with 2880-core integrated in a single-chip and these cores are served as specific purposes in graphics processing in parallel.
> 0 votes

# Answer
To be simpler with the words CPU (central processing unit- a purpose processor) has always been called the brains of the PC. But nowadays, that brain is being improvised by another part of the computer i.e the GPU (graphics processing unit).

Basically GPU's advanced features were only used in 3D and high end gaming. But these days GPU plays a vital role more importantly in speeding up computational workloads. Read more at NVIDIA CEO Jen-Hsun Huang’s latest blog post for more deeper knowledge of GPU.

CPU: it contains fewer number of cores with a lot of cache memory and can handle few threads at a time. whereas GPU has power to handle thousands of threads.A CPU generally has higher operating frequency and is designed for general purpose use and vice versa with GPU.But the combination of both the features will contribute to better performance and efficiency.
> -2 votes

---
Tags: computer-architecture, parallel-computing
---


# Question
Title: How probable is a deadlock in the dining philosophers problem
I created this simulation of the dining philosophers problem, but did not manage to initialize it with four philosophers without running into a deadlock:

\*Philosophers are represented by black beads. They think when running in small circles and eat when running in bigger circles. Forks are represented by yellow beads. The number of meals are counted.

Might it be the case that for $N=4$ participating philosophers a deadlock must inevitably be reached? Or can a situation be described in which four philosophers can eat for ever and ever?

I am looking for a quantitative model and analysis of the dining philosophers problem.

Let $N$ be the number of philosophers. Let the problem be implemented as an algorithm that takes as inputs the set $T\_k$ of partial functions $t: \[N\] \rightarrow \[k\]$ with $t(i)$ being the point in time when philosopher $i$ starts trying to pick the fork to his left (maybe never). The algorithm stops when it detects a deadlock or an oscillating state in which a philosopher starves.

I wonder especially about the probability $p\_{stop}^{(k,n)}$ that the algorithm will stop, depending on the number $n$ of philosophers that join the diner, $n \leq N$.

$$p\_{stop}^{(k,n)} = \frac{|\text{functions $t \in T\_k^n$ for which the algorithm stops}|}{|T\_k|}$$

with $T\_k^n$ the functions $t\in T\_k$ with $|\text{dom}(t)| = n$.

# Answer
the dining philosopher problem seems to be somewhat of a pedagogical "toy" example of concurrency and (dead)locking concepts for educational purposes. however it is studied seriously in some literature and there are some performance analyses of its probability of deadlock scenarios. here are some examples of quantitative models and performance analysis and other frameworks on the problem which attempt to consider the probability of deadlocks from theoretical derivations and observed scenarios (simulations etc).
> 4 votes

# Answer
I don't know what algorithm the philosophers follow, but let's assume that deadlock is reached if all philosophers try to start eating at the very same time. Since your time is discrete, under any reasonable probability distribution over the "thinking times", it will necessarily (almost surely) eventually happen that all philosophers try to start eating at the very same time (exercise, which also includes formulating the problem properly).
> 3 votes

---
Tags: concurrency, deadlocks
---


# Question
Title: Is Bresenham's Line Drawing algorithm still used today?
If so, I cannot find any examples of this.

Edit: By "used", I mean are they still used in rendering in games or whatever. I haven't seen it used anywhere except in MS Paint because Wu's algorithm looks way better (yet is still not expensive as far as I know).

# Answer
Google Scholar reports hundreds of mentions since 2012.

Specifically, the patents

explicitly mention the algorithm, if only in exemplary fashion.

Further searches, e.g. on YouTube, suggest persisting interest in the algorithm; it still seems to be in the mainstream.

That does, of course, not mean that there are no better ones, or that professional products use it still. But since proprietary devices are usually closed-source, we won't be able to answer *that* question with confidence.
> 4 votes

# Answer
This ia a bit like comparing apples and oranges.
Good written Bresenham algorithm works like Wu algorithm without antialiasing. It can be used to draw lines, ellipses and circles with very high speed using only integer arithmetic.
Among all line rasterizers Bresenham is the fastest (DDA, naive, etc.).

There are different purposes - Wu is used to draw plausible looking not jagged lines, Bresenham is used to ensure fast continous lines. Apart of taking part where only outline might be antialiased, there is no point in doing so on the inside of thick geometric primitive. Moreover good implementation of Wu algorithm also uses special cases to handle all inputs.

In the case of variable thick line there is Murphys modification built on top of Bresenham algorithm.

2D libraries use internaly Bresenham algorithm and Wu giving chance to choose (some kind of *antialiasing flag*). Even OpenGL/WebGL without flags produced Bresenham line (I haven't checked internals, just matched the output). Simple GDI and Java used it internally (new versions might use something different).

But there is more than that. There are situations where you have discrete points (like from mouse events) and want to get continous path - there is no use in antialiasing.

Practical algorithms like RoadMap *(there is only mention that Bresenham is used for connectivity check)* or moving on discrete lattice, like configuration space for robots, CNC represents obstacles or material to be milled as pixels/voxels - there is no need for antialiasing but one *must be sure* that no obstacle was hit - this is where continous and fast properties of Bresenham are used.

Summing it up, there are lots of algorithms that depend on Bresenham, use it internally or are just modified versions of it.
Depending on usage, not always antialiasing is needed, so using Wu as better is just waste of resources.

*If some references are needed beyond what Raphael provided (he already made it clear) I will update some links upon encounter.*
> 1 votes

---
Tags: algorithms, reference-request, applied-theory
---


title: Lookup complexity in B-trees [Database]

text:
# Question
Title: Lookup complexity in B-trees [Database]
Given that:

```
B = n/R blocks in the file
2d index records per block (blocking factor): 2d > R
an extra block access from the index to the datafile

```

I am not able to wrap my head around as why the lookup would incur an cost\[number of block accesses\] of
less than or equal to

```
2 + log(base to d) (n/2)

```

# Answer
Nvm, figured it out. One access would be required to find the root of B-tree. And then Logd(n/2) access to find the correct leaf containing the right key. And then another another block access to reach the requested data for the given key.
> 0 votes

---
Tags: search-trees, databases, balanced-search-trees
---


title: Two dimensional parity check

text:
# Question
Title: Two dimensional parity check
Firstly, I would like to apologize if I misplaced this topic / i think the theory of coding is close to CS /

I am little bit confused right now, in the school we were learning about Hamming's code, Block codes etc.

I was given a homework, in which I should explain how does the two dimensional parity check finds 3-bit errors. I think the two-dimensional parity check does finds 3-bit erros, but it can't (in every case) correct it.

The second thing is, we were learning about hamming distance and there is a rule, which says that block code finds t-bit error when this equation is right:

t \< d (and d stands for hamming distance, its minimum distance between the 2 code words / t stands for t-bit errors).

So for example: a = 110, b = 101, c = 100

```
1 1 0 | 0
1 0 1 | 0
1 0 0 | 1
_ _ __
1 1 1   1

```

The numbers behind the 'bars/underscores' are the parity-check bits, it means that in each column/row is even count of number 1.

So the minimum distance equals to 2. That means according to the rule t \< d, that this code can detect only a t-bit error, which means 1 ( but that's not true, because it can detect 3 bit erros).

How should I explain that?.

Thanks.

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

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

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

are the only possibilities.

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

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

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

So the array code can correct 3 errors.

---
Tags: information-theory, coding-theory, error-correcting-codes
---


# Question
Title: Examples of context sensitive syntactic constructs (statements)
So, I am implementing a context sensitive syntactic analyzator. It's kind of an experimantal thing and one of the things I need are usable syntactical contructs to test it on.

For example, the following example isn't possible to parse using standard CFG (context free grammar). Basically it allows to declare multiple variables of unrelated data types and simultaneously initialize them.

```
int bool string number flag str = 1 true "Hello";

```

If I omit few details, the language used can be formally described like this:

`L = {a<sup>n</sup>b<sup>n</sup>c<sup>n</sup> | n >= 1}`

So, I would appreciate as much of similar examples as you can think of, ideally something from the area of programming languages.

Also, I am aware that current programming languages and their compilers are context sensitive, mainly thanks to semantic analysis, so I would like to state I am not looking for things like:

```
type checking
is variable declared?

```

I would preffer the examples to be actual syntactic constructs like the shown declaration example above.

Thanks in advance ;).

# Answer
Here are three context-sensitive syntaxes actually found in programming languages. I don't believe I've ever seen a language which has types, names and values distributed as per your example, but it could certainly exist, and I'm sure there are even less readable syntaxes which are possible. The following are at least somewhat readable:

1. Syntactic whitespace, as per Python or Haskell. This is usually handled with a context-sensitive lexical scanner rather than a context-sensitive grammar, but it is certainly context-sensitive, and it *could* be handled with a context-sensitive grammar if you had the machinery available. (In fact, it could be cleaner to handle it in the parser, especially for languages like Haskell in which layout-sensitive parsing is optional. \[Note 1\])
2. Multi-dimensional array literals. Here, I'm not talking about languages which implement heterogeneous one-dimensional arrays as first-class types, so that an array can be an element of another array; in that case, there is no requirement that a multi-dimensional array be regular. Rather, I'm talking about languages in which multi-dimensional arrays must be regular, and so an irregular literal is a syntax error:

```
julia> [2 3 4;5 6 8]
2x3 Array{Int64,2}:
 2  3  4
 5  6  8

julia> [2 3 4;5 6]
ERROR: hvcat: row 2 has mismatched number of columns
 in hvcat at abstractarray.jl:993

```

That's a bit of a cheat, because the Julia syntax above is really syntactic sugar for a call to `hvcat`, as indicated in the error message. But it *could* have been syntactic. Fortress -- the syntactic collector's favourite vapourware language -- proposed syntactic array literals:

> The parts of higher-dimensional matrices are separated by repeated-semicolons, where the dimensionality of the result is equal to one plus the number of repeated semicolons. Here is a 3 x 3 x 3 x 2 matrix:

```
[ 1 0 0
  0 1 0
  0 0 1   ;;   0 1 0
               1 0 1
               0 1 0   ;;   1 0 1
                            0 1 0
                            1 0 1
  ;;;
   1 0 0
   0 1 0
   0 0 1   ;;   0 1 0
                1 0 1
                0 1 0   ;;   1 0 1
                             0 1 0
                             1 0 1 ]

```

> The elements in a matrix expression may be either scalars or matrices themselves. If they are matrices, then the elements along a row (or column) must have the same number of columns (or rows), though two elements in different rows (columns) need not have the same number of columns (rows). A scalar is treated as a one by one matrix. (Quoted from *The Fortress Language Specification* by Guy L. Steele et al, §2.3.19, p. 21)
3. Agreement between parameter count in function prototypes and number of arguments in function calls. Perhaps this fits in your concept of "type checking", and I don't think it adds anything interesting to your problem set. But it is certainly context-sensitive.

### Notes

1. I stumbled upon *Layout-sensitive Generalized Parsing* by Sebastian Erdweg, Tillmann Rendel, Christian Kästner, and Klaus Ostermann. while writing this answer, but I haven't read it. It seems to propose a usable formalism for layout-aware parsing.
> 6 votes

---
Tags: programming-languages, context-sensitive, language-design, syntax
---


# Question
Title: How to Convert a Directed Graph to an Undirected Graph (Adjacency Matrix)
Given an adjacency matrix, what is an algorithm/pseudo-code to convert a directed graph to an undirected graph without adding additional vertices (does not have to be reversable)?

similar question here

# Answer
> 2 votes
Note that for an undirected graph, the adjacency matrix is symmetric, i.e. `A[i,j] == A[j,i]`.

From this, we can see that we can simply compute the new value of `A[i,j] = A[j,i]` depending if `A[i,j]` or `A[j,i]` is set. Assuming the graph is unweighted, we can do:

```
for i from 0 to n-1
    for j from 0 to i
        if A[i,j] == 1 OR A[j,i] == 1
            A[i,j] = A[j,i] = 1
        else
            A[i,j] = A[j,i] = 0

```

Note that we only have to consider 1 + 2 + 3 + ... + n-1 entries since the resultant adjacency matrix is symmetric.

If we have a weighted graph, we now have the problem of which edge weight to take as the new undirected graph edge weight. For example, if w(2,5) = 5 but w(5,2) = 10, the resultant edge weight is ambiguous. However, this is enough for you to figure out what else you need from here.

---
Tags: algorithms, graphs, adjacency-matrix
---


# Question
Title: Would incrementing the min cut edges by 1 increase the max flow by 1 as well?
Given the theorem that max flow \<= min cut, Would incrementing the min cut edges by 1 increase the max flow by 1 as well?

# Answer
Given the theorem that max flow **=** min cut, that would indeed be the case (if all capacities are integers).

*If* you make *all* min-cuts larger. There may be more than one.

To be clear: if you increase the capacity of *all* edges in *all* min-cuts, the max-flow may increase by more than one. At least one (assuming integer capacities), but then yet another cut may be minimal.

If you increase the capacity of each min-cut by one, the max-flow increases by one (again assuming integer capacities).
> 2 votes

---
Tags: algorithms, graphs, max-flow
---


# Question
Title: Does concatenating two empty strings result in an empty string?
I have a question on the multiplication of sets of words as it is defined in Cohen's Intro To Computer Theory. He gives the definition: if S and T are sets of strings of letters, the product of the sets, ST = {All combinations of string from S concatenated with strings from T}.

The definition is easy enough to understand. But after giving a few standard examples, he gives an example along the lines of: S = {$\alpha $ a b}, T = {$\alpha $ a}

ST = {$\alpha $ a a aa b ab}

(I"ve used $\alpha$ to denote the empty string)

Basically, why is $\alpha \alpha$ = $\alpha$ in the product set and $\alpha$a = a ?

# Answer
> 1 votes
An empty string isn't zero, if you're looking at it and expecting αa=0 or αa={} then you're thinking about it like you would integers. Which if they were, you'd be correct. But you have to think about it in the form of strings, which is what you're dealing with.

Think of it like this,

α=' '
a='a'

so 'a'+ ' ' ='a'

and ' '+' '=' '

---
Tags: regular-expressions
---


# Question
Title: Count in relational algebra using Ω = { π, σ, ⋈, ⋉, β, x, ∪, ∩ , - }
```
schema(author)={name, newspaper}

```

The table contains a list of authors. Each author works for a newspaper. So a single newspaper may employ multiple authors. How can I get the names of the newspapers that have at least two authors working for them? My algebra consists of:

```
Ω = { π, σ, ⋈, ⋉, β, x, ∪, ∩ , - }

```

There is no count in the algebra. So I am limited to the above Ω. Any ideas how I can implement counting?

# Answer
Hint: to express "the set $S$ has size $\ge 1$" in propositional logic (without using the "size" operator), you can write $\exists x . x \in S$. How would you express "the set $S$ has size $\ge 2$"? Does that give you any ideas for how to use relational algebra to solve your question?
> 2 votes

---
Tags: database-theory, relational-algebra
---


# Question
Title: Cyclic Redundancy Check Codewords Finding the Original Message
So I have the received transmitted message in polynomial form as $$T'(X) = X^{15}+X^{13}+X^8+X^7+X^4+X^3$$ and the error polynomial as $$E(X) = X^{16}+X^{13}+X^3$$ and the generator polynomial as $$G(X) = X^4+X^3+X+1.$$

I am trying to find $T$ before it is transmitted. It is my understanding that the received transmitted message is the original codeword transmitted ($T$) plus the error polynomial ($E$), but in this case $T'$ is less than $E$, so when I subtract to find $T$, I get a negative polynomial. What am I doing wrong?

# Answer
> 1 votes
You should do arithmetic modulo 2. Modulo 2, $-1$ is the same as $+1$.

---
Tags: hamming-code, crc
---


# Question
Title: How correct was Justin Trudeau's explanation of Quantum Computing?
Recently, Canada's Prime Minister - Justin Trudeau - gave an impromptu explanation of Quantum Computing, much to the crowd's astonishment. I certainly thought that I "got" Quantum Computing a little bit more, even though it was a simplified explanation.

Here's the YouTube link to the actual press conference.

https://www.youtube.com/watch?v=Eak\_ogYMprk

However, some are claiming that we shouldn't jump for joy at his explanation.

I'm wondering, as someone who doesn't exactly understand Quantum Computing, **how accurate was Justin Trudeau's explanation of Quantum Computing?**

# Answer
> 7 votes
Trudeau's explanation wasn't wrong, but it also wasn't very informative.

Scott Aaronson, a well-known quantum computational complexity theorist, made a blog post discussing it:

> What marks does Trudeau get for this? \[...\] Trudeau doesn’t really assert much here: basically, he just says that normal computers work using 1’s and 0’s, and that quantum computers are more complicated than that in some hard-to-explain way. \[...\]
>
> \[...\] I’d grade Trudeau’s explanation as substantially more accurate than what you’d get from a typical popular article. \[...\] clearly suggests that he knows it’s more subtle than just “0 and 1 at the same time,” and he also knows that he doesn’t really get it and that the journalists in the audience don’t either. \[...\]
>
> \[Grade: **B+**\].

There's a lot of discussion in the comments of that post.

---
Tags: quantum-computing
---


# Question
Title: How to find middle element of linked list in one pass?
One of the most popular question from data structures and algorithm, mostly asked on telephonic interview.

# Answer
> 24 votes
By cheating, and doing two passes at the same time, in parallel. But I do not know whether the recruiters will like this.

Can be done on a single linked list, with a nice trick. Two pointers travel over the list, one with double speed. When the fast one reaches the end, the other one is half-way.

# Answer
> 7 votes
If it's not a doubly linked list, you could just count and use a list, but that requires doubling your memory in the worst case, and it simply won't work if the list is too large to store in memory.

A simple, almost silly solution, is just increment the middle node every two nodes

```
function middle(start) {
    var middle = start
    var nextnode = start
    var do_increment = false;
    while (nextnode.next != null) {
        if (do_increment) {
             middle = middle.next;
        }
        do_increment = !do_increment;
        nextnode = nextnode.next;
    }
    return middle;
}

```

# Answer
> 6 votes
Elaborating on Hendrik's answer

If it's a doubly linked list, iterate from both ends

```
function middle(start, end) {
  do_advance_start = false;
  while(start !== end && start && end) {
     if (do_advance_start) {
        start = start.next
     }
     else {
        end = end.prev
     }
     do_advance_start = !do_advance_start
  }
  return (start === end) ? start : null;
}

```

Given `[1, 2, 3] => 2`

```
1, 3
1, 2
2, 2

```

Given `[1, 2] => 1`

```
1, 2
1, 1

```

Given `[1] => 1`

Given `[] => null`

# Answer
> 3 votes
Create a structure with a pointer capable of pointing to nodes of linked list and with an integer variable which keeps count of the number of nodes in the list.

```
struct LL{
    struct node *ptr;
    int         count;
}start;

```

Now store the address of the first node of linked list in $start.ptr$ and initialize $start.count = 1$.
Ensure that the value of $start.count$ is incremented by one after the successfull creation of a new node in linked list. Similarly, decrement it by one whenever a node is deleted from the linked list.

Use $start.count$ to find the middle element in one single pass.

# Answer
> -2 votes
Create a dynamic array, where each element of the array is a pointer to each node in the list in traversing order, starting from the beginning. Create an integer, initialized to 1, that keeps track of how many nodes you have visited (which increments each time you go to a new node). When you get to the end, you know how big the list is, and you have an ordered array of pointers to each node. Finally, divide the size of the list by 2 (and subtract 1 for 0-based indexing) and fetch the pointer held in that index of the array; if the size of the list is odd, you can choose which element to return (I will still return the first one).

Here is some Java code which gets the point across (even though the idea of a dynamic array will be a bit wonky). I would provide C/C++ but I am very rusty in that area.

```
public Node getMiddleNode(List<Node> nodes){

    int size = 1;
    //add code to dynamically increase size if at capacity after adding
    Node[] pointers = new Node[10];

    for (int i = 0; i < nodes.size(); i++){
        //remember to dynamically allocate more space if needed
        pointers[i] = nodes.get(i);
        size++;
    }

    return pointers[(size - 1)/2];

}

```

# Answer
> -3 votes
Is recursion considered more than one pass?

Traverse the list to the end, passing an integer count by reference. Make a local copy of that value at each level for later reference, and increment the ref count going into the next call.

On the last node, divide the count by two and truncate/floor() the result (if you want the first node to be the "middle" when there are only two elements) or round up (if you want the second node to be the "middle"). Use a zero- or one-based index appropriately.

Unwinding, match the ref count to the local copy (which is the node's number). If equal, return that node; else return the node returned from the recursive call.
.

There are other ways to do this; some of them may be less cumbersome (I thought I saw someone say read it into an array and use the array length to determine the middle - kudos). But frankly, there are no good answers, because it's a stupid interview question. Number one, who still uses linked lists (supporting opinion); Two, finding the middle node is an arbitrary, academic exercise with no value in real-life scenarios; Three, if I really needed to know the middle node, my linked list would expose a node count. It's hella easier to maintain that property than to waste time traversing the entire list every time I want the middle node. And finally, four, every interviewer is going to like or reject different answers - what one interviewer thinks is slick, another will call ridiculous.

I almost always answer interview questions with more questions. If I get a question like this (I never have), I would ask (1) What are you storing in this linked list, and is there a more appropriate structure to efficiently access the middle node if there is truly a need to do so; (2) What are my constraints? I can make it faster if memory is not an issue (e.g. the array answer), but if the interviewer thinks bulking up memory is wasteful, I'll get dinged. (3) What language will I be developing in? Nearly every modern language I know of has built-in classes to deal with linked lists that make traversing the list unnecessary - why reinvent something that has been tuned for efficiency by the developers of the language?

# Answer
> -5 votes
By using 2 pointers . Increment one at each iteration and other at every second iteration. When 1st pointer points to end of linked list, went 2nd pointer will point to the middle mode of linked list .

---
Tags: algorithms, data-structures, linked-lists
---


# Question
Title: How to prevent deletion in an array in the B method
I have created a very basic model of an array list in the B method as shown below

```
MACHINE Array(TYPE)

VARIABLES block

INVARIANT block : seq(TYPE)

INITIALISATION block := []

OPERATIONS

add(e) =
   PRE e : TYPE
   THEN block := block <- e
   END;

remove =
   PRE block /= []
   THEN block := tail(block)
   END;

res <-- showArray =
    res := block;

res <-- getfront =
   PRE block /= []
   THEN res := first(block)
   END

END

```

However what I am trying to achieve is to create a model that prevents deletion from the list, so when an element is added, it cannot be deleted.

What should I add in the invariant to achieve this?

# Answer
> 1 votes
You cannot add such a property to your invariant because the invariant describes how a valid state might look like but not how it can be altered.

The operations are responsible for specifying the behaviour of the model. If you want to prevent that an element will be removed from the array, just do not specify that as a possible behaviour. In your example above, just remove the operation `remove`.

Every valid refinement is then not allowed to remove an element.

# Answer
> 0 votes
Add a postcondition to each operation stating that if the array held an element before the operation, then the element is still present afterwards. In other words, if $A\[i\]=x$ held before the operation, then $A\[i\]=x$ still holds. I'll let you work out how to express this in formal mathematics and prove by induction that this achieves what you want, since this is your exercise.

---
Tags: arrays, formal-methods, b-method
---


# Question
Title: Why does Dijkstra's algorithm not account for updating node distances after expanding a node?
Why does Dijkstra's algorithm not re-evaluate/re-expand nodes who have been expanded and later had their weight changed?

For example, in the accepted answer of this question (link), if the algorithm simply understands that d(b) has been updated and it should re-expand b, the shortest cost would be found.

Am i missing something?

# Answer
Since Dijkstra's algorithm always expands the shortest path first, the first time we reach a node will be along the shortest path to that node. That is the key insight that allows the algorithm to be efficient compared to a breadth-first-search.

There is no way to construct a graph where no costs are negative and there exists a path from `a` to `b` shorter than the one Dijkstra's algorithm finds.
> 3 votes

---
Tags: graphs, shortest-path
---


# Question
Title: Time and space complexity of removing duplicates in a sorted list
Is it possible to delete duplicates from a sorted array in $O(\log N)$ time and $O(1)$ space?

# Answer
It is not possible to delete all duplicates from a sorted list faster than `O(n)` time unless you have some other information about the list. You have to look at each item at least one to see what value it has. If you do not do that, we could make two of the items you're not looking at duplicates of each other, and you would have no way of knowing, since you didn't look at those items.

One example of a special sorted list where you could find any constant number of duplicate items is one with all numbers `[a,b]` with some constant number of duplicated items. We can look at any two positions and figure out how many duplicates there are in between by comparing the numbers with their positions in the array.

Consider this list:

```
1 2 3 4 4 5 6

```

There's one duplicate element. By looking at `1` and `6` we know that there should be the numbers `1 2 3 4 5 6` in between them, but there's one slot too many between them, so there must be at least one duplicate. Continue by splitting the list in half by looking at the middle element, the first `4`.

```
1 _ _ 4 _ _ 6

```

The first half has 4 items and by comparing the numbers at position 1 and position 4, we know that there cannot possibly be any duplicates there.

Between 4 and 6, however, we have 2 slots. Thus there must be a duplicate `4`, `5` or `6`.

```
1 _ _ 4 4 _ 6

```

There's our duplicate, in `O(log n)` time and `O(1)` (extra) space.
> 3 votes

# Answer
Not possible in O(logn) time and O(1) space here's the link which may solve your problem
> -4 votes

---
Tags: time-complexity, arrays
---


# Question
Title: Could someone please explain this language to me and its grammar?
This is the problem: https://i.stack.imgur.com/rl6qx.png

This was a problem I saw and I really have 0 clue what the Language means the (\**) part, and its solution.

I was wondering if anyone could please help me?

I do know what grammars are and how to read them, but this one was confusing and what I really want to know is how one would approach a problem like this. If I was given this problem, I wouldn't even know where to start.

Thank you.

# Answer
> 3 votes
The notation \** is an old way of writing exponentiation ^.

The grammar is a type-0 grammar, where any string can be replaced by another. It actually comes close to a context-sensitive grammar (or better monotonous grammar) except for the last three productions.

Generating squares is usually done using the recurrence $(n+1)^2 = n^2 + 2n +1$ so the strings always contain a $n$ specially distinguished symbols so one can add the double amount of $2n$ to get the next square. After adding 1 of course.

Here I guess this is seen in the production $M\_R A \to aA M\_R$: the symbol $M\_R$ moves over the string and adds an $a$ for each $A$.

---
Tags: formal-grammars
---


# Question
Title: Computing Von Neumann Entropy Efficiently
The Von Neumann entropy $S$ of a density matrix $\rho$ is defined to be $S(\rho)= -\text{tr}(\rho \lg \rho)$. Equivalently, $S$ is the classical entropy of the eigenvalues $\lambda\_k$ treated as probabilities. So $S(\rho) = -\sum\_k \lambda\_k \lg \lambda\_k$.

Clearly the Von Neumann entropy can be computed by first extracting the eigenvalues and then doing the sum. But extracting eigenvalues is quite expensive. **Is there a faster way to compute the entropy?**

*(For example, computing the sum of the eigenvalues is much easier than computing the individual eigenvalues. You just return the trace of the matrix. The product of the eigenvalues, the determinant, is also easier to compute than the individual eigenvalues. Is there also a shortcut for the entropy?)*

# Answer
> 5 votes
A paper Computing the Entropy of a Large Matrix by Thomas P. Wihler, Bänz Bessire, André Stefanov suggests approximating $x \lg x$ with a polynomial. Then you can use the trace of powers of the matrix to sum the results of applying that polynomial to each of the eigenvalues.

(The polynomial-via-power-and-trace thing works because density matrices have orthogonal eigenvectors. Raising the matrix to a power will raise its eigenvalues to that power. Then the trace gives you the sum of the eigenvalues at that power.)

Sounds fun. Not going to let the paper spoil it.

---

The derivatives of $f(x) = x \ln x$ are:

$$\begin{align} f^0(x) &= x \ln x\\ f^1(x) &= 1 + \ln x\\ f^2(x) &= x^{-1} \\ f^3(x) &= -x^{-2}\\ f^4(x) &= 2 x^{-3}\\\ f^5(x) &= -6 x^{-4}\\\ ...\\ f^k(x) &= (-1)^k \cdot (k-2)! \cdot x^{1-k} \end{align}$$

The derivatives don't always exist at $x=0$, but they do at $x=1$, so we can make a Taylor series from there:

$$\begin{align} x \ln x &= \sum\_{k=0}^\infty \frac{(x-1)^k}{k!} f^k(1) \\ &= (1 \ln 1)\frac{(x-1)^0}{0!} + (1 + \ln 1)\frac{(x-1)^1}{1!} + \sum\_{k=2}^\infty \frac{(x-1)^k}{k!} (-1)^k 1^{1-k}(k-2)! \\ &= x - 1 + \sum\_{k=2}^\infty \frac{(1-x)^k}{k(k-1)} \end{align}$$

So now we have a nice series $\frac{(1-x)^1}{-1} + \frac{(1-x)^2}{2} + \frac{(1-x)^3}{6} + \frac{(1-x)^4}{12} + \frac{(1-x)^5}{24} + ...$ that we can approximate by cutting off at some index $c$. Except that would converge like $O(c^{-1})$ when $x=0$, so we should probably try to account for the excess when the numerator is stuck at $1$:

$\begin{align} x \ln x &= x - 1 + \sum\_{k=2}^\infty \frac{(1-x)^k}{k(k-1)} \\ &= x - 1 + \sum\_{k=2}^{c-1} \frac{(1-x)^k}{k(k-1)} + \sum\_{k=c}^\infty \frac{(1-x)^k}{k(k-1)} \\ &\approx x - 1 + \sum\_{k=2}^{c-1} \frac{(1-x)^k}{k(k-1)} + \sum\_{k=c}^\infty \frac{(1-x)^{\Huge c}}{k(k-1)} \\ &= x - 1 + \left( \sum\_{k=2}^c \frac{(1-x)^k}{k(k-1)} \right) + \frac{(1-x)^c}{c-1} \end{align}$

Here's a graph of the difference between $x \ln x$ and the approximation when $c=10$:

And voila, just write code to evaluate that polynomial over the eigenvalues by using traces of the matrix powers:

```
import math
import numpy
def von_neumann_entropy(density_matrix, cutoff=10):
    x = numpy.mat(density_matrix)
    one = numpy.identity(x.shape[0])
    base = one - x
    power = base*base
    result = numpy.trace(base)
    for k in range(2, cutoff):
        result -= numpy.trace(power) / (k*k - k)
        power = power.dot(base)
    result -= numpy.trace(power) / (cutoff - 1)
    return result / math.log(2)  # convert from nats to bits

```

The convergence is still kinda terrible near $x \approx 0$, though. I tried replacing the last correction with some doubling steps like this:

```
import math
import numpy
def von_neumann_entropy(density_matrix, cutoff=10):
    x = numpy.mat(density_matrix)
    one = numpy.identity(x.shape[0])
    base = one - x
    power = base*base
    result = numpy.trace(base)
    for k in range(2, cutoff):
        result -= numpy.trace(power) / (k*k - k)
        power = power.dot(base)

    # Twiddly hacky magic.
    a = cutoff
    for k in range(3):
        d = (a+1) / (4*a*(a-1))
        result -= numpy.trace(power) * d
        power = power.dot(power)
        result -= numpy.trace(power) * d
        a *= 2
     result -= numpy.trace(power) / (a-1) * 0.75

     return result / math.log(2)  # convert from nats to bits

```

And that improved things a bit more, so that the maximum offset vs $-x \ln x$ across the \[0, 1\] range was $3.5 \cdot 10^{-3}$ instead of $2.9 \cdot 10^{-2}$ (for the given cutoff of 10).

(The plot is reversed.)

---

**Of course, the paper I linked at the start of the answer probably has a much better polynomial.**

For example, my error analysis should have been in terms of the *total* entropy instead of the individual value. And I should have used tricks like computing the trace of $AB$ from $A$ and $B$ in $O(n^2)$ time without doing the multiplication. And I should have thrown some simulated annealing at the coefficients.

---
Tags: quantum-computing, linear-algebra, entropy, numerical-algorithms
---


# Question
Title: Can an independent set (of vertices) be a vertex cover as well?
I wanted to clarify if this is possible, so I thought about a possible vertex cover that can also serve as an independent set:

So, to clarify, am I right to say that the nodes in red are both (i) a vertex cover, and (ii) an independent set?

**Edit:** I was confused by the theorem that states "If `G = (V,E)` is a graph, then `S` is an independent set \<-\> `V-S` is a vertex cover." So I thought that a vertex cover and an independent set are mutually exclusive.

# Answer
> 1 votes
If something satisfies the definition of $X$ and the definition of $Y$, then it is both an $X$ and a $Y$.

Although it's true that, whenever $S$ is independent, $V\setminus S$ is a vertex cover, it's possible for both $S$ and $V\setminus S$ to be independent: this happens when $S$ is one side of a bipartite graph, as is the case in the example in the question.

---
Tags: graphs
---


title: Examples of Dependent Types

text:
# Question
Title: Examples of Dependent Types
I'm gathering examples from everything that I've read about *Dependent Type Theory* mainly from Dependent types at Work paper.

This is my list so far of some dependent types (with abbreviations of mine):

* \[NVec\]: $A^n$ vectors of length n with elements of type $A$
* \[NMMAtrix\]: $A^{m\times n}$ matrices
* \[Fin\]: Finite sets of size $n$
* \[SList\]: Sorted lists
* \[NBTree\]: Height-balanced trees of a certain height
* \[SBTree\]: Sorted binary trees
* \[PAIR\]: A pair of integers *where* the second is greater than the first

How can I justify that the types from my list are indeed dependent types. I appreciate another example to add it to my list.

# Answer
I think it helps to keep in mind the *propositions as types* mantra. Every type can be read either as a propostion or a set. This gives us two readings (let's just consider types dependent on natural numbers):

1. A dependent type $P : \mathtt{nat} \to \mathtt{Type}$ is like a family of sets $P(0), P(1), P(2), \ldots$
2. A dependent type $P : \mathtt{nat} \to \mathtt{Type}$ is a *property of natural numbers* where we think of $P(n)$ as the proofs that $n$ has property $P$

With this in mind it may be easier to make sense of dependent types. For instance, consider:

* $\mathtt{Mat}(n)$: the type of matrices of size $n \times n$
* $\mathtt{Less}(a,b)$: the proofs that $a \< b$

Then $\mathtt{Mat}(n)$ should be thought of as a collection of sets, one for each $n$, while $\mathtt{Less}(a,b)$ is a *relation* (a binary predicate) on pairs $(a,b)$.

Your first three examples (NVec, NMMatrix, Fin) are dependen types of the first kind. The other ones are of the second kind.

Strictly speaking, when you say "a pair of integers where teh second is greater than the first", that is *not* a dependent type but an element of the dependent sum, i.e,

$$\mathtt{PAIR} = \textstyle\sum\_{(a,b) : \mathtt{nat} \times \mathtt{nat}} \mathtt{Less}(a,b),$$

i.e., a *triple* $(a, b, p)$ where $p$ is a proof that $a \< b$. Similarly, your NBtree and SBTree examples are really dependent sums of the form $\sum\_{t : \mathtt{Tree}} P(t)$, not dependent types. The sums of course use dependent types $P(t) = \text{"proofs that the tree $t$ is height-balanced"}$ and $P(t) = \text{"proofs that the tree $t$ is sorted"}$.
> 9 votes

---
Tags: dependent-types
---


# Question
Title: finding maximum virtual and physical memory
If the following is given:

1. CPU uses a four-level hierarchical page table, each level can contain 512 entries
2. the page size is 4KB.
3. virtual address is 48 bits

How do i get the size of the virtual memory (in terms of pages or bytes). Do i just use the number of page table entries 29\*4+12 ?

And can i get the size of the physical memory given this information ?

# Answer
> 1 votes
**No**, you can't get size of physical memory with the provided information.

Explanation:

1. Virtual memory that you mentioned is **correct**. But you can calculate it just by seeing the number of bits virtual address has (What you did is correct though).
2. To calculate the physical memory, we need to know that Physical memory is a collection of frames, which has same size as pages. Since Page size is already given (4KB), next we need to know how many frames does main memory(physical) has. For this we need to know the size of **page table entry**, which contains frame address. If we know frame address length, then we can calculate the total number of frames by calculating **2^(length of frame address).** Then you can multiply the frame size (4KB) with the above value to get the size of **Physical memory.**

---
Tags: operating-systems, virtual-memory
---


# Question
Title: Why do some authors not include summation in the $\pi$-Calculus?
In Robin Milner's book *"Communicating and Mobile Systems: the $\pi$-Calculus"*, on page 87, the set of expressions of the $\pi$-Calculus is defined as

$$P ::= \sum\_{i\in I} \pi\_i.P\_i\ {\huge|}\ P\_1|P\_2 \ {\huge|}\ \operatorname{new} a P\ {\huge|}\ !P$$

So in Milner's formulation, the summation of processes is included, just as in CCS. However, some authors do not include it: in Mathew Hennessy's book, *"A Distributed $\pi$-Calculus"*, summation is not used (section 2.1 deals with the language, and summation isn't there).

The Wikipedia article on $\pi$-Calculus also doesn't include summation.

Why is summation not included in these descriptions? Was it somehow abandoned because it can be expressed using the other primitives? If so, how would it be done?

# Answer
> 9 votes
To answer this question, it's best to reflect on the meaning of sums in process calculi. Essentially sums express a lack of knowledge. The process $P + Q$ means something along the lines of "either $P$ or $Q$ is active, but I have absolutely no information which". Note that this is related to, but different from a probabilistic sum like $P +\_{0.5} Q$ which also expresses uncertainty about which process is active, but quantifies the uncertainty by stating that both outcomes are equally likely. So $P+Q$ expresses less information than $P +\_{0.5} Q$.

A specific case of using sums to express uncertainty is the input process

$$ x(v).P $$

Cleary an process waiting on an input on channel $x$ is uncertain what input will be received, for otherwise there would not be a need to input something. Hence input can be seen as a sum over all possible inputs, e.g. if we expect to get a natural $n$, then $ x(v).P $ really is the sum:

$$ \Sigma\_{n \in \mathbb{N}} xn.P\\{n/v\\} $$

Here $xn.P$ is the process that inputs the number $n$ (seen as a constant) on $x$ and becomes $P$.

With this understanding of sums as an expression of uncertainty, the question whether to include sums, and what kind of sum depends what you use the $\pi$-calculus for. There are two main uses.

If you use it as an **idealised programming language**, then you don't need sums other than the input prefix $x(v).P$ (and possibly its replicated variant). Indeed what *computation* would $P+Q$ express?

If you use it to **specify program behaviour**, then you typically don't want to specify everything and instead express uncertainty by using sums of processes, e.g. $P + Q$. Typically you don't know exactly what the environment of a process is going to do, and use non-determinism to formalise this lack of knowledge.

# Answer
> 3 votes
The problem with summation is that it is a powerful and thus difficult/expensive/impossible to implement feature. It's especially difficult in asynchronous contexts.

If you have $x(y).\\!P + x(y).\\!Q$, when $x(z)$ occurs, *exactly* one of $P$ or $Q$ proceeds and *neither* is waiting afterwords. Consider what would be required to ensure that in a distributed context when the summands are not co-located. The point is non-trivial sums require coordination, and coordination is expensive. Even in non-distributed contexts, this is true. Also, in many theoretical contexts the purpose is to *explain* coordination, so it doesn't make sense to assume it. This is also part of the popularity of the asynchronous variant of the $\pi$-calculus, as the rendezvous semantics of the synchronous variant don't usually match the systems being modeled and require an undesirable level of coordination.

---
Tags: programming-languages, semantics, pi-calculus
---


title: Meta-grammar for context-free grammars

text:
# Question
Title: Meta-grammar for context-free grammars
Formal grammars like regular expressions (REs) or context-free grammars (CFGs) specify languages, i.e. sets of strings over an alphabet.

Grammars themselves can be seen as languages, e.g. the set of REs over $\\{0, 1\\}$. In that sense we can specify a grammars by means of a meta-grammar. For example the language of all REs over a fixed alphabet can be specified as a context-free grammar (CFG), e.g. like so

$$ R \quad::=\quad 0 \ |\ a \ |\ RR \ |\ R+R \ |\ (R) \ |\ R^\* $$

where $a$ ranges over the ambient alphabet. One advantage of thinking of grammars in terms of their meta-grammar is that we can parse REs and check them for syntactic correctness.

What kind of meta-grammar (context-free or otherwise) allows us to specify the language of CFGs over a given alphabet? What about subsets of CFGs like LL(k) or LR(k)? I'm sure this has been investigated before as there are many tools that take grammars as input, e.g. parser generators.

# Answer
> 4 votes
Backus–Naur Form's syntax can be represented with a BNF itself. Here is an example taken from this Wikipedia article:

```
<syntax>         ::= <rule> | <rule> <syntax>
<rule>           ::= <opt-whitespace> "<" <rule-name> ">"
                     <opt-whitespace> "::=" <opt-whitespace>
                     <expression> <line-end>
<opt-whitespace> ::= " " <opt-whitespace> | ""
<expression>     ::= <list> |
                     <list> <opt-whitespace> "|" <opt-whitespace> <expression>
<line-end>       ::= <opt-whitespace> <EOL> | <line-end> <line-end>
<list>           ::= <term> | <term> <opt-whitespace> <list>
<term>           ::= <literal> | "<" <rule-name> ">"
<literal>        ::= '"' <text> '"' | "'" <text> "'"

```

`""` denotes the empty string. The article provides some more details on undefined here rules for `<rule-name>`, etc.

# Answer
> 2 votes
The typical notation I've seen can be described as a regex: `(S -> (S|a)*\n)+` where `S` is a non-terminal symbol and `a` is the range of the alphabet. Informally it's a list of production rules where a non-terminal maps to a string of terminals (a character in the alphabet) and non-terminals.

However this grammar doesn't have the constraints on how proper the grammar is For example non-terminals can have no production rule. For that you can use a variant of whether a string contains every character of an alphabet at least once in any order which is a regular language.

---
Tags: formal-languages, context-free, reference-request, formal-grammars, parsers
---


title: Page vs page table entry

text:
# Question
Title: Page vs page table entry
Im studying for OS-finals and I cant figure out the difference.

A page is a chunk of addresses e.g 0-4095. This maps to 4kB of memory. This page is 4kB big. But according to the litterature the Page table entry is around 4 Bytes big. I thought Page Table Entry are the same as a page.

# Answer
> 1 votes
AFAIK, the page table entry doesn't contain the page itself. Rather, it contains the address of the physical memory chunk that the particular page in the table is mapped to. This address will be 32-bits (4 bytes).

In this example, the page table entry contains the address of the physical memory chunk (frame). Knowing the offset, we can find the actual address in the physical memory.

Hope it helps.

---
Tags: virtual-memory
---


# Question
Title: Longest substring with consecutive repetitions
I want to find the longest substring which is repeated without any gap between the repetitions. That is, given a string $x$, I want to find the longest $y$ such that $yy$ is a substring of $x$.

What I mean is the following cases:

```
In "aa"         I want "a"    with a position of 0 and repetition of 2
In "aaab"       I want "a"    with a position of 0 and repetition of 3
In "abc"        I want ""     (false or whatever)
In "abababc"    I want "ab"   with a position of 0 and repetition of 3
In "aaabbbb"    I want "b"    with a position of 3 and repetition of 4
In "eabcdabcde" I want "abcd" with a position of 1 and repetition of 2
In "cababcab"   I want "ab"   with a position of 1 and repetition of 2 (not 3, because of the "c" between the three "ab"'s)

```

I've been looking at various suffix and prefix algorithms, but none of them has the "no gaps" part build into it. Both LCP arrays and Suffix arrays seems to suffer from this.

Googling for "Longest repeated substrings" gives me algorithms which e.g. find `"hello"` in `"abcdehellofghijhelloklmn"`, but this is *not* what I want.

# Answer
From what I understand you are looking for maximal substrings of the form $y^k$ for $k\ge 2$. By some this is called a *repetition* in a string. One of the first to give an algorithm for finding these is Maxime Crochemore: An optimal algorithm for computing all the repetitions in a word, Inform. Process. Lett. 12 (1981) 244-248. From what I understand his approach has been reformulated in terms of suffix trees and arrays.
> 1 votes

# Answer
After fiddling a bit around with different options, we discovered, that what we really needed was as simple as the regular expression: `(.+)\1+`. This will match at least one character and then match at least one of the same match again.

Having `aaab` will then match the `a` which is present three times.

In `cababcab`, we match the first `ab` which is there twice and so on.

Sidenote: Now the next problem is implementing this for something other than strings and characters, e.g. C++ objects.
> 0 votes

---
Tags: algorithms, optimization, strings, substrings, longest-common-substring
---


# Question
Title: Dynamic Shortest Path with Linear Programming
Consider a grid with $x=5$ columns, $y=5$ rows, and $T$ timesteps.

There are $N=2$ agents in this grid, which can move vertically or horizontally. The positions of each agent $x$ at timestep $t$ is denoted as $A\_{xt}$. For this example, consider $A\_{00}=1$ and $A\_{10}=23$. The goal is to carry a ball from node $1$ to node $G=15$. Each agent can carry the ball or throw it at distance $k=2$ (measured in Manhattan distance). The shortest path is, in this case, for Agent $0$ to carry the ball until node $3$, while Agent $1$ moves to node $13$. Then, Agent $0$ throws the ball to Agent $1$, which kicks it to the goal node.

How can this be modeled? If agents cannot move without the ball (not a dynamic graph), the problem is fairly simple. Assume $X\_{ijt}=1$ (an activated edge) when the ball is carried or is kicked from node $i$ to $j$ at timestep $t$, and all actions cost (or have weight) $1$. All nodes (except starting and goal nodes) must have the same amount of ball 'entrances' as 'exits'.

$ \sum X\_{ijt\_1} = \sum X\_{jit\_2}, \forall i,j,t\_1,t\_2$, where $t\_1\<t\_2, d(i,j)=1$ (adjacent nodes) or $j=A\_{xt}$ (passing towards an agent)

The entrance and exit nodes will have a single activated edge.

$ \sum X\_{A\_{00}j0} + \sum X\_{A\_{00}A\_{x0}0} = 1, \forall j,x$, where $x\neq0, d(A\_{00},j)=1, d(A\_{00},A\_{X0})\leq k$

$ \sum X\_{iGT} = 1, \forall i$, where $d(i,G)\leq k$

However, if all agents can move at any given point, then the graph is dynamic, since the passes that can be performed are different in each timestep. I don't know how to model this. Before, because $A\_{1t}$ was static until it got the ball, I could list all the restrictions *a priori*, but now, I cannot do it. I can create a set of restrictions based on $A\_{xt} \forall x,t$, but I don't know how to then input this problem into a linear programming solver (for example, a simplex method).

# Answer
> 2 votes
Our matrix is modelled as a graph $G = (V,E)$ with directed edges $E$ between cells $V$. We denote $V\_{kl}$ as the set of nodes $j$ that respect $d\_{jl} \leq k$. The edges $E$ exist between all nodes $j \in V\_{kl}$ and node $l$, for any $l \in V$. Activated edges represent movements (such as players moving with the ball to an adjacent cell or passing the ball to a faraway agent). All player actions (moving, kicking or passing) take exactly $1$ action, therefore the weight of all edges in our graph is always $1$. Throughout this paper, unless specified otherwise, we use $i \in \[1, p\]$ to identify an agent, $t \in \[0, T\]$ to identify different timesteps and $l,j \in V$ to identify nodes. We must define the position and movements of each agent $i$, as well as the position and movements of the ball, all across $t$. Assuming $l\_1 \in V\_{1l}$ and $l\_k \in V\_{kl}$, then

\begin{equation} \begin{split} A\_{ijt} = & \begin{cases} 1 ,& \textrm{if Agent $i$ is on cell $j$ at timestep $t$} \\ 0 ,& \textrm{otherwise} \end{cases} \\ Y\_{ill\_1t} = & \begin{cases} 1 ,& \textrm{if Agent $i$ moved from cell $l$ at timestep $t$ to cell $l\_1$ at timestep $t+1$} \\ 0 ,& \textrm{otherwise} \end{cases} \\ B\_{jt} = & \begin{cases} 1 ,& \textrm{if Ball is on cell $j$ at timestep $t$} \\ 0 ,& \textrm{otherwise} \end{cases} \\ X\_{ll\_kt} = & \begin{cases} 1 ,& \textrm{if Ball moved from cell $l$ at timestep $t$ to cell $l\_k$ at timestep $t+1$} \\ 0 ,& \textrm{otherwise} \end{cases} \end{split} \end{equation}

These definitions inherently model the behaviour of our agents and ball, by limiting agents to only move $1$ unit of distance at most, and the ball to move $k$ units of distance at most. Both $B\_{j0}$ and $A\_{ij0}$ are defined for all $j,i$. We must now model the relation between $A$ and $Y$, as well as between $B$ and $X$. In fact, $A\_{i,l,t+1}$ (representing agent $i$ being on cell $l$ at timestep $t+1$) must be the sum of $A\_{i,l,t}$ (agent $i$ may have been in that cell in the previous timestep and remained stationary) with $\sum\_j Y\_{ijlt} - \sum\_j Y\_{iljt}$ (agent $i$'s movements entering or leaving that cell). If the agent remains stationary, the latter part of the sum is equal to $0$. Analogously, a similar relation exists between $B$ and $X$. Formally, for all $i$, $l$, $t$,

\begin{equation} \begin{split} A\_{i,l,t+1} & = A\_{i,l,t} + \sum\_{j \in V\_{1l}} Y\_{ijlt} - \sum\_{j \in V\_{1l}} Y\_{iljt}, \\ % player positions are related to their movements B\_{l,t+1} & = B\_{l,t} + \sum\_{j \in V\_{kl}} X\_{jlt} - \sum\_{j \in V\_{kl}} X\_{ljt}. \\ % ball positions are related to its movements \end{split} \end{equation}

Our optimization function now differs in the fact that $t$ must be taken into account. This is necessary due to the fact that the ball may remain in the same place for several turns, which counts as movement to the same cell. In other words, reaching the goal $G$ on the second timestep $t$ and waiting there for $50$ turns is equivalent to waiting $50$ turns and then entering the goal. Therefore, our objective functions is now

\begin{equation} Z = \sum\_{t,l \in V\_{kG} \setminus G} ( t * X\_{lGt} ) . \end{equation}

We must update the previously described constraints so that the ball enters the goal $G$ only once at any timestep $t$ and leaves the source $S$ at timestep $0$. Our modeling of $B$ dependent on $X$ will ensure that the ball will move among the cells from $S$ to $G$.

\begin{equation} \begin{split} \sum\_{l \in V\_{kS}} X\_{Sl0} & = 1, \\ % ball leaves Source once \sum\_{j \in V\_{kG} \setminus G,t} X\_{jGt} & = 1, \\ % ball enters Goal once \end{split} \end{equation}

Finally, we must guarantee that the agents do not overlap and that they carry the ball, kick it to the goal $G$, or pass it at each other. In other words, the amount of agents at node $j$ cannot exceed $1$ and the ball must either be at one of the agent's positions or at the goal $G$. Formally, for all $j$, $t$,

\begin{equation} \begin{split} \sum\_{i} A\_{ijt} \leq & 1, \\ % only 1 agent per cell B\_{jt} \leq & \sum\_i A\_{ijt} + B\_{Gt}. \\ % ball can only exist at Goal or where there are agents \end{split} \end{equation}

# Answer
> 0 votes
First of all, you can't solve this using linear programming. You have to use integer programming.

Second, you can just use a configuration graph. The configuration graph has as vertex set all possible configurations (in your case, locations of the agent and the ball), and edges correspond to possible moves that can happen within one time step. Now you can use a shortest path algorithm (possibly using heuristic search) to find the shortest number of moves to get from your initial state to one of the goal states.

---
Tags: algorithms, optimization, shortest-path, linear-programming, modelling
---


# Question
Title: How likely is it that a computer miscalculates 1+1?
Of course, normally a fully-functional computer will calculate 1+1=2. However, the physics governing the behavior of a chip is quantum mechanical. So in principle there is a certain probability that something goes wrong and we get the result 1+1=x where x≠2. In my opinion this probability should get bigger the smaller the chips are becoming.

So the question is: How likely is this event? Can one give an order of magnitude?

P.S. I'm not talking about quantum computing, just "standard" computers nowadays everyone has on their desk.

# Answer
> 1 votes
The probability of read error is bigger than write error, so there is a chance for bitflip on either of $1$ which might occur anywhere.
I can offer description of JVM attack which is not exactly the answer, but shows how much effort is needed to induce bitflips, tells about softerrors and *a very successful attack on JVM, given good heat ;)*.

The probability of error grows the most related with heat dissipation problems, and making chip smaller include it's higher efficiency (performance per watt).

Anyway there is bad assumption - making chip smaller gives more errors - if this were true over time CPUs would generate noticeable amount of errors today.

Please check also this error rate study. With calculating probability of error there is a problem - this is hardware dependent and the most of hardware actually has errors, but they get corrected at several levels, so they do not occur for user, and with invalid / broken piece machine crashes are to often to perform test.

# Answer
> 0 votes
Have you heard about SEU : Single Event Upset and MEU : Multiple Event Upset...

Cosmic rays or radioactive decay can produce high energy particles able to flip bits. EDC bits in server DRAM, parity and EDC in CPU caches are there to protect against these problems.

Radioactive decay have been a problem sometimes within chip packaging : Unstable isotopes in the epoxy.

Cosmic rays and sun emitted particles is is a problem highly dependant on altitude : It seldom occurs on ground, sometimes in aircrafts, often in satellites.

This is not really about quantum mechanics randomness.

---
Tags: computer-architecture, randomness, error-estimation
---


# Question
Title: Has it been proven that the optimization TSP is (or is not) polynomial-time verifiable if P ≠ NP?
The optimization version of TSP asks for the length of the shortest tour. Unlike the decision version of TSP, there's no obvious way to verify a proposed solution of the optimization problem in polynomial time. But is there a proof of whether or not it can be verified in polynomial time assuming P ≠ NP?

# Answer
If $optTSP$ is in $NP$, then $coNP = NP$. The latter is unresolved currently.

Proof: if $optTSP$ is in $NP$, then $coTSP$ is in $coNP$ (the certificate being whatever certificate was provided to verify a solution to $optTSP$ was minimal, and then comparing the value of that solution to the desired bound). And because $TSP$ is $NP$-complete then this implies $NP = coNP$.
> 6 votes

---
Tags: complexity-theory, optimization, np, traveling-salesman
---


title: Why is NP in EXPTIME?

text:
# Question
Title: Why is NP in EXPTIME?
Is there an easy way to see why NP is in EXPTIME? It seems to me a priori conceivable that there could be a problem which requires super-exponential time to solve, but whose solution could be verified in polynomial time.

# Answer
Any problem in **NP** is in **EXPTIME** because you can either use exponential time to try all possible certificates or to enumerate all possible computation paths of a nondeterministic machine.

More formally, there are two main definitions of **NP**. One is that a language $L$ is in **NP** iff there is a relation $R$ such that

* there is a polynomial $p$ such that, for all $(x,y)\in R$, $|y|\leq p(|x|)$,
* given the string $x\\#y$, we can determine in time polynomial in $|x\\#y|$ whether $(x,y)\in R$, and
* $L = \\{x\mid (x,y)\in R\\}$.

So, if we have exponential time and we want to know if $x\in L$, we can just try all $|\Sigma|^{p(n)}$ possible values for~$y$ and see if $(x,y)\in R$ for any of those. That takes time $2^{O(p(n))}$, so $L\in\\,$**EXPTIME**.

Alternatively, we can define **NP** as the set of languages decided by polynomial time nondeterministic Turing machines. In this case, suppose that $L$ is decided by machine $M$ in time $p(n)$ for some polynomial $p$, for inputs of length $n$. Then $M$ makes at most $p(|x|)$ nondeterministic choices while determining if $x\in L$. By examining $M$'s transition function, we can find a constant $k$ such that $M$ has at most $k$ nondeterministic choices at each step of the computation (independent of the input), so it has at most $k^{p(|x|)} = 2^{O(p(|x|))}$ different sequences of nondeterministic choices while reading input $x$. Given exponential time, we can simulate each of these possibilities one after another and see if any of them accepts.
> 22 votes

---
Tags: complexity-theory, complexity-classes
---


title: Standardizing Data for Neural Networks

text:
# Question
Title: Standardizing Data for Neural Networks
Let's say we have a data set with following features `[age, sex, country, city, annual income]
[35, male, USA, New York, 73000]`.

I came across the article which explains how to deal with strings as an NN input.

Article example showing how to standardize data:

```
[0] 30  male    38000.00  urban     democrat
[1] 36  female  42000.00  suburban  republican
[2] 52  male    40000.00  rural     independent
[3] 42  female  44000.00  suburban  other

[0] -1.23  -1.0  -1.34  ( 0.0   1.0)  (0.0  0.0  0.0  1.0)
[1] -0.49   1.0   0.45  ( 1.0   0.0)  (0.0  0.0  1.0  0.0)
[2]  1.48  -1.0  -0.45  (-1.0  -1.0)  (0.0  1.0  0.0  0.0)
[3]  0.25   1.0   1.34  ( 1.0   0.0)  (1.0  0.0  0.0  0.0)

```

Now let's try to use this approach in our example where we could end up with thousands of different cities. We would have to create at least N vectors size of \[1 ... N\]. That approach just does not seem to be very efficient when we have unlimited number of possibilities.

That was a brief explanation of standardizing data problem. Now let me expand it to my specific NN task. I have a data set with 30+ features. Features consist of real numbers, decimal numbers, strings. All of them are relevant.

I have to transform non-computable data into numeric, NN computable form. The question is how to standardize a set of data with many features of different types (strings and numbers)?

# Answer
You can distinguish between the following types of data (source, see Level of measurement for something similar):

* Nominal: You can't calculate with them. They only support checks for identity, e.g. names.
* Ordinal: You can order them, but not compare the distance. Examples are grades or sizes for cloths.
* Interval scaled: Additionally to identity checks and ordering it supports addition. Examples are temperature in °C / °F
* Ratio scaled: They support multiplication in addition to the ones before. Examples are mass and length.

For neural networks, ratio scaled feature make most sense. You can sometimes change your view on things to get it, but most of the time you cannot simply transform an ordinal scaled feature to be ratio scaled.

Two tricks for your example come to my mind:

* **1-hot encoding**: Instead of using one number for the country (e.g. 1 for Australia, 2 for Austria, 3 for France, 4 for Germany, ...) you should use a 1-hot encoding (e.g. one bit per country, the bit is only set if it is this country). I am pretty sure this will work much better, although your feature vector will get much bigger. (**Attention**: Depending on how much data you have, you might suffer from overfitting. You could also partition your dataset according to this feature. So, for example, you might have a lot of data for the US, for France and Germany. But you only have a little data for african countries. Then you could simply have one bit for each of US, France, Germany and complete Africa)
* **Latitude / Longitude**: Instead of using the citys directly, you can use the citys coordinate. This makes your feature even more meaningful and you have two floats for it which are ratio scaled.

You might also think about transforming the country to something more meaningful for your problem (e.g. membership in an organization like OECD).

You could also combine different classifiers. So you could use the "bad scaled features" for a decision tree and feed the result into a NN.
> 2 votes

---
Tags: machine-learning, data-mining
---


# Question
Title: 3-SUM hardness vs lower bounds on the complexity
I've recently encountered a new (for me) notion from computational complexity theory called 3-SUM hardness which is based on the conjecture that 3-SUM problem can not be solved in $O\left(n^{2-\varepsilon}\right)$ time where $n$ is the number of reals among which we should check whether three of them sum to zero. By giving reduction from 3-SUM we get that it is unlikely that our problem could be solved in subquadratic time. From the other hand we can prove the lower bounds on the complexity of solving our problem. Then what is the difference between these two notions ? Does it just mean that giving the reduction is simpler than obtaining lower bounds or in other words we have an additional assumption (which usually remains unproved for ages :-))in our pocket that helps us prove the lower bound.

# Answer
The reason we need complexity assumptions like the 3SUM conjecture is that we *cannot* prove meaningful lower bounds in any non-trivial computational models. Our best lower bounds are in bounded depth models or in monotone models, or use techniques such as diagonalization which usually apply only to somewhat contrived problems. Whereas we have exponential lower bounds on circuit size for circuits of bounded depth and for monotone circuits, the best lower bound for SAT is linear.

Since we cannot prove meaningful lower bounds on interesting problems in unrestricted computation models, we use the paradigm of *reductions*: assume that a specific problem is hard, and conclude that other problems are hard. The most celebrated example is, of course, the theory of NP-hardness. It is easy to criticize this methodology: the hardness assumptions that we make are sometimes controversial. Things are particularly bad in cryptography, where sometimes the hardness assumption made in a paper is a thinly veiled version of the assumption that the construction suggested in the paper works.

3SUM hardness is not a new assumption, but has recently found new interest in the community. It explains the complexity of the best known algorithms for many different problems. As such, it is coming to be viewed as the analog of NP-hardness for problems inside P. As an added bonus, 3SUM hardness makes much more accurate predictions on the complexity of problems: rather than just stating that an NP-hard problem cannot be solved in polynomial time, 3SUM hardness allows us to determine the best exponents (smallest $\alpha$ such that the problem can be solved in time $O(n^\alpha)$) of certain problems.
> 3 votes

# Answer
Currently, the only way we know to prove interesting bounds in P is through 3SUM (or other similar problems). In particular, there is no known (to my knowledge) $\Omega(n^{1+\epsilon})$ lower bound for any natural problem in NP. (There are lower bounds for artificial problems; for example determining if a Turing Machine halts in $k^3$ steps, for $k$ given in unary.) As far as we know, it's possible to solve SAT in $O(n\log n)$ time.

So your intuition is correct. It's too hard to prove a real lower bound, so we just say that we can't improve on the problem without improving on the best known 3SUM algorithm. It's similar to what we do with NP-completeness.

However, due to a fairly large amount of recent research, 3SUM is just the tip of the iceberg. Similar, and in many cases stronger, conditional lower bounds can be proven using the Strong Exponential Time Hypothesis, the Orthogonal Vectors problem, All Pairs Shortest Paths, and some others.

This survey is almost certainly the place to start, as it's written by Virginia Williams, one of the primary researchers in this field.

http://theory.stanford.edu/~virgi/ipec-survey.pdf
> 2 votes

---
Tags: complexity-theory, computational-geometry
---


# Question
Title: Replacing n with 2n in asymptotic bounds
I am going through Normal Subgroup Reconstruction and Quantum Computation Using Group Representations by Hallgren et al.

In the proof of the theorem $6$ of the paper on page 632, the authors go on proving the difference between the probabilities of sampling all irreps, $|p - q|\_1$ of a subgroup inside the symmetric group $S\_n$.

I want to compute the same bound for the symmetric group $S\_{2 n}$. Should I just replace the $n$ in $2^{-\Omega(n)}$ and make it $2^{-\Omega(2n)} = 2^{-\Omega(n)}$?

Or, do I have to work it out from the scratch as follows?

$$ | p - q|\_1 = \sum\_\rho | p\_\rho - q\_\rho| \nonumber\\ \le \sum\_\rho \frac{d\_\rho}{\left(2 n\right)!} 2^{O\left( n\right)} n^{\frac{n}{2}} \nonumber\\ \le \sum\_\rho \frac{\sqrt{\left(2n\right)!}}{\left(2 n\right)!} 2^{O\left( n\right)} n^{\frac{n}{2}} \nonumber\\ \le \frac{2^{O\left( n\right)} n^{\frac{n}{2}}}{\sqrt{\left(2 n\right)!}} \nonumber\\ = \frac{2^{O\left( n\right)} n^{\frac{n}{2}}\sqrt{\left(2 n\right)!}}{\sqrt{\left(2 n\right)!}\sqrt{\left(2 n\right)!}} \nonumber\\ = \frac{2^{O\left( n\right)} n^{\frac{n}{2}}\sqrt{\left(2 n\right)!}}{\left(2 n\right)!} \nonumber\\ = \frac{2^{O\left( n\right)} n^{\frac{n}{2}}\sqrt{\left(2 n\right)^{2n}}}{\left(2 n\right)!} \nonumber\\ = \frac{2^{O\left( n\right)} n^{\frac{n}{2}}\left(2 n\right)^{n}}{\left(2 n\right)!} \nonumber\\ = \frac{2^{O\left( n\right)} n^{\frac{n}{2}}n^{n}}{\left(2 n\right)!} \nonumber\\ = \frac{2^{O\left( n\right)} n^{\frac{3n}{2}}}{\left(2 n\right)!} \nonumber\\ = \frac{2^{O\left( n\right)} n^{\frac{3n}{2}}}{\left(2 n\right)^{\left(2 n\right)}} \nonumber\\ = \frac{2^{O\left( n\right)} n^{\frac{3n}{2}}}{ n^{2 n}} \nonumber\\ = \frac{2^{O\left( n\right)} }{ n^{\frac{n}{2}}} \nonumber\\ = \frac{2^{O\left( n\right)} }{ 2^{-\frac{n}{2}} n^{\frac{n}{2}}} \nonumber\\ = \frac{2^{O\left( n\right)} }{ \frac{n}{2}^{\frac{n}{2}}} \nonumber\\ \le \frac{2^{O\left( n\right)} }{ \left(\frac{n}{2}\right)!} \nonumber\\ \lll 2^{-\Omega \left(n\right)} $$

# Answer
In mathematics we have the substitution principle. If a certain statement is true, then it also holds if you replace all occurrences of $n$ by some other expression, as long as that other expression has the same type as $n$. In particular, you can substitute $2n$ for $n$ and deduce that $|p-q|\_1 \lll 2^{-\Omega(2n)}$. You can then conclude that $|p-q|\_1 \lll 2^{-\Omega(n)}$, using the definition of $\Omega$.
> 1 votes

---
Tags: time-complexity, asymptotics, space-complexity, lower-bounds, probabilistic-algorithms
---


# Question
Title: Maximize function over a set with a transitive and antisymmetric relation
Let $\mathcal{R}$ be a transitive and antisymmetric relation defined over a finite set $X$.

For any set $S\subseteq X$ define $\Gamma(S)=\left\\{y\in S \mid \not \exists x\in S . (x,y)\in\mathcal{R}\right\\}$. (Thus, $y \in \Gamma(S)$ if it belongs to $S$ and no other element in $S$ "dominates" it.)

Suppose that each element is assigned a weight. This is represented by the function $w:X\to \mathbb{R}^+$.

The problem is to find a subset $S \subseteq X$ to maximize $\sum\_{z \in \Gamma(S)}w(z)$.

Is this problem polynomial-time solvable?

# Answer
You can compute the maximum weight of an antichain, or more generally the maximum weight of a union of $k$ antichains, by reducing to the maximum flow problem. See for example the following technical report by Cong:

Computing Maximum Weighted K-Families and K-Cofamilies in Partially Ordered Sets. J. Cong. UCLA CS Dept Technical Report CSD-930014, May 1993.
> 2 votes

---
Tags: algorithms, optimization, np-complete, np-hard, polynomial-time
---


# Question
Title: How to identify when to use Genetic Algorithm/Programming
I have been reading/studying on genetic algorithm/programming, and have implemented Traveling salesman problem.

TSP is basically a permutation/combination problem, and I can understand how GA helps to narrow down to the solution.

As far as I see GA is helpful in finding solution to

1. similar permutation/combination problems and
2. problems like pattern recognition.

Where/What are the other problem areas where GA could be applied and How(just provide a simple explanation) and What/Where GA can not be applied?

One case where I think GA can not applied are where there is no patterns, like Coin-Toss-Guess-Heads-Or-Tails Program, where outcome is purely luck.

Note: I am not looking for practical uses like printing circuit board or NLP. I am looking for what problems GA solves? or How to recognize that GA will help solve a certain problem instead of writing a complex algorithm.

Like TSP is a permutation/combination problem where possible solution could end up in 2.4 billion or more, and finding the right answer would be nearly impossible, Hence GA(or other optimization algorithm like simulated annealing) is useful in finding an optimal solution.

# Answer
> The key point in deciding whether or not to use genetic algorithms for a particular problem centers around the question:
>
> what is the space to be searched?
>
> If that space is well-understood and contains structure that can be exploited by special-purpose search techniques, the use of genetic algorithms is generally computationally less efficient. If the space to be searched is not so well understood and relatively unstructured, and if an effective GA representation of that space can be developed, then GAs provide a surprisingly powerful search heuristic for large, complex spaces.

(De Jong, Machine Learning, 1990 nr 5, pg. 351)

Here a key point is what is an *effective GA representation*.

GA initially detects biases in low-order schemas and converges on this part of the search space. Over time, biases in higher-order schemas are detected by combining information from low-order schemas (via crossover) and eventually GA converges (at least according to the building blocks hypothesis).

Situations in which lower-order schemas give misleading information to the GA about the probable fitness of higher-order schemas are said **deceptive**.

Most efforts at characterizing the difficulty of problems for GA have concentrated on deception, but there are other factors:

* the presence of multiple conflicting solutions or partial solutions
* the amount of information from lower-order building blocks (not how much this information is misleading)
* sampling error
* the number of local optima in the landscape ...

A general relation between a given problem's structure and the expected GA performance on that problem is a very open area of research (actually it's not even clear what is the relation between the degree of deception in a problem and the problem's difficulty for the GA).

In general GA is more suited to find good solutions quickly than to finding the absolute best solution to a problem.

Some references you could find interesting are:
> 12 votes

---
Tags: algorithms, optimization, genetic-algorithms
---


# Question
Title: If a comparison-based algorithm finds the ith smallest element, it also classifies all the elements as ≥a[i] or ≤a[i]
Suppose that an algorithm uses only comparisons to find the $i$-th smallest element in a set of $n$ elements. Show that it can also find the $i−1$ smaller elements and the $n−i$ larger elements without performing any additional comparisons.

I would like to show my solution. I ask you for checking it :)

Let $k$ will be $i$-th element. Let's suppose that we don't know if element $x$ is larger or smaller than $k$
Then it is impossible to know if $k$ is the $i$-th element. Contradiction.

It is very short proof. I can't see reason that it is not correct.

# Answer
Any comparison algorithm produces a partial order on the input (assuming all elements are distinct!). The key observation is:

> Suppose that in some partial order, some element $x$ has $\ell$ elements smaller than it. Then the partial order can be extended to a total order in which element $x$ has *exactly* $\ell$ elements smaller than it (i.e., it is the $(\ell+1)$st element).

Why is this enough? (The following is somewhat informal. See below for a more formal proof.) Suppose that your comparison algorithm outputs an element $x$ but knows only $j \< i-1$ elements smaller than it, that is, in the corresponding partial order, only $j$ elements are smaller than $x$. Then there is some total order in which element $x$ is in position $j+1 \< i$, and in particular, you cannot be sure that $x$ is the $i$th element. Similarly, if the algorithm knows only $j \< n-i$ elements larger than $x$, then there is some total order in which $x$ is in position $n-j \> i$ (using the dual version of the observation). Therefore the only way in which a comparison algorithm can be sure that $x$ is the $i$th element is if in the corresponding partial order, $x$ has exactly $i-1$ elements smaller than it and $n-i$ elements larger than it.

It remains to prove the observation. Given a partial order, we can generate a total order extending it by repeatedly performing the following operation:

> Choose a source (a minimal element) $y$, output it, and remove it from the partial order.

This (non-deterministic) algorithm outputs the elements in a certain order which is a total order extending the given partial order.

In order to apply this algorithm to prove the observation, consider the set of elements $P = \\{ y : y \leq x \\}$ which are at most $x$. In the first $\ell+1$ steps, we always choose a source from $P$ (this is always possible, though this requires an inductive argument). Then it continues in some arbitrary fashion. The resulting total order has $x$ as the $(\ell+1)$st element.

---

Our argument above, showing how the key observation implies the result, was somewhat informal. Here is a more formal treatment. We will actually show a slightly weaker result, that if a comparison algorithm finds the $i$th element correctly on all inputs with distinct elements, then it "knows" which elements are smaller than the $i$th element (can output them without further comparisons). The stronger result is left as an exercise to the reader.

We can think of the algorithm, when restricted to inputs with distinct elements, as a binary tree: each non-leaf compares two elements and has two children corresponding to the result of the comparison, and each leaf contains the output of the algorithm. We can furthermore assume that each vertex is reachable (we can always prune the tree to ensure this).

We can annotate each vertex with the partial order on the input elements, representing the algorithm's knowledge given the results of the preceding comparisons. We will show that at each leaf with output $x$, the corresponding partial order has exactly $i-1$ elements smaller than $x$ and $n-i$ elements larger than $x$.

The proof is by contradiction. Suppose that there is some leaf with output $x$ at which there are $j \< i$ elements smaller than $x$ (the other case, of having less than $n-i$ elements larger than $x$, is handled symmetrically). The key observation shows that there is some linear order $L$ extending the partial order in which $x$ is not the $i$th element. If we had input this linear order to the algorithm, it would have reached the same leaf, and so would have answered incorrectly – contradicting our assumption that the algorithm is valid.

We conclude that at each leaf with output $x$ there are exactly $i-1$ elements smaller than $x$ and $n-i$ elements larger than $x$.
> 4 votes

# Answer
Let me give some insight, as I do not claim it proves it ;) If algorithm uses comparisons to find $i$th element it means there is order of elements, as it must tell apart smaller and greater elements. It is not totally ordered as it partition set by pivot (which is $i$th element), but cannot tell ordere inside these two parts.

Here comes transitivity of comparison ($a \< b \wedge b \< c$ implies $a \< c$). So after performing original number of comparisons we can deduce (not compare) which elements are in which part, due to transitivity. If we build graph (as proposed on the site) while taking comparisons we add one edge per comparison.

Now we can traverse graph to tell these two sets apart (smaller than pivot and second greater then pivot).

Now if we suppose that there exists some number $v$ in this set that we do not know whether is smaller or greater. This contradicts finding $i$th element in first place, so it would imply that $v$ was not compared to any number in set, therefore it would be not possible to determine $i$th element.

I do not claim this is proof, and I have rewritten in better structured way what I have tried to point out earlier.
> 0 votes

# Answer
You just declare an equivalent statement of the problem in a different way without a proof. How can you prove that in order to know k is i-th order statistics, for every other element x, the position of x regard to k must be known?

The proof from here http://clrs.skanev.com/09/03/04.html is also wrong. To know relative position of x and k, we do not necessarily perform comparison between x and k, e.g., if x \< y, and y \< k then we know that x \< k without doing any comparison between x and k, so there is not edge pointing from node x to k because there is no comparison between them.

This problem is not that easy!
> 0 votes

---
Tags: algorithm-analysis, selection-problem
---


# Question
Title: Show that a language cannot be generated by linear grammar
I have a language $ L= \\{ w \in \\{a,b\\}^\* ; |w|\_b=2i, i \ge 0 \\}$ that is a language with even number of b's.

I found a grammar for it with these rules:

$S \rightarrow aS \ | \ bL \ | \ \lambda $

$L \rightarrow aL \ | \ bS \ $

How could I show that this language cannot be generated by linear grammar?

According to Wikipedia, a linear grammar is a context-free grammar that has at most one nonterminal in the right hand side of its productions.

# Answer
Your grammar is right-regular and can thus be used to prove that $L \in \mathrm{REG}$. Since every regular grammar is linear, your claim is impossible to prove.
> 2 votes

# Answer
A grammar whose only rules are of the form $X \to uYv$ and $X \to w$, where $u,v,w$ are terminals, can only generate words of odd length. Your language also contains words of even length. If you also allow rules of the form $X \to \epsilon$, then you can construct a grammar for your language (exercise).
> 1 votes

---
Tags: formal-languages, formal-grammars
---