title: How does this recursive algorithm work?

text:
# Question
Title: How does this recursive algorithm work?
One question from the Grokking Algorithms book:

Implement a `max([]int)` function, returning the biggest element in the array.

Here's my solution in Golang (adapted from the Python solution in the book):

```
func maxNumber(arr []int) (r int) {
    // base case
    if len(arr) == 2 {
        if arr[0] > arr[1] {
            return arr[0]
        } else {
            return arr[1]
        }
    }

    // recursive case
    subMax := maxNumber(arr[1:])

    if arr[0] > subMax {
        fmt.Println("arr[0] > subMax")
        return arr[0]
    } else {
        fmt.Println("arr[0] < subMax")
        return subMax
    }
}

```

It works, but I can wrap my head around it. How is the third block called if every time `maxNumber(arr[1:])` is called it executes the function again, passing the array with one last element? If so, at some point in time it will hit the first block (base case) and return or the first element or the second.

I know the function works, but I'm missing the how.

Could someone help me around, explain like I'm 5 styles haha

Thanks!

# Answer
> 1 votes
The base case works because, if the array contains only 2 elements, it compares them and return the biggest. Starting from this assumption, the recursive call to the function *maxNumber* compare the maxnumber of the precedent call to the next element in the array. when the list has been read all the way to the end, the algorithm will return the max number of the whole list.

---
Tags: recursion
---


# Question
Title: vector hashing function having collisions for permutations
let's consider vectors in space dim=3 and values {0,1,2,...,99} on each dimension I would like to create `hash` function but with special trait: collisions only for permutations on input

$\forall\_{x, y \in N^3} (y = permutation(x) \<=\> hash(x) == hash(y))$

is it even possible but without sorting? if so please attach example :)

* one idea is to sort these values and then just create a key like $x\_1\*10e4 + x\_2\*10e2 + x\_3$, for higher dimensions sorting would slow down solving a bit, so is it possible without sorting?

# Answer
With your limitations, you put all values into about 166,000 or so buckets, so yes, easily. If x, y, z are arbitrarily large, of course not.
> 1 votes

---
Tags: hash, one-way-functions
---


# Question
Title: How to answer multiple queries efficiently?
I am given a $N$-length integer array. For each integer, I am given 4 values:

$$\[\mathit{left},\mathit{right},t,\mathit{value}\]$$ $$1\leq \mathit{left},\mathit{right},t\leq N$$

For each query, I have to find the sum of values which have $x$ in the range $\[\mathit{left},\mathit{right}\]$ and that satisfy $t\leq t\_1$.

Example query: $x=5$, $t\_1=4$.

So I have to find out sum of all the values satisfying $\mathit{left} \leq 5 \leq \mathit{right}$ and $t \leq 4$.

# Answer
When the value of $t\_1$ is not present you are just given weighted intervals from `left` to `right` with weight `value`, and you should ask questions of the form, what is the sum of the weights of intervals that contains `x`.

If we know all intervals/weights before hand this whole task is easy without any fancy data structure, just adding the beginning of the interval with weight `+value` and the end with weight `-value` and accumulate all such values. The answer will be constant in intervals and to find the value at $x$ you can binary search for the interval that contains $x$. Will not go deep into this solution since it will not allow us to solve the problem when $t\_1$ constraint is used again.

Assume we don't know all intervals before hand and we have a mix in of, add new interval, find sum of all intervals containing $x$. You can solve this problem using segment tree with lazy propagation to add a value on intervals fast, and query sum on points (actually with segment tree you can query in intervals but it isn't required here). Both queries are done in $O(log N)$ where $N$ is the number of intervals.

Let's call all given intervals in the input updates. To solve the problem with $t\_1$ back, sort all queries and updates by $t$ value. And process them in such order. When you are processing each query of type $(x, t\_1)$ only intervals with lower $t$ are present in the data structure, so we have an instance of the previous problem, ask for all intervals containing $x$, whenever you get an update, add it to the data structure.

This solution is offline, since you require to know all queries beforehand. This can be solved online using persistent segment trees. The overall complexity of the solution described here is $O((N+Q) log N)$.
> 1 votes

---
Tags: algorithms, arrays
---


# Question
Title: How to answer multiple queries for a tree?
I encountered an interesting problem based on tree-data-structure.

> We are given a tree which has *N* nodes, with *1≤N≤105*.
>
> Time starts from second 1 and it continues for *q* seconds.
>
> At each second, the value of each internal node is transferred to all of its child nodes. This happens with all the nodes, except leaf nodes.
>
> Sometimes, at a given time *p* (seconds), we are asked to return the current value of node *x*.

There is this *O(logN)* approach: just find the *p*th ancestor of the given node *x*, and output its value.

# A harder version of the same problem

> Sometimes, at a given time *p* (seconds), we are asked to return the current value of node *x*, **or** we are said to update the value of node *x* to *y*.

How to solve this problem for *q* queries (seconds) efficiently, where *1≤q≤105*.

## Example

### Input

*N*=5, *q*=8

Edges of the tree:-

```
4 3
3 1
5 2
1 2

```

Values of nodes 1 to 5:-

```
1 10 4 9 4

```

Queries:-

* 1st second:- `Add(1,6)`. Add the value 6 to node 1.
* 2nd second:- What is the current value of node 3? `(?,3)`
* 3rd second:- `Add(3,5)`
* 4th second:- `(?,3)`
* 5th second:- `Add(2,2)`
* 6th second:- `Add(5,10)`
* 7th second:- `(?,5)`
* 8th second:- `(?,4)`

### Expected Output

* 6
* 0
* 33
* 25

### Explanation

* 1st second: 6,1,1,13,14 (Values of all nodes)
* 2nd second: 0,6,6,14,15
* 3rd second: 0,0,5,20,21
* 4th second: 0,0,0,25,21
* 5th second: 0,2,0,25,21
* 6th second: 0,0,0,25,33
* 7th second: 0,0,0,25,33
* 8th second: 0,0,0,25,33

# Answer
> 2 votes
For this problem I recommend to solve first for trees with simpler structures that can be generalized afterwards with data structures that run on top of trees (there are plenty of them).

Let's build an idea of what are the dynamics of the problem before jumping to the answer. We have the array `A = [N0, N1, N2, N3]`. An let's say after each second numbers at each position moves one step to the right. And in some place one number might change (in cases of queries). The initial array after the first second will look like `A = [N0, N0, N1, N2]`. If we are asked to change the value at position $2$ (indexed in base $0$) with value `Q0` at the end of the first step, then the array will look like `A = [N0, N0, Q0, N2]`. After the following step the array will look like `A = [N0, N0, N0, Q0]`. We should be able to answer queries of the form: What is the value of position $i$ at this moment?

If there is a value at position $i$ at time $t$ we know this value will be at position $i+\delta$ at time $t+\delta$, unless it is overridden by some update. In the case it was overridden it must be the case that it happened on a position to the right of position $i$.

Supposed we are asked for the value at position $p$ at time $t$. Turning previous equations backwards, we are looking for the right-most position to the left of $p$ (let's call it $o$ from origin) such that an update originated there at time $t\_o = t - (p - o)$. We say that for all positions in the array there was a simultaneous update at the beginning with initial values. Rewrite previous equation as: $t\_o - o = t - p$. Notice that the problem is simpler now, for every update in position $o$ at time $t\_o$ with value $v$ we store at this position the value $(t\_o - o, v)$. For every query of the form ($p$, $t$) we should ask for the right-most position to the left of $p$ such that the first element is $t - p$ and return $v$ from such pair.

After every second add always an update in the root with current value, in order to always find the answer for every query. This idea can be implemented with a 2D Segment Tree. Complexity for every query an update will be $O(log^2 N)$.

To turn this idea into the tree case, just notice that:

* right becomes the sub-trees.
* left becomes the ancestor.
* position becomes the height.

Decompose the tree in paths using Heavy Light Decomposition (HLD) and solve the same instance of the problem. Since HLD decompose every path from node $u$ to the root in $O(log N)$ paths each update/query complexity will be $O(log^3 N)$. Overall complexity will be $O((N + Q) log^3 (N+Q))$.

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


# Question
Title: complexity of a variant of the subset sum problem
We have a set of positive integers $N=\\{a\_1,...,a\_n\\}$, we want to select a subset $N'$ of $N$ with maximum total sum of integers such that this sum should not exceed a given integer $B$.

What is the complexity of this problem.

# Answer
> 3 votes
It is NP-hard. Given an instance of your problem, the sum of the integers in the optimal subset $N'$ is at least $B$ (which implies that it must actually be exactly $B$) if and only if the corresponding subset sum instance has answer "yes".

---
Tags: algorithms, complexity-theory, np-complete, np-hard, subset-sum
---


# Question
Title: Matching each unique pokemon with a unique move
**Background:**

* There are 832 unique Pokemon in the Pokemon universe, and
* There are 728 fighting moves that the Pokemon can collectively learn.
* No Pokemon can learn to do every fighting move, and some Pokemon can only learn one.
* The average Pokemon can learn between 10-30 fighting moves , and
* Most fighting moves can be learned by multiple Pokemon.

**Challenge:**

I want to match as many unique Pokemon to one unique move. These are one-to-one matches.

**Example with U.S. presidents:**

* Name: Clinton, Moves: Democratify, Impeachify
* Name: Bush, Moves: Republicanify
* Name: Obama, Moves: Democratify, Healthcarify
* Name: Trump, Moves: Republicanify, Impeachify

**Example solution that matches the highest number** (in this case, all of them)

* Clinton-Democratify
* Bush-Republicanify
* Obama-Healthcarify
* Trump-Impeachify

**Summary:** What's an algorithm I could use to get the most potential matches of unique Pokemon to unique move?

**Caveat:** I'm just a regular guy, no computer science background, and a fuzzy memory of what I learned in my high school calculus class, and a VERY basic understanding of graph theory... so bonus points if you explain it simply enough for me to understand.

# Answer
> 1 votes
While your description of the problem is not super clear. I can guess that you're looking at a **maximum bipartite matching problem**. Which by the way, can also be viewed as a degenerate case of **maxflow problem**. Both problems are classic, you should have no problem finding resources on them. For example, this.

---
Tags: graphs, matching
---


# Question
Title: Calculating probability of reaching state in DTMC
Consider a highly-connected graph of states & transitions where each transition is marked with a weight (representing probability of occurring) and the graph satisfies the Discrete Time Markov Chain (DTMC) property: for each state the outflow transition weights are reals (or just rationals, if that makes a difference) in \[0,1\] which sum to 1, and the transition weights stay constant in time. So a finite state machine where the system moves through the states probabilistically, basically. For example:

Where $a\_{0,1} + a\_{0,2} = 1$, $a\_{1,0} + a\_{1,3} = 1$ etc.

Assume we start the system in the state where $x = 0$; what is the probability that the system reaches the state where $x = 3$, and what is the algorithm for determining that probability? From my small knowledge of probability, the algorithm requires summing of the probabilities of all finite paths that eventually reach $x = 3$; for example:

$P\[F (x = 3)\] = a\_{0,1}\cdot a\_{1,3} + a\_{0,2}\cdot a\_{2,3} + a\_{0,1}\cdot a\_{1,0} \cdot a\_{0,1} \cdot a\_{1,3} + \ldots$

Since it's possible for the system to loop indefinitely before reaching $x = 3$, this equation includes an infinite sum of infinite products and is beyond my ability to solve. How is something like this calculated?

# Answer
The answer to your question very much depends on the values of the probabilities $a\_{ij}$. If all are non-zero, then the DTMC forms one single strongly connected component and the probability of reaching $x=3$ is therefore $1$ (it is $1$ for any state in such a case in fact). This result comes from the Long-run theorem, which says that any finite DTMC eventually reaches a bottom SCC and visits all its states infinitely often.

Have a look at the lecture slides and notes of a course on probabilistic systems. Especially the third and fourth lecture.

In a general case, you would find with a graph analysis states that reach $x=3$ with probability $1$ denoted $S\_1$ and those with probability $0$ denoted $S\_0$. Then you have a set of states $S\_?$ for which you don't yet know the probability. For them you construct a matrix $\mathbf{A}$ of transition probabilities (it will be a square matrix of size $|S\_?|\times |S\_?|$). Then you construct a vector $\mathbf{b}$ with one-step probability to reach $x=3$. A solution to $\mathbf{A}\cdot \mathbf{x} = \mathbf{b}$ gives you the probabilities for states in $S\_?$.
> 1 votes

---
Tags: probability-theory, model-checking, markov-chains
---


title: Practical hard 3-sat instances

text:
# Question
Title: Practical hard 3-sat instances
The $3-SAT$ problem is known to be NP-complete problem. Which means that (as far as I understand), unless $P \neq NP$, for every algorithm $A$ which decides $3-SAT$, $A$ runs in super polynomial time (I know that this is not well defined). A stronger assumption is the "Strong Exponential Time Hypothesis " which states that every algorithm has to run in worst case exponential time.
Does that mean, for example, that every algorithm $A$ (here I refer to a "real" or practical implementation, such as Glucoses, DPLL, Z3, etc.), has an instance of size, say 200, which $A$ will not be able to solve in a reasonable time? I see many sat solvers solving formulas with millions of variables in very short time; and I am aware of subsets of $3-SAT$ which are easy, such as Horn clauses, or a random instance with a known density - but it seems that these solvers work amazingly fast without any assumptions on the input.
I have searched for Sat benchmarks, or instances which should be hard, but when running them on a modern sat solver, it doesn't seem to be a problem.
It is known that complexity assumptions (or claims) are about the asymptotic behavior, my question is: do we know for which $n\_0$ these assumptions "kick in" in the case of $3-SAT$? Can we generate, or at least be confident of the existence of a relatively small formula ($\< 200$), such that every algorithm requires $\sim2^{200}$ operations?

# Answer
> 3 votes
> do we know for which $n\_0$ these assumptions "kick in" in the case of $3-SAT$? Can we generate, or at least be confident of the existence of a relatively small formula ($\< 200$), such that every algorithm requires $\sim2^{200}$ operations?

$3-SAT$ is known to be solvable in time $O(1.321^n)$. Therefore, there is no instance that would force a $\Omega(2^n)$ run time. SETH does not hold for $k-SAT$ for any bounded $k$; it is only expected to hold for general Satsifiability (with no limit on clause size). We don't really know what asymptotic runtime to expect for $k$-SAT for any $k$ (other than something exponential).

Also, for any $SAT$ formula, there is an algorithm solving it in $O(n)$ time. You could never hope to find a single example hard for all algorithms.

One way to generate hard SAT instances is to reduce from Integer Factorization.

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


# Question
Title: number of comparisons in searching algorithms
i was going thorugh different searching algorithms,Linear,binary and ternary search.Now i want to know the number of comparisons in these.

For linear search :

```
procedure Linear_search(a1,a2,...,an:integers,k)
1.location = 0;
2.for i = 1 to n      #n+1 times
3.    if (a_i = k)  then location = i # n times
4.return location;

```

so total comparisons are =n+n+1=**(2n+1**). Right?

For Binary Search and ternary search,we know the algorithm.But the number of comparisons are,

```
T(n) = T(n/2) + 2,  T(1) = 1
 T(n) = T(n/3) + 4, T(1) = 1

```

Hence solving this will give 2clogn + O(1) and 4clogn + O(1).

how to constants(2 ,4) are formed?? Also correct me if my comparsions are wrong.

# Answer
> 1 votes
When measuring comparisons, we usually only charge comparisons of elements of the array (more accurately, we charge comparisons for the datatype of array elements, but not of array indices). In the example of linear search, at each iteration you are comparing one element of the array to the input element being searched. So in total, you are making exactly $n$ comparisons in the worst case.

For binary search, at each step you are making a 3-way comparison between the middle element of the current segment of the array and the input element. The number of 3-way comparisons satisfies the recurrence $T(n) \leq T(\lceil \frac{n-1}{2} \rceil) + 1$, with base case $T(1) = 1$ (when $n = 1$, you are making a 2-way comparison). If you are only allowing 2-way comparisons, then each 3-way comparison has to be simulated using two 2-way comparisons, which might be the reason why the recurrence has $+2$ instead of $+1$.

For ternary search, you are making two 3-way comparisons (comparing the two middle thirds to the input element), which translates to four 2-way comparisons.

(A 2-way comparison is one which has two outcomes: for example, "$x = y$?" is a 2-way comparison, as is "$x \leq y$?". A 3-way comparison is one which has three outcomes: given two elements $x,y$, the comparison tells you whether $x \< y$, or $x = y$, or $x \> y$.)

---
Tags: algorithms, time-complexity, runtime-analysis, search-algorithms, binary-search
---


# Question
Title: I don't see why the array[1..3, 1...2] is faster to index than array[1...2, 1...3]?
In my programming concept class we learned that for the array type it's faster to index in memory if the length of an element is = $2^n$. This case make us only need to offset instead of actually doing multiplication.

We also learned about the representation of multivariable arrays with row major. It was then said that the array\[1...3, 1...2\] is faster to index compared to array\[1...2, 1...3\] because we have the length of an element being = $2^n$. I don't understand why you can determine this?

# Answer
Two-dimensional arrays are stored as one-dimensional arrays. Your first array is stored as $$ A\[1,1\], A\[1,2\], A\[2,1\], A\[2,2\], A\[3,1\], A\[3,2\], $$ so the offset of $A\[x,y\]$ is $2x+y-3$. In contrast, the third array is stored as $$ A\[1,1\], A\[1,2\], A\[1,3\], A\[2,1\], A\[2,2\], A\[2,3\], $$ so the offset of $A\[x,y\]$ is $3x+y-4$. Multiplying by 2 could be faster than multiplying by 3 – for example there might be a suitable addressing mode in your instruction set.
> 4 votes

---
Tags: programming-languages
---


# Question
Title: Finite / Infinite Languages True/False and why?
Just doing some work on Finite and infinite languages. And came across some statements I know the answer to but not sure how to explain why.

1. There are finitely many finite languages. -This is false right? Since there are technically infinitely many finite languages
2. Union of any two languages over alphabet (1,0) is regular. -False right? Since you can take a (non-reg U non-reg = non-reg)
3. Single state NFA can recognize only finite languages -False, but I have no idea how to explain why...

# Answer
> 1 votes
1. False. There are infinitely many finite language. Just think of {0,1}\*. This is a infinite set of finitely long strings. or say, it is union of infinite number of finite languages over {0,1} which have strings of finite length.
2. False. Union of two non regular languages MAY BE regular but it not the case always. This answer explains it well.
3. False. Lets have a single state NFA having state q0. let 'd' be the transition function. d(q0, a) = q0 and since this is single state NFA, q0 is also final state. This NFA will accept all strings having only 'a'. i.e. {a,aa,aaa,aaaa...} The cardinality of this set is infinite, hence it can accept infinite languages too.

---
Tags: regular-languages, finite-automata
---


# Question
Title: Why does this triple loop code have a running time of 1.5lnN * N^2
Hi all, I'm currently going through the Princeton Algorithms course on coursera, and I'm having trouble understanding the answer to this quiz. I think I understand where the $\frac{1}{2} N^2$ term comes from, but I am completley lost on the $3 \ln N$ term. Unfortunatley this is the only solution.

# Answer
Let's consider the outer two loops first. For a *fixed* value of $i$, the number of iterations of the middle loop is exactly $n-1 - (i+1) + 1 = n - i -1$. Since $i$ ranges from $0$ to $n-1$ (in the outer loop), the *overall* number of iterations of the middle loop is: $$ \sum\_{i=0}^{n-1} (n - i -1) = \sum\_{i=0}^{n-1} i = \frac{n(n-1)}{2}. $$

For each of those iterations we execute the inner loop for a certain number $x \in \mathbb{N}$ of iterations. Notice that $x$ only depends on $n$ and not on $i$ or $j$. Before the first iteration, the value of $k$ is $1$, and it doubles after every iteration (i.e., before the next iteration starts). This means that after a generic number $h \in \mathbb{N}$ of iterations (i.e., just before the $(h+1)$-th iteration starts) the value of $k$ is $2^h$. Since the loop continues as long as $k = 2^h \< n$, we are interested in the minimum value of $h$ for which the above inequality is not true. This is $x = \lceil \log n \rceil $ if $n \ge 1$ (where we used the fact that $h$ must be a non-negative integer) and $x = 0$ otherwise. Since you are interested in the asymptotic behavior of the algorithm, I will ignore this latter case.

Finally, notice that for each iteration of the inner loop, exactly $3$ array accesses are performed.

To summarize:

* We reach the inner loop $\frac{n(n-1)}{2}$ times;
* Each time we perform $\lceil \log n \rceil$ iterations;
* Each iteration causes $3$ array accesses.

The total number of array accesses is therefore: $ \frac{3}{2}n(n-1) \lceil \log n \rceil \sim \frac{3}{2}n^2 \log n$.
> 4 votes

---
Tags: time-complexity, runtime-analysis
---


# Question
Title: How to encode reachability in a graph with walls as a SAT problem
Suppose we have a graph that represents a grid of cells. We are given a cell to start in and a cell that's the destination. There are cells that we cannot enter and they are known as walls. Finally we may only move to adjacent cells (diagonal movements are not allowed).

My question is how would one encode this problem in CNF to be solved by a SAT solver?

For example, let the graph represent the following 2 x 3 grid:

```
0 1 0
0 0 0

```

where 0-cells are cells we may be in or move to and 1-cells are walls. Suppose we start in (0, 0) and want to move to (0, 2). Then there is a path.

On the contrary, consider another 2 x 3 grid with the same start and destination positions:

```
0 1 0
0 1 0

```

Then this graph does not have a path from start to destination.

Clearly we may run BFS on the graph and if there's a path we can encode it as a trivially satisfiable CNF, or if there isn't then encode it as a trivially unsatisfiable CNF. For example, $A$, or, $A \land \neg A$. However, the point of my exercise is to encode the path existence in CNF.

This is indeed part of my homework. I have been stuck for a while now. Some help on this problem would be greatly appreciated.

# Answer
> 1 votes
> The point of my exercise is to encode the path existence in CNF

Well, a trivial way to do this is by reducing the problem to ***2-SAT***, following this set of rules:

1. Assing a literal to every edge of your graph, for example first element in first row become $a$, second element in first row become $b$ etc.
2. Put in ***OR*** relation the literal in the "*start*" position with each adjacent literal ( thus obtaining the clauses of your formula). If one or more adjacent literal has value 1, omit the clause in which it appears. Note that, when they are both 0, you dont need to repeat them: if you have an adjacency between $a$ and $b$, you do not have to repeat the clause between $b$ and $a$.Furthermore you must not consider the diagonal adjacencies.
3. Perform the same procedure for all the literals adjacent to the starting one and for those in turn, until you reach the *destination* literal.
4. Connects all the obtained clauses with an ***AND***

To better adapt to your example, in which a 0 value means "*you can pass*" and a 1 value means "*you cannot pass*", you can negate all the literals in the formula.

So for the matrix in the first above example the corresponding path existence encoded into *2-SAT* instance will be:

$(\not a \lor\not d) \land (\not d \lor\not e) \land (\not e \lor\not f) \land (\not f \lor\not c)$

By replacing the matrix values in the first example, the formula evaluates to 1, which means that this formula encodes a valid path. However, for the secon matrix in the example, you never obtain a true formula in which the ending literal is present, so there is no valid path.

---
Tags: algorithms, graphs, reductions, satisfiability
---


# Question
Title: Perfect Hash Function: How does it cope with lookups outside the set of keys?
I'm currently looking at perfect hash functions. One thing I miss from the texts I've read so far is, how they cope when attempting to look up with a key that is outside of the set from which the perfect hash was generated from.

# Answer
> 2 votes
Given a set of keys, a “perfect” hash function is one that gives a different hash for each key. As soon as you try to apply it to a key outside that set, it is quite likely not “perfect” anymore.

Let’s say you are writing a compiler, and you found a”perfect” hash function that maps each reserved identifier of your programming language to a different hash code. And I give you a word that is *not* one of the reserved words of the language. If you apply your “perfect” hash function then the hash code is either not the hash code of a reserved word (you need to check for that case), or it may be the hash code of a reserved word ( you need to check for that as well). The advantage is that at most *one* check is needed.

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


# Question
Title: How does the function to curry and uncurrying another function work?
The following is the code to curry or uncurry a function in Haskell:

```
curry :: ((a, b) -> c) -> a -> b -> c
curry f a b = f (a, b)

uncurry :: (a -> b -> c) -> (a, b) -> c
uncurry f (a, b) = f a b

```

I can understand the type signature part but not the function definition. Would you please explain me how those function bodies turn a curried function into an uncurried one and vice versa?

# Answer
> 3 votes
The meaning of `curry` can be easier to be seen when the type signature is written as

```
curry :: ((a, b) -> c) -> (a -> b -> c)

```

that is, a function taking a single parameter of type `(a, b)` and yielding a result of type `c` is turned into a function taking two separate values of types `a` and `b` yielding the same result type `c`.

We might define curry for this signature like this:

```
curry f = g

```

where `f :: ((a, b) -> c)` and `g :: (a -> b -> c)`.

`f` is passed by the user, but how do we get `g`? We know `g` is a function taking two parameters and yielding a result type, so it must structurally look like `\x -> \y -> z`, where `x :: a`, `y :: b`, and `z :: c` (`\v -> e` is the syntax for lambda-expressions in Haskell). We now have to find a way to get the result `z` from `x` and `y` such that the types work out correctly.

As both result types `c` must be the same, the only way to get `z` is to use `f` and apply it to a value of type `(a, b)`. So we know `z = f (?, ?)` where `(?, ?)` must have type `(a, b)`. Where do we get values of these types from? Again, as the types must match exactly, the only option is to use `x` and `y` here. We get

```
curry f = g
    where g = \x -> \y -> f (x, y)

```

This would be a proper implementation for `curry`. One that is easier to read is to inline `g`:

```
curry f = \x -> \y -> f (x, y)

```

As Haskell allows us to define functions with multiple parameters, we can resolve the lambda-expression and simplify this to

```
curry f x y = f (x, y)

```

which is (beside different variable names) the same implementation as in your question.

For `uncurry` the procedure is similar (note that you had missing parentheses in the type signature for `uncurry` in your original question which lead to a different type).

From

```
uncurry :: (a -> b -> c) -> ((a, b) -> c)

```

we conclude

```
uncurry f = g
    where g = \(x, y) -> z

```

with `f :: (a -> b -> c)`, `g :: (a, b) -> c`, `x :: a`, `y :: b` and `z :: c`. Following the types, `z` can only be defined by `z = f x y`. From that we get

```
uncurry f = g
    where g = \(x, y) -> f x y

```

and after inlining `g` and removing the lambda

```
uncurry f (x, y) = f x y

```

---
Tags: lambda-calculus, functional-programming, haskell
---


# Question
Title: Why does higher-order abstract syntax need an inverse to define catamorphisms?
In the introduction to the colorfully-named Boxes Go Bananas: Encoding Higher-Order Abstract Syntax with Parametric Polymorphism, Washburn and Weirich describe a problem in traditional formulations of higher-order abstract syntax (HOAS):

> One obstacle preventing the widespread use of this technique is the difficulty in using elimination forms, such as catamorphisms, for datatypes containing functions. The general form of catamorphism for these datatypes requires that an inverse be simultaneously defined for every iteration. Unfortunately, many operations that we would like to define with catamorphisms require inverses that do not exist or are expensive to compute.

They go on to demonstrate this problem with a small example, in Haskell. They define the following datatypes to represent simple lambda terms with HOAS:

```
data Exp = Lam (Exp -> Exp) | App Exp Exp
data Value = Fn (Value -> Value)

```

`Lam` represents lambda terms, `App` represents function application, and `Fn` represents evaluated functions. They next attempt to define `eval :: Exp -> Value`, but this causes trouble, as it requires converting a function of type `Exp -> Exp` to one of type `Value -> Value`. Since `Exp` appears in both positive and negative positions, this requires functions from both `Exp -> Value` *and* `Value -> Exp` to define.

The remainder of the paper proposes a solution to that problem, but I am stuck on something else: I don’t understand why it’s a problem at all. Usually, in programming language papers, we define languages with grammars like the following one:

$$ \begin{align\*} v &::= \lambda x. e \\ e &::= v \thinspace | \thinspace e \thinspace e \end{align\*} $$

If we define a big-step evaluation relation $e \Downarrow v$, we have no need to define some other “unevaluation” relation $v \Uparrow e$, as lambdas are already values, so $\lambda x.e \Downarrow \lambda x.e$, which is quite straightforward.

It seems to me that a natural translation of the above grammar to HOAS is different from the one Washburn and Weirich present. Specifically, I think it would look more like this:

```
data Exp = Lit Value | App Exp Exp
data Value = Fn (Value -> Exp)

```

Defining `eval` on this grammar is as simple as defining the usual big-step relation:

```
eval :: Exp -> Value
eval (Lit v) = v
eval (App e1 e2) = case eval e1 of
  Fn v -> eval (v (eval e2))

```

But this solution seems much too simple to be right. Boxes Go Bananas is a well-cited paper from reputable authors published at a reputable PL conference, so its solution surely must have some advantage over the one I presented above. My question, therefore, is simply this: what is that advantage? What am I missing?

# Answer
> 4 votes
By being corecursive between the types, you indeed get a representation of a grammar, and it does have binding. But now you've sort of "baked in" the unembedding by making it "definitionally id". (This is similar to the `Place` constructor in Fegaras and Sheard).

So you can `evaluate` to `Value`. But what if you want to `evaluate` to anything else? You can't, unless it is something that "passes through" `Value`. So consider writing an "abstract interpreter" for your language (i.e., where you evaluate only to the "type" of the expression but without computing, or where you only "count the reductions" without computing). You can't, because you need to pass through having concrete elements of `Value` to go under lambdas.

You can fix this by having both `Place` and *also* a normal HOAS binding form, as in the above paper. But then that still doesn't suffice, for reasons they explain (and similar to what I've described -- see section 2) and so you make `Place` go further abstract by parameterizing over it, etc. Follow your nose further and you'll hit free monads. I got an intuition for this stuff from Edward Kmett's phoas post.

---
Tags: programming-languages, functional-programming, haskell
---


# Question
Title: What will be the pictorial diagram of this transition table?
I was doing my homework and I am confused on what I'm doing, it can't be that straightforward. I'm making a mistake somewhere. I tried looking for practice problems but they don't cover my issue either, I'm still confused. What will be the pictorial diagram for the following transition table?

# Answer
> 2 votes
You just create a super simple Graphviz document encoding the information:

```
$ cat foo.gv
digraph {
  q0 -> q0 [label = "input: a\noutput: 0"];
  q0 -> q2 [label = "input: b\noutput: 0"];
  q1 -> q1 [label = "input: a\noutput: 1"];
  q1 -> q0 [label = "input: b\noutput: 1"];
  q2 -> q2 [label = "input: a\noutput: 1"];
  q2 -> q1 [label = "input: b\noutput: 1"];
}
$ _

```

Process it:

```
$ dot foo.gv -T png -o foo.png
$ echo $?
0
$ _

```

Profit!

---
Tags: finite-automata
---


title: Storing $K$ numbers with ordering

text:
# Question
Title: Storing $K$ numbers with ordering
Let $S$ be a sequence of $k$ many numbers. The position of the number in the $S$ matters. In the $S$ there are only $j$ many different numbers are there means $S$ contains many duplicates. Position is a query which needed to be answered, position(i) returns the element at position $i$ in $S$.

Trivial way to store them is using array which will takes $O(S)$ space and position can be solved in $O(1)$ time.

I am looking for a representation that takes $O(j)$ space (or somewhere near to it) and such that position can be solved in $O(1)$(even in more time is also ok)?

Please suggest some papers also.

# Answer
What you ask is impossible, assuming you don't really mean sets (as sets are orderless), but ordered tuples. Consider $j=2$, then you effectively have $k$-length binary strings. And those require $\Omega(k)$ storage.
> 1 votes

---
Tags: data-structures
---


# Question
Title: Algorithm to Minimize a Regular Expression
I am referring to regular expressions with alphabet {$0$, $1$}. We want to minimize them so that they have the least possible number of symbols and operators. Is there an algorithm to do this?

For instance, what is done on this page in the accepted answer:

https://stackoverflow.com/questions/35112630/minimize-specific-regular-expression

Is there a formal algorithm to explain the process that the answer went through?

# Answer
> 0 votes
There is a trivial algorithm to find the minimum regular expression equivalent to a given one:

> Go over all regular expressions in nondecreasing order of length. For each one, check whether it is equivalent to the original regular expression. Return the first one which is.

To check equivalence, convert the regular expressions to NFAs, then to DFAs, then computed the product automaton for the symmetric difference, and check whether any accepting state is reachable from the initial state.

This algorithm isn't very efficient. Indeed, minimizing regular expressions is PSPACE-complete. See for example Gramlich and Schnitger, Minimizing nfa's and regular expressions.

---
Tags: regular-expressions
---


# Question
Title: Context-free grammar how to have unequal number of a's on either side of b
I have been trying to create a CFG for the set $\\{w=a^iba^j \mid i \neq j\\}$.

To my understanding, there are essentially 2 scenarios, one where there are more $a$s on the left side of $b$, and one where there are more $a$s on the right side of $b$. So far I have come up with: \begin{align} S &= TbR \mid RbT \\ T &= aT \mid \varepsilon \\ R &= TaT \end{align} My intention is the have $R$ to always have more $a$s than $T$, however I don't think this is correct as $T$ can be greater than $R$ in this definition, as $R$ could take be just $a$ while $T$ is $aa$.

I need a bit of help defining 2 variables $T$ and $R$, where $R$ always has more $a$s than $T$.

# Answer
> 2 votes
Equal numbers of a’s on either side, then the middle is replaced by a+b or by ba+.

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


# Question
Title: How to split a context-free language into three sub-languages?
I try to split the language $$ L = \\{a^ib^j \mid i \neq 2j, i \neq 3j\\} $$ into three languages \begin{align} L\_1 &= \\{a^ib^j \mid i \< 2j\\} \\ L\_2 &= \\{a^ib^j \mid 2j \< i \< 3j\\} \\ L\_3 &= \\{a^ib^j \mid i \> 3j\\} \end{align} and then use one more production $S = S\_1|S\_2|S\_3$, but I have no idea how to find the CFG for $L\_2$.

# Answer
The idea is to start with a grammar for the related language $L'\_2 = \\{a^ib^j \mid 2j \leq i \leq 3j\\}$: $$ S \to a^2Sb \mid a^3Sb \mid \epsilon. $$ We want to force at least one production of the form $a^2Sb$ and at least one of the form $a^3Sb$. There are many ways of doing that. The simplest, probably, is to force one of these productions to be the first, and the other one to be the last: $$ \begin{align\*} &S \to a^2 T b \\ & T \to a^2 T b \mid a^3 T b \mid a^3 b \end{align\*} $$ Alternatively, let us notice that the condition $2j \< i \< 3j$ can be written as $2j+1 \leq i \leq 3j-1$, and also as $2(j-2) \leq i-5 \leq 3(j-2)$. This implies the even simpler grammar $$ S \to a^2Sb \mid a^3Sb \mid a^5 b^2 $$
> 2 votes

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


# Question
Title: Context-free grammar how to have same number of variables within a language
I am trying to get a CFG for the language:

> The set $A$ of odd-length strings in $\\{a,b\\}^\*$ whose first, middle and last symbols are all the same.

(some example of correct answers would be: a, aaa, ababa, aababba, some incorrect answers include: ɛ, aaaa, abbaa)

This is what I've done so far:

```
S = a|b|aTaTa|bTbTb
T = aT|bT|ɛ

```

However the problem is, I need T to be a string of any combination of 'a's and 'b's but of the same length, but I'm not sure how to express this. As you can see above, I can get strings made up of any combination, but they won't be the same length when passed to S. Any help is appreciated!

# Answer
Your approach won't work. Whenever you try to match the length of two non-terminals, that should be a big red flag your approach won't work.

Here's a hint: expand from the middle out, after starting with $S = a \mid b \mid aAa \mid bBb$. Can you take it from here?
> 2 votes

---
Tags: context-free
---


# Question
Title: Creating sum of all numbers within a sequence
Write an algorithm that, given sequence *seq* of *n* numbers where 3 \<= *n* \<= 1000 and each number *k* in *seq* 1 \<= *k* \<= 200, finds maximum sum by repeatedly removing one number from *seq*, except for first and last number in *seq*, and adding its value to sum of two adjacent numbers. Algorithm ends when there are only two numbers left.

For example: Max sum for sequence \[2, 1, 5, 3, 4\] is 31.

So far I've written brute force algorithm checking all possible combinations but it's not well suited for large sequences.

```
public static int solve(ArrayList<Integer> seq, int sumOfRemoved) {
  if (seq.size() == 3) {
    return seq.get(0) + seq.get(1) + seq.get(2) + sumOfRemoved;
  }
  LinkedList<Integer> maxValues = new LinkedList<>();
  for (int i = 1; i < seq.size() - 1; i++) {
    ArrayList<Integer> clone = (ArrayList<Integer>) seq.clone();
    clone.remove(i);
    int sum = seq.get(i - 1) + seq.get(i) + seq.get(i + 1);
    maxValues.add(solve(clone, sum));
  }
  int max = 0;
  for (int val : maxValues) {
    max = Math.max(max, val + sumOfRemoved);
  }
  return max;
}

```

My question is, is there more efficient algorithm solving this problem?

# Answer
> 1 votes
From the top of my head I would use a greedy approach, always remove the lowest available number so the potential sum of later steps lessens the least this way. But I do not have a proof for this finding the top possible sum, especially not at 0:21 on Monday :-).

With 2,***1***,5,3,4(0) it would go to 2,5,***3***,4(2+1+5=8), then to 2,***5***,4(8+5+3+4=20), and end at 2,4(20+2+5+4=31). So it finds your sum, but this is just one case.

---
Tags: java
---


title: Formal program verification in practice

text:
# Question
Title: Formal program verification in practice
As a software engineer, I write a lot of code for industrial products. Relatively complicated stuff with classes, threads, some design efforts, but also some compromises for performance. I do a lot of testing, and I am tired of testing, so I got interested in formal proof tools, such as Coq, Isabelle... Could I use one of these to formally prove that my code is bug-free and be done with it? - but each time I check out one of these tools, I walk away unconvinced that they are usable for everyday software engineering. Now, that could only be me, and I am looking for pointers/opinions/ideas about that :-)

Specifically, I get the impression that to make one of these tools work for me would require a huge investment to properly define to the prover the objects, methods... of the program under consideration. I then wonder if the prover wouldn't just run out of steam given the size of everything it would have to deal with. Or maybe I would have to get rid of side-effects (those prover tools seem to do really well with declarative languages), and I wonder if that would result in "proven code" that could not be used because it would not be fast or small enough. Also, I don't have the luxury of changing the language I work with, it needs to be Java or C++: I can't tell my boss I'm going to code in OXXXml from now on, because it's the only language in which I can prove the correctness of the code...

Could someone with more experience of formal proof tools comment? Again - I would *LOVE* to use a formal prover tool, I think they are great, but I have the impression they are in an ivory tower that I can't reach from the lowly ditch of Java/C++... (PS: I also *LOVE* Haskell, OCaml... don't get the wrong idea: I am a fan of declarative languages and formal proof, I am just trying to see how I could realistically make that useful to software engineering)

Update: Since this is fairly broad, let's try the following more specific questions: 1) are there examples of using provers to prove correctness of industrial Java/C++ programs? 2) Would Coq be suitable for that task? 3) If Coq is suitable, should I write the program in Coq first, then generate C++/Java from Coq? 4) Could this approach handle threading and performance optimizations?

# Answer
I'll try to give a succinct answer to some of your questions. Please bear in mind that this is not strictly my field of research, so some of my info may be outdated/incorrect.

1. There are many tools that are specifically designed to formally prove properties of Java and C++.

However I need to make a small digression here: what does it mean to prove correctness of a program? The Java type checker proves a formal property of a Java program, namely that certain errors, like adding a `float` and an `int`, can never occur! I imagine you are interested in much stronger properties, namely that your program can never enter into an unwanted state, or that the output of a certain function conforms to a certain mathematical specification. In short, there is a wide gradient of what "proving a program correct" can mean, from simple security properties to a full proof that the program fulfills a detailed specification.

Now I'm going to assume that you are interested in proving strong properties about your programs. If you are interested in security properties (your program can *not* reach a certain state), then in general it seems the best approach is model checking. However if you wish to fully specify the behavior of a Java program, your best bet is to use a specification language for that language, for instance JML. There are such languages for specifying the behavior of C programs, for instance ACSL, but I don't know about C++.
2. Once you have your specifications, you need to prove that the program conforms to that specification.

For this you need a tool that has a formal understanding of both your specification and the operational semantics of your language (Java or C++) in order to express the **adequacy theorem**, namely that the execution of the program respects the specification.

This tool should also allow you to formulate or generate the proof of that theorem. Now both of these tasks (specifying and proving) are quite difficult, so they are often separated in two:

* One tool that parses the code, the specification and generates the adequacy theorem. As Frank mentioned, Krakatoa is an example of such a tool.
    * One tool that proves the theorem(s), automatically or interactively. Coq interacts with Krakatoa in this manner, and there are some powerful automated tools like Z3 which can also be used.

One (minor) point: there are some theorems which are much too hard to be proven with automated methods, and automatic theorem provers are known to occasionally have soundness bugs which make them less trustworthy. This is an area where Coq shines in comparison (but it is not automatic!).
3. If you want to generate Ocaml code, then definitely write in Coq (Gallina) first, then extract the code. However, Coq is terrible at generating C++ or Java, if it is even possible.
4. Can the above tools handle threading and performance issues? Probably not, performance and threading concerns are best handled by specifically designed tools, as they are particularly hard problems. I'm not sure I have any tools to recommend here, though Martin Hofmann's PolyNI project seems interesting.

In conclusion: formal verification of "real world" Java and C++ programs is a large and well-developed field, and Coq is suitable for parts of that task. You can find a high-level overview here for example.
> 46 votes

# Answer
I would like to mention three remarkable applications of formal methods/formal verification tools in industry or non-trivial real systems. Note that I have little experience on this topic and I only learn them from reading papers.

1. The open-source tool Java Pathfinder (JPF for short) released by NASA in 2005 is a system to verify executable Java bytecode programs (see Java Pathfinder@wiki). It has been used to detect inconsistencies in the executive software for the K9 Rover at NASA Ames.
2. This paper: Using Model Checking to Find Serious File System Errors@OSDI'04 shows how to use model checking to find serious errors in file systems. A system called FiSC is applied to three widely-used, heavily-tested file systems: ext3, JFS, and ReiserFS, and 32 serious bugs are found. It won the Best Paper Award.
3. This paper: How Amazon Web Services Uses Formal Methods@CACM'15 describes how AWS applies formal methods to its products like S3, DynamoDB, EBS, and Internal distributed lock manager. It focuses on Lamport's TLA+ tool. By the way, Lamport has intensively used his own TLA toolbox. He often gives a (quite complete) formal verification in TLA of the algorithms/theorems proposed by himself (as well as coauthors) in appendixes to the papers.
> 20 votes

# Answer
Formal verification is now possible for programs written a subset of C++ designed for safety-critical embedded systems. See http://eschertech.com/papers/CanCPlusPlusBeMadeAsSafeAsSpark.ppt for a short presentation, and http://eschertech.com/papers/CanCPlusPlusBeMadeAsSafeAsSpark.pdf for the full paper.
> 5 votes

# Answer
A formal specification of a program is (more or less) a program written in another programming language. As a result, the specification will certainly include its own bugs.

The advantage of formal verification is that, as the program and the specification are two separate implementations, their bugs will be different. But not always: one common source of bugs, overlooked cases, will often match. Thus, formal verification is not a panacea: it can still miss a non-trivial number of bugs.

A disadvantage of formal verification is that it can impose something like twice the implementation cost, probably more (you need a specialist in formal specification, and you need to use the more or less experimental tools that come with it; that won't come cheap).

I'd guess setting up test cases and scaffolding to run them automatically would be a better use of your time.
> 4 votes

# Answer
You ask a few different questions. I agree it does appear that formal verification methods for industrial/commercial applications are not so common. one should realize however that a lot of "formal verification" principles are built into compilers to determine program correctness! so in a way, if you use a modern compiler, you're using much of the state-of-the-art in formal verification.

You say "I'm tired of testing" but formal verification is not really a substitute for testing. in a way its a *variation* on testing.

You mention Java. there are many advanced formal verification methods built into a java verification program called FindBugs which indeed can be run over large codebases. Note it will turn up both "false positives and false negatives" and the results need to be reviewed/analyzed by a human developer. But note even if it is not turning up real functional defects, it does generally turn up "antipatterns" that should be avoided in code anyway.

You make no more mention of your particular application other than "industrial". Formal verification in practice tends to depend on the particular application.

Formal verification techniques seem to be widely used in EE to prove circuit correctness e.g. in microprocessor design.

Here is an example of a survey of formal verification tools in the EE field by Lars Philipson.
> 2 votes

# Answer
Perhaps, a model checker may be helpful.

http://alloytools.org/documentation.html Alloy is a model checker.

A nice presentation explaining the concept of model checking using Alloy: https://www.youtube.com/watch?v=FvNRlE4E9QQ

In the same family of tools comes 'property-based testing', they all try to find a counter-example for the given specification model of your software.
> 1 votes

---
Tags: programming-languages, program-correctness, software-verification
---


# Question
Title: P/NP - Polynomial Reduction vs Certificate
I am learning about the P/NP problem right now, and I don't understand when to use polynomial reduction and when to use a certificate.

---

How I understand polynomial reduction is that you can use it to show that:

* Problem A is in P if:

B is in P and you can reduce A to B in polynomial time -\> A $\leq\_p$ B

* Problem A is in NP if:

B is in NP and you can reduce B to A in polynomial time -\> B $\leq\_p$ A

---

Then I read about certificates and this is how I understand the basic Idea/Components behind it:

* Problem: Problem to solve
* Certificate: possible solution
* Certifier: Checks if the Certificate is correct

---

What I don't understand is:

1. What do you want to show with solution that uses a certificate?
2. When do you use one over the other ?

# Answer
> 1 votes
> * Problem A is in NP if: B is in NP and you can reduce B to A in polynomial time -\> B $\leq\_p$ A

Not quite right. The class P is a subset of NP anyway, and hence A is already NP if it is in P. The question is whether A is in P or not.

By reducing B to A in polynomial time, you prove that any polynomial solution of A is a polynomial solution of B. Assuming B is in NP gives no useful information about A, since it is possible that B is in P as well (remember that P $\subseteq$ NP). However, assuming (and probably that is what you meant), that B is NP-Hard, then, by reducing B to A, we prove that A is also hard for NP class, and hence unless P=NP, the problem A is not in P.

Now back to the question. What we know so far, P $\subseteq$ NP. There are more classes above NP like EXP and under P like L for example. Which means, $$L \subseteq P \subseteq \mathit{NP} \subseteq \mathit{EXP}.$$ Check the link for more information about the classes. However, one characterization of problems in NP, is that they all admit a certifier, that can in polynomial time in the size of the input, say if the given instance is a yes instance. For example, for travelling salesman, which is an NP-Complete problem, the certificate is a path. You can clearly certify it, by checking if it visits all cities and each city exactly once and return to the beginning. Since P $\subseteq$ NP the same works for P problems. Like shortest path. given a shortest path between two vertices, you can certify it it is a shortest path. For example, the certifier can compute a shortest path in polynomial time and compare the lengths.

Now the interesting part about certificates, is to certify if a problem admits a certificate for the negative answer. That means, given an instance and a certificate, the certifier can tell in polynomial time, if the instance is not in the language. Problems that admits such a certifier belong to the class co-NP. It is believed that NP $\neq$ co-NP unless P = NP. The class P belongs to the intersection of both classes and hence we can certify both negative and positive answers in polynomial time.

**Summary**

* Reducing $A$ to a polynomial problem proves that it is solvable in polynomial time.
* Reducing an NP-Hard problem to $A$, proves that $A$ is NP-Hard and probably not in P. In this case, even if the problem is in NP and hence is NP-complete, we can only say about $A$ that it is NP-hard, we still do not not if it is in NP.
* A problem is in NP if there is for each instance that belongs to language of the problem, a certificate, that can be certified in polynomial time in the size of the instance.
* A problem is in co-NP if there is for each instance, that odes not belong to the language of the problem, a certificate, that can be certified in polynomial time in the size of the instance.
* The class P belongs to the intersection of P $\cap$ co-NP.

# Answer
> 0 votes
Polynomial reduction and certificates have very little to do with each other.

Basically, we defined the set P of all easy problems that can be solved by a computer in polynomial time.

Then obviously problems not in P are hard.

We then defined the set NP of all problems which can be solved in polynomial time by a non-deterministic computer, in other words a computer that can follow an unlimited number of paths in parallel, or equivalent a computer that can make unfailingly lucky guesses, or equivalent, a computer that is given a problem and a correct hint at the solution, also known as “certificate”.

---
Tags: np, decision-problem, polynomial-time, p-vs-np, polynomial-time-reductions
---


# Question
Title: How can I make my algorithm more efficient or Is there a better way to solve the problem
**Problem Statement:** You are given an array/sequence of positive numbers $a\_1,a\_2,a\_3,\cdots,a\_n$ and you need to execute `q` queries on the array and in each query you will take a positive number as an input and find out all the multiples of the number in the given array and print it.

```
Input:
2 4 9 15 21 20
q1 = 2
q2 = 3
q3 = 5

Output:
3
3
2

```

To solve this problem I thought of an algorithm which works as explained below:

* Create an array name `freq_data[]` whose length will be equal to the maximum element of the array, and it stores the count of each and every number occurred in the input array.
**For Example:**

```
  array[] = {2, 4, 9, 15, 21, 20}
  max_element = 21
  freq_data[] = {0,1,0,1,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,1,1}

```
* Create an array name `multiples[]` whose length will also be equal to maximum element encountered in the array. This array will store all the multiples of the numbers between $\[1,\text{maximum value}\]$. Using `multiples[]` array, I can answer the query in $O(1)$ time by printing the value at `multiples[q - 1]`.
* Initialise the `multiples[0] = (size of arr[] - 1)` because every number in the array is divisible by 1.
* If the query entered is $(\gt \text{maximum value})$ in the array, then the answer will be zero because there will be no element in the array which will be divisible by `arr[i]` because for the number to be multiple of another, the number should be either equal to or greater than the divisor i.e $(\geq arr\[i\])$.
* Time Complexity: $O(max \times log(max))$
Space Complexity: $O(max)$

Now I was wondering what if I changed the question like instead of taking the queries from the user, I am now interested in finding for each `arr[i]` how many multiples are present in the left-sub array with respect to `arr[i]`.

Formally: You are given a sequence of positive numbers $a\_1,a\_2,a\_3,\cdots,a\_n$. Write a program to count the number of multiples in $a\_0,a\_1,a\_2,\cdots,a\_{j-1}$ where $0 \leq j \lt i$ for each $a\[i\]$ where $0 \leq i \lt n$.

**For Example:**

```
1. Input:
arr[] = {2 6 3}
Output:
no_of_multiples[] = {0,0,1} // For 2 , 6 there are no multiples present but for 3 there is one multiple present i.e. 6

2. Input:
arr[] = {16,25,63,12,65,45,23,65,78,99,36,12,36,41,36,2,3}
Output:
no_of_multiples[] ={0,0,0,0,0,0,1,0,0,0,2,1,0,2,6,9}

```

To solve the above problem, the algorithm which I designed is basically based on the previous problem solution but rather than updating the `freq_data[]` at once I will first check how many multiples of the `arr[i]` is present in the `freq_data[]` and after finding all the multiples, I will increment the value at `++freq_data[data[i] - 1]` and then I will print the `freq_data[i]` array after processing the whole arra`arr[i]`.

Time Complexity: $O(n \times log(max))$
Space Complexity: $O(max)$

Solution In C Programming

*My question is: Is there any better algorithm to solve the second part i.e Write a program to count the number of multiples in $a\_0,a\_1,a\_2,\cdots,a\_{j-1}$ where $0 \leq j \lt i$ for each $a\[i\]$ where $0 \leq i \lt n$.*

Edit-1: With reference to @gnasher729 points, there are constraints on the inputs because if the size of the input gets larger the algorithm will not give the right answer:

* $1\leq n \leq 10^5$ `Constraint on the length of the sequence`
* $1 \leq arr\[i\] \leq 10^6$ `Constraint on the values of the sequence`

# Answer
Your attempt runs into a huge problem with the input \[1, 2, $2^{63}$\].

Either your numbers are so small that it doesn’t matter. Otherwise, you start with a solution, find its speed and why it is slow, and then iteratively improve it. That’s usually a much better method than hoping that someone does the work for you.

For this specific problem, I think that for any algorithm you give someone will be able to come up with input that makes it behave badly. So I would try to find what are *typical* inputs and design a solution for those.

With the given restrictions, if the numbers are unique, I’d probably turn the number into a bit array, so to find all multiples of k only max / k numbers need checking. If k is tiny, check the elements of the original array. If k = 1 return the number of array elements. And cache the results.

For example to count the multiples of 1,234 you’d check if bits 1,234, 2,468, 3,702 etc are set which would be 800 checks or so. If large numbers are allowed the solution would be awful.
> 1 votes

# Answer
I think of divisibility mostly in terms of decomposition into prime factors: to be divisible by a query integer $q$, an integer $a\_i$ has to be divisible by at least the same power of each prime in $q$s decomposition.
Divisibility by different primes is independent: I think of this (divisibility of integers from a set that can be preprocessed) as a geometric problem of unlimited dimensions.

I do not see a better/cheaper solution for the second form ("batch problem": multiple queries are known right from start) of your problem than for the form stated at the top of your question (single queries).

---

With the example from the question:

> Input canonical representation (exponents of primes in ascending order, trailing zeroes omitted)
> 2 1
> 4 2
> 9 0 2
> 15 0 1 1
> 21 0 1 0 1
> 20 2 0 1
> Queries - multiples are lines from Input where no exponent is less than for the current query:
> 2 1 2, 4, 20
> 3 0 1 15, 21
> 5 0 0 1 15, 20

If I wanted to get the count of multiples *fast*, I'd explore keeping summary information like *count of numbers divisible by $2^1, 2^2,$*
Should work like a charm for powers of primes.
What about divisibility by a compound number, say, 6? Sure there are no more multiples of 6 than the minimum of even numbers and numbers divisible by three, but even given an abundance of both, there doesn't have to be a single multiple of 6.
> 1 votes

---
Tags: algorithms, algorithm-analysis, data-structures, discrete-mathematics
---


# Question
Title: Simplifying the Boolean expression $A + \bar{A}\bar{B}$?
So I'm trying to simplify the Boolean expression (1) $A + \bar{A}\bar{B}$.

I noticed that by Karnaugh maps this is equivalent to $A+\bar{B}$, and I also noticed that if I take the complement of (1), I get ~(1)= $\bar{A}(A + B) = \bar{A}A + \bar{A}B = \bar{A}B$, so then taking complements again yields (1) = $A + \bar{B}$.

But this feels very ad hoc to me, and makes me feel like I'm missing some key point about how to simplify this expression more systematically.

Any thoughts appreciated.

Thanks.

# Answer
There is a **Law of Distributivity** of Boolean operation $\lor$ (*disjunction*, which is sometimes denoted by $+$) over Boolean operation $\land$ (*conjunction*, which is sometimes simply omitted): $$x \lor (y \land z)= (x \lor y)\land(x \lor z)$$ So, in your case: $$A \lor (\lnot A \land \lnot B) = (A \lor \lnot A) \land (A \lor \lnot B) = A \lor \lnot B$$ For more information please see: Boolean Algebra.
> 4 votes

# Answer
To simplify small expressions, you *will* use ad hoc methods (in larger expressions, this often lets you achieve \_some _ simplification).

For larger cases, you could write or use existing software, which tries to find the “simplest” expression equivalent to a given one, according to your definition of “simplest”. The runtime will grow fast. Actually the question whether an expression can be simplified to “false” is NP-complete (that is practically unsolvable for hard cases), and that is just one very special case of simplifying an expression.
> 0 votes

---
Tags: boolean-algebra
---


# Question
Title: Why companies that create native mobile apps are forced to make duplicate versions on other platforms?
I am not computer savvy, so forgive me for asking why companies that create native mobile apps are forced to make duplicate versions on other platforms. "Duplicate" means the "same", so it means those companies don't have to modify the original version of the native mobile app for other platforms. I am guessing "other platforms" refer to other types of smartphones ... The question is based on the following statement. Please let me know if I have posted on the wrong forum. Thank you!

"However, this type of app is expensive to develop because it is tied to one type of operating system, forcing the company that creates the app to make duplicate versions that work on other platforms."

# Answer
> 1 votes
Duplicate here refers to the functionality only.

Imagine you were making a row boat out of oak, or out of pine... not quite the same thing.

Android and iOS platforms in particular encourage you to program in different languages, Java or Swift, which can be very different for highly complex apps.

---
Tags: applications
---


# Question
Title: Why hasn't there been an encryption algorithm that is based on the known NP-Hard problems?
Most of today's encryption, such as the RSA, relies on the integer factorization, which is not believed to be a NP-hard problem, but it belongs to BQP, which makes it vulnerable to quantum computers. I wonder, why has there not been an encryption algorithm which is based on an known NP-hard problem. It sounds (at least in theory) like it would make a better encryption algorithm than a one which is not proven to be NP-hard.

# Answer
> 85 votes
Worst-case Hardness of NP-complete problems is not sufficient for cryptography. Even if NP-complete problems are hard in the worst-case ($P \ne NP$), they still could be efficiently solvable in the average-case. Cryptography assumes the existence of average-case intractable problems in NP. Also, proving the existence of hard-on-average problems in NP using the $P \ne NP$ assumption is a major open problem.

An excellent read is the classic by Russell Impagliazzo, A Personal View of Average-Case Complexity, 1995.

An excellent survey is Average-Case Complexity by Bogdanov and Trevisan, Foundations and Trends in Theoretical Computer Science Vol. 2, No 1 (2006) 1–106

# Answer
> 52 votes
There have been.

One such example is McEliece cryptosystem which is based on hardness of decoding a linear code.

A second example is NTRUEncrypt which is based on the shortest vector problem which I believe is known to be NP-Hard.

Another is Merkle-Hellman knapsack cryptosystem which has been broken.

Note: I have no clue if the first two are broken/how good they are. All I know is that they exist, and I got those from doing a web search.

# Answer
> 29 votes
I can think of four major hurdles which are not entirely independent:

* NP-hardness only gives you information about complexity *in the limit*. For many NP-complete problems, algorithms exist that solve all instances of interest (in a certain scenario) reasonably fast. In other words, for any *fixed* problem size (e.g. a given "key"), the problem is not necessarily hard just because it is NP-hard.
* NP-hardness only considers worst-case time. Many, even most of all instances may be easy to solve with existing algorithms. Even if we knew how to characterise the hard instances (afaik, we don't), we'd still have to find them.
* You need to have *huge* instances that are hard to solve. Searching for (products of) large prime numbers is easy in the sense that the search space is flat: one number is either suited or not. Imagine using graphs: out of all $2^{n(n-1)}$ graphs of size $n$ for large $n$, you have to find those that have nice properties.
* You need some kind of reversability. For example, any integer is uniquely described by its prime factorisation. Image we would want to use TSP as encryption method; given all shortest tours, can you (re)construct the graph they came from uniquely?

Note that I have no expertise in cryptography; these are merely algorithmic resp. complexity-theoretic objections.

# Answer
> 14 votes
Public-key cryptography as we know it today is built on one-way *trapdoor* permutations, and the trapdoor is essential.

For a protocol to be publicly secure, you need a key available to anyone, and a way to encrypt a message using this key. Obviously, once encrypted, it should be hard to recover the original message knowing only its cipher and the public key : the cipher must only be decipherable with some extra information, namely your private key.

With that in mind, it's easy to build a *primitive* crypto system based on any one-way trapdoor permutation.

1. Alice gives the one-way permutation to the public, and keep the trapdoor to herself.
2. Bob put its input in the permutation, and transmit the output to Alice.
3. Alice uses the trapdoor to invert the permutation with Bob's output.

The difficulty now is to find actual one-way trapdoor permutations, and there's a bunch of function we think are good candidates (RSA, Discrete logarithm, some variations on the lattice problem). However, if we can find with certainty a one-way function, then we also prove that $\mathsf{P} \ne \mathsf{NP}$, so actually proving that a function is one-way is intractable.

The other way around, if we prove that $\mathsf{P} \ne \mathsf{NP}$, we also prove that there is a class in between called $\mathsf{NPI}$ (intermediate), of the problems in $\mathsf{NP}$ but not $\mathsf{NP}$-hard. Some good candidates for problems in $\mathsf{NPI}$ are also the candidates for one-way permutations, as we've not yet been able to prove that they are $\mathsf{NP}$-hard.

So to answer your question, we don't use $\mathsf{NP}$-hard problems because we need one-way permutation with trapdoors, and these special functions *probably* live in a class between $\mathsf{NP}$ and $\mathsf{NP}$-hard.

# Answer
> 1 votes
Just to give a heuristic argument, based on practical experience.

Almost all instances, of almost all NP-complete problems, are easy to solve. There are problems where this isn't true, but they are hard to find, and it's hard to be positive you have found such a class.

This has come up in practice several times when people try to write random problem generators for some famous NP-complete class, such as Constraint Programming, SAT or Travelling Salesman. At some later date someone finds a method of solving almost all the instances that random generator produces trivially. Of course, if that was the case for an encryption system we would be in serious trouble!

# Answer
> 0 votes
Merkle-Hellman cryptosystems are based on binary knapsack problems (subset sum).

---
Tags: complexity-theory, np-hard, encryption, cryptography
---


# Question
Title: If an NP complete problem 'A' is polynomial time reducible to another problem 'B' does that imply 'B' is also NP complete?
The following question was asked on a quiz:

> Let S be an NP-complete problem, and Q and R be two other problems (that we don't know much about). If we now know that Q is polynomial time reducible (i.e., can be reduced in polynomial time) to S, and S is polynomial-time reducible to R, which one of the following statements can be deduced from the above information?

It was asked to choose a correct option out of these four options:

> 1. R is NP-complete
> 2. R is NP-hard
> 3. Q is NP-complete
> 4. Q is NP-hard

# Answer
> 3 votes
All that you know is that R is NP-hard.

To show that R is NP-complete, you need to show that it is in NP. But that is not automatically true.

As an example, let S be the question "Is there a path of cost at most `l` that visits every node of a graph `G`?" and R be the question, "What is the cheapest path that visits every node of a graph `G`?" These are variants of the Traveling Salesman problem. S is in NP while R is believed not to be. The issue being that given a proposed solution, you just add it up for S. But for R, there is no known polynomial way to verify that you actually have the best path.

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


# Question
Title: Combinations and Permutations of M sets of distinct items?
I'm wokring on this problem for a while. I want to know:

1. The correct name of this problem, so I can look it up in textbooks\online.

Here is the problem descirption:

The **(un-ordered)** combinations to be generated are:

* of 1 item size: {a1}, {a2} .... {c4}
* of 2 items size: {a1, b1}, {a1, b2} ... {b2, c4}
* of 3 items size: {a1, b1, c1}, ... {a3, b2, c4}

**The question is:** *Given any number of sets **M** where each set has distinc number of items, How many (un-ordered) combinations are there of size 1, 2, ..., up to M? And how to generate those combinations?*

# Answer
> 2 votes
Let's solve your example question first. Say, we want to know the number of combinations of size 2 possible from $A, B, C$. This would be equal to

1. for each element in $A$, pair it with each element in $B$. This gives us $|N\_A||N\_B|$ combinations of size 2.
2. for each element in $A$, pair it with each element in $C$. This gives us $|N\_A||N\_C|$ combinations of size 2.
3. for each element in $B$, pair it with each element in $C$. This gives us $|N\_B||N\_C|$ combinations of size 2.

In total, this gives us as $ |N\_A||N\_B|+|N\_A||N\_C|+|N\_B||N\_C| = 3\times2 + 3\times4 + 2\times4 = 26$

What we have done above is to take all possible combinations of the sets in $M$ (set combinations of size 2 are $AB, AC, BC$), taken the product of all their sizes, and finally added them up.

In general, given $n$ sets in $M$, and we want to know the number of $k$ sized combinations. The high-level algorithm would be as follows

```
for each k-sized set combination of sets in M
  multiply the sizes of all the sets in the k-size set combination
  add this product to the final result

```

This can be written briefly as $$ \sum\_{\substack{S \subseteq M\\\|S|=k}}\prod\_{X\in S}{|X|}$$

Now, to generate all unordered combinations of size $k$, we follow the same steps as the above algorithm, but instead of taking the product of set sizes, we perform a cross product on all the sets in each $k$-size set combination.

```
Combinations(M,k):
  if |M| == 1
    return { {e} | e in any set of M }

  M[1] = first set in M

  if |M| > k
    Result = Combinations(M\{M[1]} ,k)
  else
    Result = {}

  Temp = Combination(M\{M[1]},k-1)

  for each element e in M1:
    make a copy of Temp called Dummy
    to each set in Dummy, add e
    add all the elements in Dummy to Result

  return Result

```

---
Tags: algorithms, combinatorics, permutations
---


# Question
Title: Proof with induction even number of letter
I have to proof that in a word $w$ the number of the letter d is always even.

Let $L \subsetneq \Sigma^\*$ be a language over the alphabet $\Sigma = \\{a,b,c,d\\}$ such that a word $w$ is in $L$ if and only if it is $a$ or $b$ or of the form $w = ducvd$ where $u$ and $v$ are word of $L$.

Examples:

$dacad$, $ddacbdcad$, $dddbcbdcdbcbddcad$

I know there are three cases:

1. $|w| = 0$ the number of the letter d is zero and even
2. $|w| = 1$ and $w = a$ or $w = b$ same as number 1
3. $|w| = 5$ and $w = ducvd$ the number of letter d is even

I know how induction works, but I don't know to write the base, hypothesis and step. I think it works with the length of $w$. Does somebody have a hint?

# Answer
> 1 votes
The proof is by induction on the length of $w$. If $|w| \leq 2$ then necessarily $w = a$ or $w = b$, and in both cases $w$ doesn't contain any $d$'s. If $|w| \geq 3$ then necessarily $w$ is of the form $ducvd$, where $u,v \in L$ are shorter words. By induction, each of $u,v$ contains an even number of $d$'s. It follows that $w$ also contains an even number of $d$'s: if $u,v$ contain $2s,2t$ many $d$'s (respectively), then $w$ contains $2s+2t+2=2(s+t+1)$, which is also even.

# Answer
> 0 votes
Alternatively show for every k: There is no w containing 2k+1 d’s.

---
Tags: formal-languages
---


# Question
Title: The upper bound on a Nondeterministic Finite Automata's configurations number
In **"Engineering: A Compiler"** 2nd ed. by Cooper and Torczon, in **2.4.1 "Nondeterministic Finite Automata"** of Chapter 2,
section **"Equivalence of NFAs and DFAs"**

discusses the upper bound of a NFA's configurations number.

Here

* NFA stands for Nondeterministic Finite Automata
* DFA stands for Deterministic Finite Automata

NFA is a is a five-tuple $(S, \Sigma, \delta, s\_0 , S\_A)$, where

* $S$ is the finite set of states in the recognizer, along with an error state $s\_e$.
* $\Sigma$ is the finite alphabet used by the FA. Typically, $\Sigma$ is the union of the edge labels in the transition diagram.
* $\delta(s,c)$ is the FA's transition function. It maps each state $s ∈ S$ and each character $c \in \Sigma$ into some next state. In state $s\_i$ with input character $c$, the FA takes the transition $s\_i \xrightarrow{\text{c}}\delta(s\_i ,c)$.
* $s\_0 \in S$ is the designated start state.
* $S\_A$ is the set of accepting states, $S\_A \subseteq S$.

A **configuration** of a NFA is defined as follows

> Each time the NFA must make a nondeterministic choice, the NFA clones itself to pursue each possible transition. Thus, for a given input character, the NFA is in a specific set of states, taken across all of its clones.
>
> In this model, the NFA pursues all paths concurrently. At any point, we call the specific set of states in which the NFA is active its **configuration**.
>
> When the NFA reaches a configuration in which it has exhausted the input and one or more of the clones has reached an accepting state, the NFA accepts the string.

Given the definitions above, the books states

> Consider the state of an NFA when it has reached some point in the input string. \[...\] the NFA has some finite set of operating clones.
>
> The number of these configurations can be bounded;
>
> for each state, the configuration either includes one or more clones in that state or it does not. Thus, an NFA with $n$ states produces at most $\lvert\Sigma\rvert^n$ configurations.

**My question.**

*Please explain in as much details as possible, how $\lvert\Sigma\rvert^n$ is derived.*

I need help, because while trying to follow the book's reasoning, I get lost right after this sentence

> for each state, the configuration either includes one or more clones in that state or it does not.

This sounds like the upper bound on the number of configurations should be $2^n$, but instead the book gives $\lvert\Sigma\rvert^n$ bringing in $\Sigma$ seemingly out of the blue.

# Answer
> 2 votes
Remember that:
We can view a nondeterministic computation as a directed acyclic graph of configurations indexed by time.

I have a guess that in your eyes:
$2^n$ for both, one directs itself and one directs others and *at most* every has the $\Sigma$ chance to go next state, maybe to itself, maybe the other state, so from $1$ to $n$ state, an NFA produces at most $\mid\Sigma\mid^n$ configurations.

Here are more details: http://www.cse.msu.edu/~torng/360Book/NFA/

---
Tags: finite-automata, parsers, upper-bound
---


# Question
Title: Does the Kleene star distribute over each element? (0+1)* = 0* + 1*?
Does the Kleene star distribute over each element? Is this true: $(0+1)^\* = (0^\* + 1^\*)$?

# Answer
> 3 votes
You can verify that $010$ is in $(0+1)^\*$ but not in $(0^\* + 1^\*)$. Therefore, $(0 + 1)^\* \neq (0^\* + 1^\*)$.

# Answer
> 2 votes
I believe this makes more sense:

$$ (0+1)^\* = (0^\*1^\*)^\* $$

$0^\* + 1^\*$ would limit the amount of strings covered.

---
Tags: regular-languages, regular-expressions, discrete-mathematics
---


# Question
Title: Existence of d-regular subgraphs in a k-regular graph
The claim is as follows: Let's say we have a $k$-regular simple undirected graph $G$ on $n$ vertices. Then, does $G$ then always have a $d$-factor for all $d$ satisfying $1 \le d \lt k$ and $dn$ being even.

I think its true, since we can construct a

* $k+1$-regular graph from $G$ by adding $\frac{n}{2}$ edges for even $n$ or
* $k+2$-regular graph from $G$ by adding $n$ edges for odd $n$

And the converse for the above. We can construct a $k$-regular graph on $n$ vertices by

* removing $\frac{n}{2}$ edges from a $k+1$-regular graph for even $n$.
* removing $n$ edges from a $k+2$-regular graph for odd $n$.

Hence, using the converse argument, we can say that the original claim is true, since from a $k$-regular graph $G$ we can construct

* $1$-factor, $2$-factor, ... $k-1$-factor for even $n$ or
* $2$-factor, $4$-factor, ... $k-2$-factor for odd $n$

Is my argument correct or is there any flaw in this argument?

# Answer
Your conjecture is false. There are regular graphs with an even number of vertices yet without a 1-regular subgraph. See this question on Mathematics.

The complement of such a graph gives a counterexample to your claim that you can always add a perfect matching to increase the regularity (when the number of vertices is even).

In the bipartite case, however, your conjecture is true. Any $k$-regular bipartite graph can be decomposed into $k$ perfect matchings. This follows from Hall's theorem.
> 2 votes

---
Tags: graphs
---


# Question
Title: Subset Sum: reduce special to general case
Wikipedia states the subset sum problem as finding a subset of a given multiset of integers, whose sum is zero. Further it states that it is equivalent to finding a subset with sum $s$ for any given $s$.

So I believe as they are equivalent, there must be a reduction in either side. The one from $s$ to zero is trivial by setting $s = 0$. But I had no luck finding a reduction from zero to $s$, i.e. given a set of integers $A$, construct a set of integers $B$ containing a subset with sum $s$ (for any $s$), if and only if there is as subset of $A$ with sum zero.

Can you give me some pointers?

# Answer
> 12 votes
You actually already have a reduction from special to general. By setting $s=0$, you are basically using the general algorithm to solve the special problem.

For the other way round (i.e. a reduction from general to special):

Suppose you are given a set $S = \\{x\_1, \dots, x\_n\\}$ and a number $K$ and you have to determine if there is some subset of $S$ which sums to $K$.

Now you want to solve this problem, given an algorithm for the case where you can determine if some subset sums to $0$.

Now if $x\_i \gt 0$, we have an easy reduction: $S' = \\{x\_1, x\_2, \dots, x\_n, -K\\}$.

$S'$ has a subset of sum $0$ iff $S$ has a subset of sum $K$.

The problem occurs when we can have $x\_i \le 0$ for some of the $i$.

We can assume that $K \gt 0$ (why?).

Suppose the sum of the positive $x\_i$ is $P$ and the negative $x\_i$ is $N$.

Now construct a new set $S' = \\{y\_1, y\_2 \dots, y\_n\\}$ such that

$y\_i = x\_i + M$ where $M = P + |N| + K$.

Each $y\_i \gt 0$.

Now run the zero-subset-sum algorithm on the sets

$ S' \cup \\{-(K+M)\\}$

$ S' \cup \\{-(K+2M)\\}$

$ S' \cup \\{-(K+3M)\\}$

$\dots$

$ S' \cup \\{-(K+nM)\\}$

It is easy to show that if $S$ has a subset of sum $K$, then at least one of the above sets has subset of sum zero.

I will leave the proof of the other direction to you.

# Answer
> 0 votes
Aryabhata's answer can be fixed up by making use of the fact that we can multiply all the numbers by some large $c$, and then add something small to each one to act like a "presence tag", and then supply some extra numbers that will allow us to get to zero *if* we could get to $cK$ without them. Specifically, we will use $c=2(n+1)$ and 1 as the presence tag.

Given an instance $(S = \\{x\_1, \dots, x\_n\\}, K)$ of the general problem with target value $K$, we will create an instance of the specific problem (with target value 0) that contains:

* $Y = \\{y\_1, \dots, y\_n\\}$, where $y\_i = 2(n+1)x\_i + 1$.
* The number $z = -2K(n+1)-n$.
* $n-1$ copies of the number 1, to be referred to as "pull-up" numbers.

I'll assume as Aryabhatta does that $K$ is positive. (Since it's been 6 years, I'll answer his exercise for the reader: the reason we can do this is that if we swap the signs of *all* numbers in an instance of the general problem, including $K$, then we wind up with a new, equivalent problem instance. That means that an algorithm to solve positive-$K$ instances suffices to solve any problem -- to solve an instance with negative $K$, we could perform this sign-swap, run that algorithm, and forward its answer on as the answer to the original question. And of course if $K=0$ then we don't need to perform any transformation of the general case into the special case at all!)

First let's show that **a YES answer to the given instance of the general problem implies a YES answer to the constructed instance of the special problem.** Here we can assume that some solution $\\{x\_{j\_1}, \dots, x\_{j\_m}\\}$ to the general problem exists: that is, this nonempty collection of $m$ numbers sums to $K$. So if we take the corresponding $y$-values $\\{y\_{j\_1}, \dots, y\_{j\_m}\\}$ into our solution to the constructed instance, they will sum to $2K(n+1)+m$. We can then choose to include $-2K(n+1)-n$ in the solution, leaving us with a sum of $m-n$. Since $1 \le m \le n$, this in the range $\[-n+1, 0\]$, which we can successfully pull up to 0 by including some subset of the pull-up numbers.

Now let's show that **a YES answer to the constructed instance implies a YES answer to the original given instance.** This is where the multiplication by $2(n+1)$ becomes important -- it is what allows us to be certain that the extra numbers we included can't "do too much".

Here we may assume that some solution $\\{y\_{j'\_1}, \dots, y\_{j'\_{m'}}\\}$ to the constructed instance exists: that is, this nonempty collection of $m'$ numbers sums to 0. By the problem requirements, this solution contains at least one element. Further, it must contain at least one element from $Y$, since without this it is impossible to reach a total of 0: If only pull-up numbers are present, then the sum is necessarily in the range $\[1, n-1\]$ (note that in this case *at least one* pull-up number must be present, and all of them are strictly positive, so the sum cannot be 0); while if the solution consists of just $z$ and some pull-up numbers, then the total is necessarily negative because $z = -2K(n+1)-n \le -n$ and the most that the pull-up numbers can increase the sum by is $n-1$.

Now suppose towards contradiction that the solution does not contain $z$. Every element in $Y$ consists of two terms: A multiple of $2(n+1)$, and a +1 "presence tag". Notice that the +1 term on each of the $n$ elements of $Y$ increases the sum by 1 if that element is chosen, as does each of the up to $n-1$ pull-up numbers that are chosen, so the total contributed by these 2 sources to any solution is at least 1 (because we established in the previous paragraph that at least one element of $Y$ must be chosen) and at most $n + n-1 = 2n-1$. In particular, this implies that the sum of these two sets of terms, *when taken modulo $2(n+1)$*, is nonzero. Under the assumption that the solution does not contain $z$, the only other components in this sum are the multiples of $2(n+1)$ contributed by the chosen members of $Y$, which do not affect the value of the sum when taken modulo $2(n+1)$. Thus the sum of all terms in the solution, when taken modulo $2(n+1)$, is nonzero, meaning it cannot be equal to the target sum of 0, meaning it cannot be a valid solution at all: we have found a contradiction, meaning that it must be that $z = -2K(n+1)-n$ is present in every solution after all.

So every solution contains $z$. We know that

$(-2K(n+1) - n) + \sum\_{i'=1}^{m'} (2(n+1) x\_{j'\_{i'}} + 1) + \sum {\text{pull-ups}} = 0$,

and we can rearrange the terms:

$-2K(n+1) + \sum\_{i'=1}^{m'} (2(n+1) x\_{j'\_{i'}}) - (n + \sum\_{i'=1}^{m'} 1 + \sum {\text{pull-ups}}) = 0$

$-2K(n+1) + \sum\_{i'=1}^{m'} (2(n+1) x\_{j'\_{i'}}) - (n + m' + \sum {\text{pull-ups}}) = 0$

$2(n+1)(-K + \sum\_{i'=1}^{m'} x\_{j'\_{i'}}) - (n + m' + \sum {\text{pull-ups}}) = 0$.

Since the sum is 0, it must remain 0 when taken modulo $2(n+1)$, which implies that we can discard all terms containing a multiple of $2(n+1)$ to obtain the new equation

$-(n + m' + \sum {\text{pull-ups}}) = 0$.

This can be directly substituted back into the previous equation to get

$2(n+1)(-K + \sum\_{i'=1}^{m'} x\_{j'\_{i'}}) = 0$.

Finally, dividing both sides by $2(n+1)$ leaves

$-K + \sum\_{i'=1}^{m'} x\_{j'\_{i'}} = 0$,

which yields a solution to the original general problem instance.

---
Tags: complexity-theory, reductions, np-hard
---


# Question
Title: Does there exist any unrelativized separation between a quantum complexity class and a classical one?
I'm familiar with results of relativized separation for BPP-BQP, BQP-PH and NPC-BQP. I'm also aware that while e.g. Factoring is not believed to be in BPP, it hasn't been proven and so we're not quite near proving BQP!=BPP.

My question is, do we have any certain, theoretical, unrelativized proof that quantum computers are "superior" to classical one on any specific problem - Where here, I define superior to include any sort of runtime complexity superiority, so e.g. a quadratic improvement would qualify in this regard.

I'd expect Grover's algorithm to qualify for this criterion - But despite being supposedly "obvious", I'm not sure if it's been proven that classical computers can't solve it in sqrt(n) time as well, in a non-black-box model (i.e. unrelativized).

# Answer
Separations are known for constant-depth circuits. One recent result in this area is due to Bravyi, Gosset, and Koenig (see also the journal version in *Science*). Recent independent works by Bene Watts, Kothari, Schaeffer, and Tal, Coudron, Stark and Vidick, and Le Gall strengthened the hardness result for classical circuits from worst-case hardness to average-case hardness.
> 2 votes

---
Tags: complexity-theory, quantum-computing, oracle-machines
---


# Question
Title: Understanding memory mapping conceptually
I've already read several blogs and questions on stack exchange, but I'm unable to grasp what the real drawbacks of memory mapped files are. I see the following are frequently listed:

1. You can't memory map large files (\>4GB) with a 32-bit address space.

QUESTION #1: Why? Isn't that the whole point of virtual memory? If a file is greater than 4GB, it may cause trashing by swapping out some memory mapped pages, but why is there a limitation?

2. If the application is trying to read from a part of the file that is not loaded in the page cache, it (the application) will incur a penalty in the form of a page-fault, which in turn means increased I/O latency for the operation.

QUESTION #2: Isn't this the case for a standard file I/O operation as well? If an application tries to read from a part of a file that is not yet cached, it will result in a syscall that will cause the kernel to load the relevant page/block from the device. And on top of that, the page needs to be copied back to the user-space buffer.

Is the concern here that page-faults are somehow more expensive than syscalls in general - my interpretation of what Linus Torvalds says here? Is it because page-faults are blocking =\> the thread is not scheduled off the CPU =\> we are wasting precious time? Or is there something I'm missing here?

3. Overhead of kernel mappings and data structures - according to Linus Torvalds. I won't even attempt to question this premise, because I don't know much about the internals of Linux kernel. :)
4. No support for async I/O for memory mapped files.

QUESTION #3: Is there an architectural limitation with supporting async I/O for memory mapped files, or is it just that it no one got around to doing it?

5. One drawback that I thought of was that if too many files are memory mapped, this can cause lower available system resources (memory) =\> can cause pages to be evicted =\> potentially more page faults. So some prudence is required in deciding what files to memory map and their access patterns.

QUESTION #4: Vaguely related, but my interpretation of this article is that the kernel can read-ahead for standard I/O (even without fadvise()) but does not read-ahead for memory mapped files (unless issued an advisory with madvice()). Is this accurate? If this statement is in-fact true, is that why syscalls for standard I/O maybe faster, as opposed to a memory mapped file which will almost always cause a page-fault?

# Answer
With memory-mapped files, a file is mapped to a pointer p, and byte #i of the file can be accessed through the pointer p+i. For each byte in the file, there must be an address available in the logical address space. With 32 bit, there are only 2^32 possible logical addresses, so 2^32 bytes in a memory mapped file that can be accessed at all.

You are confusing address space and RAM. A 64 bit computer with just 1 GB if RAM can memory map multi-terabyte files without problems. There will be lots of paging, but it will work. With a 32 bit computer, no chance.
> 1 votes

# Answer
Re #1: If your address space is 32 bits, you can address only 4GiB by pointers into memory. You can process larger files by e.g. reading the sequentially, or `lseek(2)` into it (note that usually `off_t` is a 64-bit type today).

Re #2: Yes, the operating system will read (part of) the file into memory for munging it. The offset into the on-disk file doesn't have to be limited to 32 bits. For quite some time now Unix/Linux handles "large files" with 64 bit file offsets, lately by default (in the beginning some incantation was needed to enable that).
> 0 votes

---
Tags: memory-management, virtual-memory, memory-access
---


title: Arithmetic operators and regex

text:
# Question
Title: Arithmetic operators and regex
Let $L$ be the language over the alphabet $\\{0, 1, 2, 3, (,), +, -, \*, /\\}$, $L$ is the set of operations with correctly formatted natural numbers. A single number is considered to belong to $L$.

2 - - 3 is an incorrect expression, 2 + 3 is correct, 2 + (-3) is correct. Is it possible to write a regular expression for this language? If not, why?

I think that it is not possible to write a regular expression for this language, because of the operator / we cannot write 2 / 0 for example and are more than a finite number combinations to make this possible. Is it correct?

# Answer
You haven't defined your language, but presumably $$ L \cap \[^\*0+0\](+0\])^\* = \\{ \[^n\[0+0\](+0\])^n : n \geq 0 \\}, $$ where I replaced parentheses with square brackets. The latter language is essentially $\\{a^nb^n : n \ge 0 \\}$ in disguise, and so isn't regular. It follows that $L$ isn't regular as well.
> 3 votes

---
Tags: regular-expressions
---


# Question
Title: Modifies Dijkstra’s Algorithm to find the maximum cost path
In a DAG and all weights are larger than 0. Is it possible to use a max heap to get the maximum cost?

# Answer
> 3 votes
This will not work. Consider

* (a)-4-\>(b)
* (a)-1-\>(c)
* (b)-2-\>(d)
* (c)-6-\>(d)

Looking for the max cost path from (a) to (d), the max heap will follow (a)-4-\>(b)-2-\>(d) and never explore the (a)-1-\>(c) edge.

See here for an alternative based on a topological sort.

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


# Question
Title: Describe construction of finite automata that accepts the language Double-Letter(L)
> Describe construction of finite automata that accepts the language Double-Letter(L), where Double-Letter(L) is in the language of words from L, except each letter in the word appears twice. So $abc\in L$ $\iff aabbcc \in $ Double-Letter($L$).
>
> For example if L={a,aa,ab,ba} then Double-Letter(L) = {aa,aaaa,aabb,bbaa}

My idea: Create states Q that are named s and ss where $s\in \Sigma$. Make states named ss accepting if $ss \in L$

FA illustrated for the example above

What next? is this a good approach? I can't think of the next step on how to construct this doubled DFA for ALL languages.

# Answer
The idea is to start with an automaton for $L$, and replace each transition labeled $\sigma$ by a path of length 2 both of whose edges are labeled $\sigma$. In order to make it a DFA, we also add a sink state. (This might be unnecessary in your definition of DFA.)

In more detail, suppose we start with a DFA $(Q,q\_0,\delta,F)$ for $L$ (here $Q$ is the set of states, $q\_0$ is the initial state, $\delta$ is the transition function, and $F$ is the accepting states). We construct a DFA whose set of states is $Q \cup Q \times \Sigma \cup \\{q\_{\mathit{sink}}\\}$, where $\Sigma$ is the alphabet. The initial state is still $q\_0$, and the accepting states are still $F$. The transition function $\delta'$ is defined as follows:

* $\delta'(q,\sigma) = (q,\sigma)$ (this is a member of $Q \times \Sigma$).
* $\delta'((q,\sigma),\sigma) = \delta(q,\sigma)$.
* $\delta'((q,\sigma),\tau) = q\_{\mathit{sink}}$ if $\tau \neq \sigma$.
* $\delta'(q\_{\mathit{sink}},\sigma) = q\_{\mathit{sink}}$ for all $\sigma \in \Sigma$.

A simpler way of proving that the regular languages are closed under Double-Letter is using regular expressions: given a regular expression for $L$, simply double each letter. This is a special case of closure under homomorphism and regular substitution.
> 1 votes

# Answer
This a hand drawn solution to your problem, I'll explain the transitions,

Before you see the diagram, note that those are not 2 different DFAs, but I have drawn one more transition of states q1, q3, q5 to make the image more clear, as it is already very messed up.

q0 is the start state, machine has not seen anything until now.

On scanning the first symbol, suppose, it turns out to be 'a'

d(q0, a) -\> q1 (d is the transition function)

machine is in q1 now.

If it sees another 'a' it will reach q2 which CAN BE the final state,

else it will reach q7 from where it will never reach any final state because 'a' has not repeated.

from q2, if machine see another 'a' it will go back to q1 else it will go to q3 on seeing a 'b' or q5 on seeing a 'c'

Same thing goes on for 'b' and 'c'

After scanning the complete string, if the machine is in final state then the string is in the language else, it is not in the language.

This assumes that the empty string epsilon is not in Double-Letter(L)

In that case q0 will be also be a final state.
> 0 votes

---
Tags: automata
---


title: support vector machine values

text:
# Question
Title: support vector machine values
Does anybody knows how to calculate w1 and w2 and b . I have the formula but I have no idea where those numbers come from . my question has solution so it is not a home work because the solution of question is included I only want to learn how the numbers come from .

# Answer
> 0 votes
From your figure, assume the orange is $x\_1=mx\_2+n$, then substituting point $(5,5)$ or $(9,1)$ will give you: $x\_2=-x\_1+10$. Similarly, you can know that the blue line is $x\_2=-x\_1+7$. Then the dotted line in the middle (which is exactly the separating hyperplane) is \begin{align} &x\_2=\frac12((-x\_1+10)+(x\_2=-x\_1+7))=x\_2=-x\_1+8.5\\ \Longrightarrow\\; &x\_2+x\_1-8.5=0\\ \Longrightarrow\\; &w\_1=1,w\_2=1,b=-8.5. \end{align}

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