# Question
Title: what does **input** mean for the $3SAT$ question? Is it the number of variables $n$ or the number of clauses $m$
We know that $3SAT \in NP$, and the definition of $NP$ is as follows:

$NP$ is the class of languages that have polynomial time verifiers.

But I have a question:

> what does **input** mean for the $3SAT$ question? Is it the number of variables $n$ or the number of clauses $m$,

Let's take an example, given a CNF expression, whose clauses has exactly 3 literals. The CNF expression consists of $m$ clauses involving $n$ variables $x\_1, ..., x\_n$.

If the input refers to the number of variables $n$, and the Boolean formula has $2^n$ clauses, it is obvious that an assignment of the validation formula requires $3\*2^n$ steps, not polynomial time.This contradicts that $3SAT \in NP$

If the input refers to the number of clauses $m$, an assignment of the validation formula requires 3\*m steps, which is polynomial time, which makes sense

So I think for the 3sat problem, the input refers to the number of clauses $m$, Is there a problem with my idea？

# Answer
Neither. The input is the Boolean formula $\phi$. You are probably asking what is the *length* of the input, as computational complexity tries to express the running time of the algorithm as a function of the length of the input. The length of $\phi$ depends on how it is encoded, but typically the length will depend on both $n$ and $m$. A reasonable estimate, for a typical encoding, is $\Theta(m \log n)$. If you want to think of the length of the input as $m$ that is a plausible approximation that is likely to be good enough for many purposes. As long as you use a reasonable encoding, the exact details are unlikely to change whether an algorithm is polynomial-time or not.
> 1 votes

# Answer
The input is just a Boolean formula $\phi$.

$|\phi|$ depends on the way in which $\phi$ has been encoded.
> 1 votes

---
Tags: complexity-theory, satisfiability, 3-sat, sat-solvers
---


# Question
Title: Time-complexity of evaluating a CNF formula
Given a Boolean formula over $n$ variables in CNF and a partial assignment to it, all the algorithms I can think of to evaluate the assignment run in time $\Theta(n^2)$. Is it possible to do it in $O(n)$? I'd say no, because otherwise SAT would be in NTIME(n) and we know that P is different from NTIME(n), but maybe this is a misleading argument.

# Answer
> 1 votes
No. You can't even do it in $O(n^2)$ time, if $n$ is the number of variables. The formula might be much longer than $\Theta(n^2)$ (it might have many more clauses than that), and obviously any correct algorithm will have to read the entire formula (at least in the worst case), so the running time of any correct algorithm has to be at least as large as the length of the formula. The length of the formula can be as big as $2^n$, so any algorithm to evaluate the formula under a particular assignment might take as long as $O(2^n)$ time, assuming you try to measure its running time only in terms of the number of variables.

In complexity theory, we normally don't measure the running time of algorithms in that way. Typically, we measure the running time as a function of the length of the input, not the number of variables.

---
Tags: complexity-theory, time-complexity, satisfiability, sat-solvers, boolean-complexity
---


# Question
Title: Find if two numbers are linked by a greatest common divisor
Two numbers $x,y$ are 'connected' if $gcd(x,y)\>g$. Here $gcd$ is the greatest common divisor. A path exists between two numbers $x,y$ if given $g$ and $n$ there is a sequence of numbers that connect $x$ to $y$ such that all numbers along the path are less than or equal to $n$.

How do you find if there exists a path between two numbers and if this needs to be repeated for multiple pairs of numbers would it be more optimal to first find all existing paths.

I've tried a basic approach of breadth-first search, where each query between two numbers involves calculating $gcd(x,y)\>g$. However, this is quite laborious and want to see if there is a more optimal solution.

As a simple example to motivate the problem, let $x=10, y=30, z=18$. Assume $g\>4$ and $n=50$. Then $x$ and $z$ are not directly connected but there is a path connecting $x$ to $y$ and from $y$ to $z$.

# Answer
That's an interesting problem. First of all, calculating directly the gcd between two numbers is clearly the fastest way to decide if they are connected. But as you noticed, quite unefficient for your problem.

A solution is to use prime factorization. Let's denote $P(z)$ the multiset prime factorization of a number $z$. Thus, you note that $gcd(x, y) = P(x) \cap P(y)$. Once you have the prime factorization $P(x\_0)$ of a number $x\_0$, you may compute all sub-multisets (there are $2^k$ for $k$ primes values), and if the product $p$ of any sub-multiset is above $g$, any multiple of $p$ lesser than $n$ is connectected to $x\_0$. Also note that all these multiples are a clique.

In fact, to generate all the connected numbers, you are only interested by "irreductible" sub-multisets. By irreductible, I mean that removing any (the smallest) prime factor would make the product lesser than $n$. Indeed, a reductible sub-multiset is already a multiple of an irreductible one and would generate no new connection. This may help to prune the loop on all sub-multisets of $x\_0$.

Let's take a small example: $n = 100$, $g=10$, $x\_0=60$.

$P(x\_0) = \\{2, 2, 3, 5\\}$. The irreductible sub-multisets above $g$ are:

* $P(12) = \\{2, 2, 3\\}$ =\> generating connections to $12 \times \[1, 8\]$
* $P(15) = \\{3, 5\\}$ =\> generating connections to $15 \times \[1, 6\]$
* $P(20) = \\{2, 2, 5\\}$ =\> generating connections to $20 \times \[1, 5\]$

Thus, we may generate the exhaustive list of the numbers conneted to $x\_0$: $12, 24, 36, 48, 60, 72, 84, 96, 15, 30, 45, 75, 90, 20, 40, 80, 100$.

Also note that by construction you already have partially the prime factorization of all these numbers.

In your question, it is quite unclear of what may be the limits of ($n$, $g$). Or if your several ($x$, $y$) share the same ($n$, $g$). What I discussed until now is the fastest way I found to explore the graph of connections. But for very high ($n$, $g$), it may be unconvenient to list explicitely all connections of a number. If you do a BFS/DFS, an important point is that there is no point to explore again the clique of an irreductible multiset. In fact, I think I would try to do the BFS/DFS on the graph of these irreductible multiset instead of the graph of the number values.

Also remember that it may exist no path between $x$ and $y$. For example with $g = 20$ and $n = 80$, one may identify some connected components:

* $\\{31, 62\\}$
* $\\{35, 70\\}$
* $\\{21, 42, 63\\}$
* $\\{25, 50, 75\\}$
> 1 votes

# Answer
At a minimum, whenever you check successfully that x and y are connected, you have found a divisor \> g of x and of y. You can record this and may be able to use it when you look for gcd(y, z).

If g is large then using Euclid’s algorithm but stopping when you know that gcd(x, y) \<= g might make things quicker. For example if g=100, and Euclid showed you that gcd(x,y) = gcd (3517, 99) you don’t need to calculate the gcd at all. If g is close to n you may be able to do more: Say g \>= n/3 and x \<= n, then gcd(x, y) \> g can only be true gcd = x or gcd = x/2.

But most savings can be had by having a good algorithm for finding a path from a to b, and breadth first isn’t it. Assume you have a trillion points, breadth first means you will examine more than half of all reachable points on average. Start your search from both ends and rely on the birthday paradox.
> 0 votes

# Answer
Your problem isn’t calculating gcd’s, your problem is the number of pairs you need to examine. If your algorithm isn’t clever then given some x, you’ll have to examine all y whether they are connected. This will take O(n) for each x.

Throw out all x \> n and x \<= g first. If one of your numbers is less than g then they cannot be linked. If their gcd is ≥ g then they are already linked. Factorise each x. Find all prime factors p with the property “x has a factor \> g consisting of prime factors \<= p only”. Example: x = $13\*11\*3\*2$, g=7. p=13,11. If x is connected to y, then y must have a prime factor 13 or 11. If g=70 then p=13: x cannot be connected to any number that isn’t divisible by 13 (and such a number needs some smaller prime factors as well).

For each prime p make a list of all x with such a factor. Now you know that only numbers on the same list can be connected. And obviously if p \> g then all pairs of numbers in the list are connected.

This is all done in k log n where k is the count of your numbers. Finding all numbers connected to some x should then be a lot quicker.

And then follow my algorithm for making an algorithm fast: implement something. Make it run. Figure out what it actually does. Figure out if it does unnecessary work or if it does necessary work too slowly. Make it faster and repeat.

PS. There are other things that you can do to simplify the problem. For example, if a ≤ n is a multiple of b, then you don't need b in the chain at all. If a is the only number containing some prime factor p then you can remove that factor from a.

With many numbers given, a solution is likely to exist. For example, if g = 2 then connecting both x and y to some (different) even number is enough. If g = 2 or g = 3 then connecting both x and y to a multiple of three is enough, and so on. This may give you a solution quickly. If g = 2 and there are two multiples of six, then all even numbers and all multiples of three are linked to each other, so if either x or y are connected to a multiple of 2 or 3, they are linked. So there are plenty of cases where you find links quickly.
> 0 votes

# Answer
You need to check all pairwise relations (by explicit computation of the $\gcd$s) and fill a graph. Then compute the *transitive closure* of the graph, in a modified way (to account for the $n$ constraint).

https://en.wikipedia.org/wiki/Transitive\_closure#Algorithms
> 0 votes

---
Tags: algorithms, time-complexity
---


# Question
Title: What is the amortized cost of pulling top K elements from a priority queue?
To pop an element off of a priority queue, the worst-case complexity is:

```
O(logN) where N is the number of elements.

```

Now if you do K pop operations on the priority queue, the number of elements decreases.

So the cost of these K operations would be:

```
O(logN) + O(log(N-1)) + O(log(N-2)) + O(log(N-3))... O(log(N-K))

```

How do you add these terms up? if K was a fixed number you could just amortize all of these terms to O(logN) and add them up together, so the sum becomes O(KlogN). But K is not a constant, it depends on the input!

If I wanted to pick top 5 elements from a 1000 elements, K = 5 & N = 1000. If I wanted to pick 10 elements, K would be 10.

How do you derive the cost of performing K pop operations on a priority queue?

Edit: I meant a priority queue implemented that is implemented using a heap

# Answer
Big-O doesn't care about a factor 0.5, for example. Now log sqrt(N) = 1/2 log N. So if you take away enough elements to change the size of the queue from N to sqrt(N), you have multiplied the time by 0.5, which doesn't affect O(N). And there are now only sqrt(N) elements remaining, removing them even if you could do it at zero cost won't change the time complexity either.
> 5 votes

---
Tags: time-complexity, amortized-analysis, priority-queues
---


# Question
Title: How to create all even length words from a given CNF grammar
given CFG *G1 = {V1, Σ1, R1, S1}* in its CNF form,

I have to define a new *G5* grammar that constructs *L(G5)* using {V1, Σ1, R1, S1}:

while *L(G5)* = { x ∈ L(G1) | |x| is even }

i . e .

*L(G5)* composed of all even length words in *L(G1)*

How can I do it?

# Answer
> 4 votes
This is a specific application of the fact that context-free languages are closed under under intersection with a regular languages. The usual proof is to use the fact that we can find a pushdown automaton and a finite state automaton, and then for the intersection simulate the pair in parallel. This is called the product construction.

Here there is a simple solution directly on the context-free grammar. For each nonterminal $A$ introduce two copies $A\_e$ and $A\_o$ that together derive the same set of strings, but separated into even length and odd length respectively. The productions must be annotated with odd and even accordingly.

---
Tags: context-free
---


title: Whether a number is in a sorted matrix

text:
# Question
Title: Whether a number is in a sorted matrix
I have a square n-by-n matrix of integers. The number of columns is equal to the number of rows. Each column and row are sorted from the lowest to highest numbers. For example:

Another example:

I need an algorithm to find whether a given number is in the matrix, with a complexity of $n$ or lower.

Thanks people

# Answer
The solution is in fact easy. See https://www.geeksforgeeks.org/search-in-row-wise-and-column-wise-sorted-matrix/

You start from the top-right element.

* if smaller than the target, you can strike-out the row to the left;
* if larger than the target, you can strike-out the column to the bottom;
* repeat with the new top-right element, until you find the target.

E.g. looking for the value 65, not found:
> 5 votes

---
Tags: matrices
---


# Question
Title: Would this be the correct time complexity?
I'm currently working on an exercise that has made me ponder for a bit. The following exercise is from the 6th Edition of Data Structures and Algorithms in Java:

> An **inverted file** is a critical data structure for implementing applications such an index of a book or a search engine. Given a document *D*, which can be viewed as an unordered, numbered list of words, an inverted file is an ordered list of words, *L*, such that, for each word *w* in *L*, we store the indices of the places in *D* where *w* appears. Design an efficient algorithm for constructing *L* from *D*.

I decided to go with a multimap. It is my understanding that my algorithm could work by "reading" *D* and putting each word as key and its position as value in the map. Because it is a multimap, this would mean that it doesn't matter if it's encountered the word before, since the previous value(s) wouldn't be lost. Then by the end of "reading", the algorithm will have created a map where it would be easily accessible to find a word we're looking for in the text, could return all the positions of the word, etc. And since `put(k,v)` takes $O(1)$ time, then for $n$ words that would be $O(n)$ time.

I would like for someone to explain the following things, so that I can understand a bit more:

1. Because it sounds like a simple solution I'd like to make sure it's a correct one.
2. $O(n)$ sounds like an awful lot when the *D* file contains a lot of words. Does this solution limit it to smaller files too much?
3. Lastly, is there another way to implement this that is more efficient? It doesn't matter if the method is unknown to me, I'm just curious about it.

# Answer
Since you have $n$ word, the `put(k,v)` operation needs to be done at least $n$ times. Let's say you have an algorithm that process $D$ in $o(n)$. The algorithm is not considering some words, hence it's not working properly. That's because words have not an ordering or a property that can let any algorithm "skip" some words.

Also, I don't think $O(n)$ is awful, in this case it's the best we can do :)
> 2 votes

---
Tags: time-complexity, data-structures, filesystems
---


title: Algorithm to change order of tree

text:
# Question
Title: Algorithm to change order of tree
I'm looking for an algorithm name to change the order of the levels of a tree. I've done something that works but there's a lot of code and the $ O(n) $ is very bad.

Here's an example, let say there are 3 levels. Each level representing something in a hierarchy `project > budget > fiscal year`

project = {a} budget = {b, c} fiscal year = {d, e}

```
   root
    |
    a
   / \
  b   c
 /\   /\
d  e  d e

```

I would like to build a tree with the level in different order

fiscal year \> project \> budget

```
   root
    / \
   d   e
   |   |
   a   a
  /\   /\
  b c  b c

```

budget \> fiscal year \> project

```
   root
   /  \
   b   c
  /\   /\
 d  e d  e
 |  | |  |
 a  a a  a

```

The initial tree can be more complicated. Each node can have more than 2 children.

```
    root
    /  \
   a    b     - Projects {a, b}
  / \  / \
 c  d  c  e   - Budgets {c, d, e}
 |  | /\  |
 f  g f g g   - Fiscal year with data {f, g}

```

# Answer
> 0 votes
If I may elaborate on @Optidad 's comment.

Input:

```
   root
    |
    a
   / \
  b   c
 /\   /\
d  e  d e

```

*"Building the list of all possible tuplets"* means, in other words, enumerating all max length paths, namely:

```
   0 1 2
   -----
   a b d
   a b e
   a c d
   a c e

```

Shuffle the columns (representing the levels of the original tree) as you want, e.g.:

```
   2 0 1
   -----
   d a b
   e a b
   d a c
   e a c

```

Taking this data record by record, the desired tree can be built directly.

Output:

```
   root
   /  \
  d    e
  |    |
  a    a
 /\    /\
b  c  b  c

```

# Answer
> 0 votes
I would write a function to fill a new tree one record at a time, each record being percolated down by levels. (There will be as many such functions as different orderings that you want to handle.)

Then traverse the existing tree to extract all records and feed them to the filling function.

E.g., if you retrieve the records in the order abd, abe, acd, ace, you will feed dab, eab, dac, eac, giving the partial trees

```
r - d - a - b

r + d - a - b
  - e - a - b

r + d - a + b
          - c
  - e - a - b

r + d - a + b
  |       - c
  - e - a + b
          - c

```

You said nothing about your representation of the tree nodes, so this is up to you. Anyway, consider my remark below your post.

---
Tags: algorithms, trees
---


# Question
Title: Finding source-like nodes in a flow notework
Let $G$ be a flow network, where $c(e)$ is the capacity of an edge, and the source is $s$ and sink $t$. Define a node $v$ to be "source-like" if for every min-cut $(S,T)$ of $G$ where $S$ contains $s$, $S$ contains $v$. Find an efficient algorithm to determine the source-like nodes.

I was thinking that since Ford-Fulkerson is efficient, we can go ahead and run that to get the max flow solution, and perhaps use that to find the source-like nodes. However, as I look at examples and try to think of what to do with the flow network, I don't see how to identify source-like nodes.

Of course when you look at the residual graph at the end of Ford-Fulkerson, there is a cut where all the edges point away from $t$ and toward $s$ roughly speaking. This cut is a min-cut. But it is just one min-cut. I'm not sure how to work in the idea of all possible min-cuts. Cutting an edge seems like a bad idea. Redirecting flow in small changes seems like a bad idea.

When I think of a graph where I can trivially spot two distinct min-cuts, I think of:

```
s -> b weight 3
s -> c weight 3
b -> d weight 3
c -> e weight 3
d -> t weight 3
e -> t weight 3

```

Basically this just sets up two parallel tracks. In fact as I think about it, here I think the source-like node would be the source node.

I wonder if it's the case that in any max-flow solution, every min-cut is some set of edges which are completely used up by the max-flow?

# Answer
The example given in the question suggests that we want to find the min-cut that is "nearest" to the source $s$.

The answer is "the first" min-cut yielded by a max-flow. More specifically, find a max-flow $f$ of $G$, which can be done efficiently by Ford-Fulkerson algorithm or other algorithms. Let $G\_f$ be the residual network of $f$. Let $S$ be the set of the nodes reachable from $s$ in $G\_f$. Then $S$ is the set of all source-like nodes.
> 1 votes

---
Tags: algorithms, network-flow, ford-fulkerson
---


title: Nested for-loop math notation

text:
# Question
Title: Nested for-loop math notation
I'm new to writing math notation that describes algorithms and I need to translate some python code. Does the notation structure below correctly describe a nested for-loop that for-each value in p iterates over all other values in p?

Example code

```
function(p):
    for a in p:
       for b in p:
         // do something with a and b...

```

# Answer
The $\sum$ notation is specifically summation. There is also product notation:

$$n! = \prod\_{i=1}^{n} i $$

But I think what you want is some kind of Zermelo-Fraenkel notation?

$$\left\\{ f(a,b)\\,|\\,a,b \in P \right\\}$$
> 0 votes

# Answer
That would be

$$\sum\_{a\in p}\sum\_{b\in p}\delta\_{ab}$$

if we assume that you want to count the number of duplicate elements in $p$, using the Kronecker delta notation.

This works for $p$ being a set. In case of a sequence $p\_k$ of length $n$,

$$\sum\_{i=0}^{n-1}\sum\_{j=0}^{n-1}\delta\_{p\_ip\_j}$$
> 0 votes

---
Tags: algorithms
---


# Question
Title: Stable sort an array with k distinct elements, each appearing double the times the previous one appears
I've started with thinking of a bucket sort/radix sort variation, only to be disproved by a colleague.

Here's the problem:

> Given an array with $k$ distinct elements, it is known that the smallest element appears once, the 2nd smallest element appears twice, the 3rd smallest element appears 4 times, the 4th smallest appears 8 times, and so on until the $k$-th smallest element, which appears exactly $2^{k-1}$ times.
>
> Marking the size of the array as $n=2^k-1$, suggest an algorithm to stable sort the array in $O(n)$, provide explanation for the algorithm.

The second path of thought I had was making a new array sized $\log(n)$ with a queue in each cell, thus repeating elements keep their order.

However, the best algorithm I came of is doing this is $O(nk)=O(n\log n)$ time, which seems pretty legit to a sorting algorithm without a given range(such as in bucketsort). Yet the problem demands $O(n)$.

# Answer
> 4 votes
Copy the elements into a temporary array. As long as the temporary array isn't empty, repeat this:

1. Find the majority value in the temporary array (e.g., using Boyer-Moore (or, as Rainer's answer reminds, simply `max` in our case, but I'll keep `majority` now)).
2. Copy the majority elements backwards into the original array.
3. Remove the majority elements from the temporary array.

Python implementation including test (Try it online!):

```
def sort(xs):
    tmp = xs[:]
    i = len(xs)
    while tmp:
        m = majority(tmp)
        for x in reversed(tmp):
            if x == m:
                i -= 1
                xs[i] = x
        tmp = [x for x in tmp if x != m]

def majority(xs):
    leader = None
    lead = 0
    for x in xs:
        if not lead:
            leader = x
            lead = 1
        elif x == leader:
            lead += 1
        else:
            lead -= 1
    return leader

from random import sample, shuffle
k = 15
xs = sorted(sample(range(1000), k))
xs = [[x] for i, x in enumerate(xs) for x in [x] * 2**i]
shuffle(xs)
expect = sorted(xs)
sort(xs)
print(xs == expect)
print(all(x is e for x, e in zip(xs, expect)))

```

For the curious reading the test code: I wrap each number in a list so that I get distinct (but equal-valued) objects. That allows testing the stability, which I do at the end with the identity checks using `is`. Note that Python's own `sorted` is stable, so I use that to compute the expected order.

# Answer
> 1 votes
Find the maximum element, then partition the array into two buckets, smaller and equals. Apply the algorithm recursively to the smaller bucket. Here is an example implementation in Python:

```
def quicksort(data):
    '''stable out-of-place quicksort with maximum element for pivot'''
    if not data:
        return []
    pivot = max(data)
    smaller = [x for x in data if x < pivot]
    equals = [x for x in data if x == pivot]
    return quicksort(smaller) + equals

```

If the majority element is not necessarily the largest one, you have to expand it into a full quicksort and use the Boyer-Moore majority algorithm to find the pivot, like this:

```
def quicksort(data):
    '''stable out-of-place quicksort with majority element for pivot'''
    if not data:
        return []
    pivot = majority(data)
    smaller = [x for x in data if x < pivot]
    equals = [x for x in data if x == pivot]
    greater = [x for x in data if x > pivot]
    return quicksort(smaller) + equals + quicksort(greater)

```

Runtime complexity is linear because half of the items fall into the equals bucket, where no recursive sort is applied. Both algorithms produce a correct and stable sort on any input, but linear runtime complexity is only guaranteed if a majority element exists and is chosen for pivot.

# Answer
> 0 votes
Consider a version of Mergesort that returns an array of lists. Each list in the array groups all element with the same value (and stores them in the same order as they appear in the original array).

Clearly each array has at most $k$ elements. Moreover, if we are given two sorted arrays, each of which stores $m$ elements overall in its lists, we can merge them in time $O(\min\\{m,k\\}) = O(\min\\{m, \log n\\})$.

The running time of the algorithm is therefore described by the recurrence:

$$T(m) = 2T(m/2) + O(\min\\{m,\log n\\}),$$ which has solution $T(n) = O(n)$.

# Answer
> 0 votes
The main idea is to sort it from the largest element that basically will appear $n/2$ times, the second largest will appear $n/4$ and continues on until the smallest.

For example after sorting this array $\[8,3,2,8,8,8,3\]$ it will look like that $\[2,3,3,8,8,8,8\]$ (where k=3). In order to take out the all appearances of 8 it will cost $O(n)$ (one iteration for finding who the largest is, and second to move all of his appearances to be between $n/2\_{th}$ and the $n\_{th}$ places).

Now we have half sorted array $\[3,2,3,8,8,8,8\]$ so we will need to deal with the remaining half array $\[3,2,3\]$ so basically we are facing now the same problem but with k=2.

Therefore we will use recursive solution:

$T(n)=T(\frac{n}{2})+O(n)$ By using the master theorem the answer is $O(n)$

For better understanding it really close to merge-sort just with sorting half array every time.

---
Tags: algorithms, time-complexity, sorting
---


# Question
Title: Design a CFG for $L=\{ w \in \{ 0,1 \}^* \}$, where $w$ contains at least three ones
$L=\\{ w \in \\{ 0,1 \\} \\}$ **where $w$ contains at least three ones**

Here is one solution for the productions:

$S \to A1A1A1A$

$A \to 1A | 0A | \epsilon$

However, now I have a question. Could I modify the second rule to be as follows:

$A \to A1 | A0 | \epsilon$

What I did was just switch the places of the non-terminals and terminals in the second rule. For most of the words I tried, this grammar also works well. What is the difference between writing $1A$ and $A1$?

# Answer
> 1 votes
Yes, you can safely modify the rules for $A$. In this particular case, the order ($A1$ vs. $1A$) makes no difference in the language generated by your grammar.

The difference is in the way how words are generated (derived) using your grammar.

When the rules for $A$ are the former ($A \to 1A \mid 0A \mid \varepsilon$, the derivation can be (for example) $S \Rightarrow A1A1A1A \Rightarrow 0A1A1A1A \Rightarrow 01A1A1A \Rightarrow 011A1A1A \Rightarrow 0111A1A \dots$.

While in the latter form, the derivation can look like $S \Rightarrow A1A1A1A \Rightarrow A01A1A1A \Rightarrow 01A1A1A \dots$

# Answer
> 0 votes
I suggest you need to understand very carefully Chomsky Hierarchy for $Type-0,Type-1,Type-2,Type-3$ grammar. Then you perceive all the grammar and production rules, restrictions for respective $Type.$

Alone the grammar $A \rightarrow 1A|0A|\epsilon$ is under $Type-3$ grammar which is known as Right-Linear-Grammar. If you are writing production which is $Type-3$ then you could use only one production which either Right-Linear or Left-Linear at a time not the both at same time.

But your written grammar in the question is the grammar which is under $Type-2$ that's why it has less restrictions than $Type-3$, it's allowed both Right-Linear or Left-Linear at a time or combination of both are allowed.

---
Tags: formal-languages, finite-automata, context-free, formal-grammars
---


# Question
Title: How could Penrose's universal Turing machine with a binary alphabet work?
In his book *The Emperor's New Mind*, Roger Penrose gives an overview of Turing machines in Chapter 2. In his definition of what a Turing machine is he is very minimalist. There is a single linear tape infinite in both directions composed of cells, each of which is either blank or contains a single mark. He represents a blank as '0' and a mark as '1'. There is no separate blank ' ' space which the machine treats differently from '0'. (See page 37.)

Penrose walks through a scheme for encoding a Turing machine as a binary string of '0's and '1's. (See page 52.) He then introduces what a universal Turing machine $U(n,m)$ would do: simulate what the $n$th Turing machine $T\_n$ would do with the input integer $m$. He says:

> What the Turing machine $U$ would have to do, at each successive step of the operation of $T\_n$ on $m$, would be to examine the structure of the succession of digits in the expression for $n$ so that the appropriate replacement in the digits for $m$ (i.e. $T\_n$'s 'tape') can be made. In fact it is not difficult in principle (though decidedly tedious in practice) to see how one might actually construct such a machine. Its own list of instructions would simply be providing a means of reading the appropriate entry in that 'list' which is encoded in the number $n$, at each stage of application to the digits of the 'tape', as given by $m$. There would admittedly be a lot of dodging backwards and forwards between the digits of $m$ and those of $n$, and the procedure would tend to be exceedingly slow. Nevertheless, a list of instructions for such a machine can certainly be provided.

In the chapter's endnotes he gives a binary representation of a universal Turing machine he concocted, and which he says was verified by David Deutsch. He doesn't give any details about its implementation.

**My question:**

I would like to understand what he says is "not difficult in principle...to see". I'm having difficulty because of the restrictiveness of the binary alphabet. Other descriptions of universal Turing machines I've seen online use a more expansive alphabet, so that the machine can use a special character to mark where it needs to return when it is has completed doing something else. How would a Turing machine which only uses '0's and '1's for both input and output do its bookkeeping?

The input tape consists of

* the binary integer $n$
* followed by '111110' (which, because of the encoding Penrose has chosen, doesn't appear in any Turing machine $T\_n$ which is correctly specified---see page 54) marking the end of the specification of $T\_n$
* followed by the binary integer $m$ (and an extra '1', see bottom of page 54/top of page 55).

What if $T\_n$ needs to write to the left of $m$? It can't overwrite the specification of $T\_n$ itself, so it would need to copy the specification, shifting it to the left to make more blanks available. (Alternatively it could copy everything to the right of the specification for $T\_n$ even further right.) I can't even see how $U$ would bookkeep a copy operation.

How could $U$ keep track of the current state that $T\_n$ is in? When it is parsing $T\_n$ to figure out what action it is next supposed to take, how could it keep track of where in $m$ it is supposed to go back to perform the action? Etc.

I'm not looking for anything too detailed, just something that would help me understand "in principle", as Penrose says. I suppose I could "disassemble" the universal Turing machine Penrose gives to see how he did it, but the binary specification is almost two pages of '0's and '1's and I'm not very excited about the prospect of doing that.

# Answer
One can overcome the limitations of binary characters by adding new states and treating binary characters as bounded-size groups – rather similarly to how physical computers combine zeroes and ones into bytes, words and beyond.

Suppose you have "all the symbols you'll need" in your alphabet, to implement a Turing machine you want. Let $N$ be the number of states – therefore you need $\lceil \log\_2N \rceil$ bits to differentiate them. Let's call this number $b$.

A naïve but easy solution to convert the TM to binary is to assign each non-blank symbol a distinct combination of $b$ bits. When the original TM would move the head, we instead move $b$ times, and read the symbol represented by the bits by storing the bits read in the TM's state. This is possible, since $b$ is a constant affected only by the size of the original TM's alphabet. Writing a new symbol is likewise just a state transition to a chain of states which remembers the $b$ bits that need to be written and the state to proceed to from there.

All in all, this causes the TM to require a dramatic increase in the number of states, but the important point is not that it is efficient or easy but that it is possible.
> 1 votes

# Answer
> It can't overwrite the specification of $T\_n$ itself

why wouldn't it? Part of that specification could include tape space for pseudo registers, instruction pointers or other scratch memory space that the turing machine needs to function.

But there is a simpler solution to writing to the left of $m$ (or right of $n$): copy the number over by one cell and then write into the newly created gap.
> 0 votes

---
Tags: turing-machines
---


# Question
Title: What does this condition in the for loop mean?
I found a solution of exercise C-8.28 from Data Structures and Algorithms in Java (6th Edition), but I'm having trouble understanding how the for loop condition works here.

```
for(Position<E> c : T.children(p))

```

I'm having trouble understanding what the condition in the for loop means. From what I've learned so far the for loop is formatted with 3 conditions so I'm not familiar with it and I'm trying to understand the concept behind this solution. I looked it up online, but I haven't been able to find another instance of this, though I did find something about the format `for(type variable : collection)` in a greek Data Structures book by Panagiotis D. Mpozanis. Yet, I don't understand it. Could you help me a bit with this?

# Answer
> 1 votes
This is called a For-each loop. in your example: `for(Position<E> c : T.children(p))` the **c** is a variable of type **Position\<E\>** and it takes it's value in each iterate of the for from a **list** or an **array** or whatever container of type **Position\<E\>**, meaning the **T.children(p)** must be a container of type **Position\<E\>**.

For a more simple example in order to understand the mechanism of the For-each loop here is an example: Consider a class named Person and an App class where App creates instances of Person and prints it using the For-each loop:

Person:

```
package org.example;

public class Person {

    private String firstName;

    private String lastName;

    private String gender;

    private byte age;

    public Person(String firstName, String lastName, String gender, byte age) {
        this.firstName = firstName;
        this.lastName = lastName;
        this.gender = gender;
        this.age = age;
    }

    public String getFirstName() {
        return firstName;
    }

    public String getLastName() {
        return lastName;
    }

    public String getGender() {
        return gender;
    }

    public byte getAge() {
        return age;
    }
}

```

App:

```
package org.example;

import java.util.ArrayList;
import java.util.List;

public class App {

    static void generate(List<Person> personList) {

        for (int i = 0; i < 10; i++) {
            personList.add(new Person("John" + i, "Smith" + i, "Male", (byte) (i + 20)));
        }
    }

    public static void main(String[] args) {

        List<Person> personList = new ArrayList<>();
        generate(personList);
        System.out.println();
        for (Person person : personList) {
            System.out.println("First Name: " + person.getFirstName() + "; Last Name: " +
                    person.getLastName() + "; Gender: " + person.getGender() + "; Age: " + person.getAge());
            System.out.println();
        }
    }
}

```

Note in the App.main in the for loop it's the same as your loop but it takes a person in each iterate in the order it appears in the list and prints it.

For further explanation you can read at For-each loop in Java.

---
Tags: data-structures, loops, java
---


# Question
Title: Recreate a spanning tree in a grid graph given vertex descriptions
Let's assume I have graph above with spanning tree pointed out by blue edges.

Vertex at position (1,1) (row 1, column 1) is connected to the bottom vertex and has degree 1.

Vertex at position (4,2) (row 4, column 2) is connected to the up, left and right vertex and has degree 3.

Let's call (up, down, left, right) a description of a vertex. For a vertex that is connected to a vertex above it and a vertex left to it, description is (1, 0, 1, 0). For a vertex that is connected to a vertex above, below, left and right to it, description is (1, 1, 1, 1).

Given an array of descriptions of vertices that belong to a spanning tree of a grid graph, dimensions of the grid, recreate a spanning tree that decodes to a given array of descriptions.

For example, for the image above an input to the algorithm could be:

```
[
  (0, 0, 1, 0),  # this one describes vertex at position (4, 4), it is connected to the vertex on the left
  (1, 0, 1, 1),  # vertex (4, 2)
  (0, 1, 1, 0),  # vertex (2, 4)
  (1, 0, 1, 1),  # vertex (2, 3)
  (1, 0, 1, 1),  # vertex (2, 2)
  (1, 0, 0, 1),  # vertex (2, 1)
  (0, 1, 0, 0),  # vertex (1, 2)
  (0, 1, 0, 0),  # vertex (3, 1)
  (0, 1, 0, 1),  # vertex (1, 3)
  (1, 0, 1, 0),  # vertex (3, 4)
  (0, 1, 0, 0),  # vertex (1, 1)
  (0, 1, 0, 1),  # vertex (3, 2)
  (0, 0, 1, 0),  # vertex (1, 4)
  (0, 0, 1, 1),  # vertex (4, 3)
  (0, 0, 1, 1),  # vertex (3, 3)
  (1, 0, 0, 1),  # vertex (4, 1)
]

```

One of the possible outputs can be (reordered array of descriptions, but I can go over each description and color the edges in an empty grid and get the image above):

```
[
  (0, 1, 0, 0),  # vertex (1, 1)
  (0, 1, 0, 0),  # vertex (1, 2)
  (0, 1, 0, 1),  # vertex (1, 3)
  (0, 0, 1, 0),  # vertex (1, 4)
  (1, 0, 0, 1),  # vertex (2, 1)
  (1, 0, 1, 1),  # vertex (2, 2)
  (1, 0, 1, 1),  # vertex (2, 3)
  (0, 1, 1, 0),  # vertex (2, 4)
  (0, 1, 0, 0),  # vertex (3, 1)
  (0, 1, 0, 1),  # vertex (3, 2)
  (0, 0, 1, 1),  # vertex (3, 3)
  (1, 0, 1, 0),  # vertex (3, 4)
  (1, 0, 0, 1),  # vertex (4, 1)
  (1, 0, 1, 1),  # vertex (4, 2)
  (0, 0, 1, 1),  # vertex (4, 3)
  (0, 0, 1, 0),  # vertex (4, 4)
]

```

The array can come in any order (there is no way to know for which position the description is). Of course, vertices in the first row can never be connected to a vertex above (there is no row above), similarly, vertices in the last row, first column, last column, cannot be connected to vertices below, left, or right, respectively.

Is there an efficient algorithm that will recreate the spanning tree or enumerate all possible spanning trees that decode to the given descriptions array.

I think that from the given array there are multiple spanning trees of a grid graph (the array does not uniquely define the spanning tree shown on the picture). Similarly, if I was given a sorted degree array `[1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3]` (decoded from the image above), I could construct a variety of trees that satisfy this degree array but some of these trees would not span a grid.

Problem is related to the game described here https://math.stackexchange.com/questions/3191645/uniqueness-of-spanning-tree-on-a-grid/3191756 but there one can rotate things, here, we just have shuffled grid and need to recreate some spanning tree of the grid by repositioning the elements.

# Answer
> 2 votes
It's not possible. There isn't enough information in the input, even if you had unlimited computing time.

The order of the input is irrelevant. So, we could equivalently specify the input as follows. Each node can be assigned to one of 16 different descriptions (for instance, a node that is connected to one above it and one to the left of it has description (1,0,1,0)). So, the input could equivalently be described by providing 16 counts: for each description, a count of how many nodes have that description.

And now we can see that, for large grid graphs, the number of possible spanning trees exceeds the number of possible inputs. So, you can't hope to uniquely recover the spanning tree from just this information. Moreover, there can be exponentially many spanning trees that are consistent with any one given input, so there is also no efficient algorithm to enumerate all possible spanning trees that match the input.

Why? Suppose you have a $m\times n$ grid graph, where $m\>2$ and $n\>2$. Then the number of spanning trees of this grid graph is exponential in $mn$. However, the number of possible inputs is at most $(nm+1)^{16}$, since there are 16 descriptions and for each description we have a count that ranges from $0$ to $nm$. The latter number is polynomial in $nm$, so when $nm$ is large, we find that the number of possible spanning trees vastly exceeds the number of possible inputs.

---
Tags: algorithms, enumeration, spanning-trees, planar-graphs, square-grid
---


# Question
Title: Is there a realistically implementable algorithm for testing the termination of a given petri net?
I am trying to implement this petri net simulator. Amongst it's specifications it has to return a map of reachable markings from the current state. I don't really want it to give me an OutOfMemoryError or something if I'm given a petri net with infinite reachable markings. Can this be resolved more elegantly?

In my case the net can have inputs and outputs of any natural value, as well as reset and inhibitor arcs.

# Answer
> 0 votes
It is very hard in general (EXPSPACE-complete) to decide whether the set of reachable markings is finite, even for standard Place/Transition nets without any added features.

What I'd probably do is generate a list of reachable markings with an option for the user to generate more.

---
Tags: algorithms, petri-nets
---


# Question
Title: Verification of atomic primitives using Petri Net Models
I want to verify semantics of a library of atomic primitives that I wrote. The idea is, only if the semantics of all the primitives are consistent with each other, an application that uses them could behave predictably.

For example, a composition of a primitive Fx(lck) which takes exclusive lock on an lck object could be - Fx(Fx(lck)). But this could lead to a dead lock when operated on a single thread. This is a valid scenario if lck is a non-recursive lock.

I wonder if I could create a Petri Net model of my primitives to check if they are present a perfect synchronization tool.

You can also propose an alternate solution.

# Answer
Definitely, but you may need something stronger than a standard Place/Transition net.

You could try a tool for colored Petri nets, such as CPN Tools.
> 1 votes

---
Tags: computation-models, synchronization, petri-nets
---


# Question
Title: Prove the equivalence of the modified Turing Machines and the standard Turing Machines
We have a Turing Machine that cannot write the same symbol it has read in a transition, meaning it should always alter the symbol when passing it. How can we prove that such machines have equal processing power compared with the standard Turing Machines?

# Answer
Since a modified Turing machine is a special kind of the standard Turing machine, the power of modified Turing machines is at most that of standard Turing machines.

Now suppose $S$ is a stand Turing machine with $\Gamma$ as its alphabet on tape.

Let $\Gamma'$ be a copy of $\Gamma$, i.e., for all $\gamma\in\Gamma$, there is a corresponding $\gamma'\in\Gamma'$.

Let Turing machine $M$ be the same as $S$ except that

* $M$'s alphabet on tape is $\Gamma\sqcup\Gamma'$.
* Suppose $M$ read $\alpha\in\Gamma$ or $\alpha'\in \Gamma'$. Then $M$ will behave like $S$ as if $S$ had read $\alpha$, except that $M$ will write $\beta'$ instead if $S$ would write $\beta\in\Gamma$ when $\alpha$ was read.

We see that $M$ is a modified Turing machine that simulates $S$. Hence the power of modified Turing machines is at least that of standard Turing machines.
> 0 votes

---
Tags: turing-machines, automata, simulation
---


# Question
Title: Given a list of strings enumerated over a finite alphabet, what's the most efficient way to get a string by its index?
Say you have the finite alphabet $\\{a,b,c,d,e,f,g\\}$ and an enumeration of finite strings over it by the shortlex order (length-lexicographic ordering), starting with the empty string, i.e., $\epsilon, a, b, c, d, e, f, g,$ $aa, ab, ac, \cdots,$ $gg, \cdots, aaa, aab, aac,$ $\cdots, ggg, \cdots$.

What's the most efficient algorithm to get a string from that sequence by its index? For example, given 9, we should get $ab$.

Basically, I'm looking for a fast procedure that takes an integer $x$ and returns the $x$-th string from a list of strings enumerated over a fixed, finite alphabet.

# Answer
> 1 votes
Easier problem: Suppose you want the $i$th string, from all length-$k$ strings over that template. Can you find the $i$th string? This is easy. I'll let you figure out how to do that.

Your problem: Suppose you want the $i$th string. Well, there are $1+6+6^2+\dots+6^k$ strings of length $\le k$ over this alphabet. So, find the smallest $k$ such that $i \le 1+6+6^2+\dots+6^k$; then you know that the output needs to be a length-$k$ string. Let $j=i-(1+6+6^2+\dots+6^{k-1})$; and find the $j$th string, from all length-$k$ strings.

I'm guessing you can take it from here.

---
Tags: algorithms, strings, enumeration
---


title: Can computers only add?

text:
# Question
Title: Can computers only add?
So recently I've been involved in a discussion and I was told that literally the only thing computer can do is addition. Is that true? What about logic operations? Aren't they performerd by physical logic gates?

# Answer
> 1 votes
You know something about logic gates since I see them in your question. I believe that computers can do much more than add, but let me play devil's advocate and try to show you that we could think of most of what computers do is adding.

So the main logic gates in classical computers (the ones that use electricity) are "and gates", "or gates", and "not gates". The "and gate" takes two bits and produces a one if both input bits are 1. We could say that this computes the addition of two bits and outputs a one if adding the two bits equals 2. We can prove this by checking each case. If both bits are 0, then clearly their addition does not equal 2, so it outputs a zero. If only one of the bits is 1, and the other bit is zero, these bits only sum to 1 and so the output is also a zero. Finally, if both input bits are 1, their sum is 2 since 1+1=2, and so the gate outputs a 1.

"Or gates" produce an output of 1 if the sum of the input bits is 1 or more. So checking our cases, if both bits are zero, than the sum is 0 and so the output is 0. If the inputs are 1 and 0, then the sum is 1 and so the output is 1. If both input bits are 1, then the sum is 2 and the output is 1.

The "not gate" may be the trickiest gate to think of in terms of addition. The not gate only has one input. It basically switches the input, so its output is "not" its input. We can think of this as adding one, but with a carry bit. If the input is 0, then the output is 0 + 1 = 1. The tricky part is when the input is 1. We can do this, but only in "binary". In binary, adding one plus one gives you 2, but 2 in binary is written as 10, so that the ones digit is zero, as desired.

I think that for arithmetic, @Pseudonym's links show you how to do that.

Their are instructions that tell the computer to go to different parts of the computer program or code. A lot of these use comparison, which use the logic gates I mentioned above, and Boolean algebra. For example, the computer may use an instruction that tells the computer to go to a different part of its instructions if a number is larger than 10. The computer does this by first adding -10 to the input, and then using Boolean algebra to test if this result is greater than zero, which is easy for a computer. It can use Boolean algebra and logic gates for this.

Computers also do things like copying registers (which are just numbers stored in the processor). While this doesn't involve addition, you could think of it as a way of putting a number into the computer's processor so that it can add something the next time that the processor does something.

---

Well, hopefully this wasn't boring, and that you learned something. There are many ways to think of a computer, and scientists have actually put a fair amount of time into actually defining what a computer is. What scientists came up with is a Turing machine, named after Alan Turing.

# Answer
> 1 votes
Computers can perform any algorithm using only addition (or even using only the x86 MOV instruction).

But what they have is a set of instructions aiming to maximize performance.

A computer that only use the add operator will be slow in doing multiplication. To get around this, computers have hardware-implemented functions performing binary multiplication and division. But actually the most of instructions executed in the hardware by the code are moves, branches and add/sub operations, as you can see in SPEC CPU2017 Benchmarks.

Logic gates are part of the processor components, but also can be implemented in software, for example: to compare two numbers for equality we can subtract them and check if the result is zero.

# Answer
> 0 votes
I think the comments answer your question. To add some more context, it also depends on what you define as a computer. If you consider FPGAs and ASICs computers, then there are hard-coded circuits that can perform a variety of logic operations with transistors.

# Answer
> 0 votes
If “the only thing a computer can do is adding”, then a computer can do everything it does just by adding.

But by adding you can’t change a 1 to a 0. There are many things you can’t do just by adding.

What you do need to do anything a computer can do: Perform a NAND operation. Select memory. Produce electrical signals that can be detected outside. (Open to suggestions what else would be needed).

# Answer
> 0 votes
Presumption: We're talking about CPU.

At the lowest level, we have only logic gates. \[We may go even lower than that ;) \]. In that sense even `add` is a combination of logic operation, else CPUs have much more instructions besides addition.

For arithmetic: subtraction can be represented as `a + (-b)`, multiplication as series of addition and division as series of subtraction. How do we represent negative numbers that's another topic (r's complement).

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


# Question
Title: Extending Suurballe's disjoint path algorithm
I have implemented Suurballe's and Bhandari's algorithms into a project I am currently doing based on this:

http://www.macfreek.nl/memory/Disjoint\_Path\_Finding

And it seems to work really well. However, what I am doing now is having a start and end node, from which the disjoint paths are calculated.

The extension is, that I now wish to be able to use different start and end nodes for each path, or just one of them. If I just use the current algorithm it will indeed find two disjoint paths, however, if one of the end or start nodes are a part of the shortest route this will be included in the Suurballe algorithm for example - which it obviously shouldn't.

My question is: How do I do this extension? Do I just delete the start and end nodes in the Suurballe algorithm, or do I need to take something else into account?

# Answer
> 1 votes
**Caveat**

The procedure suggested here only works if you *either* have multiple start or multiple terminal nodes. As @D.W. has pointed out in the comments, if you have multiple end points of both kinds, the following idea does not ascertain that the right nodes be paired when constructing the paths.

**Answer**

If you have $k$ paths with pairwise different start or end nodes $\\{s\_i\\} \_{(i=1...k)}$ or $\\{t\_i\\} \_{(i=1...k)}$, resp. , add to the graph a synthetic start node $s$ or a synthetic end node $t$ and edges between the synthetic and the original start/end nodes: $\\{(s, s\_i)¦i=1...k\\}$ or $\\{(t\_i, t)¦i=1...k\\}$, each of the new edges having weight 0.

Then apply Suurballe's algorithm with pairs of start/end nodes $(s, t\_0)$, or $(s\_0, t)$, with $s\_0$ or $t\_0$, resp., being the end point shared between paths.

There are exactly $k$ incident edges to $s$ ($t$), so all original start / end nodes will be located on exactly one of the $k$ disjoint result paths.

If you have a start or end node where multiple paths (say $m(x\_i)$ for node $x\_i$) should start or end, clone that node and it's linkage with the rest of the graph $m(x\_i)-1$ times, use the new nodes as additional start/end nodes and follow through with the above construction.

From your problem description, you want to compute node-disjoint paths. Then no complication arises from nodes subject to cloning which are adjacent in the original graph: in linking the set of clones you only need to consider the original nodes, as the edge between the original two nodes will not be part of any path in the (node-)disjoint solution.

# Answer
> 0 votes
You already know the Suurballe algorithm that works for paths with same source and same destination vertices. So to solve your problem, you can just add a dummy vertex S to your graph and connect Start node of path1 and start node of path2 to S with edge weight 0. Add a dummy vertex E to your graph and connect End node of path1 and End node of path2 to S with edge weight 0. Now you can run suurballe algorithm to compute disjoint paths from S to E. After you get the paths, remove dummy vertices S and E. Now you have got your desired output.

---
Tags: algorithms
---


# Question
Title: Why does Calibration of NN not lead to higher accuracy?
I have a question about the use of calibration in neural networks and its relation to accuracy. In Guo et al. it says: "Because the parameter T does not change the maximum of the softmax function, the class prediction remains unchanged. **In other words, temperature scaling does not affect the model’s accuracy**."

This makes sense to me, but then I don't understand why it is used as a method for uncertainty estimation. Suppose we use a softmax function to determine our probabilities, which is known to be bad to measure uncertainty. Now, if we use temperature scaling or something similar for calibration, do the probabilities calculated with the softmax function become true confidence measures? If this were the case, I don't see why this would be necessary, since the accuracy of the model should not be affected by the calibration.

I think I misunderstood something in the procedure and would be very glad if someone could help me!

# Answer
It doesn't change the model's prediction (which class it predicts), but it *does* change the model's confidence in its prediction (the value of the corresponding softmax output). The point of uncertain estimation is to make this confidence reflect the degree of certainty we should have in the model's prediction.

There is no standard definition of "true confidence measure". The outputs can be viewed as confidences. We can then assess how well calibrated they are. Empirically, temperature scaling typically helps improve how well calibrated these outputs are.
> 1 votes

---
Tags: neural-networks
---


# Question
Title: Finding the loop invariant for Array Reversal
I've been assigned to find the loop invariant for the following code:

```
i=0;
j=n-1;
while(i < n/2){
    l = A[i];
    r = A[j];
    A[j] = l;
    A[i] = r;
    j = j-1;
    i = i+1;
}

```

I understand the code function (reverses array), the guard (`i < n/2`), and I can find different invariants (e.g. `i+j = n-1`), but I'm stuck finding anything useful that relates the precondition:

```
A[0], A[1] ... A[n-2], A[n-1]

```

to the postcondition:

```
A[n-1], A[n-2] ... A[1], A[0]

```

Can anyone help with this problem, or even generally how to find useful invariants for loops that operate on arrays?

# Answer
> 2 votes
The invariant will express that we have performed a partial reversal, i.e. the array zones `A[0..i[` and `A[n-i..n[` have been swapped the intended way, while the middle is unchanged.

So, if you denote the *initial* content of the array as `Z`, the invariant is like

```
Forall k: k < i => A[k] = Z[n-k] and n/2 > k ≥ i => A[k] = Z[k]

```

(Caution: off-by-one errors are possible, I didn't check.)

---
Tags: correctness-proof, first-order-logic, loop-invariants
---


title: Time complexity of a 2-heap question

text:
# Question
Title: Time complexity of a 2-heap question
The problem statement is pretty straightforward: given an array of integers and a window size, return an array of doubles of the median of each window.

$arr = 1, 3, 5, 10, 6, 9, 2$ and $k = 3$ would yield a result of $3, 5, 6, 9, 6$.

Using std::priority\_queue (in C++) for the heap implementation, there's a **minHeap** and **maxHeap**. In a single iteration, insert the value entering our window in the correct heap, rebalance as necessary, add the median to the result (if the window is big enough), then remove the value which is leaving the window from whatever heap it's in: This could require moving all but 1 heap element to the other heap, then moving them back.

The lesson I saw this on actually inherits from priority queue and implements remove functionality: Linear search \[O(k)\], then removes the item \[O(log k)\]. It claims O(n * k) complexity as at each iteration the insertion is O(log k) and the search to remove is O(k). I assume in an interview extending a heap beyond it's traditional form is not only unnecessary but probably frowned upon.

I'm curious of the complexity at which the version w/o the direct removal would run. The O(n) part is obvious but the sub operations not as clear to me. A heap will generally have k/2 items in it. In the worst case you delete \[O(log k)\] and then insert \[O(1)\] each one. My mind is telling me O(n * k log k) but I wouldn't bet my house on it.

For the record: Not looking for an optimal solution - just the runtime of this one.

**Insertion Algorithm:** We accept an integer `n` as input.

1. If `n` is smaller than the top element of `maxHeap`, push it on `maxHeap` and go to step 3.
2. Push `n` on `minHeap`.
3. If `maxHeap`'s size is 2 or more than `minHeap`'s size, move the top element of `maxHeap` to `minHeap` and go to step 5.
4. If `minHeap`'s size exceeds `maxHeap`'s size, move the top element of `minHeap` to `maxHeap`.
5. Stop the algorithm.

**Obtaining The Median:**

1. If sizes of `minHeap` and `maxHeap` are the same, then return the arithmetic mean of their top elements and go to step 4.
2. If `maxHeap`'s size exceeds `minHeap`'s size, return the top element of `maxHeap` and go to step 4.
3. If `minHeap`'s size exceeds `maxHeap`, return the top element of `minHeap`.
4. Stop the algorithm.

**Removal Algorithm:** We accept an integer `n` as input.

1. If `num` is not greater than the top element of `maxHeap`, remove the current top element from `maxHeap` and insert it to `minHeap`, until `n` becomes the new top element of `maxHeap`. Else skip to step 4.
2. Remove the top element of `maxHeap`.
3. Remove the current top element of `minHeap` and insert it to `maxHeap`, until the sizes of `minHeap` and `maxHeap` will differ by no more than 1. Go to step 7.
4. Remove the current top element from `minHeap` and insert it to `maxHeap`, until `n` becomes the new top element of `minHeap`.
5. Remove the top element of `minHeap`.
6. Remove the current top element of `maxHeap` and insert it to `minHeap`, until the sizes of `minHeap` and `maxHeap` will differ by no more than 1.
7. Stop the algorithm.

**Finding Sliding Window Median:** We accept an array of integers `arr`, and an integer `k` as input.

1. Set `left` to $0$. Set `right` to $0$. Set `result` to $0$.
2. Insert (by using **Insertion Algorithm** above) the element of `arr` with index `right`.
3. If `k-1` is not greater than `right`, add median (found by **Obtaining The Median** algorithm above) to `result`. Else go to step 6.
4. Remove the element of `arr` with index `left`.
5. Add $1$ to `left`.
6. If `right` is less than the greatest index of `arr`, add $1$ to `right` and go to step 2.
7. Return the current value of `result` and stop the algorithm.

This last algorithm is where the mystery is. Worst case we have is to remove a number at the bottom of a $k/2$ sized heap. Would that be $\log k$ for $k/2$ operations then $O(1)$ for $k/2-1$ operations?

# Answer
Store the window in a self-balancing binary search tree, augmented in the standard way for computing item ranks (each node is augmented with the number of values stored in the subtree rooted at that node).

Each time a value arrives, add it to the tree, remove the one leaving the window, compute the median, and output it. Each of those operations can be done in $O(\log k)$ time. (For instance, insert and delete take $O(\log k)$ time, because it is a self-balancing binary tree; finding the median of the values in the tree can be done in $O(\log k)$ time using the augmented rank information.) Therefore, the total running time to process $n$ items will be $O(n \log k)$.
> 0 votes

# Answer
It’s easier to figure out if k is large, say k = 100.

You start by creating two heaps with 50 elements each, one with the 50 smallest of the first 100 numbers with fast access to the largest one, and one with the 50 largest, with fast access to the smallest one. The median of all 100 items can be found in O(1).

Now you move the window by one position. Element #0 is removed from its heap, element #100 is added to its heap. Then if you are lucky you have two heaps of size 50, if you are unlucky you have one heap of size 49 and one of size 51, and move either the largest of the small numbers, or the smallest of the large numbers, from its heap to the other heap.

For odd k both heaps need a size that is different by one and the heap with the largest number of elements contains the median. For example k=99, your two heaps must contain 49 and 50 elements. If you are unlucky moving the window results in 48 and 51 items and you move one item over.

Since accessing the second element is also quite fast, you can allow a slightly larger size difference of the heaps which may save some insertions.

And you need O(n log k) operations.

PS. Figured out that you can’t delete an arbitrary item from a heap. So you need to keep track of where your k elements in the window are in the heap, but that doesn’t make things much harder. Still O(n log k).
> 0 votes

---
Tags: algorithms, time-complexity, heaps
---


# Question
Title: Fixing the min-heap after subtracting a value from a couple random elements in it
> Given a Min-Heap with $n$ elements.
> Assume that we choose $\lceil \log\_2n \rceil$ elements from the heap (not in any specific order/index's), and we subtract a value $k\>0$ from all of their keys.
> Suggest an algorithm to fix the min-heap that runs in $O((\log\_2n)^2)$.

**My thoughts:**
In a min heap the key value of children nodes is bigger or equal to the parent.
Which means when we subtract a positive value from a key of a node, we may have a child with a key value less than it's parent and we need to switch between them.
My main problem is how to locate those nodes that I need to fix their position in the heap? This seems somehow impossible to me without going through all the nodes of the heap which will cost $O(n)$.
I would appreciate any help and hints in how to locate these nodes, since when I locate them I could just do the DecreaseKey function in a min-heap which brings the child up to it's correct place (keeps switching between the child and parent until we get a child key value greater or equal than the parent or we reach the root of the heap).
Thanks in advance.

# Answer
> 2 votes
First you remove the O(log n) items from the heap. You can do this by finding their indices then removing them starting with the highest index. Make sure that your removal algorithm doesn’t move any items at lower indices.

Then you modify the keys any way you like and move them back into the heap. Operations on the heap run in O(log n), and there are O(log n) of them. You should have code for adding or removing an item, so you don’t need to care about the details.

---
Tags: data-structures, heaps
---


# Question
Title: Where should I start for making an AI Bot that processes on screen prompts
I would love to learn visual AI and what better way than creating a bot to play offline games. The problem is with no experience in AI other than Azure through my college, I have no experience. Does anyone have resources that could aid in my learning or any tips for getting started? All will be appreciated.

# Answer
> 0 votes
More generally you should read about deep reinforcement learning.

---
Tags: machine-learning, artificial-intelligence
---


# Question
Title: Decidability of intersection of regular and decidable languages
I'm wondering if a language (A) is a decidable language and language (B) is a regular language, is the intersection between A and B regular?

# Answer
I don't quite understand what you mean by if (A) is decidable then it is a language in R, if you mean that A is regular and B is regular then the intersection of two regular languages is still regular.

However, if you mean that A is decidable and it isn't certainly regular then no. take for example:

$$A=\\{a^nb^nc^n\ |\ n\geq0\\}$$ $$B=\Sigma^\*$$

Note that A is a decidable language using a Turing machine, I assume you know this already, otherwise, you can simply achieve a proof for it, it's a well-known example for a language that is not context-free. Moreover, B is a regular language and the intersection between both is: $$A\cap B=\\{a^nb^nc^n\ |\ n\geq0\\}$$ which is still not a regular language (note that since it's not a context-free language then it's certainly not a regular language).
> 1 votes

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


# Question
Title: Solving efficiently NP problems with infinite precision
I heard a few times that if we allow computations with infinite precision, we could have unrealistic powers of computation up to the point of solving NP problems efficiently.

Is it true? If yes:

* what is the model of computations used to define infinitely precise arithmetic? Like do we need to assume that accessing to the n-th digit of a number can be done in constant time and that operations between two numbers is done in constant time? (Otherwise I guess it would be possible to efficiently simulate this in classical computer using lazy arithmetic.)
* given this model of computation, how would you use it to break NP complete problems?
* is it possible to approximate physically such model, for instance in an analogic way considering the (unrealistic) assumption that there is no noise?

# Answer
One such model of computation is explained in this note. In this model of computation, we are allowed to perform arithmetic operations, logical operations, and comparisons on integers of arbitrary precision. We encode Boolean functions $f\colon \\{0,1\\}^n \to \\{0,1\\}$ as bitstrings of length $2^n$, thinking of the index of a bit as encoding a truth assignment. Explicitly, if $i = i\_{n-1} 2^{n-1} + \cdots + i\_0$, where $i\_0,\ldots,i\_{n-1} \in \\{0,1\\}$, then the $i$'th bit of the bitstring (where the $0$th bit is the LSB) is $f(i\_0,\ldots,i\_{n-1})$.

Given functions $f,g$, we can compute $f \land g, f \lor g, \lnot f$ using bitwise operations. The projection function $(x\_1,\ldots,x\_n) \mapsto x\_i$ corresponds to the bitstring $$ 2^{2^{i-1}} \prod\_{I \neq i-1} (1 + 2^{2^I}) $$ which can be computed efficiently (in this model) using repeated squaring.

Given a Boolean formula (or even a Boolean circuit) on $n$ inputs, we can efficiently compute the bitstring corresponding to the function computed by the formula. Comparing the result to zero, we can solve SAT.

In fact, we can even solve QBF. Roughly speaking, to implement a quantifier, we decompose the bitstring into two halves, and then either AND them (in the case of $\forall$) or OR them (in the case of $\exists$). This is possible if we also allow the shift operation.
> 3 votes

---
Tags: np-complete, computation-models
---


# Question
Title: Complexity of the (Complete/Assign) 3-SAT problem?
A *complete $k$-CNF formula* on $n$ variables $(k\le n)$ is a $k$-CNF formula which contains all clauses of width $k$ or lower it implies.

Let us define the (Complete/Assign) 3-SAT problem: Given $F$, a complete 3-CNF formula on $n$ variables and $I$, a partial assignment of $l$ literals among $n$ (where $l\le n$). Let $F\_I$ be the induced formula obtained by applying $I$ to $F$: Any clause that contains a literal which evaluates to *true* under $I$ is deleted from the formula, and any literals that evaluate to *false* under $I$ are deleted from all clauses. Is $F\_I$ satisfiable?

Even if deciding the satisfiability of a complete $k$-CNF formula is clearly a tractable problem — since a $k$-CNF formula is satisfiable as long as it does not contain the empty clause — I guess that this problem is NP-Complete, but I haven't succeeded in finding a reduction to prove it.

**Question:** What is the complexity of the (Complete/Assign) 3-SAT problem?

(The question is different as in the post Complexity of the Complete (3,2) SAT problem?, which is about mixing a complete 3-CNF with any kind of 2-CNF formula.)

# Answer
Let $C\_1 \lor \cdots \lor C\_m$ be a 3CNF. We replace the clause $C\_i = \ell\_1 \lor \ell\_2 \lor \ell\_3$ with the clause $C'\_i = \ell\_1^{(i)} \lor \ell\_2^{(i)} \lor \ell\_3^{(i)}$, that is, with a clause which contains three literals, appearing only in that clause. For every variable $x\_i$ and for every two clauses $C\_j,C\_k$ it appears in, we add a gadget that encodes, in a way, "$x\_i^{(j)} = x\_i^{(k)}$": $$ \bar{x}\_i^{(j)} \lor z\_1^{(i,j,k)} \lor w\_1^{(i,j,k)} \\ \bar{z}\_1^{(i,j,k)} \lor z\_2^{(i,j,k)} \lor w\_2^{(i,j,k)} \\ \bar{z}\_2^{(i,j,k)} \lor z\_3^{(i,j,k)} \lor w\_3^{(i,j,k)} \\ \bar{z}\_3^{(i,j,k)} \lor x\_i^{(k)} \lor w\_4^{(i,j,k)} \\ \bar{x}\_i^{(k)} \lor z\_4^{(i,j,k)} \lor w\_5^{(i,j,k)} \\ \bar{z}\_4^{(i,j,k)} \lor z\_5^{(i,j,k)} \lor w\_6^{(i,j,k)} \\ \bar{z}\_5^{(i,j,k)} \lor z\_6^{(i,j,k)} \lor w\_7^{(i,j,k)} \\ \bar{z}\_6^{(i,j,k)} \lor x\_i^{(j)} \lor w\_8^{(i,j,k)} $$

The resulting 3CNF is complete, as we show below. If we assign zero to all $w$ variables, then we get a 3CNF which is logically equivalent to the original one. This shows that your problem is NP-hard.

To show that the 3CNF is complete, we need to show that it is possible to extend any truth assignment of up to three variables to a satisfying assignment, unless this truth assignment falsifies a clause.

Let $\alpha$ be a truth assignment of up to three variables which doesn't falsify any clause. We can complete it to a truth assignment which satisfies the clauses $C'\_1,\ldots,C'\_m$. It remains to show that we can satisfy each equality gadget.

Out of $w\_1^{(i,j,k)},\ldots,w\_4^{(i,j,k)}$, at least one is not set by $\alpha$, and we set it to $1$. This allows us to satisfy the first half of the gadget; this requires some case analysis, but the idea is that this half of the gadget expresses $$ x\_i^{(j)} \stackrel {w\_1^{(i,j,k)}} \Longrightarrow z\_1^{(i,j,k)} \stackrel {w\_2^{(i,j,k)}} \Longrightarrow z\_2^{(i,j,k)} \stackrel {w\_3^{(i,j,k)}} \Longrightarrow z\_3^{(i,j,k)} \stackrel {w\_4^{(i,j,k)}} \Longrightarrow x\_i^{(k)}, $$ and substituting $w\_t^{(i,j,k)} = 1$ breaks the implication cycle. We can similarly satisfy the second half of the gadget, which expresses $$ x\_i^{(k)} \stackrel {w\_5^{(i,j,k)}} \Longrightarrow z\_4^{(i,j,k)} \stackrel {w\_6^{(i,j,k)}} \Longrightarrow z\_5^{(i,j,k)} \stackrel {w\_7^{(i,j,k)}} \Longrightarrow z\_6^{(i,j,k)} \stackrel {w\_8^{(i,j,k)}} \Longrightarrow x\_i^{(j)}. $$
> 4 votes

---
Tags: complexity-theory, np-complete, satisfiability, decision-problem, complexity-classes
---


title: Numerical "Biases" Computation Issue

text:
# Question
Title: Numerical "Biases" Computation Issue
I discovered this issue last night & can't make sense of it. Numerical biases programming sounds ridiculous but the code is the same, only changing the denominator from 4 to 5 and changing the corresponding values and outputs. Why does the 4 denominator work but the 5 doesn't?

#include using namespace std;

double main () { double input;

double value;

int round;

double function;

cout \<\< "Program will calculate remandor from an INTEGER ÷ 4" \<\< endl;

cout \<\< "Enter the INTEGER value: "; cin \>\> input;

value = (input/4);

round = (input/4);

function = (value - round);

if (function==0.0) {cout \<\< ".0";}

if (function==0.25) {cout \<\< ".25";}

if (function==0.5) {cout \<\< ".5";}

if (function==0.75) {cout \<\< ".75";}

return 0; }

#include using namespace std;

double main () { double input;

double value;

int round;

double function;

cout \<\< "Program will calculate remandor from an INTEGER ÷ 5" \<\< endl;

cout \<\< "Enter the INTEGER value: "; cin \>\> input;

value = (input/5);

round = (input/5);

function = (value - round);

if (function==0.0) {cout \<\< ".0";}

if (function==0.2) {cout \<\< ".2";}

if (function==0.4) {cout \<\< ".4";}

if (function==0.6) {cout \<\< ".6";}

if (function==0.8) {cout \<\< ".8";}

return 0; }

# Answer
> 0 votes
**This is an answer to "a solution for remained divided by 5 of a given integer".**

The problem is not with `output= input/5 - int(input/5)`, which is a correct way to get the fractional part of a number (alternatively, `input/5 - floor(input/5)`). The problem is with `output == 0.2`. Comparisons for exact equality of floating-point numbers usually does not work. You need to introduce a tolerance, which is related to the accuracy of the representation. In this case, you should use something like `abs(output - 0.2) ≤ 0.2 * epsilon`, where `epsilon` is a small multiple of the relative machine precision (about `2^-52`).

---

For more informative experiments, you'd better observe the quotient

$$\frac{\text{computed value} - \text{ideal value}}{\text{ideal value}}$$

# Answer
> -1 votes
Floating-point numbers are stored in the following form (forgetting about some niceties): $$ 1.b\_1 \ldots b\_m \times 2^x, $$ where $b\_1,\ldots,b\_m$ are bits, and $x$ is an integer belonging to some bounded range. (You need special encodings to store zero, infinities, NaNs, and so on.)

Dividing a floating-point number by 4 is exact, since it just involves decreasing $x$ by 2 (unless you get underflow, but this won't happen in your case). In contrast, dividing by 5 isn't exact, since 5 isn't a power of 2. Similarly, whereas 0.25 can be stored exactly in floating-point, 0.2 cannot. The outcome is the kind of behavior that you see.

---
Tags: computer-algebra
---


# Question
Title: Computer networks - Can there be an out of order frames in a noiseless channel?
In a noiseless channel can frames in the 2 layer of OSI model(Data link layer) reach to the destination out of order?

\*I am studying from Computer networks 5 Edition of Andrew S. Tanenbaum

# Answer
> 1 votes
Yes this is possible. For instance when the protocol sends several frames without waiting for the individual acknowledgements: if one of the frames gets lost it will be retransmitted out of order.

# Answer
> 0 votes
It depends on the channel and the assumptions you are making. There may well be some communication channels where messages can be re-ordered but will not be dropped or lost or modified in transit.

# Answer
> 0 votes
A channel is an abstraction. And an asbstraction can only do what it is assumed to be doing. When describing networks, we usually assume channel capabilities related to in-order delivery, which are completely independent of being noisy or not.

If you plug in a singe cable between two single core devices, then probably no reordering can happen. However data link layer is more complicated than this.

* Ethernet is a network with bridges, and as such, frames can be delivered out of order, e.g., when topology changes. Note also, that if packets are dropped in bridges during topology changes, it is not called noise.
* there are technologies (i think link bonding) where a single link consists of several physical wires, and since that packets that are sent over different wires can be reordered
* on a PC with multicore processors, packets can be reordered if you process one packet by one core and one by another, and there is no guarantee that order is preserved

---
Tags: computer-networks
---


# Question
Title: What is the difference between problem solving and theorem proving?Is mathematics problem solving or theorem proving?
Some books of permutation and combinations ,theorems are to proved while in some book problem is to be solved using logic.

# Answer
In school, your problems are often pre-cooked exercises in which you are supposed to apply theorems or maybe prove them.

In the real world, you may encounter problems that you have no idea how to find adequate mathematical representations for, or whether such representations exist at all. Mathematical representations are abstractions: they simplify by leaving out detail, so you need to be able to simplify such that some important essence you want to reason about is captured without oversimplifying and distorting what is really going on. This can be more challenging than the subsequent work of applying or proving theorems in the representation you've chosen.
> 1 votes

# Answer
Problem solving is the art of finding the solution(s) from a problem statement. Theorem proving is the art of showing that a known solution is indisputably correct.

But if the given problem is to craft a proof, then theorem proving is an instance of problem solving. :-)
> 0 votes

---
Tags: discrete-mathematics
---


title: Sum of average of all subarrays

text:
# Question
Title: Sum of average of all subarrays
Suppose there is an integer array $a\_1,a\_2,...,a\_n$. Calculate the sum of average of all subarrays. For example, the sum of average of all subarrays of array $\[1,3,5\]$ is $1+3+5+\frac{1+3}{2}+\frac{3+5}{2}+\frac{1+3+5}{3} = 18$

I'm wondering does it exist an $O(n)$ algorithm?

# Answer
**Hint:**

This sum is a linear combination of the array elements, with varying weights .

In the case of four elements, $$a+b+c+d+\frac{a+b}2+\frac{b+c}2+\frac{c+d}2+\frac{a+b+c}3+\frac{b+c+d}3+\frac{a+b+c+d}4$$

$$a:1+\frac12+\frac13+\frac14$$

$$b:1+\frac22+\frac23+\frac14$$

and symmetrically for $c,d$.

If precomputing these coefficients for the required $n$ is allowed, the solution is indeed $O(n)$. Otherwise, the pattern is a sum of fractions with denominators that are the naturals and the numerators follow a triangle wave. I guess that these can be computed efficiently by computing the prefix sum of the inverses of the naturals, then accumulating the terms incrementally, in total time $O(n)$.
> 4 votes

# Answer
The idea is provided by Yves Daoust.

Here is the C++ code I implemented just now. The input format is like

```
n
a_1 a_2 ... a_n

```

The modular number is $10^9+7$.

```
#include<bits/stdc++.h>
using namespace std;
constexpr int mod = 1e9+7;
void solve(){
    int n;
    cin>>n;
    vector<int> a(n+1);
    vector<int> inv(n+1);
    for(int i=1;i<=n;++i) cin>>a[i];
    inv[1] = 1;
    for(int i=2;i<=n;++i) // linearly calculate mod inverse of [1,2,...,n]
        inv[i] = 1LL * (mod-mod/i)*inv[mod%i]%mod;
    for(int i=2;i<=n;++i) // prefix of mod inverse of [1,2,...,n]
        inv[i] = (1LL * inv[i] + inv[i-1])%mod;
    int ans = 0;
    int tot = 0;
    int r = n, l = 0;
    for(int i=1;i<=(n+1)/2;++i){
        tot = (1LL * tot + inv[r--] - inv[l++] + mod) % mod;
        ans = (1LL * ans + 1LL * a[i] * tot ) % mod;
    }
    if(n%2==0) ans = (1LL * ans + 1LL * a[n/2+1] * tot) % mod;
    for(int i=(n+1)/2+1+(n%2==0);i<=n;++i){
        tot = (1LL * tot - inv[++r] + inv[--l] + mod) % mod;
        ans = (1LL * ans + 1LL * a[i] * tot) % mod;
    }
    cout<<ans<<'\n';
}

```
> 0 votes

---
Tags: algorithms, discrete-mathematics
---


# Question
Title: What is the best way to compare two images for similarity if the brightness of the second image was changed?
I calculate similarity percent between two images. Another image is the same with changed brightness. I've already tried comparing by pixel (euclidean distance for grayscale and 0/1 values), comparing by HSV. I've tried also normalisation (pixel brightness-mean brightness). The results were quite good (80-90%), but the similarity rate with changed image was lower than similarity between images with compeletely different tables, for example. Is there any simple approach to solve this problem? Or should I use neural networks?

# Answer
You can try multiplicative normalization (pixel brightness / mean brightness), or subtractive normalization *after transforming with a logarithmic LUT*.
> 1 votes

# Answer
Have a look at the h.264 spec. It’s for encoding movies, so it does a lot of comparing similar images.

The model is that image2 = image1, translated, with some linear transformation of the pixels.
> 0 votes

---
Tags: computer-vision, image-processing, comparison, digital-image-processing
---


# Question
Title: Shortest path in a directed weighted graph
Suppose we have a directed, weighted graph, $G = (V, E, w)$, with non-negative weights. We define the weight of the shortest path different from the original definition.
The weight of a path with at most 5 edges (including 5) will be defined as usual, meaning the sum of the edges weights. The weight of a path with at least 6 edges will be the sum of the edges weights multiplied by 2.
Propose and analyze an efficient algorithm (as you can), That given a graph $G$ and two vertices $u, v$, the algorithm will find the shortest path from $u$ to $v$, as we defined the paths weights. Describe in words why the algorithm works and analyze it's runtime.
My thought was to run first $BFS$ on the graph and for every edge that in a path with 6 or more edges, just multiply the edge weight by 2, and then run dijkstra, but I think it won't work. So then I was tending to do a brute force algorithm and find all the paths from $u$ to $v$ and then find the shortest one, but it is not efficient. So I'm stuck on an answer to this one and would glad for some help.

# Answer
> 1 votes
You can take this approach:
**Step one:**
Duplicate G's nodes 6 times to get a new directed graph with 6 levels $L\_1,...,L\_6.$
For $1\le i\le5$ and nodes $a,b: $ There will be an edge from $a \in L\_i$ to $ b \in L\_{i+1} $ if there was an edge from $a$ to $b$ in the original graph, and the weights will be same as the original graph.
From $L\_6$ there will be no way to move between the nodes, or to move to any other level.
In this way we can run an SP algorithm from node $u$ in $L\_1$ to find the shortest path to $v$ (in any level) with respect to $w$, and each path's length will be no longer than 5.
Assume that we got a shortest path $s\_1$ (if no path was found $s\_1 = \infty).$
**Step two:**
Create a new weight function $f(w)=2w$ for the original graph's weights and run Dijkstra's again on the original graph with the new weight function to get another shortest path $s\_2$ (again if no path was found $s\_2 = \infty).$
**Step Three:**
return $\min\\{s\_1,s\_2\\}.$
Time complexity is that of Dijkstra's since constructing the graph in step 1 takes linear time.

---
Tags: graphs, dijkstras-algorithm
---


# Question
Title: What is the simplest algorithm to compress a string?
I need to compress a string in my application but I am very limited in the operations I can perform. In particular, I cannot store data in any file and I cannot query any database. Also, I cannot call any library so I have to code my own data compression algorithm. What would be the simplest algorithm to achieve this goal? I could code the smaz algorithm myself but it does not seem to work very well with long strings.

# Answer
> 4 votes
If you need something reasonably effective but not very taxing to implement, I would recommend LZW.

LZW has several advantages, not the least of which is that it uses fixed-width codes (the width strictly increases as compression proceeds), rather than Huffman or arithmetic coding. It also does not require string searching through a sliding window, instead performing hash table or tree lookup per input character. This means that it requires significantly less code to implement than methods based on LZ77.

# Answer
> 3 votes
The simplest (besides "no compression at all") is RLE.

RLE is useless on many kinds of data, but better kinds of general-purpose compression require more complex algorithms.

# Answer
> 2 votes
My vote goes to LZP. It's hilariously simple.

It should be drastically simpler and faster than anything that uses trees in any capacity, such as Huffman coding, LZW or practically every compression algorithm that remotely tries to achieve better compression. Compression ratios aren't great however, works better on longer strings.

Here's a complete working implementation in C i adapted from here:

```
#include <stdio.h>

#define HASH_SIZE   (1 << 16)
#define HASH(h, x)  (h = (h << 4) ^ x)

void encode(unsigned char *input, unsigned int inputlen, unsigned char *output, unsigned int *outlen) {
    unsigned char buf[9], table[HASH_SIZE] = {0};
    unsigned short hash = 0;
    int mask, i, j, c, inpos = 0, outpos = 0;

    for (;;) {
        j = 1;
        mask = 0;
        for (i = 0; i < 8; i++) {
            if (inpos == inputlen) break;
            c = input[inpos++];
            if (c == table[hash]) {
                mask |= 1 << i;
            } else {
                table[hash] = c;
                buf[j++] = c;
            }
            HASH(hash, c);
        }
        if (i > 0) {
            buf[0] = mask;
            for (i=0;i<j;i++) { output[outpos++] = buf[i]; } // one-liner copy function
        }
        if (inpos == inputlen) break;
    }
    *outlen = outpos;
}

void decode(unsigned char *input, unsigned int inputlen, unsigned char *output, unsigned int *outlen) {
    unsigned char buf[8], table[HASH_SIZE] = {0};
    unsigned short hash = 0;
    int mask, i, j, c, inpos = 0, outpos = 0;

    for (;;) {
        j = 0;
        if (inpos == inputlen) break;
        mask = input[inpos++];
        for (i = 0; i < 8; i++) {
            if ((mask & (1 << i)) != 0) {
                c = table[hash];
            } else {
                if (inpos == inputlen) break;
                c = input[inpos++];
                table[hash] = c;
            }
            buf[j++] = c;
            HASH(hash, c);
        }
        if (j > 0) {
            for (i=0;i<j;i++) { output[outpos++] = buf[i]; } // one-liner copy function
        }
    }
    *outlen = outpos;
}

int main(){
    unsigned int strlen = 82, outlen;
    unsigned char str[1024] = "Fuzzy Wuzzy was a bear. Fuzzy Wuzzy had no hair. Fuzzy Wuzzy wasn't fuzzy, was he?";
    unsigned char out[1024];

    printf("original length: %d\n", strlen);
    for (int i=0;i<strlen;i++) { printf("%c", str[i]); }
    printf("\n\n");

    encode(str, strlen, out, &outlen);

    printf("encoded length: %d\n", outlen);
    for (int i=0;i<outlen;i++) { printf("%d ", out[i]); }
    printf("\n\n");

    decode(out, outlen, str, &strlen);

    printf("decoded length: %d\n", strlen);
    for (int i=0;i<strlen;i++) { printf("%c", str[i]); }
    printf("\n\n");
}

```

---
Tags: algorithms, strings, data-compression
---


title: FPT algorithm for dominating set

text:
# Question
Title: FPT algorithm for dominating set
An instance of the Dominating Set problem is given by an undirected graph $G = (V, E)$ and an integer $k$; it is a ‘yes’-instance if there is a subset of vertices $S ⊆ V$ with $|S| ≤ k$ such that for each $v ∈ V$ we have $v ∈ S$ or $u ∈ S$ for some ${u, v} ∈ E$.

I'm trying to show that if the degree of each vertex of $G$ is at most 3 then Dominating Set is in FPT with respect to $k$.

I thought of maybe creating a bounded search tree algorithm for this, where if all nodes have degree \<= 2, it can trivially be solved in $O(|E|)$ time. Otherwise consider a node $v ∈ V$ with degree 3. Either it's in the dominating set, or one of its neighbours is which results in a $O(4^k |E|)$ algorithm. I think there should be something better (maybe using kernels?).

# Answer
See the FPT algorithm in Linear Time Algorithms for Finding a Dominating Set of Fixed Size in Degenerated Graphs. Since the proof applies for $k$-degenerate graphs, it also applies for graphs whose maximum degree is $k$.
> 2 votes

---
Tags: graphs
---


# Question
Title: Determining whether formula is only satisfied by the all-true assignment
I'm trying to prove that $\mathrm{HALF}\text-\mathrm{FALSE}$ is NP-hard, where $\mathrm{HALF}\text-\mathrm{FALSE}$ is the following problem:

> given a boolean formula $\phi(x\_1,\dots,x\_n)$, is there a satisfying assignament in which exactly $n/2$ variables have value false?

Now, i got the problem down if it was like this:

> given a boolean formula $\phi(x\_1,\dots,x\_n)$, is there a satisfying assignament in which at least $n/2$ variables have value false?

the reduction for this modified problem from $\mathrm{SAT}$ to (let's call it $\mathrm{HALF}\text-\mathrm{FALSE}'$) i think is the following: $$f(\phi(x\_1,\dots,x\_n))=\phi(x\_1,\dots,x\_n)\bigwedge\_{i=1}^{n}y\_i'$$

it's correct because $\phi \in SAT \Leftrightarrow f(\phi) \in \mathrm{HALF}\text-\mathrm{FALSE}'$ and $f$ is computable in polynomial time.

Back to the original problem, my thoughts were something like this, if i can transform first the original formula in a formula that is satiasfied only by all true assignament iff the original formula is satisfied, then do the same thing as before. So something like this: $$f(\phi(x\_1,\dots,x\_n))=\psi(x\_1,\dots,x\_n)\bigwedge\_{i=1}^{n}y\_i'$$ where $\psi(x\_1,\dots,x\_n)$ has only all true assignament iff $\phi(x\_1,\dots,x\_n)$ is satisfied. But i don't know how to construct $\psi$.

# Answer
> 1 votes
Convert your formula into 3-CNF (not strictly necessary, I think). Duplicate every clause in the formula with new variables and every literal inverted. Then if there exists a satisfying assignment in the original formula one exists in the new one and exactly half of the variables are false. Clearly, if this HALF-FALSE problem is solvable in p-time then so is SAT.

Suppose your 3-CNF formula is $(x\_1+x\_2'+x\_3')(x\_1'+x\_2+x\_3)(x\_1'+x\_2'+x\_3)$. Rewrite it so that it becomes: $$ (x\_1+x\_2'+x\_3')(x\_1'+x\_2+x\_3)(x\_1'+x\_2'+x\_3)\land \\ (y\_1'+y\_2+y\_3)(y\_1+y\_2'+y\_3')(y\_1+y\_2+y\_3') $$

---
Tags: reductions, np-hard
---