# Question
Title: Finding the shortest path for synchronized pawns in a maze
I have been trying to wrap my head around this problem, and I just can't get it.

* We have an $a \times b$ matrix where every cell corresponds to either an empty space, denoted with a dot, or a wall, denoted with $X$.
* There are two pawns in different locations within the maze, their movements are synchronized and they must leave the maze (it has multiple exits) in the same move.
* If one moves and the other is up against a wall, it's a valid move and the other one stays in place.
* The goal is to write an algorithm that finds the lowest possible moves to get both out of the maze at the same time, of time complexity $\mathcal O(a^2 b^2)$.

I got some advice to use BFS for this problem, but I don't get how it would deal with all of the backtracking that has to be done. I've included two visualizations with the correct paths labeled to help explain the problem.

---

**Example 1:** Pawn starting positions shown as blue squares

---

**Example 2:** Pawn starting position shown as blue square and red square

# Answer
I am going to take a guess that you are having trouble with understanding how BFS will work on this game. First, you may wonder "what is the graph we are searching on?" Let's first start with, you are *not* searching through the game board. This is not what you are doing at all.

### How to represent Game State

You are search through game *states*. I am using *game state* to mean:

> *Game state* \- a full and unique description of all pieces/players in the game at the start of any "turn" during the duration of game play. A game state is *final* when pieces are in a position that satisfies the *termination* constraint.

Termination constraint as you have define is when two pawns are both able to leave the grid with the same move. You could alternatively define it as a state right after this move has been made.

Here are some examples of game states that can be uniquely describe by a $3 \times 8$ matrix $G$ where we make each entry either: Red, Blue, White, or Black.:

1. We would have $G\_{1,1} = \text{Blue}$ and $G\_{1,4} = \text{Red}$ and assign the rest of $G\_{i,j}$ appropriately.

2. We would have $G\_{0,1} = \text{Blue}$ and $G\_{1,3} = \text{Red}$ and assign the rest of $G\_{i,j}$ appropriately.

3. We would have $G\_{0,6} = \text{Blue}$ and $G\_{1,1} = \text{Red}$ and assign the rest of $G\_{i,j}$ appropriately.

One important thing to note here is that the only thing changing in these game states is the location of Red and Blue, everything else stays the same. This should give you some indication that we only need to maintain the location of Red and Blue to get a unique description of the game state. With this idea, we can represent all three of the prior games states as:

1. $\text{Blue} = (1,1)$ and $\text{Red} = (1,4)$
2. $\text{Blue} = (0,1)$ and $\text{Red} = (1,3)$
3. $\text{Blue} = (0,6)$ and $\text{Red} = (1,1)$

To be concise I will represent them as pairs of coordinates:

1. State = $\[(1,1), (1,4)\]$.
2. State = $\[(0,1), (1,3)\]$.
3. State = $\[(0,6), (1,1)\]$.

Another important thing to note here, is that the states do not need to be "possible" in the sense that we can always reach them from our initial state. The purpose of using these states is so that we can create a graph to BFS.

---

### Graph Representation of Game States

To be able to properly "search" through the game states, we will make each state a node in our abstract graph. We will add an edge from state $s\_1$ to state $s\_2$ if we can get from state $s\_1$ to state $s\_2$ by moving both players either Up, Down, Left, or Right. Using our first example:

State $\[(1,1), (1,4)\]$ can move to:

1. State $\[(0,1), (1,4)\]$ via the Up move.
2. State $\[(1,0), (1,3)\]$ via the Left move.
3. State $\[(1,1), (1,4)\]$ via the Down move.
4. State $\[(1,2), (1,5)\]$ via the Right move.

So in a graph it would look like this:

---

### How to BFS Game States

We will be looking for the shortest sequence of moves such that we reach a *final* state. For instance, $\[(0,1), (0,6)\]$ would be a final state because they can both move Up to leave the grid. One option would be to create the entire graph, then run the BFS from our start node. However, this can be costly. We can instead generate nodes adjacent to our current node on demand. We can also check if we reach a *final* state on demand. We need to also make sure we cannot visit "invalid" board states. For instance $\[(-1,1),(1,4)\]$ would be invalid because "-1" is outside our bounds. $\[(0,0), (1,4)\]$ would also be invalid because $G\_{0,0}$ is a black square and we cannot move there.

This should be enough information to get you started. I will leave the analysis up to you. A hint on the analysis would be to consider how many game states are possible as we know in the worst cases we may visit each and all of them.
> 3 votes

---
Tags: algorithms, graphs, trees, matrices, board-games
---


# Question
Title: How to count the combinations not greater than a given volume in a knapsack problem?
You are given a certain set of items with weight wi and the volume of the bag.

Case:

```
Input:

3 (count of items) 10 (volume of the bag)
1 2 4 (weight for each item)

Output

8 (since you can put any item in or not 2 * 2 *2)

```

I have a naive solution using DFS as

```

public class Main {
    public static void main(String... args) throws Exception {
        Scanner scanner = new Scanner(System.in);
        int size = scanner.nextInt();
        int volume = scanner.nextInt();
        int[] weights = new int[size];
        for (int i = 0; i < size; ++i) weights[i] = scanner.nextInt();
        System.out.println(getCounts(weights, 0, volume));
    }

    private static int getCounts(int[] nums, int pos, int target) {
        if (target < 0) return 0;
        if (pos >= nums.length) return 1;
        return getCounts(nums, pos+1, target) +
            getCounts(nums, pos+1, target-nums[pos]);
    }
}

```

As expected, it produced `TLE` and I added cache to avoid re-calculation as

```
public class Main {
    private static int[][] cache;
    public static void main(String... args) throws Exception {
        Scanner scanner = new Scanner(System.in);
        int size = scanner.nextInt();
        int volume = scanner.nextInt();
        cache = new int[size+1][volume+1];
        for (int i = 0; i <= size; ++i) {
            for (int j = 0; j <= volume; ++j) {
                cache[i][j] = -1;
            }
        }
        int[] weights = new int[size];
        for (int i = 0; i < size; ++i) weights[i] = scanner.nextInt();
        System.out.println(getCounts(weights, 0, volume));
    }

    private static int getCounts(int[] nums, int pos, int target) {
        if (target < 0) return 0;
        if (pos == nums.length) return 1;
        if (cache[pos][target] != -1) return cache[pos][target];
        int count = getCounts(nums, pos+1, target) +
            getCounts(nums, pos+1, target-nums[pos]);
        cache[pos][target] = count;
        return count;
    }
}

```

But the OJ prompt me of memory error while the memory is within the limit =\> *13064K \< 32768K*, any idea to solve this issue?

1. Why did it fail?
2. Could a DP solution without backtracking be found for this?

Any help will be appreciated :)

Here is the original problem in Chinese.

# Answer
> 2 votes
> Why did it fail?

Look at the code `cache = new int[size+1][volume+1];`. Suppose `size` is 1 and `volume` is $10^9$. One int uses 4 bytes. So this cache will use $4 \times 2 \times 10^9$ bytes, which is about 8G, which is way much bigger than the limit, 32768K. So the online judge will show you out-of-memory error.

> Could a DP solution without backtracking be found for this?

The right strategy here is called "meet in the middle". Here is the idea of the algorithm, where $w$ is the volume of the bag.

1. Split the items into $A$ and $B$, two lists of approximately equal size.
2. Compute all possible sums of items in A, appending them to array arrA. Sort arrA.
3. Compute all possible sums of items in A, appending them to array arrB. Sort arrB.
4. For each number in arrA, find the last element in arrB such that the sum of the two is not greater than $w$. Let its index be $upper$. Add $upper + 1$ to the total.
5. Return total.

The time-complexity of the algorithm is $O(n2^{n/2})$, which comes from sorting two arrays of size about $2^{n/2}$. For $n= 30$, we get $30\times 2^{30/2}=30\times32768$, which is about 1 million.

The space-complexity of the algorithm is $O(2^{n/2})$. For example, if $n= 30$, we allocate two arrays of longs of size $2^{15}$, which spans $2\times2^{15}\times8$ bytes, which is less than 600K. We need some extra work memory for sorting and etc, which will at most triple the memory allocated specifically for our algorithm.

Here is the implementation in Java.

```
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        final int n = sc.nextInt();
        final int w = sc.nextInt();
        final long[] v = new long[n];
        for (int i = 0; i < n; ++i) v[i] = sc.nextLong();

        int total;
        if (n == 1) {
            if (v[0] <= w) total = 2;
            else total = 1;
        } else {
            final int half_n = n / 2;

            final long[] front = getSortedSums(v, 0, half_n);
            final long[] behind = getSortedSums(v, half_n, n);

            int lastIndexFront = front.length - 1;
            while (front[lastIndexFront] > w) lastIndexFront--;

            int upper = behind.length - 1;
            for (int i = 0; i <= lastIndexFront; i++) {
                while (front[i] + behind[upper] > w) upper--;
                total += upper + 1;
            }
        }

        System.out.println(total);
    }

    // Return all possible sums of elements in the specified segment of v,
    // sorted. Note the first sum is 0, representing the empty sum.
    private static long[] getSortedSums(long[] v, final int low, final int high) {
        int index = 0;
        final long[] sums = new long[1 << (high - low)];
        for (int i = low; i < high; i++) {
            long u = v[i];
            int end = 1 << (i - low);
            for (int j = 0; j < end; j++) {
                sums[++index] = sums[j] + u;
            }
        }
        Arrays.sort(sums);
        return sums;
    }
}

```

---
Tags: dynamic-programming, knapsack-problems, backtracking
---


title: Address bus and memory

text:
# Question
Title: Address bus and memory
If I have an address bus of 64K, i.e. it can access 64\*1024 or 65536 locations, should I also have a memory chip with 65536 locations in it? What I'm trying to ask is that do all the 65536 locations that the address bus can address have a corresponding memory location? Or can some address bus values go unused? (Like when I have 65536 address locations but my memory chip has only 32768 locations) Is such a combination acceptable?

# Answer
> 2 votes
What you are looking for is named "address decoding".

If a processor can address 64kB, its address bus is something like A\[15:0\]. If you use a 1kB memory chip, its addresses will be A\[9:0\].

There are several options :

* Either you don't connect the bits A\[15:10\] of the processor. The memory will be mirrored at several "places" in the CPU address map, in this example, the same memory cell is accesssed at address 0, 1024, 2048, 3072, ... etc.
* Or you use additional hardware to select the memory chip only when A\[15:10\]=00000, for example, to map the RAM only between 0 and 1023, allowing to connect other chips and map them elsewhere in the address map : ROM, IO ports...

If a memory location is not mapped, when an read access is attempted, it will generate random noise, some default value or repeat the last access. This was true on simple CPUs (for example the old 8bits CPUs)

In more advanced architectures (typically build with 16 or 32bits CPUs), accesses to non mapped memories generates an exception usually named "Bus Error".

# Answer
> 1 votes
Yes. You can have a smaller memory chip. Trying to read or write an address beyond that range might cause unpredictable behavior or meaningless results, so you'd want to avoid doing that.

---
Tags: computer-architecture, memory-hardware
---


# Question
Title: Algorithm for scheduling unit time tasks with arrival times and deadlines
Suppose we have $n$ tasks to order over $n$ days. Each tasks takes 1 day to be completed. Each task has a start date when the task becomes available and a deadline when the task must be delivered.

Here is an example:

Is there an algorithm that can solve this problem with a worst case efficiency of $O(n)$ where $n$ is the number of tasks and days.

# Answer
The more general version of your problem is the scheduling problem where we have $n$ independent tasks, each with an arrival time, a resource requirement (time), and a deadline. We define the Earliest Deadline First algorithm such that at every timepoint, we choose to process the task with the nearest deadline. While time is continuous, it is trivial to see that we can discretize time to be all points at which a task finishes or a new task arrives.

It is known that EDF is an optimal uniprocessor scheduling algorithm i.e. if there is a feasible schedule, EDF will find it and if EDF does not find a feasible schedule, then no feasible schedule exists. \[\], \[\]. However, this is not linear time if we aren't guaranteed an ordering of the deadlines of the arriving tasks. Let's use a priority queue to represent the waiting tasks. At every time point, which there are $O(n)$ of, we must insert and/or pull the next task from a priority queue sorted on deadlines. Each insertion is $O(\log n)$ time, thus resulting in $O(n\log n)$ time.

**If your input was sorted by arrival**, we could easily find whether or not there is a valid schedule by following the algorithm above, iterating through the days, adding tasks for that day to a priority queue and selecting the task with the nearest deadline from the queue. We fail if we ever try to assign a task to a day on or past its deadline.

As mentioned in the comments, we can sort the input by arrival time in linear time using counting sort or pigeonhole sort. The issue then is to somehow make the priority queue also linear time.
> 0 votes

# Answer
As each task has the atomic time step as duration, you can consider your scheduling problem as an assignment problem :

You have N tasks and N days and have to assign each task a day. Just consider a bipartite graph with N "task" nodes on a side and N "days" tasks on the other. There are edges between a task and a day when assignement is possible ($start \le day \le deadline$). The problem is now to select exactly N edges with one per task and one per day.

Then the best is probably to use an Hopcroft-Karp algorithm to look for the maximum cardinality assignment. If a perfect solution exists, it would be found else the number of "lost" task would be minimized.

This algorithm is $O(|E|\sqrt N)$ with $E$ the set of edges in the bipartite graph. If the time slots of the tasks are short with respect to the whole time horizon ($deadline - start \ll N$), then this algorithm is near-linear in the number of edges $O(|E|)$.
> -1 votes

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


# Question
Title: What is the equivalent of the integers symbol Z for n bit only integers?
We refer to the set of all integers as $\mathbb{Z}$. Now suppose we have a set of integers that can be held within a computer variable of $n$ bits width. Clearly they can only be of $2^{n}$ range, signed or not. How would we symbolise that? Is there something that is done to the zed, or does it remain simply $\mathbb{Z}$?

# Answer
> 2 votes
For bounded sets, the usual convention is to use interval notation.

Specifically, $\[a,b\]$ means "real numbers between $a$ and $b$, inclusive", while $\[a\mathinner{\ldotp \ldotp}b\]$ means "integers between $a$ and $b$, inclusive". Changing any of the square brackets to curved means that endpoint is not included: $a \not\in (a,b\]$, for example.

In this case, you'd want the interval $\[0\mathinner{\ldotp \ldotp}2^n)$. Or, if you think the delimiters look mismatched and weird, you can use $\[0\mathinner{\ldotp \ldotp}2^n-1\]$.

P.S. LaTeX doesn't have a builtin for "two dots", so I used `\mathinner{\ldotp \ldotp}` from this answer.

---
Tags: terminology, notation, integers, number-formats
---


# Question
Title: Why is the halting problem decidable for LBA?
I have read in Wikipedia and some other texts that

> The halting problem is \[...\] decidable for linear bounded automata (LBAs) \[and\] deterministic machines with finite memory.

But earlier it is written that the halting problem is an undecidable problem and thus TM can't solve it! Since LBA are defined as a type of TM, should the same not hold for them?

# Answer
The halting problem is solvable for any Turing machine which uses a known bounded amount of space, by a generalization of the argument given by Yonatan N. If the amount of space is $S$, the alphabet size is $A$, and the number of states is $Q$, then the number of possible configurations is $QSA^S$. If the machine halts then it must halt within $QSA^S$ steps, since otherwise, by the pigeonhole principle, it has a repeated configuration and so is stuck in an infinite loop. Therefore to determine whether the machine halts, we just run it for $QSA^S$ steps and see whether it halts within that time frame.
> 22 votes

# Answer
**You seem stuck with a logical problem.**

From the fact that there are books that you cannot read, you cannot infer that you cannot read any book.

Saying that the halting problem is undecidable for Turing Machines (TM) only means that there are machines for which there is no way to determine whether they halt or not by some uniform procedure that will always halt.

However there are Turing Machines that do halt. Now take a subset of Turing Machines, called the Nice Turing Machines (NTM), such that it contains only Turing Machines that do halt if and only if the tape contains an even number of symbols. If a machine M is known to be from that set, you have a simple way to decide whether M will halt: you check whether the number of tape symbols is even (it requires only two fingers).

But that procedure will not work for TM that are not in the NTM set. (too bad!)

So the halting problem is decidable for the NTM, but not for the TM in general, even though the NTM set is included in the TM set.

**This is actually critical, and sometimes forgotten, when interpreting undecidability result.**

It may well be that one can prove that an important property is undecidable for a very large family of mathematical or computational objects.

This does not mean that you should stop looking for a solution, but only that you will not find one for the whole family.

What you may then do is identify relevant subfamilies for which solving the problem remains important, and try to provide algorithms to decide whether the property holds for members of that smaller family.

Typically, halting is undecidable for TM in general, but it is decidable, often very simply, for large and useful families of automata, which can all be seen as special cases of TM.
> 10 votes

# Answer
In short, A LBA has finite number of configurations, say D. Hence, we can run for D steps and conclude the result. If it runs for more that D steps, by pigeonhole principle, we can say that, it is stuck in an infinite loop.
> 2 votes

---
Tags: turing-machines, automata, undecidability, halting-problem, linear-bounded-automata
---


# Question
Title: Question is about a paper "A Block-sorting Lossless Data Compression Algorithm" by M. Burrows and D.J. Wheeler
In the paper A Block-sorting Lossless Data Compression Algorithm by M. Burrows and D.J. Wheeler Link. On page number 5. please describe this line

> If the original string $S$ is of the form $Z^p$ for some substring $Z$ and some $p \> 1$, then the sequence $T^i\[I\]$ for $i = 0,...., N - 1$ will also be of the form $Z'^p$ for some subsequence $Z'$.

# Answer
F.e. string "abc" becomes "bca" after BWT. This means that "abcabc" will transform into "bbccaa", i.e. "external repetition" of entire string will lead to "internal repetition" of each char in transformed string.
> 1 votes

---
Tags: algorithms, data-compression, research
---


# Question
Title: Does solving all Halting problem instances 'in the limit' imply we solve an undecidable problem?
The recent Arxiv paper "Learning the undecidable from networked systems" attempts to construct a network of $N$ Turing machines$^1$ that can solve the Halting problem for any program of size $O(\log N)$. From this, they claim in the conclusion that

> This result shows that there is at least one fixed algorithm that can be distributedly run on networked randomly generated universal Turing machines, so that the entire algorithmic network can compute a function in the Turing degree $0'$, if the population/network size in large enough.

However, each network solves the Halting problem only for programs of bounded size, a restriction that makes the problem computable (For finitely many programs, there exists a look-up table that tells whether each of those programs halts). So, 'large enough' here has to mean some sort of infinity, and I do not really see how their construction extends to networks of infinite size. Am I misunderstanding their claim?

If (as I suspect), this network indeed does not solve an uncomputable problem, I also wonder whether this result is relevant to the notion of computability at all?

---

$^1$: Apparently, a halting oracle is involved as well, see section 4.2 in the paper. The authors even claim

> ... the oracle is *only* necessary to deal with the non-halting computations.

(emphasis mine) This confuses me greatly, because isn't the fact that there are non-halting computations the entire point? Also, if we are using an oracle for the halting problem anyway, why not use the oracle directly? However, even if we assume that this oracle is not nessecary, I still do not see why the main claim would hold.

# Answer
If we take 'in the limit' to mean 'a network (countably) infinite number of Turing machines', then the answer is yes, but a network of an infinite number of bits would also do.

We take some an ordering on all Turing machines. Since the number of Turing machines is only countably infinite, for each Turing machine, we can assign '0' to bit $n$ if Turing machine $n$ halts and '1' if it does not. (It does not matter that we don't know if we should put 0 or 1, since there exists a correct assignment, there exists a correct 'algorithm'. Since we don't have an infinite number of Turing machines anyway, I'm ok with a non-constructive 'algorithm') The 'network' then simply looks up the result at the $n$th bit when given Turing machine $n$ as input.
> 0 votes

---
Tags: computability, halting-problem, network-topology
---


title: Asymptotics question

text:
# Question
Title: Asymptotics question
Is $\frac {n!} {2!\cdot 4!\cdot 8!\dots (n/2)!}=O(4^n)$?

I am really stuck and I tend to believe it's true, but I don't know how to prove it.

Any help would be appreciated!

# Answer
> 18 votes
We have $$ \frac{n!}{(n/2)!(n/4)!\cdots 2!} = \frac{n!}{(n/2)!(n/2)!} \frac{(n/2)!}{(n/4)!(n/4)!} \cdots \frac{4!}{2!2!} \frac{2!}{1!1!} = \\ \binom{n}{n/2} \binom{n/2}{n/4} \cdots \binom{4}{2} \binom{2}{1} \leq 2^n 2^{n/2} \cdots 2^4 2^2 = 2^{n+n/2+\cdots+2+1} \<2^{2n} = 4^n. $$ Using Stirling's approximation we can get more refined asymptotics, but we leave this to the interested reader.

---
Tags: asymptotics, factorial, big-o-notation
---


title: Undecidability of emptiness of LBA

text:
# Question
Title: Undecidability of emptiness of LBA
How is the emptiness of Linear Bound Automata (LBA) i.e $L = \\{B \mid L(B) = \emptyset \\}$ is undecidable?

# Answer
Given a Turing machine $M$, we can construct an LBA $B$ which on input of length $n$ checks whether $M$ halts on the empty input within $n$ space. Therefore $L(B)$ is empty iff $M$ doesn't halt.
> 1 votes

---
Tags: turing-machines, linear-bounded-automata
---


# Question
Title: Least common multiple of a list of numbers
I'm trying to learn computer science by doing some challenges. One is the following.

> 2520 is the smallest number that can be divided by each of the numbers from 1 to 10 without any remainder.
>
> What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?

Let's generalize the problem from $1$ to $n$.

I thought of a loop between $n$ and $n/2$ as everything above $n/2$ is a multiple of something between $1$ and $n/2$. At each iteration, the result is the least common multiple of the loop variable and the precedent result (at the beginning the result is 1).

If I am correct, the complexity of this should be $\mathcal{O}(n/2)$. Am I right?

Is there any more efficient algorithms to solve this problem? If so witch one and what is their complexity?

# Answer
> 1 votes
Suppose that we are interested in the LCM of all numbers from $1$ to $n$. It is not hard to check that the answer is the product of $p^{k\_p}$ for all primes $p \leq n$, where $k\_p$ is the largest integer such that $p^{k\_p} \leq n$. For example, the primes at most 10 are $2,3,5,7$, and so the answer is $$ 2^3 \cdot 3^2 \cdot 5 \cdot 7 = 2520. $$ Similarly, the primes at most 20 are $2,3,5,7,11,13,17,19$, and so the answer is $$ 2^4 \cdot 3^2 \cdot 5 \cdot 7 \cdot 11 \cdot 13 \cdot 17 \cdot 19. $$

# Answer
> 0 votes
\[Answer to the complexity part\] The complexity is surely greater than O(n/2) because finding least common multiple also carries some non-constant complexity. Check out GCD by Euclidean algorithm. If you are calculating GCD of a and b, the complexity would be O(log(min(a,b)). Also, complexity of calculating GCD(a,b) and LCM(a,b) are same because one of them can be calculated in constant time if the other is known.

---
Tags: algorithms, complexity-theory
---


# Question
Title: Assume we have an algorithm HC for HAMILTONIAN CIRCUIT. How is it possible to convert the HC algorithm to an algorithm HP for HAMILTONIAN PATH?
My understanding is that I have to use the algorithm for Hamiltonian Circuit to help solve the Hamiltonian Path problem.

My understanding is that we have to perform a reduction from Hamiltonian Path---\> Hamiltonian Circuit (since we have an alg for Hamiltonian Circuit the reduction should be from Ham path---\> Ham circuit)

But in contrast, the question says CONVERT the Ham Circuit algorithm to an algorithm to an algorithm of HP. Does this imply that the Ham Circuit problem should be reduced to the Ham Path problem?

Any guidance/feedback greatly appreciated.

# Answer
> 1 votes
The wording of the question is a bit unclear. You're supposed to reduce `HamiltonianPath` to `HamiltonianCircuit`: in other words, write an algorithm that solves `HamiltonianPath` by using a subroutine for `HamiltonianCircuit`.

I assume you're specifically going for a polytime reduction, so you shouldn't do an exponential amount of work in your new program—but there are a few different types of polytime reductions (Karp vs Cook in particular), and I can't get any more specific without knowing which one you're using. In a Karp reduction, for example, you only get to call the `HamiltonianCircuit` subroutine once, and have to return its output unmodified—all the transformation has to happen before you make the subroutine call. In a Cook reduction you can call it as many times as you want, and transform the outputs however you like before returning.

# Answer
> 0 votes
Given algorithm $HC$ that solves Hamiltonian Cycle, and a graph $G = (V,E)$ in which you must decide whether a Hamiltonian Path exists:

$\bullet$ Define $G'$ as the graph obtained by adding a new vertex $v'$ to $G$ and connecting it to every $v \in V$

$\bullet$ Apply $HC$ on graph $G'$

If and only if $HC$ found a hamiltonian cycle in $G'$, there is a Hamiltonian path in $G$.

---
Tags: algorithms, complexity-theory, np-complete, reductions, decision-problem
---


# Question
Title: Path between two vertices in directed graph without cyclic vertices
I have been searching online for some time but I have not found an answer.

Is there a polynomial time algorithm to find a path in directed graph between two vertices so that within the path no *cyclic vertices* can be found:

A path $v\_1,\ldots , v\_n$ (so $v\_i\rightarrow v\_{i+1}\in E$ for all $i$) has *cyclic vertices* when $v\_{j}\rightarrow v\_i \in E$ for some $i \< j$.

For example: a the path $m \rightarrow v \rightarrow n\rightarrow u$ has cyclic vertices when $u\rightarrow v$.

# Answer
> 3 votes
My previous suggestion was wrong. So I have deleted, and will now modestly suggest another approach. Hope this works.

It seems your problem is NP hard. I will sketch a reduction from 3SAT. take a formula $\varphi$. Construct a single line of vertices, with alternatives in between. The path describes a valuation, and a verification that all clauses are true.

First, let the variables be $x\_1,x\_2, \dots,x\_n$. Then we have vertices $u\_0,u\_1, \dots u\_n$, $x\_1, \dots x\_n$, and $\bar x\_1, \dots \bar x\_n$. And we set edges $(u\_{k-1},x\_k)$, $(x\_k,u\_k)$ and $(u\_{k-1},\bar x\_k)$, $(\bar x\_k,u\_k)$ for $k=1,\dots,n$. A path from $u\_0$ to $u\_n$ sets the variables.

Now consider the $m$ clauses. We continue by having $m$ fresh vertices $v\_0,v\_1, \dots v\_m$. Connect $u\_n$ to $v\_0$. Let the $k$th clause be (for instance, to avoid too many variables) $(x\_3\lor \lnot x\_7 \lor x\_8)$. For have three vertices $c\_1, c\_2,c\_3$ for the alternatives, and connect these in parallel between $v\_{k-1}$ and $v\_k$: edges $(v\_{k-1},c\_i)$ and $(c\_i,v\_k)$. Now we want to be able to choose a path via $c\_i$ if the corresponding variable makes the clause true: so connect $c\_1$ with a back edge to $\bar x\_3$, $c\_2$ with a back edge to $x\_7$, and $c\_3$ with a back edge to $\bar x\_8$.

This somehow reminds me of a problem called Geography, which also uses a similar reduction, but is even PSPACE complete! So, check out that reduction, for reference. Your problem has no two players, and is within NP: one easily guesses and verifies a solution in polynomial time.

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


title: Simple property of DFAs

text:
# Question
Title: Simple property of DFAs
Do you know if this simple property of a DFA is stated as a property (or theorem) in some Automata theory book (possibly with a particular name)?

**Property**: Given a DFA $A = \\{ Q, \Sigma, \delta, q\_0, F \\}$, if $w = uv$ and the state of $A$ on input $w$, after scanning $u$ is $q\_i$ (when the head is at the beginning of subword $v$); and $A' = \\{ Q, \Sigma, \delta, q\_i, F \\}$ then $w \in L(A)$ if and only if $v \in L(A')$

# Answer
> 1 votes
Actually I think I have spotted this property in a book. It uses the "extended" transition relation $\delta^\*$, i.e., for strings rather than single letters.

> Other properties you would expect $\delta^\*$ to satisfy can be derived from our definition. For example, a natural generalization of the recursive statement in the definition is the formula $$\delta^\*(q,xy) = \delta^\*(\delta^\*(q,x),y))$$ which is true for every state $q$ and every two strings $x$ and $y$ in $\Sigma^\*$. The proof is by structural induction on $y$ and is similar to the proof \[...\] in Example 1.27.
>
> John C. Martin, Introduction to Languages and the Theory of Computation, McGraw-Hill, 4th edition, c2011. Page 54.

I hope you agree with me that this matches the "machine" terminology you use in your question.

---
Tags: automata, finite-automata, reference-request
---


# Question
Title: Given an array of size n, create a sub array with given conditions using dynamic programming
We are given an array of integers of size n, which is not necessarily sorted, and we want to create a sub array. We are allowed to do one of 3 tasks below in each level: 1. skip the number in original array and go to the next 2. insert the number in the start of the sub array 3. insert the number in the end of the sub array.
And at last we want the sub array to be the longest one that can be created with the conditions above and sorted. For example we have A={10,3,13} now we can insert 10 in the beginning, then 3 at the beginning and finally insert 13 in the end. so the size of sub array is 3.

I know that I must solve this using ***dynamic programming*** but I do not know how to do it exactly.

# Answer
> 2 votes
In other words, the procedure produces two subsequences of the given array such that

* the only shared element between the two is their first elements
* one of them is non-decreasing.
* one of them is non-increasing.

Let the given array be $a\[0\], a\[1\], \cdots, a\[n-1\]$. Here are the subproblems. $DP\[i\]\[j\]\[\[k\]$ is the maximal number of elements in any such two subsequences such that their shared element is $a\[i\]$, the non-decreasing sequence ends at $a\[j\]$ and the non-increasing sequence ends at $a\[k\]$. Here $0\le i$, $i\le j\lt n$ , $i\le k\lt n$ and, unless $i=j=k$, $j\not=k$.

The wanted number is the maximum of all $DP\[i\]\[j\]\[k\]$.

The base cases are $DP\[i\]\[i\]\[i\]=1$, where $0\le i\lt n$.

What is the recurrence relation? $DP\[i\]\[j\]\[k\]$ is, basically, the larger of the following two numbers.

* the maximum of $DP\[i\]\[\ell\]\[k\] + 1$ for all $\ell$ such that $i\le\ell\lt j$, $a\[\ell\]\le a\[j\]$.
* the maximum of $DP\[i\]\[j\]\[\ell\] + 1$ for all $\ell$ such that $i\le\ell\lt k$, $a\[\ell\]\ge a\[k\]$.

How will we fill the 3-dimensional table $DP\[i\]\[j\]\[k\]$? Roughly, for a fixed $i$, we will find

* $DP\[i\]\[i\]\[i\] = 1$,
* then $DP\[i\]\[i\]\[i+1\]$ and $DP\[i\]\[i+1\]\[i\]$,
* then $DP\[i\]\[i\]\[i+2\]$, (not including $DP\[i\]\[i+1\]\[i+1\]$ since $i+1 = i+1$) and $DP\[i\]\[i\]\[i+2\]$,
* $\cdots$,
* Finally, $DP\[i\]\[n-2\]\[n-1\]$ and $DP\[i\]\[n-1\]\[n-2\]$ (there is no $DP\[i\]\[n-1\]\[n-1\]$ for $i\not=n-1$ and $DP\[n-1\]\[n-1\]\[n-1\]=1$ is not helpful.)

---
Tags: algorithms, dynamic-programming, algorithm-design
---


# Question
Title: Merging rectangles into rectilinear polygon
Having a set of adjacent rectangles, what would be the algorithm that gets the rectilinear polygon wrapping around them?

# Answer
> 3 votes
* Form a list of the $4n$ edges making up the $n$ rectangles.
* Delete every edge that appears twice.

The edges that remain describe the outside of the polygon. If you want to list these edges in clockwise or anticlockwise order, that's easy enough to do -- just pick an arbitrary starting vertex and find one of the two edges it is incident on, then find the other edge that the other vertex of that edge is incident on, repeating this until you hit the original vertex again. If you encounter two edges in the same direction, you might want to turn them into a single, longer edge as you go.

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


# Question
Title: ILP representation of the number of maximal 1 sequences in a row
I am currently using an ILP to model events which occur on some input sequence from $1...n$. These events modify the input sequence in order to obtain a desired sequence. Each event can happen on some consecutive range $(i,j)$ and no two events can overlap. Therefore, I can represent events by some matrix $a=\\{0, 1\\}^{n\times n}$ where $a\_{i,j} = 1$ iff there is an event that begins at $i$ and ends at $j$ ($i\<=j$).

Unfortunately, this results in $O(n^2)$ variables and in some cases $O(n^3)$ or greater number of constraints. It would be ideal if instead I could represent these events as a row $a'=\\{0,1\\}^n$, where $a'\_i = 1 \iff \exists a\_{p,q}\quad \text{s.t.}\quad p\leq i\leq q \land a\_{p,q} = 1$
i.e. a position $a'\_i=1$ iff there is an event that modifies position $i$.

Since I am optimizing over the number of events, at the moment I am minimizing $\sum a\_{p,q}$, since it represents the number of events. If I ditch $a$ and try to only use $a'$, I am left with some row, for example $a'=\[1,1,0,...,1,0,1\]$.

**Question 1:** I want to represent the total number of events given $a'$. Currently, I am thinking $\sum a\_i(1-a\_{i+1})$ to count the number of "ends" of events. Obviously I can deal with the edge case as well. Unfortunately, this results in a product of binary variables. I know that I can represent this with a helper variable, and just sum over that, but I was wondering if there was any more efficient ways.

**Question 2:** This question is more important, since my whole model revolves around this. An event will only affect the input elements **after** the end of the event. Think of events as duplications. If some range $(i,j)$ is duplicated, all elements **after** $j$ would shift to the right by $j-i+1$ slots. Following this idea of events being duplications, consider the input below:

$a,b,c,d,e$ and the desired sequence $a,b,a,b,c,d,e,d,e$. We can achieve this by duplicating $a,b$ and $d,e$ i.e. $a'=\[1,1,0,1,1\]$. Notice how positions $0$ and $1$ did not shift at all, positions $2,3,4,5,6$ were originally $0,1,2,3,4$, and positions $7$ and $8$ were originally $3$ and $4$.

Essentially, for every position $i$ in the resulting sequence, I would like to be able to determine which position $j$ it came from in the original sequence. Consider position $6$ in the resulting sequence, we can clearly see it came from position $4$. We notice that this shift of $2$. Similarly, position $5$ came from position $3$. A pattern unfolds such that the shift of position $i$ is always equal to the $\sum\_{j\<k} a'\_j$ where $k$ is the largest index such that $k\leq i \land a\_k=0$. This is the same as saying that we are taking the sum of all values of $a'$ up to the most recent $0$ before or at $i$ in $a'$.

How can I model such shifting in an ILP? I.e. given $a’$, how can I create a variable $h$ in the ILP such that $h\_{r, l}=1$ iff $\sum\_{j\<k} a'\_j= l$ where $k$ is the largest index such that $k\leq r \land a\_k=0$.

# Answer
I think this can be done with $9n$ variables, instead of $n^2$. Define the following integer variables for use in your linear program:

* $a\_i = 1$ if index $i$ is within an event
* $s\_i = 1$ if an event starts at index $i$
* $e\_i = 1$ if an event ends at index $i$
* $c\_i = $ the number of positions until the end of this event (so that index $i+c\_i-1$ is the end of the event containing $i$), if $i$ is in an event, or $0$ if $i$ is not in an event
* $d\_i = $ is how many positions since the start of the event (so that index $i-d\_i+1$ is the start of the event containing $i$), if $i$ is in an event, or $0$ if $i$ is not in an event
* $\ell^1\_i = $ the length of the event containing $i$, if $i$ is the end of an event, or $0$ if $i$ is not the end of an event
* $\ell^2\_i = $ the length of the event containing $i$, if $i$ is the start of an event, or $0$ if $i$ is not the start of an event
* $o^1\_i = $ the amount index $i$ is shifted when copying to the new array, for the first copy of that element
* $o^2\_i = $ the amount index $i$ is shifted when copying to the new array, for the second copy of that element

These can be enforced with the following equations:

* $s\_i = a\_i \land \neg a\_{i-1}$ (see Express boolean logic operations in zero-one integer linear programming (ILP) for how to enforce this)
* $e\_i = a\_i \land \neg a\_{i+1}$
* $c\_i \ge c\_{i+1} + 1 - n s\_{i-1}$, $c\_i \le c\_{i+1} + 1$, $c\_i \le n a\_i$, $c\_i \ge e\_i$, $c\_i \ge 0$
* $d\_i \ge d\_{i-1} + 1 - n e\_{i-1}$, $d\_i \le d\_{i-1} + 1$, $d\_i \le n a\_i$, $d\_i \ge s\_i$, $d\_i \ge 0$
* $\ell^1\_i \le n e\_i$, $\ell^1\_i \ge d\_i - n(1-e\_i)$, $\ell^1\_i \ge 0$
* $\ell^2\_i \le n s\_i$, $\ell^2\_i \ge c\_i - n (1-s\_i)$, $\ell^2\_i \ge 0$
* $o^1\_i = o^1\_{i-1} + \ell^1\_{i-1}$, $o^1\_0 = 0$
* $o^2\_i = o^2\_{i-1} + \ell^2\_i$, $o^2\_0 = 0$

Then the total number of events is $s\_1+\dots+s\_n$, and you can model shifting as follows: index $i$ in the original array is shifted to indices $i+o^1\_i$ and $i+o^2\_i$ in the new array.

Do check my work carefully. There could easily be off-by-one errors or other mistakes in the above.
> 1 votes

---
Tags: algorithms, linear-programming, integer-programming, substrings, subsequences
---


# Question
Title: Sieve of Eratosthenes vs. Sieve of Sundaram
Relevant Information:
Sieve of Eratosthenes
Sieve of Sundaram

Suppose I want to generate all primes in `[2,n]`, and I have both of these algorithms at my disposal to get the job done. Which is preferable under what conditions?

I read that Sundaram runs in O(n log n) time, whereas Eratosthenes runs in O(n log log n) time, so it seems that Eratosthenes is preferable. However, that is just a very superficial evaluation. Are there other factors (aside from ease of implementation) to be considered? Which is the 'better' algorithm?

# Answer
> 7 votes
Although this question is old, the considerations are still relevant and there is still some lack of proper analysis on which prime sieve to choose for various purposes. In this evaluation, it is important to note that these intense considerations are only necessary for ranges of primes in the order of a hundreds of millions or more: A simple trial division algorithm can be sufficient for a range of up to about a million and just about any properly optimized sieve can sieve to a billion in a few seconds to tens of seconds in just about any language that is not interpreted (compiled or Just-In-Time - JIT - compiled to native code). It is large ranges of a billion an up where things get interesting in that the amount of memory used becomes a consideration such that it may be a requirement to implement page segmentation so as to be able to efficiently use the available memory.

First, note that there are three considerations on what makes a particular sieve fast, as follows:

1. The number of operations and how these operations increase for increasing ranges for a particular sieve, which latter evaluation is what is indicated by the big-O value for asymptotic execution complexity for large ranges.
2. The complexity of each individual culling operation as in machine cycles per operation which usually isn't considered in given big-O functions as per point 1.
3. The ability to add page segmentation without impacting excessively on the above two requirements, which segmentation is necessary to reduce memory requirements for large ranges so the sieve can be run at all, to achieve better cache associativity which otherwise will have a (large) negative impact on point 2 above.

Many mistakenly think that the best big-O performance is the best algorithm, but that is an error in analysis: An algorithm may have the best big-O performance as in (say) O(N) for sieving (where `N` is the sieving range) but require either many more operations or such complex operations that the execution time for each operation is so high that the total time to execute to a given range may be much higher than for an algorithm with less operations/complexity such that it can never catch up to an algorithm with worse big-O performance for practical achievable sieving ranges; thus, it is usually not the best or only consideration for comparison and is more useful for predicting the performance of a given algorithm with increasing range **as compared to itself**.

The main three contenders are usually the following with the given big-O performance characterizations following:

1. The Sieve of Eratosthenes (SoE) - O(N log(log (N)))
2. The Sieve of Sundaram (SoS) - O(N log(N))
3. The Sieve of Atkin (SoA) - O(N) (i've added this one as it is usually considered...)

Let's consider these in order:

1. First, it is pointless to implement the SoE without including the very simple "odds-only" optimization that reduces the number of operations by a factor of about two and a half to about the same number of culling operations as the sieving range. However, there is no reason to stop there, and with a little added complexity in using the maximally wheel factorized "combo sieve" as per the Wikipedia article, one can reduce this to about a quarter of the sieving range for ranges of about a billion to about a third of the sieving range for sieving ranges of about a trillion. Thus, with maximum wheel factorization the number of culling operations aren't much more than the best of the other algorithms. The majority of the inner culling loop(s) in which the SoE spends most of its time can be reduced to a very simple native code single clock cycle read/modify/write instruction with maximum optimization techniques so that even when averaged across supporting code and parts of the code that can't use this optimization, the average is still only two to three CPU clock cycles per culling cycle for ranges of trillions. While it's true that operations get gradually a little slower on the average for larger ranges, they increase relatively slower than the practical application of the other algorithms.
2. The unmodified SoS algorithm can never approach the performance of other sieves due to not specifying the proper limits for the `i` and `j` variables, which can easily be limited so that the culling function `i + j + 2ij` never exceeds one half of the culling range value as larger values exceed the sieve buffer range. However, the SoS still has many more operations than the "odds-only" SoE as it culls by the factors of all odd values rather than only the prime factors as for the SoE, which is why it has the O(N (log N)) performance rather than O(N ((log (log N))) performance; this makes a significant difference in the number of culling operations for culling ranges of a billion and above, and while the number of operations can be reduced by such techniques as pre-culling for small values of factor, this optimization (and more) can also be applied to the SoE. Now, it could be improved by using a recursive loop so that it uses a secondary source of primes to generate the `i` values and letting the `j` values start from `i` up to maximum, and then observing that every increment from `i + j + 2ij` to `i + (j + 1) + 2i(j + 1)` is just `i + j + 2ij + (1 + 2i)` or just the value of the sieving base prime/factor, but that is exactly the algorithm for the "odds-only" SoE. Once we've optimized the SoS into the SoE, we can apply the same further optimizations as it now identical. So the SoS can not be considered as a competitor as in its simple form it is much less efficient and in its maximally optimized form it is the SoE.
3. The SoA is by definition a wheel factorized sieve by the prime factors of 2, 3, and 5. The SoA once (and perhaps still does) enjoy quite a bit of Internet hype due to it's very good big-O performance of O(N). However, while it does perform according to that relation with a constant about 0.2517 times N number of culls starting at a very low N value, all is not so rosy as believed: It doesn't match that combined performance for any reasonably large range requiring page segmentation where primes squares-free spans get huge as compared to the page segment range and the complexity of the continuously increasing culling span means that the true combined big-O performance is much worse than that of the fully wheel optimized Sieve of Eratosthenes while the code complexity in implementing it even this efficiently is worse than the maximally wheel factorized SoE. Much of the confusion comes about due to the reference page segmented implementation of the SoE by Atkin and Berstein, which, while reasonably fast in sieving to a billion, did not prove (even close) its claim of linear asymptotic big-O complexity with increasing range as it is very slow for larger ranges, and only beat the reference SoE to which it is compared for a range of a billion by artificially limiting the level of wheel factorization of that implementation. As to the culling speed, due to the increased complexity of the span increasing with every successive operation, typical speed is about twice as slow as for the SoE in CPU cycles per operation, so it would have to have half the number of operations as the maximally wheel factorized SoE, which it never does within practical ranges.

In conclusion, for large sieving ranges using page segmentation, the Page Segmented SoE is a clear winner with the number of cull operations ranging only up to about 0.35 to very large ranges of 1e16 or more and the number of machine cycles when efficiently compiled to native machine code as little as under two CPU clock cycles per operation for small ranges under a billion and only increasing to the order of ten CPU cycles per operation for very large ranges (of about 1e19) in some common implementations such as primesieve, which can also be multi-threaded for even faster execution times. Even when compiled in Just-In-Time (JIT) environments such as the Java Virtual Machine (JVM), Microsoft's DotNet, or even JavaScript engines as are builtin to modern browsers, the performance is still only about ten CPU cycles per operation with the number of operations the same. In contrast, the unmodified SoS is many times slower and when fully optimized just becomes the SoE with its only feature over the SoE that it doesn't need the secondary primes feed for a page segmented version and thus the code optimized to the same extent is somewhat simpler, and the SoA never comes anywhere close to the number of CPU clock cycles per cull operation at any point as for larger culling ranges such that the reduced number of culling operations is never enough lower to make up for this discrepancy nor for the increased complexity of implementation.

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


title: Constant factor of an array

text:
# Question
Title: Constant factor of an array
In *Elements of Programming Interviews in Python* by Aziz, Lee and Prakash, they state on page 41:

> Insertion into a full array can be handled by resizing, i.e., allocating a new array with additional memory and copying over the entries from the original array. This increases the worst-case time of insertion, but if the new array has, for example, a constant factor larger than the original array, the average time for insertion is constant since resizing is infrequent.

I grasp the concept of amortization that seems to be implied here, yet they seem to imply that in other cases, a newly allocated array could possess a constant factor *smaller* than the original array. Is that so? What does "constant factor" mean in this particular context? I'm having trouble understanding what's being said here.

# Answer
> 5 votes
That's probably a typo or poor wording -- in the quote, "has" should be "is".

# Answer
> 3 votes
This approach suggest to pick any constant factor $k\>1$ and use that whenever one needs to reallocate the array. That is, each time the array becomes full and has $n$ elements, a new array of size $k\cdot n$ is allocated, and data is copied from the old array.

It is important here to multiply the size by a constant $k$ rather than, say, adding a fixed amount of additional entries (moving from $n$ to $n+k$) to achieve a better amortized complexity.

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


title: Limitations of DFA

text:
# Question
Title: Limitations of DFA
In this link it is mentioned:

> A DFA is not powerful enough to recognize many context-free languages because a DFA can't count.
>
> But counting is not enough -- consider a language of palindromes, containing strings of the form $ww^R$. Such a language requires more than an ability to count; it requires a stack.

I would extremely appreciate if someone could explain in simple words or refer a tutorial what is the meaning of not being able to count.

Moreover, DFA does not accept $\\{0^n1^n \mid n \ge 1\\}$ because it can't count or because it does not have stack?

Any help to clarify above points is truly appreciated.

# Answer
DFA has a finite memory. By finite memory, I mean, It can not store any information of infinite length. Let's take an example, $$ l = {0^n1^n | n \> 0} $$ This is a very simple example of a language which can not be recognized by a DFA, because, to accept a word of the above language, the DFA need to count the number of 0's seen. The number of 0's can be infinite as n has no upper bound. Therefore this language is an irregular language. But if he we have an upper bound to n, then then any word of the language will be finite length and can be recognized by a DFA (just make those many number of states in the worst case).
Now, let's take another example: $$ l = { (01)^n | n \> 0 } $$ The words of languge l can be of infinite length. But it does not imply that it is a irregular language, i.e. can not be recognized by any DFA, Because it has a pattern. DFA does not need to memorize the input symbol seen two states before the current state, hence, a finite memory can do the job.
In your example, $$ l = { WW^R} $$ DFA has to memorize the contents of W first, to recognize it's reverse, and there is no upper bound on the length of W. Hence it requires an infinite memory. This is very nice tutorial playlist on theory of computation by Prof. Harry Porter. The first 3 videos should clarify your doubts.
> 1 votes

---
Tags: automata, finite-automata, counting
---


# Question
Title: Regular Expression: L= {w | every even position of w is '1'}
I am trying to solve a regular expression of binary string where every even position is a '1'

I've solved this for an **odd position**: (1(0+1))\*(1+ε)

How would it look like for an even position then? Thanks in advance.

# Answer
An odd position can either have 0 or 1 and every even position can only have 1. RE for this can be: $$ ((0 + 1)1)^\* (\epsilon + (0+1))$$ Note that, it also contains the empty word.
> 2 votes

---
Tags: automata, regular-expressions
---


# Question
Title: Finding a complexity by solving inequality
I would like to calculate the complexity of an algorithm using the "inequality strategy".

This algorithm takes two integers as an entry $n, m$. Moreover this algorithm is recursive and if we denote $C\_{n,m}$ the number of operations this algorithm does for entry $n, m$ we have the following inequality :

$$C\_{n,m} \leq C\_{n, (m-1)} + C\_{(n-1), (m-1)} + O(1)$$

Moreover the algorithm terminates for the entry : $(0,k)$ and $(k, 0)$ for all $k \in \mathbb{N}$ and $C\_{0,k} = O(1)$ and $C\_{k, 0} = O(1)$.

So now I need to somehow solve the inequality to get $C\_{n,m}$ for all $n, m$. Yet I don't really know how to do this.

The problem is that it seems to me that any function work. For example If I say : $C\_{n,m} = O(m)$ then it's tre since by unduction we then have :

$C\_{n,m} \leq O(m-1) + O(m-1) + O(1) = O(m-1)$

Moreover If I say that : $C\_{n,m} = O(n)$ then it also work since by induction :

$C\_{n,m} \leq O(n) + O(n-1) + O(1) $

So what is the problem with I am doing, and how to solve this inequality to get the complexity of $C\_{n,m}$ ?

Thank you !

# Answer
You can’t use $O(m) + O(m) = O(m)$ in an inductive proof, since the hidden constant will keep blowing up. To see this more closely, suppose that you bound $C\_{n,m}$ with $A\cdot m$. Then $$ C\_{n,m} \leq C\_{n,m-1} + C\_{n-1,m-1} + O(1) \leq 2A(m-1) + O(1). $$ The right-hand side will generally not be at most $Am$.

Instead, let's try to use Pascal's identity, $\binom{a}{b} = \binom{a-1}{b} + \binom{a-1}{b-1}$. We guess that $C\_{n,m} \leq A\binom{m}{n}-B$. Then $$ C\_{n,m} \leq C\_{n,m-1} + C\_{n-1,m-1} + O(1) \leq \\ A\left(\binom{m-1}{n} + \binom{m-1}{n-1}\right) - 2B + O(1) = A \binom{m}{n} - 2B + O(1). $$ For $B$ larger than the hidden constant in $O(1)$, the right-hand side will be at most $A\binom{m}{n} - B$, and so we will be able to prove the induction hypothesis. For given $B$, we can choose large enough $A$ so that $C\_{0,k} \leq A \binom{k}{0} - B$ would hold. However, we reach a problem when considering the other base case $C\_{k,0} \leq A \binom{0}{k} - B$. Therefore we need to fix our strategy.

At this point, we leave it to the reader to find the right binomial coefficient to add.
> 1 votes

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


# Question
Title: Understanding paging and internal fragmentation
I am currently studing questions but stuck on this one, I hope someone can help me out to understand.

**Question**: Assume that we have a paged virtual memory with a page size of 4Ki byte. Assume that each process has four segments (for example: code, data, stack, extra) and that these can be of arbitrary but given size. How much will the operating system loose in internal fragmentation?

**The answer is**: Each segment will in average give rise to 2Ki byte of fragmentation. This will in average mean 8 Ki byte per process. If we for example have 100 processes this is a total loss of 800 Ki byte.

**My question**: That 2Ki byte each segment is confusing but I think that is just a guess. Anyway, if we have 8Ki byte per process, that would not even fit in a 4Ki byte page isn't that actually a external fragmentation? Can someone explain the correct answer that is easier to understand?

# Answer
> 1 votes
1. If each page is 4 KB and segment has arbitrary size, then you lose from 0 to 4095 bytes on each segment, i.e. 2 KiB at average
2. I think it can be called internal fragmentation for pages, but external one for segments

---
Tags: virtual-memory, paging
---


# Question
Title: How do we know $\neg \neg LEM$ isn't provable in MLTT?
I've been trying (fruitlessly) to prove something which I now know is not provable. Take the following definitions: $$LEM \equiv \prod\_{A : Type} \neg A \vee A$$ $$DNE \equiv \prod\_{A : Type} \neg \neg A \to A$$ $$C(x) \equiv DNE \to x$$ I wanted to prove $\prod\_{A : Type} C(A) \to \neg \neg A$. In trying to prove it the key thing to prove seemed to be $\neg \neg DNE$. I couldn't figure out how to prove this however. I thought it must be provabale however. Note that the above would be logically equivalent (implication goes both ways) to $\neg \neg DNE$ because the formula trivially implies it.

But this simple formula proved tricky. It feels like $\neg \neg DNE$ should hold because $DNE$ is consistent with MLTT. At least I had it in my mind that it already held but I couldn't seem to find a prove of it. Finally I started searching. I knew that $\neg \neg LEM$ was equivalent and found this: https://ncatlab.org/nlab/show/excluded+middle#DoubleNegatedPEM

This states that $\neg \neg LEM$ is not provable. This is the same as saying that $\neg LEM$ is consistent, at least in MLTT and other such theories. I'm certainly aware that there exist statements for which both the statement and its negation are equivalent but I hadn't realized that $LEM$ and $DNE$ were examples of this in MLTT. I'm kind of baffled that $\neg \neg \neg A \to \neg A$ holds but $\neg DNE$ is still consistent. That's a subtle point about quantifier placement that I must of missed last time I thought about this sort of thing.

Normally in logic when we want to show that something isn't provable we either show that a property that is preserved by all the inference rules (and holds for all axioms) is false for the given statement or we directly find a model for the logic and show that the given statement is false in the model. The only models I know for constructive logics are fairly complicated. For propositional logic we have Heyting algebra but the quantifier here leaves us no hope of using that. I vaguely recall that it is possible to extend these algebras to the quantifier case by doing something like taking the least upper bound or greatest lower bound of a set of instances of the algebra generated by substituting constants in the set being quantified over into the formula. I don't remember exactly how this works nor am I really clear that I could extend a result from first order constrictive logic (the logic of constructive set theory).

How do we know this? Do we have a simple enough model that would explain this? Do we just know from trying to prove it that we get stuck? After trying to prove it myself I feel intuitively that we'll always get stuck and I can explain it more or less as "you have a very limited number of ways to dig down and after digging down, you get stuck really quickly" but that's quite informal. Is there a meaty formal explanation of why this isn't provable?

# Answer
The task here is indeed to find a model of MLTT in which $\neg LEM$ holds (and so $\neg\neg\neg LEM$ holds as well). Realizability models have this feature, for instance; see also this. Here, MLTT functions are interpreted with codes of computable recursive functions, so the usual uncomputable functions, e.g. halting oracles, cause $LEM$ to fail.

If you define $LEM$ as ranging over all types, and not just types which are propositional (i.e. have at most one inhabitant up to propositional equality), then it is also the case that $LEM$ is inconsistent with the univalence axiom of homotopy type theory, so this version of $LEM$ is also refuted by any model which can interpret the univalence axiom. Such are the simplicial set and cubical set models.

$LEM$ is also inconsistent with parametricity, so models validating parametricity also refute $LEM$. I think formally these are considerably simpler than univalent or realizability models; see for example the reflexive graph model. Intuitively, this works by noticing that MLTT does not allow inspecting the structure of types, so any function with type $\prod\_{A : Type} A \rightarrow A$ must be the identity function. However, $LEM$ allows one to branch on whether two types are equal, allowing a function with the above type which is not the identity function on all types, e.g. negates Boolean inputs.
> 10 votes

---
Tags: logic, programming-languages, lambda-calculus, type-theory
---


# Question
Title: Vertex cover in bipartite graph from Hopcroft-Karp Algorithm
Vertex cover in bipartite graph is polynomial algorithm: by König's theorem the number of edges in a maximum matching is the number of vertices in a minimum vertex cover. I've implementated the Hopcroft Karp algorithm to find a maximum matching in the bipartite graph. I would like to get the minimum vertex cover from this.

Is there any way of adjusting Hopcroft–Karp so that it produces the minimum vertex cover, other than the obvious way of just computing the matching and then passing that to an algorithm that computes the corresponding cover?

# Answer
> 5 votes
The Wikipedia page on König's theorem gives an algorithm that converts a maximum matching to a minimum vertex cover. I'm not sure that an algorithm for finding maximum matching can be tweaked to an algorithm for finding minimum vertex cover in any other way, though it's perfectly possible.

# Answer
> 2 votes
Hopcroft–Karp fundamentally uses the fact that it's computing a matching. If you try to compute the vertex cover straight away by storing just the vertices in the cover constructed so far, the concept of "alternating path" makes no sense because it's defined with respect to a set of edges, not vertices. So it seems unlikely that there's a "Hopcroft–Karp-like" algorithm for min vertex cover that isn't just Hopcroft–Karp followed by a transformation from the matching to the cover.

(Well, I suppose you could try to construct the cover as you went along, updating it every time the matching is updated. But that's not fundamentally different and I don't see how it would be more efficient.)

# Answer
> 1 votes
This is the way.

Suppose you have left and right parts in bipartite graph and you found the maximum matching M.

Let's define orientation of edges. Those edges that belong to M will go from right to left, all other edges will go from left to right.

Now run DFS starting at all left vertices that are not incident to edges in M. Some vertices of the graph will become visited during this DFS and some not-visited.

To get minimum vertex cover you take all visited right vertices of M, and all not-visited left vertices of M.

---
Tags: algorithms, graphs, bipartite-matching
---


title: Backtracking in DFA

text:
# Question
Title: Backtracking in DFA
Is it true that backtracking is allowed in deterministic finite automaton (as mentioned in many comparisons between DFA and NDFA)? If yes, how is it possible when transition in DFA is to a single state?

# Answer
I'm not sure what your sources are here. DFAs read the characters of the input one after another, strictly in order and accept or reject according to the state they're in when they reach the end of the word. There is no backtracking.
> 1 votes

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


# Question
Title: What is the minimum type of logical system that recognizes if a formalized sentence is a well-formed formula thus reducible to the boolean value?
The formula, in the old way of using it, can contain symbols in order and a mixture that does not meet the criteria of correctness (i.e. arbitrary symbols do not form a well-formed formula (WFF) and do not conform to the grammar).

Also, a sentence written in a natural language could be in such a form that it cannot be transformed to the WFF. WFF, on the other hand, always reduces to the boolean true/false values and two-valued truth tables in predicate logic.

It is possible that we can never make a parser good enough to do English sentence transformation to an informal one perfectly. Peter Norvig has the following parser made in Python to give an idea of the process: https://github.com/norvig/pytudes/blob/master/ipynb/PropositionalLogic.ipynb

So, at the end, when a sentence cannot be transformed, by automation or by human manual work, to the well-formed formula, we need to categorize it by some way not fitting to the classical propositional paradigm.

I want to examine this interface where we decide if a logical formula is correctly formed so that we can call it WFF or if a naturally written sentence is transformable to the correctly formed propositional and predicate logic formula. I assume that this logical system, or maybe it us anticipating a larger theoretical framework, would at least entail the use of one additional type? This is: to decide if the sentence is transformable to the boolean reducible format, thus if the sentence reduces to the boolean type or not.

So, my question has a few parts. On the other hand, I'd like to get a clarification what kind of theoretical framework is required to axiomate a system that has propositional and predicate logic functionality, but also can determine, if the formula or the sentence is a boolean type at all? Related to that, what is needed to determine theoretical wise if a given sentence is well-formed at all?

Does this have something to do with language parsers and syntax checking? From that perspective, how does this affect the minimum logical paradigm required?

I hope these questions intertwine in such a way that they can be handled in one answer.

**Additional info**

For example, the following paper is discussing similar topic and introduces the logic of presuppositions and the truth-relevance concepts: https://www.researchgate.net/deref/https%3A%2F%2Fphilpapers.org%2Farchive%2FNEWMPT.pdf

Logic systems that I'm talking about are introduced in: https://www.britannica.com/topic/logic#ref1049434

Possible candidate for such logical framework might be found from this document: http://homepages.inf.ed.ac.uk/gdp/publications/Framework\_Def\_Log.pdf where the S4 modal logic is mentioned to have both truth and validity relations.

Also this cstheory topic may relate to my question: https://cstheory.stackexchange.com/questions/30541/logical-framework-vs-type-theory

I have added these clarifications due to request by D.W. If the former forum is better for handling my question, I hope it can be forwarded there.

# Answer
There is no systematic algorithm that, given any English sentence, can always determine whether it can be translated to a well-formed formula in first-order logic. The English language allows expression of statements that are inherently subjective and imprecise; the meaning of some English sentences is unavoidably a matter of opinion.
> 0 votes

---
Tags: formal-languages, logic
---


# Question
Title: Will this algorithm always solve a constrained sudoku puzzle in quadratic time?
# Constrained Puzzle Generation:

Let us say a sudoku puzzle is generated with the following procedure:

1. Gather a sequence input of 9 unique numbers in the range $\[1 .. 9\]$. Call it $S$.
2. Map $S$ to a $3 \times 3$ grid $G$ as follows: $$G\_{i,j} = \begin{cases} S\_{j} & i = 0\\ S\_{j + 3} & i = 1\\ S\_{j + 6} & i = 2 \end{cases}$$
3. Let's now call $M$ the sudoku board contained of 9 smaller $3 \times 3$ grids. (For instance $G$ will be one of these grids in the board). Define it as follows:

$$M\_{i,j} = \text{shift}(G, i + 3 j)$$

Where $\text{shift}(G, 1)$ is defined as:

* Move $G\_{0,0}$ to $G\_{0,1}$
* Move $G\_{0,1}$ to $G\_{0,2}$
* Move $G\_{0,2}$ to $G\_{1,0}$
* Move $G\_{1,0}$ to $G\_{1,1}$
* Move $G\_{1,1}$ to $G\_{1,2}$
* Move $G\_{1,2}$ to $G\_{2,0}$
* Move $G\_{2,0}$ to $G\_{2,1}$
* Move $G\_{2,1}$ to $G\_{2,2}$
* Move $G\_{2,2}$ to $G\_{0,0}$

Then define $\text{shift}(G, n) = \text{shift}(\text{shift}(G, n-1), 1)$. Basically a "shift" is moving everything one cell to the right when possible or else move it down to the leftmost position in the next row.

4. Now, for all present entries in a difficult puzzle (let's say world's hardest puzzle) we make the entries in $M$ present in the final output.

---

# Example

1. Let's say our input is $S = \[8,5,9,6,1,2,4,3,7\]$.
2. We map $S$ to $G$ and get:

$$G = \begin{bmatrix} 8 & 5 & 9\\ 6 & 1 & 2\\ 4 & 3 & 7 \end{bmatrix}$$

3. Now we can produce $M$ with the shifts which would look like the following:

$$M = \begin{bmatrix} 8 & 5 & 9 & 4 & 3 & 7 & 6 & 1 & 2\\ 6 & 1 & 2 & 8 & 5 & 9 & 4 & 3 & 7\\ 4 & 3 & 7 & 6 & 1 & 2 & 8 & 5 & 9\\ 7 & 8 & 5 & 2 & 4 & 3 & 9 & 6 & 1\\ 9 & 6 & 1 & 7 & 8 & 5 & 2 & 4 & 3\\ 2 & 4 & 3 & 9 & 6 & 1 & 7 & 8 & 5\\ 3 & 7 & 8 & 1 & 2 & 4 & 5 & 9 & 6\\ 5 & 9 & 6 & 3 & 7 & 8 & 1 & 2 & 4\\ 1 & 2 & 4 & 5 & 9 & 6 & 3 & 7 & 8\\ \end{bmatrix}$$

4. Now map this onto the present entries in a difficult puzzle like this one. We get the final grid:

$$M = \begin{bmatrix} 8 & & & & & & & & \\ & & 2 & 8 & & & & & \\ & 3 & & & 1 & & 8 & & \\ & 8 & & & & 3 & & & \\ & & & & 8 & 5 & 2 & & \\ & & & 9 & & & & 8 & \\ & & 8 & & & & & 9 & 6\\ & & 6 & 3 & & & & 2 & \\ & 2 & & & & & 3 & & \\ \end{bmatrix}$$

---

# Semi-Solver

If we assume that a sudoku puzzle was generated with this procedure we can now create a "semi"-solver. I say "semi" because we need the $3 \times 3$ grid $M\_{2,2}$ already solved for us. Let's assume we have this. As an example I will assume we are provided:

$$\begin{bmatrix} 5 & 9 & 6\\ 1 & 2 & 4\\ 3 & 7 & 8 \end{bmatrix}$$

Now we will flatten it into: $\[5,9,6,1,2,4,3,7,8\]$ and permute as follows:

```
[8, 5, 9, 6, 1, 2, 4, 3, 7]-----list 1
[7, 8, 5, 9, 6, 1, 2, 4, 3]-----list 2
[3, 7, 8, 5, 9, 6, 1, 2, 4]-----list 3
[4, 3, 7, 8, 5, 9, 6, 1, 2]-----list 4
[2, 4, 3, 7, 8, 5, 9, 6, 1]-----list 5
[1, 2, 4, 3, 7, 8, 5, 9, 6]-----list 6
[6, 1, 2, 4, 3, 7, 8, 5, 9]-----list 7
[9, 6, 1, 2, 4, 3, 7, 8, 5]-----list 8
[5, 9, 6, 1, 2, 4, 3, 7, 8]-----list 9

```

Now for each list, we will turn them into a $3 \times 3$ grid using the same mapping in step 2 above. For example list 1 would get mapped to

$$\begin{bmatrix} 8 & 5 & 9 \\ 6 & 1 & 2 \\ 4 & 3 & 7 \end{bmatrix}$$

Now we position these in the game board the same way we did as step 3 above. For example our layout would be as follows:

```
**list1**  **list4**  **list7**

**list2**  **list5**  **list8**

**list3**  **list6**  **list9**

```

In the prior example this would give us the correct solution:

$$M = \begin{bmatrix} 8 & 5 & 9 & 4 & 3 & 7 & 6 & 1 & 2\\ 6 & 1 & 2 & 8 & 5 & 9 & 4 & 3 & 7\\ 4 & 3 & 7 & 6 & 1 & 2 & 8 & 5 & 9\\ 7 & 8 & 5 & 2 & 4 & 3 & 9 & 6 & 1\\ 9 & 6 & 1 & 7 & 8 & 5 & 2 & 4 & 3\\ 2 & 4 & 3 & 9 & 6 & 1 & 7 & 8 & 5\\ 3 & 7 & 8 & 1 & 2 & 4 & 5 & 9 & 6\\ 5 & 9 & 6 & 3 & 7 & 8 & 1 & 2 & 4\\ 1 & 2 & 4 & 5 & 9 & 6 & 3 & 7 & 8\\ \end{bmatrix}$$

Then we have list 9 (our input) will always give you correct solution in quadratic time.

# Question

Will this algorithm always solve the given puzzle if we assume the puzzle input was created with these constraints?

# Answer
Let me start from correctness check, will this method always generate grids abiding sudoku rules?
In fact yes, your shift operator is simply circulant matrix, scattering boxes. Since circulant matrix always abide rules by row and column but not by box, you use permutation (scattering scheme), which now abide all rules, it will produce a subset of possible grids, let us call it $G$.

Now mapping $G\_i$ entries to some mask (here given sudoku) is bijective, since you promise to give puzzles generated that way, and those are deterministic.
There are only $9!$ grids generated that way, as far as go either way it will always work. Please note there are 6 670 903 752 021 072 936 960 grids computed by Bertram Felgenhauer and Frazer Jarvis.

Your mapping allow to recover solution if you give 9 unique numbers from grid.

Any other puzzle provided as input will simply fail.
> 4 votes

---
Tags: algorithms, sudoku
---


# Question
Title: Data structure with insert, and delete-min (or max) in $O(1)$?
Is it possible to have a data structure that supports both insertion and delete-min (or max) in $O(1)$?

You can assume the numbers that will be inserted are integers in the range \[0,n\] and that you will be inserting a maximum of n elements.

# Answer
> 2 votes
No; at least, it seems unlikely. Such a data structure would contradict the lower bound on comparison-based sorting algorithms and would imply linear-time sorting algorithms (where none is known to exist).

Suppose we want to sort $m$ numbers from the range $1..n$, where $m \ll n$. If we had your data structure, we could do that in $O(m)$ time. However, this seems implausible. The fastest comparison-based algorithm runs in time $\Theta(m \log m)$, which is larger than $O(m)$. Counting sort takes $O(m+n)$ time, which is much larger than $O(m)$ when $m \ll n$. Van Emde Boas sorting takes $O(m \log \log n)$ time, which is still larger than $O(m)$ time. Han & Thorup's sorting algorithm takes $O(m \sqrt{\log \log n})$ time, which is still larger than $O(m)$ time.

So, you should not expect there to be any data structure of the form you list, as that would imply a huge breakthrough in sorting algorithms.

However, there is probably an algorithm where those operations can be done in $O(\log \log n)$ time, or possibly even $O(\sqrt{\log \log n})$ time, by applying Van Emde Boas trees or Han & Thorup. See also https://en.wikipedia.org/wiki/Integer\_sorting#Sorting\_versus\_integer\_priority\_queues.

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


# Question
Title: Looking for two-way communication/consensus/contract algorithm for use in marriage proposal
I am looking for some sort of communication or consensus algorithm with the following properties:

* Can be used with just two parties (and ideally doesn't collapse to a trivial case with two parties)
* Requires each party to initiate some sort of communication to which the other responds (ideally in a binary way)
* Non-hierarchical
* Bonus points if it's some sort of consensus, decision-making, or contract signing algorithm

Context: my boyfriend and I are planning on getting engaged soon. For various reasons, we would both like to propose to each other. The challenge is that we don't want whichever proposal is second to feel like it was unnecessary. Since we're both computer scientists, we figure there must be an algorithmic solution to this problem! So we are looking for a communication protocol/consensus algorithm/something else in that vein in which it is necessary for both parties to initiate and respond to a communication. We will be implementing the chosen algorithm verbally, not over an actual internet connection. In case you're having a hard time picturing this, it would be kind of like how a lot of textbooks will have conversational English versions of the messages being sent under various communications protocols, e.g.:

Except we would replace "Hey. Can I talk to you?" with something more like "Will you marry me?".

Before anyone asks, yes, this is entirely symbolic/for fun, but we feel that's true of most aspects of getting engaged/married. And yes, we are nerdy enough that we will happily exchange random numbers with each other in public if that's what the protocol (or its associated cryptography) demands.

Possibilities we've considered so far:

* TCP: This was our first thought, but it's not a great fit. For connection establishment all the server sends is a SYN-ACK, which isn't really satisfying either as a response to the first proposal or as the question being asked in the second proposal. The connection termination protocol seems like it would be weird to adapt to verbal communication.
* Dining cryptographers: Would be great (although we'd have to use 0 to mean yes, which is a little gross), except it falls apart with only two parties. So we'd have to include a third person (and give them veto power over our engagement). It would be perfect for a polyamorous engagement, though!
* Some sort of blockchain consensus algorithm: All the ones I'm aware of seem like they'd collapse to a trivial case with two parties (but I could be wrong about this)
* Some sort of contract signing algorithm: Probably the best option we've found so far. These are the closest to being designed to solve the actual problem that we have, but all the ones I've seen require some sort of trusted third party (we could make that work but it wouldn't be ideal).

Does anyone know of an algorithm that is a better fit than these? Apologies if this is off-topic (I'm hoping it falls under "we do not hate fun")!

# Answer
> 3 votes
If you're feeling up for something particularly geeky, you might enjoy a fair exchange protocol, either one based on gradual release (see e.g., this paper) or one based on Bitcoin (e.g., this). The number of steps is very large though! Probably not suitable to carry out by hand.

You could try a simpler protocol:

1. Alice picks a message $m\_A$, computes a commitment $C(m\_A)$ to $m\_A$, and reveals the commitment $C(m\_A)$. For instance, maybe Alice writes down $C(m\_A)$ in view of Bob.
2. Bob picks a message $m\_B$, computes a commitment $C(m\_B)$ to $m\_B$, and reveals the commitment $C(m\_B)$ -- say, writing it down too. (Steps 1 and 2 can be done simultaneously or in any order.)
3. Alice opens her commitment to reveal $m\_A$ (e.g., she writes $m\_A$ down on the piece of paper). Bob verifies that the message matches her commitment.
4. Bob opens his commitment to reveal $m\_B$. Alice verifies that the message matches his commitment. (Steps 3 and 4 can be done in any order; but they shouldn't be started until both Steps 1 and 2 are complete.)

In your case, Alice could choose as her message "Bob, will you marry me?" or "Bob, let's not get married yet" and Bob could choose as his message "Alice, will you marry me?" or "Alice, let's not get married yet" and then you could compare at the end.

There are various ways to do a cryptographic commitment. One way is with a cryptographic hash function (you could use a web site to compute it for you). A simpler method is to secretly write down the message on a piece of paper, then put the paper in an envelope, seal the envelope, and place the envelope on the table in front of both of you.

See, e.g., https://keybase.io/blog/cryptographic-coin-flipping for a gentle introduction to related ideas.

---

Another idea is to execute a two-phase commit protocol.

---
Tags: algorithms, communication-protocols, consensus
---


# Question
Title: Why is the syntax of some programming languages very much not according to earlier conventions?
Looking at the syntax of the programming language C and others inspired by it, I cannot help but ask the question in the title. Mathematics, logic and other subjects have been existing for many ages and so have natural languages and all of their symbols. Still, instead of respecting these conventions fully, designers of languages such as C have gone against them, for example by using the very old *&*, used in logic and natural language to denote conjunction, for something totally different, or by using the well-known *=* and *==* in unexpected ways, or by using *!* for negation. Why?

Even if there were constraints to work with, certainly a programming language designer and implementor could make the syntax much more readable, less cryptic, and still concise and more natural, respecting established conventions? After all, there have been examples of that (Wirthian programming languages). And they can certainly do it these days.

Furthermore, certainly subjects such as philosophy, logic, mathematics and natural languages are very much primary and very essential subjects without which there would not even exist any computer science and no programming language. The symbols there used are very much known by many or they are at least standard. Why then go against established principles?

# Answer
Today, most people who learn a programming language know very little mathematical notation and are more familiar with other programming languages, and with symbols that are available on their computer keyboard. Of course, this wasn't the case in the 1950s and 1960s when some of the major programming language families that exist today appeared.

A lot of programming languages use a C-like syntax today because this has become the earlier convention. C established conventions such as braces `{``}` to delimit code blocks, semicolons `;` to delimit instructions, dot `.` to access an element of a compound structure by name, the equal sign `=` as the assignment operator, double-equal `==` as the equality operator and `!=` as inequality, `&&` and `||` as logical-and and logical-or, square brackets `[…]` for array indices, etc. C also participated in some conventions inherited from mathematics, such as the decimal notation for numbers, infix binary operators with parentheses for precedence, and the function call syntax with parentheses around the argument lists and commas to separate arguments `function(argument1, argument2, …)`.

The conceptors of C, like Wirth, followed some conventions already established in ALGOL. I think (but I'm not sure) that's where brackets for array access comes from.

Syntax choices are of course very strongly influenced by technical reasons: most languages use syntax that programmers will be able to type on their keyboard. To start with, most languages represent their source code as a sequence of lines, each line being itself a sequence of printable characters. This rules out some aspects of mathematical notation such as subscripts, superscripts, superposition (like the fraction notation), etc.

The set of available characters is usually limited to what typical computers of the time allow people to type easily. This self-perpetuates because operating system and keyboard manufacturers keep making these characters easily available. The basic standard set of characters today is ASCII: computer systems that don't support ASCII are extremely rare. Some of the characters in ASCII today weren't commonly available in the 1950s and 1960s, which explains why some languages that trace their roots to this time period don't use all of them.

An example of characters that are used by mathematicians, but weren't commonly available on computers at the time, is the logical operators $\wedge$, $\vee$ and $\neg$. FORTRAN and ALGOL 58 spelled them out `AND`, `OR` and `NOT`. C (following some of its ancestors) used `&&`, `||` and `!`. Mathematicians never used `&` for conjunction, as far as I know¹: that came from Latin (`&` started out as a ligature for “et”, which is how the Latin word for ”and“ is spelled). Later versions of ALGOL added ∧ and ∨ as syntax for boolean operators, but since most computers didn't have them, they allowed other spellings, including `/\` and `\/`, which contributed to the imposition of the backslash as a standard character.

Some languages stray further from classical mathematical notations than C. A major example is Lisp, where the syntax for a function call is `(function argument1 argument2 …)` and there are no infix operators. Lisp made this choice in the interest of uniformity: there is only one syntax for function calls and not many ($2+3$, $2^3$, $2x$, $\sin x$ are some examples of mathematical notations for function calls that don't follow the usual $f(x,y,\ldots)$ syntax). This uniformity has some theoretical advantages (Lisp was heavily inspired from the mathematical work on the lambda calculus), technical advantages (Lisp makes it easy to manipulate code as data objects), and sociological advantages (it makes the language easier to learn: for example you don't need to learn operator precedence).

A (basically *the*) notable language that baked in more classical mathematical notations is APL. It's still limited by the line syntax, but uses a special character set that includes characters such as $\leftarrow$, $\rightarrow$, $\neq$, $\neg$, $\subset$, $\supset$, etc. The special character set was a strong barrier to adoption because it required special software and made it harder to learn to type programs. The syntax of APL makes it very terse, and is a reasonably good fit for numerical programming, but it isn't particularly *readable*.

Beyond symbol availability, another reason for programming languages to depart from mathematical notation is the need for new concepts. Most programming languages incorporate syntax for imperative programming, with major concepts that mathematics doesn't have: operations done in sequence, assignment. For sequencing, the most logical character would have been `.` following the typography of most languages, but that character was also used in mathematics for decimal numbers. `;`, which is not used in mathematics, was the next logical candidate. For assignment, some languages tried to introduce $\leftarrow$, but since it wasn't available in typical character sets, it never really took on. The symbol `=` was a logical candidate for both equality testing (“are these things equal?”) and assignment (“make this equal to that”). C uses `=` for assignment and `==` for equality testing. Other languages made different choices. ALGOL used the arguably more fitting `:=` for assignment (more fitting because it's asymmetric, leaving the symmetric symbol `=` free for the symmetric concept of equality). PL/1 uses `=` for both and distinguishes the meaning from context, but this requires the language to distinguish between contexts that allow an assignment and contexts that allow a predicate and not to have any context that allows both. Some languages go closer to mathematical notation and use syntax like `set x = …` or `let x = …`; I think the designers of B and C considered this too verbose. I think FORTRAN was the heaviest original influence on imposing `=` for assignment.

¹ <sub> Linear logic uses $\\&$ but that's not the ordinary conjunction and that came later. </sub>
> 7 votes

---
Tags: programming-languages, language-design, syntax
---


# Question
Title: Computability - The language of all strings of even length
Define a language $L$ as follows: $$L = \\{\langle M \rangle \in \\{0, 1\\}^\* | M\text{ is a TM that halts on all strings of even length} \\}$$

I can prove that $L$ is not decidable/recursive, but is it recognisable/recursively enumerable? My intuition is that $L$ is unrecognisable because suppose there exists a TM $N$ that recognises $L$, $N$ would have to test all strings of even length which is countably infinite.

I have tried reducing $HALT^-$ to $L$ but not succeeded. Is it unrecognisable or not? How would you prove it?

Thanks.

# Answer
> 2 votes
$L$ is not recognizable. To avoid confusion, my assumption is that by $\text{HALT}^-$ you mean the language $\\{\text{code}(M) \ w \mid M \text{ does not halt on } w\\}$. We know that $\text{HALT}^-$ is not recognizable, thus showing $\text{HALT}^- \leq L$ implies that $L$ is not recognizable.

For showing that $\text{HALT}^- \leq L$, we have to give a computable mapping $\text{code}(M)\ w \mapsto \text{code}(M')$ such that $M$ does not halt on w iff $M'$ halts on all input of even length. For a given $M$ and $w$, define $M'$ to be the TM that behaves as follows: It checks the length $l$ of its input. If $l$ is uneven, it does something arbitrary. If $l$ is even, $M'$ simulates $M$ for $l/2$ steps on $w$. If $M$ halts during this simulation, $M'$ goes into an infinite loop, otherwise $M'$ halts.

You can easily verify that this mapping has the desired properties. It is clearly computable and:

* If $M$ does not halt on w, then $M'$ will for any input of even length $l$ simulate $M$ for $l/2$ steps on $w$ without the simulation halting, thus by definition $M'$ will halt afterwards.
* If $M$ does halt on $w$ (after $k$ steps), then $M'$ does not halt on all inputs of even length, because for inputs of length $2k$ it will simulate $M$ on $w$ for $2k$ steps, with the simulation halting, thus by definiton of $M'$ it will go into an infinite loop.

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


title: Adaptive vs non adaptive queries in PCP

text:
# Question
Title: Adaptive vs non adaptive queries in PCP
Consider verifiers in the usual sense:

Non adaptive : reads all positions of the proof predefined

Adaptive: Reads the proof iteratively.

Many lecture notes on PCP say the following: Adaptive verifier with q queries is equivalent to non-adaptive with some q' queries where q' is a constant and both using same randomness. In other words I think this means

Non adaptive q' queries can simulate adaptive q queries. But I don't see why? How to show this?

# Answer
> 1 votes
Consider an adaptive algorithm making $q$ queries. Fixing the randomness, we can describe the positions queried by the algorithm using a function $A$ which gets as input the answers of the preceding queries, and outputs the next position to be queried. If the bits are read from an array $x$, then the adaptive algorithm works as follows:

1. Read $b\_1 = x\_{A(\lambda)}$.
2. Read $b\_2 = x\_{A(b\_1)}$.
3. Read $b\_3 = x\_{A(b\_1b\_2)}$.
4. ...
5. Read $b\_q = x\_{A(b\_1 b\_2 \ldots b\_{q-1})}$.

To simulate this non-adaptively, we simply read $x\_{A(w)}$ for all words $w$ of length at most $q-1$. Given these $q' = 2^q-1$ non-adaptive queries, we can simulate the adaptive algorithm.

---
Tags: complexity-theory
---


# Question
Title: The expectation of the total number of pairs of keys in a hash table that collide using universal hashing
I am reading CLRS relating to perfect hashing. When computing the $$ \mathbb{E}\[\sum\_{j=0}^{m-1}{n\_j\choose{2}}\] $$

where $m$ is the number of slots in the hash table, and $n\_j$ is the number of keys in position $j$. I don't understand why we can directly conclude that

$$ \mathbb{E}\[\sum\_{j=0}^{m-1}{n\_j\choose{2}}\]\leq{n\choose{2}}\frac{1}{m} $$

I understand that since $h$ is randomly chosen from a universal hash function family, $\Pr{(h(x\_i)=h(x\_j))}\leq{\frac{1}{m}},\forall{i\neq{j}}$. I don't understand why we can use the total number of pairs (the combination part) directly because if $h(x\_i)=h(x\_j)$ and $h(x\_j)=h(x\_k)$, then we have $h(x\_i)=h(x\_k)$ immediately instead of a probability of $\frac{1}{m}$.

Someone can help me out? Thanks!

# Answer
I'm assuming that there is a (non-uniformly) random function $h\colon \[n\] \to \[m\]$, and $n\_j$ is the number of preimages of $j$.

Notice that $\binom{n\_j}{2} = \sum\_{1 \leq a \< b \leq n} 1\_{h(a) = h(b) = j}$. We have $$ \mathbb{E}\left\[\binom{n\_j}{2}\right\] = \frac{1}{2} \sum\_{a \neq b} \Pr\[h(a) = h(b) = j\] = \frac{1}{2} \sum\_{a=1}^n \sum\_{b \neq a} \Pr\[h(a) = h(b) = j\] \leq \frac{n-1}{2m} \sum\_{a=1}^n \Pr\[h(a) = j\]. $$ Summing this over $j$, we get $$ \sum\_{j=1}^m \mathbb{E}\left\[\binom{n\_j}{2}\right\] \leq \frac{n-1}{2m} \sum\_{a=1}^n \sum\_{j=1}^m \Pr\[h(a) = j\] = \frac{n(n-1)}{2m} = \frac{1}{m} \binom{n}{2}. $$
> 2 votes

---
Tags: probability-theory, hash, counting, hashing
---


# Question
Title: Sudoku Puzzles in O log n time although inefficient
Suppose, I got a hypothetical fixed list of all possible general Sudoku puzzles. I then create the pseudo-code to demonstrate the algorithm.

* The algorithm does a search to compare the indexes of elements in the puzzle that are not listed as zero.
* In other words, all the possible listed Sudoku
grids are compared until a solution is found matching solution sharing the elements with the
same index.

--

```
tuple=[.......]

tuple=[.......]

all possible Sudoku grids.

Here's our solver.

solver = input('enter the puzzle like this 10000030004000...)

if Element with Same Index solver == tuple1, tuple2,...

print (solution containing exact elements that share the indexes in
       both the solution and puzzle)

```

*Will this algorithm solve all Sudoku Puzzles in O log n time?*

# Answer
Such an algorithm *can* solve Sudoku, but it will be very slow in practice.

By definition, Sudoku is on a 9x9 grid, so there are only a fixed (finite) number of possible puzzles. Your algorithm encodes all of them. Therefore, your algorithm takes constant time, i.e., $O(1)$ time.

What this is telling you is that asymptotic analysis is not a useful tool for analyzing the running time of a Sudoku solver, as asymptotic running time focuses on how the running time grows as you increase the size of the input. With Sudoku, you can't increase the size of the input; the size of the input is fixed. Thus it doesn't even make sense to talk about asymptotic running time for solving Sudoku puzzles.

Some people do analyze a generalization of Sudoku, where instead of a 9x9 grid, we have a $k^2 \times k^2$ grid, where $k$ can be any integer. Then one can consider asymptotic running time. However, your algorithm can't be applied to this generalization of Sudoku, as there are infinitely many puzzles for this generalization, so you can't hardcode them all in the code of your algorithm -- every algorithm must be of finite length. Thus, in that setting, while asymptotic analysis does apply, your algorithmic approach no longer works.
> 4 votes

---
Tags: np-complete, sudoku
---


# Question
Title: Does the intersection of VC and CLIQUE belong to NPC?
Define: $$L=\\{(G,k) : G\text{ has a vertex cover of size at most $k$, and a clique of size at least $k$}\\}$$

I need to determine whether $L\in \mathrm{NPC}$ or $L\in \mathrm{P}$. I suspect that $L\in \mathrm{NPC}$, been trying to prove it by looking for a reduction from Vertex Cover, but couldn't find one.

# Answer
The graphs with clique size at least $k$ and VC at most $k$ have a particular structure: They can be partitioned into three sets, $C$, $I$ and a singleton $\\{s\\}$; $G\[C\]$ is a clique, $G\[I\]$ is an independent set and $s$ is just a vertex. $G\[C \cup I\]$ is what's called a split graph.

Proof: If a graph $G$ contains a clique of size $k$, then that clique uses up (at least) $k-1$ of your vertex cover budget. Let $G,k$ be a yes instance and $C$ any $k$-clique. Observe that $G - C$ is a star with possibly isolated vertices.

There are two cases: $G-C$ has edges, and $G-C$ does not have edges. The latter case is trivial, since we can let $C$ be the solution. In the former case, $G-C$ is the star graph with isolates. Let $s$ be the vertex with non-zero degree.

Both these cases lead to polynomial recognition algorithm. The one in which $G-C$ is an independent set, is the case where $G$ is a split graph. The other case has one vertex $s$ for which $G-s$ is a split graph. Guess $s$, and you're back at case 1.

As xskxzr pointed out, there is not necessarily a unique "split partition", that is, a partitioning of a split graph into the vertex sets $C$ and $I$, however, there are at most $n$ such partitions, and you can try all. This leads in the end to an $O(n^3m)$ algorithm for VC∩C, which I'm sure can be improved.
> 3 votes

---
Tags: np-complete, clique, vertex-cover
---


# Question
Title: Do regular languages belong to Space(1)?
I was wondering, if we take some regular language, will it be in Space(1)?

For a regular language X, for instance, we can construct an equivalent NFA that matches strings in the regular language.

But I cannot see why is X in Space(1).

If it is true, why is X or any other regular language in Space(1)?

# Answer
> 4 votes
A regular expression can be transformed into an NFA as you say. And an NFA can be transformed into a DFA. This latter transformation is exponential in the worst case (in terms of the size of the original NFA), but that is irrelevant. The amount of time this transformation takes is independent from the size of the input, and is thus $O(1)$.

Similarly, the size of this DFA is also independent from the size of the input, so storing it takes $O(1)$ space. No further space is needed other than the DFA, and thus a recognizer for a regular expression can run in $O(1)$ space.

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