# Question
Title: finding a greedy algorithm that maximizes total energy of fruits subject to expiry dates
> This problem is based off of the following problem on stack overflow: https://stackoverflow.com/questions/64797299/greedy-algorithm-to-maximize-score. The second answer is incorrect because the answer $\[3,4,1,6\]$ does not satisfy the constraint that games must be played at or before their deadline, and game $1$ is played on day $3$, after its deadline of day $2$. The first answer doesn't provide pseudocode and I'm not sure about the running time for the improved approach.

> **Here is the problem**: There are $n$ fruits, and each has an associated energy level, stored in the array e\[1...n\]. Also, each fruit has an expiry date, stored in the array d\[1...n\]. Fruit i must be picked up before d\[i\] days from today. Today is 0 days from today. Both e\[1...n\] and d\[1...n\] only store positive values. A person wishes to maximize the total energy of the fruits they can take subject to the constraint that they take at most one fruit per day.

> **How would one design and prove a greedy algorithm (or a dynamic programming algorithm) for this problem that runs in time $O(n\log n)$?**

> **If possible, could the algorithm avoid using disjoint set forests?** It can be similar to the fast implementation of the algorithm described in CLRS (problem 16-4) that is used to solve this problem: A task-scheduling problem as a matroid (CLRS book), but I'd like to have a more detailed description of how the faster method involving disjoint set forests works.

I've found an algorithm that works (at least for the many tests I've done) in $O(n^2)$ time. It essentially involves computing the maximum energy that can be obtained assuming $i$ days have passed for $0\leq i\leq n-1$. Since it may update previous selections, it is arguably not a greedy algorithm.

# Answer
This problem is basically the problem of unit-time job sequencing with deadlines and profits as appeared on Geeksforgeeks, if we consider each fruit with its expiry date and energy as a one-day job with corresponding deadline and profit.

### Basic idea

The basic ideas to solve this problem are

* A fruit with higher energy level is prioritized over another fruit with lower energy level, and
* a fruit should be picked up on the latest day among the remaining available days so as to leave more available days for fruits with more stringent expiry dates.

### A greedy algorithm

1. Let the total energy be 0.
2. Obtain a sorted list of all fruits. A fruit with higher energy level precedes another fruit with lower energy level.
3. For each fruit $f$ in the sorted list, try finding $d$, the latest available date before the expiry date of $f$.
    * If there is no such date, do nothing (this fruit is ignored).
    * Otherwise, pick up this fruit on date $d$. Add the energy level of $f$ to the total energy. Mark date $d$ as unavailable.
4. Return the total energy.

### Proof of correctness

**Agreement(k), $0\le k\le n.$** There is an optimal scheduling that agrees with the algorithm on the scheduling of the first $m$ fruits (in the sorted list of all fruits) at steps 3.

The correctness of the algorithm is the proposition Agreement(n). Let us prove Agreement(k) for all $k$.

**Proof**. The base case, when $k=0$, is of course correct.

As the induction hypothesis, assume the proposition is correct for $k$, i.e., there is an optimal scheduling $\mathcal O$ that agrees with the algorithm on the scheduling of the first $k$ fruits.

Suppose the algorithm has just finished processing the first $k$ fruits at step 3. Consider the next iteration of step 3, when the next fruit, $g$ is processed.

* If there is no available date before the expiry date of $g$, the algorithm will not pick up $g$. This is what $\mathcal O$ has to do as well.
* Otherwise, the algorithm will pick up fruit $g$ on date $d$, the latest available date before the expiry date of fruit $g$.
    + If $\mathcal O$ does not pick up any fruit on date $d$,
        - If $\mathcal O$ does pick up $g$, modify $\mathcal O$ so that $\mathcal O$ pick up $g$ on date $d$.
        - Otherwise, $\mathcal O$ does not pick up $g$. Modify $\mathcal O$ so that $\mathcal O$ picks up $g$ on date $d$, which will increase the total energy, which is impossible. So this case cannot happen.
    + Otherwise, $\mathcal O$ picks up some fruit $g'$ on date $d$. Note that $g'$ cannot be one of the first $k$ fruits.
        - If $g'$ is $g$, we are done.
        - Otherwise, $g'$ is not $g$.
            * If $\mathcal O$ pick up fruit $g$ on some date $d'$, modify $\mathcal O$ so that $\mathcal O$ picks up $g$ on date $d$ and picks up $g'$ on date $d'$. This modification is valid since both $g$ and $g'$ expires later than date $d$ and date $d'$ must be earlier than date $d$.
            * Otherwise $\mathcal O$ does not pick up fruit $g$. Modify $\mathcal O$ so that $\mathcal O$ picks up $g$ instead of $g'$ on date $d$. Since the list of fruits are sorted primarily by energy level, the energy level of $g$ is no less than that of $g'$. So after modification, $\mathcal O$ should be optimal still.

In all cases, $\mathcal O$ with possible modification is an optimal scheduling that agrees with the algorithm on the scheduling of the first $k+1$ fruits. $\quad\checkmark$

### Implementation with $O(n\log n)$ time-complexity

* Use a sorting algorithm with $O(n\log n)$ time-complexity such as merge sort to sort all fruits.
* How can we track available days and find some particular available day?
    + We can use a balanced binary search tree where each node represents some consecutive available days.
    + We can also use disjoint-set data structure (DSDS). Make a DSDS out of the first $n$ days. Maintain a partition of the set where each part consists of some consecutive days such that the only available day among them is the earliest one. Initially each day constitutes its own part of the partition. Whenever a day is used to pick up a fruit, the two parts near that day are combined into one part. Thanks to the power of path compression, the scheduling takes $O(n\log n)$ time.

### An implementation in Python

Here is an implementation in Python.

There is a minor tweak to boost performance. We will apply the greedy algorithm only for all fruits whose expiry dates are no less than $n$. All other fruits will be counted towards total energy. It is not hard to verify the correctness of this modification. (We do not have to use this tweak. We can just replace every expiry date that is no less than $n$ with $n$.)

```
def maximum_energy(n, energy, expiry):
    """Return the maximum total energy

    There are fruit 0, 1, ..., n-1.
    `energy[i]` is the energy level of fruit `i`
    `expiry[i]` is the expiry day of fruit `i`
    """
    fruits = [(energy[i], expiry[i]) for i in range(n) if expiry[i] < n]
    fruits.sort()  # ordered primarily by energy level

    # disjoint-set data structure (DSDS)
    # day `parent[d]` is some day no later than day `d`.
    # for any `d < n`, day `d` is available iff `parent[d] == d`.
    parent = {i: i for i in range(n)}  # all days are available
    parent[-1] = -1  # day -1 is yesterday

    def find(date):
        """ return the latest available day no later than `date`"""
        if parent[date] != date:
            parent[date] = find(parent[date])
            return parent[date]
        else:
            return date

    # customized union method of DSDS. `date` was available.
    def use(date):
        # day `date` is not available any more.
        parent[date] = find(date - 1)

    total_energy = sum(energy[i] for i in range(n) if expiry[i] >= n)
    while fruits:
        energy, expiry = fruits.pop()  # from the end
        pick_up_day = find(expiry - 1)
        if pick_up_day >= 0:
            total_energy += energy
            use(pick_up_day)

    return total_energy

def test():
    energy = [76, 66, 52, 51, 47, 23]
    expiry = [3, 2, 2, 4, 2, 1]
    max_energy = maximum_energy(6, energy, expiry)
    print("maximum energy:", max_energy)  # 245

test()

```
> 1 votes

# Answer
We use a greedy algorithm. Sort all fruits in decreasing order of energy. Let $d\_i$ be the deadline of the $i$-th fruit in the sorted array. Iterate through the fruits and schedule each fruit on the *latest* day less than or equal to $d\_i$ that has not been taken yet (if it exists). This can be implemented with, for example, a balanced binary search tree (BBST) in $O(n \log n)$. It can also be implemented with disjoint sets.

We provide a (very rough) sketch of a proof that the algorithm is optimal. Let the set of fruits be $S$ and the set of fruits the greedy algorithm takes be $G$. As elements have already been placed at the latest possible time, we cannot take an additional element $i \in S \setminus G$ without removing at least one element $j \in G$ (or else we would have already taken it). Moreover, removing an element $j \in G$ would only free up one space for a different element to take. Since this element would have had to be after $j$ in the order, it would have had less value then $j$ and so the answer would be no better.
> 1 votes

---
Tags: algorithms, time-complexity, greedy-algorithms, correctness-proof
---


# Question
Title: Doesn't the Riemman series theorem imply that any real number is computable?
For clarity, I'm talking about this theorem. My confusion lies at the fact that we can seemingly compute any real number by re-arranging a conditionally convergent infinite series, but apparently we can't actually compute every real number, so I'm not sure where I'm wrong.

# Answer
> 2 votes
Yes, one can permute the terms of a conditionally convergent series to get a series which converges to any real value. But the permutation needed to achieve any particular value may itself NOT be computable!

---
Tags: computability
---


# Question
Title: Finding 2 paths between 2 source-target pairs
Given an undirected graph $G=(V,E)$ and 2 sources $s\_1,s\_2$ and 2 targets $t\_1,t\_2$, I am looking to find paths $P\_1$ and $P\_2$, where $P\_i$ is a path from $s\_i$ to $t\_i$ and $P\_1$ and $P\_2$ are edge-disjoint.

One attempt is to find $P\_1$ by DFS or BFS, and then find $P\_2$ using a DFS/BFS with the remaining edges. Obviously, a solution found by this approach is a valid solution, but we may skip many valid solutions.

Another approach is by using integral flow. Adding a special source vertex and a special target vertex, and capacities of $1$ on the edges. But using this approach, one could get a path $s\_1 \rightarrow t\_2$ and $s\_2 \rightarrow t\_1$.

I get a feeling this problem might be NP-Hard, but even if it is, I'm looking for some heuristic approach or some approximation.

# Answer
The problem is known as the Edge disjoint path problem. It can be solved in polynomial time on undirected graphs.
> 2 votes

---
Tags: algorithms, graphs, shortest-path, approximation, network-flow
---


# Question
Title: Finding if input has exactly one pair and zero or more triplets
I was on a interview with an algorithm problem, which I cannot seem to solve nor find a solution already for it, but I'm really curious how it can be solved.

Here is the problem.

> You’re working on making some mini-games, and you’ve decided to make a simpler variant of the game Mahjong. In this variant, players have a number of tiles, each marked 0-9. The tiles can be grouped into pairs or triples of the same tile. A “complete hand” is defined as a collection of tiles where all the tiles can be grouped into any number of triples (zero or more) and exactly one pair, and each tile is used in exactly one triple or pair. Write a function that takes a string representing a player’s tiles in no particular order, and returns the string “COMPLETE” if the hand is complete, and “NOT COMPLETE” if it is not. Each tile may only be used in a single group (either a pair or a triple). All tiles must be used to complete a hand. There may be a pair and triples of the same tile. A single pair with no triples (ex: 99) is a valid hand. The input will only consist of characters 0-9.
>
> Examples
>
> These three hands would all return “COMPLETE”:
> 33344466 -\> 333 444 66 This hand can be grouped into a triple of 3s and 4s, and a pair of 6s
> 55555555 -\> 555 555 55 This hand can be grouped into two triples of 5s and a pair of 5s
> 22 -\> 22 This hand is a single pair of 2s (no triples are required)
>
> These three hands would all return “NOT COMPLETE”:
> 1357 This hand has tiles which cannot be formed into pairs or triples
> 335577 This hand has three pairs, a complete hand must have exactly one pair
> 666888 This hand has two triples, but no pairs.

Is this related to some math formula or some already know algorithm?

# Answer
> 2 votes
I don't know if this is really suited for *computer science* SE, perhaps better at Stackoverflow.

Just write a simple function that counts modulo 3 and then goes through all values:

```
from collections import defaultdict

def expressingx(game):
    counter = defaultdict(int)
    for e in game:
        counter[e] = (counter[e] + 1) % 3
    pairs = 0
    for k, v in counter.items():
        if v == 1:
            return "NOT COMPLETE"
        if v == 2:
            pairs += 1
    return "COMPLETE" if pairs == 1 else "NOT COMPLETE"

```

# Answer
> 0 votes
Yes, there is a simple algorithm.

1. Count the frequencies of characters 0-9 in that string.
2. Check whether all frequencies are divisible by 3 except exactly one frequency, which must have a remainder of 3 when divided by 2.
    * If yes, return "COMPLETE".
    * Otherwise, return "NOT COMPLETE".

For example, given "33344466", the frequencies are 3, 3, and 2. Return "COMPLETE".

For example, given "88888888", the only frequency is 8. Return "COMPLETE".

For example, given "335577", the frequencies are 2, 2, and 2. There are more than one frequency that have a remainder of 3 when divided by 2. Return "NOT COMPLETE"

---

Here is an implementation in C#.

```
StackExchange.CS148876.BatchTest();

namespace StackExchange {
    class CS148876 {
        public static bool IsCompleteHand(String tiles) {
            var counter = new int[10];
            foreach(char c in tiles) {
                counter[c - '0'] += 1;
            }

            var hasOnePair = false;
            foreach(var c in counter) {
                if (c % 3 == 1) return false;
                if (c % 3 == 2) {
                    if (hasOnePair) {
                        return false;
                    } else {
                        hasOnePair = true;
                    }
                }
            }
            return hasOnePair;
        }

        public static void Test(String tiles) {
            Console.WriteLine(tiles + ": " + (IsCompleteHand(tiles) ? "COMPLETE" : "NOT COMPLETE"));
        }

        public static void BatchTest() {
            Test("44433344466");
            Test("88888888");
            Test("22");
            Test("1357");
            Test("335577");
            Test("666888");
        }
    }
}

```

---
Tags: algorithms
---


# Question
Title: Minimum number of increment / decrement operations to make an array distinct?
I've been stuck on this problem for some time now..

Given an array A of size N that ranges between \[1..N\], a "move" is to increase or decrease an element (by 1). After each move the array must remain within \[1..N\]

I need to find the minimum number of move operations to make the array pairwise distinct.

# Answer
> 6 votes
First Observation:
Consider the result array, which contains $N$ distinct numbers between 1 and $N$.
Since there are only $N$ numbers between 1 and $N$, all those numbers must appear in the result array and no other numbers will appear.

Second Observation:
Consider $1$, the smallest number in the result array. Which number in $A$ should be changed to $1$ so as to incur the least cost? The smallest number of $A$.
Then consider $2$, the next smallest number in the result array. Which number among the remaining numbers in $A$ should be changed to $2$ so as to incur the least cost? The smallest of the remaining numbers in $A$.
Then consider $3$, the next smallest number in the result array. Which number among the remaining numbers in $A$ should be changed to $3$ so as to incur the least cost? The smallest of the remaining numbers in $A$.
And so on.
That is, we should change the $k$-th smallest number in the original array to $k$.

So, the algorithm is

1. sort $A$.
2. return the sum of $|A\[i\]-i|$, with $i$ ranging over $1..N$, assuming $A$ is 1-indexed.

---

**Exercise.** Given four numbers $a\_1\le a\_2$ and $b\_1\le b\_2$, prove $$|a\_1-b\_1| + |a\_2-b\_2| \le |a\_1-b\_2| + |a\_2-b\_1|.$$

# Answer
> 1 votes
Consider an array of all $1$'s. Then, the number of increments required (no decrements are required) is exactly

\begin{equation}\sum\_{i=1}^{N-1} i\end{equation}

This value is known to be equal to $\frac{N(N-1)}{2}=\Theta(N^2)$

Additionally, every array with size $N$ you can transform to be pair-wise distinct with $O(N^2)$ operations, so this value is the optimal possible number of operations required.

# Answer
> 1 votes
Here’s one possible approach that frames the problem as a minimum-cost bipartite matching. You know that each number in the array must end up holding one of the values from $1$ to $N$, and that no two numbers can get the same value. Therefore, you’re looking to assign the sequence $1, 2, \dots, N$ to the initial values in the array. And in particular, the cost of incrementing or decrementing the initial value $i$ to a target value $j$ is $|i - j|$. So construct a complete bipartite graph where one set of nodes is the original array values, another set of nodes is the target values $1, 2, \dots, N$, and the costs are defined as above. Find a minimum-cost perfect matching in that graph to see which number each array item should be changed to, then sum up those costs to get your total number of moves required.

# Answer
> 0 votes
Why not doing like bellow- As you are given an array A of size N and elements are ranged between \[1..N\], and you need to make the Array non duplicate array element, so, the final array will be A=\[1,2,...,N-1,N\] We can have the total of this N\*(N+1)/2 now given array can be like \[N,N,....N\](with length N) or \[1,2,2,..N,N\](with length N) or \[1,1,...1\](with length N). So we just need to make the array like A=\[1,2,...,N-1,N\]. We can just subtract the total count of given array which will give us the minimum number of moves.

```
        long total = (A.Length * (A.Length + 1)) / 2;
        long currentTotal = 0;
        for (int i = 0; i < A.Length; i++)
        {
            currentTotal += (long)A[i];
        }

        long minMove = Math.Abs(currentTotal - total);

```

---
Tags: algorithms, arrays
---


title: What is a pseudocode of try-catch?

text:
# Question
Title: What is a pseudocode of try-catch?
What is a pseudocode of try-catch? Is it this?

```
**Try** SOMETHING

If you succeed
    Do nothing special
Else, if you didn't succeed
    Do what's described in the **Catch** block
Anyway, either if you succeeded or failed
    Do what's described in the **Finally** block (if there is one)

```

## Update

I aim to find the pseudocode that will reflect the logic of every `try...catch` pattern in generally any modern abstract programming language (such as JavaScript, PHP, Python, etc.).

I might have found it already (the one above), and I basically ask for an affirmation.

# Answer
The pseudocode for `try`-`catch` is

```
try:
  〈some-code〉
catch:
  〈exception-handling-code〉

```

My point is that *pseudocode* is not a well-defined concept but an informal way of displaying algorithms. You thus have the freedom to adapt the pseudocode so that it reflects the control-flow and other features of the computation that you would like to present.
> 1 votes

# Answer
It's not really possible to express exception handling in pseudocode like that, because exception handling allows for non-local returns at arbitrary points. That is, even the line "try something" doesn't express what's going on.

So your pseudocode would really need to encompass the code of the "something" you're trying as well. The normal way to express this would be with a tagged union return type like the `Result` type in Rust, which can express both the desired return value and a "did not return properly" value. Even then, to properly demonstrate the behavior of the construct you'll need a type hierarchy or other way of determining whether a catch clause attaches to a particular exception, otherwise there's no way to demonstrate propagating the exception or the Finally block.
> 0 votes

# Answer
There is no formal standard for pseudocode. It is unlikely that you will find something that encompasses every possible exception pattern in every modern language. Instead, pseudocode is a form of informal communication. As long as it is clear to the reader, you are probably fine. I encourage you to focus on clarity of communication in your specific situation, not trying to identify a single pseudocode syntax that covers all possible cases that might ever arise.
> 0 votes

---
Tags: programming-languages, pseudocode
---


# Question
Title: What is the meaning of "You describe the result you want rather than specifying the steps required to get there." in Functional Programming?
One of the characteristics of functional programming is as follows:

> You’re describing the result you want rather than explicitly specifying the steps required to get there.

I found this quote at https://realpython.com/python-functional-programming/.

I don't really understand what is the meaning of this. Functional Programs still have to define steps to calculate something, there is no magic.

For example, a quicksort in Haskell looks something like this:

```
quicksort :: (Ord a) => [a] -> [a]
quicksort [] = []
quicksort (x:xs) =
    let smallerSorted = quicksort [a | a <- xs, a <= x]
        biggerSorted = quicksort [a | a <- xs, a > x]
    in  smallerSorted ++ [x] ++ biggerSorted

```

I don't really understand where the "you're describing the result" part is there. In imperative programming language I'd do pretty much the same thing. The only difference is that probably I wouldn't have a one-liner like `[a | a <- xs, a <= x]`, I'd have to do some loop. However, it's just syntax sugar, normally I'd create my own method/function that does exactly the same thing as `[a | a <- xs, a <= x]`. So, I don't consider that syntax to be some breakthrough, because it could some as a library in any other language.

Could you help me to understand the meaning of the quote in the title of this post?

# Answer
It's just someone's opinion. I don't find it super persuasive, for the reasons you've articulated. There are some situations where the code in Haskell is a bit closer to a mathematical specification than the code we'd write in C (say), but it seems like it is open to debate how common that is.

Not everything written on the Internet is 100% reliable or authoritative.
> 3 votes

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


# Question
Title: DFA Automaton with at least two 1s every four digits
How can I create a DFA automaton that will have every four digits (if they exist) at least two 1s for strings of languages with alphabet {0,1}? The expression *at least two 1s* seems easier than the expression *every four digits*

# Answer
> 3 votes
Create a DFA with 16 states, each corresponding to the last four letters possible.

For more details:

* the first three states will be special states with no turning back that will serve to count the number of $1$'s only in the three first letters;
* then you will navigate between states depending on the number of $1$'s read in the last four letters;
* each time you might reach a state describing zero or one $1$'s read in the last four letters, you can instead reach a non-final sink state that will loop on itself.

---
Tags: finite-automata
---


# Question
Title: How we transform IS inputs to VC (reduction)?
I would like to clarify something in my understanding of proving a problem to be NP-hard.
So in short, what I know is that:
"If I have a problem A that I want to prove that is NP-hard and another well -known NP-hard problem B and I can find a polynomial time reduction R such that if I answer A I know the answer to B as well for all the possible inputs to problem B , then I have proved that $B \leq\_P A$ which means that "A is harder or as hard as B which is known to be hard already" and therefore A is NP-hard."
What confuses me is that I see sometimes some proofs that show that two algorithmic questions (or at least that's what I think that they are proving) **are completely equivalent but not by transforming the inputs of one to another but by simply providing an argument that states that they are equivalent**.
What do I mean :
Let's say we know Independent Set (IS) is NP-hard and we want to show that vertex cover (VC) is NP-hard. If I understand well the well-known method is to claim this :
Let's say we want to find out whether an IS of at least k vectices exists in $G(V,E)$.
Now we take **this very same G (no transformation perfomed on it)** and ask the question : "Is there a vertex cover S of at most n-k vertices"?
If I find one and then delete the vertices of it the $|V|-|S|$ vertices that are left form an independent set. That's true because let's say they do not : then there is at least an edge $(u,v)$ such that $u,v \in V-S$ so it was "never really covered by our VC ".
But $|S|$ has at most n-k vertices and therefore the $V-S$ has at least $k$ vertices.
So what is the transformation here ? In the part we delete the vertices of $S$ we create an induced subgraph of G which is a transformation but I am not sure how it connects to "the whole method of proving this as NP-hard" .
(I hope my question makes sense I tried hard to put it into words)

# Answer
You can express this idea as a reduction.

IS consists of all pairs $\langle G,k \rangle$, where $G$ is a graph which contains an independent set of size at least $k$.

VC consists of all pairs $\langle G,k \rangle$, where $G$ is a graph which contains a vertex cover of size at most $k$.

To reduce IS to VC, take an instance $\langle G,k \rangle$ of IS to the instance $\langle G,n-k \rangle$ of VC, where $n$ is the number of vertices in $G$.

In this case there is also a reduction between the problem of finding a maximum independent set in a graph and the problem of finding a minimum vertex cover in a graph. Given a graph $G = (V,E)$, find a minimum vertex cover $S$, and output the independent set $V \setminus S$. This is a different type of reduction, and the problems are also of a different kind.
> 1 votes

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


# Question
Title: How does $xy^0z = λ$ not contradict $y \ne λ$ in the pumping lemma?
I have just started out theory of automata in my university and we are studying the pumping lemma. From what I have understood, the lemma states that $y \neq \lambda$ (where $\lambda$ is the empty string) and that $xy^iz$ (where $i \ge 0$), so if $i = 0$ then $y^0 = \lambda$ and the string is still accepted.

How do these not contradict each other? If $i = 0$, then $y$ becomes the empty string that is previously stated cannot be empty? Please explain.

# Answer
Here is an example. Consider the regular language consisting of all words over $\\{0,1\\}$ with an even number of $0$s and $1$s. It has a pumping constant of at most $4$.

Let's pick a word in this language: $0110$.

We can write it in the form $xyz$, where $x=\lambda$, $y = 0110$, $z = \lambda$.

Then:

* $xy^0z = \lambda$.
* $xy^1z = 0110$.
* $xy^2z = 01100110$.
* $xy^3z = 011001100110$.

And so on. All of these words are in the language, and in fact $xy^i z$ is in the language for all $i \ge 0$.

The pumping lemma states that for every regular language there is a constant $n$ such that every word in the language of length at least $n$ has such a decomposition $xyz$, where moreover $|xy| \leq n$ and $y \neq \lambda$.

As you can see, $x,y,z$ are the parts into which the original word is decomposed. When we look at $xy^iz$, the strings $x,y,z$ don't change at all.
> 0 votes

---
Tags: automata, finite-automata, pumping-lemma
---


# Question
Title: Why NP-Complete reduction is not reversible?
I have read the question asked here Is polynomial reduction reversible and the logic actually makes sense to me. In other words, if A is polynomially reducible to B, it means that A \<= B in terms of hardness.

However, when I thought more about the reduction process, I am confused. As far as I can understand, the NP-Complete reduction process is as follows:

(1) Find some NP-Complete problem (i.e. A), convert its inputs and output to the inputs and output of the problem we want to prove (i.e. B)

(2) Show that if A is YES, then B is YES

(3) Show that if B is YES, then A is YES.

Then I also read several classic reduction proofs, and here is my confusing part. In all the reductions I read, step (1) seems to be a "one-to-one mapping" between the inputs of A to the inputs B. For example, minimum set cover (MSC) to minimum vertex cover (MVC), edges in MVC is elements in MSC and nodes in MVC is sets in MSC. Since it's a "one-to-one mapping" of inputs A to inputs B, if we can convert the inputs of A to the inputs of B, then we can always convert the inputs of B to the inputs of A. In this case, isn't step (1) a reversible process? I am not sure if "one-to-one mapping" is the correct terminology, but the main idea I want to say is "the specific way" of mapping inputs of A to the inputs of B. Is there any reduction example that maps the input from A to the inputs of B, but the mapping is not reversible, i.e. can't map the inputs of B back to A?

What's more, no matter if we convert A to B or convert B to A, I think step (2) and step (3) above are still the same. Therefore, I am really confused about which part makes the NP-Complete reduction not reversible?

# Answer
Here is a concrete example. Let $A$ be the problem in which all instances are NO instances, and let $B$ be the problem with a unique YES instance $1$. The function $f(x) = 0$ is a reduction from $A$ to $B$, but there is no reduction from $B$ to $A$, since there is nothing we can map $1$ into.

The asymmetric part in the reduction is the reduction itself, which is not guaranteed to be invertible. As the example above shows, it doesn't have to be one-to-one either, though usually we can make it so.
> 2 votes

---
Tags: np-complete, reductions, np-hard, np, polynomial-time-reductions
---


# Question
Title: Proving loop invariant for a possibly nonterminating while loop
I started studying through Aho, Ullman - Foundations of Computer Science as a free time exercise. In the second chapter about loop invariants and inductive proofs, there is a starred exercise.

```
int sum = 0;
scanf("%d", &x);
while(x >= 0) {
    sum = sum + x;
    scanf("%d", &x);
}
printf("%d", sum);

```

Read a number into `x`, accumulate it into `sum` variable if `x` is nonnegative, and move on with the loop until user enters a negative number. Pretty simple stuff. Intuitively, we can readily see the `printf` output will be a nonnegative number. This is the thing we want to prove.

My loop invariant choice is:

> Before every check of loop condition, value of `sum` is nonnegative.

Of course, in line with the aim of the chapter, we also need to prove this invariant by induction. I can't come up with a rigorous formulation for an inductive proof myself.

Here is a bogus attempt:

$$S(x): If \hspace{0.4em} x\geq0, sum \geq 0$$

Proof is by induction on the value of variable `x`.

1. $S(0)$ base case holds because adding 0 can't change the value and sum already starts with 0.
2. Assume $S(n)$ is true. How to use the inductive hypothesis?

I can't formulate this. I am more used to utilizing the number of iteration of the loop (i) to base my inductive proof on and say "such and such is true before the $i^{th}$ iteration. But in this example, there is no easy way to talk about the number of iteration in terms of program variables `sum` and `x`.

# Answer
There's no need to perform an explicit induction here. Notice how your proposed invariant doesn't refer to the number of loop iterations. You're on the right track. Let $I \equiv \text{sum}\geq 0$ be our candidate loop invariant.

To show that $I$ is indeed a loop invariant it suffices to show that

* $I$ holds when control reaches the loop for the first time and
* $I$ is re-established by the loop body, assuming $I$ held before and the loop test (here $x\geq 0$) was true as well.

This already guarantees that $I$ will also hold upon loop termination. (Actually, even $I\land \neg(x\geq 0)$ since the loop test cannot be true anymore, but you don't need that in this example.)

The assignment statement $\text{sum} = 0$ establishes $I$ because $0\geq 0$. To do that more formally we'd use Hoare logic.

Working backwards from $I$ through the loop body we notice that the reading into $x$ doesn't affect $\text{sum}$, so we still have $I$. Pushing further backwards through the assignment statement, we arrive at $K\equiv \text{sum}+x\geq 0$ (by substituting the right-hand-side of the assignment for the occurrences of the left-hand-side in $I$). We need to prove that $I\land x\geq 0$ implies $K$, but that's trivial.
> 1 votes

---
Tags: loops, induction, loop-invariants
---


title: First-order iteration operator example

text:
# Question
Title: First-order iteration operator example
I am reading on https://en.wikipedia.org/wiki/FO\_(complexity)#Iterating that FO\[$t(n)$\] consists in first-order logic with an iteration operator that iterates $t(n)$ number of times some quantifier block Q.

Can someone provide me an example of a formula using such operator, please?

I feel that I am not understanding the concept since, for me, iterating some number of times the very same quantifier block with the same variables does not seem to add anything valuable to the formula. For instance, if I consider the quantifier block $\exists x. P(x)$, iterating it two times, as far as I understand, seems to bring $\exists x. P(x) \land \exists x. P(x)$, which is trivially equivalent to the original. Can someone clarify me this operator (preferibly, with some example)?

# Answer
Here is an example from Section 4.3 of Immerman's *Descriptive Complexity*.

Consider the block $$ (\forall z. \lnot (x = y \lor E(x,y))) (\exists z) (\forall uv. (u = x \land v = z) \lor (u = z \land v = y)) (\forall xy. x=u \land y=v) $$

Here $(\forall z.P)Q$ stands for $(\forall z) P \to Q$ and $(\exists z.P) Q$ stands for $(\exists z) P \land Q$.

Denoting the block by $TC$, let's check when $TC\\,R(x,y)$ holds. The first quantifier ensures that this holds if $x = y$ or $E(x,y)$. Otherwise, we need there to exist a $z$ such that for $(u,v) = (x,z)$ and for $(u,v) = (z,y)$, $R(u,v)$ holds, that is, we need both $R(x,z)$ and $R(z,y)$ to hold. In other words, $$ TC \\, R(x,y) \longleftrightarrow x=y \lor E(x,y) \lor (\exists z) (R(x,z) \land R(z,y)). $$ The operator TC "recycles" variables; in particular, the inner part mentions $x,y$ again. This means that if we apply it twice, we get the following: $$ TC \\, TC \\, R(x,y) \longleftrightarrow x=y \lor E(x,y) \lor \\ (\exists z)(x = z \lor E(x,z) \lor (\exists w) (R(x,w) \land R(w,z))) \land (z = y \lor E(z,y) \lor (\exists w) (R(z,w) \land R(w,y))) $$ If the domain has size $n$ and we apply TC iteratively $\lceil \log\_2 n \rceil$ times to $E$, then we get the transitive closure of $E$ (which is the same as solving directed reachability, an NL-complete problem).
> 1 votes

---
Tags: first-order-logic, descriptive-complexity
---


title: proving program equivalence

text:
# Question
Title: proving program equivalence
I understand that the general problem of program equivalence is undecidable, but I'm wondering what approaches exist to tackle the problem? I am familiar with Hoare-style verification, but are there any other frameworks for proving program equivalence?

# Answer
One general approach to the problem is to prove program equivalence by showing the programs have the same semantics. Hoare-style verification, as you say, is one option categorized as axiomatic semantics. Have a look at this article which describes most of the semantic approaches out there, including denotational semantics and operational semantics.
> 1 votes

# Answer
Proving this via a detour to a semantics is unnecessary and cumbersome.

Hoare logic is for showing that correctness conditions (AKA Hoare triples) of the form $\\{\phi\\}P\\{\psi\\}$ hold. To show equivalence of $P$ and $Q$, you'd have to show that $$\\{\phi\\}P\\{\psi\\}$\quad\text{iff}\quad\\{\phi\\}Q\\{\psi\\}$$ for *all* pairs $(\phi,\psi)$ of pre- and postconditions. You could attempt that using a symbolic postcondition and then compare the two weakest preconditions. Dijkstra showed how to do that in the 70ies.

A more modern way of doing the same thing would be to use a *refinement calculus* to show that the two programs under consideration mutually refine each other. Consult any of the good books on the topic, e.g., Carroll Morgan's Programming from Specifications.
> 0 votes

---
Tags: logic, formal-methods, hoare-logic
---


# Question
Title: Why can't we reduce register automata to symbolic automata?
When considering automata, they are normally considered over finite alphabets. The following are two types of automata that can handle words over infinite alphabets (definitions included for clarity).

The symbols $\triangleright$ and $\triangleleft$, appended to the beginning and end of the word respectively, are delimiters and are not in $\Sigma$. That is, the automata process words of the form *w* = $\triangleright$*v*$\triangleleft$ where *v* $\in$ $\Sigma^\*$.

A ***k-register automaton*** $\mathcal A$ over $\Sigma$ is a 5-tuple (Q, $q\_0$, F, $\tau\_0$, P) where:

* Q is a finite set of states;
* $q\_0$ $\in$ Q is the initial (or starting) state;
* F $\subseteq$ Q is the set of final (or accepting) states;
* $\tau\_0$ : $\\{0,1,...,k\\}$ $\to$ $\Sigma$ $\cup$ $\\{\triangleright,\triangleleft\\}$ is the initial register assignment; and,
* P is a finite set of transitions of the form ($i$, $q$) $\to$ ($q'$, $d$) or $q$ $\to$ ($q'$, $i$, $d$) for $i$ $\in$ $\\{0,1,...,k\\}$, $q$, $q'$ $\in$ Q and $d$ $\in$ $\\{Stay, Left, Right\\}$.

A ***symbolic finite automaton (SFA)*** $\mathcal M$ is a 5-tuple ($\mathcal A$, Q, $q\_0$, F, $\Delta$) where:

* $\mathcal A$ is an effective Boolean Algebra (the alphabet);
* Q is a finite set of states;
* $q\_0$ $\in$ Q is the initial (or starting) state;
* F $\subseteq$ Q is the set of final (or accepting) states; and,
* $\Delta$ $\subseteq$ Q $\times$ $\Psi\_{\mathcal A}$ $\times$ Q is a finite set of transitions.

Research has shown that for register automata, equivalence is not decidable but in symbolic automata, it is. My question is why? These two automata types work with similar results, so why is it that we can't reduce one to the other?

Something tells me this is a very simple problem but I can't seem to find an answer anywhere, so thank you for any help! :)

My current thoughts are to do with the fact that SFA require their alphabet to be an effective boolean algebra, whereas RA work on anything and so their alphabets dont have to follow the rules of a Boolean algebra. I dont know how to correctly formulate this idea into anything useful though.

# Answer
The basic difference is that register automata have a memory while symbolic finite automata do not. Over an infinite alphabet this gives RA a power that can't be replicated in SFAs. Symbolic automata can only recognize *unary* predicates, and other relations are much harder.

For a simple example, consider the language $L=\\{xx\mid x\in\Sigma\\}$. That is, the set of all strings of length 2 that repeat a character. There is an easy RA to achieve this: state 0 reads x and stores it in register 1, going to state 1 (i.e. $q\_0\to (q\_1,0,\mathsf{right})$), and state 1 goes to the accept state 2 if the current value matches (that is $(q\_1,0)\to (q\_2,\mathsf{stay})$, and $F=\\{q\_2\\}$) and rejects otherwise.

Suppose that a SFA accepts this language, where $\Sigma$ is infinite. Because for all $x\in\Sigma$, $xx\in L$, every character must initially be permitted. That is, for all $x\in\Sigma$ there is a state $q\_x$ such that $(q\_0,\phi,q\_x)\in\Delta$ and $\phi(x)$ is true. Since $\Delta$ (and $Q$) are finite, there are clearly a finite number of such states $q\_x$. But they are being tasked with distinguishing an infinite number of possible outcomes, depending on which $x$ was read. More precisely, by the pigeonhole principle there must exist $x\ne y$ such that $q\_x=q\_y$. Then the SFA must accept the string $x$ starting from $q\_x$, since $xx\in L$, but that means it also accepts the string $x$ starting from $q\_y$, so $yx\in L$ as well and hence the SFA doesn't correctly recognize $L$.
> 1 votes

# Answer
There is an extension of symbolic automata with registers. See

https://arxiv.org/abs/1811.06968
> 0 votes

---
Tags: automata, reductions, boolean-algebra
---


# Question
Title: LZ-type compression with a limited recursion depth
I would like to begin by apologizing. I am not a computer scientist, so my use of terminology will be off. I came across an interesting problem, which I believe to be pretty hard and would love to get references or any other advice to know what to search for in the academic literature on this topic.

Consider a standard LZ77-type compression algorithm. The compressor replaces substring at the current position with the pointer back to the already decompressed text or a literal copy of a single character. Early compressors tended to use greedy algorithms for choosing specific substrings, but better (in fact, optimal for a fixed LZ77 code) results can be obtained by generating a set of several (all) encoding options at each position and then treating the problem as a problem of finding the shortest path on a weighted graph. Each position of the text becomes a vertex, each edge contains the length of the code needed to encode the corresponding substring. The resulting problem is routinely solved by using the Dijkstra algorithm.

In principle, one does not need to store the decompressed text. Instead, one can make references back to the positions in compressed stream and decompress it as needed on the fly. In this case the algorithm becomes recursive - references to previous positions in the compressed stream can require one to follow further references before in the compressed stream. Dealing with overlapping substrings in this case can be a bit tricky, but otherwise, the logic of the algorithm remains mostly the same.

Now, suppose that we have an additional complication. We are using a recursive (buffer-less) version of LZ77 with back references to the compressed stream, but for various reasons we would like to limit the depth of recursion that we are allowed to use during decompression. For example, the maximum recursion depth of 1 would mean that a referred substring can involve further references to previous substrings, but neither of these substrings would be able to have any further back references. The easiest case would be to prohibit recursion completely. Overlapping substrings would not be allowed in this case. All this can be done and in fact I have a working implementation of a greedy algorithm for this problem. Of course, it is much less efficient compared with the classic LZ77. However, this is not a problem.

My real question is: what approach would be necessary to construct an optimal representation of the original text in the case when no recursion is allowed? It is clearly not possible to implement something similar to a Dijkstra algorithm mentioned earlier, because the graph is no longer static: once a particular edge (i.e. a particular substring) gets included into the shortest path, all edges referring to substrings overlapping with the current substring disappear from the graph. The graph is now dynamic and the path-finding algorithm is not "local" in the sense that it can no longer work in a "ripple"-type fashion, because any rush decision early on may disallow much greater savings later on. How would one attack this kind of problem?

# Answer
> 1 votes
While I do not have a fully satisfactory answer to my own question, I have now found the academic context for what I was trying to do. In their classical paper \[1\] Storer and Szymanski introduce a classification of "macro encoding schemes", which includes all kinds of LZ compressors as particular cases. The usual LZ77 would be described in their terminology as an OPM (original pointer macro) scheme, and the modification described in my question would be a CPM (compressed pointer macro) scheme. Definition 5 on p.931 specifically introduces macro schemes without recursion in exactly the same sense as described in my question.

They present analysis of different types of macro encoding schemes and, specifically for CPM they state on p.942 that the "optimal encoding for the CPM scheme appears to be intractable". They also give Theorem 9 saying that the problem of finding a constant bound for the optimal CPM compressed size is NP-complete. I cannot see at present if this implies that the problem of finding optimal encoding is NP-complete too, although I would not be particularly surprised if it does.

\[1\] Storer, J. A., & Szymanski, T. G. (1982). Data compression via textual substitution. Journal of the ACM (JACM), 29(4), 928-951.

---
Tags: data-compression, lempel-ziv
---


title: 2VertexDisjointPaths ≤p SimpleCycle

text:
# Question
Title: 2VertexDisjointPaths ≤p SimpleCycle
Given the following problems:

**2VertexDisjointPaths:**

**Given:** a directed Graph $G$ und vertices $s1, s2, t1, t2$.

**Question:** Do paths $p1$ from $s1$ to $t1$ and $p2$ from $s2$ to $t2$ exist if $p1$ and $p2$ are vertex disjoint? Vertex disjoint meaning if $p1$ uses a vertex $p2$ can't use it and vice versa.

**SimpleCycle:**

**Given:** a directed Graph $G$ and two edges $e1, e2$ of $G$.

**Question:** Is there a directed circle in G, which goes through e1 and e2?

**Show that SC is np-complete by using that 2VDP is np-complete.**

I know you have to reduce 2VDP to SC but I don't know the mapping function which will map the input of 2VDP to the input of SC. In other words I don't know the basic idea yet.

# Answer
> 0 votes
Add the edges: $(t\_1,s\_2)$ and $(t\_2,s\_1)$ to the graph $G$ if they are not there already. Let the new graph be $G'$. For $SC$ problem, take $e\_1 = (t\_1,s\_2)$ and $e\_2 = (t\_2,s\_1)$ and solve it on $G'$.

---
Tags: complexity-theory, graphs, path
---


# Question
Title: Show that a subproblem of Sparse Subgraph is $\mathcal {NP}$-Complete
I want to show that a subproblem of the known, $\mathcal {NP}$-Complete, Sparse Subgraph problem is also $\mathcal {NP}$-Complete.

> **Sparse Subgraph problem**:
>
> Input: Undirected graph $G(V,E)$, two integers $k, l$.
>
> Output: Is there a subset $S \subseteq V$, where $|S| \geq k$, such that there are at most $l$ edges between pairs of vertices in $S$?

My subproblem is the special case where $k=l$:

> **Subproblem of the Sparse Subgraph problem**:
>
> Input: Undirected graph $G(V,E)$, an integer $k$.
>
> Output: Is there a subset $S \subseteq V$, where $|S| \geq k$, such that there are at most $k$ edges between pairs of vertices in $S$?

We can easily show that the first one (Sparse Subgraph) is $\mathcal {NP}$-Complete, by reducing the Independent Set problem to it.

I tried to reduce the Independent Set problem, as well, to the subproblem without success.

**Is there another known $\mathcal {NP}$-Complete problem, which I can reduce to the subproblem?**

Is the assumption, that the subproblem must also be $\mathcal {NP}$-Complete, as it is a special case of the original Sparse Subgraph problem, correct?

I would appreciate any help.

# Answer
> 0 votes
Let the independent set problem be $\mathsf{IS}$, and the subproblem of the sparse subgraph problem be $\mathsf{SIS}$.

The Independent set problem is hard to approximate within any constant factor (see here). It means, it is NP-hard to distinguish between the following instances:

1. **Yes Instances:** The graphs that contain an independent set of size at least $k$
2. **No Instance:** The graphs that do not contain any independent set of size $c \cdot k$ for any constant $c\<1$.

Using it, we show NP-hardness of $\mathsf{SIS}$. That is, we show that it is NP-hard to distinguish between the following instances:

1. **Yes Instances:** The graphs that contain a set $S \subseteq V$ of size at least $k$ and with at most $k$ edges in $S$.
2. **No Instance:** The graphs that do not contain a set $S \subseteq V$ of size at least $k$ and with at most $k$ edges in $S$.

**Proof:** (-\>) If $(G,k)$ is a yes instance of $\mathsf{IS}$ then $(G,k)$ is a yes instance of $\mathsf{SIS}$. It is trivial.

(\<-) We have to show that if $(G,k)$ is a no instance of $\mathsf{IS}$ then $(G,k)$ is a no instance of $\mathsf{SIS}$. For the sake of contradiction, assume that $(G,k)$ is a yes instance for $\mathsf{SIS}$. That is, $G$ contains a set $S \subseteq V$ of size at least $k$ and with at most $k$ edges in $S$. Let there be $m$ edges in $S$. Then, there exists a subset $S' \subseteq S$ of size $t \cdot m$ for $1\leq t \leq 2$, that contains the $m$ edges. Then we make the following claim:

> $S'$ contains an independent set of size at least $m/4$.

The proof of the above claim follows from Theorem 3.14 in this thesis. Furthermore, the above claim implies that $S$ contains an independent set of size at least $m/4 + (|S|-|S'|) \geq |S'|/8 + (|S|-|S'|) \geq |S|/8$. That is, $G$ contains an independent set of size $k/8$. It contradicts that $G$ does not have any independent set of size $c \cdot k$ for $c = 1/8$.

---
Tags: complexity-theory, np-complete, reductions, decision-problem, polynomial-time-reductions
---


# Question
Title: λ-Calculus extensions: meaning of extension symbols
When working with λ-Calculus I see lots of extensions that use other symbols such as ∀ \<:Top {} ←, which are from "Types and Programming Languages" (WorldCat) by Benjamin C. Pierce.

```
Name                   Extends/Based on Figure                          Figure                                                   Page
B unyped                                                                3-1 Booleans (B)                                         34
B ℕ (untyped)          Extends 3-1 B                                    3-2 Arithmetic expressions (ℕB)                          41
→ (untyped)                                                             5-3 Unyped lambda-calculus (λ)                           72
B (typed)              Extends 3-1 B                                    8-1 Typing rules for booleans (B)                        93
B ℕ (typed)            Extends 3-1, 8-1 B                               8-2 Typing rules for numbers (ℕB)                        93
→ (typed)              Based on5-3 λ                                    9-1 Pure simply typed lambda-calculus (λ→)               103
→ Unit                 Extends 9-1 λ→                                   11-2 Unit type                                           119
→ as                   Extends 9-1 λ→                                   11-3 Ascription                                          122
→ let                  Extends 9-1 λ→                                   11-4 let binding                                         124
→ x                    Extends 9-1 λ→                                   11-5 Pairs                                               126
→ {}                   Extends 9-1 λ→                                   11-6 Tuples                                              128
→ {}                   Extends 9-1 λ→                                   11-7 Records                                             129
→ {} let p (untyped)   Extends 11-7, 11-4                               11-8 (Untyped) record patterns                           131
→ +                    Extends 9-1 λ→                                   11-9 Sums                                                132
→ +                    Extends 9-1 λ→                                   11-10 Sums (with unique typing)                          135
→ <>                   Extends 9-1 λ→                                   11-11 Variants                                           136
→ fix                  Extends 9-1 λ→                                   11-12 General recursion                                  144
→ B List               Extends 9-1 λ→ with 8-1 booleans                 11-13 Lists                                              147
→ Unit Ref             Extends 9-1 λ→ with 11-2 Unit                    13-1 References                                          166
→ error                Extends 9-1 λ→                                   14-1 Errors                                              172
→ error try            Extends 9-1 λ→ with 14-1 Errors                  14-2 Error handling                                      174
→ exceptions           Extends 9-1 λ→                                   14-3 Exceptions carrying values                          175
→ <: Top               Extends 9-1 λ→                                   15-1 Simply typed lambda-calculus with subtyping (λ<:)   186
→ {} <:                Extends 15-1 λ<: and 11-7 Records                15-3 Records and subtyping                               187
→ <: Bot               Extends 15-1 λ<:                                 15-4 Bottom type                                         192
→ <> <:                Extends 15-1 λ<: and 11-11 Simple variant rules  15-5 Variants and subtyping                              197
→ {} <:                Extends 15-1 λ<: and 15-3 Records and subtyping  16-1 Subtype relataion with records (compact version)    211
→ {} <:                                                                 16-2 Algorithmic subtyping                               212
→ {} <:                                                                 16-3 Algorithmic typing                                  217
→ u                    Extends 9-1 λ→                                   20-1 Iso-recursive types (λu)                            276
→∀                     Based on 9-1 λ→                                  23-1 Polymorphic lambda-calculus (System F)              343
→∀∃                    Extends 23-1 System F                            24-1 Exestential types                                   366
→∀∃ Top                Based on 23-1 System F and 15-1 simple subtyping 26-1 Bounded quantification (kernel F<:)                 392
→∀∃ Top full           Extends 26-1 F<:                                 26-2 "Full" bounded quantification                       395
→∀<: Top ∃             Extends 26-1 F<: and 24-1 unbounded existentials 26-3 Bounded existential quantification (kernel variant) 406
→∀<: Top                                                                28-1 Exposure Algorithm for F<:                          418
→∀<: Top               Extends 16-3 λ<:                                 28-2 Algorithmic typing for F<:                          419
→∀<: Top               Extends 16-2 λ<:                                 28-3 Algorithmic subtyping for kernel F<:                422
→∀<: Top full          Extends 28-3                                     28-4 Algorithmic subtyping for full F<:                  424
-⇒                     Extends 9-1 λ→                                   29-1 Type operators and kinding (λω)                     466
-∀⇒                    Extends 29-1 λω and 23-1 System F                30-1 Higher-order polymorphic lambda-calculus (Fω)       450
-∀∃⇒                   Extends 30-1 Fω and 24-1                         30-2 Higher-order existential types                      452
-∀⇒<: Top              Based on 30-1 Fω and 16-1 kernel F<:             31-1 Higher-order bounded quantification (Fω<:)          470
-∀<: Top {}←           Based on 26-1 F<: with 11-7 records              32-1 Polymorphic update                                  485

```

or use of σ and ν as in

"From λσ to λν-a Journey through Calculi of Explicit Substitutions" by Pierre Lescanne.

and of course Barendregt's Lambda Cube

Note: For the Weak systems ω should be underlined.

```
λ→   The Simply Typed Lambda Calculus
λω   Weak Lambda Omega
λ2   Polymorphic or Second Order, Typed Lambda Calculus
λω   The System Fω
λP   LF
λPω  Weak Lambda P omega
λP2  Lambda P2
λPω  The Calculus of Constructions

```

Is there any standard or commonality to the use of these symbols? Where can I find a listing of their meaning.

Also, as I have shown with the extenstions using TAPL, is there any list of the most noteworthy calculi with there symbols, defnition and what they extend?

I am really after a DAG of related λ-Calculi that gives a brief explaination of each one.

# Answer
> 0 votes
Since I have waited years for Dave Clarke to answer I am just going to copy his comment so that others can see this has an answer.

> If I am not mistaken, you have just given such a list. And if you read the abstract of the paper you just linked, then you'll find what σ and v refer to. Many many papers studying programming language constructs will introduce their own λ-variant, so the only way of knowing what each one is is by consulting the research papers. Pierce's book goes a long way, though, with the standard ones.

---
Tags: terminology, lambda-calculus, computation-models, types-and-programming-languages
---


title: Buchi arithmetic meaning

text:
# Question
Title: Buchi arithmetic meaning
I am studying this article. But I have trouble with understanding the Buchi arithmetic. It says in section IV:

> ... Formulas in this fragment generalise classical integer programming and are of the form $$ \mathbf{A} \boldsymbol{x}=\boldsymbol{c} \wedge \bigwedge\_{i \in I} V\_{p}\left(x\_{i}\right)=y\_{i} $$

But I don't understand what does it mean by $ \mathbf{A} \boldsymbol{x}=\boldsymbol{c} \wedge \bigwedge\_{i \in I} V\_{p}\left(x\_{i}\right)=y\_{i} $. I know that the goal is to finding $\boldsymbol{x}$ such that was an answer for previous equation. But my question is about the meaning of $\boldsymbol{c} \wedge \bigwedge\_{i \in I} V\_{p}\left(x\_{i}\right)=y\_{i}$. According to the previous sections of the article $\boldsymbol{c}$ is a vector and I want to know what does wedge symbol mean in this case?

In addition, I want to know, as $V\_{p}\left(x\_{i}\right)$ is an integer, is the big wedge notation here a bitwise and or something else?

As It is the first time I have studied this kind of material, my question may seem naive. However, I appreciate any help containing some references about Buchi arithmetic.

# Answer
> 2 votes
The wedge sign means *AND*. The formula states that $\mathbf{A}x=c$ and for all $i \in I$, $V\_p(x\_i) = y\_i$.

---
Tags: complexity-theory, computability, automata, arithmetic, buchi-automata
---


# Question
Title: Convex Polygon Triangulation: Line Intersects at most $O(\log n)$ Triangles
Suppose a convex polygon $P$ in plane is given. We want to triangulate it such that any arbitrary line $L$ intersects with $O(\log n)$ triangles.

I divide $P$ in half using a diagonal line. Then I continue in each half in the same way. But at this step I get stuck.

# Answer
> 3 votes
Let the polygon be defined by the vertices in clockwise order: $(v\_1, \dotsc, v\_n)$. For simplicity, assume that $n$ is even.

1. Add the lines: $(v\_1,v\_3)$, $(v\_3,v\_5)$,...,$(v\_{n-2},v\_1)$.
2. Then, recursively triangulate the polygon: $(v\_1, v\_3, \dotsc, v\_{n-2})$.

Note that, the algorithm creates $n/2$ triangles in step $1$. And, any arbitrary line $L$ can intersect at most $2$ of these triangles. By induction, it is easy to prove that any line $L$ will not intersect more than $2 \log n$ triangles overall.

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


title: How to solve T(n) = T(n-1) + n(n-1)?

text:
# Question
Title: How to solve T(n) = T(n-1) + n(n-1)?
I am not able to solve the following recurrence relation:

T(n)={T(n−1)+n(n-1) if n≥2,T(1)=1.

# Answer
Here's a useful rule of thumb.

A recurrence of the form

$$T(n) = T(n-1) + p(n)$$

where $p$ is a polynomial has the solution

$$T(n) = q(n)$$

where $q$ is a polynomial one degree higher than $p$.

I'm going to give you an example, and leave you to solve your own problem. The example is the sum-of-cubes formula:

$$\begin{eqnarray\*}S(0) & = & 0 \\ S(n) & = & S(n-1) + n^3\end{eqnarray\*}$$

We look for a quartic solution:

$$S(n) = a\_4 n^4 + a\_3 n^3 + a\_2 n^2 + a\_1 n + a\_0$$

The base case gives:

$$a\_0 = S(0) = 0$$

And the inductive case gives:

$$\begin{eqnarray\*}& & a\_4 n^4 + a\_3 n^3 + a\_2 n^2 + a\_1 n + a\_0 \\ & =& a\_4 (n-1)^4 + a\_3 (n-1)^3 + a\_2 (n-1)^2 + a\_1 (n-1) + a\_0+ n^3\end{eqnarray\*}$$

That is:

$$\begin{eqnarray\*}& & a\_4 n^4 + a\_3 n^3 + a\_2 n^2 + a\_1 n + a\_0 \\ & =& a\_4 (n-1)^4 + a\_3 (n-1)^3 + a\_2 (n-1)^2 + a\_1 (n-1) + a\_0+ n^3\end{eqnarray\*}$$

$$(4a\_4-1)n^3+(3a\_3-6a\_4)n^2+(4a\_4-3a\_3+2a\_2)n+(-a\_4+a\_3-a\_2+a\_1) = 0$$

Because this must be true for all $n$, we get the system of equations:

$$\begin{eqnarray\*}4a\_4 - 1 & = & 0 \\ 3a\_3-6a\_4 & = & 0 \\ 4a\_4-3a\_3+2a\_2 & = & 0 \\ -a\_4+a\_3-a\_2+a\_1 & = & 0\end{eqnarray\*}$$

Four equations in four unknowns. Solve this:

$$\begin{eqnarray\*}a\_4 & = & \frac{1}{4} \\ a\_3 & = & \frac{1}{2} \\ a\_2 & = & \frac{1}{4} \\ a\_1 & = & 0\end{eqnarray\*}$$

Therefore:

$$S(n) = \frac{1}{4} n^4 + \frac{1}{2} n^3 + \frac{1}{4} n^2$$

Now try solving your problem.
> 2 votes

---
Tags: algorithms, time-complexity, algorithm-analysis
---


# Question
Title: Lexical analysis on a series of tokens given regexes
I am to parse through a series of strings with a given token list. I was wondering if my lexical analysis is correct.

```
T1 = { abc, abc1 }
T2 = { abd, abd1 }
ID = [a-z]+[a-z0-9]
NUM = 0 | [1-9][0-9]

```

`lexer.getToken()` will return the current token and advance the input buffer by one. `lexer.peek(num)` will return the token at the index `num` and NOT advance the input buffer. `num` starts at 1 and 1 indicates the next possible token.

Here are the strings

`abc 202 02202 abcabd1 abd0abc1 a123 abd1 abd2 abd3`

and here are the function calls

```
t1 = lexer.getToken(); # will return t1 = {T1, "abc"}
t2 = lexer.getToken(); # will return t2 = {NUM, "202"}
t3 = lexer.peek(1); # will return t3 = {NUM, "2202"}
t4 = lexer.peek(2); # will return t4 = {ID, "abcabd1"}
t5 = lexer.getToken(); # will return t5 = {NUM, "0"}
t6 = lexer.peek(2); # will return t6 = {ID, "abd0abc1"}
t7 = lexer.peek(3); # will return t7 = {ID, "a123"}
t8 = lexer.peek(4); # will return t8 = {T2, "abd1"}
t9 = lexer.getToken(); # will return t9 = {NUM, "2202"}
t10 = lexer.peek(5); # will return t10 = {ID, "abd3"}

```

I got this because

`t1` will consume and return `"abc"` as conforms to `T1` and advance the input buffer

`t2` will consume and return `"202"` as conforms to `T2` and advance the input buffer

`t3` will return `"2202"` because we are currently at `"0"` since `"0"` conforms to regex `NUM` and we peek past it.

`t4` will find the next valid token which is `"abcabd1"`

`t5` will consume the `"0"` as conforms to `NUM` and advance the input buffer

`t6` will return `"abd0abc1"` as conforms to `ID` since input buff on `"2202"`

`t7` will return `"a123"` as conforms to `ID` since we are still on `"2202"`

`t8` will return `"abd1"` as conforms to `T2`

`t9` will return `"2202"` as conforms to `NUM` and consume `"2202"`, moving to `"abcabd1"`

`t10` will return `"abd3"` as conforms to `ID` since we are currently on `"abcabd1"`.

Does this logic look correct? I apologize if this is somewhat messy, just wanted to see if my logic is correct and I am following all regex/lexical rules.

# Answer
> 0 votes
I think it's odd to say that "1 indicates the next possible token" when you intend to return the token *after* the first unconsumed token. Or do you allow $peek(0)$ to return the current token without consuming it? (Far and away the most common use for a peek function.) But that's just documentation, I guess.

`abd0abc1` is not a match for `[a-z]+[a-z0-9]`. `abd0` would match that regular expression; once a digit is matched, nothing more can be added.

---
Tags: formal-languages, regular-expressions, compilers, parsers
---


# Question
Title: How can a non-deterministic Turing Machine be converted to a deterministic TM with a witness-input?
This 2014 paper by Barak and Goldreich defines the notion of a universal set $S\_{\mathcal{U}}$ as the set of all tuples $(M,x,t)$ such that the non-deterministic machine $M$ accepts the input $x$ in $t$ steps or less (page 2). They further go on to describe a relation $R\_{\mathcal{U}}$ for $S\_{\mathcal{U}}$ which they call the 'natural witness-relation,' defined as

$$R\_\mathcal{U}\equiv\\{((M,x,t),w)\mid M\text{ accepts $(x,w)$ in $t$ steps or less}\\}$$

Here $M$ is changed from a non-deterministic machine to a two-input deterministic machine. Since the purpose of this relation seems to be to list all instance-witness pairs, if I am understanding it correctly then $w$ is a witness for instance $x$ of the problem decided by $M$. That an NDTM can be expressed as a DTM is trivial.

However, just exactly how is the arbitrary machine $M$ in $S\_\mathcal{U}$ transformed into the one that accepts $(t,w)$ in the definition of $R\_\mathcal{U}$? Is the relation well-defined for arbitrary machines?

Sorry if the question is trivial, I come from a cryptography background and this is my first time dealing with these notions.

# Answer
> 1 votes
Let $\delta:\Sigma\times Q\rightarrow \mathcal{P}(\Sigma\times Q\times\\{L,R\\})$ be transition function of nondeterministic Turing Machine $N$. So for a given input $(a,q)$ where $a\in \Sigma$ and $q\in Q$, the machine $N$ has possibly lots of choices to transit.

In order to transform a Nondeterministic TM $N$ for input $x$ to a deterministic TM $D$, we can give ***the path of correct choices*** (that is which choice of transition it should choose) of transition function as a witness or certificate that TM $N$ can accept $x$. The deterministic machine $D$, use $N$ and ***this path*** to check whether $N$ reach accept state for input $x$ in $t$ steps or not.

---
Tags: turing-machines
---


title: is HaltingFuck computable?

text:
# Question
Title: is HaltingFuck computable?
A while ago I defined the language HaltingFuck, but I've never been able to figure out its computational class. The language is defined as follows:

> HaltingFuck is a language very much like Brainfuck, with one key difference: instead of loops stopping when the value in the current cell is zero, they stop when the value in the current cell is the Gödel number of a HaltingFuck program that halts. The specific Gödel encoding is not specified since it doesn't affect any interesting properties of the language.

I argued on the page linked that HaltingFuck is a total language, because

> While it's very easy to write a HaltingFuck program that halts (for instance, the empty program), in order to write a HaltingFuck program that doesn't halt it is necessary to first write a HaltingFuck program that doesn't halt. This is because any HaltingFuck program that doesn't halt must contain at least one loop that starts with the current cell containing the Gödel number of a non-halting program. Since it is impossible to construct a non-halting program, every loop in a HaltingFuck program runs exactly zero times, and since every loop in a HaltingFuck program runs exactly zero times, it is impossible to construct a non-halting program.

But I'm not convinced that's true. Consider the encoding where 0 encodes `[]`. then the program `[]` halts if and only if the program `[]` halts, and as far as I can see we have no other information about whether it halts or not. I'm not sure how to interpret that, unless it means that the language is underspecified and there are two possible such HaltingFucks - a total one where `[]` halts and an uncomputable one where it doesn't.

# Answer
> 7 votes
> it means that the language is underspecified and there are two possible such HaltingFucks - a total one where \[\] halts and an uncomputable one where it doesn't.

That's correct. The specification does not obviously define the semantics of the language in an unambiguous way. It's self-referential:

> they stop when the value in the current cell is the Gödel number of a HaltingFuck program that halts

To determine the semantics of a program containing a loop, you need to know whether some other program terminates. If that other program has a loop, you need to know whether yet another program terminates, and so on. Depending on the Gödel encodings, this can mean that there are multiple possible semantics, or none. Your example where the termination of `[]` depends on its own encoding is a simple example where there are either two HaltingFuck semantics corresponding to that encoding, or none at all, depending on the consistency of other programs.

What you've defined is not the semantics of a language, but a set of possible semantics for a language. That set depends on the precise choice of Gödel encoding. In other words, you've defined a (possibly empty) family of languages for each Gödel encoding. It's not obvious to me whether there are Gödel encodings for which that set is non-empty, or whether there are Gödel encodings for which that set has exactly one element.

---
Tags: computability, programming-languages, turing-completeness
---


# Question
Title: Find if an edge doesn't belong to any $MST$ with some edges of unknown weights
I've faced this problem with my homework.

We're given a weighted, undirected graph $G=(V,\ E,\ w)$ with weight function $w:E\rightarrow \mathbb{R\_{\ge0}}$, someone deleted the weights of some edges $T\subseteq E$ so their weights are unknown. Describe an efficient algorithm that finds the following:

1. For every $e\in T$ if it belongs to every MST (no matter what the weights of $T$ are).
2. For every $e\in T$ if it doesn't belong to any MST (no matter what the weights of $T$ are).

More explanation: all the edges in $T$ don't have their weight now so we can't know what their weights were, therefore we can't use Kruskal or Prim algorithm unless we give them weights that will give us the results we want.

So I was thinking of a solution for the first part which is finding all bridge edges and of them to check the edges that are in $T$, these edges are for sure belongs to every $MST$ and that because they are the lightest edges in some $cut$ of the graph.

As for the second part, I know that we must find edges that are for sure the heaviest edges in any cycle but the problem is that we don't have the weights of these edges and we can't give them maximum weight in any cycle too because this would lead to wrong results.

If anyone could help I'll be thankful.

# Answer
So, we are asked to find the answer to the following two question, regardless of whatever values we will reassign to $w(u)$ for all $u\in T$.

### Does $e\in T$ belong to every MST?

Your approach is correct.

* If $e$ is a bridge, every MST must contain $e$ since an MST must be connected.
* Otherwise, $e$ is not a bridge. We can let the weight of $e$ be bigger than the weight of every other edge. Then no MST can contain $e$ since $e$ is the unique heaviest edge of any cycle that contains $e$.

### Does $e\in T$ not belong to any MST?

If $G$ is a graph without loops, there is no such edge since we can assign weight $0$ to $e$. We can then run Kruskal's algorithm to select $e$ as the first edge to include, obtaining an MST that contains $e$ in the end.

Otherwise, every loop of $G$ that is in $T$ does not belong to any MST. In fact, any MST of any graph does not contain any loop since an MST is a tree.
> 1 votes

---
Tags: algorithms, trees, weighted-graphs, minimum-spanning-tree
---


# Question
Title: Is SUBSET SUM only for positive integers in P or NP?
Since UNARY SUBSET SUM is in P, and a positive-only SUBSET SUM problem could be represented in unary, I struggle to see why it wouldn't be the case that it is in P, when restricted to positive numbers?

# Answer
> 0 votes
Subset-sum is not in $P$ for a Positive Integer, The reason that subset-sum in P for an unary alphabet is that Subset-sum admit a pseudo-polynomial algorithm, and the running time of the algorithm is measured with respect to the length of the input, the length of the encoding of an integer is $log\_b(n)$ where $b$ is the base that using, but if $b = 1 $ then the length of the integer is $|n|$ in that case the pseudo-polynomial algorithm is a polynomial algorithm.

---
Tags: complexity-theory, turing-machines, np, subset-sum
---


# Question
Title: Why when a function is quadratic, the approximation by Newton's method is exact, and the algorithm converges to the global minimum in a single step?
> Suppose we want to find the value of $x$ that minimizes $$ f(x)=\frac{1}{2}\\|A x-b\\|\_{2}^{2} . $$ Specialized linear algebra algorithms can solve this problem efficiently; however, we can also explore how to solve it using gradient-based optimization as a simple example of how these techniques work. First, we need to obtain the gradient: $$ \nabla\_{x} f(x)=A^{\top}(A x-b)=A^{\top} A x-A^{\top} b . $$ We can then follow this gradient downhill, taking small steps.
>
> \begin{array}{} \hline \text{Algorithm $4.1$ An algorithm to minimize} f(x)=\frac{1}{2}\\|A x-b\\|\_{2}^{2} \text{ with respect to $x$} \\ \text{using gradient descent, starting from an arbitrary value of $x$.} \\ \hline \text{Set the step size $(\epsilon)$ and tolerance $(\delta)$ to small, positive numbers. }\\ \text{while $\left\\|A^{\top} A x-A^{\top} b\right\\|\_{2}\>\delta$ do} \\ \quad x \leftarrow x-\epsilon\left(A^{\top} A x-A^{\top} b\right) \\ \text{end while} \end{array}
>
> **One can also solve this problem using Newton's method. In this case, because the true function is quadratic, the quadratic approximation employed by Newton's method is exact, and the algorithm converges to the global minimum in a single step.**
>
> *Deep Learning*, Bengio and al. page 94

I don't get this very last point. Indeed, we set the step size $(\epsilon)$ and tolerance $(\delta)$ to small, positive numbers and we don't even have something like an adaptative step size that would augment if we are far from the target. So would it truly converge to the global minimum in a single step? Don't we need to iterate quite a lot rather?

I am a dumb programmer and slow math learner, don't hesitate to explain it to me as if I was a teenager.

# Answer
> 0 votes
When the book wrote that Newton's method converges in a single step, it is correct. If you look at the specification of Newton's method, you will notice no $\epsilon$ or $\delta$ to set. (There is no need for a tolerance $\delta$ here as it converges in one step, and in any case, even if you set one, it would terminate after one step no matter what $\delta$ you set.) Newton's method is not the same as gradient descent. To see why it converges in a single step for a quadratic function, try writing a general quadratic function (say $f(x)=ax^2+bx+c$), compute what Newton's method gives you after one step, and compare to the actual minimum of this function.

---
Tags: gradient-descent
---


# Question
Title: Algorithmic Complexity of Enqueue and Dequeue of a Special Queue
**The Canteen Queue Problem**

There is a common canteen for K hostels. Each hostel (co-ed) has some $N\_1,N\_2,...,N\_K$ students. These students line up to pick up their trays in the common canteen, in a queue.
The queue is implemented as follows: If a student sees a person from his/her hostel, she/he joins the queue behind this person. This is the “enqueue” operation. The “dequeue” operation is as usual, at the front. How would we implement such a queue? Additionally, what would be the time complexity of the enqueue and dequeue operations? Would the average waiting time in this queue would be higher or lower than a normal queue?

# Answer
> 0 votes
Use a doubly linked list of students in the queue. Also, for each hostel, have a second doubly linked list of students in the hostel, in the order they appear in the queue. When a new student arrives, look up their hostel's linked list to find the person at the front of the queue, then add them to the queue. All operations can be done in $O(1)$ time.

---
Tags: algorithms, time-complexity, data-structures, queues
---


# Question
Title: What is the counterclockwise index of diagonal endpoints in a diagonal$\to$triangulation algorithm?
I'm reading the book *Computational Geometry in C* by O'Rourke. One of the problems ask the following

> *Diagonals$\rightarrow$triangulation*. Given a list of diagonals of a polygon forming a triangulation, with each diagonal specified by a counterclockwise indices of the endpoints, design an algorithm to build the triangulation dual tree.

While I have a vague idea of how to solve the given problem, it isn't clear to me what exactly **diagonal specified by a counterclockwise indices of the endpoints** mean as this seems important in the algorithm design.

O'Rourke's own sample input (below) specified a list of coordinates which isn't obvious to me how they are a list of diagonals.

```
0   0
10  7
12  3
20  8
13  17
10  12
12  14
14  9
8   10
6   14
10  15
7   18
0   16
1   13
3   15
5   8
-2  9
5   5

```

I would be grateful if someone could give a hint on either what the counterclockwise indices of the endpoints mean, or how the list of points above translates to a list of diagonals. Thank you.

# Answer
> 1 votes
I can only guess, but here is my guess. Indices means that if there are $n$ points, you assign each point a different number from $1,2,\dots,n$. Counterclockwise means that you imagine walking around the perimeter in counterclockwise direction, sequentially numbering the points you visit 1, 2, 3, ..., respectively. This assigns an index to each point. "diagonal specified by a counterclockwise indices of the endpoints" means that the way a diagonal represented is by identifying its two endpoints; each endpoint is identified by the index assigned above.

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


# Question
Title: How do I take the average of multiple Fast Fourier Transforms?
**How do I take the average of multiple fast Fourier transforms (ffts)?**

I have multiple audios that I want to take the fft of and then average these results to smooth out the random noise that appears in each audio. The ffts of the audios are shown in the graph below.

However the problem I'm having is that I can't work out how to ensure that all the arrays I'm averaging have the same length and the same frequency spacing, because sampling the audios at a rate inversely proportional to their length makes them the same size, however it changes the frequency spacing of each audio sample.

What I'm trying to do is find a way to average all these results so I can look for trends in the signal. The audios are from a particular species of birds, so averaging across multiple recordings would give me an insight into the frequencies at which this species communicates at and could be used to do the same for other species.

# Answer
One simple solution is to pick a fixed-size window (of $w$ samples). Then, break down each audio sample into multiple windows, compute the FFT on each window, and average all of the results.

Another possible approach is to pick a fixed array length $L$; take the output of the FFT on each sample and resize that array to be of length $L$ using upscaling/downscaling; and then average all of those length-$L$ arrays.

I don't know which is best -- I am not an expert on signal processing, and what is best for your needs might depend on your particular situation and what you'll do with the results.
> 2 votes

---
Tags: signal-processing, fast-fourier-transform
---


# Question
Title: Least-balanced possible red-black tree of n distinct nodes
Let's say we have a red-black tree of $n$ total nodes where all keys are distinct. The subtree rooted at the root node's left child has $n\_L$ nodes, and similarly the subtree rooted at the root node's right child has $n\_R$ nodes.

What is the range of values on $n\_L$ and $n\_R$ for any $n \geq 3$?

From Red Black Tree vs AVL Tree

>

For example, in the above image: $n = 8, n\_L = 1, n\_R = 6$.

# Answer
> 1 votes
Let $b$ be the black height of the left subtree, which is also the black height of the right subtree.

The number of nodes in the left subtree is at least $2^{b}-1$. $2^b-1$ is reached when the left subtree is a perfect binary tree of black nodes and height $b-1$.

The number of nodes in the right subtree is at most $2^{2b+1}-1$. $2^{2b+1}-1$ is reached when the root is black and the right subtree is a perfect binary tree of height $2b$ with nodes colored red, black, red, black and so on alternatively from top to bottom.

$$2^b-1 + 2^{2b+1}-1\ge n-1$$

Solving for $b$, we obtain $$ b\ge f(n) := \lceil \log\_2(\sqrt{8n+9}-1)\rceil-2$$

So, the range for $n\_L$ is $\[2^{f(n)}-1, n - 2^{f(n)}\]$, which is, by symmetry, also the range for $n\_R$.

For example, when $n=8$, $f(n)=1$, the range is $\[1, 6\]$ as illustrated in the question.

---
Tags: binary-search-trees, red-black-trees
---


# Question
Title: Is it really impossible to use K-fold cross validation for time series data?
I would like to know if it is impossible to use K-fold cross-validation for time series of data. It has been discussed that it is not reasonable to predict past from future, but I think this does not make sense since time series data might be repeated in the future. Suppose a past fold is going to be repeated in the future exactly with the same pattern. Therefore, in that case, the fold that we are considering as past data will be part of the future!

# Answer
> 1 votes
K-fold cross-validation is not appropriate for time series. It's perfectly reasonable to use the past to predict the future; the problem is that cross-validation will normally try to predict the past from the future, which is silly and not representative of how it would be used in real life.

Instead, the appropriate way is to use temporally consistent cross-validation. In this method, we randomly pick a date; all data before that date goes into the training set, and all data after that date goes into the validation set.

If you discover that certain patterns repeat, then yes, a good model will be able to take advantage of that to predict the future accurately. If so, great! That will show up positively during both cross-validation and during real-world deployment, so cross-validation is indeed accurately estimating how well the scheme will perform if deployed in practice, which is what we want.

---
Tags: machine-learning, python
---


# Question
Title: Using an optimal number of agents, maximise coverage of an area while minimising distance travelled
I'm a CS Year 2 student working on a team project which requires a solution to the following problem:

Given a starting position on the edge of an irregular shape (example above) and a maximum number of available agents, maximise the area covered (meaning the number of squares visited inside the shape\*) while minimising the distance travelled (euclidian distance - travelling diagonally inside a square is not the same as along an edge of the square) by the agents. It is also important to note that the agents have to return to the starting position and they also have a limited travel distance (they must return to the starting point before that maximum travel distance is reached).

\*A square is considered to be "visited" if the agent travelled through a small enough vicinity around its center.

I am aware that this is a NP-hard problem and I am not looking for a revolutionary algorithm.

Finding the most efficient paths to cover an area from multiple starting locations

I also found this post which seems to be a variation of the problem I'm trying to solve and it suggests looking at metaheuristics and genetic algorithms.

What I am asking for is a starting point (articles, models, concepts, working solutions for variations of this problem) which would help me and my team develop a feasible but not extremely complex solution.

Thank you!

Image source: https://socratic.org/questions/58d82905b72cff79ad7811e9

# Answer
First, note that if the shape is convex, the problem has a pretty easy heuristic solution: if each agent goes in a straight line from the start point, they can cover as much as possible by splitting the possible directions they can move in over the $n$ agents. If the maximum distance they can travel is less than the size of the region, then they'll visit a conical region, for example.

If the shape is not convex, then perhaps it can be approximated as a union of convex regions, and then the problem could be solved by assigning some subset of the agents to the nearest point in each convex subregion and then execute the algorithm above.

One way to approximate a shape by a union of convex regions is by calculating a Voronoi diagram. There's undoubtedly a rich literature on this that I unfortunately don't know much about.

Another thing that might help is routing the agents to each Voronoi cell starting from the farthest, so that you can take advantage of the fact that they will cover cells on the way. A primitive that could help with this is creating a graph that has a node per cell and edges between neighboring cells representing straight line moves, which you then run Dijkstra's algorithm on. If a cell has already been visited, you remove that node from the graph.

Ultimately the best solution is going to be strongly dependent on the geometry of the region, the distance that the agents can move, and how many agents there are. For example, if the number of agents is very small compared to the number of cells to visit, the problem is relatively easy.
> 0 votes

---
Tags: optimization, artificial-intelligence, approximation
---


# Question
Title: How can I know if more non-determinism can be used in an NFA?
I have to give the transition diagram of an NFA accepting all strings that are not empty and start and end with the same symbol, I should also use non-determinism as much as possible (language is {0,1}\*). I drew the following diagram:

Even thought this is an NFA (as all DFAs are NFAs too), I did not really use non-determinism (I don't have any case where I would go to multiple states at the same time) My question is the following: is it possible to add more non-determinism in this diagram? In general, how can I know that and how to do it if it is possible?

# Answer
> 2 votes
I'm not aware of measures of nondeterminism for NFAs (though these might exist). The instruction to use as much nondeterminism as possible is informal. It asks you to try to take advantage of nondeterminism in order to construct as simple an automaton as possible. In fact, in your case there doesn't seem to be any reasonable way to employ nondeterminism in order to simplify the automaton.

Here is an informal description of one way to solve your problem:

* "Guess" (nondeterministically) what is the symbol that the input starts and ends with.
* Verify that the input conforms to the guess.

In this case, there is no need to guess, since we can just read the first input symbol, so this is an unconvincing application of nondeterminism.

---
Tags: automata, finite-automata, nondeterminism
---


# Question
Title: Calculating Big O if unknown runtime of called functions
I haven't been able to track down if there is a generally accepted practice for assigning a Big O value when dealing with functions of unknown runtime.

Given the following pseudocode, with two functions that operate in an unknown time, is it typical to assume the processing is constant time, or would it be more correct to mention them as possible bounds?

```
function under_evaluation(n)
   int sum = 0;
   for (int x=0; x<n; x++) {
       sum = sum + mathFunction1(x);
   }
   other_value = mathFunction2(n);
   return sum + other_value;
}

```

So would the best answer for the Big O of function under\_evaluation be

* O(n)
* O(n\*O(mathFunction1))
* O(n*O(mathFunction1)) unless O(mathFunction2)\>O(n*O(mathFunction1)) in which case O(mathFunction2)

# Answer
> 3 votes
It depends on the situation. Sometimes we treat function calls as "oracle calls", and then we just count oracle calls. Your function makes $n$ oracle calls to the first function, and one oracle call to the second function.

Another option is to denote the running time of the first function by $T\_1(n)$ and that of the second function by $T\_2(n)$. Assuming that $T\_1(n)$ is monotone, this will give $O(nT\_1(n) + T\_2(n))$. If you don't want to assume that $T\_1(n)$ is monotone, then you need to define $T\_1(n)$ as the maximum running time of the first function on an input which is *at most* $n$.

# Answer
> -1 votes
The mathFunction1 and mathFunction2 must not be unknown. Either

1. no known algorithm exists for one or both of them (and it is incumbent on you to provide at least a strawman feeble/naïve attempt at that algorithm) or
2. one or more algorithms exist for both of them.

If the latter situation, then inventory all (not-unreasonable) known algorithms for each of mathFunction1 and mathFunction2, then obtain what a scientific paper for the lowest-asymptotic growth algorithm states is its big-O growth. (Or if for some reason that algorithm is unsuitable \[e.g., has good asymptotic time growth but unacceptable asymptotic space growth\], then obtain what a scientific paper for the 2nd-lowest-asymptotic growth algorithm states as its big-O growth.) Then compute your problem algorithm's big-O by utilizing the obtained big-O for both mathFunction1 and mathFunction2, then draw attention to the fact that additional work needs to be done on perhaps finding better algorithms for mathFunction1 and mathFunction2. Especially useful would be to find unproven conjectures about mathProblem1 and/or mathProblem2 that would permit a better big-O growth for one or both of them, then draw attention to these as possible future work that improves your problem algorithm's asymptotic growth.

Also, sometimes big-O (i.e., big omicron) is neither easily theoretically determinable nor easily empirically measurable in practice given worst-case inputs; in this situation small omicron, theta, big omega, and/or small omega might be calculable or empirically measurable for revealing growth-sets of inputs, which also provides a rule-of-thumb idea of mathFunction1's and mathFunction2's growth characteristics which can be utilized to calculate the corresponding small omicron, theta, big omega, or small omega for your problem's algorithm.

Without doing any of this answer in original problem's situation, stating a big-O notation for the original problem's asymptotic growth other than O(n max(O(mathProblem1),O(mathProblem2))) is little better than saying “then a miracle occurs”. It is your job to dig deeper as very very very much as you can into characterizing mathFunction1 and mathFunction2 for your research to be any more than trivially useful (if not: entirely unhelpful, depending on the situation).

---
Tags: big-o-notation
---


title: Books for learning horn clause logic

text:
# Question
Title: Books for learning horn clause logic
I want to learn prolog,two reason for that are -one can always find a counter example to the argument by searching for negation.So,one can learn by debugging the scripts.I heard that prolog is based on horn clause logic ,so want to learn more about it.

# Answer
> I want to learn prolog.

While I would not recommend learning Prolog on your own, if one insist then one of the better places to learn is from

Learn Prolog Now!

---

> So, one can learn by debugging the scripts.

If you want to try Prolog online without installing Prolog use SWISH. To debug Prolog use trace/1 or gtrace/0.

---

> Books for learning horn clause logic

To learn Prolog one does not need to dig into Horn clauses in detail. Understanding them is helpful at times. I have been programming in Prolog daily for a few years now and only when I am trying to understand the inner workings of Prolog do I really think about Horn clauses.

---

For other books and such related to Prolog see:

Useful Prolog references
> 1 votes

---
Tags: programming-languages, prolog
---


title: Difference between bits and bytes?

text:
# Question
Title: Difference between bits and bytes?
What are bits and bytes? How do they differ? What role do these notions play in the computer science world? Why do talk about 8 bits = 1 byte = 256 states or different patterns? What's the rationale behind it? Why not 4 bits = byte? What is so special about 8? How much info can a bit and a byte hold?

# Answer
> What is a bit and byte? How do they differ?

A bit is the smallest useful unit of information. A bit can only have two states, which are commonly called `0` and `1`, `False` and `True`, or `Off` and `On`.

A byte is the smallest individually addressable unit of memory in a computer system.

> Why role do these notions play in the computer science world?

As I mentioned above, a bit is the smallest useful unit of information. Information is very important in Computer Science: It has been said that Computer Science is really a misnomer, and is akin to calling Astronomy "Telescope Science" – just because computers can be used to investigate information and processes doesn't mean that they are somehow inherent to that science, just like the fact telescopes can be used to investigate planets and stars doesn't mean that telescopes are somehow inherent to astronomy.

There are some languages, for example German, French, and Italian, where the scientific discipline makes no reference to computers at all: in German, it is called *Informatik*, in French *informatique*, in Italian *informatica* – all are a neologism based on *information* and the Greek suffix *-ik*. In Spanish, it is called *ciencias de la informática* (similar to German, French, and Italian) or *ciencias de la computación*: note the subtle difference to English, it is the science of comput**ation**, not the science of comput**ers**. Danish uses the terms *datalogi* (a neologism formed by combining *data* with the *-logi* suffix as in geology, meteorology, metrology, etc.) for the stricter sense of the science of information, data, computation, and processes, and *informatik* for a broader inter-disciplinary view of the effects of "datalogi" on society, politics, humanity, and the broader world in general; what might be called *Social Informatics* in English.

As you can see, in many languages, there is a clear distinction made between "Informatics" and computers. It is a rather unfortunate accident of history that the language which confuses the two also happens to be the lingua franca for it.

Bytes, on the other hand, are not really playing a role in computer science. They *do* play a role in the organization of real-world computer systems, though. Accessing memory is an important operation in real-world computer systems, and the way the memory is addressed plays an important role in high-performance low-level code.

> Why do talk about 8 bits = 1 byte = 256 states or different patterns?

We don't. A byte is not 8 bits. A byte is the smallest individually unit of memory in a computer system. In other words: the size of a byte depends on *which* computer system you are talking about. E.g. the DEC PDP-1, PDP-4, PDP-7, PDP-9, and PDP-15 has 18-bit words consisting of 3 6-bit bytes. The DEC PDP-5, PDP-8, PDP-12, and PDP-14 has 12-bit words consisting of 2 6-bit bytes. In fact, 6-bit bytes used to be rather common. Other byte sizes that have been used are 1, 4, 7, 9, 10, 12, 18, 20, 36, and generally many different sizes between 1 and 48 bits.

> What's the rationale behind it?

There are many different trade-offs to consider when choosing the byte-size of a computer system. Traditionally, a byte had the same size as a character, and many early computers had 6-bit characters so they had 6-bit bytes. But for a DSP designed to process digital audio with a sampling bit depth of 24 bits, having both the word size and the byte size be 24 bits is completely natural.

> Why not 4 bits = byte?

There *have* been computer systems with a byte size of 4 bits. There probably still are such computer systems.

> What so special about 8?

From a theoretical perspective: nothing. From a market perspective: traditionally, bytes were the same size as characters, and first ASCII became a popular character set and encoding, which has a size of 7 bits. Even byte sizes and even more so, byte sizes which are a power of 2, are somewhat nicer to handle, so when 7-bit characters became common, 8-bit bytes became common. And once 8-bit bytes were common, 8-bit character sets (such as ISO8859-15 or Windows1252) became common, further cementing 8-bit bytes as the most common byte size.

Many networking protocols are based on 8-bit "chunks" as well, but they usually call them "octets" to make it clear that they are *always* 8 bit, even if the computer system has a different byte size.

> How much info can a bit and a byte hold?

One bit can represent 2 different unique states. A byte can represent $2^{size}$ different unique states.
> 2 votes

---
Tags: c
---


# Question
Title: Radius Local Search Algortihm for Max-Sat problem approximating ratio
Assume that in classical Local Search algorithm for MAX-SAT we could flip no more than $r \leq n/2$ variables (let's call it $r$-flip) on every iteration. More precise: on every iteration we're finding $r$-flip which satisfies more clauses then was satisfied before the flip.

What is the approximation ratio of this algorithm? Is there any worst case where my algorithm has multiplicative error 1/2?

# Answer
> 1 votes
Suppose that the all-zero assignment is a local optimum for your algorithm, for some CNF $\varphi$, say satisfying an $\alpha$ fraction of the clauses. If we choose any assignment of weight at most $n/2$, it should satisfy at most an $\alpha$ fraction of the clauses. In particular, a random assignment of weight exactly $n/2$ satisfies at most an $\alpha$ fraction of clauses. If we assume that no clauses are empty (empty clauses only work in our favor), then every clause is satisfied with probability at least $1/2$ under this distribution. Hence $\alpha \geq 1/2$, and so your algorithm gives a $1/2$ approximation.

If $\alpha = 1/2$ then all clauses are unit clauses. Since the all-zero assignment is a local optimum, this means that for each variable $x\_i$, there must be at least as many clauses $\bar{x}\_i$ than clauses $x\_i$. Hence the all-zero assignment is actually optimal. This shows that there is no worst case in which the approximation ratio is exactly $1/2$.

Perhaps this gives you a start on finding the actual approximation ratio of your local search algorithm.

---
Tags: satisfiability, approximation, maxsat
---