# Question
Title: Computational complexity comparison of floating-point Euclidean distance calculation with binary fixed-point Hamming-distance calculation
This could relate to different applications, but my application of interest is in similarity-search systems based on high-dimensional feature vectors. In these systems, since search based on Euclidean distance is costly, the vectors are encoded as binary vectors. Then the search is done based on Hamming distance computation which is supposed to be faster than the Euclidean counterpart. My question is, **practically**, how much is this speed-up for an average architecture?

More formally, suppose we have a database $\mathrm{X} = \[\mathbf{x}\_1, \cdots, \mathbf{x}\_i, \cdots, \mathbf{x}\_N\]$ of $N$ vectors of dimension $n$, and a vector $\mathbf{y}$ of the same dimensionality. Now imagine two cases:

* Vectors are real-valued, i.e., $\mathbf{x}\_i \in \Re^n$. We are interested in finding the $\mathbf{x}\_i$ from $\mathrm{X}$ with the minimum Euclidean distance to $\mathbf{y}$, i.e.:

\begin{equation} i = \underset{{1 \leqslant i \leqslant N}}{\text{argmin}} ||\mathbf{y} - \mathbf{x}\_i||\_2. \end{equation}

* Vectors are binary, i.e., $\mathbf{x}\_i \in \mathcal{B}^n$ with $\mathcal{B} = \\{0,1\\}$. We are interested in finding the $\mathbf{x}\_i$ from $\mathrm{X}$ with the minimum Hamming distance to $\mathbf{y}$, i.e.:

\begin{equation} i = \underset{{1 \leqslant i \leqslant N}}{\text{argmin}} \sum\_{j=1}^n \big( \mathbf{y}(j) \oplus \mathbf{x}\_i(j) \big), \end{equation} where $\oplus$ denotes the XOR operation.

Both of these operations have complexity of $\mathcal{O}(Nn)$. However, the real case requires doing the operations in floating-point arithmetic while the binary case enjoys the fixed-point binary operations which are faster.

My question is, in practice, how are these complexities different? Can we say, very roughly though, that they have different constant factors and the ratio of these factors is a constant value? What would that constant value be then? Around 10 or 100 maybe? And how much is it architecture dependent?

# Answer
> 1 votes
The asymptotic complexity is the same (assuming you treat each floating-point operation as a constant-time operation, which is probably the right assumption). The *practical* running time may be different. Asymptotics ignores constant factors, but constant factors can be important in practice.

The way to tell how much faster it is in practice is to implement it and do some experiments, i.e., benchmark it on realistic workloads. Asymptotic analysis probably won't be very helpful in this case for predicting how much faster it will be. No one is likely to be able to give you a prediction for what the results of those experiments will be; you'll just have to try it and see.

# Answer
> 1 votes
The asymptotic complexity for the worst case is the same. Actually, the constant factors will be quite close together on a typical modern processor - if you don't calculate the execution time depending on n, but depending on the input size. The size of a vector of n bits is say 64 times less than the size of a vector of n floating point numbers. The execution time for a vectors of n bits will be lower only because 64 bit operations can be calculated simultaneously with one integer operation. So the ratio (execution time) / (input size) will be close.

In practice, the average complexity will be data dependent. As soon as a vector quite close to y is found, you may be able to prove that the distance to another vector xi is larger, based on examining a few vector elements only.

---
Tags: binary-search, euclidean-distance
---


title: Knight on a chessboard

text:
# Question
Title: Knight on a chessboard
This is a Hackerrank challenge

$Knight$ is a chess piece that moves in an L shape. We define the possible moves of $Knight(a,b)$ as any movement from some position $(x\_1, y\_1)$ to $(x\_2, y\_2)$ satisfying either of the following:
$x\_2 = x\_1 \pm a$ and $y\_2 = y\_1 \pm b$, or
$x\_2 = x\_1 \pm b$ and $y\_2 = y\_1 \pm a$

Given the value of $n$ for a square chessboard, answer the following question for each $(a, b)$ pair where :
$1 \leq a \leq b \lt n$

Constraints
$1 5 \leq n \leq 25$

What is the minimum number of moves it takes for $Knight$ to get from position $(0, 0)$ to position $(n-1, n-1)$? If it's not possible for the Knight to reach that destination, the answer is -1 instead.

If $a = b$ then it is simply $(n-1) / 2a$ if it is evenly divisible

What I cannot figure out is when some of the steps need to be backwards $x\_2 \lt x\_1$.

Can this be solved with an algorithm other than brute force?
If so what is the algorithm?

Brute force to me is iterate over all possible moves.

If brute force is it safe to assume $a$ and $b$ would never both be negative on a move? Answer is no. If brute force could it be limited to one diagonal or the other? Answer is no.

# Answer
You could use the breadth first search (BFS) algorithm. The knight may move at most to eight cell (from a single position) which means that if each cell is treated as a single node then degree of each node is at most eight and so the number of edges is at most $\frac{8N}{2} = 4N$, where $N = n^2$ is the total number of nodes/cells and $n\times n$ is the size of the chessboard. Since BFS' complexity is $O(V + E)$ your algorithm will run in $O(N+ 4N) = O(N)$.

**Warning**: do not try to create a graph from the chessboard. It is overkill. You just need to maintain queue and mark all visited cells as you iterate. While the knight is at the position $(i,j)$ just compute all possible moves from this position and push them into the queue if they are not already visited and you haven't yet reached $(n-1, n-1)$.
> 6 votes

# Answer
I am going to delete this

Just showing the accepted answer how I got the step count

```
public static void Visit(int row, int col, int n, Queue<int> queue, bool[] visited)
{
    if (row < 0 || col < 0 || row >= n || col >= n)
        return;
    int position = row * n + col;
    if (visited[position])
        return;
    visited[position] = true;
    queue.Enqueue(position);
}
public static int KnightHelper(int n, int i, int j)
{
    if (i == j)
    {
        return ((n - 1) % i == 0) ? (n - 1) / i : -1;
    }

    //try bfs
    bool[] visited = new bool[n * n];
    Queue<int> queue = new Queue<int>();
    int steps = 0;
    queue.Enqueue(0);
    while (queue.Count > 0)
    {
        int count = queue.Count();
        for (int m = 0; m < count; m++)
        {
            int position = queue.Dequeue();
            int row = (position / n);
            int col = (position % n);

            if (row == n - 1 && col == n - 1)
            {
                // Found solution.
                return steps;
            }

            Visit(row + i, col + j, n, queue, visited);
            Visit(row + i, col - j, n, queue, visited);
            Visit(row + j, col + i, n, queue, visited);
            Visit(row + j, col - i, n, queue, visited);
            Visit(row - i, col + j, n, queue, visited);
            Visit(row - i, col - j, n, queue, visited);
            Visit(row - j, col + i, n, queue, visited);
            Visit(row - j, col - i, n, queue, visited);
        }
        steps++;
    }
    return -1;
}

```
> 1 votes

---
Tags: algorithms, optimization, board-games
---


# Question
Title: Composition of polynomial and logaritmic function
Let $f$ be a computable function in $PSPACE$ It is true that Turing machine that computes $f$ can produce only $EXP$-size output at most. I see that $\log 2^n = n$ we can "control" the output. But, it doesn't convince me.

Please explain

# Answer
> 2 votes
Consider a Turing machine computing $f$. Suppose that it has $q$ states and $m$ tapes, that the tape alphabet is $\Sigma$, and that on input of length $n$, it uses at most $M(n)$ space. The number of possible configurations of the Turing machine is at most $N(n) = qM(n)^m|\Sigma|^{M(n)}$. In particular, if it runs for more than $N(n)$ steps then some configuration must repeat, and so it never terminates. Since the machine computes $f$, it does terminate, and so it runs in time $N(n)$. In particular, the output size is at most $N(n)$.

When $M(n)$ is polynomial, $N(n)$ is exponential ($2^{n^{O(1)}}$).

---
Tags: complexity-theory
---


# Question
Title: When talking about the length of a path in a graph, what exactly is a skip?
I'm studying for a final and when looking for the shortest path in a graph from one vertex to another, what is meant by k-skips?

One website defines it as the ability to change the weight of one edge to zero, as if you don't include it in the path distance.

Another one defines it as:

> $P\*$ is a k-skip shortest path from s to t, if it includes at least a vertex out of every k consecutive vertices in P

Which I can't seem to understand. I would appreciate some clarification in the matter.

# Answer
> 1 votes
The second definition that you quote is informal, and open to interpretation. Fortunately, the same paper On $k$-skip shortest paths by Tao, Sheng and Pei contains a formal definition, Definition 2 on page 4.

That said, *$k$-skip* is not a common term, and doesn't really have a universally accepted definition (or indeed, *any* universally known definition), except perhaps in work following up on the Tao et al. paper mentioned above.

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


# Question
Title: Prove correctness for computing the nth Fibonacci number for the pseudo code
How do we prove the correctness of this pseudo code by induction?

```
fastfib(integer n)
if n < 0 return 0;
else if n = 0 return 0;
else if n = 1 return 1;
else a ← 1; b ← 0;
   for i from 2 to n do
       t ← a; a ← a + b; b ← t;
return a;
end

```

# Answer
> 1 votes
The idea is that at the end of the $i$th iteration, $a = F\_i$ and $b = F\_{i-1}$. This is something that you can easily prove by induction. (Usually this sort of condition is called a *loop invariant*.)

# Answer
> 0 votes
Try to

* simplify the program and
* get it into a more functional form.

So

* Dump the negative case - there is no -3rd Fibonacci number.
* You can do without the explicit $1 \mapsto 1 $. No times round the loop gives that result.
* The function applied round the loop is $\[a, b\] \mapsto \[a+b, a\]$.
* If you take $b$ instead of $a$, you can get rid of the $0 \mapsto 0$ case too.

You then have something you can reason inductively about.

---

I find it much more convincing with real than with pseudo code. Translating your pseudo-code into Clojure ...

```
(defn fast-fib [n]
  (case n
    0 0
    1 1
    (first
      (nth (iterate
             (fn [[a b]]
               (let [t a
                     a (+ a b)
                     b t]
                 [a b]))
             [1 0])
           (- n 1)))))

```

... which the above transformations turn into the equivalent ...

```
(defn fast-fib [n]
    (second
      (nth (iterate
             (fn [[a b]] [(+ a b) a])
             [1 0])
           n)))

```

... which is much easier to reason about.

Other functionally expressive programming languages are available.

# Answer
> 0 votes
Here's my approach:

First I check that the code is indeed possibly correct by checking that it gives the correct result for say all n ≤ 10. If not then you have your answer.

Second I determine the values of a and b for 2 ≤ i ≤ 10 and see if I can find a pattern. If I can't find a pattern then I ask for help. If I find a pattern, then I use induction to prove the following:

```
If n ≥ 2, then at the end of the loop the values of a and b will be xxx and yyy.

```

Obviously with values that immediately prove the code is correct.

It happens quite often that the desired statement cannot be proven by induction directly - in this case giving the correct result fib (n) for some n doesn't imply the correct result fib (n+1) for the next larger n. You need to prove something about a and b.

---
Tags: correctness-proof, induction
---


# Question
Title: $P/Poly \setminus P$. What langugage does reside there?
What language is in $P/Poly \setminus P$? I was thinking of it by hours but I cannot come with an idea. Please help.

# Answer
One example is the language $$\\{ 1^n : \text{the $n$th Turing machine halts on the empty input}\\}.$$ This language has constant size circuits, but isn't computable.
> 1 votes

---
Tags: complexity-theory
---


title: Number of rooted labelled trees

text:
# Question
Title: Number of rooted labelled trees
According to Cayley's formula, we have number of spanning trees on a complete graph as n^n-2 and number of labelled trees with n vertices as n^n-2

If the tree is rooted then in each tree we can choose a root in n ways so total number of rooted labelled trees is n^n-1.

Here when computing the total number for rooted labelled tree, why don't we consider the ordering of elements ?

For example if we have a regular graph with 3 vertices then one of the spanning tree is 1-\>2-\>3. Here each element can be root and we can have remaining elements at right or left. So why don't we consider the ordering (right or left) in the formula?

# Answer
We don't consider the order of elements since what we are counting is the number of graphs on the vertex set $\\{1,\ldots,n\\}$ which are trees, that is, connected and having no cycles.

This is the usual graph-theoretic notion of tree. In computer science we often think of trees as rooted objects with ordered children, which is a similar but different concept.
> 1 votes

---
Tags: graphs, trees, combinatorics, spanning-trees
---


# Question
Title: How many recursively enumerable sets are there?
I'm trying to get some notion of how "many" recursively enumerable sets there are.

Here's one way of formalizing the question: consider $S =\\{q: q\in Q\cap \[0,1\]\\}$ and $R\subset S$ the set of recursively innumerable subsets of $S$.

What is the measure of $R$? My intuition is that it is 0 (i.e. a given set is almost surely not RE), but I am having difficulty proving it.

# Answer
Countably infinite. Each RE set corresponds to a TM $M$ recognizing that RE set, where the set of all TMs is countably infinite.
> 3 votes

---
Tags: computability
---


title: Why page size = size of one cache way?

text:
# Question
Title: Why page size = size of one cache way?
Why is that the page size equals the size of one cache way?

My book states "A direct-mapped cache cannot be bigger than a page".

# Answer
> 1 votes
Assume you have different processes sharing memory. That means you can have different pointers pointing to the same physical memory. If you have two different pointers, pointing to the same physical memory, but pointing to different entries in the cache, then you will be in trouble.

In practice, memory mapping is done page by page. So both pointers will have the same offset into a page, but the page numbers can be different. One pointer can have an even page number, one an odd page number. If your cache is bigger than a page, for example two pages, then two pointers with an even and an odd page numbers would point to different cache entries, exactly what we want to avoid.

Of course an operating system could just not do any memory mapping that creates two pointers to the same memory location pointing an odd number of pages apart, and then the cache could be two pages in size.

# Answer
> 1 votes
**First, your book is wrong.**

It is possible to have a direct-mapped cache larger than a page. For example, a while ago, when caches were made of fast SRAM chips, it was quite common to have simple direct mapped 64kB to 1MB L2 caches (for example Pentium 2 & 3). In modern chips, the caches are not simply direct mapped anymore, but their ways are often larger than a page.

The reason is about virtual and physical addresses, and aliasing.

Cache addresses and tags can be either virtual or physical, taken "before" or "after" the MMU. There is an issue with virtual cache indexes larger than a MMU page, because different processes could map the same physical address range into different virtual addresses, that don't coincide in the cache. There are several mitigation techniques, such as cache colouring (constraining the way the OS does memory allocation, grouping MMU pages to match the cache size), using write-thru caches and automatic invalidation of aliased lines after context switches...

The benefit of virtual addresses is that they are available earlier, as they don't need to cross the MMU. Except with very complex deeply pipelined out-of-order CPUs, this reduced latency can make a large difference.

The simplest solution is to constraint cache ways to the MMU page size, in that case, the low addresses needed for addressing the cache memory is identical for physical and virtual addresses. Then, after the cache has been read, the tags can more easily use physical addresses (reading cache memory and tags occurs at the same time as MMU address resolution)

---
Tags: computer-architecture, cpu-cache, memory-hardware, paging
---


# Question
Title: Show that checking if there exists word not containg patterns from list is in $PSPACE$
> There are given:
>
> * alphabet $Σ$ with some symbols $a,b$.
> * list of forbidden patterns
>
> Result: Is there exists word of form $a\Sigma^\*b$ such that it doesn't contains (as subword) any of word from list (list contains many words, expressed by patterns). Show that this problem is in $PSPACE$.
>
> Example to better understand patterns: $bbaaacb$ contains a word $a??c$, but $aacba$ doesn't contain $a??c$, where $?$ is some special symbol in $\Sigma$
>
> So patterns are like words with holes (?)

My approach is follwing:
Let $k$ will be max length among all patterns. There is no sense to consider longer words than $k$ because if exists word longer than $k$ such that it contain none of words from forbidden list then also exists word of length $k$.

So, using the fact that $PSPACE = NPSPACE$ we can guess word of length $i=1...k$ and check if it contains subword from forbidden list. Matching is easy to do in $NPSPACE$.

I am not sure about corectness of using nondeterminism. What do you think ?

# Answer
i think you are in the right direction, i will try to expand your answer a bit. first we want to prove that a problem is in PSPACE, which means there exists a TM that solves the problem with a polynomial space tape.

let M be a NTM that receives $w=\<Σ,list\>$ and does the following algorithm:

1) guess word of length $i=1...k$ given the $Σ$.this can be done in polynomial space depending on our input, since $O(k)=O(|w|)$ space.

2) check if there exists a pattern in the list which matches any of the strings of the word. this phase needs describing how exactly it can to be done, but it can certainly be done in polynomial space of $|w|$. hint: use 2 special characters to check each sub-string at a time.

and now since $PSPACE=NPSPACE$ (as you mentioned) ,if there exists a NTM that solves the problem in Polynomial Space tape we can conclude the problem is in $PSPACE$ and your solution was in a good direction.
> 2 votes

---
Tags: complexity-theory, space-complexity, nondeterminism
---


# Question
Title: Machine learning approach to auction game
I am newbie with machine learning. In order to learn more I decided to try solving a specific problem/game that I have in mind. The problem is the following:

I have a list of $N$ items which are auctioned in a random sequence. There are $n$ participants to the auction. They have a fixed budget and $M$ items to buy. Each agent will decide whether to make a bid and how much to bid each time a new item is auctioned; bids have to be integer numbers and the agent with the highest bid gets the item; correspondingly its budget is decreased of the amount of the bid. Items, once bought, cannot be released, so if an agent has already bought $M$ items, it cannot participate to other auctions. If nobody places a bid, the item is discarded and the auction continues with the next one. Thus, an agent ends its auction if it has bought $M$ items or the available budget has reached $0$.

At the end, the value of the final set $I$ of items items bought by each agent is evaluated by an external oracle function $f(I)$. The function is not explicitly known and will in general be more complicated that the sum of values of each item, e.g. two items may be essential parts of a single object and are worthless one without the other. However, it is known that $$ f(I \cup J) \geq f(I) + f(J).$$ Each agent is free to evaluate the function $f$ on any set of items. Each agent's goal is to maximize the value of $f(I)$, where $I$ is the set of items successfully bought by that agent.

Which strategy would you suggest to approach this problem? At each time, the agent has information about the list of items that have been auctioned, which participant has bought each of them and the costs, so that it knows the number of available slots and budget of each participant. According to these data, it must decide if and how much to bid for each item. Note that the list of items is fixed and the function $f$ are fixed. I suppose this is a reinforcement learning question but I don't have a clear understanding of how the input would be structured in this case.

# Answer
> 0 votes
There probably is no solution that will be optimal for all possible situations. So, you are left with heuristics: trying to find a technique that will often work well in the situations that arise for you in practice, but with no guarantees that it will work for everything. Machine learning might be one possible such approach.

You might start by trying to learn the function $f$. You said that the agent is free to invoke $f$ on any set of items. Therefore, a possible starting point is to try to learn a model that predicts $f$: e.g., given a representation of the set $I$, outputs an estimate for $f(I)$. You can easily collect a training set by querying $f$ on many sets and observing its output.

Reinforcement learning would be a plausible approach to the broader problem. There are many approaches to reinforcement learning, but in one typical approach, we need to compute a function $V(a)$ that computes the anticipated value of being in state $a$ (i.e., if the agent is in state $a$ and then follows its policy/strategy, what do we expect the final value of $f(I)$ will be?). Normally machine learning techniques are used to build a model that estimates the value of $V(a)$. This then requires forming a representation of the state $a$, i.e., a feature vector that summarizes or extract relevant information about the current state. The current state includes: (a) the set of items bought by this agent so far, (b) the budget and number of slots available to this agent, (c) the number and list of items remaining to be bought, and (d) information about the other agents, including what they've bought so far and the number of slots and budget remaining to them. So, you can think about how to build a feature vector that represents them, then apply standard methods for reinforcement learning to learn the function $V(a)$.

I suggest reading a tutorial on reinforcement learning to learn more about how it works and see some examples in a simpler setting.

---
Tags: machine-learning, game-theory, reinforcement-learning
---


# Question
Title: Interval schedule maximization when encountering intervals with equivalent end points
In interval scheduling, the ***greedy solution*** which *maximizes* the schedule that contains the largest number of *"compliant intervals"* involves initially sorting the list of intervals in ascending order by the end-times/point of each interval.

What confuses me, is if two or more intervals have the same ending time.

When performing the **initial sort**, should one base the sort of the sub-range of intervals on start time?

and if so should it be in ascending or descending order?

# Answer
> 1 votes
The greedy algorithm can be characterized as follows:

Let $I$ be the initial set of intervals

1) Select an interval, $x \in I$, with the earliest finishing time.

2) Remove $x$ and all intervals intersecting $x$ from $I$, obtaining $I^{'}$.

3) add $x$ to the solution

4) Set $I=I^{'}$

5) Continue until $I$ is empty.

Here, $x$ is some remaining interval that finishes before all other intervals in $I$. When we add $x$ to our solution we have already removed any interval with the same finish time as $x$ that may have had a start time which was "too early." If there is some other $y\in I$ with the same finish time as $x$ that is present when $x$ is chosen, then by necessity, both $x$ and $y$ begin after the last interval we added to our solution, so either is a legitimate choice.

---
Tags: algorithms, optimization, scheduling
---


# Question
Title: How are binary trees represented on disk
Assume I have a word document, the contents in it are stored on the disk as bits. Nothing so complex here. When the word processor reads those bits, it just knows how to display on screen.

But what about binary trees. They are just not data, they have route node, child nodes. How are they actually represented on disk?

I tried searching using this term "binary trees representation on disk". But I didn't find anything useful.

Let me know if I am not clear

**Update:**
I was looking for details on how actually they are stored on disk. Given this simple binary tree:

Any data is stored in bits on disk. How are these stored?

# Answer
*This may not be an exact answer but some information of interest related to your question*

Other answers have mentioned various ways in which the binary data structure can be represented and you might want to use one of them but mostly when using databases the **Adjacency List Model** and **Nested Set Model** are used for representing Binary Trees.

Binary Trees are mostly not used for storing data on disk and some alternatives are usually preferred.If you are interested in optimized data access, search,insertion and deletion on disk then you may want to consider these alternatives

B-Tree data structure is one of the alternatives used for storage on disk.It provides search, sequential access, insert, and delete operations in logarithmic time and is optimized for disk storage.

B-Tree data structure was created by Rudolf Bayer and Ed McCreight in 1972 to overcome a shortfall of Binary Tree i.e. using too many disk reads.B-Tree reduces the number of disk reads by allowing more keys in a single node ( typically making a B-tree node as large as the sector minimizes the number of access times).

SQL Server uses a further optimized extension of B-Tree data structure known as B+Tree in which only the leaf nodes hold the actual data and the rest of the nodes are pointers.

*According to Wikipedia B+Trees are also used for storing directory structures by some filesystems:*

> The ReiserFS, NSS, XFS, JFS, ReFS, and BFS filesystems all use this type of tree for metadata indexing; BFS also uses B+ trees for storing directories. NTFS uses B+ trees for directory and security-related metadata

**Update** How will a tree be represented as bits on the disk?

Trees can be represented by using static data structures like arrays in a fashion similar to this,consider each row tag as an array

```
//Node A can be represented as

[row 1][node A data in bits][separator bits]
[pointer to B i.e row 2][separator bits]
[pointer to C i.e. row 3][row1end]

//Node B can be represented as

[row 2][node B data in bits] [separator bits]
[no child flag][separator bits][no child flag][row2end]

//Node C can be represented as

[row 3][node C data in bits] [separator bits]
[no child flag][separator bits][no child flag][row3end]

```

I'd recommend studying some file formats so that you know how to represent logical data in a file, this also might be helpful

dcs.gla.ac.uk/Keith/Chapter.4/Ch.4.html
> 9 votes

# Answer
There are many ways to represent trees, each with their own set of advantages and disadvantages.

Here's an incomplete list:

* Use any *graph* representation, e.g.

+ adjacency matrix,
    + incidence matrix,
    + adjacency list,
    + linked nodes,

potentially adding a label for the root (if you have one).
* An array, listing nodes level by level (see e.g. heaps).
* Post- and pre-order sequence (together).

For each of these *conceptual* representations, there are many ways to *implement* it memory. For example, you can store adjacency matrices

* row by row,
* colum by column,
* augmented with pointers to skip (long) stretches of zeroes,
* partially (e.g. for diagonal matrices),
* implicitly as product of smaller matrices,

and so on.

Basically, you pick (or invent) a representation and an implementation that has performance characteristics that match the needs at hand.

---

That all said, the most standard representation of binary trees (unless you're looking at heaps), in the absence of contraindicating requirements, are probably *linked nodes*. It's what you get if you define binary trees similar to this:

```
type BinaryTree<Value>:
    Leaf
|   Node(BinaryTree, BinaryTree)

```

Note that this is, essentially, a specialized form of adjacency lists.

A natural implementation would be just the value for leaves, and a value with two pointers for inner nodes. A pointer to the (a) root would represent the (a) whole (sub)tree. How to arrange these in memory is, of course, yet another design decision (maybe deferred to automatic heap management).
> 7 votes

# Answer
There is no standard way to represent data structures of this kind.

One approach could be to sequentially write the content of every node during a *inorder* traversal, together with information aboud the tree structure.

I guess (this needs to be checked) that two bits indicating if a node has left and right children is enough to reconstruct correctly while reading back.

---

Note that it some applications, you needn't keep the original tree structure but only the content: for instance for a balanced search tree, you can just build a new tree from the keys.
> 2 votes

# Answer
How would you locate your word document?

By storing the location of the "word file" somewhere in an index which again gets stored somewhere, this structure itself represent a tree

For your ans,suppose you store the location of files("C:/abc/def/a.doc") in your "word document" and those files are also "word documents" which stores location of another files and so on, this is how trees are stored,however instead of file format they store memory location of other node and so on.
> -1 votes

---
Tags: data-structures, binary-trees
---


# Question
Title: Calculating the end-to-end delay of a message sent over a network
This is a problem from a MOOC on computer networking:

> We wish to send a message of size $150,000$ bytes over the network. There are four hops, each of length $20$ km and running at $100$ Mb/s. However, before sending we split the message into $1500$ byte packets. What is the end-to-end delay of the message? Use speed of light in copper $c = 2 * 10^8$ m/s, and round your answer to the nearest integer millisecond.
> **HINT**: Break the problem into two parts: the end-to-end delay of one packet and the delay of the rest of the message across the slowest link.

After struggling for a bit, I obtained the answer by following the hint as follows:

$$ 4\left(\frac{1500 \ B * 8 \ (b/B)}{100 \ Mb/s} + \frac{20 \ km}{2 * 10^8 \ m/s}\right) + \left(\frac{150000}{1500} - 1\right)\left(\frac{1500 \ B * 8 \ (b/B)}{100 \ Mb/s}\right) = 12.76 \ ms $$ The answer is correct but I don't understand why the packetization delay only was considered for the rest of the message. Why wasn't the propagation delay also considered for the remaining packets?

# Answer
In this case the propagation delay is more than the transmission delay, the propagation delay acts as a bottleneck for the whole network therefore the total time depend on it.

Consider a pizza shop, it takes 10 min to prepare pizza but 5 min to transport it, having infinite labour to transport, calculate how much time will it take to finsh job for 100 pizza.

Your ans might be correct but equation is wrong, you should draw the transmission diagram for better understanding.
> 0 votes

---
Tags: computer-networks
---


title: Matching with One-sided Preferences

text:
# Question
Title: Matching with One-sided Preferences
I'm dealing with a slight variation on a classic matching problem on sets $A$ and $B$), where:

* Set $A$ has an incomplete set of preferences (not all of $B$ is included)
* Set $B$ has no preferences whatsoever.

I want to find an $A$-optimal matching (e.g, for any $(a\_1 \rightarrow b\_1), (a\_2 \rightarrow b\_2)$, then either $b\_2$ is lower than $b\_1$ or does not appear in $a\_1$'s preferences, and likewise for $a\_2$) between $A$ and $B$, respecting $A$'s preference lists, and where ties between members of $A$ are broken randomly. I've been trying to apply the Gale Shapely algorithm to this problem, with random preferences for B, but it appears to have degenerate cases where the above criterion is violated.

A pre-rolled solution to this problem seems to be somewhat elusive, potentially because it's so obvious. There's a related SO question, Stable marriage problem with only one side having preferences, which states the no-preference issue, but the answers only cover how to check for a perfect matching, which does not necessarily guarantee the optimality of the result with respect to $A$'s preferences. Is there an algorithm that produces an $A$-optimal matching?

# Answer
We can suppose without loss of generality that the elements of $A$ have complete sets of preferences (if an element of $A$ is indifferent to some elements of $B$, we put them at the bottom of the element's preference list).

Our goal would be to match elements of $A$ and elements of $B$ such that the resulting matching is stable in the following sense. For any two elements $a\_1,a\_2 \in A$, either $a\_1$ prefers its current match to that of $a\_2$, or $a\_2$ prefers its current match to that of $a\_1$.

Here are two different algorithms for solving the problem. The first uses a greedy approach. Order the elements of $A$ arbitrarily: $A = a\_1,\ldots,a\_n$. Let $a\_1$ choose its top pick, let $a\_2$ choose the top available pick, and so on. This results in a stable matching since if $i \< j$ then $a\_i$ prefers its current match to that of $a\_j$.

A different approach, more similar to the Gale-Shapley algorithm, is iterative. Start with an arbitrary matching $f$. If there is a pair $a\_1,a\_2$ in which $a\_1$ prefers $f(a\_2)$ over $f(a\_1)$ and $a\_2$ prefers $f(a\_1)$ over $f(a\_2)$, then switch $f(a\_1)$ and $f(a\_2)$. This decreases the objective function $\Phi$ which is the sum over $i$ of the index of $f(a\_i)$ in $a\_i$'s preference list. Since $n \leq \Phi \leq n^2$ and $\Phi$ is an integer, we deduce that this algorithm terminates in $O(n^2)$ rounds.
> 1 votes

---
Tags: algorithms, matching, assignment-problem
---


title: Is connected forest a spanning tree?

text:
# Question
Title: Is connected forest a spanning tree?
> forest : set of disjoint trees.

So a connected forest is a forest, a tree, a spanning forest and a spanning tree.

Is that correct?

Edit: disjoint trees in the forest are connected by single edge, so as to make the forest connected

# Answer
> 2 votes
A connected forest is a tree (as well as a forest).

The terms *spanning forest* and *spanning tree* refer to an ambient graph. Given a connected graph $G$, a *spanning tree* is a subset of the edges of $G$ (spanning all vertices) which forms a tree. Similarly, if $G$ is a graph with $c$ connected components, then a *spanning forest* is a subset of the edges of $G$ (spanning all vertices) which is a disjoint union of $c$ trees.

---
Tags: graphs, terminology
---


# Question
Title: Is there an algorithm to compute the shortest Hamiltonian path in an undirected graph from one point to another in polynomial time?
Assumptions:

* given a graph with N nodes, and two specific nodes A and B
* the graph is undirected and no edge has a negative cost
* there exists at least one Hamiltonian path with A and B as an end points

Is there a way to find the shortest path from A to B that passes through all the other points?

Note: I'm only concerned with the specific given nodes A and B as endpoints, thus there's no need to compute for other Hamiltonian paths with different endpoints.

I'm thinking if it's possible to modify Dijkstra's shortest path algorithm to find Hamiltonian paths. Is it possible? If so, how? If not, is there any other algorithm that can be used? (in polynomial time)

# Answer
The case you are describing is NP-complete, so the answer is no.

I don't know if still remains NP-complete if the graph is a Euclidean graph. Anyone knows?
> 2 votes

---
Tags: algorithms, complexity-theory, graphs, shortest-path, hamiltonian-path
---


title: Size of Circular Queue

text:
# Question
Title: Size of Circular Queue
I am Implementing a Queue using circular arrays in C language .The Implementation uses one empty position to indicate that the queue is full.That is if the rear is two position behind front. The condition is we cant use a variable to count the entries in the queue as we insert or delete . I have created this function to find the size of queue with Time Complexity Big-Oh(n) because it starts with front and goes upto rear in a loop .

```
int QueueSize(Queue *q)
{
    if(QueueEmpty(q))
    {
        return 0;
    }
    else{
        int count=0;
    for(int i=q->front;;i=(i+1)%MAXQUEUE)
    {
        count++;
        if(i==q->rear) break;
    }
        return count;
}
}

```

Is there a way to find the size of queue in constant time ? Elements are inserted from rear and deleted from front ! My Queue starts from 0 and assume maximum queue size is 6 in below example

```
10 Appended at position 0
20 Appended at position 1
30 Appended at position 2
40 Appended at position 3
50 Appended at position 4
10 Removed from position 0
20 Removed from position 1
60 Appended at position 5
70 Appended at position 0
30 Removed from position 2
40 Removed from position 3
80 Appended at position 1
90 Appended at position 2
Queue Size:5
Position:4  Element:50 (front)
Position:5  Element:60
Position:0  Element:70
Position:1  Element:80
Position:2  Element:90 (rear)

```

# Answer
Suppose that the queue consists of elements $Q\[a\],\ldots,Q\[b\]$, where $Q = Q\[1\],\ldots,Q\[n\]$ is an array of length $n$. If $a \leq b$ then the queue contains $b-a+1$ elements, and if $a \> b$ then the queue contains $b-a+1+n$ elements.
> 1 votes

---
Tags: algorithm-analysis, data-structures, queues
---


title: Unique ID from date and rotating offset

text:
# Question
Title: Unique ID from date and rotating offset
Hopefully this is the right board for my question, We are facing an issue creating a unique ID from the following inputs :

* datetime (can be present more than once in the same set, cannot not be present in 2 different sets)
* offset ( an integer representing each line position in the set, the offset will be reset when switching to next/previous set)

As output we would like to get a unique ID, which will be used for sorting purpose later.

The concrete example for this issue is the rotating logs files. They will be collected into same database/table and later-on they will be shown and sorted/filtered based on this unique id.

Example :

* log1.txt (set 1)

+ 2017-08-06 10:36:07,988 something (let say offset=54)
    + 2017-08-06 10:36:07,988 something (let say offset=108)
    + 2017-08-06 10:36:07,988 something (let say offset=162)
    + ...
    + 2017-08-06 10:40:06,488 something (let say offset=1200) =\> A
* log2.txt (set 2)

+ 2017-08-06 10:40:06,788 xyz (let say offset=20)
    + ...
    + 2017-08-06 10:40:07,488 xyz (let say offset=200) =\> B
    + ...

Obviously a naïve uid function by adding offset as milliseconds to the date will lead to collusion, the frequency of the collusion cannot be foreseen, it depends on the logged text and the rotation size. (A & B for collusion example).

Regards

# Answer
> 0 votes
You can create a unique identifier by concatenating the two fields in question. If there are files where both fields are identical, concatenate an extra field disambiguating them.

---
Tags: hashing
---


# Question
Title: If problem is coNL-complete, is it NL-complete
We know from Immerman-Szelepcsényi theorem that $coNL=NL$. But, what about: If problem is $coNL\text{-}complete$, is it $NL\text{-}complete$? And why?

# Answer
> 4 votes
If the language $A$ is $NL$-complete then

1. $A \in NL$
2. Each problem in $NL$ is logspace reducible to $A$

Since $coNL = NL$ each problem in $coNL$ is logspace reducible to $A$ as well. Thus $A$ is $coNL$-complete.

# Answer
> 2 votes
Yes, if a problem is $coNL-complete$ it's $NL-complete$.

Take a language $L$ which is $coNL-complete$.

1. By theorem (that you mentioned) there exist a TM which accepts it in $NL$ so $L \in NL$.
2. Now, take a language $L\_1 \in NL$. By theorem $L\_1 \in coNL$ and by $L$ being $coNL-Hard$ there exist a log-space reduction $L\_1 \<\_L L$. So, $L$ is $NL-Hard$.

Therefore, $L$ is $NL-complete$.

The theorem : Immerman–Szelepcsényi theorem

---
Tags: complexity-theory, space-complexity
---


title: Lower Bound of Matrix Multiplication

text:
# Question
Title: Lower Bound of Matrix Multiplication
I am reading the textbook algorithms by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani

The authors state in page $67$:

> The preceding formula implies an $O(n^3)$ algorithm for matrix multiplication: there are $n^2$ entries to be computed, and each takes $O(n)$ time. For quite a while, this was widely believed to be the best running time possible, and it was even proved that in certain models of computation no algorithm could do better. It was therefore a source of great excitement when in $1969$, the German mathematician Volker Strassen announced a significantly more efficient algorithm, based upon divide-and-conquer.

The statement that interests my more in this quotation, is:

> it was even proved that in certain models of computation no algorithm could do better.

Could anyone support me with some references where I can find a proof of that kind?

# Answer
Strassen, in his paper describing Strassen's algorithm (Gaussian elimination is not optimal) mentions

> the result of Klyuyev and Kokovkin-Shcherbak \[1\] that Gaussian elimination for solving a system of linear equations is optimal if one restricts oneself to operations upon rows and columns as a whole.

The reference is to

> 1. Klyuyev, V. V., and N. I. Kokovkin-Shcherbak: On the minimizations of the number of arithmetic operations for the solution of linear algebraic systems of equations. Translation by G. I. Tee: Technical Report CS 24, June 14, 1965, Computer Science Dept., Stanford University.

The paper is available online.

In modern literature this result is virtually unknown, and I am not aware of any other lower bound on matrix multiplication beyond the $\Omega(n^2)$ lower bounds of Bshouty and Shpilka and the $\Omega(n^2\log n)$ lower bound of Raz.
> 6 votes

---
Tags: reference-request, matrices, multiplication
---


# Question
Title: Proving that converting min-heaps to max-heaps requires time Ω(n)
Suppose I have a min-heap SH stored inside an array. I can perform the operations:

* view-min(SH) in $O(1)$
* extract-min(SH) in $O(\log n)$
* insert(SH) in $O(\log n)$
* is-empty(SH) in $O(1)$

If I want to build a max-heap BH from the first one, the naive algorithm I can implement is obviously

```
BH <- build-heap()
while not is-empty(SH) do             O(n)
    elem <- extract-min(SH)           -> O(logn)
    insert(BH, elem)                  -> O(logn)
done

```

whose complexity is obvously $O(n \log n)$ worst case. Is this the best algorithm or there is any algorithm whose complexity is lower? Yes

According to Wikipedia we can at least achieve $O(n)$. Without making any assumption about our array being an heap. Can we use this fact to achieve $O(\log n)$ complexity? No

It should be impossible, because we have to deal with any of the $n$ items at least one time. Does this prove that the conversion is $\Theta(n)$?

# Answer
You could argue that the level-hierarchy gives more information, but not by much. Assuming a full max-heap of distinct values the $min$ element is on the deepest level of $\frac{n+1}{2}$ nodes. Unless there is some *additional* ordering to the heap, it would then take $\Omega(n)$ just to find the $min$ element.
> 4 votes

---
Tags: complexity-theory, algorithm-analysis, data-structures, lower-bounds, heaps
---


# Question
Title: Doubt regarding address calculation in two-dimensional arrays
I am reading about the address calculation formulas for one and two-dimensional arrays. I have two related doubts concerning it.

In one of the problems, we are asked to calculate the location of B \[1700\] for an array B \[1300....1900\]. Now, I understand that B \[1700\] is actually the 401th element in the array (correct?), so we can calculate its address.

But in another problem, we are given an array X \[-15....10,15.....40\] and are asked to determine the location of X \[15\]\[20\] but I don't see how it is even a part of the array since the "row" subscript(i.e. 15) is not contained in (-15....10). (According to me the last element of this array is X \[10\]\[40\]).

My second doubt is: In another question, we are given the array M\[-3......18,-8......7\] (stored column-wise where width of element = 8 bytes) and are asked to calculate the base address given that the address of element M \[5\]\[10\]=4000.

The solution proceeds as -

> M \[5\]\[10\] = BA + W\*(M\*(j-Lc)+(i-Lr)) therefore, M \[5\]\[10\]=4000 + 8\*(22\*(10-0)+(5-0))

i.e. my book answer takes Lc = 0 & Lr = 0 but I think it should be Lc = -8 and Lr = -3? So, which is it? Also can I write a program in which I can verify this for myself (specifically, how can I declare an array in c++ whose subscript doesn't start at 0?)? Thank you so much.

# Answer
For the first question, you can calculate an address for it -- languages that don't do array bounds checking will gladly calculate an address and read/write there, even if it is out of bounds. Of course, if the program is accessing an out-of-bounds element, that's typically a bug of some sort.

For your second question, you are right.

You probably won't run into arrays that start at an index other than 0 in practice very often (if ever), so I wouldn't worry too much about it. Your understanding seems solid.
> 1 votes

---
Tags: data-structures, programming-languages, arrays, lower-bounds, c
---


# Question
Title: Does Paxos consensus algorithm scale linearly?
I'm trying to build a P2P web application using Paxos to obtain a consensus value.

How well does Paxos scale? linearly? or what kind of distribution can you expect? E.g. in using 10 to 10,000 users in the network.

If not, are there consensus algorithms that scale well?

# Answer
> 1 votes
*Apologies if this answer does not belong to this site*

According to this paper released in 2013 which compares the performance over scale of **Paxos** and an optimized version of it **Fast Paxos**

> Paxos and Fast Paxos are optimal consensus algorithms that are simple and elegant, while suitable for efficient implementation

Reading further section **3.4. Scale Up** , you can find two graph plots.

*The **left** plot shows the number of requests served on y-axis and the number of replicas on x-axis.* *The **right** plot displays the average response time on y-axis and the number of replicas on x-axis.*

I think it gives an idea about what one should expect.They are optimal choices according to the paper and I don't know of any other

As far as it goes for the running time , I think I read somewhere that it's linear.

---
Tags: algorithms, distributed-systems, consensus
---


# Question
Title: If A is NL-complete then complement of A is also NL-complete?
We know that coNL = NL. But, is this also true?

> If A is NL-complete then complement of A is also NL-complete?

I don't see a reason for that it could be true.

# Answer
Start with the definition of $coNL$. $$coNL = \\{A\mid \overline{A} \in NL\\}$$ Since $NL=coNL$, every $coNL$-complete language is $NL$-complete as well. Let $A$ be a $NL$-complete problem. Then $$\forall B \in NL,B \leq\_L A$$ or equivalently $$x \in B \Longleftrightarrow f(x) \in A, \text{ where } f \text{is logspace computable}$$ $$x \notin B \Longleftrightarrow f(x) \notin A, \text{ where } f \text{is logspace computable}$$ $$x \in \overline{B} \Longleftrightarrow f(x) \in \overline{A}, \text{ where } f \text{is logspace computable}$$

and so $$\forall \overline{B} \in coNL,\overline{B} \leq\_L \overline{A}$$ This shows that $\overline{A} $ is $coNL$-complete and hence $NL$-complete (since $coNL=NL)$.
> 2 votes

---
Tags: complexity-theory, closure-properties, space-complexity
---


# Question
Title: $a^{2n}$ where $n\geq1$ is not Regular using Pumping Lemma
I'm having trouble understanding Pumping Lemma for $RL$ , i know that $0^{2n}$ is regular and we can design a FSM for it.
Here's my pumping Lemma statement

Let $p$ be the pumping length and my string is $0^{2p}$
1. $z=|0^{2p}|=\> 2p \> p $ (**Satisfied**)
2. $z=uvw$ such that $|uv|\geq p$, I'm choosing $|u|=n-p$ and $|v|=p$ so that $|uv|\geq p$ (**Satisfied**)
3.Now $u(v^i)w$, I choose $i=3$ then $|uvw|=2(n+p)$ which is even
But if $n=2$ then $|uvw|=2n+p$, how do i know if this could be even/odd?

# Answer
> 1 votes
You can't prove that a language is regular by applying the pumping lemma.

Regular Languages are a subset of Languages that satisfy the pumping lemma. So you can only proof irregularity with the lemma. (By assuming that the language is regular and coming to a contradiction)

One way to show that a language is regular, is e.g. constructing a Regular Expression, NFA or DFA (all of these being equivalent).

---
Tags: formal-languages, regular-languages, pumping-lemma
---


# Question
Title: Periodic Pattern recognition In a Sales Log
I'm pretty new in this field and I need some advice for my first professional challenge.

I'm trying to create a sort of *client segmentation* from a my company's sales log which has the peculiarity that the clients has a pretty long-term relationship and a periodic behavior.

1. Based on when does he has bought (Ex: Twice a month, once a week, once every three months...) determine the ***frequency*** of purchase.
2. I need to figure out the ***phase*** of this client, so I can know in what stage of his/her period is.
3. I would like to know how much does it buys each time ***purchase amplitude***

Once i have his **three** elements I want to be able to use that info to detect when the client changes his behavior (specially when they have an missing period or they decrease the buying amplitude)

I would like to get a really neat result, because i think that i will use it to a Markovian process.

So far I've tried astropy's lomb-scargle implementation but it seems that is too-precise and needs to many data points.

# Answer
> 1 votes
These are the steps you need to follow.

1. **Model**

You need to pick a model that you think explains your data. It can be very simple (e.g. linear regression) or very complex (e.g. a four-layer neural network). You want to pick as simple a model as possible!

*Example*: Assume sales follow $s(x) = a + b\sin(cx)$.
2. **Train**

Using one part of the data, you determine which parameters of the model fit your data best. The method of training depends on your model of choice.

*Example*: You fit the parameterized sine against the first half of your data with least-squares and find $(a,b,c) = (3,77, 13)$ is "best".
3. **Validate**

Inspect how well the model explains the rest of the data. You will have to decide in step 1 how you quantify quality here, and what your acceptance criteria are.

Separately, if that makes sense in your domain, apply the model entirely different data sets that *should* follow the same model if your hypotheses are correct. Does it predict anything there? What does the answer say about your model and/or your assumptions?

*Example*: Inspecting the squared error between $3 + 77\sin(13x)$ and the second half of the timeline data, you notice it is far too large.
4. **Iterate**

Unless the predictive quality of your model is good, go back to step 1. Sometimes, more training data can be the answer, too; note how that weakens your result, though.

---
Tags: machine-learning, pattern-recognition
---


# Question
Title: Locate all locations in a sorted array where arr[i]<arr[i+1]
Suppose you are given an array of $n$ integers with duplicates in non-decreasing order. The goal is to find the locations where a value is different from its neighbor. For example, given the array $arr={3,3,5,5,5,200,200,200,200,209}$, the output would be: ${2,5,9}$. Obviously, this can be done in linear time. I am trying to improve upon this using a binary search. Let $k$ be the number of output locations. In $O(k \log n)$ time we can get our answer. To find first location, check locations $2,4,8,$etc. Suppose you find that $arr\[1\]\<arr\[2^{j}$\], recursively search the interval from $2^{j-1}$ to $2^j$-1.

My QUESTION: In the worst case, $k=O(n)$. I do NOT want to ever pay $O(n \log n)$ since the naive algorithm is $O(n)$. However, I do not pay $O(n \log n)$ for $k=O(n)$ since the binary searches terminate in $O(1)$ time. How do I prove that the algorithm is worst case $O(k \log n)$ when $k \<\< n$ and never worse than $O(n)$?

# Answer
Here is a fairly simple fix. Anytime you "overshoot" in your search (I.e. $A\[i\]=A\[i+2^j\]$ but $A\[i\] \neq A\[i+2^{j+1}\]$ when you backtrack to find the correct index, also keep track of elements in that range that satisfy the inequality (may as well if your scanning over them anyway). You can pick back up at $A\[i+2^{j+1}\]$. This way, your running time is $O(n)$ worst case.
> 2 votes

# Answer
In fact you need start binary search $k$ times. Assuming, you use divide & conquer techniques (after found one location `x_i`, start binary search on `x_0..x_i-1` and `x_i..x_n` separately), algorithm will have runtime $O(n)$.

Algorithm would look as follows:

```
Search(low, high)
    mid = (low + high) / 2;
    if A[mid] == A[mid - 1]
    {
        if (A[low] < A[high])
        {
            Search(low, mid - 1);
            Search(mid, high);
        }
    }
    else
    {
        print k_i
        if (low < high)
        {
            Search(low, mid - 1);
            Search(mid, high);
        }
    }

```

You can see we have $p=O(\log n)$ depth of recursion. Each call takes $O(1)$ operations and we have $2^p = O(n)$ calls. Graph of recursive calls would never have more than $O(n)$ vertices since each pair of neighboring elements is compared only once (or not compared at all).
> 1 votes

# Answer
A crude argument would be that you dereference a pointer in the array a constant number of times (depending on how you code it...), and hence the asymptotic complexity is at most linear in the input array.

If you want to seek a more formal direction to prove this worst case bound, I suggest you to read about amortized analysis and use its' tools.

Amortized Analysis - Wikipedia
> 0 votes

# Answer
Let's say your algorithm is roughly: Let k = 0. Then repeatedly either find the smallest k' \> k such that arr \[k\] \< arr \[k'\], or prove that none exist. If you find k', output k' - 1, let k = k', and repeat the search.

You need an algorithm that achieves the following: 1. In the worst case, finding k' takes O (log n). 2. The number of steps finding k' is at most O (k' - k).

I think you can't guarantee n comparisons (because to guarantee this, you need to compare arr \[k\] \< arr \[k+1\] first in case all elements are different, then arr \[k\] \< arr \[k+2\] in case every second element is different, then arr \[k\] \< arr \[k+3\] in case every third element is different and so on).

You can achieve this with a guarantee of at most say 1.5n comparisons, if you grow the indices slowly initially.
> 0 votes

---
Tags: algorithm-analysis, runtime-analysis, binary-search, searching
---


# Question
Title: Is interaction more powerful than algorithms?
I've heard the motto **interaction is more powerful than algorithms** from Peter Wegner. The basis of the idea is that a (classical) Turing Machine cannot handle interaction, that is, communication (input/output) with the outside world/environment.

> How can this be so? How can something be more powerful than a Turing Machine? What is the essence of this story? Why is it not more well known?

# Answer
Turing machines can handle interaction just fine, using oracle tapes. It works are follows: from the point of view of a computer that handles interaction, the input of the operator is simply another sequence of bits that it sent into the computer from time to time. We all know that a lazy sysadmin could write a script to send the input to the program when it is requested, so that the sysadmin could go on break earlier. The interaction machine has no way to know if there is really a live operator at the console, or if the input is being piped from another program.

Having all the interaction input prepared ahead of time is the same, in theoretical terms, as having all the input on a separate tape that is used by an oracle Turing machine. Whenever the computer would normally request interaction from the operator, the machine instead reads from the input tape. If the thing read from the tape seems invalid in some way, the Turing machine does exactly what the interaction machine would do on receiving that input.

I would guess that Wagner is aware of the ability to use oracle tapes to code input, so you have to take his comments with a grain of salt, or you have to ask what he actually means. I believe that people who think about interaction are generally worried about two things:

* "Real" computers do have interaction, but algorithms as defined by Turing don't. We can get around this by coding the input on oracle tapes, but this still does not match the way that real computers operate. It might be nice to study models of computation that are more closely aligned with real computers.
* Oracle-based algorithms are not often considered in day-to-day computing because normal computers don't come with a magic "oracle" to supply data. But we might be able to actually just use a person as the oracle. If the person understands the data that is being requested, they may even be able to help the algorithm along, thus improving its performance. In other words a human may be able to provide a useful oracle tape rather than simply a random one, and in principle this might lead to faster or more powerful computing methods compared to non-oracle-based ones. A similar thing happens with randomized computing, after all, where the machine is given a sequence of random bits as an extra input.
> 11 votes

# Answer
Recently ACM held Ubiquity symposium 'What is Computation?' in which Peter Wegner published an article which reflects his views on Interactive computing.

Here are two excerpts from the article by Peter Wegner:

> One new concept, missing from early Turing machines, is "Interactive Computing," which accommodates interaction with the environment during the computation.
>
> Interaction machines can perform more powerful forms of computing than Turing machines, and can perform the kind of thinking proposed by Turing because interaction improves their performance over that of Turing machines.

However, Fortnow, who has an article in the same symposium, appears to disagree with the Wegner views and believes that interactive computing does not offer any additional power over Turing Machines.

To add to the mix, it appears that we are still debating and defining computation. Moshe Vardi has an article, What is an Algorithm?, Communications of the ACM, Vol. 55, No. 3, March 2012.

Vardi reports on two new definitions of algorithms. The first is proposed by Gurevich and the second by Moschovakis.

> Gurevich argued that every algorithm can be defined in terms of an abstract state machine.
>
> Moschovakis, in contrast, argued that an algorithm is defined in terms of a recursor, which is a recursive description built on top of arbitrary operations taken as primitives.
> 8 votes

# Answer
Turning Machines model computation, and don't have a concept of interaction. In that sense a machine that supported interaction with an outside system can do things a Turning Machine can't. But the computation done *between* bit of input from an outside source can obviously always be modelled by a Turing Machine, so even an "IO Machine" can't do anything *with* outside input that a Turing Machine couldn't do.

In some sense such a machine may be able to "decide" problems that are undecidable by Turing Machines, but only if you imagine that the system it is interacting with has super-Turing-Machine powers *and is reliable* (in some way; probabilistic reliability would be enough).

Imagine a program for an IO Machine like: "for any initial tape input, print the tape contents, then read a symbol from outside input; accept if the symbol is 1 and reject otherwise". This program can decide **any** problem. But *only* if the outside system it can interact with is capable of deciding the problem; to me that's not a very interesting way of saying that the IO Machine of is able to decide problems that are undecidable by Turing Machines.

I think it would always be possible to represent an interactive computation by imagining a machine that takes as input on its tape an encoding of some prior configuration together with an outside input, and have the machine halt with its tape containing an encoding of a configuration together with output. Then the process of "running a program" is repeatedly running this Turing Machine in a mechanical fashion, with the only "non-mechanical" part being however the outside input is sourced. I'm certain that you could prove that if such a system got its input by giving its output to *another Turing Machine* set up to operate in a similar manner, then the combined system has identical computational powers to a single Turing Machine. I find that a convincing argument that interactive computation is no more powerful than non-interactive computation, *unless the system the computation interacts with is more powerful than a Turing Machine*.

---

There is a non-theoretical sense in which interactivity can add to a computer's ability to solve problems, however. There are many things which humans do very accurately that we don't know how to get computers to do very well. But there are also many many things that humans are rubbish at that we can get computers to do. Combining these two can lead to projects such as reCaptcha, which is effectively automatically digitising books by farming out the problems of recognising words to humans in difficult cases. The resulting system of computer + human labour achieves a result that is currently impractical to achieve with either the computation alone or the human labour alone.
> 8 votes

# Answer
I do not think models with IO are "more powerful" than Turing machines, they just model different things.

In theory, you could view IO as (noisy?) oracle. With a perfect oracle you can computer Turing-uncomputable functions; but where to get the oracle from? Humans are the only "super-Turing" choice (if there is any) and we are known to be very unreliable.

A class of programs that fit this model are interactive proof assisstants (e.g. Isabelle/HOL, Coq). They deal with undecidable proof spaces but (arguably) every proof can be found (and checked) with suitable user input.
> 6 votes

# Answer
Check this out :) "***Turing's Ideas and Models of Computations***" https://www.cs.montana.edu/~elser/turing%20papers/Turing%27s%20Ideas%20and%20Models%20of%20Computation.pdf
> 0 votes

---
Tags: computability, computation-models
---


title: Algorithm to create tournament brackets

text:
# Question
Title: Algorithm to create tournament brackets
I'm designing a web app to host e-sports tournaments and want to create an algorithm that generates tournament brackets.

Given a list of participants' user ID's (minimum 4, maximum let's say 64), I want to generate a bracket in the form of a list of pairings, where each element of the pair represents a match participant or a reference to the winner of a previous match, i.e. User 1 vs. User 2, Winner of match 1 vs. User 3, and so on.

A simple example, given the array of entrants:

```
(user1, user2, user3, user4)

```

We get the end result as a set of pairs, in the logical order:

```
(user1, user2), (user3, user4), (winner0 vs winner1)

```

Where `winner0` refers to the winner of match 0 (the first pair in the result set). Thus, the winner of the last match in the set is the winner of the tournament.

I need this to work with any size entrant list between 4 and 64 (or some other theoretical maximum), not just for powers of 2. When the entrant count is not a power of 2, some entrants must get one more or one fewer match in order to fill in the entire bracket. All initial placements will be random.

I suppose it's also possible to represent the result as a binary tree, but I'm not sure I will be able to apply it that way.

# Answer
> 2 votes
Create a new node for each entrant, then put a pointer to each such node in a FIFO queue. Remove the two pointers $p\_1, p\_2$ in front of the queue, then create a new node with children $p\_1$ and $p\_2$, and enqueue a pointer to it. Repeat until the queue size is $1$. The one element you're left with is the root of a binary tree that encodes the bracket.

# Answer
> 0 votes
I worked on a PHP / Laravel plugin that generates brackets with / without preliminary round robin. Maybe it can be useful to you, I don't know what tech you are using. Here is the github.

https://github.com/xoco70/kendo-tournaments

Hope it helps!

---
Tags: algorithms, binary-trees, randomness
---


title: Computer Program vs. Algorithm

text:
# Question
Title: Computer Program vs. Algorithm
It's said that a program include algorithms, however if we refer to their definition, an algorithm is a sequence of instructions written to perform a specified task and a computer program is also a sequence of instructions to perform a (some) tasks with computer.

Then what makes a program different from an algorithm? is it a type of algorithm too?

In fact, I look for formal definitions for an algorithm and a computer program so I can distinguish them from each other or identify algorithms within a program.

**Update**:I have noticed in Wikipedia by an informal definition (at least syntactically) any program is an algorithm.

> An informal definition could be "a set of rules that precisely defines a sequence of operations." which would **include all computer programs**, including programs that do not perform numeric calculations. Generally, a program is only an algorithm **if it stops eventually**.

# Answer
> 13 votes
I'm going to give the same answer as I gave the previous time this question came up.

First, understand that there is no good *formal* definition of "algorithm" at the time of writing. The key word here is "formal".

However, there are smart people working on it.

What we know is that whatever an "algorithm" is, it sits somewhere between "mathematical function" and "computer program".

A mathematical function is formal notion of a mapping from inputs to outputs. So, for example, "sort" is a mapping between a sequence of orderable items and a sequence of orderable items of the same type, which maps each sequence to its ordered sequence. This function could be implemented using different algorithms (e.g. merge sort, heap sort). Each algorithm, in turn, could be implemented using different programs (even given the same programming language).

So the best handle that we have on what an "algorithm" is, is that it's some kind of equivalence class on programs, where two programs are equivalent if they do "essentially the same thing". Any two programs which implement the same algorithm must compute the same function, but the converse is not true.

Similarly, there is an equivalence class between algorithms, where two algorithms are equivalent if they compute the same mathematical function.

The hard part in all this is trying to capture what we mean by "essentially the same thing".

There are some obvious things that we should include. For example, two programs are essentially the same if they differ only by variable renamings. Most models of programming languages have native notions of "equivalence" (e.g. beta reduction and eta conversion in lambda calculus), so we should throw those in too.

Whatever equivalence relation we pick, this gives us some structure. Algorithms form a category by virtue of the fact that they are the quotient category of programs. Some interesting equivalence relations are known to give rise to interesting categorical structures; for example, the category of primitive recursive algorithms is a universal object in the category of categories. Whenever you see interesting structure like that, you know that this line of enquiry will probably be useful.

# Answer
> 7 votes
Ultimately, the difference is one of perspective. A program is a program: a sequence of statements in some language, perhaps a programming language or machine-level instructions. Algorithms are usually described at a higher level than machine instructions or programming language statements but just how high a level is rather flexible. For example, in some circumstances, "Sort the array, then look at the $k$th element" is a perfectly good description of an algorithm for finding the $k$th largest object in an array; in other circumstances, you might want to specify much more detail about how the sorting takes place.

As you say, an algorithm is something like "a process or set of rules to be followed in calculations or other problem-solving operations, especially by a computer." So, literally speaking, every program *is* an algorithm. Usually, though, we speak of programs *implementing* algorithms. Usually, when describing an algorithm, we avoid the low-level detail of exactly how things are implemented, assuming that a competent programmer would be able to implement it in the langauge of their choosing.

# Answer
> 5 votes
Algorithms in the Turing-complete mindset are usually specified by input and output. Real programs do more; they

* communicate with the user,
* communicate with other machines,
* react to the environment,
* do not terminate and are still useful,

and more. These things are usually not considered in algorithms or theory of computation, but are essential for most programs.

# Answer
> 3 votes
An algorithm is a concept or idea. It is a formal approach for solving a problem. Algorithms can be expressed, or implemented, in a variety of programming language (usually, almost any language can implement any algorithm). For some examples you should read through the Sorting Algorithms in Wikipedia.

A computer program is a specific sequence of instructions in a specific programming language. A program may contain the implementation of many algorithms. Excel is a program, but it's sorting capabilities are the manifestation of an algorithm.

# Answer
> 2 votes
* An algorithm is a systematic approach to solving a specific problem.
* A program is a set of instructions for a computer to follow.

A program therefore does not even need to solve a problem. I'm sure we can all think of several programs that have caused more problems than they've solved. A program can be an implementation of many algorithms, or an algorithm can be implemented by patching together many programs. A program can even contain no algorithms. For example, the empty program which simply exits, or perhaps even a Hello World, could be considered a program with no algorithm.

Since an algorithm solves a specific problem, it is focused on a specific whole concept. An algorithm therefore provides abstract steps for processing one set of related information into a different set of derived information. A program does not require its constituents to be at all conceptually related. For example, a program can have an easter egg, but a thing properly called an algorithm should not. You can have a virus or trojan lurking in a program, but not in an algorithm. The closest an algorithm can get to this would be something like a backdoor in an encryption algorithm, where the planned flaw is part of the information relationship established by the algorithm.

And lastly, a program, as it is short for a computer program, tautologically requires a computer. An algorithm does not. If I systematically separate the shirts, pants, and socks from my laundry before putting them away, this is an algorithm. It deals with related inputs and outputs, can be described in a flow chart, and has calculable consequences in terms of efficiency (for example, the number of clothing pieces which must be compared to find matching socks).

# Answer
> 2 votes
Here is a couple of ways to draw the line between an algorithm and a program:

# Meaningful Purpose

Programs are written with a purpose and represent an attempt to achieve a goal. Algorithms may be viewed as tools to achieve that goal.

E.g. a screwdriver is an algorithm to modify the state of a screw but the screwdriver itself does not hold a purpose to do that. The purpose is in the head of the screwdriver operator who holds the program like putting up shelves.

# Business logic

This point strongly relates to the purpose of a program. Since programs have purposes they inevitably have bits of real world in them like specific dates, measurements, technologies, names etc.

Algorithms on the other hand contain neither business logic nor bits of real world and instead of operating on specific values operate on variables.

E.g. in this sense you can compare a mathematical function like `f(x) = x^2` which is abstract and operates on variables to a cooking recipe which contains precise values (at least one for reference).

# Result

This point strongly relates to the business logic of a program. An agent (like a web browser user) consumes the result of a program not the result of an algorithm.

E.g. the consumer of a cooking recipe consumes the cake not the result of whipping cream or heating oven.

# Answer
> 1 votes
> An algorithm is a self-contained step-by-step set of operations to be performed to solve a specific problem or a class of problems.
>
> A computer program is a sequence of instructions that comply the rules of a specific programming language , written to perform a specified task with a computer.

Algorithms are general and have to be translated into a specific programming language (implemented).

# Answer
> 1 votes
An algorithm is expressing our idea or solution for specific problem in step by step approach.it is only problem solving and human understandable approach not for computer system

Program is step by step instructions which implemented for solving problem by computer system .it must be understandable by not only programmer also computer.

# Answer
> 1 votes
The other answers here, I think, miss an important point. The definition of 'algorithm' which I was taught included the requirement that the procedure *halts on all inputs*. Naturally that makes 'program' a broader class of procedures than 'algorithm', since some programs halt on all inputs and others do not.

# Answer
> 1 votes
*I am pretty sure that other answers are good enough to take the lead but here's how I see the difference between an algorithm and program*

* ***An algorithm consists of simply the steps (machine independent) needed to be followed in some order to solve a problem.***
* ***A program is an instruction set for a specific type of machine to put an algorithm to practice*.**

For example.

Let's say you have an algorithm that has a step for reaching to a particular place before doing some other step.Now how this step of reaching will be carried out is not exactly defined.You may choose to walk or run or take a bus for doing it but that depends on how you choose to implement it (which is your program).

***You can say that an algorithm is an abstraction of a program i.e. missing the exact details but lays out a plan to do something.***

---
Tags: algorithms, terminology, programming-languages
---


title: function in big O but not in little o?

text:
# Question
Title: function in big O but not in little o?
Give two functions that is in O(n^2) but not in o(n^2).

The answer is nlogn and n,But I think a lot but can't understand why answer are them.I doubt answers is wrong.

And this question,Give two functions that is in big-omega(n^2) not in little-omega(n^2)?

The answer is n^2logn and n^3.But I think a lot but can't understand why answer are them.

# Answer
Where have you got those answers?

**1.** Answers are wrong if *that* was the task. The simplest answer is $n^2$. Why? Because this function satisfies restructions: $\lim\_{n\to\infty}\frac{f(x)}{n^2}\>0$ (not in $o(n^2)$ requirement) and $\lim\_{n\to\infty}\frac{n^2}{f(x)}\>0$ (in $O(n^2)$ requirement).

**2.** Exactly the same answer.
> 2 votes

# Answer
The answers you give are wrong. It is easy to verify that $n, n\log n \in o(n^2)$, and similarly $n^2 \log n, n^3 \in ω(n^2)$.

> Give two functions that is in $O(n^2)$ but not in $o(n^2)$.

Looking at the definitions, we see that there are two ways to come up with such a function:

* Pick any function from $\Theta(n^2)$.

Besides the obvious candidates of the form $cn^2 + o(n^2)$, there are also more obscure ones like, for instance $ 2^{\frac{\sin n}{\log n}} \cdot n^2$.
* Pick any function $f \in O(n^2)$ for which $\lim\_{n \to \infty} f(n) \cdot n^{-2}$ does not exist.

Simple examples are $(2 + \sin(n)) \cdot n^2$ or $2^{\sin n} \cdot n^2$ or

$\qquad \displaystyle f(n) = \begin{cases}n^2, &n \in 2\mathbb{N};\\n, &n \in 2\mathbb{N}+1.\end{cases}$

There are many more.

I'll leave the proofs to you as an exercise, as well as the symmetric case with $\Omega$ vs $\omega$.
> 6 votes

---
Tags: asymptotics
---


# Question
Title: The border between P and NP for some problems
A problem is defined to be in **NP** when it can be reduced to another **NP** problem in polynomial time.

In Karp's 21 NP-complete problems, the most famous ones are presented. However, I wonder (and could not find a reference) for some of them, what happens if we "relax" the objective function.

For instance, say Hamiltonian path problem: given a graph $G$ with $n$ vertices, is there a simple path $P$ of length $n$? (i.e. passes through all vertices). This problem is **NP**-complete.

But what if I ask for a path $P$ whose length is $n-k$? At which value of $k$ the problem becomes tractable?

Similarly, 3-coloring problem: color the vertices of a graph with three colors such that no two adjacent vertices have the same color. What if I allow $k$ pairs of adjacent vertices to be the same color?

Is this descripton the very same thing with approximation algorithms? Or is this a different concept?

# Answer
Approximation algorithms are most often encountered in the context of optimization problems. Consider the problem of minimizing some function $f$ subject to constraints $C$. An $\alpha$ approximation algorithm (where $\alpha$ can depend on some parameters of the instance, such as the number of vertices in a graph) is a (usually) polynomial time algorithm which produces a feasible solution (that is, one satisfying the constraints $C$) whose value is at most $\alpha$ times the optimum.

In some cases, *bicriteria* approximation algorithms are considered. These are algorithms as above, with the only difference being that the solution doesn't satisfy the constraints $C$ but rather some weaker version of them $C'$. See this question for some examples.

In the case of 3-coloring, your notion is very similar to the following optimization version of 3-coloring: given a graph, find a 3-coloring which violates the least number of constraints. There are several hardness results that show that it is difficult to approximate the optimum, even if you are allowed to use more colors (in the spirit of bicriteria optimization problems). For example, Guruswami and Khanna, in their paper On the hardness of 4-coloring a 3-colorable graph, show that it is NP-hard to distinguish between the following two classes of graphs: (i) 3-colorable graphs, (ii) graphs in which every 4-coloring has an $\epsilon\_0$-fraction of monochromatic edges (for some constant $\epsilon\_0$).

Similarly, your relaxation of the Hamiltonian path problem can be rephrased as an optimization problem: the longest path problem. It is NP-hard for any constant $k$, and even for much larger $k$; see the paper mentioned in Wikipedia, On approximating the longest path in a graph by Karger, Motwani and Ramkumar.
> 5 votes

---
Tags: complexity-theory, np-complete, np
---


title: Prove that $P/poly$ is closed on $^*$.

text:
# Question
Title: Prove that $P/poly$ is closed on $^*$.
Prove that $P/poly$ is closed on $^\*$. Please help me with that because I cannot deal with that.

# Answer
Note that for $w\in\\{0,1\\}^n$ it holds that:

$w\in L^\*\iff w\in L \lor \left(\exists i\in \\{1,...,n-1\\} : w\_1...w\_i\in L^\* \land w\_{i+1}...w\_n\in L\right)$.

You can translate the above into a dynamic programming algorithm for deciding $L^\*$. One way to do that is keeping an array $A\[i\]$, where $A\[i\]=1\iff w\_1,...,w\_i\in L^\*$, and filling it from $i=0$ upwards. The running time $T(n)$ is bounded by $T(n)\le T(n-1)+T\_L(n)$, where $T\_L(n)$ is the time required for deciding membership to $L$ on inputs of length $n$. Hence, $T(n)\le nT\_L(n)$, which is polynomial if $L\in P$.

This works fine if $L\in P$, however when $L\in P/Poly$, you have a polynomial time machine $M(x,y)$ and a sequence of advice $\\{\alpha\_n\\}\_{n\in\mathbb{N}}$, where $\alpha\_n\in\\{0,1\\}^{p(n)}$ for some polynomial $p$, such that $x\in L \iff M\left(x,\alpha\_{|x|}\right)=1$. The above procedure requires deciding membership to $L$ on inputs of length at most $n$. Thus, your advice for deciding $L^\*$ on length $n$ inputs will be $\beta\_n=\alpha\_0,\alpha\_1...,\alpha\_n$ (which is still polynomial), and whenever you need to check membership to $L$ on a word $w$ of length $0\le i\le n$, execute $M(w,\alpha\_i)$.
> 1 votes

# Answer
To my eye, it is sufficient to show that there exists polynomial advice such that it recognize $L=M^\*$, where $M\in P/Poly$.

It is obvious that such advice exists because we can split advices of particular words (recognizing by $M$) with symbol $\\#$. Then, we have polynomial advice: $w\_1\\#w\_2\\#...\\#w\_n$, where $w\_i$ is advice for some word recognizing by $M$. Polynomial machine for language $L$ can recognize it,simply launch $M$ on each $w\_i$.
> 0 votes

# Answer
INPUT: $w=w\_1..w\_n$

```
for l = 1 to n
    for i = 1 to n - 1
        j = i + l - 1
        if w_ij is accepted by M then A[i,j] = true
        else
           for k = i to j
              if  A[i,k] and A[k+1,j] then A[i,j] = true

if A[1,n] then accept
else reject

```

Where `w_ij` is substring starting at $i$ and ending at $j$. $M$ is Turing machine recognized $L \in P/poly$. It work in polynomial time.

@Ariel, I don't see how it differs with algorithm for polynomial.
> -1 votes

---
Tags: complexity-theory
---


# Question
Title: Understanding kQBF: changing order of quantification?
2QBF is a problem of determining whether formula $\exists X~\forall Y:\varphi(X,Y)$ is valid. $X$ and $Y$ here are sets of variables. Next, 3QBF asks if formula $\exists X~\forall Y~\exists Z:\varphi(X,Y,Z)$ is valid. But what I can't understand is following:

1. Can't we change order of quantification? E.g. isn't following true $\exists X~\forall Y:\varphi(X,Y) = \forall Y~\exists X:\varphi(X,Y)$?
2. If we can, what prevents us from doing this in the second case and reducing 3QBF to 2QBF? E.g. $\exists X~\forall Y~\exists Z:\varphi(X,Y,Z) = \exists \\{X, Z\\}~\forall Y:\varphi(X,Y,Z)$.

The main idea is to reduce the number of alternations to one.

---

What I thought:

Let we have a formula $\forall x\_1~\exists y\_1...\forall x\_k~\exists y\_k:\varphi(x\_1,y\_1...x\_k,y\_k)$. Then we can construct a truth-table (theoretically) where columns will be sorted this way:

```
x_1 x_2 ... x_k y_1 ... y_k ф
  0   0 ...   0   0 ...   0 _
  0   0 ...   0   0 ...   1 _
  .   . ...   .   . ...   . .
  .   . ...   .   . ...   . .
  1   1 ...   1   1 ...   1 _

```

Then we can divide table (no row/column moving) in $2^k$ parts each containing $2^k$ rows. If each of that part has satisfiying assignment, formula is valid. *But that means that there is no difference at all in which order we should assign variables, since **truth-table of formula is independent** on the quantifiers.*

In other words following must be true: $\forall x\_1~\exists y\_1...\forall x\_k~\exists y\_k:\varphi(x\_1,y\_1...x\_k,y\_k) = \forall x\_1~\forall x\_2...\forall x\_k~\exists y\_1...\exists y\_k:\varphi(x\_1,y\_1...x\_k,y\_k)$

---

It seems that we can change order of quantification in first order logic. Compare following sentences:

1. *There exists a village such that all villagers have shovels.* Here we have two alternations ($\exists X~\forall Y~\exists Z$).
2. *Every villager has a shovel in some village.* This is logically equivalent, but has only one alternation ($\forall Y~\exists Z~\exists X$).

There are 4 another ways to move quantifiers and all of them will produce equal statements. Yet I do not have any reasons to think we can't change order of quantification in logic.

---

Ability to change order of quantification $\Leftrightarrow \mathsf{NP = PSPACE}$. This problem is open for decades and logic rules I used are not something really new. So, this is strange... like I am missing something.

# Answer
> 4 votes
$\exists x\forall y \hspace{1mm}\varphi$ is not equivalent to $\forall y \exists x \hspace{1mm} \varphi$.

Consider for example the formula "for all $x$ there exists $y$ such that $y=x^2$". When evaluated over the reals, this is true (every real number has a square). However, if you switch the quantifiers you get the statement "there exists $y$ such that for all $x$ it holds that $y=x^2$". Note that this has an entirely different meaning, since now the statement reads "there exists a real number which is the square of all real numbers", and this is obviously false.

The order of quantifiers is important, so you can't trivially reduce $kQBF$ to $(k-1)QBF$.

---
Tags: np-hard, boolean-algebra, propositional-logic
---


# Question
Title: How does it possible that $ZPP=RP\cap coRP$?
How does it possible that $ZPP=RP\cap coRP$ ?
After all, it must be that $RP\cap coRP = \emptyset$
Where Am I wrong ?

# Answer
The complexity class P is obviously contained in their intersection (since the probability to err on either side is zero), so the intersection isn't empty.

(The complement of a complexity **class** isn't the same as the complement of a specific language.)
> 2 votes

---
Tags: complexity-theory
---


title: Understanding of self-information

text:
# Question
Title: Understanding of self-information
I am trying to fully understand the meaning behind the self-information of events. While I totally understood how to calculate it, all explanations I find online lack of an explanation *why* less likely events have more self-information.

I can't figure out what consequences this has and can't put it into perspective like other concepts in computer science.

What does the self-information really mean? Can someone put it into context and why exactly less likely events have a higher self-information?

# Answer
The self-information is a measure of deviation from expectation of random variable in shannons (bits, the unit may vary when used in different context) when sampling a random variable.

Straight from definition it is reciprocal of probability of occurence for some event, so a little example would help.

Imagine that somewhere it rains only in one month every year (for some random number of days). From the event *it is a sunny day* we know almost nothing and it could be any month, so it meets the common (the most probable) outcome and we learned almost nothing, so it is not very important piece of information. But the event *it rains* gives us the exact month, so it is worth more in the sense that we have learned more, hence the higher self-information.

Some people call it a *surprisal*, which means "not the expected outcome". You need more memory to store rare event, (sorry for circular ref, but it is one of consequences, for the compression) think about the entropy encoding, it takes the most amount of bits to store the least expected events. Huffman codes and self-information.
> 3 votes

---
Tags: information-theory
---


# Question
Title: Should we assume both processes are getting same CPU clock while we solve SYNCHRONIZATION problems in uniprocessor system?
In synchronization, when one process is in a critical section & another is busy waiting, both are using CPU. But in a uni processor system, in the same clock both cant get the CPU. So there must be a scheduling algorithm for them. Should we consider these while solving synchronization problem or should we think both are doing their work on the same clock while we solve problems in synchronization?

# Answer
> 2 votes
It is very common to run processes on an operating system with a preemptive scheduler. The scheduler can switch between processes at any time: it is unpredictable when the operating system will switch from one process to another.

Unless otherwise specified, this is the model we use when discussing synchronization problems: there may be a switch between processes at any time. This means that in many cases there is no difference between the uniprocessor case and the multiprocessor case: the same execution sequences are possible in both. The operating system effectively pretends that there's one CPU per process.

The switches can even happen in the middle of a high-level instruction. For example, if you write a simple assignment in a high-level language

```
x := y;

```

this could translate to multiple machine instructions such as

```
copy top half from x to y
[possible switch]
copy bottom half from x to y

```

or

```
load x to register r1
[possible switch]
store y from register r1

```

This is why it's important to know which operations are atomic even in the uniprocessor case.

When you consider synchronization between kernel threads, and you get down to the level of machine instructions, there are things that are not possible in a uniprocessor case, because the kernel decides when a context switch is possible. But to exclude these impossible sequences, you need to know both how the machine instructions work and how the kernel works. If you don't know that then you can't exclude any interleaving of the execution.

---
Tags: operating-systems, process-scheduling, synchronization
---


# Question
Title: how to prove original intervals and canonical form of intervals have the same interval graph
According to this paper,a family of intervals is said to be canonical if the coordinates of the endpoints of the intervals are distinct integers between 1 and 2n where n is the number of intervals.

Here is the example Original intervals = {\[2,5\], \[3,11\], \[6,9\], \[7,13\], \[8,18\], \[12,16\], \[15,19\]}

Canonical form of intervals = {\[1,3\], \[2,8\], \[4,7\], \[5,10\], \[6,13\], \[9,12\], \[11,14\]}

These original intervals and canonical form of the original intervals give the same interval graph, but how can I prove that it is always the case mathematically ?

Edit: This is the method I use to create canonical intervals: I sort the intervals according to their starting points in ascending order Then, I assign the first interval's \[2,5\] starting point as 1. Then, I compare it with the following intervals to see the overlappings. Then, I arrange the intervals accordingly.

I repeat this process for all intervals.

Examples:

\[2,5\] contains only the starting point of interval 2, so

\[2,5\] becomes \[1, (start of interval 2), 3\] = \[1,3\]

\[3,11\] contains, start of interval 3, start of interval 4, end of interval 3, and start of interval 5, so

\[3,11\] becomes \[2, 3, (start of interval 3), (start of interval 4), (end of interval 3),(start of interval 5),8\] = \[2,8\]

note: interval 2 can not start here because at point 3 because it is where interval 1 ends. All start and end points should be distinct.

# Answer
> 1 votes
You haven't described how a system of intervals are converted to canonical form, but here is one way to do it. We find an order-preserving mapping (satisfies $f(x) \< f(y)$ iff $x \< y$) from the coordinates in the original system to the integers $\\{1,\ldots,2n\\}$ (we do this by sorting all of the original coordinates). We get the same interval graph since the mapping is order-preserving – that's a nice exercise.

---
Tags: graphs, proof-techniques, intervals
---


# Question
Title: find number in array divided into k parts
I was wondering what is the most efficient way to find the a number in an array with the following conditions:

> Array $A$ of size $n$ divided into even parts in the size of $k$
>
> * every element in each part is bigger than all the elements in the part before (Lets say in the left)
> * every element in each part is smaller then then every elements in the part after it (lets say on the right)

At this moment after trying couple of ways I am under the impression that the only way is $O(n)$

Is it correct?

# Answer
Choose an arbitrary representative from each part. Using binary search, you can find the two representatives which bracket the given element. You can then look for your given element in the $2k$ elements comprising the two parts that the representatives belong to. This algorithm takes time $O(\log(n/k) + k) = O(\log n + k)$, interpolating between the cases $k=1$ (sorted array, $O(\log n)$) and $k = n$ (unsorted array, $O(n)$).
> 0 votes

---
Tags: algorithms, sorting, efficiency
---


title: Optional prefix code for the naturals

text:
# Question
Title: Optional prefix code for the naturals
The naturals $\mathbb{N}$ can be encoded with a binary unary code such as

$$ \begin{align} 1&=0\_b\\ 2&=10\_b\\ 3&=110\_b\\ &... \end{align} $$ The length this the encoding grows linearly with the natural number it represents. For example the length of $110\_b$ is 3 and it also represents the number 3.

I am looking for an upper bound on the optimality of the prefix free encoding. For example, can we design a prefix coding of $\mathbb{N}$ such that the length of the encoding grows according to ~$\sqrt{n}$, instead of $n$. Is there an upper bound on the optimality that we can prove?

# Answer
I wrote a paper on this. The short answer is that there is no optimal encoding, nor even an optimal sequence of better and better encodings.

Kraft's inequality states that there is a prefix code with word lengths $k\_0,k\_1,\ldots$ if and only if $$ \sum\_{n=0}^\infty 2^{-k\_i} \leq 1. $$ This gives a positive answer to your question. Concretely, Elias gamma coding has code word length $O(\log n)$. The idea is simple: first you encode the bit-length of the integer using your method (using roughly $\log\_2 n + 1$ bits), then you encode the number itself (using another roughly $\log\_2 n$ bits), for a total of roughly $2\log\_2n + 1$ bits.
> 12 votes

---
Tags: algorithms, data-compression, encoding-scheme
---


# Question
Title: Why in simulated annealing, thermal equilibrium need to be meet for each temperature throughout the iterations?
I have read in this book, simulated annealing, on page 40-41, if temperature $t$ tend to $0$, then the stationary distribution will be distributed among optimal solutions. What i can not understand here is that, if with temperature $0$, the stationary distribution will be distributed among optimal solutions, so why we need to have initially large temperature and reduce it slowly, so that at each temperature, the algorithm reaches the thermal equilibrium? Why do not we set the temperature to $0$ at the start of the algorithm and iterating until reaching thermal equilibrium for temperature $0$.

Form physical point of view, i know that, if in the annealing process, the temperature reduced quickly, the meta-stable amorphous structures will be reached rather than the low energy crystalline lattice structure. But from theoretical point of view, i can not understand the depth of the subject.

# Answer
> 2 votes
At temperature 0, simulated annealing degenerates into local search (also known as hill climbing). The problem with local search is that it gets stuck at local optima. Simulated annealing is a way to overcome this difficulty by letting the algorithm sometimes make moves that temporarily deteriorate the value of the current solution.

---
Tags: optimization, markov-chains
---


# Question
Title: Compress 32 bit integer into a normalized float
and sorry if this is a duplicate of some sort, my poor technical vocabulary doesn't get me very far with google.

I am trying to implement some well-known PRNG algorithms. For the time, the algorithm in themselves do their job very well (generating 16/32/64/128 random bits). I am now trying to create a uniform distribution function, that, taking as input a 16/32/64/128 bit integer spits a IEEE compliant binary2, binary4 or binary8 (the function doesn't have to handle all of them at once, but by able to somewhat template for the other floating point types.

As quoted in the title of the question, the output shall be between -1.0 and 1.0 . A naive implementaion would be to take a byte of the integers, and affect it to the exponent, while leaving the rest to the mantissa (padding with 0s if there's not enough bits), but how to handle denormals (the code is performance critical, and the target is reluctant with un-uniform data-based condition). How to handle these then ?.

And while that may be asking two questions at once, how to do the same for a normal distribution ?

Any help or guidance is appreciated. Thanks in advance

# Answer
You can avoid getting denormals by truncating the number of random bits to ensure that there are none; even if you don't do that, the probability of getting a denormal is extremely small.

The standard way to convert uniform random variables to Gaussians is the Box–Muller transform.
> 2 votes

---
Tags: integers, floating-point
---