# Question
Title: With regards to algorithms what's exactly a free-primitive?
With regards to algorithms does anyone could explain what's exactly a *free-primitive*?

By chance is a *free-primitive* any kinda sorting?

I've read about that from book *Algorithms Illuminated Part 1: The Basics by Tim Roughgarden* page 31.

# Answer
No. *Free-primitive* is not any particular algorithm. The author has himself chosen this notion to make the writing interesting.

By calling an algorithm *primitive*, he mean that the algorithm is so basic that many other complex algorithms frequently use it as a subroutine. Moreover, by calling an algorithm a *free-primitive*, he mean that the running time of the algorithm is small so that one can freely use it anytime for pre-processing etc.; it won't impact the overall running time too much. For example, sorting which has near linear running time $O(n \log n)$, is used almost most anytime in many complex algorithms like range searching, graph algorithms, scheduling problems, etc.
> 1 votes

---
Tags: algorithms
---


title: Exact cover matrix for project planning

text:
# Question
Title: Exact cover matrix for project planning
I'm trying to solve the project planning problem using DLX and exact cover matrix, but I'm struggling to find the set of constraints (columns) and the set of options (rows) to achieve this. Here is a sample that represents the main constraints of the problem.

* Each project have a set of tasks $\\{T\_1, T\_2, T\_3\\}$
* Each project have a set of resources $\\{R\_1, R\_2\\}$
* Each task has a duration ($T\_1$ has $2$ days, $T\_2$ has $3$ days, $T\_3$ has $4$ days)
* Tasks can block each other, and tasks can be blocked by $0$ or many other tasks ($T\_1$ is not blocked, $T\_2$ is blocked by $T\_1$, $T\_3$ is blocked by $T\_1$ and $T\_2$)
* Only one resource can work on task at a time
* Resource can only work on one task at a time

I tried several combinations but none of them worked for me. I'm using this npm package to test the matrix.

Can anyone help me find the right set of constraints and options to feed the matrix. Thanks in advance

# Answer
Your problem fall under deadlock avoidance and can be solved easily by Bankers algorithm.
> 0 votes

---
Tags: combinatorics
---


title: Super graph restriction based on girth

text:
# Question
Title: Super graph restriction based on girth
Let $n$ be the minimum possible size of a 4-regular graph with girth $g$. Consider a graph with a minimum degree of at least four with girth $g$, can I say that the size of such graph must be at least $n$ (as each vertex has at least four neighbours, making the graph more denser than a 4-regular graph; hence, in order to obtain the same girth it requires more vertices) or there might be such a graph with size less than $n$?
Girth is the length of the shortest cycle in the graph.

# Answer
> 0 votes
No, you can't say that, unless you prove it to be true. The way to know what you can say is to try to prove it; if you can prove it, you can say it, otherwise you can't.

It is possible that offering more freedom in the permissible degrees for each vertex allows constructing a smaller graph, so you can't trivially infer the conclusion you wish for.

---
Tags: graphs
---


# Question
Title: Fibonacci Sequence recursion algorithm and the time complexity
I am reading a free book on algorithms

http://www.cse.iitd.ernet.in/~Naveen/courses/CSL630/all.pdf

and on page 13 it says

"Compare this to the recurrence relation for Fn: we immediately see that T(n) ≥ Fn"

I do not understand how they know that T(n) ≥ Fn

if someone could explain it to me it would be much appreciated. here is a picture of the information needed

# Answer
> 1 votes
It's "explained" in t(n) formula you're adding 3 to each "passage" so it will always be greater than f(n). That's because the number of steps for finding f(n) has the same growth of f(n).
Starting from the first numbers Tn is greater than fn.

# Answer
> 2 votes
You can prove that $T(n) \geq F\_n$ by induction. For $n = 0$ and $n = 1$ we have $T(n) \geq 1$ and $F\_n \leq 1$. Suppose that the claim holds for $n-1$ and $n-2$. Then $$ T(n) = T(n-1)+T(n-2)+3 \geq F(n-1)+F(n-2) = F(n). $$

# Answer
> 1 votes
**Lemma:** For all $c\ge\log\_2\Big(\dfrac{1+\sqrt{5}}{2}\Big)\approx 0.6942$ we have $F\_n\le 2^{cn}$ for all $n\ge 0$

---

Since $T(n-1)\ge T(n-2)$ we have, $$ T(n)=T(n-1)+T(n-2)+3\ge 2T(n-1)+3\\ T(n-1)\ge 2T(n-2)+3\\ T(n-2)\ge 2T(n-3)+3\\ \vdots $$ Therefore, \begin{align} T(n)&\ge 2T(n-1)+3\ge 2\big\[2T(n-2)+3\big\]+3=4T(n-2)+9\\ &\ge 4\big\[2T(n-3)+3\big\]+9=8T(n-3)+21\\ &\ge 2^iT(n-i)+3(2^i-1) \end{align} Let's take $i=n$ and using lemma, $$ T(n)\ge 2^nT(0)+3(2^n-1)=4.2^n-3\ge 2^{n}\ge 2^{0.6942n}\ge F\_n\\ \implies\boxed{T(n)\ge F\_n} $$

# Answer
> 1 votes
The simplest way to see that $T(n) \geq f(n)$ is to note that in the definition of the function, the only two values explicitly defined are $f(0) = 0$ and $f(1) = 1.$ All the rest are defined by adding two values together. Since the only explicitly defined, non-zero value is $f(1) = 1,$ we see at least $f(n)$ additions are required, giving $T(n) \geq f(n)$ immediately.

# Answer
> 0 votes
$$T(n)=T(n-1)+T(n-2)+a$$ is a linear recurrence with constant coefficients, and its solution is obtained as usual by combining

* the general solution of the homogenous equation

$$T\_h(n)=T\_h(n-1)+T\_h(n-2),$$ which is the Fibonacci recurrence, and

* a particular solution of the non-homogeneous equation, in this case the constant $-a$:

$$-a=-a-a+a.$$

Hence

$$T(n)= c\_+\phi^n+c\_-(-\phi)^{-n}-a,$$ which grows as fast as the Fibonacci sequence.

---

Strictly speaking, it is wrong to say $T(n)\ge F(n)$, unless this is justified by the initial conditions.

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


# Question
Title: Are edge-triggered interrupts "hardware polled"?
Thanks in advance for assistance and patience with my hardware naivety

Reading the below answer about the NMI on pin 6 for an Apple 6502, and the signal on the pin falls from high to low, how does this get recognized by the edge detector to CPU food chain? Is there "hardware polling" (each cycle check/read a bit, check a line, etc.) somewhere in the food chain? Or is the change in voltage/signal a "triggering" or "notification" mechanism that obviates the need for "hardware polling" (no checking each cycle) in the food chain?

https://cs.stackexchange.com/a/57103/161733

My naive sense is the level-triggered interrupts are more analogous to "hardware polling".

But is the bottom line that the CPU (or some other hardware in the food chain) has to "hardware poll" the output from the edge or level or interrupt controllers at some point in each cycle? That the interrupt classification (edge-triggered, level-triggered) does not obviate the need for the CPU or interrupt handling food chain to "hardware poll" each cyle?

N.B. The above context is "input". When I say "hardware polling" I am not meaning a situation where the CPU is checking an external device to see if it is ready for more output.

Thanks in advance

# Answer
> 0 votes
The NMI pin on the 6502 isn't *exactly* edge-triggered. Rather, it is sampled into a latch on every cycle, and if the NMI line is asserted, the signal is held until the CPU is ready to service it.

And now, the long answer.

The 6502 timing uses a two-phase clock. The input clock signal (called $\phi\_0$) is cleaned up and inverted to generate a clean two-phase clock signal (called $\phi\_1$ and $\phi\_2$). The two clock pulses are never high at the same time, so during a clock cycle, the CPU can be said to be "in phase 1" and "in phase 2".

The 6502 hardware manual explains this.

Given this clock design, you can implement a clock-edge-triggered latch in the usual way by using two level-triggered latches: one triggered by high level feeds into another triggered by low level.

(Note: In 1976, this was called a "master-slave" design. We don't use that terminology any more for obvious reasons, but also, as we are about to see, it's not always as simple as that.)

It's a little more complex in a CPU such as the 6502, because you can't half-execute an instruction. So an NMI signal may need to be stored for a few cycles.

In 1989, Donald Hanson did a detailed analysis of the 6502, citation at the end. In that paper, he came up with a detailed block diagram. According to this analysis, the interrupt delivery circuitry contains seven flip-flops, three of which handle NMI specifically. These are labelled NMIG, NMIL, and NMIP in the diagram.

The other interesting part of the diagram are the timing logic latches, which generate signals for multi-cycle instructions. The CPU starts in state T0 at the start of an instruction, and transitions through various states up to T6, with the length of the sequence depending on the instruction.

So what happens when the external NMI signal is asserted is that a two-stage latch holds this signal until the NMI is ready to be serviced. NMI delivery doesn't commence until three conditions are met:

* The CPU is in the T0 state (i.e. no instruction is being executed).
* There isn't a RESET sequence in progress.
* The clock cycle is in phase 2.

One final point: NMI and IRQ do the same thing on a circuit level in the 6502. The main differences are:

* Priority. NMI takes priority over IRQ.
* IRQ can be masked.
* They go to different addresses.

Source:

Hanson, Donald F., *A VHDL Model for Pass Transistors Used in the 6502 Microprocessor*, Proceedings of the Fall 1989 VHDL Users' Group Meeting, Redondo Beach, CA, October 22-25, 1989, pp. 12-19 to 12-25.

**And having said all that...**

...interrupts on a modern computer work *very* differently than they did in the 1970s. When you have multiple cores, the operating system would like to control which core receives which interrupts. So today, this is all handled with message-passing between cores and external programmable I/O controllers.

---
Tags: cpu
---


# Question
Title: What us difference between distributed computing and workgroup computing?
According to the definition, distributed computing means to distributed a problem among different users while workgroup computing means to work on a problem by different users. So what's the difference between these two? Plz explain it with an example

# Answer
Distributed computing is understood as splitting a big computational task between computers on a network, to reduce the total time and share the computational resources. The whole process is organized in such a way that the subtasks are distributed to the computing nodes in a fully automated way.

Workgroup computing is more the cooperation of several *individuals* working on the same project, sharing documents to be edited or exchanging messages. The challenge of this mode of operation is to ensure data coherence and correct distribution of the updates.

---

In a way, these two concepts are the opposite of each other: distributed computing splits data between different nodes, and workgroup processing lets different actors operate on the same data simultaneously.
> 2 votes

# Answer
Workgroup is Microsoft's term for peer-to-peer local area network. Computers running Microsoft operating systems in the same workgroup may share files, printers, or Internet connection. They call small local area networks such as home or hospital as 'workgroup'. But it's performance is best with fewer number of computers. You can share resources like printers, scanner, etc,. between computers connected on workgroup. Also, it is not safe for sensitive information and there is no centralized management of the resources.

Whereas, distributed computing is the field of study in computer science. E.g. distributed database, aircraft control systems, routing algorithms, grid computing could computing etc.,

Now, I ask you one question: Can workgroup be that part of distributed computing or vice verse or both are possible? I hope this question will help you dig out more information and learn little bit more about workgroup and distributed computing.
> 0 votes

---
Tags: terminology, distributed-systems
---


title: Oracle for LBA halting on some input

text:
# Question
Title: Oracle for LBA halting on some input
Assume we have an oracle that tells, given a linear bounded automaton, if there exists an input on which it halts.

Can we then solve the real halting problem (i.e. decide if a given Turing machine halts on a given input)?

# Answer
> 1 votes
I would imagine yes. The emptiness problem for context-sensitive grammars is undecidable, presumably by a reduction from the halting problem. Given the equivalence between LBA and context-sensitive grammars, this implies that the same should hold for your problem too. I suggest you verify that this is correct by working through the proofs of these statements, to check that they indeed give an explicit reduction from the halting problem; assuming they do, you will have the answer to your question.

# Answer
> 1 votes
Yes, we can do that. The basic idea is that from an arbitrary Turing machine $M$ we can produce an LBA $C$ which checks whether its input codes a valid sequence of configurations for $M$ starting with the starting state and the empty tape, and ending in a halting state. Now we have that $C$ will accept some input if and only if $M$ halts on the empty input.

---
Tags: turing-machines, computability, halting-problem
---


# Question
Title: Is this Patricia tree implementation wrong?
I'm reading the chapter Radix Search of the book Algorithms (Robert Sedgwick).

I've made a simple implementation and something isn't behaving as expected.

In program `15.5` you can see that we start with an empty tree where the head is a null node. In figure `15.12` you can see that the null node is always the leftmost node. This is also described in the text:

> We use the convention that the leftmost link (the one correspond- ing to a key that is all 0 bits) does not point to any internal node

program `15.7` is the implementation of Patricia-trie insertion.

If you look at the code, there's never a chance for the head reference to change, let's say, to `A` as depicted in figure `15.12`.

Is this a bug?

# Answer
In *Program 15.5* they state:

> The root of the trie is at `head.l` (the link `head.r` is unused).

`head.l` *does* get assigned.
> 0 votes

---
Tags: algorithms, data-structures, binary-trees, trie
---


# Question
Title: Is there an upper bound on the number of different sorting algorithms
Is there a proven upper bound on the number of possible sorting algorithms that cannot be reduced to another sorting algorithm?

Sorting algorithms with "useless steps" wouldn't count because they can be reduced by removing the useless steps. I define a "useless step" as something that can be removed from the algorithm without affecting the result. I would consider a no-op or a wait to be a "useless step".

Wikipedia lists 44 sorting algorithms. https://en.wikipedia.org/wiki/Sorting\_algorithm

My motivation for this question is pure curiosity.

# Answer
> 1 votes
No. There are an infinite amount of sorting algorithms that are essentially distinct.

I sketch the argument below (using Yao's topological sort model).

Inputs: unordered lists

Outputs: sorted list

A sorting algorithm transforms each input (a topological sort over the discrete order) into an output (a topological sort over the linear order).

Consider any finite partial order P of size N between the discrete order and the linear order of size N. ("Between" in the refining order on partial orders).

A sorting algorithm can be created transforming topological sorts over the discrete order to topological sorts over P, which then are transformed by the algorithm to the sorted output.

For heapsort the partial order P is a binary tree that is the Hasse diagram of the underlying partial order created by the algorithm. Its topological sorts are heaps.

Clearly infinitely many different partial orders P can be chosen (where differences in structure can occur for larger input sizes N).

Each choice of P determines a new sorting algorithm. Hence infinitely many sorting algorithms (with distinct "intermediate" orders P) exist.

# Answer
> 1 votes
An obvious upper bound for the number of programs to sort $n$ numbers is $\left(\dfrac{n(n-1)}2\right)!\\,2^{(n(n-1)/2)}$, an astronomical number. This is simply established by considering that you can perform at most $\dfrac{n(n-1)}2$ distinct pairwise comparisons, in any order, and every comparison can have two outcomes. That makes a decision tree of depth $\dfrac{n(n-1)}2$.

Among these, many include useless steps resulting from the transitivity law (if $a\<b$ and $b\<c$ are known, it is useless to compare $a$ to $c$). In addition, many of these are structurally equivalent, i.e. they are identical to a renaming of the compared elements. The census of these algorithms is a terrible endeavor.

Also quite interesting are the efficient programs, i.e. requiring no more than $O(n\log n)$ comparisons, and even better, the minimum-comparisons algorithms (https://en.wikipedia.org/wiki/Comparison\_sort#Number\_of\_comparisons\_required\_to\_sort\_a\_list). This is still an open problem.

---

But for most of these sequences of comparisons, the corresponding program does not "compress" and is virtually as large as the decision tree. That makes them completely impractical.

So a more interesting question is about the number of programs of bounded length, independently of $n$, which deserve the name of *algorithms*. There is perforce a finite number of such algorithms, though for large lengths it can be huge. This is because there is a finite number of text strings of bounded length (and most of them are no sorting at all, not even valid programs).

---

Can you beat the length of this code ?

```
def sort(a, n):
    for i in range(n):
        for j in range(0, n - i - 1):
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
    return a

```

---
Tags: algorithms, sorting
---


# Question
Title: Time Complexity of Matrix Fibonacci Algorithm
In my reference, Exercise 0.4(e), Algorithms by Sanjoy Dasgupta, Christos H. Papadimitriou, and Umesh V. Vazirani, it is given that $$ \begin{bmatrix}F\_n\\F\_{n+1}\end{bmatrix}=\begin{bmatrix}0&1\\1&1\end{bmatrix}^n\begin{bmatrix}F\_0\\F\_1\end{bmatrix} $$

Prove that the running time of $fib3$ is $\mathcal{O}(M(n))$, where $M(n)$ be the running time of an algorithm for multiplying n-bit numbers, and assume that $M(n)=\mathcal{O}(n^2)$

---

**My Attempt**

Consider the idea of binary exponentiation in which,

the number $n$ has exactly $\lfloor\log\_2 n\rfloor+1$ digits in base 2, ie., we need to perform $\lfloor\log\_2 n\rfloor$ multiplications if we know the powers $a^1,a^2,\cdots,a^{2^{\lfloor\log\_2 n\rfloor}}\implies \mathcal{O}(\log n)$ multiplications at most.

So we need to compute $\lfloor\log\_2 n\rfloor$ powers of $a$, and also at most $\lfloor\log\_2 n\rfloor$ multiplications, ie., in total $\le 2\lfloor\log\_2 n\rfloor\implies\mathcal{O}(\log n)$.

---

Squaring the matrix $X$ doubles the number of bits of its entries, and we need to compute $\lfloor\log n\rfloor$ powers of $X$. $$ \text{The number of bits of the entries of }X^{\lfloor\log n\rfloor}\le 2^{\lfloor\log n\rfloor}\le 2^{\log n}=n\\\\ \implies\mathcal{O}(n) $$ $\implies $all intermediate results must be of length $\mathcal{O}(n)$

---

Now, with all these facts in mind how do we prove the claim ?

# Answer
> 1 votes
To prove that the running time is $O(n^2)$, you need to observe that not every multiplication step takes $O(n^2)$ time. For example, the first matrix multiplication can be done in $O(1)$ time. For finding all the powers $X^{2^i}$ for $i \in \\{1,\dotsc,\lfloor \log n \rfloor \\}$, if you carefully sum the complexities over all matrix multiplications, the running time would be:

$$8 \cdot (M(1) + M(2) + M(4) + M(8) + \dotsc + M(2^{\log n}))$$

where $8$ are the multiplication operations we do for one matrix multiplication.

Furthermore, to compute $X^i$ for any $i \in \\{1,\dotsc,n\\}$ using binary exponentiation, the complexity can again be bounded by $$8 \cdot (M(1) + M(2) + M(4) + M(8) + \dotsc + M(2^{\log n}))$$ since at any time we would be multiplying a matrix $X^{2^{i}}$ with a matrix $Y$ where each entry in matrix $Y$ has at most $2^i$ bits. And, multipylying matrices $X$ and $Y$ takes $M(2^i)$ time.

Thus, the total complexity is: $$16 \cdot \sum\_{i = 0}^{\log n} M(2 ^ i)$$ For $M(n) = O(n^2)$, this form a series: $$O(1) \cdot \sum\_{i = 0}^{\log n} 2 ^ {2i} = O(1) \cdot \sum\_{i = 0}^{\log n} 4^i = O(1) \cdot \sum\_{i = 0}^{\log n} \frac{4^{\log n}}{4 ^ {i}} = O(1) \cdot \sum\_{i = 0}^{\log n} \frac{n^2}{4 ^ {i}} = O(n^2) \cdot \sum\_{i = 0}^{\log n} \frac{1}{4 ^ {i}} = O(n^2)$$.

Thus the cost due to all the multiplication operations is $O(n^2)$. Note that the cost due to addition operations only take $O(n \log n)$ overall all matrix multiplications. Thus the total running time is $O(n^2)$. Such type of analysis is known as amortized analysis.

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


title: Time complexity of log(n+logn)

text:
# Question
Title: Time complexity of log(n+logn)
Is time complexity of log(n+logn) is equal to theta log(n)? Can I take only the dominants from inside of a log?

# Answer
> 0 votes
Yes.

$$\log(n)\le\log(n+\log n)=\log n+\log\left(1+\frac{\log n}n\right)\le\log n+\log(1+e^{-1}).$$

---

More generally,

$$\log(f(n))\le\log(f(n)+g(n))=\log(f(n))+\log\left(1+\frac{g(n)}{f(n)}\right)\le \log(f(n))+\frac{g(n)}{f(n)}$$ and if the last term is $o(1)$ you can drop it.

---
Tags: time-complexity
---


# Question
Title: On the equivalence between two definitions of universal hashing
Let $H=\\{h|h:X\to Y\\}$, $|X|=n$, $|Y|=m$. $H$ is a universal hash family if

**Def 1.** For any $x\_1,\ x\_2\in X$, $x\_1\neq x\_2$, $\left|\left\\{h\in H\middle| h(x\_1)=h(x\_2)\right\\}\right|\leq |H|/m$. (or what if $=|H|/m$ ?)

**Def 2.** For any $x\_1,\ x\_2\in X$, $x\_1\neq x\_2$ and for any $y\_1, y\_2\in Y$, $$ \Pr\limits\_{h\in\_u H}\left\[y\_1=h(x\_1)\ \text{and}\ y\_2=h(x\_2)\right\]=1/m^2. $$

Are these two definitions equivalent? Please give some explanations.

# Answer
No. They are not equivalent. Consider $X=Y=\\{0,1\\}$ and $H$ contains two hash functions, $h\_b(x)=x \oplus b$ where $\oplus$ represents the xor function. This satisfies definition 1, but not definition 2.

See also https://en.wikipedia.org/wiki/Universal\_hashing, which explains that definition 2 is a stronger condition.
> 0 votes

---
Tags: discrete-mathematics, hash, cryptography
---


title: Algorithm to identify common subsets

text:
# Question
Title: Algorithm to identify common subsets
Given a large dataset $D$ and multiple sets of filters that can be applied to $D$, e.g.

* $setA = \\{filterOnColorRed\\}$
* $setB = \\{filterOnAgeGreaterThan20\\}$
* $setC = \\{filterOnColorRed, filterOnAgeGreaterThan20\\}$
* $setD = \\{filterOnColorRed, filterOnAgeGreaterThan20, filterOnSizeIsLarge\\}$

where each filter is expensive (but it's unknown ahead of time how expensive each filter is, so we assume they all have a similar cost, importantly applying multiple filters at once is only as expensive as applying a single filter), it would helpful to compute the set such that:

$setA$ or $setB$ are computed first, and then $setC$ ultimately followed by $setD$, rationale being that using $setA$ or $setB$ makes it cheaper to compute $setC$, and the same can be said about using $setC$ to compute $setD$.

Is there an algorithm that can be used to solve this efficiently (assuming $N$ sets of filters, of varying sizes)?

Or is the best approach to basically build a DAG where each set of filter is a vertex, and there's an edge from $V1$ to $V2$ iff $V1$ is a strict subset of $V2$ (let's assume no two sets are equal to simplify things a bit). And then run a topological sort over this graph and process the sets in the resulting order?

As an extension to the question, given:

* $setA' = \\{filterOnColorRed, filterOnSizeIsLarge\\}$
* $setB' = \\{filterOnAgeGreaterThan20, filterOnSizeIsLarge\\}$

How about and algorithm that identifies that creating notional sets might be useful, e.g. in this case processing $filterOnSizeIsLarge$ before computing $setA'$ and $setB'$ would be beneficial.

# Answer
> 1 votes
I suggest creating a DAG, as you suggest, with one vertex per set, and an edge from set $S$ to set $T$ if $T$ is guaranteed to be a subset of $S$ (i.e., the filters of $T$ are a superset of the filters of $S$).

Then do a topological sort on the DAG, and process the sets in topologically sorted order. When computing a set $S$, with predecessors $Q\_1,\dots,Q\_k$, I can see two options:

* Use a merge join to compute the intersection $Q\_1 \cap \cdots \cap Q\_k$, scan linearly through the items in the intersection, and check which items are in $S$ (i.e., which items additionally satisfy all filters that are associated with $S$ and aren't already associated with $Q\_1,\dots,Q\_k$).
* Pick whichever set $Q\_i$ is smallest, scan linearly through the items in $Q\_i$, and check which items are in $S$ (i.e., which items satisfy all filters that are associated with $S$ and aren't already associated with $Q\_i$).

I suggest you do some benchmarking to determine which of these two strategies is faster on your dataset. My guess is that the first strategy will be faster, because it requires fewer queries to the filters.

---

If you only have a single set, and the time to check $k$ filters is the sum of the times to check each of the filters separately (rather than the time to check $k$ filters at once being the same as the time to check a single filter), see What is the optimal strategy for filtering a large collection of items with multiple filter functions?.

---
Tags: graphs, sets, topological-ordering
---


# Question
Title: How to express that a graph has Independent set of size at least $n/2$ in $\exists SO$
I am looking to provide a formula saying "A graph with $n$ vertices has an independent set $X$ of size at least $n/2$" in existentional second order logic.

(This is exercise 1.2. from Libkin's Elements of Finite Model Theory (see here for online pdf, page 10 of the book (or 23 in the pdf)).

I can express that $X$ is an independent set as follows (assume that our vocabulary containts just one binary relational symbol $E$ for the edge relation):

$$ \exists X (\forall x\forall y : X(x) \wedge X(y) \Rightarrow \neg E(x,y)) $$ However, how to express that $X$ is of size at least $n/2$?

There is a simillar example with bipartite subgraph with at least $m/2$ edges ($m$ is the number of total edges) in the same exercise.

E: For the bipartite subgraph, in fact, this is true in general, so a formula like $\forall x\colon x=x$ would describe all graphs that have bipartite subgraph with at least $m/2$ edges, however, is it expressible really as it is -- without knowing that it is in fact valid for all graphs?

Any hints?

# Answer
> 2 votes
One way to see it is to notice that asking for $|X|\ge n/2$ is the same as asking that $X$ is bigger than $V(G)\setminus X$, which can be witnessed by an injection from $V(G)\setminus X$ to $X$. Thus, the property can be expressed in the following way:

$$ \begin{align\*} |X|\ge n/2 &\iff |V\setminus X|\le|X| \\ &\iff \exists F: V\setminus X \hookrightarrow X \\ &\iff \exists F \left(\ \forall x\forall y: F(x)\neq F(y)\ \wedge\ \forall x: \neg X(x)\implies X(F(x))\ \right) \end{align\*} $$

---
Tags: graphs, logic, finite-model-theory, independent-sets
---


# Question
Title: How does this left-associative recursive descent parser work?
For personal enlightenment, I'm trying to write a recursive descent parser for lambda calculus without abstraction, i.e., just identifiers and function application.

The BNF grammar that describes the language could be this, where `<var>` is a terminal standing for identifiers:

```
<exp> ::= <exp> <var>
        | <var>

```

But this grammar can't be parsed by a recursive descent parser because it is left-recursive. So we need to rewrite it to something like this:

```
<exp> ::= <var> <app>
<app> ::= <var> <app> | ""

```

We can now write a recursive descent parser, in Standard ML here, that parallels the grammar:

```
type token = string

datatype ast =
  VAR of string
| APP of ast * ast

fun exp tokens =
  case tokens of
    [] => raise Fail "missing expression"
  | var :: tokens =>
    case app tokens of
      NONE => SOME (VAR var, tokens)
    | SOME (absyn, tokens) => SOME (APP (VAR var, absyn), tokens)

and app tokens =
  case tokens of
    [] => NONE
  | var :: tokens =>
    case app tokens of
      NONE => SOME (VAR var, tokens)
    | SOME (absyn, tokens) => SOME (APP (VAR var, absyn), tokens)

```

However, while the new grammar doesn't exhibit left-recursion, the parser that implements it will produce right-associative function application nodes. This is a fairly known limitation of recursive descent parsers.

```
- exp ["a", "b", "c"];
val it = SOME (APP (VAR "a",APP (VAR "b",VAR "c")),[])

```

Here's what puzzles me, though. I can write a function that can parse a list of tokens into an AST with the correct left-associative function application nodes, but I'm not sure why I can do that. Is this parser still a recursive descent parser? What's the grammar that it implements? Does it work because it uses a 2-token lookahead? I'm unsure.

```
fun exp tokens =
  let
    fun loop tokens ast =
      case tokens of
        [] => SOME (ast, tokens)
      | name :: rest => loop rest (APP (ast, VAR name))
  in
    case tokens of
      [] => NONE
    | name :: rest => loop rest (VAR name)
  end

- exp ["a", "b", "c"];
val it = SOME (APP (APP (VAR "a",VAR "b"),VAR "c"),[])

```

Is this a known, formalized, trick for hand-writing recursive descent parsers?

# Answer
> 1 votes
ANTLR handles direct left recursive grammar via a technic they call an oracle. You can find their paper to learn all about it.

Basically the parser remembers if it had just parsed the current non-terminal being parsed. If it hasn't, then the left recursive choice gets ignored. Otherwise the left recursive branch is visited using the parse that was remember to jump over the left recursive part.

ANTLR however can only handle direct left recursion and not indirect left recursion. So an oracle is no silver bullet.

That said. Left recursive in recursive descent parsing is extremely rare. Most people rewrite their grammars to be right recursive, if they are going to write their own recursive descent parser.

Shift reduce parsers however have no problem with left recursive or right recursion, and no problems with direct or indirect recursion either. They work from bottom up rather than top down. However the learning curve is a lot steeper, but I think it is worth it imo.

Your hand rolled code down the bottom of your post is using a loop and parsing from bottom up. It is very lightly touching on the shift-reduce parsing technique. I'd google or watch YouTube videos on implementing an LR(1) parser (its shift-reduce based). It will be very enlightening.

# Answer
> 0 votes
You can’t use recursive descent for two reasons: You don’t know which rule to apply until you have parsed the first var. And a recursive call must not parse the last var, or the caller will fail. Fortunately you can handle this easily in this case:

```
var = parse_var()
exp = make_exp(rule2, var)
while input starts with var
    var = parse_var()
    exp = make_exp(rule1, exp, var)
end while
return exp

```

---
Tags: lambda-calculus, parsers, left-recursion
---


# Question
Title: Showing that nearly regular graphs have a specific $(2,O(\log n))$ ruling set with high probability
An $(\alpha,\beta)$-ruling set is a set $S$ such that any two nodes in $S$ are at distance at least $\alpha$ from each other, and, for any node $v \notin S$, there exists a node $u \in S$ such that the distance between $u$ and $v$ is at most $\beta$.

Let $G$ be graph which is nearly regular, with all degrees in $\[k,2k\]$.

Consider the following creation of the set $S$:

each vertex $v$ chooses a random number $r\_v$ uniformly in $\[0,1\]$. If $r\_v$ is local minima, namely $r\_v \< r\_u$ for any neighbor $u \in N(v)$, then $v$ joins the set $S$.

I want to show that with high-probability, it has a set $S$ which is a $(2,O(\log n))$ ruling set.

Proving the $\alpha$ part is easy, because from the creation of $S$, only one vertex in $N^{+}(v)$ can be a local minima, and will be in $S$.

Proving the $\beta$ part is more difficult.

I can prove that $Pr\[S \cap N^{+}(v) \ne \emptyset\]$ for every $v$ with high probability. But not sure how to continue from here.

Help would be appreciated

# Answer
> 1 votes
I was about to complain that this statement:

> Then, I can prove that $Pr\[S \cap N^{+}(v) \ne \emptyset\]$ for every $v$ with high probability

is probably wrong, because it would imply a stronger result, namely that nearly regular graphs have a $(2, 1)$ ruling set w.h.p.

But then I realised that, not only does this stronger claim actually hold, an *even stronger* claim holds, and is almost trivial to show:

**Theorem:** Every graph has a $(2, 1)$ ruling set.

**Proof sketch:** Choose any vertex $v$, add it to $S$, and remove it and its neighbours (which have distance 1 from $v$). Repeat until no vertices remain. Every pair of vertices in $S$ have distance $\ge 2$ since the only vertices with distance 1 are neighbours, and we removed all of those.

This claim is stronger than the original in three ways: It applies to every graph (not just nearly regular graphs), always (not just w.h.p.), and $1 \< \log n$ except on a finite number of graphs.

This makes me wonder if you missed a condition.

---
Tags: algorithms, complexity-theory, graphs, randomized-algorithms
---


# Question
Title: Weighted sample of ~k elements from array in O(n) time?
I have an array $a$ with $n$ elements, all of which have an associated weight. For example:

$a = \\{ (A,2), (B,5), (C,9), ..., (Z,1) \\}$, such that element $A$ has weight $w\_A=2$, element $B$ has weight $w\_B=5$ and so on. The array is not necessarily sorted.

Now, I would like to obtain a sample from this array where each element is selected **without repetition** and the probability is proportional to the weight of the element.

My goal is to sample *approximately* $k \< n$ elements. I am emphasizing approximately because it does not have to be exactly $k$ but something close to $k$ is good enough. More precisely, I don't care if there is a deviation in the size of the final sample of $\pm \delta$ so long as $\delta$ is not too large in comparison to $k$ or $n$.

I know how to do the sampling in time $O(n + k \log n)$ by computing the cumulative weight $W$, then generating a random value in $\[0,W\]$ followed by a binary search to check which element this corresponds to.

However, my goal here is to understand whether it is possible to make a sampling in $O(n)$ by defining a probability $p\_i$ for each element in such a way that I can decide independently for each element whether it should belong to the sample. Meanwhile, in the end I would still have a sample with approximately the size $k$ that I am looking for. If this is possible, then I could make a single pass in array $a$ after defining the probability $p\_i$ accordingly which would require the procedure to define $p\_i$'s to be $O(n)$ too, of course.

In summary, my question is: is there a way of defining these probabilities $p\_i$ to achieve my goal? Or am I looking for an impossible solution here?

# Answer
> 1 votes
A solution should be like:

Assign the probability $p\_i$ to the element $i$ equal to the normalized weight, $\dfrac{w\_i}{w}$. Then perform $n$ systematic drawings that accept the element $i$ with probability $p\_i=kw\_i$, in turn. Then the expectation of the number of elements drawn is $k$ and the distribution is honored.

But this fails whenever $w\_i\>\dfrac1k$, which is no surprise because the elements may not be repeated, which limits their probability of appearance.

# Answer
> 0 votes
Yes, assuming we can assume that all elements are distinct. Here is one approach. Let $x\_1,\dots,x\_n$ denote the elements and $w\_i$ the weight associated to $x\_i$. Consider the following algorithm:

* For $i:=1,2,\dots,n$:
    + Let $p\_i=w\_i/(w\_i+w\_{i+1}+\dots+w\_n)$.
    + Draw $m\_i$ from a Binomial($k$, $p\_i$) distribution.
    + Output $m\_i$ copies of $x\_i$.
    + Set $k := k - m\_i$.

This outputs the right distribution.

What is its running time? Well, you can compute the $p\_i$'s in linear time, with a single backward scan. Also, you can sample a value $m$ from a Binomial($k$, $p$) distribution in $O(m)$ time. (Draw a uniform random number $q \in \[0,1\]$, then compute the tail sums of the Binomial, namely $\Pr\[m\ge j\]$ for $j:=0,1,2,\dots$, until you find the first tail sum that is $\ge q$. It takes a little bit of care to compute the tails sums, but you can do them in $O(1)$ time per tail sum.) Also, we have $m\_1+\dots+m\_n=k=O(n)$, so it follows that the total running time of this algorithm is $O(n)$.

I don't know whether this will be faster in practice. The constant factors might well dominate the difference between $O(1)$ vs $O(\log n)$.

---
Tags: probabilistic-algorithms, sampling
---


title: Verify $n\log n=\Theta(10n\log10n)$

text:
# Question
Title: Verify $n\log n=\Theta(10n\log10n)$
> How do I Verify that $n\log n=\Theta(10n\log10n)$

I think I need to prove that there exists $c\_1,c\_2\>0$ such that $c\_1.g(n)\le f(n)\le c\_2.g(n)$

*Step 1*

$$ \log n\le \log 10n\implies f(n)=n\log n\le 10n\log 10n=g(n)\\ f(n)\le c\_2.g(n)\implies f=O(g) $$

*Step 2*

$$ n\log n\ge\frac{1}{10\log 10}\big\[10n\log 10n\big\]=\frac{n\[\log 10+\log n\]}{\log 10}\\ \log n\ge 1+\frac{\log n}{\log 10}=1+\log\_{10} n\\ n\ge e^{1+\log\_{10}n} $$

is it the right way to approach the given problem without using limit ?

Note: The original statement of the problem in my reference is: In each of the following situations, indicate whether $f = O(g)$, or $f = Ω(g)$, or both (in which case $f = Θ(g)$), and one example given is $f(n)=n\log n$ and $g(n)=10n\log 10n$.

# Answer
> 1 votes
As constant factors do not matter, you can read the question as asking if

$$\log n=\Theta(\log n+c),$$ where $c\>0$.

In other words

$$a(\log n+c)\le \log n\le b(\log n+c)$$ or

$$a+\frac{ac}{\log n}\le 1\le b+\frac{bc}{\log n}.$$

Now take $\log n\_0=c$ so that

$$n\>n\_0\implies0\<\frac c{\log n}\<1$$ and you need to solve

$$2a\le1\le b.$$

---
Tags: algorithms, time-complexity, big-o-notation
---


# Question
Title: Understanding the Internal Stack Frames in a Recursive Function Call
I'm trying to understand how the system's call stack works internally when a recursive function is called. Specifically, I'm looking at a function that computes the maximum depth of a binary tree using a postorder traversal.

I do know there is a stack solution out there, but I would one that mimics the internal call as closely as possible.

Here's the tree I'm working with:

```
    1
   / \
  2   3
 / \
4   5

```

And here's the recursive function:

```
def maxDepth(root: Optional[TreeNode]) -> int:
    def dfs_postorder(node: TreeNode) -> Union[int, Literal[0]]:
        if not node:
            return 0

        left_depth = dfs_postorder(node.left)
        right_depth = dfs_postorder(node.right)
        return max(left_depth, right_depth) + 1

    return dfs_postorder(root)

```

When this function is run on the tree, it first calls itself on the root, then on the root's left child, then on the left child's left child, and so on, until it reaches a leaf. At each step, it adds a frame to the call stack.

However, I'm confused about when the right children get added to the stack. From my understanding of the code, it seems like the function would only start processing the right children after it has finished with all the left children.

For instance, after the first call to the function (with the root node `1`), I would expect the next call to be with the left child (`2`), and the system's call stack to look like this:

```
[(1, "processed"), (2, "process")]

```

where `process` means the node's left and right are yet to be explored and `processed` means we explored its left and right and probably ready to be "popped" later.

However, I've been told that even at this early stage, the call stack would also include a frame for the right child (`3`), like this:

```
[(1, "processed"), (3, "process"), (2, "process")]

```

Why is this the case? How does the system's call stack actually work in this situation?

# Answer
> 2 votes
It might be helpful to think of call-stack frames as remembering "where to return to" when a function call returns. There are two recursive calls in your example (one for the left child, and one for the right), so there are two possibilities of where those calls should return to.

Let's label these two return points, `A` and `B`:

```
    left_depth = dfs_postorder(node.left)
A:
    right_depth = dfs_postorder(node.right)
B:
    return max(left_depth, right_depth) + 1

```

All the call-stack needs to do is remember whether or not it is returning to the code at `A`, or returning to the code at `B`.

---

While processing node `2`, the stack looks something like the following. Here, the stack remembers that, when we return to node `1`, the program should continue at point `A` in the code.

```
[(node: 1, continue_at: A), (node: 2, ...)]

```

Later, the program continues with node `1` at point `A`, causing it to start processing the right child, at which point the stack looks like this:

```
[(node: 1, continue_at: B), (node: 3, ...)]

```

---

Now, to address this point:

> However, I've been told that even at this early stage, the call stack would also include a frame for the right child

This is not correct. The call-stack includes a frame that remembers it should continue at point `A`, but there is no explicit frame for the right child (yet). It just so happens that the next thing to occur at point `A` is a call that will begin processing the right child.

---
Tags: algorithms, data-structures, recursion, binary-trees
---


# Question
Title: Looking for all "valid" combinations taken from a set of things, where subsets of "valid" things are always "valid"
I have a problem where I need to find all subsets of a set that satisfy some validity function. The function has the property that if a subset is invalid, so are all its supersets, and if a subset is valid, so are all its sub-subsets.

This can clearly take exponential time if, for instance, all subsets are valid. However, there are many instances where significant optimization can be done, because if some subset isn't valid, we don't need to check any supersets of it. This suggests some optimization techniques, such as memoization and pruning, but I’m not sure how to implement them efficiently. Here are two approaches I’ve tried:

**Bottom-up:** Start with valid singletons and build larger subsets by adding elements. Stop when no more valid subsets can be formed. The challenge is how to avoid checking subsets that contain invalid "sub-subsets" we've already tried.

**Top-down:** Start with the full set and remove elements one by one. Stop when all remaining subsets are valid. The challenge is how to avoid checking subsets that are already known to be valid, because they are sub-subsets of some previously validated subset.

One strategy would be some kind of "super-memoization," where the memoizer doesn't just check if some subset has been evaluated, but knows to return false if any "sub-subset" of it has already evaluated to false, or to return true if any "super-subset" of it has already evaluated to true. I'm not sure the best way to implement this.

Another strategy, which is probably better than the above, would be to prune the search tree so we don't generate subset combinations to begin with which are supersets of something we've already evaluated false, or which are subsets of some larger subset already evaluated to true. This also seems somewhat subtle.

**My questions are:**

1. Does this problem have a name?
2. Are there standard algorithms or libraries to solve it?
3. What is the best way to do the memoization and pruning?
4. Are there any textbooks or literature on this problem?

Any help or advice would be appreciated.

# Answer
> 1 votes
This can be formulated as finding all minimal subsets for a monotone function. Here monotone captures your property about supersets and subsets.

Or, this can be formulated exact interactive learning of a DNF representation of a monotone Boolean function $f:\\{0,1\\}^n \to \\{0,1\\}$, i.e., given ability to evaluate a monotone Boolean function $f:\\{0,1\\}^n \to \\{0,1\\}$ at arbitrary points, find a DNF representation for $f$. Here 0 represents valid and 1 represents invalid, and $x=(x\_1,\dots,x\_n)$ represents a subset as follows: the subset contains the $i$th item iff $x\_i=1$.

# Valiant's algorithm

There is a simple algorithm from Valiant for learning such a DNF formula. (See "Learning disjunctions of conjunctions", Proceedings of Joint Conference on AI, 1985.) The algorithm works as follows:

1. Let $g$ be the empty DNF formula (i.e., always false).
2. Pick a random $x \in \\{0,1\\}^n$. If $f(x)=0$, go back to step 2. Otherwise, if $f(x)=1$, continue.
3. Find a minimal assignment $w$ such that $f(w)=1$ and the variables set to 1 in $w$ are a subset of those in $x$. This can be done by iteratively flipping a variable that $x$ assigns to $1$, to now be assigned to $0$, and keeping this change if $f$ continues to output $1$, otherwise reverting this change.
4. Set $g(x) := g(x) \lor (x \ge w)$, i.e., add the set of variables that $w$ assigns to 1 to the list of minimal subsets.
5. Go to step 2.

As an optimization, you can change step 2 to sample from $\\{x \in \\{0,1\\} \mid g(x)=0\\}$. I think such an $x$ can be sampled by iteratively picking a new variable that hasn't been assigned yet, setting it to a random value (0 or 1), and at each step, if there is any DNF clause where all but one of the variables have already been set to 1, set the remaining variable to 0. Continue until all variables have been set, and that is your $x$.

The running time is roughly proportional to the number of terms in the DNF representation, i.e., to the number of minimal subsets.

# Testcase minimization

Your problem is also closely connected to testcase minimization and delta debugging. In delta debugging, we typically assume that there is only a single minimal subset, only a few, or only one minimal subset whose size is minimum; and the size of this subset is quite small compared to the total number of variables. The connection is that you have a set of lines of code that exhibit some buggy behavior, and you want to find a minimal/minimum subset of lines that also exhibit the same buggy behavior.

Here is an algorithm that I have seen used for testcase minimization, applied to your problem statement:

1. Let $S$ be the set of all items. Let $\varepsilon=0.1$.
2. Repeat forever:

* Let $S'$ be a random subset of a $1-\varepsilon$ fraction of the items in $S$. If $S'$ is invalid, set $S := S'$, otherwise do nothing.
* If you've done a few hundred iterations in a row where $S'$ was valid in every one: if $\varepsilon \< 2/|S|$, exit the loop, otherwise set $\varepsilon := \varepsilon/2$ and continue the loop.

3. Test each subset of $S$ obtained by removing a single item from $S$. If any of them is invalid, replace $S$ with that subset and restart step 3. Otherwise, if they are all valid, output $S$.

This outputs a single minimum subset. You can probably repeat many times to collect as many minimal subsets as possible.

---
Tags: algorithms, reference-request, combinatorics, enumeration
---


# Question
Title: Does graph traversal require stack machine?
I'm writing a graph traversal function to be used in a garbage collector.

To avoid stack overflow, I used a finite state machine. Roughly, it descends into child nodes recursively to mark objects, and return to root (to descent down again) whenever a branch is exshausted.

However, I realized that if there's loop in the graph, it cannot handle it, as it cannot distinguish a node marked for traversal in its children/descendents from a node that it had visited before.

Q: Does traversal on a graph with loop require a stack machine? If so, I'll rewrite my traversal function.

# Answer
> as it cannot distinguish a node marked for traversal in its children/descendents from a node that it had visited before.

This can be fixed by traversing a list of nodes it's visiting, starting from root - this list doesn't have to be stored, restarting from root and iterating forward is sufficient; when a node found matching the one it's about to descend into, the function retracts.

Hence, it doesn't require a stack. But again, such implementation is very complex to implement and comprehend, and quite inefficient.
> 0 votes

---
Tags: finite-automata, graph-traversal, stacks
---


# Question
Title: Minimum Number of Unique Identifiers for a Grid of Cells
I have a grid of cells, X cells wide by Y cells high. Each cell has four corners, NW, NE, SW and SE. Each corner is shared with adjacent neighbors; i.e., a cell's SW corner is the NW corner of the cell just below it.

In any grid of (X,Y) cells, there are (X+1,Y+1) corners.

In this grid, each corner can be assigned an arbitrary identifier, giving the cell an 'address' of the format NW-NE-SW-SE

In this image below, for cell 'h' the four corners are named `@, #, $ and %`. The NE corner of cell 'g' would also share the corner name '@'. Cell 'h' would have the address `@#$%`

What is the minimum number of unique identifiers needed to allow all cells to have a unique 'address'?

Is there a generalized algorithm or pattern one might use to calculate such a list of identifiers and to assign them to all the corners in a grid of size (XY)?

Thanks in advance!

**Edited to add**: My purpose in asking this question is to solve a real-world problem, which I did not originally state in my question, and further, that I don't necessarily need the theoretical or provable 'minimum set of unique symbols' but rather an algorithm that combines the properties of **a)** being easy to understand and implement and, **b)** provides fairly good answers (i.e., small, perhaps not smallest). Very subjective, I know.

# Answer
> 3 votes
You can solve the problem using at most $\left\lceil \sqrt{2X} \right\rceil + \left\lceil \sqrt{2Y} \right\rceil + 3$ identifiers as follows:

*PART 1:*

Let $G$ be a complete graph over $\left\lceil \sqrt{2X} \right\rceil + 1$ vertices if the $\left\lceil \sqrt{2X} \right\rceil + 1$ is odd; otherwise $G$ be a complete graph over $\left\lceil \sqrt{2X} \right\rceil + 2$ vertices. Each vertex corresponds to a distinct identifier. Note that each vertex in $G$ has even degree. Thus, there exists an Eulerian path in $G$ that can be computed in $O(X)$ time. The path length is at least $X$. In other words, there is a sequence of at least $X$ identifiers such that any pair of consecutive identifiers appears exactly once in the sequence. Lets name this sequence $S\_X$.

Use the sequence $S\_X$ as the first row of the grid. This ensures that all the cells in the first row have distinct addresses.

Now use the same sequence for each odd numbered row in the grid. This ensures that all the cells within the same row have distinct addresses.

$\text{}$

*PART 2*:

To ensure that the cells in the same column have distinct addresses, take a new set of $\left\lceil \sqrt{2Y}\right\rceil+1$ identifiers. Let this idetifier set be $I\_Y = \\{y\_1,\dotsc,y\_t\\}$ for $t = \left\lceil \sqrt{2Y} \right\rceil + 1$. Construct $I\_Y \times I\_Y$. Let $p = \\{y\_i,y\_j\\}$ be any pair of identifiers in $I\_Y \times I\_Y$. Let $(y\_i,y\_j,y\_i,y\_j,\dotsc,y\_i)$ be an alternating sequence of these two identifiers. Use this sequence for any even numbered row of the grid. Since there are at least $Y$ such distinct pairs, each grid vertex is now labeled. Note that all the cells in the same column have distinct addresses since they have different $\\{y\_i,y\_j\\}$ pairs. Thus all the cells in the grid have the distinct address too. This completes the proof.

---

Note that you can solve the problem using at most $\left\lceil \sqrt{X} \right\rceil + \left\lceil \sqrt{Y} \right\rceil$ identifiers as well using directional edges in the part $1$ of the above construction and more careful analysis of part $2$.

# Answer
> 4 votes
This is one of the 800 possible optimal (2-colour) solutions (including reflections and rotations) to the 4x4 problem, found using an exhaustive search:

The optimality is because 16 cells require 16 distinct 4-digit labels, which exhausts the set of 4-bit patterns. The next "interesting" problem size (in the sense that a "perfect" solution might be possible) is $3^4=81$ cells (so 9x9, 27x3 or 81x1), which would exhaust all 4-digit base-3 numbers -- but this is much too large to check with a dumb brute-force search.

Larger grids can be tiled with a pattern like this, using fresh pairs of colours for each copy. It's then advantageous to use a slightly less "efficient" base pattern that contains no monochromatic cells (the optimal solution above necessarily contains a blue and a yellow monochromatic cell) -- since then you can reuse each colour with every other colour. In other words, $k$ colours permit $k \choose 2$ copies of the base pattern if it is free of monochromatic cells, rather than just $k/2$ copies.

Tiling-based solutions will in general not be optimal. I don't yet see any better way to attack the problem of finding optimal or boundedly approximate solutions other than brute force on a case-by-case basis with a SAT or ILP solver, as suggested by D.W.

# Answer
> 2 votes
For a pragmatic solution, I suggest using a SAT solver.

Suppose we want to find a valid coloring, using $C$ colors. Let $L=\lceil \lg C \rceil$, so that each color can be encoded as a $L$-bit integer. Let $x\_{i,j,k}$ be a boolean variable, representing the $k$th bit of the color of the corner at position $(i,j)$. for each $i,j$, add the constraint that $x\_{i,j,L-1} \cdots x\_{i,j,1} x\_{i,j,0} \< C$ as unsigned integers (this can be expressed as CNF clauses). This will force every corner to be colored with one of the $C$ colors.

Also, for each pair of cells, we encode the requirement that those two cells have different 'addresses', as follows: let $y$ denote the sequence of boolean variables that represents the address of the first cell, and $z$ the same for the second cell. We introduce temporary variables $t\_0,\dots,t\_{4L-1}$, constrain them so that $t\_i=y\_i \oplus z\_i$ ($\oplus$ represents the logical-xor; this can be enforced with a few CNF clauses), and then add the CNF clause $t\_0 \lor t\_1 \lor \cdots \lor t\_{4L-1}$. This will force $y,z$ to differ in at least one bit position, so that the two cells receive different addresses.

Now feed this entire CNF formula to a SAT solver and see if it finds a solution. You can use binary search over $C$ to minimize the number of colors.

A front-end like Z3 will make implementing this easier.

If I had to guess, I would guess that $\sim (XY)^{1/4}$ colors might suffice, but I have no proof.

# Answer
> 2 votes
Each *Even* column of corners (blue arrows) encodes a single unique ‘X’ indicator: x0,x2,x4… (here colored using Red, Green, Blue)

Each *Odd* column of corners (yellow arrows) encode a semi-incrementing ‘y’ indicator y0,y0,y1,y1,y2,y2 (here colored using Cyan, Magenta, Yellow)

Resulting set of required unique symbols is (x+1)/2 + (y+1)/2

While I doubt this is an optimal solution for *smallest* set of unique symbols, it does have the advantage (for my purposes) of being a simple algorithm to implement.

This method seems very similar to the approach suggested by j\_random\_hacker in a comment above, but I'm not good enough at all this to understand how similar or divergent they actually are.

---
Tags: topology
---


# Question
Title: Doubt in pumping lema for context-free language
I have a doubt related to pumping lemma in CFL for which I dont find an answer, so I think is very easy because no one wonder about. The lemma says:

My doubt is: **Is there any restriction related to strings u (the most left) and y (the most right), I mean can they be empty?.**

In case they can, I cannot proof that a^nb^n is context-free because, for p=3, I could make vwx only a's or only b's and when pumping there will be different quantity of a's and b's.

Thanks

# Answer
> 1 votes
They can be empty, but the pumping lemma is used to prove that a language is *not* context free.

It says that if a language is context free, such a configuration always exists, and it's the case for $a^nb^n$ as one can take $u=a^{n-1}, v=a, w=\varepsilon, x=b, y=b^{n-1}$. The lemma says that one such configuration exists, not that all configurations work.

To prove that $L$ is context free you would have for example to provide a context free grammar generating it.

---
Tags: context-free, formal-grammars, pumping-lemma
---


# Question
Title: How can this problem be solved in $O(n^{3/2}log(n))$ time?
I can solve the following problem by Jeff Erickson in $O(n^3)$(and maybe in $O(n^2logn)$) time but how is the $O(n^{3/2} log(n))$ time solution possible?

> Let $D\[1 .. n\]$ be an array of digits, each an integer between $0$ and $9$. A **digital subsequence** of $D$ is a sequence of positive integers composed in the usual way from disjoint substrings of $D$. For example, $3, 4, 5, 6, 8, 9, 32, 38, 46, 64, 83, 279$ is a digital subsequence of the first several digits of $\pi$:$$ \underline 3 , 1, \underline 4 , 1, \underline 5 , 9, 2, \underline 6 , 5, 3, 5, \underline 8 , \underline 9 , 7, 9, \underline{3, 2} , 3, 8, \underline{4, 6} , 2, \underline{6, 4} , 3, 3, \underline{8, 3 }, \underline {2, 7, 9}$$ The length of a digital subsequence is the number of integers it contains, not the number of digits; the preceding example has length $12$. As usual, a digital subsequence is **increasing** if each number is larger than its predecessor.
>
> Describe and analyze an efficient algorithm to compute the longest increasing digital subsequence of $D$. \[*Hint: Be careful about your computational assumptions. How long does it take to compare two k-digit numbers?*\]
>
> For full credit, your algorithm should run in $O(n^4)$ time; faster algorithms are worth extra credit. The fastest algorithm I know for this problem runs in $O(n^{3/2}log n)$ time; achieving this bound requires several tricks, both in the design of the algorithm and in its analysis, but nothing outside the scope of this class.

# Answer
I will assume you know how to solve the problem by keeping a table $T\[i, j\]$ which stores the length of the best solution whose last integer is $D\[i\cdots j\] = D\[i\]D\[i+1\] \cdots D\[j\]$. To compute $T\[i, j\]$ you need to find the best $T\[a, b\]$ such that $D\[a \cdots b\] \<\_{\text{lex}} D\[i \cdots j\]$ and $b \< i$. The computation of $T\[i, j\]$ (provided the previous entries of $T$ have been filled) can take $O(n)$ if the $\<\_{\text{lex}}$ is implemented in $O(1)$ time with a good data structure like a suffix array + LCP; after all, you're always comparing substrings of $D$. Naively, this would yield a runtime of $O(n^3)$ which is the state at which you seem to be.

Now consider the following observations.

**Observation 1**: The $i$-th term of the optimal sequence should never be longer than the $i-1$-th term by more than 1 digit.

**Observation 2**: Taking $D\[1\]$, $D\[2\cdots3\]$, $D\[4 \cdots 6\], \ldots D\[n-\sqrt{n} \cdots n\]$ is always a solution, implying that the answer is always at least $\sqrt{n}$, and by Observation 1, we get that only the cells of $T$ with $j-i+1 \leq \sqrt{n}$ should be computed (one can even limit it to $j-i+1 \leq \sqrt{j}$, but it doesn't help asymptotically...). There are now $O(n^{3/2})$ cells.

Now let's try to speed-up the computation of \begin{equation} T\[i, j\] = 1 + \max\_{a \leq b \< i} \Big\\{ T\[a, b\] \\; \vert \\; D\[a\cdots b\] \<\_{\text{lex}} D\[i\cdots j\] \Big\\}.\tag{1} \end{equation}

As you were already doing in your $O(n^3)$ approach, we should only consider $b - a = j - i$ or $b-a = j - i -1$ (this is just Observation 1). If we keep, for each substring length $\ell \in \\{1, \ldots, \sqrt{n}\\}$ a matrix where $B\[\ell\]\[i\] := \max\_{b \< i} \Big\\{ T\[b-\ell+1, b\]\Big\\}$, then $B\[j-i-1\]\[i\]$ is one candidate for the $\max$ in Equation (1), while the other candidate will be

$$ \max\_{b \< i} \Big\\{ T\[b-j+i+1, b\] \\; \vert \\; D\[a\cdots b\] \<\_{\text{lex}} D\[i\cdots j\] \Big\\}. $$

How could we compute this last amount more efficiently? We can assume we're constructing $T\[i, j\]$ in increasing order of $i$, and let the length be denoted $\ell = j-i+1$. We can keep in memory a set of pairs $$S^{i}\_\ell = \Big\\{ (T\[b-\ell+1, b\], D\[b-\ell+1 \cdots b\]) \\; \vert \\; b \< i\Big\\}.$$

If we let $w = D\[i\cdots j\]$, then we're looking for $$ \max v \\; \text{s.t. } \\; (v, y) \in S^i\_{\ell} \text{ and } y \<\_{\text{lex}} w. $$

We're now facing a data structures problem; how can we keep a set of pairs $(\text{integer}, \text{string of length } \leq \sqrt{n})$ in a way that quickly allows us to query with a word $w$ for the maximum first coordinate whose second coordinate is smaller than $w$? It is enough to maintain $S$ as a balanced binary search tree, where the ordering of the tree is based solely on the words $y$ inserted in it, but every node keeps track of the best value $v$ present in its subtree. Notice that because comparisons between strings take $O(1)$, searching on the tree will take $O(\log n)$. Therefore our entire algorithm runs in $O(n^{3/2} \log n)$.
> 1 votes

---
Tags: algorithms, time-complexity, dynamic-programming
---


# Question
Title: Finding Shift-Invariant "Interesting" Elements In Words
I want to find "interesting" elements in a sequence of symbols that are independent of their absolute position in that sequence.

Formally, I have a window size $s \in \mathbb{N}$ and a finite alphabet $\Sigma$. I'm looking for a function $f: \Sigma^s \to \\{0, \\; ..., \\; s\\}$ that points to the first interesting position of the input word that stays interesting even if the first character is removed and an arbitrary character is appended to the end. This means:

$\forall w \in \Sigma^s, c \in \Sigma: f(w\_0...w\_{s-1}) \> 0 \Rightarrow f(w\_1...w\_{s-1}c) = f(w\_0...w\_{s-1}) - 1$

Of course a trivial $f$ would always return $0$. However, I'm most interested in a function $f$ that maximizes the average result, so that interesting positions are as far away from each other as possible.

Thus my question is: What is the $f$ that maximizes $\Sigma^{w \in \Sigma^s} f(w)$ (= the score of $f$)?

One idea would be to sort the alphabet and return the first index $i \leq s/2$ of the smallest symbol in $w\_0...w\_{i+i}$. That way, after every shift of $w$, the index is decreased by $1$ until it reaches $0$. What is an `f` with higher score?

Ideally, this function $f$ should also be fast to compute and not depend on brute forcing all possible $f$ first (there are only finitely many!).

One observation is that if $w = v^iv\_0...v\_j$ for some $i, j \in \mathbb{N}$ and $v \in \Sigma^\*$, $j \< |v|$, then $f(w) \< s/i$. In particular $f(c...c) = 0$ for $c \in \Sigma$.

# Answer
Using an answer to write down a nice insight, inspired by the comments:

**Definition**. A function $f: \Sigma^s \to \\{0, ..., s-1\\}$ is called *shift-invariant* if $\forall w \in \Sigma^s, c \in \Sigma: f(w\_0...w\_{s-1}) \> 0 \Rightarrow f(w\_1...w\_{s-1}c) = f(w\_0...w\_{s-1}) - 1$.

**Definition**. For a finite set of patterns $P \subseteq \Sigma^\*$, define $f\_P: \Sigma^s \to \\{0, ..., s-1\\} $ to be the function that returns the smallest position of where some $p \in P$ occurs in the input word, or $0$ if no pattern matches.

**Theorem**. Let $f: \Sigma^s \to \\{0, ..., s-1\\}$ be a shift-invariant function. Then there exists a finite set $P \subseteq \Sigma^\*$ so that $f = f\_P$.

*Proof*:

Set $P\_f := P := \\{ p \in \Sigma^\* \\; | \\; \exists v \in \Sigma^\*: |vp| = s \land f(vp) = |v| \\}$.

Let $w \in \Sigma^s$ be an arbitray input word.

Set $vp := w$ with $|v| = f(w)$. Then $p \in P$ by definition of $P$.

Because (with $p$) at least some pattern in $P$ matches $w = vp$ at or before position $|v|$, by definition of $f\_P$, there exists $p' \in P$ and $x, y \in \Sigma^\*$ with $xp'y = w$, $|x| = f\_P(w)$ and $|x| \leq |v|$.

Because $p' \in P$, there exists $v'$ so that $f(v'p') = |v'|$. Shift-invariance of $f$ now implies $f(p'u) = 0$ for any $u \in \Sigma^{|v'|}$. Thus, $|v| = f(xp'y) \leq |x|$ (otherwise, shifting $|x|$ times doesn't reach $0$). Finally we have $f(w) = |v| = |x| = f\_P(w)$, which finishes the proof.

---

**Note**. If no element of $P$ is a substring of another, then $f\_P$ is shift-invariant.

**Conjecture**. For a shift-invariant function $f$ it is $f = f\_{P\_f} = f\_{P^{\mathrm{min}}\_f}$ , with $P^{\mathrm{min}}\_f$ being all minimal elements (regarding substrings) of $P\_f$.

**Open Question**. What is $P$ such that $f\_P$ is shift-invariant and $\Sigma\_{w \in \Sigma^s} f\_P(w)$ is maximal?
> 2 votes

---
Tags: optimization, word-combinatorics
---


title: Reduction from MAX-3-CUT to MAX-CUT

text:
# Question
Title: Reduction from MAX-3-CUT to MAX-CUT
Both MAX-CUT and MAX-3-CUT are known to be NP-complete. This post shows a reduction from MAX-CUT to MAX-3-CUT. I am curious if there is a way to reduce MAX-3-CUT to MAX-CUT?

**MAX-CUT:** Given an undirected graph $G=(V,E)$, a weight function $w:E\to\mathbb{N}$, and $k\in\mathbb{N}$, determine if there exists a partition $(V\_1,V\_2)$ of $V$ (that is, $V\_1\cap V\_2=\emptyset$ and $V\_1\cup V\_2=V$) such that $$ \sum\_{(u,v)\in V\_1\times V\_2}w(u,v)\ge k. $$

**MAX-$3$-CUT:** Given an undirected graph $G=(V,E)$, a weight function $w:E\to\mathbb{N}$, and $k\in\mathbb{N}$, determine if there exists a tri-partition $(V\_1,V\_2,V\_3)$ of $V$ (that is, $V\_1\cap V\_2=V\_1\cap V\_3=V\_2\cap V\_3=\emptyset$ and $V\_1\cup V\_2\cup V\_3=V$) such that $$ \sum\_{(u,v)\in V\_1\times V\_2}w(u,v)+\sum\_{(u,v)\in V\_1\times V\_3}w(u,v)+\sum\_{(u,v)\in V\_2\times V\_3}w(u,v)\ge k. $$

I do not have a good idea of what a reasonable reduction approach would look like. It seems to me that going from a tri-partition to a partition would necessarily involve merging two subsets into one, but I am not sure how this can be done without losing information on the tri-partition. Any help is appreciated.

# Answer
> 1 votes
We want to use a $\textsf{MAX-CUT}$ algorithm to solve the $\textsf{MAX-3-CUT}$ problem. Therefore we need to transform our original graph $G$ into a new graph $G'$ in such a way that finding a max-cut on $G'$ tells us how to cut $G$ into 3.

Let's start by creating, for every $v \in V(G)$ three vertices $v\_A, v\_B, v\_C \in V(G')$. We will say $v\_A, v\_B$ and $v\_C$ are vertices *of type* $v$ in $G'$. We will design $G'$ in such a way that exactly one vertex of type $v$ is on the left side $V\_1$ of $\textsf{MAX-CUT}(G')$, which will naturally tell us how $G$ should have been cut into $3$ parts.

To do that, we will design $G'$ such that the value of $\textsf{MAX-CUT}(G')$ can be separated into two parts; one *natural* part of value $K$ corresponding to the value of $\textsf{MAX-3-CUT}(G)$, and one *artificial* part $P$ corresponding to additional edges of $G'$.

If for every $v \in V(G)$ we add edges of a weight $W$ which will be guaranteed to be much larger than $K$ (e.g., $ W = |V| \cdot \sum\_{e \in E(G)} w(e) \geq |V| \cdot K $) to $G'$ between each pair of vertices of type $v$, then the $\textsf{MAX-CUT}(G')$ will definitely separate 2 of the vertices of type $v$ from the 3rd.

Let us now enforce that all the groups of $2$ vertices of type $v$ will be on the same side. For this, create a special vertex $S$ that is connected to all other vertices of $G'$ by edges of weight $W' := \frac{W}{{|G|}}$. Assume without loss of generality that $V\_1$ is the part of $\textsf{MAX-CUT}(G')$ where vertex $S$ ends up, and observe now that all groups of $2$ vertices of the same type must be in $V\_2$, as otherwise swapping them from $V\_1$ to $V\_2$ would increase the artificial part of the cut-value by $W'$, which is more than whatever loss it could incur in terms of the natural value $K$. Note as well that it is not convenient to have the $3$ vertices of the same type on $V\_2$, as that would gain only $\frac{W}{{|G|}}$ by edges toward $S$, while losing two edges of weight $W$ between the vertices of the given type.

Now, given we can safely assume $V\_1$ will contain exactly one vertex per type, for each edge $(u,v)$ of weight $w$ in $G$ we add edges $(u\_A, v\_A)$, $(u\_B, v\_B)$ and $(u\_C, v\_C)$ of weight $w/2$ in $G'$. That way, if $u\_X \in V\_1 \land v\_{Y} \in V\_1$ for some $X \neq Y \in \\{A, B, C\\}$, then $w$ should be part of the natural value of the cut, which is indeed achieved as now $u\_Y \in V\_2$ and $v\_X \in V\_2$. On the other hand, if $u\_X \in V\_1 \land v\_X \in V\_1$, then none of these additional edges is in the cut, which matches $u$ and $v$ being on the same part of $\textsf{MAX-3-CUT}(G)$.

This way, there will be a cut of value $K + 2|V(G)|W + 2|V(G)|W'$ in $G'$ iff there was a 3-cut of value $K$ in $G$.

---
Tags: complexity-theory, optimization, reductions, discrete-mathematics, max-cut
---


# Question
Title: knapsack with graph connectivity constraints
I am looking for a variant of the knapsack problem in which the items are nodes in an undirected graph, and the knapsack must be filled with a connected subgraph. Formally:

* The input is an undirected graph $G=(V,E)$, where each node $v\in V$ has both a size and a value; and a knapsack capacity $C$.
* The goal is to find a subset $U\subseteq V$ such that the sum of sizes of all nodes in $U$ is at most the capacity $C$, and in addition, there is a path between every two nodes in $U$; subject to this, the sum of values of all nodes in $U$ should be as large as possible.

The original problem is NP-hard, but has a pseudopolynomial-time algorithm. The problem with the additional constraint is definitely NP-hard too; does it have a pseudopolynomial-time algorithm?

# Answer
There shouldn't be a pseudopolynomial-time algorithm; the problem is NP-hard even if all values are given in unary. We can reduce from the $\textsf{Connected Vertex Cover}$ problem in which we need to decide whether a graph has a connected subgraph of at most $k$ vertices touching all edges. This is NP-hard by a simple reduction from standard Vertex Cover (simply add an extra vertex and connect it to everything else).

For our reduction, take the input graph $G = (V, E)$ of $\textsf{Connected Vertex Cover}$ and build $G'$ with vertex set $V \cup E$ and edge set $E \cup \\{(v, e) \in V \times E \mid v \in e\\}$. Make the size of vertices in $V$ equal to $1$, and the size of the vertices in $E$ equal to $0$. Set the value of the vertices in $E$ equal to $1$, and put value 0 for those in $V$. We set the capacity for the knapsack instance equal to $k$, the desired connected vertex cover size.

Now for any connected vertex cover $S$ of $G$ of size at most $k$, the subgraph induced by $S \cup E$ in $G'$ has value $|E|$ while respecting the capacity. For the other direction, any connected subgraph $S'$ of $G'$ of value $|E|$ and size at most $k$ must include all vertices in $E$, while not including more than $k$ vertices of $E$. That means that $|S' \cap V| \leq k$, and also that $(S' \cap V)$ is a vertex cover for $G$. It only remains to show that $(S' \cap V)$ is connected in $G$, which is direct, since for any pair of vertices $u, v \in (S' \cap V)$, there was a path $u \to e\_1 \to v\_1 \to e\_2 \to v\_2 \to \cdots \to e\_\ell \to v$ in $G'$ proving its connectedness, and now $u \to v\_1 \to v\_2 \to \cdots \to v$ is a path in $G$.
> 3 votes

---
Tags: dynamic-programming, knapsack-problems, pseudo-polynomial
---


# Question
Title: Checking if all nodes are reachable in a oriented graph from all other nodes
I'm having a lot of troubles understanding a preparation exercise about oriented graphs:

> Consider the following game played on a directed graph G = (V, E) with n nodes and m edges. A pawn is initially placed on node s. The pawn can be moved from its current position u to a node v if there exists a directed edge (u, v) ∈ E in G. Additionally, there is a set of special nodes X ⊆ V. If the pawn is on a special node x ∈ X, it can also be moved along incoming edges to x, in addition to the outgoing edges from x. In other words, the pawn can be moved from x to v if and only if (v, x) ∈ E or (x, v) ∈ E, or both.
>
> Design an algorithm that, in O(m + n) time, decides whether, regardless of the initial position s, it is always possible to move the pawn from s to any other node t in the graph with an appropriate sequence of moves.

I really don't understand where to begin to solve this problem.

Here is what i know: i need to find if the graph is connected, which would be very easy with a BFS visit. The fact that the problem asks for a O(m+n) solution means that i need to use BFS somewhere. What makes it complicated to me is the condition that there are special nodes where the pawn can be moved through incoming edges.

Can anyone help me on this? I just need some advice on how to go forward with this problem

# Answer
> 1 votes
One way to deal with having these special vertices is to create a reversed graph from your original graph, which can be done in $O(n+m)$ time, assuming you are using adjacency list representation. This reversed graph contains all vertices but with the direction of the edges flipped. When you traverse the original graph and you encounter a special vertex you will also visit its neighbours in the reverse graph.

Also, since you have a directed graph you might want to use algorithms for testing strong connectivity

---
Tags: graphs, graph-traversal
---


# Question
Title: High-multiplicity maximum-weight matching
There are $n$ people and $m$ jobs. We would like to assign at most one job to each person. For each person,job pair, there is a positive value determining the fitness of this person to that job. The goal is to find an assignment that maximizes the total value. So far, it is exactly the problem of finding a maximum-weight matching in a bipartite graph, which can be solved in time poly$(m,n)$.

Now, suppose that in each job there are $p$ identical positions: for each person, the fitness value is the same for all positions of the same job. The problem can be reduced to maximum-weight matching by constructing a new graph with $p$ clones of each job, and then running any algorithm for maximum-weight matching. The run-time would by poly$(m,n p)$. But this run-time is exponential in the length of the binary representation of $p$; it may be very wasteful when $p$ is large.

Is there a more efficient algorithm for this problem? Particularly, is there an algorithm that runs in time poly$(m, n, \log p)$?

# Answer
You can solve this using min-cost flow.

Construct a graph with a source vertex $s$, one vertex per person, one vertex per job, and one sink $t$. Add edges as follows:

* Add an edge of capacity 1 from $s$ to each person, with cost 0.
* Add an edge of capacity 1 from each person to each job they are qualified for, with cost equal to the negative of their fitness.
* Add an edge of capacity $p$ (the number of positions per job) from each job to $t$, with cost 0.

Now find an integral solution to this min-cost flow problem. There are polynomial-time algorithms for min-cost flow, which produce an integral solution. That solution then solves your problem, as the amount of flow on the edge from a person to a job is 1 or 0 according to whether that person should be assigned to that job.
> 2 votes

---
Tags: algorithms, matching, assignment-problem
---


# Question
Title: Does there exist some ``partial" universal hashing?
Suppose we have sets $X$ and $Y$, $|X|=m$, $|Y|=n$. $H$ is a universal family of hash functions from $X$ to $Y$. Let $S\subsetneq X$ be a proper subset of $X$. Does there exist some "partial" universal hash family that is universal on $S$ to $Y$, but not necessarily universal on $X$ to $Y$? The circuit complexity of that "partial" universal hashing should be preferably lower then $H$.

---

Update: Does there exist construction such that taking the union of two "partial" universal hash families from S1 and S2 to Y we can get a universal hash family from S1∪S2 to Y?

# Answer
> 1 votes
Sure, of course. Let $S$ be a single point, so $|S|=1$; then any family is trivially a universal hash on $S \to Y$, and is faster than $H$, even though it is not universal on $X \to Y$.

---
Tags: complexity-theory, circuits, cryptography, hashing
---


# Question
Title: Trying to understand the proof of the halting problem presented in Sipser textbook
I'm having some problems to understand the classic proof of the halting problem.

The Proof:

$A\_{tm} = ${$\<M,w\>$ | $M$ is a $TM$ and $M$ accepts $w$}.

We assume that $A\_{tm}$ is decidable and obtain a contradiction.

> I have no problem to imagine that. It's a machine that accepts some string $w$. But it must not accept others strings $not-w$. And if it's decidable, it always halts.

Suppose that $H$ is a decider for $A\_{tm}$. On input $\<M, w\>$, where $M$ is a $TM$ and $w$ is a string, $H$ halts and accept if $M$ accepts $w$. Furthermore, $H$ halts and rejects if $M$ fails to accept $w$. In other words, we assume that $H$ is a $TM$, where

\begin{equation} H(\<M, w\>)=\begin{cases} accept &\text{if $ M$ accepts $w$}.\\ reject & \text{if $ M$ does not accept $w$}. \end{cases} \end{equation}

> Here I have the impretion that $H$ is doing the same thing that $A\_{tm}$ does. But If it's saying that $H$ is decider, I can assume that $H$ has some magic power to discover if $A\_{tm}$ will halt in input $w$

Now we construct a new Turing machine $D$ with $H$ as a subroutine. This new TM calls H to determine what $M$ does when the input to M is it own description $\<M\>$. Once $D$ has determined the information, it does the opposite. That is, it rejects if $M$ accpets and accepts if $M$ does not accept. The follow is a descripion of $D$:

> No problem here.

\begin{equation} D=\begin{cases} 1. &\text{Run $H$ on input \<M, \<M\>\>}.\\ 2. & \text{Output the oposite of what $H$ outputs; that is, if $H$ accpets, reject and if $H$ rejects, accept}. \end{cases} \end{equation}

> Here is where I find hard to understand. The input string of $H$ is $\<M, w\>$, how could it run some thing like $\<M, \<M\>\>$ ?
>
> If was only $\<M\>$, I could imagine that $w$ is the empty string.

I understand the halting problem with the following code:

```
function halts(func) {
  // Insert code here that returns "true" if "func" halts and "false" otherwise.
}

function deceiver() {
  if(halts(deceiver))
    while(true) { }
}

```

# Answer
The first misconception is that $A\_{TM}$ is a Turing Macahine. $A\_{TM}$ isn't a machine, it's a language, $H$ is the machine that decides the language $A\_{TM}$. So you give $H$ a string that consists of two parts, a string $M$ that describes a Turing machine, and another string $w$, which can be anything.

This leads us to the second part, $w$ can be any string - it's the theoretical input to $M$ that you want to know whether $M$ would accept or not. So $H$ should accept if $M$ would accept $w$, and reject otherwise (i.e. when $M$ doesn't accept, which could be by rejecting or never halting). $\langle M \rangle$ is just a string, it happens to coincidentally be a description of a Turing Machine, but it is still just a string. So there's no reason we can't ask "does $M$ accept the string which is its own description?"
> 1 votes

# Answer
\<M,\<M\>\> is like the functionality of the following C++ codes: (file name: test\_self.cpp)

```
#include <iostream>
#include <fstream>
#include <string>
using namespace std;

int main()
{
    string file_name;
    cout << "Enter the file name: ";
    cin >> file_name;
    fstream out(file_name, ios::in);

    if(!out){
        cout << "Can't open the file!" << endl;
        return 1;
    }

    while(!out.eof()){
        string line;
        getline(out, line);
        cout << line << endl;
    }

    out.close();

    return 0;
}

```

It's not as strang as you think because you can view any source file as a pure text file, which consists of several characters. After the source file compiles into machine codes, it is different from the content of the source codes. After compiling, the source file is still there and since it's just a text file, you, of course, can read its contents even if the source file is the same as the file before compiling. You can try out the above program and see what the contents shows in the console(especially if you enter test\_self.cpp). Then, I think you can understand what \<M,\<M\>\> means.
> 0 votes

---
Tags: computability, halting-problem
---


title: Rotating sort algorithm

text:
# Question
Title: Rotating sort algorithm
Take a set of $n$ points in the plane. You want to sort them by increasing abscissa. But you also want to sort them by abscissa after several arbitrary rotations, say $k$, in increasing angles.

The obvious brute-force solution takes time $O(kn\log n)$. Is there a method with a better complexity ?

If one considers a full rotation of the point cloud, there will be $\frac{n(n-1)}2$ swaps in total, corresponding to all directions formed by pairs of points. This hints that the problem could be $\Omega(n^2)$, unfortunately.

If the points are the vertices of a convex polygon, after sorting the vertices in two monotone chains, we can restore the order after every rotation by delimiting the next two monotone chains and merging them. The total time is $O(kn)$.

But what if we don't need an explicit enumeration of the sorted sequence, but instead a suitable update of a search tree ?

# Answer
In everything which follows I assume general position of the points (no 3 colinear points), mostly for simplicity.

This is might not be exactly what you are looking for, but you can build a data structure with $O(n^2\log n)$ preprocessing time and $O(n^2)$ space which allows you to navigate a balanced binary search tree corresponding to any angle in $O(\log n)$ time (plus whatever time your query takes to look at stuff in the search tree, which is probably also $O(\log n)$).

For rank and predecessor/successor queries specifically, you can also do $O(n\log^2 n)$ preprocessing time, $O(n)$ space and $O(n^{\log\_4 3}) \approx O(n^{0.7925})$ query time.

\__

For the first data structure, you can do this using (for example) a partially persistent red-black tree. A partially persistent red-black tree allows you to insert/delete elements in $O(\log n)$ time and $O(1)$ space increase, and search in any previous version of the tree in $O(\log n)$ time.

So start by inserting all your points in the BST according to their initial order by $x$ coordinate.

Now do the following: sort the pairs of points according to the angle made by the line passing through them. Each pair corresponds to one swap in the order of points as you rotate the plane. For each pair of points (in sorted order by angle), delete them from the BST and reinsert them according to the order after they swap. This costs $O(n^2\log n)$ time and results in a data structure taking $O(n^2)$ space.

Now given some arbitrary angle, you can find the correct version of the BST in $O(\log n)$ time and then do whatever you want in it (as long as you don't modify it).

If you were to do all of this without persistence then you would have $O(n^3\log n)$ preprocessing time and $O(n^3)$ space, so this is a win, even if it doesn't buy you anything when $k$ is small.

\__

For the second data structure, we will build a partition tree on the points based on the ham sandwich theorem. A consequence of the ham sandwich theorem in the plane is the following:

* For any set of $n$ points in the plane, there exists two lines which partition the plane into $4$ regions each containing at most $\lceil n/4 \rceil$ points. Moreover, it is not too hard to show (or to look up a proof) that you can find such two lines in $O(n\log n)$ time.

So we build a partition tree of the plane by recursively applying this result until we reach sets of constant size. Each node also stores the number of points in its subtree. This is our data structure.

Let's see how to perform a rank query using this data structure. I will describe the queries for the pointset without rotation applied to it, but you can adapt it for any rotation by replacing the vertical lines I will use here with rotated lines.

Given some $x$-coordinate $x\_0$, we want to find the number of points left of the line $\ell:x=x\_0$. We are at the root of the partition tree. Notice that the line $\ell$ intersects at most $3$ of the $4$ regions which partition the plane at this level. We need to recurse on these $3$ regions we recurse. For the other, non-intersected region, we can know directly whether all points inside lie to the left or right of $\ell$ so we add that to the total as needed. This leads to a recursion on the runtime of $T(n) = 3T(n/4) + O(1)$, yielding $T(n) = O(n^{\log\_4 3})$.

Successor/predecessor queries are done similarly.

You can almost certainly improve query runtime by using more modern partition methods, but this is the only thing I can whip up on the spot. I think there are methods which can also shave a log factor on the preprocessing time.
> 1 votes

---
Tags: computational-geometry
---


# Question
Title: Number of "one neighbourhood" search trees in a graph
Consider the following algorithm: We are given a planar graph $G$. We initialise a set of vertices $S$ to an empty set. We randomly pick a vertex $v$ in $G$ and insert it in $S$. Now we keep including in $S$ vertices from the neighbourhood of $S$ such that the vertex we include is adjacent to exactly one vertex in $S$. We stop expanding $S$ when there is no vertex in the neighbourhood of $S$ which is adjacent to exactly one vertex in $S$. Just like BFS produces a breath first tree and DFS produces a depth first tree, the "one neighbourhood" search above also produces a tree. Give a tight upper bound on the number of such trees in $G$.

I expect the number of such trees to be asymptotically lower than O($2^n$), where $n$ is the number of vertices in $G$.

The illustration below shows such a tree in a graph.

# Answer
Consider the following planar graph $G$. There are $n+2$ vertices: $\\{x,y,u\_1,\dotsc,u\_n,v\_1,\dotsc,v\_n\\}$. The edge set is $\\{(x,y),(x,u\_1),\dotsc,(x,u\_n),(y,v\_1),\dotsc,(y,v\_n),(u\_1,v\_1),\dotsc,(u\_n,v\_n)\\}$.

Suppose your algorithm initially picks $x$ and $y$ in $S$. Then, the algorithm can construct $2^n$ possible search trees depending on whether $u\_i$ or $v\_i$ is included in the serach tree for each $i \in \\{1,\dotsc,n\\}$. Therefore, there are $2^{\Omega(|V|)}$ possible search trees for this graph.

Note that this is asymptotically tight bound in the exponent since in a planar graph, the number of edges are linearly bounded by the number of vertices, i.e., $|E| = O(|V|)$ (see here for the properties of a planar graph). Therefore, the number of subgraphs of any planar graph are at most $2^{O(|V|)}$.
> 4 votes

---
Tags: algorithms, graph-traversal
---


# Question
Title: Can Rural Postman Problem with arbitrary start and end be reduced to Rural Postman Problem with single depot node?
Can Rural Postman Problem with arbitrary start and end be reduced to Rural Postman Problem with single depot node?

The rural postman problem is:

*Given a weighted MultiDiGraph $G=(V,E)$, a subset of edges $A$ must be traversed. The path must start and end at the depot node. Find the shortest of all such paths.*

I'm wondering if a similar problem can be reduced to the above problem:

*Given a weighted MultiDiGraph $G=(V,E)$, a subset of edges $A$ must be traversed. The path can start at arbitrary $s$ and end at arbitrary $t$. Find the shortest of all such paths.*

I've explored a few reductions, similar to the common reduction used for max flow problems, by creating an artificial $s,t$, and connecting all arcs. But, I'm not able to determine a proper reduction, nor a meaningful relationship between these two problems. Any help is appreciated. Thanks.

edit: ("arbitrary" meaning start and end are not given. However if a solution can be found if start and end are given, that might give us some useful insight.)

# Answer
> 1 votes
Let the *rural postman problem without depot node* be denoted by $\textrm{RND}$ and the *rural postman problem with depot node* be denoted by $\textrm{RD}$.

Let $G = (V,E,w)$ be a positive weighted graph instance of $\textrm{RND}$. Add a new vertex $d$ to the graph. Add directed edges $(s,v)$ and $(v,s)$ for each vertex $v \in V$. Assign weight $W$ to each of these new edges such that $W = |E| \cdot \sum\_{e \in E} w\_e$, where $\sum\_{e \in E} w\_e$ the sum of weights of all edges in $G$. Let this new graph be $G'$ which is an instance of $\textrm{RD}$ with depot node $d$.

Then, the following claim holds:

*Claim:* For $L \< W$, there exists a feasible path of cost at most $L$ in $G$ for $\textrm{RND}$ if and only if there exists a feasible path of cost at most $L + 2W$ in $G'$ for $\textrm{RD}$.

*Proof:* ($\to$) Let $p = (v\_1,\dotsc,v\_k)$ be a feasible path of cost at most $L$ in $G$ for $\textrm{RND}$. Let the new path be $p' =: (d,v\_1,\dotsc,v\_k,d)$. This is a feasible path in $G'$ for $\textrm{RD}$. The cost of this path is at most $L + 2W$.

($\gets$) Let $p' = (d,v\_1,\dotsc,v\_k,d)$ be a feasible path of cost at most $L + 2W$ in $G'$ for $\textrm{RD}$. Note that any $v\_i \neq d$; otherwise the cost of the path will be at least $3W$ which contradicts that the $L \< W$. Therefore the subpath $p =: (v\_1,\dotsc,v\_k)$ lies completely inside $G$. The path $p$ is a feasible path in $G$ for $\textrm{RND}$. And, $p$ has cost at most $L$.

This proves the claim.

---

Note that I assumed that $L \< W$, since for $L \geq W$, the problem can be solved in polynomial time.

---
Tags: graph-traversal, weighted-graphs, eulerian-paths
---


title: Two Questions About Fibonacci Heaps

text:
# Question
Title: Two Questions About Fibonacci Heaps
I am learning about Fibonacci heaps from the following set of notes: http://staff.ustc.edu.cn/~csli/graduate/algorithms/book6/chap21.htm. There are 2 things that are confusing me.

Firstly, in the consolidate function, the author has created an array of size D(n), where D(n) is the maximum number children of a root of a tree. I don't get why this is sufficient. Suppose we have heap whose root trees are of degrees 2, 2, 2, 2 and 1, which means D(n) = 2. Then merging the first 2 trees will create a tree of degree 3, meaning we have nowhere in this array to store this tree. Wouldn't this be a problem? Because that means if we get a second root node of degree 3, we wouldn't be able to merge it with the first!

Secondly, the notes claim that after we run the consolidate function, we will be left with at most D(n) + 1 roots remaining. I don't understand why this is the case again. Suppose we have a heap whose root trees are of degrees 2, 2, 2, 1, 0. Merging the first 2 will create a root node of degree 3, so then we're left with a heap whose root trees are of degrees 3, 2, 1 and 0. This is greater than D(n) + 1, so I don't understand how this can be true.

Thanks in advance.

# Answer
> 0 votes
$D(n)$ is the maximum possible degree of a root node in the *final* heap after the consolidate operation. Specifically, $D(n) = \left\lceil \log\_2 n \right\rceil$.

Note that real implementations usually use an array that is the size of the machine word in bits; that would be 64 on 64-bit machines.

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


title: Analyzing network architecture with TDA

text:
# Question
Title: Analyzing network architecture with TDA
I'm doing Neural Architecture Search (NAS) by varying the number of layers and neurons per layer for a neural network (connections are feed-forward throughout), and then training it on a fixed task to test its performance. The end goal is to perform topological data analysis (TDA) on the best and worst architectures (graphs) to spot the persistent structures in a good/bad architecture.

My question is: am I right in my assumption that TDA could spot such persistent structures? If so, which metric should I use? Just the connection weights?

P.S.: My background in (computational) topology is quite minimal.

# Answer
> 1 votes
For the previously interested and for those to come, I'd recommend reading through this: https://arxiv.org/abs/1812.09764. The authors open-source their code as well. AFAIK, this is limited to feed-forward networks.

# Answer
> 0 votes
The only way to know is to try it; or to find someone else who has tried it (e.g., by searching the research literature for a published paper that has tried this approach).

---
Tags: machine-learning, network-topology
---


# Question
Title: BFS vs DFS, and Timing of Marking Vertex as Visited
The Wikipedia article on Depth-Frist Search states that:

> The non-recursive implementation is similar to breadth-first search but differs from it in two ways:
>
> * it uses a stack instead of a queue, and
> * **it delays checking whether a vertex has been discovered until the vertex is popped from the stack rather than making this check before adding the vertex.**

*(emphasis mine)*

Conversely, the article on Breadth-First Search states that:

> This non-recursive implementation is similar to the non-recursive implementation of depth-first search, but differs from it in two ways:
>
> * it uses a queue (First In First Out) instead of a stack and
> * **it checks whether a vertex has been discovered before enqueueing the vertex rather than delaying this check until the vertex is dequeued from the queue.**

**My two questions are:**

* Why is this important (i.e., why does each algorithm need to do it in a different way), and
* Why does it specifically apply to the **non-recursive** implementation?

# Answer
1. Without this step, you are not actually going through a "DFS". You would still be visiting all the nodes, however. Have a look at the example below:

You can see that the order in which one marks nodes as visited in an iterative DFS matters. In the image, by following the approach of marking "visited" before we visit a node, at step 3) node C) is not pushed (since it was marked as visited when exploring node A)

2. There is not actually any difference in the order this is done between the recursive implementation and the iterative one. In the recursive implementation, one typically:

```
def dfs(node):
  mark node as visited
  # other visitation logic may go here ...
  for neighbour of node:
    if neighbour not in visited:
       dfs(neighbour)

```

You will notice that other nodes are not explored in the neighbour list until one fully finishes with the neighbour, by calling dfs(neighbour). Thus, a node's neighbours are visited in depth-first manner vs one-after-another.

In the recursive implementation, one may choose to mark the neighbours as visited before calling dfs() for them as well. In this case, the order is still preserved, because the next thing that happens is that one fully recurses into the neighbour's subtree.
> 1 votes

---
Tags: graph-traversal
---


title: Throughput and response time

text:
# Question
Title: Throughput and response time
I have read that a decrease in response time does not necessarily entail an increase in throughput, but I'm struggling to understand the exact way that this can happen. What I'm imagining is a server receiving requests from several different connected devices. Say computer `A` sends a request and the server starts working on it. While it's working, it receives a request from computer `B`.

To keep the model simple, we imagine that while the computer is processing request `A`, it holds request `B` and will get to it when it's done sending the response to `A`. Task `A` takes 10 seconds to compute 1 billion flops or whatever. `B` takes 10 seconds to compute 2 billion flops because maybe those flops for some reason required more processing or something. And maybe `B` was received 5 seconds after `A`.

So the net time that `A` spent waiting is 10s, and the net time `B` spent waiting is 15s, so the average response rate is I guess is

$$ 25s/3\ billion\ flops $$

(I don't know that this is the right way to think about response rate but it's the best I can come up with.)

And the throughput is, I guess proportionate to

$$ 3\ billion\ bits / 20s $$

(if the number of bits about linearly correlates to the number of flops, which I think is reasonable?)

Now if you double the response rate, the number of bits doesn't change but the server now spends just 5s on `A` and receives `B`'s request right when it's done with `A`, spending 5s on that. The response rate is now

$$10s/3\ billion\ f$$

The throughput is proportionate to

$$3\ billion\ b/10s$$

So the response rate more than halved, but the throughput doubled.

---

So what could happen to make the throughput stay fixed while the response rate doubles? Any examples that I can find while googling seem to vaguely indicate that the server could increase the response rate by distributing the time that it spends on each request evenly while not affected the throughput.

But I don't see how that increases the response rate -- isn't the response rate a weighted average over all requests? If not how could you even talk about "the response rate" when every particular request will make a different demand and require a different amount of time? If it is an average, then the order in which requests are processed shouldn't matter since the net time and net flops isn't affected.

# Answer
You have to define what you mean by "response time".

Let's suppose we have a client sending a request to a server over a network, and the server sending back a response. What is the time it takes from when the client has the request to when it receives the response? Well, there likely is the time the request spends on a queue waiting for the network to become available, the time it takes for the request to transit the network, the time the request spends on a queue waiting for the server to become available, the time it takes for the server to compute a response, the time the response spends on a queue waiting for the network to become available, and the time it takes for the response to transit the network. Response time might mean the sum total of all of those, or it might mean just one of those quantities (e.g., the time it takes for the request or the response to transit the network, or the time it takes for the server to compute the response).

If the time it takes for the response to transit the network decreases, but the bottleneck is the server's ability to handle requests, then the overall throughput will not increase, because the server's throughput will be the bottleneck. You will get responses back a little bit quicker but the number of responses received per second will remain the same.
> 1 votes

---
Tags: computer-networks
---