title: Optimal generalized bisection method

text:
# Question
Title: Optimal generalized bisection method
Suppose I'm looking for a some unknown number $x$ in the interval $\[a,b\]$ under the following assumptions:

* $x$ is unique.
* Given any $t \in \[a,b\]$ I can check, at some fixed computational cost, whether $t\>x$. Let's call this operation $C(t)$.

Let $\epsilon\>0$ be some small number. I'm interested in efficient algorithms to find an interval $I$, containing $x$, with length $\<\epsilon$. The bisection method begins by using $C((a+b)/2), $ halving $\[a,b\]$, and repeating the process over $\log\_2 \left((b-a)/\epsilon \right)$ times. I was wondering if there are more efficient modifications to it, such as breaking the interval into 3 or 4 subintervals at each iteration. Any other efficient alternative is also welcome. Thank you!

P.S. One can assume that $x$ is distributed uniformly in $\[a,b\]$, and that this process needs to be done many times for different $x$s.

# Answer
Take any policy that you like. It will consist in a number of calls to $C$ during which you will reduce the size of the incertainty of the location of $x$.

Whatever rule you use, you can't beat dichotomy, because if you split in unequal subintervals, you can always end-up in the longest, which is longer than the half.

This also holds in the average sense. Assume a split in relative sizes $\alpha$ and $1-\alpha$, which will be performed with these probabilities. The expectation of the relative length after a division is $\alpha^2+(1-\alpha)^2\ge1/2$. The minimum is reached for $\alpha=1/2$.

---

You might only improve on this result when $x$ is not uniformly distributed and you have some information about this distribution, such as the histogram of frequencies. (In such a case, the optimal rule is probably to split in equiprobable subintervals.)
> 2 votes

# Answer
No. You can't do better than binary search. Without knowing $x$, there are at least $(b-a)/\epsilon$ possible answers. This means it will take at least $\log\_2((b-a)/\epsilon)$ bits to encode the answer, on average. Each time you invoke the "check whether $t\>x$" operation, you learn one bit of information about the answer. Therefore you need to invoke that operation at least $\log\_2((b-a)/\epsilon)$ times, on average.
> 1 votes

---
Tags: algorithms, efficiency, numerical-algorithms, binary-search
---


title: "Hash" Probing?

text:
# Question
Title: "Hash" Probing?
While there are many types of *probing* in hash tables, such as *linear probing, quadratic probing*, and more, I haven't encountered a so-called *"hash-probing"* (maybe this method which I describe below exits and I just don't know its name, and if that is the case I would love some references).

This is the concept:

When generating a hash table of size $m$, generate an assisting array of size $m$, for which every index will be given a different hash function from a universal (or almost universal) hash family.

When inserting/deleting an item from the hash table, we use probing, for which if the first index in the hash table is taken, calculate the second index to be checked using the second hash function from the array, and so on...

Each calculation will be $O(1)$ (by itself).

Now - the goal is to avoid problems such as clustering that occurs in *linear probing* which can cause the time complexity to increase when the load factor rises.

I'm pretty sure this method I suggested now is flawed, since I haven't encountered this method anywhere, but I couldn't formally point to the flaws of the method.

One idea I've come up with is that by using different hash functions we cannot guarantee that the second (nor the third, etc..) hash function for a given item $x$ will not result in the same value (i.e the same index in the hash table), but I'm not sure about this since for big hash tables (and therefore many hash functions), cannot we expect a low amount of collisions (for the same item by different functions)?

Would love some comments on the method and my last analysis (and/or references). Thanks.

---

**EDIT:**

Well, I've went on to try to implement it in order to make some tests on efficiency, but then I've noticed two extremely major flaws in this method:

1. Unsuccessful search will always be $O(m)$, since you need to go all over the hahs function in the hash-array.
2. Deletion - when we delete an item from the table, we can't "correct" the table, unless we rehash it, which will be $O(m)$ as well.

I don't think this method works, because of this two flaws, but if someone has an idea on how to avoid those (and not changing the method much, or suggesting cuckoo hashing) it will be interesting to read.

Thanks.

# Answer
Your scheme is very similar to Cuckoo Hashing. In Cuckoo Hashing you have two (or, in variations, more) independent hash functions $h,g$. To insert an item $x$ you check at location $h(x)$. If that location is occupied, you suggest to check at $g(x)$. If we were to do it that way, we would have a problem in case $g(x)$ is also occupied and would have to fall back to another scheme, e.g. linear probing, with the associated problems. In Cuckoo hashing we employ a trick. If $h(x)$ is occupied by some item $y$, we store $x$ at that location anyway and try to store $y$ its alternate location (so either $g(y)$ or $h(y)$). If those locations are occupied as well, we repeat the process of kicking out the existing item and trying to place it at its alternate location.

You might wonder whether this process doesn't lead to loops and how long insertion can take. After all the sequence of kicking out and trying alternate spots doesn't seem to have a defined bound.

And indeed, if your hashtable is too full, the insertion can fail.

Consider the graph in which table positions are vertices and there is an edge between two vertices when we need to insert an item that maps to them. Usually this graph is called the cuckoo graph. We seek a matching of edges to vertices. By Hall’s theorem it exists if and only if there is no subgraph that has more edges than vertices.

We can use the first moment method to find a bound for the appearance of such subgraphs. Hence we have to calculate their expected number. There are many graphs with more edges than vertices, too many to tackle the expectation with our limited knowledge of probability theory. Luckily we can make a clever observation. If there are no subgraphs with more edges than vertices, there can’t be subgraphs with exactly one more edge than vertices.

There are only two types of these graphs, see the figure below. Both can be characterized by three numbers. Either the length of the three paths, or the size of the two cycles and the length of the connecting path. As all of these numbers must be smaller than $n$, there can be at most a cubic number of forbidden subgraphs. If we simplify the problem a little (actually we would have to use a random graph model where we fix the number of edges to the number items. For our purposes these two models are similar enough.) and consider the graph to be a $G\_{n,p}$, a random graph on $n$ vertices where every edge is present with probability $p$, a fixed subgraph with $k$ edges is contained with probability $p^{-k}$. Hence the probability that a fixed forbidden graph appears is certainly smaller than $p^{-3}$.

As we have at most $n^3$ forbidden subgraphs, the expected number is at most $n^3p^{-3}$. This value goes to zero for $p \< 1/n$ and thus (modulo our simplified graph model) for graphs with less than $n/2$ edges. Therefore in such graphs no forbidden subgraphs occur with high probability and insertion can work in principle.

But how about our greedy algorithm, is it sufficient for inserting new elements? Let’s consider a directed version of the cuckoo graph. Every edge is directed towards the position where the element is moved to in case it gets kicked out of its current spot. Hence elements reside at the edges tails and every node has at most one outgoing edge. Inserting a new element corresponds to inserting a new edge and directing it. If both endpoints already have an outgoing edge, we select an arbitrary one and kick the element out of its position. This means we reverse the edge and check at the new position whether there is already an outgoing edge.

This process fails if we cross an edge for the third time. The first time we see it, we flip it and continue. If we see it again, there was a directed cycle somewhere further down the path, that made us return. Note that this cycle still exists, only it now has the opposite direction. If we see the edge a third time, there was also a directed cycle on the other side–the process loops forever between these cycles.

But we’ve shown that these types of subgraphs don’t appear with high probability for hash tables with an occupancy of less than 0.5. So if you keep the occupancy low, insertion is very likely to succeed.

If you use more hash-functions the maximum occupancy goes up very quickly (see for example https://arxiv.org/pdf/0910.5147.pdf)

Using similar reasoning over the random graph model I described above you can show that insertion takes constant time in expectation.
> 4 votes

---
Tags: data-structures, hash, hash-tables
---


title: How to proof a heuristic?

text:
# Question
Title: How to proof a heuristic?
I am not very familiar with "heuristic", so please correct me if anything said by me is wrong.

Per my understanding, ***Algorithm*** is an automatic steps which guarantee to give a correct solution corresponding to a specific problem (and its input domain)

***Heuristic*** is somehow a rule to guess the next step, hoping when repeating this rule a nearly-optimal solution is found.

---

Algorithm is proof-able, the complexity, the correctness, etc.

But I wonder how can one proof heuristic?

Indeed I wonder is "proof" a correct term / action correlate to heuristic, but how about say, proof the heuristic can give sub-optimal answer (like at most 10% worst than the optimal) for 90% out of all possible input?

# Answer
> 2 votes
According to Wikipedia:

> A heuristic technique (...) is any approach to problem solving, learning, or discovery that employs a practical method not guaranteed to be optimal or perfect, but sufficient for the immediate goals.

Thus you can employ a heuristic to design an algorithm. This would give suboptimal answers, however you can still state theorems that relate to the correctness of such algorithm:

> For any $\epsilon\>0$, the algorithm approximates the problem $P$ with a multiplicative factor $1+\epsilon$ in time $O(T(\epsilon))$.

which means that for every input, if the expected answer of $P$ is $y$ and your algorithm returns $y'$, then:

$$y\le y'\le (1+\epsilon)y$$

You can also bound the error with an additive factor for instance.

* For decision problems, if you fix a probability distribution on the input, you may state that your algorithm returns a correct answer with a probability of 90%. That would be a correctness result.

---

In any case you should keep in mind that a *heuristic* usually denotes general ideas applicable in many situations, which is said to work well empirically and for which you don't try to prove error bounds (such as in simulated annealing).

---
Tags: algorithms, terminology, heuristics
---


# Question
Title: Given DAG G(V,E), and weight on the vertices, find the heaviest path that starts from s
**Given:** G(V,E) DAG, vertex s, and function w: V -\> R. **(the weight on the vertices)**

**Define:** We define a weighted path in G as sum of all the **vertices weight**.

**Question:** Find the heaviest path in G that starts from s. in linear time.

Well, first of all we notice it's DAG, so we can use topological sort here. and also.

My thoughts so far: for each vertex v in G, w(u,v) = w(v). Then my friend told me to multiply by minus one and check for w(p1) \< w(p2) before the multiplication iff w(p1) \> w(p2). But I'm not sure why it needs to be added.

Then we came up with proceeding with topological sort, relaxing all the edges that are outgoing from the nodes (according to the sort - meaning we start from the heaviest, and we continue with the heaviest edges..)

Time complexity linear.. O(E+V).

**My question:** If my algorithm is correct, **how can I prove it? Is there another algorithm you can think of to solve this question in linear time?**

# Answer
Try to transform the graph as following. Assign weight 0 to each edge and then "split" each vertex into two vertices by connecting them by an edge with the weight equal to the vertex's weight.

```
  ====>(12)====>   turns into  =====>(v)--12-->(u)====>

```

The find the longest path in $O(|V| + |E|)$. Please look here.
> 2 votes

# Answer
Actually you can solve it using Djkastra's algorithm in linear time if weights are not negative.

This algo finds the minimum distance from one to all nodes, so if you want to find the maximum distance you need to consider negative of the weight of edges.

That is why your friend was telling to check for -ve(weight).

Link https://stackoverflow.com/questions/8027180/dijkstra-for-longest-path-in-a-dag
> 0 votes

---
Tags: algorithms
---


title: The last failure link in KMP automaton

text:
# Question
Title: The last failure link in KMP automaton
I know that in order to build i's failure link, I compare i's and j's success links:
If they are the same (if a = b), then i's failure link should point to state j + 1.
If they aren't the same, we go to the state pointed by j's failure link and do the same. (we stop when we fail at the initial state)
How do you compute the last state's "failure" link? For example if the pattern is "ABA":

How do we compute that after we found a match, we should go to state 1? State 3 doesn't have a character it's expecting to see, so how do we do it?

# Answer
The link for position $i$ is not determined by the letter at position $i$ but instead by the letter $b$ at position $i-1$ (and the failure link at $i-1$).

For the rest you correctly describe the algorithm: follow the failure links until we find a position $j$ such that the letter at that position equals $b$.

Usually the failure link at the last letter is not computed. The reason is that one does not need it: when we have reached the last position we have found the pattern! However, if we want to find the next match, a failure link at the end would be helpful.
> 2 votes

---
Tags: strings, string-matching
---


# Question
Title: What will be the Turing machine to show that the function $T(n) = n$ is time constructible?
Specifically, we need a Turing machine that on input $1^n$ outputs binary representation of $n$ on output tape in $O(n)$ time. I am not able to get any thing better than trivial $O(n \log n)$ time. Any hints or solution?

# Answer
You almost certainly have the right machine: just implement a binary counter and increment it once for each character of the input.

What you need is a more sophisticated analysis of the running time. You've presumably reasoned that the counter will end up with $\log n$ bits, you need to increment it $n$ times and each increment could change all the bits, so there are $O(n\log n)$ operations. This is completely correct but you can do better.

Suppose the current value of the counter is even. How many bits do you have to change to increment the counter? How often do you need to change more than two bits? How often do you have to change all $\log n$ bits to increment the counter?
> 1 votes

---
Tags: complexity-theory
---


# Question
Title: Does an RL agent need to experience a complete episode in order to learn?
Suppose we have a game where there is no good measure of how "far" the target is (that we could use to nudge the agent towards the goal via the immediate returns).

If the agent gets only -1 reward per time step and experiencing a full episode where it reaches the goal is extremely improbable (it's equivalent to just blind search at this point), can it still learn?

# Answer
> 2 votes
If the agent gets no feedback whatsoever and has no information about the structure of the search space (just blind search, hoping to get lucky), then no, it can't learn. It has nothing to learn from. In your scenario, it has no information to enable it to improve: the feedback is always the same -- always an unending stream of -1,-1,-1,-1,-1,... unless it happens to get lucky. Without feedback, there's no basis for learning.

---
Tags: machine-learning, reinforcement-learning
---


# Question
Title: Is there a difference between perfect, full and complete tree?
Is there a difference between perfect, full and complete tree? Or are these the same words to describe the same situation?

# Answer
> 33 votes
Yes, there is a difference between the three terms and the difference can be explained as:

**Full Binary Tree:** A Binary Tree is full if every node has 0 or 2 children. Following are examples of a full binary tree.

```
         18
       /    \
     15      20
    /  \
   40   50
  /  \
 30  50

```

**Complete Binary Tree:** A Binary Tree is complete Binary Tree if all levels are completely filled except possibly the last level and the last level has all keys as left as possible.

```
            18
       /         \
     15           30
    /  \         /  \
  40    50     100   40
 /  \   /
8   7  9

```

**Perfect Binary Tree:** A Binary tree is Perfect Binary Tree in which all internal nodes have two children and all leaves are at same level.

```
           18
       /       \
     15         30
    /  \        /  \
  40    50    100   40

```

# Answer
> 4 votes
These words don't have a standard definition. A full binary tree could be one in which every node has either none or two children. A complete binary tree of height $h$ could be one in which all nodes up to level $h$ have two children. I have never heard of the adjective *perfect* used to describe trees.

That said, a complete binary tree of height $h$ usually means what I wrote above.

# Answer
> 1 votes
A complete binary tree is on in which every level excepts possible the last level is completely filled and every node are as far left as possible but for a full binary tree every level has the maximum number of nodes in it

# Answer
> 0 votes
A full binary tree has all it's nodes with either none or two children. A complete binary tree of height h could be one in which all nodes up to level h have two children. A perfect binary tree is a tree which is both full and complete.

---
Tags: graphs, terminology, trees
---


# Question
Title: Optimal covering of 2D matrix elements given spatial constraints
I have a particular problem I need to solve, but I'm not sure how to classify the problem or pick the right algorithm to solve it. I'm hoping someone here can lead me in the right direction.

I've generalized and reduced the problem to this:

Given an $M \times N$ matrix with elements in $\\{0, 1\\}$, cover all the $1$ elements according to the following rules:

* "Marking" an element covers that element as well as the elements directly above and below
* A maximum of $\frac{N}{2}$ elements can be marked in any row of the matrix

while minimizing the number of $1$ elements that are covered by an adjacent element but not marked itself.

For example,

Let $M = N = 4$ and consider the following matrix:

$$ \begin{bmatrix} 1 & 0 & 1 & 1\\ 0 & 1 & 1 & 0\\ 1 & 1 & 1 & 1\\ 0 & 0 & 0 & 1 \end{bmatrix} $$

Because $N = 4$, only 2 or less elements may be marked per row.

An optimal solution is as follows, where marked elements are shown in red, and elements that are covered but not marked are shown in blue.

$$ \begin{bmatrix} \color{red}{1} & 0 & \color{blue}{1} & \color{red}{1}\\ 0 & \color{red}{1} & \color{red}{1} & 0\\ \color{red}{1} & \color{red}{1} & \color{blue}{1} & \color{blue}{1}\\ 0 & 0 & 0 & \color{red}{1} \end{bmatrix} $$

In this solution, there are three $1$ elements that are covered but not marked (in blue).

For this problem, I need an actual assignment of the marks for each row, not just the final minimum cost.

---

The spatial relationship between neighboring elements initially led me to think about the problem in terms of a graph, so I tried setting it up as a minimum-cost maximum-flow problem, but I couldn't figure out how to model the flow graph.

Then I started looking into set-covering and ILP, but I'm not sure how to specify the rule about the relationship between vertical neighbors as a constraint.

# Answer
> 1 votes
Yes, this can be expressed as an instance of integer linear programming and then solved with an ILP solver. I don't know if there's a better way (for instance, I don't know if the problem is NP-complete).

We'll define zero-or-one variables $x\_{i,j}$ and $y\_{i,j}$, with the intention that $x\_{i,j}=1$ means that cell $(i,j)$ of the matrix is marked and $y\_{i,j}=1$ means that cell $(i,j)$ is covered. Let $A$ denote the matrix. Then we have constraints to ensure that all 1's in the matrix are covered: $y\_{i,j} \ge 1$ for all $i,j$ such that $A\_{i,j} = 1$. Also, we have constraints to ensure that the $x$'s and $y$'s are related appropriately:

$$y\_{i,j} \ge x\_{i,j} \qquad y\_{i,j} \ge x\_{i-1,j} \qquad y\_{i,j} \ge x\_{i+1,j}$$

$$y\_{i,j} \le x\_{i-1,j} + x\_{i,j} + x\_{i+1,j}$$

To impose the requirement that at most $N/2$ cells are marked in each row, add the constraints

$$\sum\_j x\_{i,j} \le N/2.$$

Finally, notice that $y\_{i,j}-x\_{i,j}$ is $1$ if cell $(i,j)$ is covered but not marked, and $0$ otherwise. Therefore, the objective function is:

$$\sum\_{i,j} y\_{i,j}-x\_{i,j}$$

Now feed this to an ILP solver, and let it do what it can to try to solve it.

---
Tags: algorithms, optimization, network-flow, set-cover
---


# Question
Title: Heights series in the DFS traversal of a binary tree
Assume a binary tree of height N. All nodes have exactly 2 children and all leaves have height N. For example, the following tree has N=3:

```
             3
           /   \
         /       \
       /           \
      2             2
    /  \          /  \
   /    \        /    \
  1      1      1      1
 / \    / \    / \    / \
0   0  0   0  0   0  0   0

```

When we do a depth-first traversal and note the height of each node, we get the following array (for any N\>3):

```
[0, 0, 1, 0, 0, 1, 2, 0, 0, 1, 0, 0, 1, 2, 3, 0, 0, 1, ...]

```

Note how the head of the array isn't dependent on N and can go infinitely.

I'm looking for a function F that, for any index in that array, would give the corresponding value. For example:

```
F(2) = 1
F(4) = 0
F(6) = 2

```

If possible, the function shouldn't be recursive. I do no want to have to iterate through millions of elements to calculate a height at an index far in.

# Answer
> 2 votes
In each node, store the number of nodes that are in its subtree. This can be maintained efficiently during tree manipulation operations.

Then, you can find the $k$-th node of a DFS-traversal in time corresponding to its level: recurse left if the left subtree contains more than $k$ elements, recurse right if it contains more, stop if neither applies. With a simple counter, you get the level of the node you find.

This applies to trees in general.

In your special case, you already *know* all the numbers so just don't actually have to see the tree. "Search" for $k$ in the virtual tree where each subtree has $2^{L+1} - 1$ nodes, $L$ being the level. This gives you an $O(N)$-time algorithm, discounting the exponentiation.

# Answer
> 2 votes
Follow the hint of @DDoSolitary and write the argument of your function (which is the number of the node you are interested in, counting in postorder) in binary. On my notepad it seemed easier to start with node number 1 (rather than 0) but it is easy to compensate that.

```
               1111
              /   \
            /       \
          /           \
        /               \
     111                1110
    /   \              /    \
   /     \            /      \
  11      110        1010     1101
 / \      / \       /  \      / \
1   10  100  101  1000 1001 1011 1100

```

If the binary number consists of $k$ ones then the result is $k-1$. Otherwise, you will have to move from the right branch of the tree to the left branch by substracting an appropriate number, and recurse. E.g., you move from `1101` to `110` and from there to `11` which gives result $1$.

Perhaps you want to figure that out yourself.

ps. https://oeis.org/A215020

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


# Question
Title: Solving a T(n) recursion without Master Theorem
i have a problem solving the recursion $T(n) = T(n-20)+log(n)$, because the Master Theorem is not applicable in this case.

This is my attempt:
$T(1) = 1$(given)
$T(n) = T(n-20)+log(n)$
$T(n) = T(n-20-20)+log(n-20)+log(n) $
...
...
$T(n) = T(n-k)+log(n-(k-20))+....+log(n)$

Let be $ k = n-1$
$T(n) = T(n-(n-1)) +log(n-(n-1-20)+...+log(n)$
$T(n) = T(1)+log(21)+....+log(n)$

Which results in:
$ 1+ \sum\_{n=1}^{\frac{n}{20}} ???$(i dont know if this is correct)

I am searching for a final result, which should be $\Theta(nlog(n))$

# Answer
Start with $$T(1)= 1$$ $$T(21)= T(1)+\log(21)$$ $$T(41)= T(21)+\log(41)$$ $$\dots$$ $$T(20k+1)= T(19k+1)+\log(20k+1)$$ Then move $T(i)$s from the right side to the left side $$T(1)= 1$$ $$T(21) - T(1) = \log(21)$$ $$T(41) - T(21) = \log(41)$$ $$\dots$$ $$T(19k+1) - T(18k+1) = \log(19k+1)$$ $$T(20k+1) - T(19k+1) = \log(20k+1)$$ And sum the left and right sides

$$T(20k+1) = 1 + \log(21) + \dots + \log(20k+1) \leq 1 + \sum\_{i=1}^{k}{\log(21i)} = $$ $$1 + \sum\_{i=1}^{k}{\[\log(21)+\log(i)\]} \leq 1+ \sum\_{i=1}^{k}{\log(21)}+ \sum\_{i=1}^{k}{\log(k)} = $$ $$1 + k\log(21) + k\log(k)$$ which is $O(n\log{n})$. This was only upper bound.

**More general case**

There is nothing special with the integers 1 and 20. You could take any positive integers instead of 1 and 20 and solve the relation

$$T(b) = c$$ $$T(n)= T(n-s) + \log{n}$$ as $$T(b) = c$$ $$T(s+b) = T(b) + \log{(s+b)}$$ $$T(2s+b) = T(s+b) + \log{(2s+b)}$$ $$\dots$$ $$T((n-1)s+b) = T((n-2)s+b) + \log{((n-1)s+b)}$$ $$T(ns+b) = T((n-1)s+b) + \log{(ns+b)}$$ which gives $$T(ns+b) = c + \log{(s+b)}+\log{(2s+b)}+\dots + \log{(ns+b)}$$

**Is $n\log{n}$ a lower bound for this relation?**

UPDATE: Omar's post attempts to establish a lower bound.
> 3 votes

# Answer
I would have guessed that $T(n)$ is in $\Theta(n \log n)$, so below is an attempt to lower bound the recurrence. Corrections (major as well as minor) and comments are very welcome.

For simplicity, I assume $ n = 20k + 1 $, as in fade2black's answer, with $ k = \frac{n-1}{20} $.

Thus,

$$ T(n) \geq \sum^{k-1}\_{i=0}\log(n-20i) \geq \sum^{k/2}\_{i=0}\log(n-20i) = $$

$$ \log(n) + \log(n - 20) + \log(n - 40) + ... + \log(n - 20(k/2)) $$

But,

$$ n - 20(k/2) = n - 20(\frac{n-1}{20})/2 = n - \frac{n-1}{2} \geq n/2 $$

Hence,

$$ \sum^{k/2}\_{i=0}\log(n-20i) \geq \frac{k}{2} \times \log(n/2) \geq \frac{n-1}{40} \times \log(n/2) \in \Omega(n \log n) $$

So, it seems like the $ n \log n $ bound is tight after all.
> 2 votes

---
Tags: asymptotics, recurrence-relation
---


# Question
Title: Given a binary min-heap, getting a sorted array of the $\log n$ smallest elements
Let's say we have a binary min-heap of size $n$, and we want to get an array of the smallest $\log n$ values in the heap, sorted. What is the best complexity that we can get and how do we implement it?

The simplest solution would be using $\text{Get-Min, Delete-Min}$, $\log n$ times, and that would be of time complexity of $O(\log ^2 n)$.

I've been told that this problem can be solved in time complexity of $O(\log n \log \log n)$, but I couldn't figure out an algorithm that reaches that time complexity.

# Answer
> 2 votes
Consider another min-priority queue $q$. The result will be in array $a$.

* Push the top of the heap into $q$.
* For $i$ from $1$ to $\log n$:

+ Set $a\_i = \text{pop}(q)$.
    + Push the two sons of $a\_i$ in the heap into $q$.

$q$ may be implemented with a min-heap of size $O(\log n)$, so the overall complexity is $O(\log n \log \log n)$.

---
Tags: time-complexity, heaps, selection-problem
---


# Question
Title: Are counting problems the same as problems involving listing all possible combinations?
I recently tried coming up with an algorithm that uses dynamic programming for the counting variant of the change problem. Given a set of target and a set of denominations, print the number of possible combinations that add up to the target. So if my target is 5 and my set is `{ 1, 2, 5, 10 }` then the solution is 4. More information can be found on: http://www.wcipeg.com/wiki/Change\_problem

Although the solution to this particular problem is a single number, I instead decided to list all possible combinations. My reasoning was that if I list all combinations then it'll be easier for me to work out whether or not my algorithm is working. I assumed that these two problems are identical other than the obvious difference that the form of the output is different. But I really struggled with coming up with a dynamic programming solution for listing all combinations (recursive algorithm wasn't an issue). Since then I've been trying to find such an algorithm online but I'm surprised that it doesn't seem to exist. So I'm wondering if my assumption is incorrect and these are actually two separate problems.

I'm aware that when solving problems like this I should focus on just what's required to make things a little easier, but I didn't think it'd result in two completely separate problems. So there are actually THREE variants of change problem:

* optimisation problem where I work out the smallest number of coins required to meet my target (the same algorithm can be used for both working out the minimum number of coins required AND also the actual minimum set of coins)
* counting problem which lists number of possible combinations (can be solved using dynamic programming AND recursion)
* listing set of possible combinations (can only be solved using recursion)

Is this correct? Are these separate problems?

---

Edit: I should mention that I did come up with this algorithm that uses dynamic programming but I think it only works for certain sets of denominations hence why I said that I failed to come up with an algorithm.

```
int main()
{
    std::unordered_map<int, std::vector<std::pair<std::vector<int>, int>>> m;
    m[1].push_back({ { 1 }, 1 });

    const int target = 25;
    const std::vector<int> coins = { 200, 100, 50, 20, 10, 5, 2, 1 };

    for (int i = 2; i <= target; i++) // N
    {
        std::unordered_set<int> s;

        for (auto coin : coins) // M
        {
            if (coin > i) continue;
            if (coin == 1)
            {
                m[i].push_back({ { i }, 1 });
                s.insert(1); // constant
            }

            for (auto v : m[i - coin]) // N
            {
                if (s.find(v.second + 1) != s.end()) continue; // constant
                std::vector<int> temp_v = v.first;
                temp_v.push_back(coin); // constant
                m[i].push_back({ temp_v, v.second + 1 }); // constant
                s.insert(v.second + 1); // constant
                std::cout << i << ": ";
                PRINT_ELEMENTS(temp_v);
            }
        }
    }

    return 0;
}

```

The *trick* I'm using is that for a given target, each combination has a unique number of elements. E.g. for target 5 the combinations are `{5}, {2, 2, 1}, {2, 1, 1, 1}, and {1, 1, 1, 1, 1}` and as you can see the cardinality of each set is unique. This won't work if, let's say, the denominations were `{1, 2, 3, 5, 6}` and the target was 8. In that case I can store use arrays/vectors to represent combinations and store them in a set but I'd have to sort each vector first (so that they can be easily compared) and that increases the complexity of my solution quite a bit I think.

# Answer
> 2 votes
First of all note it is an NP complete problem if you are searching for a specific subset of denominations that sums to a particular integer.

You could solve this problem by brute-force simply generating all subsets of coins checking each time that the set adds up to the target. Time complexity of this algorithm is terrible, though there are pseudo-polynomial solutions too.

A counting problem which lists the number possible outputs doesn't have to be solved using recursive algorithm though a recursive algorithm in particular for generating subsets is much more shorter, intuitive, and readable.

Any recursive algorithm may be rewritten in a nonrecursive form. Similarly, there is nothing special with dynamic programming, it is just a way to solve a problem. But not all counting problems (or any problem) are solved or have to be solved using DP.

Also, once you generated a list of sequences or sets then of course you could count, in other words your listing solves corresponding counting problem. However, if you are interested just in the number of elements/sequences/sets then you don't have to list/generate sets. For example given $n$ you could compute that the total number of binary strings of length is $2^n$ without generating these strings. Computing $2^n$ is easier than listing all strings. Similarly, if you are interested in the number of subsets of size $m$ of a set of size $n$, then that value is $\binom{n}{m}$ which may be calculated using the Stirling's approximation. But listing all possible subsets is harder.

Thus counting problems ARE NOT always same as problems involving listing all possible combinations.

# Answer
> 2 votes
Usually it is easy to adjust a dynamic programming algorithm that checks for the existence of a solution, so it outputs a solution (or all solutions).

When we only care about existence of a solution, the usual algorithm is to create an array $A\[1..n\]$, where $A\[i\]$ gets set to true if there exists a subset of coins that sums to $i$, or false if not, and $n$ is the target. We can calculate $A\[i\]$ in terms of $A\[1..i-1\]$, e.g., $A\[i\] = A\[i-c\_1\] \lor A\[i-c\_2\] \lor \cdots \lor A\[i-c\_k\]$ where $c\_1,\dots,c\_k$ are the coin denominations. Let's adjust that to output all solutions. How? We'll add an auxiliary array $B\[1..n\]$, where $B\[i\]$ contains a list of all subsets that sum to $i$ (or the empty list if none exists). Notice that we can compute $B\[i\]$ as a function of $B\[1..i-1\]$, namely,

$$B\[i\] = B\[i-c\_1\] \cup B\[i-c\_2\] \cup \cdots \cup B\[i-c\_k\].$$

Alternatively, we can think of this as a graph problem. Construct a graph with vertices $0,1,2,\dots,n$ -- one vertex for each possible sum (up to the target $n$). For each coin denomination $c\_i$ and each sum $j$, add the edge $j \to j+c\_i$ to the graph. Now the existence problem asks "does there exist a path from $0$ to $n$ in this graph?". If you want to list all solutions, the problem becomes "list all paths from $0$ to $n$ in this graph", so your problem reduces to listing all paths from one vertex to another in a dag. There are standard algorithms for that, which you can find via a web search.

# Answer
> 1 votes
The complexity of listing all the solutions is at least O (f (n)), where f (n) is the number of solutions. There are plenty of problems where f (n) can be computed in o (f (n)), which would be asymptotically faster than f (n).

As an extreme example, "count the number of permutations of the integers 1 to n" vs. "list all permutations of the integers 1 to n". The latter takes O (n!). Counting the number of solutions is nothing more than calculating n!, which can be easily done in $O (n^2 \log^2 n)$ (faster with a bit of effort).

There are even situations where you can prove the existence of exactly one solution, but the solution is hard to find. For example, if the problem is finding an RSA encrypted number, it is trivial to count the number of solutions (the number is 1), but very, very hard to find a solution.

On the other hand, there are problems where the only way to determine that a solution exists is to find it. In that case, counting and listing the solutions will take about the same time.

---
Tags: algorithms, dynamic-programming, counting
---


# Question
Title: What's the advantage of "value restriction" over its alternatives?
What is the motivation to pick "value restriction" over other candidates?

Examples of alternatives:

1. Enclosing pureness into the function type, for example:

```
pure_function : x -> x
impure_function : x => x

```
2. Polymorphism by name (call by name) as in Xavier Leroy, 1993

Xavier Leroy, 1993. Polymorphism by name for references and continuations. In *20th symposium Principles of Programming Languages*, pages 220-231. ACM Press, 1993.

# Answer
> 5 votes
I'm sure that this isn't the only advantage, but I think the primary advantage is *simplicity*. This is even identified in the original paper introducing the value restriction: previous solutions all existed, but the complexity of annotations made them undesirable.

* The majority of value that people want to give polymorphic types are functions, which are values, and you can "fake it" with thunks for anything that isn't a value.
* The language of types is unchanged, so it's easier for the programmer to use. There is no need for extra annotations or types. The users

In "real world" languages, the solutions falls into two categories. ML-style languages use the value restriction, and Haskell-style language use purity and monadic effects. Rust even uses a more restrictive version of the value restriction, where only top-level functions can be polymorphic.

As is common with PL research, there may be many theoretically sound solutions which don't gain traction in popular languages because of their difficulty or awkwardness of use.

---
Tags: type-checking, type-inference, polymorphisms
---


# Question
Title: Recursion Davis' Staircase understanding
I'm going through a hackerrank challenge on recursion https://www.hackerrank.com/challenges/ctci-recursive-staircase

and I'm having difficulty understanding how the solution below solves the problem. Here's the tree (the recursion calls) like you would with the fibonacci problem but I don't see the insight

With N = 3 the possible choices are

* 3
* 1,1,1
* 2,1
* 1,2

But I don't see these states represented in the tree, I guess I'm not following the logic which makes it hard for me to solve recursive problems

```
func f(int n){
   if (n < 0) /* base case */
    return 0;
   if (n == 0) /* base case */
    return 1;

   return f(n-1) + f(n-2) + f(n-3)
}

```

# Answer
Your base case seems to be wrong. Suppose we want to climb $n$ stairs, we want to compute $F(n)$. There are three possibilities which can be defined recursively:
1) First cover 1 stair, then there are $F(n-1)$ ways to continue.
2) First cover 2 stairs, then there are $F(n-2)$ ways to continue.
3) First cover 3 stairs, then there are $F(n-3)$ ways to continue.

So we need to add these three options $$F(n) = F(n-1) + F(n-2) + F(n-3)$$ where base case is

$$F(1) = 1, F(2)=2, F(3) = 4$$

**UPDATE** (on Charles, and quicksort comments):

**How to derive base cases**

$F(1)$ means we have only one stair and thus there is only one way to climb it. So, $F(1)=1$.

For $F(2)$ we have two stairs and there are only two ways to climb it: First stair, and then the second, or directly jump on the second stair. So, $F(2) = 2$.

Similarly for $F(3)$. We may move to the first stair, then to the second, and then to the third one. We may also jump to the second and then to the third, or alternatively step on the first and then jump to the third. And finally we could directly jump to the third stair. In total, four possibilities, $F(3) = 4$.

The following is the pseudocode:

```
 Count(N)
   if N == 1 return 1
   if N == 2 return 2
   if N == 3 return 4
   return Count(N-1) + Count(N-2) + Count(N-3)
 end

```

As for the above tree, you don't need to "unravel" for the case $N=3$ since it is the base case which is handled in a single if-statement. However, for $N=5$ the recursion tree would look like as the following:

```
                      ( 5 )
                     /  |  \
                    /   |   \
                   /    |    \
                  /     |     \
                (4)    (3)    (2)
               / | \    |      |
              /  |  \   4      2
            (3) (2) (1)
             |   |   |
             4   2   1

```

Note that the above method of counting is **the most terrible way since you always solve the same subproblems** (overlapping subproblems) many times which leads to the exponential time. You could rewrite the algorithm which solves iteratively without using recursion as following

```
Count(n)
  if n == 1 return 1
  if n == 2 return 2
  if n == 3 return 4

  x1 = 1
  x2 = 2
  x3 = 4
  i = 4

  while i <= n
    sum = x1 + x2 + x3
    x1 = x2
    x2 = x3
    x3 = sum
    i+=1
  end

  return sum
end

```

Finally (as quicksort noted in his/her comment), you could solve the above recurrence relation and find the closed form formula which gives you $O(1)$ solution (without need to compute the entire sequence up to $N$).
> 5 votes

---
Tags: recursion
---


# Question
Title: Connected Components - Linear Decision Trees
What does connected components mean in the context of non-graphs? Graphs have vertices and the vertices are connected by edges. Hence, you can build a spanning tree (for example) by systematically joining connected components (where connected components refer to connected subgraphs).

Previous discussion on this topic reveals that each connected component of a linear decision tree on some function F represents a particular region bounded by a set of half-planes and hyperplanes. For linear decision trees applied to the element uniqueness problem, we have 2 possible type of connected components (correct me if I'm wrong) - YES and NO components.

Apparently there is only 1 NO component, and at least n! YES components when for linear decision trees applied to the element uniqueness problem on a set of "n" distinct items. I can understand the number of YES components (simply permute all items), but I'm not sure why there's only 1 NO component.

# Answer
Connected components are a concept of topology. Under the usual topology on $\mathbb{R}^n$, we say that two points $x,y \in S$ belong to the same connected component if there is a path from $x$ to $y$ which is entirely in $S$ (this is known as *path-connectedness*). This defines an equivalence relation on $S$, and a connected component of $S$ is an equivalence class of this relation. This generalizes the graphical definition which is more familiar to this audience.
> 2 votes

---
Tags: algorithms, connected, decision-tree
---


# Question
Title: What is the loop invariant of the following function?
```
x = n; y = 0

while x >= b:

   x = x DIV b

   y = y + 1

return y

```

This function takes in $n,b\in\mathbb{N}, n \> 0, b \> 1$, and returns $k\in\mathbb{N}$ such that $b^k\leq n \lt b^{k+1}$

So far I think it is:

$b^y \leq n$

$x \leq n$

but now I'm stuck

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

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

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

---
Tags: loop-invariants, program-correctness
---


# Question
Title: Efficient algorithm to find minimum steps to cover all the given points in infinite 2D grid?
**Problem statement:** You are in an infinite 2D grid where you can move in any of the 8 directions :

```
(x, y) to
(x+1, y),
(x-1, y),
(x,   y+1),
(x,   y-1),
(x-1, y-1),
(x+1, y+1),
(x-1, y+1),
(x+1, y-1)

```

You are given a sequence of points. Give the minimum number of steps in which you can cover all of them. You start from the first point.
Example:

```
Input : [(0, 0), (1, 1), (1, 2)]
Output : 2

```

**My approach:**

1. For each pair $0\le i\le N-1$ in the list find its subtraction with $\forall{j}$ except $i\neq{j}$.
2. Sort the list of resultant subtractions.
3. Selection of each pair in the list corresponds to the subtraction in increasing order & keep counting $\max(x\_{2}-x\_{1},y\_{2}-y\_{1})$ till the end.

Now,

* If it is correct it's complexity is $\Theta(n^{2}\log n)$ because of subtraction between $\frac{n(n-1)}{2}$ pairs + sorting in $n^{2}\log n$. Is there any better efficient algorithm? (Updated from Prateek's answer)

# Answer
Actually I did not get exactly what you are trying to do in Step 1 but complexity of this algorithm should be $O(n^{2} log(n))$ because you will get $(n\*(n-1)/2)-c$ elements i.e $O(n^{2})$ elements and then to sort them you will get $O(n' log(n'))$ complexity where $n'=O(n^{2})$.

Their is a full proof solution for this problem and it also has complexity of $O(n^2 log(n))$.

```
Step 1. Lets assume all co-ordinates are nodes from 1,2.....N.First find
 distance b/w all the vertices in O(n^2).
Step 3. Find minimum spanning tree which can be formed using Prim's
 algorithm or Kruskal's algorithm whose complexity is O(E log(E))
 where 'E' is the number of edges and in our case E=n^2.

```

Hope that helps.
> 0 votes

# Answer
**UPDATE:** after additional clarification it turned out that OP meant "set of points" instead of "sequence of points", and so the problem is reduced to TSP. Ignore the following solution which assumes "sequence of points".

The first approach is that you **could** solve using Floyd-Warshall algorithm in $O(|V|^3)$ time.
1) Convert the grid into a weighted graph where $w(v\_i,v\_j) = 1$ for each neighbouring pair of points $(p\_i,p\_j)$ on the grid. I assume that every move in any of the eight directions from a point takes 1 step (but you may use a different metric).
2) Compute shortest paths for each pairs of vertices (points on the grid) $(v\_i,v\_j)$, by storing them in the matrix $M$, where $M\[i\]\[j\]$ means the shortest path from point $p\_i$ to the point $p\_j$, using Floyd-Warshall algorithm.
3) Then for the given sequence of points $\[p\_1(x\_1,y\_1),\dots, p\_k(x\_k, y\_k)\]$, compute the sum $M\[p\_1\]\[p\_2\] + M\[p\_2\]\[p\_3\] + \dots + M\[p\_{n-1}\]\[p\_n\]$ (The shortest path from $p\_1$ to $p\_2$ plus the shortest to $p\_3$ plus $\dots$).

You could take a different approach (a greedy algorithm). Given a sequence of points $\[p\_1(x\_1,y\_1),\dots, p\_k(x\_k, y\_k)\]$, you first compute the shortest path from $p\_1$ to $p\_2$ (using Fredman-Tarjan algorithm, using Fibonacci heaps) in $O(E + V\log{V})$ time, then from $p\_2$ to $p\_3$, and so until the last point. So, its complexity is $O(K(E + V\log{V}))$, where $K$ is the number of points $p\_i$. To improve further observe that each vertex has at most eight neighbours and so the graph has at most $8V/2 = 4V$ edges, and hence the time complexity is $O(K(4V + V\log{V}))$ which is $O(KV\log{V}))$.

Yet another approach to improve the greedy algorithm is using BFS for finding the shortest path from one point to another one since your graph has edges only of weight 1 (may be considered as unweighted). BFS works in $O(V+E)$ time or $O(V)$ since your vertices have constant number of neighbours (eight at most). So the running time may be reduced to $O(KV)$.

And finally, you may compute the shortest path from one point $p\_i$ to another $p\_j$ in $O(1)$ by $\max(|x\_i-x\_j|, |y\_i-y\_j|)$ given coordinates $(x\_i, y\_i)$ and $(x\_j,y\_j)$ and reduce the algorithm to $O(K)$ time.
> 0 votes

---
Tags: algorithms, optimization, square-grid
---


# Question
Title: Turn words array from a document with their coordinates into sentences
I have an array of words with their coordinates in the document, I want to turn them into sentences. For example this:

```
  [
    {
        "bounds": [
          {
            "x": 10,
            "y": 10
          },
          {
            "x": 15,
            "y": 10
          },
          {
            "x": 15,
            "y": 15
          },
          {
            "x": 10,
            "y": 15
          }
        ],
        "desc": "Hey"
      },
    {
        "bounds": [
          {
            "x": 18,
            "y": 10
          },
          {
            "x": 24,
            "y": 10
          },
          {
            "x": 24,
            "y": 15
          },
          {
            "x": 18,
            "y": 15
          }
        ],
        "desc": "Name"
      },
          {
        "bounds": [
          {
            "x": 18,
            "y": 20
          },
          {
            "x": 24,
            "y": 20
          },
          {
            "x": 24,
            "y": 25
          },
          {
            "x": 18,
            "y": 25
          }
        ],
        "desc": "What"
      },
    {
        "bounds": [
          {
            "x": 18,
            "y": 20
          },
          {
            "x": 24,
            "y": 20
          },
          {
            "x": 24,
            "y": 25
          },
          {
            "x": 18,
            "y": 25
          }
        ],
        "desc": "Sup"
      }
]

```

Should Have turned into this:

```
Hey Name
What Sup

```
* The coordinates are not accurate just an example, also the algorithm needs to deal with words that are in the middle of sentences and other extreme cases.

What it the best way I can do it (Ideally implemented with JavaScript)?

# Answer
On this site, we only care about algorithm itself and not javascript. From what I gathered, your problem statement (without the javascript part) is:

> Given a set of rectangles in described in Cartesian coordinate, (1) partition the set into "lines" (2) sort rectangles within each "line" by their position along the "line"

The reason I put the word "line" in quotation is because there are many ways to define it, and you didn't give enough information to decide which one.

Let's formulate this a bit: we are given

* set $S$ of rectangles
* four functions $t,b,l,r \colon S \rightarrow \mathbb{N}$ standing for top, bottom, left and right coordinate of the rectangle respectively.

We need to output:

* ordered partition of $S$ such that "each partition is a line"

For convenience, I'm going to let $\sim \subseteq S \times S$ denotes the **equivalence** relation that partition $S$ into lines.

Here are three separate (not exhaustive) examples of definition of a line:

1. Two rectangle is in the same line if they have the same bottom $y$ value.$$x \sim y \iff bx = by$$
2. A rectangle is in the same line with its nearest neighbour in $y$ direction that is not further than some threshold. $$y = min\_z |bx-bz| \implies (|bx-by| \leq T \implies x \sim y)$$ don't forget to make $\sim$ transitive.
3. Decide on the direction of a line first which may not be parallel to $x$ axis. Change the basis of coordinate. Then apply one of the above.

Decide on one you want according to the degree of sophistication needed to handle your input. Once you have the partition (supposed by $y$ value), you can then sort each by $x$ value.

---

Finally, there is also the alternative to do Hough Transform which is also generally applicable to bitmap images. In our case, our image is one of rectangles (or centre of rectangles, or corner of rectangles).
> 1 votes

---
Tags: algorithms, ocr
---


title: Asymptotic runtime of a nested sum

text:
# Question
Title: Asymptotic runtime of a nested sum
i have to calculate the asymptotic runtime of a nested sum:

Sum $\sum\_{n=1}^{log\_{4}(n)} \sum\_{n=1}^{\sqrt{n}}1$

My solution is $\Theta(log(n) \cdot \sqrt{n})$, which is wrong, because the solution says $\Theta(\sqrt{n})$. I dont understand where my mistake is:

Sum $\sum\_{i=1}^{log\_{4}(n)} \sum\_{j=1}^{\sqrt{n}}1 = \sum\_{i=1}^{log\_{4}(n)} \sqrt{n} = \sqrt{n} \sum\_{i=1}^{log\_{4}(n)}1 = \sqrt{n} \cdot (log(n)+1) =$ $ log(n) \cdot \sqrt{n} + \sqrt{n} \stackrel{?}{=} \Theta(log(n) \cdot \sqrt{n}) $

Maybe my formula is wrong. Here is the pseudo-code i have to analyse:

```
someFunc(n)
  i = n
  while (i >= 1)
   i=i/4;
   //we do sqrt(i) operations
   for j=1 to sqrt(i)
     do_some_atomic_op() //O(1)
   end
   //i will reduce in every step!
  end
end

```

# Answer
> 2 votes
In fact you do change the value of $n$, see $n=n/4$, and so the while-loop results in $\sum\_{i=1}^{\log\_4{n}}{\sqrt{i}}$ which is equal to $\sqrt{1} + \sqrt{2} + \dots + \sqrt{\log\_4{n}}$.

**Upper bound** $\sqrt{1} + \sqrt{2} + \dots +\sqrt{\log{n}} \leq \log{n}\sqrt{\log{n}}$ which is less than $\sqrt{n}$ for sufficiently large $n$s (you may prove it using induction or using some other techniques).

---
Tags: asymptotics, runtime-analysis
---


# Question
Title: Decide if binary encoded number is divisible by 3
Let's consider the language over $\\{0,1\\}$ containing such words $w$ that: $$w = m\_1m\_2..m\_n $$ where $m\_i$ has length $n$. (so $|w|=n^2$) and $$m\_1 + m\_2 + .. + m\_n \mod 3 = 0$$

($m\_i$ we interpret as binary encoded number).

Prove, that the language is $NC^1$ class.

---

The first problem is: How to decide whether $m\_i$ is divisible by $3$?

$m\_i = a\_na\_{n-1}...a\_0$ where $a\_i$ is a bit, so the number interpreted is: $v = a\_0 \cdot 2^0 + a\_1 \cdot 2 + .. + a\_n \cdot 2^n$.

My only observation is:

$$2^{2k+1} \mod 3 = 1 \\ 2^{2k} \mod 3 = 2$$

Please hint me.

# Answer
you have to use the fact that $2^n\mod 3 = n\mod 2 + 1$:

* 2 mod 3 = 2
* 4 mod 3 = 1
* 8 mod 3 = 2
* 16 mod 3 = 1
* 32 mod 3 = 2

and so on.

The solution then for an $n$ bit number is to use $n$ processors, the $i$th processor will calculate $f\_0(i) = i\mod 2 +1 * w\[i\]$ where w is the little-endian array of bits.

Then, each of the processors can calculate the following: $f\_{t+1}(i) \<= f\_{t}(i) + f\_{t}(i+2^t)\mod 3$, for $t \in \\{1...log\_2(n)\\}$ (increasing sequentially of course). $f\_{log\_2(n)}(0)$ will then contain the sum of the bits mod 3.
> 2 votes

# Answer
The most direct way to show that this is in $\mathsf{NC}^1$ is through a "divide and conquer" approach.

First, we show how to compute $m\bmod{3}$ in $\mathsf{NC}^1$. The idea is to write $m = 2^h m\_h + m\_\ell$, where $m\_h,m\_\ell$ have roughly the same number of bits, compute $m\_h,m\_\ell \bmod{3}$, and combine the results.

After computing $m\_i \bmod{3}$ for all $i$, we use a balanced binary tree to add (modulo 3) all these remainders. Then we can compare the result to 0. Details left to you.
> 1 votes

---
Tags: circuits
---


# Question
Title: How similar is the Goldwasser-Sipser Set Lower Bound Protocol to the Hashcash/Bitcoin Proof-of-Work?
Given a hash function $H:\\{0,1\\}^\*\rightarrow\\{0,1\\}^n$, a difficulty $d\in\mathbb{N}$, and data $D\in\\{0,1\\}^\*$, the framework of the Hashcash/Bitcoin Proof-of-Work entails finding a nonce $c$ such that $H(c\Vert D)$ starts with $d$ zero’s. That is to say, Hashcash/Bitcoin Proofs-of-Work appear to find a preimage $c\Vert D$ that partially inverts a hash $H$. Depending on $d$ and the size of the nonce, it may be impossible to find a nonce $c$ without having to change the data $D$. Currently (Aug. 2017) with Bitcoin, the target difficulty $d$ is, I think, 17 consecutive hexadecimal 0's.

Given a set $S\subseteq\\{0,1\\}^m$ and a number $K$, the Goldwasser-Sipser Set Lower Bound Protocol is an Arthur-Merlin protocol for Merlin the prover to show Arthur the verifier that $|S|\geq K$. Letting $k$ be a number such that $2^{k-2}\leq K\leq 2^{k-1}$, Arthur chooses a random hash $H$ from pairwise independent hash function collection, along with a random $y\in\\{0,1\\}^k$. Merlin’s goal is to find an $x\in S$ such that $H(x)=y$. That is to say, Merlin’s goal in the Goldwasser-Sipser Set Lower Bound Protocol is to find a preimage $x$ that inverts a hash function $H$. The larger the set $S$, the easier it may be to find a preimage. Indeed, if $S\leq \frac{K}{2}$, then Merlin has a much smaller chance of finding a preimage than if $S\geq K$. Thus, Merlin may provide evidence to Arthur that $S$ is large. This may be used, e.g., to show that two graphs are not isomorphic.

My question is: can we reinterpret the Hashcash/Bitcoin Proof-of-Work as a Set Lower Bound? In other words, can we consider finding a nonce $c$ in the Bitcoin Proof-of-Work as similar to finding a preimage $x$ in the Goldwasser-Sipser Set Lower Bound, which may show that some (arbitrary) set is large?

Or is the similarity between the two not very strong?

---

**EDIT**

Following up on D.W.'s answer, I wonder if $D$ could be considered as the input to a test of membership of $x\in S$. For example, $S$ could be the set of all permutations of two graphs $G\_1$ and $G\_2$, $D$ might "encode" the two graphs $G\_1$ and $G\_2$, and $x$ might "encode" a permutation $\pi$ of one of $G\_1$ or $G\_2$. The fact that a preimage $x$ was found might indicate that $G\_1$ is *not* isomorphic to $G\_2$, because it indicates $S$ is large.

However, I think there may be no easy way to tell what the "encoding" is. So I wonder if a Proof-of-Work can, *by design,* be based on some interesting problem in $\mathsf{coNP}$, by having the encodings of the problem specified *a-priori*.

For example, the adjacency matrix of the two graphs $G\_1$ and $G\_2$ may be encoded in $D$. The miner may engage in looking for another graph $G\_3$ that is a permutation $\pi$ of one of $G\_1$ or $G\_2$, such that the hash $H\_2$ is $0$. That is, the miner may treat $G\_3=\pi(G\_1)$ or $G\_3=\pi(G\_2)$ as $x$ (i.e. the "nonce" $c$.) The miner may "succeed" if $H(\pi(G\_1) \Vert G\_1 \Vert G\_2)$ begins with $d$ zeroes, or $H(\pi(G\_2) \Vert G\_1 \Vert G\_2)$ begins with $d$ zeroes, thus indicating that the number of permutations of $G\_1$ and $G\_2$ together is "large" and not "small."

# Answer
> 4 votes
I can see some similarity too, but only in a loose sense; there are also some significant differences.

Here's the similarity. Define $H\_2(x)$ to be the first $d$ bits of $H(x||D)$. Then you can think of the Bitcoin proof-of-work as being: find $x$ such that $H\_2(x)=0$. This is loosely similar to the Goldwasser-Sipser protocol; you could imagine that Merlin is the bitcoin miner and Arthur is the verifier, and the goal is for Merlin to prove to Arthur that Merlin has probably done at least about $2^{d-1}$ hash computations. Or, if we let $S$ denote the set of values $x$ such that Merlin has computed $H\_2(x)$, you could think of the goal being to prove that $|S|$ is at least $2^{d-1}$ or so. Now if you imagine that Arthur always chooses $y=0$ in the Goldwasser-Sipser interactive proof, we get the same kind of computation. So in that sense there is a similarity.

However, the correspondence is imperfect. The threat models for the two schemes are quite different: Goldwasser-Sipser deals with a Merlin with unbounded computational power, whereas Bitcoin assumes the miner's computational power is limited. The requirements for the hash function are quite different: Goldwasser-Sipser only needs a pairwise independent hash, whereas Bitcoin needs a cryptographically secure hash. Also the nature of the set $S$ is different: in Goldwasser-Sipser the set $S$ is well-defined and there is a method specified in advance that Merlin can use to prove that a certain value is an element of the set, whereas in my analogy $S$ is only loosely defined and we don't have a clear way to prove that an element is a member of $S$.

---
Tags: hash, graph-isomorphism, interactive-proof-systems, proof-of-work
---


title: Definition of $\alpha$-approximation

text:
# Question
Title: Definition of $\alpha$-approximation
I know this question is trivial. But I am looking for a concise formal definition of $\alpha$-approximation.

Is it correct to say that "An algorithm is an $\alpha$-approximation to problem $X$, if for any instance of problem $X$ the solution returned by this algorithm is within a factor $\alpha$ of the optimal solution"?

Any correction on the above definition is welcomed.

# Answer
There are actually two main types of approximation algorithms: those that return an approximate solution, and those that return the approximate value. In order to explain the difference, let me define the problem more formally. Below everything is stated for *minimization* problems. It is a simple exercise to generalize everything for *maximization* problems.

Let me stress that the definitions below are not standard; in fact, there is no standard agreed-upon definition. However, it can be taken as a formal definition without too many complaints from the community, if you find this kind of definition enlightening.

**Definition:** A *minimization problem* consists of a tuple $\mathcal{O},\mathcal{S},v$ such that:

* $\mathcal{O}$ is the set of instances.
* $\mathcal{S}$ is the set of solutions.
* $v$ is a function from $\mathcal{O} \times \mathcal{S}$ to $\mathbb{R}\_+ \cup \\{\infty\\}$ (the non-negative reals together with positive infinity) such that for every $o \in \mathcal{O}$ there exists $s \in \mathcal{S}$ such that $v(o,s) \< \infty$.

We define $v^\*(o) = \inf\_{s \in \mathcal{S}} v(o,s)$.

The function $v$ is the *value* of the given solution for a given instance. The *optimal value* for the instance is $v^\*(o)$. If $v(o,s) = \infty$ then we say that the solution is *infeasible* for the instance.

(Alternatively, we could have a function $f\colon \mathcal{O} \to 2^{\mathcal{S}} \setminus \\{\emptyset\\}$ giving the (non-empty) set of feasible solutions, and then $v$ is a partial function $\mathcal{O} \times \mathcal{S} \to \mathbb{R}\_+$ such that $v(o,s)$ is defined iff $s \in f(o)$.)

**Definition:** An *$\alpha$-approximation algorithm* is an algorithm $A\colon \mathcal{O} \to \mathcal{S}$ that satisfies the following property:

> For all $o \in \mathcal{O}$, $v(o,A(o)) \leq \alpha v^\*(o)$.

If $\alpha = 1$, then the algorithm finds an optimal solution.

We are usually interested in polynomial time approximation algorithms. In this case we have to fix an encoding for $\mathcal{O}$ and $\mathcal{S}$, that is, we should treat $\mathcal{O},\mathcal{S}$ not as abstract sets but rather as sets of strings.

**Definition:** A *weak $\alpha$-approximation algorithm* (non-standard terminology) is an algorithm $B\colon \mathcal{O} \to \mathbb{R}\_+$ such that:

> For all $o \in \mathcal{O}$, $v^\*(o) \leq B(o) \leq \alpha v^\*(o)$.

Once again, we are usually interested in polynomial time algorithms. Given an $\alpha$-approximation algorithm $A$, we can construct a weak $\alpha$-approximation algorithm $B$ using $B(o) = v(o,A(o))$ (this works assuming $v$ is computable). In many specific case we can also go in the other direction.

In some cases (especially hardness of approximation proofs), when the phrase "$\alpha$-approximation algorithm" has the weaker meaning given in the latter definition.
> 5 votes

---
Tags: optimization, terminology, approximation
---


# Question
Title: When would best first search be worse than breadth first search?
I am studying best first search as it compares to BFS (breadth-first search) and DFS (depth-first search), but I don't know when BFS is better than best-first search. So, my question is

> When would best-first search be worse than breadth-first search?

This question is one of the back exercises in *Artificial Intelligence* by Rich & Knight, and it asks for an answer in terms of time & space complexity and allows you to define any heuristic function.

# Answer
> 6 votes
Best first search is different from BFS and DFS by that that it uses problem specific information to chose which node of the search tree to expand next. Best first search is informed search and DFS and BFS are uninformed searches.

In order to use informed search algorithm you need to represent the knowledge of the problem as heuristic function.

Best first search is sometimes another name for Greedy Best First Search, but it may also mean class of search algorithms, that chose to expand the most promising node based on an evaluation function(not necessary the same as the heuristics) such as Greedy Best First Search, A\* and others.

If you meant Greedy Best First Search:

* it is complete (finds a solution in finite graphs) like BFS
* it is not optimal(to find the least cost solution) as DFS, but BFS is optimal when the cost of each arc is the same
* in the worst case its time and space complexity is O($b^n$), where b is the branching factor and n is the maximal depth. For BFS time and space complexity is O($b^m$), where m is the depth of the shallowest goal. **Greedy best-first search is in most cases better than BFS- it depends on the heuristic function and the structure of the problem**. If the heuristic function is not good enough it can mislead the algorithm to expand nodes that look promising, but are far from the goal. Here is one simple example

Let all arcs have the same cost, S - start node, G - goal node and h-heuristic function

Here Greedy best-first search will expand : **S,B,C,D,G**

And BFS will only expand : **S,A,B,G**

# Answer
> 1 votes
1. Breadth-first search is blind search(uninformed), it just keeps expanding all the leaves and checks if one of them is the goal.
2. Best-first search is informed search, i.e, it has some information (heuristics) about the goal.For example if the information is about the distance from the current to state to the goal state, best first will choose the state with will reduce the distance by the maximum amount.
3. Best-first search can get stuck in an infinite loop.

So, if you think the agent might stuck in an infinite loop or if you don't have any heuristics (information), then go with breadth-first search else go for best first search.

A better comparison would be between best-first and hill climbing search.

# Answer
> 0 votes
When the heuristic function, which Best first search algorithm using is not admissible or good enough, that may mislead the search. The heuristic function may lead the algorithm towards the infinite loop.

---
Tags: graphs, artificial-intelligence, search-algorithms
---


title: Closure property and undecidability

text:
# Question
Title: Closure property and undecidability
I know that if a language class is closed under operation X then the problem is decidable.

for eg: "Intersection of two CSL is CSL"? this problem is decidable because it is already proved that CSL follow intersection closure property.

But what if language is not closed under the operation. for eg: problem: Is intersection of two CFL is CFL or not?

as CFL/DCFL is not closed under intersection. then is this true saying that not following closure opertion implies Undecidable problem?

My approach:This problem is same as saying that "A given CSL is CFL or not?" because intersection of two CFL's is CSL for sure. as every CSL is RE then can we also say this problem as "A RE is CFL or not"? if my last statement is true then by using rice theorem this problem must be undecidable and even not RE.

how to approach these type of question when a language is not closed under the given operation?

# Answer
Your approach doesn't work. Try proving it to see that it doesn't work. As a silly example, the set of non-empty regular languages isn't closed under intersection, but given two non-empty regular languages, it is decidable whether their intersection is a non-empty regular language.

However, it is in fact undecidable to decide whether the intersection of two context-free languages (say given as context-free grammars) is context-free, essentially since you can encode the computation of a Turing machine as the intersection of two context-free languages. See Theorem 1 in a writeup of Hendrik Jan (a bit of work is required to get this particular result from the theorem: construct grammars for $L(G\_1) \flat \\{a^nb^n c^m\\}$ and $L(G\_2) \flat \\{a^nb^mc^m\\}$; the intersection of these context-free languages is non-context-free iff $L(G\_1) \cap L(G\_2)$ is non-empty).
> 2 votes

# Answer
I don't think closure property implies decidability. Consider r.e. languages and intersection. R.e. languages are closed under intersection, e.g., if $L\_1$ and $L\_2$ are r.e. languages then $L\_1 \cap L\_2$ is also r.e. but may be undecidable.

On the other hands, CFLs are not closed under intersection. However, a language which is intersection of two CFLs is not CF but may be decidable. For example $L\_1=\\{a^ib^ia^j |i,j \geq 1 \\}$, $L\_2=\\{a^ib^ja^j |i,j \geq 1 \\}$ are both CF, however $L\_1 \cap L\_2 = \\{ a^ib^ic^i | i,j \geq 1\\}$ is not CF, but it is still decidable.
> 2 votes

---
Tags: undecidability
---


# Question
Title: Partial intersection of 10 sorted lists of integers
Suppose I want to find the numbers that appear in at least 3 of the 10 sorted lists, is there an efficient way to do it apart from iterating over all 10 of them in parallel?

# Answer
> 2 votes
The simplest way is to first remove duplicates from the 10 lists, and then merge all of them. Any number appearing 3 times in the merged list also appears in 3 of the 10 sorted lists.

A more complicated way is using pointers as you indicate. Briefly, the pointers start at the beginning of the lists, and then you keep incrementing the pointer pointing at the minimal element. You can use a heap to implement detecting which pointer to advance.

If you have $m$ lists containing $n$ elements in total, the first way takes optimal time $O(n)$ but uses up space (or modifies the input), and the second takes time $O(n\log m)$ (the $\log m$ comes from the heap) but uses less auxiliary space.

# Answer
> 1 votes
You could consider using a hash table.

Just store each number together with three element array that holds information about which array that integer belongs to (pointer to the list for example). Every time you add an element to the hash table, check if its three element array is full, meaning that element is in at least three lists, and so add that integer to another array which holds desired elements so that not to scan the hash table again. This will take $O(n)$ time where $n$ is the total number elements.

In addition, if your integers are bounded by $K$ then you could simply use an array of size $K$ as the hash table.

# Answer
> 0 votes
There's a method I found some time ago that works if you have iterators that can "forward" to or past a given value easily, eg with a skip list, in addition to the usual "next", ie it can do the equivalent of multiple next's to reach a given value, with sublinear cost. (I'll refer to these iterators below as single values X for the purposes of which one is minimum etc. at any given time.)

If you want runs of length $k$, do replacement selection (the heap-of-iterators idea), but pipe the heap into a FIFO/ring buffer of length $k-1$. Picture this as a funnel, where the sharp end of the heap goes into a fixed-length FIFO, and we iteratively pull the minimum off the end of the FIFO and reinsert it after bumping it forward as I'll describe.

To bump the smallest element E on the FIFO, compare it with the minimal element M on the heap. If E = M, we have a run, so output E's value, move it to its next value, and put it back on the heap while moving M to the FIFO. If E \< M, *forward* it to or past M, move M to the FIFO, and put E back on the heap. Note we don't insert the bumped value into the FIFO; that's the fun part.

The FIFO in this case is an obvious way to see runs in the merged sequence, but it also allows us to forward E past runs which will never reach length $k$. The reason is that if E and M are different, then any value X between them in the FIFO can never reach $k$ repetitions, even if E and everything to the left of X comes to equal X eventually. That is, if the FIFO and M contain

$E...X,...X,..M$

it can possibly become, if E.next = X, say,

$X...X,..M$,

but never the case where all $k$ are

$X..X$

by simple counting.

So we can forward E's value past any $X$ where $E \< X \< M$ without losing any k-runs.

---
Tags: data-structures, lists
---


# Question
Title: What did Turing's mysterious small programme on the Manchester computer calculate?
I am reading Turing's "Computing machinery and intelligence" paper (https://www.csee.umbc.edu/courses/471/papers/turing.pdf) and found a fragment in which he says:

> I have set up on the Manchester computer a small programme using only 1,000 units of storage, whereby the machine supplied with one sixteen-figure number replies with another within two seconds. I would defy anyone to learn from these replies sufficient about the programme to be able to predict any replies to untried values.

It looks like a machine learning problem to me :) but putting my interest on AI aside, my question is the following:

Does anyone know **what** this program was doing?

I am *very* curious.

PS: By the length of the input and output, I suspect it was an encryption algorithm, but I would appreciate any clue to the *actual* program.

# Answer
You're right that this has to do with encryption, but it's not encryption per se. It's something called hashing. What his program does is take a number, hash it, and output the hash. What Turing created is now called a **cryptographically secure hash.**

A modern cryptographically secure hash must do the following. It should be easy to hash the input, but very difficult to 'unhash' an output to get the input. In this case, "very difficult" usually means "it would take months or years on a supercomputer, if not even longer."
> 2 votes

---
Tags: algorithms, history
---


# Question
Title: Multi-dimensional Knapsack with added one-per-group constraint
I have some sets (A, B, ...) each containing some vectors (e.g. \[1, 0, -1\]). How can I pick exactly one vector per set such that they sum to a specified target vector?

For example:

```
A: { [1, 0, -1], [3, 0, 0], ... }
B: { [0, -1, -1], [2, -1, 0], ... }

Target: [3, -1, -1]

Solutions:

1) A=[1, 0, -1], B=[2, -1, 0]
2) A=[3, 0, 0], B=[0, -1, -1]

```

I think this is a variation of the multi-dimensional knapsack problem with the added 'one-per set' constraint. Has this been written about anywhere?

For my domain, there are 30 sets each containing 50 vectors with 30 dimensions. These vectors are sparse with ~80% zeroes. There is at most one negative number per vector.

Any pointers to research papers or proposed algorithms would be hugely appreciated.

Thanks.

# Answer
One reasonable starting point is to try formulating it as an instance of integer linear programming, and apply an ILP solver. This might not be the best possible algorithm, but it is simple and easy to try.

Let $A\_{i,j}$ be the $j$th vector in the $i$th set. Define zero-or-one variables $x\_{i,j}$, with the intended meaning that $x\_{i,j}=1$ means you have picked the $j$th vector from the $i$th set. Then you have constraints of the form

$$\sum\_{i,j} A\_{i,j} x\_{i,j} = t$$

where $t$ is the target vector. (Notice that this is a sum of vectors, so it actually turns into 30 different equations, one per dimension.) Also to ensure that you pick exactly one element from each set, we have

$$\sum\_j x\_{i,j} = 1$$

for every $i$. Then send that to an ILP solver.
> 1 votes

---
Tags: algorithms, complexity-theory, knapsack-problems
---


# Question
Title: Chernoff bound when we only have a lower bound of expecation
This question: Chernoff bound when we only have upper bound of expectation is similar, but for an upper bound of expectation.

The standard Chernoff bound says that is $X$ is a sum of 0/1 random variables, then, for any $\delta \in (0,1)$,

$P(X \leq (1-\delta) E(X)) \leq e^{-\frac{\delta^2 E(X)}{2}}$.

Suppose we only have $\alpha \leq E(X)$. Is it true, and if so, how to prove, that

for any $\delta \in (0,1)$,

$P(X \leq (1- \delta) \alpha) \leq e^{-\frac{\delta^2 \alpha}{2}}$.

# Answer
> 2 votes
You can use a coupling. Let $X = X\_1,\ldots,X\_n$, and suppose that $\Pr\[X\_i=1\] = \beta\_i$ (so $\beta := \mathbb{E}\[X\] = \sum\_i \beta\_i \geq \alpha$). Let $p = \alpha/\beta$, and define $\alpha\_i = p\beta\_i$. Let $Z\_i \sim \mathrm{Bernoulli}(p)$, and define $Y\_i = X\_i Z\_i$. Notice that $X\_i \geq Y\_i$ and that $\Pr\[Y\_i=1\] = p\beta\_i = \alpha\_i$. If we define $Y := Y\_1 + \cdots + Y\_n$ then $X \geq Y$ and $\mathbb{E}\[Y\] = \sum\_i \alpha\_i = \alpha$, and so Chernoff's bound apply to $Y$, showing that $\Pr\[Y \leq (1-\delta)\alpha\] \leq e^{-\delta^2\alpha/2}$. Since $Y \leq X$, we conclude that $$ \Pr\[X \leq (1-\delta)\alpha\] \leq \Pr\[Y \leq (1-\delta)\alpha\] \leq e^{-\delta^2\alpha/2}. $$

---
Tags: probability-theory, chernoff-bounds
---


# Question
Title: Writing a Context-Free-Grammar using Backus Naur Form for a for-loop?
I'm pretty new to CFG, and I've tried out some samples as well. As of now I'm trying this `for-loop` to write it in CFG using BNF:

```
Start{
    int z = 20;
    for(int b = 0; b < 5; b++)
    {
        //some statement
    }
}

```

Attempted BNF:

```
<program> ::= Start <blockstatements>
<blockstatements> ::= <statement> | <statement>; | <statement_list> | <empty>
<statement> ::= <typespecification> <varDeclaration> <assignment-operator> <expression>
<typespecification> ::= char | short | int | long | float | double | string
<varDeclaration> ::= a | b | c | d | e | f | g | h | i | j | k | l | m | n | o | p | q | r | s | t | u | v | x | y | z
<assignment-operator> ::= =
<expression> ::= <value>
<value> ::= <digit> | <letter> | <number> | <word>
<digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
<letter> ::= "A" | "B" | "C" | "D" | "E" | "F" | "G" | "H" | "I" | "J" | "K" | "L" | "M" | "N" | "O" | "P" | "Q" | "R" | "S" |
            "T" | "U" | "V" | "W" | "X" | "Y" | "Z" | "a" | "b" | "c" | "d" | "e" | "f" | "g" | "h" | "i" | "j" | "k" | "l" |
            "m" | "n" | "o" | "p" | "q" | "r" | "s" | "t" | "u" | "v" | "w" | "x" | "y" | "z"
<number> ::= <digit> + <digit> | <digit> - <digit> | <digit> * <digit> | <digit> / <digit>

```

The above CFG isn't complete and I wanted to make sure that I'm doing it correctly. Am I heading towards the right path? Should it be written as above or have I missed anything?

Any help could be appreciated.

# Answer
> 3 votes
I've usually seen it expressed as something like:

```
forExpression ::= for ( <declExpression> <expression>; <expression> ) <blockStatement>

blockStatement ::= <statement> |  { <statementlist> }

statement ::= <declExpression> | <forExpression> | <ifExpression> | ...

```

`<declExpression>` includes the semi colon

You want to be very careful of the details like where you define where things like the semi colon are required,

In your `<number>` you don't have any priorities set up, there is also no option for parenthesis, ...

Creating a good CFG is hard which is why so many languages start out as a dialect of C and just take that grammar and adapt it.

---
Tags: formal-languages, context-free, formal-grammars, attribute-grammars
---


title: CPU sending and recieve Data?

text:
# Question
Title: CPU sending and recieve Data?
I am looking for an answer regarding the CPU read and write. We know there are two clocks that are working in the computer system, one is the peripheral clock and the other is the CPU own clock on which its control systems are working. I am familiar with the clock domain crossing but I dont understand how the CPU read and write data working on different clocks. For example the CPU sends the data to be written on the data bus and address on the address bus. Since the rest of the peripherals are working on their own clocks such as PCI or other standards, Now the CPU which is working on its own clock will execute the next instruction send the address again on the address bus and the data on the data bus to the same peripheral but data bits have still not been read by the peripheral so doesnt the data will be lost in this process or is there any mechanism of handling this situation ?

# Answer
That's why buffers are used.

While the transfer is in progress the peripheral writes the data into a buffer and the cpu ignores it and just works on its own clock.

Then when the transfer to the buffer is complete the peripheral will issue an interrupt (or other toggle a transfer complete pin) and the cpu will read from the buffer and if applicable let the next transfer start.

The buffer used can be the RAM this is often referred to as Direct Memory Access. The peripheral is attached to the memory bus and can issue reads and writes to ram directly.
> 1 votes

---
Tags: computer-architecture, cpu
---


# Question
Title: Find $i$-th number in unsorted sequence in logspace (deterministic turing machine)
> There is given input - words is sequence of numbers: $w\_i$ is number in sequence, $i$ is position. All of them are in written in binary system.
>
> $$w\_1\\#,...\\#w\_k\\#i$$ Prove that there exists deterministic Turing machine which find $i$-th number in sorted sequence $w$ in logspace.

I am not sure if I correctly solved it, so I ask for checking my reasoning. It seems to be fairly simple.

First of all, what we can do in logspace:
compare two numbers
iter over sequence (move to $n$-th number)

Simply, we consider one by one each element of sequence and count how many elements is less than currently considered. If we count $i-1$ numbers, then we stop. It requires logarythmic($k$) memory for counter. These counter can be reused (for each iteration).

Waht do you think ? Maybe some other approach to proving it ?

# Answer
> 2 votes
First let's consider the case when **numbers are unique**. The idea is that for each element $w\_t$ we count the number of elements in the sequence which are less than $w\_t$. After each loop on all elements of the sequence we check if there are $i-1$ elements less than $w\_t$ then $w\_t$ must be $i$-th element in the sorted sequence, so we halt with the output equal to $w\_t$.

```
proc(w, k, i)
 for t=0 to k
   counter = 0
   for j=0 to k
     if w[t] > w[j]
      counter = counter + 1
   if counter == i-1 then output w[t] and halt
end-proc

```

Now, if **numbers are not unique** then we have to count duplicates as well

```
proc(w, k, i)
 for t=0 to k
   counter = 0
   dups = 0
   for j=0 to k
    skip if j == t
    if w[t] == w[j]
      dups = dups + 1
   for j=0 to k
     if w[t] > w[j]
       counter = counter + 1
   if counter+1 <= i AND i <= counter + dups+1
     then output w[t] and halt
end-proc

```

```
  w[1] w[2] ... w[counter] w[t] w[t] ... w[t] ..
  \__________  __________/     \_____  ____/
             \/                      \/
 all elements less than w[t]   duplicates

```

Both procedures require only constant number of variables `i`, `j`, `k`, `counter`, and `dups` whose lengths are $O(\log(k))$. Your solution is similar to these algorithms so your approach is correct.

# Answer
> 0 votes
Maintain 3 registers, A, B, C. For the first two have them be "the Ath number is located at index B". The third register, use it to find the next largest number. Psuedo:

```
A = 1
B = the index of the smallest element in the sequence
C = number of elements equal to W[B]
A += C
while (A < I) {
  C = index of smallest element larger than W[B]
  B = C
  A += 1
  C = number of elements equal to W[B]
  A += C
}
output B

```

The main idea is that the entire procedure can be carried out with a constant number of pointers (you may need pointers for the subroutines also, but the amount doesn't depend on the input). Constant number of pointers and never copying any of the data from the list results in logspace.

---
Tags: algorithms, complexity-theory, turing-machines, space-complexity
---


# Question
Title: Contrasting Peterson’s and Dekker’s algorithms
I am trying to understand the algorithms by Peterson and Dekker which are very similar and display a lot of symmetries.

I tried to formulate the algorithms in informal language like follows:

```
Peterson's: "I want to enter."                 flag[0]=true;
            "You can enter next."              turn=1;
            "If you want to enter and          while(flag[1]==true&&turn==1){
            it's your turn I'll wait."         }
            Else: Enter CS!                    // CS
            "I don't want to enter any more."  flag[0]=false;

Dekker's:   "I want to enter."                 flag[0]=true;
            "If you want to enter              while(flag[1]==true){
             and if it's your turn               if(turn!=0){
             I don't want to enter any more."      flag[0]=false;
            "If it's your turn                     while(turn!=0){
             I'll wait."                           }
            "I want to enter."                     flag[0]=true;
                                                 }
                                               }
            Enter CS!                          // CS
            "You can enter next."              turn=1;
            "I don't want to enter any more."  flag[0]=false;

```

The difference seems to be the point where `"You can enter next."` occurs and the fact that `"if it's your turn I don't want to enter any more."` occurs in Dekker's.

In Peterson's algorithm, the two processes seem to be dominant. A process seems to force his way in into the critical section unless it's the other one's turn.

Conversely, in Dekker's algorithm, the two processes seem to be submissive and polite. If both processes want to enter the critical section, and it's the other one's turn, the process decides to no longer want to enter. (Is this needed for starvation-freedom? Why?)

How exactly do these algorithms differ? I imagine that when both processes try to enter the critical section, in Peterson's, the process says "I enter", while in Dekker's the process says "You may enter". Can someone clear up the way the processes behave in each algorithm? Is my way of putting it in informal terms correct?

# Answer
> 30 votes
Your informal descriptions of the algorithms is wonderful.

I think in both cases the author was trying to come up with the simplest solution they could think of that guaranteed both mutual exclusion and deadlock freedom. ~~Neither algorithm is starvation free or fair.~~\[ed: as pointed out in the comments, both algorithms are starvation free, and Peterson's algorithm is also fair\]. Dekker's solution was the first mutual exclusion algorithm using just load and store instructions. It was introduced in Dijkstra, Edsger W.; "Cooperating sequential processes", in F. Genuys, ed., *Programming Languages: NATO Advanced Study Institute*, pp. 43-112, Academic Press, 1968. If you read through the paper you see Dijkstra work through a number of attempts, recognizing the problem with each, and then adding a little bit more for the next version. Part of the inefficiency of his algorithm comes from the fact that he starts with a turn-taking algorithm and then tries to modify it to allow the processes to progress in any order. (Not just 0,1,0,1,...)

Peterson's algorithm was published in 1981, after more than a decade of experience and hindsight about Dekker's algorithm. Peterson wanted a much simpler algorithm than Dekker so that the proof of correctness is much easier. You can see that he was feeling some frustration with the community from the title of his paper. Peterson, G.L.; "Myths about the mutual exclusion problem," *Inf. Proc. Lett.*, 12(3): 115-116, 1981. Very quick read and very well written. (And the snide remarks about formal methods are priceless.) Peterson's paper also discusses the process by which he built his solution from simpler attempts. (Since his solution is simpler, it required fewer intermediate steps.) Note that the main difference (what you call "dominance" rather than "submissiveness") is that because Peterson started out fresh (not from the turn-taking algorithm Dijkstra started with) his wait loop is simpler and more efficient. He realizes that he can just get away with simple looped testing while Dijkstra had to backoff and retry each time.

I feel I must also mention Lamport's classic Bakery algorithm paper: Lamport, Leslie; "A New Solution of Dijkstra's Concurrent Programming Problem", *Comm ACM* 17(8):453-455, 1974. The Bakery algorithm is arguably simpler than Dekker's algorithm (and certainly simpler in the case of more than 2 processors), and is specifically designed to be fault tolerant. I specifically mention it for two reasons. First, because it gives a little bit of history about the definition of the mutual exclusion problem and attempts to solve it up to 1974. Second because the Bakery algorithm demonstrates that no hardware atomicity is required to solve the mutual exclusion problem. Reads that overlap writes to the same location can return *any* value and the algorithm still works.

Finally, a particular favorite of mine is Lamport, Leslie; "A Fast Mutual Exclusion Algorithm," *ACM Trans. Comp. Sys.*, 5(1):1-11, 1987. In this paper Lamport was trying to optimize a solution to the mutual exclusion problem in the (common) case that there is little contention for the critical section. Again, it guarantees mutual exclusion and deadlock freedom, but not fairness. It is (I believe) the first mutual exclusion algorithm using only normal reads and writes that can synchronize N processors in O(1) time when there is no contention. (When there is contention, it falls back on an O(N) test.) He gives an informal demonstration that the best you can do in the contention free case is seven memory accesses. (Dekker and Peterson both do it with 4, but they can only handle 2 processors, when you extend their algorithms to N they have to add an extra O(N) accesses.)

In all: I'd say Dekker's algorithm itself is interesting mainly from a historical perspective. Dijkstra's paper explained the importance of the mutual exclusion problem, and demonstrated that it could be solved. But with many years of hindsight simpler (and more efficient) solutions than Dekker's have been found.

# Answer
> 4 votes
In the following paper we give formal models for Peterson’s and Dekker’s algorithms (and some others) and we used model checker to prove their properties. Please, find our results in the table below (columns "Deadlock" and "Divergent" refer to our models, "ME" = TRUE means that the algorithm is correct, "Overtaking" = TRUE means that it is fair).

R. Meolic, T. Kapus, Z. Brezočnik. ACTLW - An Action-based Computation Tree Logic With Unless Operator. Information Sciences, 178(6), pp. 1542-1557, 2008.

https://doi.org/10.1016/j.ins.2007.10.023

# Answer
> 1 votes
**Peterson** algorithm has a more **strict** pressure on entering the critical section, where as **dekker**'s algorithm is relatively **softer** and **less** aggressive. To make it more clear, let's check out an example about iranian culture. Before getting into this example, it's good to know that iranian people have a real soft behavior to each other while entering somewhere! Guess two iranian men are going to enter a house, and that house has only one door to enter.

Now imagine two men from another culture(**Zombian Culture**) which they don't actually care too much about each other while entering somewhere(**It's a matter of respect to ask someone whether he wants to enter or not**).

To clarify the information about the problem we can say that:

* **Two Iranians = Two processes using the Dekker algorithm**
* **Two Zombians = Two processes using the Peterson algorithm**

So let's find out what's done in each algorithm(**culture**). The following comments are for the first **Iranian** man who is going to enter the house while using the **Dekker** algorithm:

```
p0:
   wants_to_enter[0] ← true // Goes through the house entrance
   while wants_to_enter[1] { // If the other man wants to enter too
      if turn ≠ 0 { // Then see if it is your turn or not
         wants_to_enter[0] ← false // If it is not your turn don't go furthur
         while turn ≠ 0 { // and wait until it is your turn
           // busy wait
         }
         wants_to_enter[0] ← true // when it is your turn go through the door
      }
   }

   // critical section
   ...
   turn ← 1
   wants_to_enter[0] ← false // Set the turn for the other man
   // remainder section

```

We have also two **Zombians** which are going to enter the house using the **Peterson** algorithm. This one goes as follows:

```
P0:
  flag[0] = true; // Goes through the house entrance
  turn = 1; // Set the turn for himself
  while (flag[1] && turn == 1) // Wait until the other one is going in
  {
   // busy wait
  }
   // critical section
      ...
   // end of critical section
  flag[0] = false; // Done going inside

```

It's important to mention that both of them are not going inside while the other one is doing so(**Mutual Exlusion**) but, **Iranian** people are much more softer.

---
Tags: concurrency, synchronization, mutual-exclusion
---


# Question
Title: How many different trees can we form from given graph?
I'm trying to practice some combinatorics and I faced this problem, let's say we have given graph with N nodes and M edges. $$N\leq500, M \leq N\cdot(N - 1)/2$$

In this graph I want to count the sub-sets of edges such that each subset will have exactly $N-1$ edges and the edges forming the subset will form connected graph.

**Example**

Let's say we have the following graph

We can count a total of 3 subsets: {1,2,3,5}, {1,2,3,4}, {1,2,4,5}. Please note the the numbers from 1 to 5 are marking the edges, not the nodes.

**What I think**

Let's say our graph is complete graph, it is the worse case. If we have 500 nodes and 499 nodes going out from each node, I think that there could be $500^{500}$ possible combinations which is huge number.

# Answer
> 3 votes
There is a simple algebraic algorithm based on the Matrix Tree Theorem. Just make the Laplacian matrix of the graph and compute $N^{-1}$ times the product of its non-zero eigenvalues.

---
Tags: algorithms, graphs, trees, counting
---


# Question
Title: Inclusion of points in rectangles using a sweepline algorithm
Given is a set of points $P\_{1},....,P\_{n}$ with $P\_{i} = (x\_{i},y\_{i})$. No two points have the same x and y coordinates. Given is also a set of m axis-parallel rechtangles $R\_{1},...,R\_{m}$ in a plane, described by their bottom left corner $(l\_{j},b\_{j})$ and upper right corner $(r\_{j},u\_{j})$. No two rechtangles intersect or overlay each other and no point is on the border of a rechtangle.

We need to describe a sweepline algorithm which can output all the points which are not in a rechtangle.

I proceeded like so:

The sweepline is a vertical line going from left to right and stopping and evaluating at each event point. Out event points are the points $P$ and also the $(l,b),(r,u)$ of each rechtangle. We sort all the event points according to their x-coordinate.

We use an AVL-Tree to save the y-coordinates of the lower left corner of a rechtangle and remove it once we reach it's upper right corner. When we reach a point $p$, we will simply evaluate if p is within the borders of a currently active rechtangle by checking if $y\_{p} \in \[b,u\]$ of active rechtangle. If so we mark it as false and proceed.

The solutions are that we are given more complicated and I don't understand them fully. I also don't know if my solution would work and why. It seems to be plausible to me.

They also save at each node of the AVL, the size of its subtrees so they can see how many points smaller than a node there are. Then while evaluating a point $p$, they search for p in the AVL tree and determine $A$ the number of keys smaller than $p$. Then it says that if $A$ is an even number, then the point is not in a rechtangle. Done.

I don't understand how this works. please help.

Thank you very much

# Answer
I think storing in the AVL-tree only bottom $y$ coordinate is not enough. I think you should store at least both bottom and top coordinates of the active rectangle. Since your rectangles are not overlapping storing only the bottom and top coordinates is enough to solve the problem.

Basically, storing active rectangle in the AVL tree needs to decide whether a point is in a rectangle. Consider the following scenario

```
  y1 ----------------------------
     |                          |
     |                          |
  y2 ----------------------------
         o y6
  y3 ----------------------------
     |                          |
     |           o y7           |
  y4 ----------------------------

  y5 ----------------------------
     |                          |
     |                          |
  y6 ----------------------------

```

Initially your $p$ points in the AVL tree. As you sweep you add both $y$ coordinates of the active rectangles in the tree (and remove them as you rich the end of the rectangle).

If at the same time you have more than one active rectangles then by brute force method you would need to go over all rectangles and check whether $p\_y \in \[b,u\]$. However, using AVL tree you could find the point $p\_y$ in the tree and check the number of points smaller than $p\_y$. If that number is even, say $2k$, then you have exactly $k$ active rectangles below $p$ meaning that $p$ is not in one of them, otherwise (if odd) it is in a rectangle. Look at the above figure, there are 4 points smaller than $y\_6$ and so $y\_6$ is outside, but there are 3 points smaller than $y\_7$ and so $y\_7$ is in a rectangle.
> 2 votes

---
Tags: algorithms, computational-geometry
---


# Question
Title: Function that enumerates a recursively enumerable language
I have an exercise where one is supposed to give a function that will enumerate the following language:

$L\_1 = \\{ a^pb^p \hspace{1mm} |\hspace{1mm} p \in \mathbb{N} \hspace{1mm} \wedge \text{ (P is a prime number )} \\}$.

The solution is the following function: $f: \mathbb{N} \rightarrow \Sigma^\*$ with $f(i) = a^{p\_{i+1}}b^{p\_{i+1}}$, where $p\_{i+1}$ is the $(i+1)^{th}$ prime number, ordered by the prime's order.

Could anyone explain to why does this solution work? And especially why does the function include $p\_{i+1}$ instead of $p\_{i}$ ?

Thank you!

# Answer
> 0 votes
This function maps nonnegative integers to the set of integers of the form $a^pb^p$. Enumerating is trivial, just start $i$ from 0, compute $p\_{i+1}$-th prime, compute $a^{p\_{i+1}}b^{p\_{i+1}}$ and output that number.

As for the index $i+1$, I guess that is because $0 \in N$ and it is assumed that primes are ordered starting from the index 1 not from 0, in other words we start from $p\_1$ not from $p\_0$, e.g., $f(0) = a^{p\_1}b^{p\_1}$.

---
Tags: computability, turing-machines, enumeration
---