# Question
Title: Differential Privacy with only positive noise
The Laplace mechanism is a standard way of making the output of a function $f$ differentially private. More concretely, let $\Delta\_f$ be the sensitivity of $f$, i.e. the maximum value by which the output of $f$ can change, if the input database is changed by one row. On input database $x$, the $\epsilon$-private Laplace mechanism outputs $x + R$, where $R$ is sampled from the $Lap(1/\epsilon)$ distribution, which is scaled by $1/\epsilon$. Since the distribution is symmetrically distributed around $0$, it can regularly happen that the added noise $R$ is negative and thus the reported value $x + R \< x$.

**Question:** Are there mechanisms that only adds positive noise, i.e. that never produces an output that is smaller than the real output? Importantly, I'm interested in mechanisms that do not know a lower bound on the output range of $x$ (this exclude simple truncation approaches like the ones used for histograms, which can be truncated at $0$).

# Answer
what you are looking for is the "exponential mechanism". See https://www.cis.upenn.edu/~aaroth/Papers/privacybook.pdf. It is a very general mechanism, which includes one-sided noise as a special case.
> 1 votes

---
Tags: statistics, differential-privacy
---


# Question
Title: $L =$ { $\langle M \rangle$ | $M$ moves left on at least one input }
Is $L =$ { $\langle M \rangle$ | $M$ moves left on at least one input } decidable? What would the proof look like?

Intuitively, I would say it's undecidable: We cannot predict if a given TM ever reaches an accepting transition on a specific input, let alone predicting if it would reach some transition $\delta(q,a) = (p,b,-1)$ on ANY input.

This leads me to another question: Let $L' =$ { $\langle M, w \rangle$ | $M$ moves left on input $w$ }. Is L' decidable? Could two such "versions" of a language, where one version asks about **any** input and the other about a **specific** input, differ in decidability?

# Answer
The language $L'$ is decidable. Consider the operation of a TM $M$ on an input $w$. If $M$ does not move its head to the left when it runs on $w$, then after $|w|-1$ steps, $M$'s head reaches the first blank tape cell and it enters some state $q\_1$. When in $q\_1$ and $M$ reads a blank, it moves to the right and enters a state $q\_2$ (possibly equals $q\_1$). Applying the latter considerations again, you get that from $q\_2$, $M$ reads a blank symbol, moves its head to the right and enters a state $q\_3$, etc. As we're only reading blanks and moving to the right, we will eventually repeat a state and get stuck in a loop of states, and that is guaranteed to happen within at most $|w|-1 + |Q|$ steps of the machine's. In total, we have the following. If $M$ does not move its head to the left upon reading the input $w$, then it enters a loop of states (where it only reads blanks and moves to the right) after at most $|w|-1+|Q|$ steps. Hence, the following algorithm decides $L'$. On input $\langle M, w \rangle$, simulate the run of $M$ on $w$ for at most $|w|-1 + |Q|$ steps, and accept only when $M$ moves its head to the left during the simulation.

Regarding the language $L$, it is also decidable! The idea is as follows. Given a machine $M$, check if there is a path (according to the definition of the transition function) from $q\_0$ to a transition that moves the head of the machine to the left. We distinguish between two cases:

**1-** **No such path exist:** this case is easy, as it implies that there is no input on which the machine moves its head to the left.

**2-** **Such a path exists:** consider a minimal path $p$ from $q\_0$ to a Left-transition. As $p$ is minimal, when the machine reads the input word $w$ that is induced by $p$'s transitions, it never moves to the left, and thus we can say for sure that $M$ moves its head to the left on at least one input.

**Notes:**

* I assumed that the machine moves only to the left or right.
* Your intuition is misleading. Checking if a machine accepts at least one input is undecidable since even if we detect that $q\_{acc}$ is reachable, it can be reachable via transitions that can only be used upon reading a specific tape content that we can never reach because what we write on the tape right before moving to the left can change the tape's content in a way that makes it impossible to use some "reachable" transitions.
> 0 votes

# Answer
Concerning the general question *Could two such “versions” of a language, where one version asks about any input and the other about a specific input, differ in decidability?*:

They sure can. E.g., consider $L=\\{\langle M\rangle:\text{$M$ halts}\\}$ and $L'=\\{\langle M,n\rangle:\text{$M$ halts in $n$ steps}\\}$ (where $M$ is a TM with no input). Or, in the other direction: $L=\\{w:\text{$w$ is accepted by some TM $M$}\\}$ and $L'=\\{\langle w,M\rangle:\text{$M$ accepts $w$}\\}$.
> 0 votes

---
Tags: turing-machines, undecidability, decidability
---


# Question
Title: Does the Nth iteration of Bellman-Ford relax every edge reachable from a negative cycle?
Consider a graph $G$ with $N$ nodes, with the distance of each node initially set to infinity (there is no start node). If there are no negative cycles in the graph, then after $N - 1$ iterations of Bellman-Ford, any additional iterations will not modify the distances (the distances are stable).

On the other hand, if there are negative cycles in the graph, then the $N$th, $N+1$th, ... iterations will continue to decrease the distances of nodes reachable from any negative cycles in the graph.

The question is: will the $N$th (and only the $N$th) iteration relax every edge reachable from a negative cycle? That is, does it suffice to perform $N$ iterations to find all edges reachable from a negative cycle?

# Answer
> 1 votes
The following is a simple counter-example.

Let $V = \\{a,b,c,d\\}$ be a vertex set with all the initial distances set to arbitrarily value $D$.

There are the following directed edges with weights:

1. $w(a,b) = -3$
2. $w(b,c) = 1$
3. $w(c,a) = 1$
4. $w(b,d) = -3$

Then the edge $(b,d)$ relaxes in the $1$st, $2$nd, and $5$th iteration, and not the $4$th iteration.

---
Tags: graphs, shortest-path, weighted-graphs, dag
---


# Question
Title: Construct a Circuit computing all boolean functions over n bits
> Let $ n∈N $ . Construct a circuit with $ C\_n(x\_1,\dots,x\_n) $ with $ 2^{2^n} $ outputs $ y\_1,\dots,y\_{2^{2^n}} $ which computes all distinct boolean functions $ f\_i:\\{0,1\\}^n→\\{0,1\\}$ such that $ y\_i $ is the output of $ f\_i $ and satisfying $ Size(C\_n)\in O(2^{2^n}) $

Remark: The circuit is in a model of fan-in 2.

I've already found a solution in $ O(2^{2^n + n}) $ but I can't find less even recursively.

# Answer
Given the circuit $C\_n$, you can compute $C\_{n+1}$ using $O(2^{2^{n+1}})$ additional gates. Indeed, each output gate of $C\_{n+1}$ is of the form $$ (\lnot x\_{n+1} \land y\_i) \lor (x\_{n+1} \land y\_j) $$ for some $i,j$, so can be computed from the outputs of $C\_n$ using $O(1)$ additional gates.

In total, the circuit $C\_n$ uses $O(2^{2^n} + 2^{2^{n-1}} + \cdots) = O(2^{2^n})$ gates.
> 1 votes

# Answer
There is such a circuit with exactly $2^{2^n}$ nodes (which is, of course, minimal possible). I’m assuming arbitrary nodes in the circuit can be designated as output nodes, including input nodes and nodes of nonzero fan-out; otherwise you would have to copy them, leading to at most double the size.

Start with the $n$ input nodes $x\_1,\dots,x\_n$, and repeat the following in arbitrary order until it is no longer applicable, where $f\_y$ denotes the Boolean function computed by node $y$ of the circuit:

* Pick a node $y$ such that $\neg f\_y$ is not computed by any node of the circuit, and add a new node $\neg y$.
* Pick a pair of nodes $y$ and $y'$ such that $f\_y\land f\_{y'}$ is not computed by any node of the circuit, and add a new node $y\land y'$.

When the construction stops, the set of functions $\\{f\_y:y\in C\\}$ is closed under $\neg$ and $\land$, hence it contains all Boolean functions in $n$ inputs. On the other, by construction, no two nodes of the circuit compute the same function. Thus, the size of the circuit equals the number of functions in $n$ variables, viz. $2^{2^n}$.

An alternative construction with the same result: take *any* circuit that computes all functions in $n$ inputs, and keep removing redundant nodes. That is, if $y\ne y'$ compute the same function, and (wlog) $y$ does not depend on $y'$, then remove $y'$, and redirect all output wires of $y'$ to use $y$ instead. When you cannot do this any longer, no two nodes compute the same function, hence the size of the circuit is $2^{2^n}$, again.
> 0 votes

---
Tags: complexity-theory, circuits, upper-bound
---


# Question
Title: Scheduling classes with lower and upper bounds on students and classes
I am struggling to solve the following excercise:

> Design an assignment of a group of n students to m classes. Student i should take a minimum of $l\_i$, and a maximum of $u\_i$ within a set C1 of classes. Class j should be attended by a minimum of $m\_j$ and a maximum of $M\_j$ students in order to be activated.
>
> 1. Design an algorithm that solves the problem of the existence of a feasible schedule in polynomial time.
> 2. Study the time complexity of the algorithm.

I think I am overthinking this a bit: I have tried creating a graph made as follows:

* Minimum classes per student as capacities on edges from a source to each student
* Maximum number of students per class on edges from classes to a sink
* Edges between students and classes: if student $i$ can attend class $j$, then there is a single capacity edge This was done in order to calculate max-flow, which I am aware would not actually solve the problem. But I can't come up with anything better. Any help would be greatly appreciated!

# Answer
> 1 votes
I think you are almost there: the intuition about using the max-flow is correct.

In your graph model one thing lacking is the constraint on minimum students that a class must have(for this to be a feasible solution).

A correct model(on which an appropriate max flow algorithm would give us the answer on existence of solution) is:

* Create node sink t and source s.
* Create a node for each student and a node for each class.
* From node s create an arc to each student node with maximum capacity equal to the maximum number of classes the student can take and minimum capacity as the number of classes the student must take.
* Each student node has an arc to each class node he can take with minimum capacity 0 and maximum capacity 1.
* Each class node is linked to the sink t with minimum capacity equal to the minimum number of students that need to take the class and maximum capacity equal to the maximum number of students that can take the class.

Now, for the algorithm, you can use Ford Fulkerson on an appropriately transformed graph where all minimum flow constraints are set to 0.

A possible transformation is given here. Lemma 1. proves that if you find a max flow saturating all arcs exiting the new source(and entering the new sink) in the transformed graph then a feasible solution on original graph exists thus a valid scheduling exists.

---
Tags: algorithms, complexity-theory, algorithm-analysis, network-flow, bipartite-graph
---


title: Application of dependent product

text:
# Question
Title: Application of dependent product
On the proof assistants StackExchange site, someone gave this example of a dependent product:

$$\prod\_{i\in I}\sum\_{j\in J\_i}x\_{ij}=\sum\_{f\in\prod\_iJ\_i}\prod\_{i\in I}x\_{if(i)}$$

The dependent product is the $\prod\_iJ\_i$ bit, and just what role it plays in this case is mysterious to me.

It's a very short answer, and the above equation expresses "the rule for multiplying out brackets". https://proofassistants.stackexchange.com/a/1114/628

I am trying to understand the RHS as a procedure for multiplying an expression such as $(a + b + c)(d + e)(f + g + h)$

So, say this expression is represented as a two-dimensional array, with a, b, c on the first row, and so on. Then, the formula on the LHS sums each row and calculates the product of the results.

What does the RHS do, in terms of code?

# Answer
Thanks to Trebor for explaining the procedure.

Here is Python code which uses explicit indexing in order to match the original expression. For simplicity it replaces the function `f` with an array-—so `f(i)` becomes `f[i]`.

In order to get the dependent product of the arrays of indices, I use `itertools.product()`, because actually computing the Cartesian product is not really in the scope of the question, and how it is calculated is not conceptually important.

```
import itertools

# (1 + 3)(7 + 9 + 1 + 3)(6 + 7)
terms = [
   [1, 3],
   [7, 9, 1, 3],
   [6, 7]
]

indices = []
for t in terms:
    indices.append(list(range(len(t))))

fs = itertools.product(*indices)

total = 0
for f in fs:
    intermediate = 1
    for i in range(len(terms)):
        intermediate *= terms[i][f[i]]
    total += intermediate

print(total)

```
> 0 votes

---
Tags: dependent-types
---


# Question
Title: Proof or Disproof if $ L $ is a Regular language then it has to be that $ L\leq HP $
> Proof or Disproof
>
> if $ L $ is a Regular language then it has to be that $ L\leq HP $

$ HP=\\{\<M,x\> | M \ halts \ on \ x \\} $ Regular language is a language that can be expressed with a regular expression or a deterministic or non-deterministic finite automata

I know that HP is in RE\R and I know the regular language is in R and I know that due to the reduction principle, if $ L1 \leq L2 $ then if $ L2 \in RE $ then L1 must also be in RE and also if L1 is not in RE then L2 also not in RE but this is not the case...

$ f(x) = \<M',x\> $ lets create M' such that for all x $in \Sigma^\* $

1. run $ M\_{regular} $ on x if accepts then accepts
2. if rejects then go to infinite loop

L is a decidable language then exist a decidable turning machine such that for all x will halt

HP will only halt on x in the language,

if I try to build a reduction from L to HP lets look at the conditions

$x\in L \rightarrow M\_L(x)=1 \rightarrow $ M halt on x $ \<M',x\> \in HP $

$x\notin L \rightarrow M\_L(x)=0 \rightarrow $ I can send here to an infinite loop so that M **doesn't** halt on x $ \<M',x\> \notin HP $

# Answer
> 2 votes
From your attempt, I see that you got the intuition, but you need to define the reduction formally, and then prove that it works. In your solution, it is not clear how $M'$ is defined, and what is $M\_{regular}$ -- for me, I just saw your thoughts/attempts, not a proof.

Here, I showed a slightly more general claim, specifically, every non-trivial language is $R$-hard (harder than every language in $R$). Since $L\in R$, and $HP$ is non-trivial, then what you're asking for follows immediately. Try to prove that the reduction there is computable (there is a TM that computes it), and that it is correct.

The idea essentially is as follows. Since we can decide $L$, then we can define a reduction that checks whether its input is in $L$, and then outputs a word inside or outside $HP$, accordingly. So languages in $R$ are too easy, w.r.t mapping reductions, in the sense that we (the reduction) can solve/decide them, and then output whatever we want.

---
Tags: formal-languages, turing-machines
---


# Question
Title: The problems in the P class can be polynomially reduced to its complement and vica versa?
I considered the Euler circle problem to decide this. The polynomial reduction is: I add a new vertex in the graph:

* If the degree of each vertex is even, then I connect all the vertices with this new vertex
* Otherwise, I only connect the vertices with an odd number of degrees to the new vertex Is this a correct reduction?

# Answer
> 2 votes
The claim is false. $\emptyset$ cannot be reduced to its complement $\Sigma^\*$ (and vice-versa).

However, if you restrict yourself to languages $L$ such that $L \not\in \\{ \emptyset, \Sigma^\*\\}$ then it is true that $L \le \overline{L}$. To see this let $n$ be any fixed element of $L$ and let $y$ be any fixed element of $\overline{L}$. Such elements exist by our choice of $L$.

The reduction is given by: $$ f(x) = \begin{cases} y & \mbox{if } x \in L \\ n & \mbox{if } x \not\in L \end{cases}. $$ Notice that $f$ can be computed in polynomial time since $L \in \mathsf{P}$, which means that we can decide in polynomial time whether $x \in L$.

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


# Question
Title: $A$ and $B$ two decision problems.If $A\le\ B$ then $\overline{B}\le\overline{A}$ is true?
I have proved that $\overline{A}\le\overline{B}$ is true, but I have no idea how to prove or disprove the opposite direction.

# Answer
> 2 votes
The claim is false. There are several ways to show it. Note that if $\overline{B} \leq\_m \overline{A}$, then $B\leq\_m A$ (this is what you've shown). Hence, if by contradiction the claim is true, then we can write it as $A \leq \_m B \to B\leq\_m A$, which is clearly wrong. Why? because it simply says "if $B$ is harder than $A$, then $A$ is harder than B". Hence, an immediate classical counter-example would be, an "easy" problem $A\in \text{R}$, and a "hard" problem $B\notin \text{R}$.

**Edit:** I focused on the intuition that you should have when reading such claims. If you do not see immediately why what I wrote serves as a counter-example, then I suggest to think about it, or you can note that every non-trivial language is $R$-hard.

# Answer
> 1 votes
No. Take $A = \emptyset$ and $B = \\{0\\}$. A reduction $f$ from $A$ to $B$ is the function $f(x) = \varepsilon$ since $x \not\in A$ (regardless of the choice of $x$) and $\varepsilon\not\in B$. However $0 \not\in \overline{B}$ and there is no function $g$ such that $g(0) \not\in \overline{A} = \Sigma^\*$, hence there is no reduction from $\overline{B}$ to $\overline{A}$.

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


title: Is the Given Languages CFL or DCFL?

text:
# Question
Title: Is the Given Languages CFL or DCFL?
$L\_1$ = {$a^nb^mc^xd^y$|$n=m$ or $x=y$}

$L\_2$ = {$a^nb^xc^md^y$|$n=m$ or $x=y$}

For $L\_1$:

* Push a's
* Now pop the same number of b's , Given n=m
* If Stack is empty and x=y=0 accept the Langauge
* else push c's and pop d's
* If Stack is empty accept the Langauge

It's DCFL and also CFL.

For the $L\_2$: It's Not CFL.

But the answer key mentioned in my Quiz said that they both are CFL.

Answer\_key

How $L\_2$ is CFL and the $L\_1$ not DCFL?

# Answer
> 1 votes
Your argument for $L\_1$ isn't quite correct, but the core idea can indeed be adapted to obtain a deterministic pushdown automaton for $L\_1$. I don't know why the answer key claims that the language is non deterministic context-free; that is probably something to take up with whoever provided that key.

For the second language, there is a pushdown automaton for it, thus it is indeed context-free. The automaton guesses first whether to check $n = m$ or $x = y$, and then does that.

---
Tags: automata, pushdown-automata
---


# Question
Title: The SAT problem can be reduced to the complement of the halting problem?
The SAT is in NP, I suppose that the complement of the halting problem is in coNP-hard. I suppose the answer is no because SAT is not in coNP, but I am not sure.

# Answer
Let $T$ be a fixed Turing machine that decides SAT. From $T$ it is easy to construct a Turing machine $T'$ that takes SAT instance $x$ as input and halts iff $T(x)$ rejects.

In other words, given a SAT instance $x$, $x$ is satisfiable iff the pair $\langle T', x \rangle$ is in the complement of the Halting language.
> 2 votes

# Answer
A PTIME reduction from $\text{SAT}$ to $\overline{HALT\_{TM}}$ operates as follows. On input $\varphi$, the reduction outputs $\langle M, \varphi\rangle$, where $M$ is a constant TM that operates as follows. On input $\varphi$, $M$ goes over all assignments to variables of $\varphi$, and checks whether $\varphi$ is satisfiable. If $\varphi$ is satisfiable, $M$ gets stuck in a loop, otherwise, $M$ halts. It is not hard to see that the reduction is polynomial in $|\varphi|$. Indeed, the description of $M$ does not depend on $\varphi$. Also, $M$ halts on $\varphi$ iff $\phi \in \overline{\text{SAT}}$, and thus $\phi \in \text{SAT}$ iff $\langle M, \varphi\rangle \in \overline{HALT\_{TM}}$.

The point here is that we do not care if $M$ is efficient as the reduction outputs its description, which costs us a constant time in $|\varphi|$.
> 5 votes

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


# Question
Title: Algorithm to find the seating capacity on each trip within a multi stop journey
Imagine there's a boat with a fixed number of seats. The boat goes on a journey with n number of stops.

Here is a diagram of the journey where n = 4

The squares represent a stop. The lines represent a trip.

Trips occur from each stop to every other stop that comes after it.

People may go onboard at the start of a trip (which occupies a seat) and may leave at the end of the trip (which frees up a seat).

What would be the algorithm to find out the seats occupied in each trip?

# Answer
> 2 votes
To find out the seats occupied in each trip, you can use the following algorithm:

**Step 1.** Initialize an empty array or list to store the seats occupied in each trip.

**Step 2.** Create a 2D array or matrix to represent the stops and trips. The rows represent the stops, and the columns represent the trips.

**Step3.** Iterate over each stop, starting from the first stop to the second-to-last stop.

**Step4.** For each stop, iterate over the trips that start from that stop and go to subsequent stops.

**Step5.** During the iteration, for each trip, determine the occupied seats.

* If the current stop is A and the subsequent stop is B, you can represent the occupied seats as a tuple (A, B, occupied\_seats), where occupied\_seats is a list or set of seat numbers occupied during the trip from A to B.
* To determine the occupied seats, you can use a seat allocation algorithm. One simple approach is to assign seats sequentially starting from seat 1, and if a passenger leaves the boat, mark their seat as available again.
* Keep track of the occupied seats for each trip segment.

**Step6.** After iterating over all the stops and trips, you will have a list of occupied seats for each trip segment.

**Step7.** You can then use this information to analyze the occupancy patterns or perform further calculations as needed.

# Answer
> 1 votes
How I implemented this algorithm in go:

```
func calcRouteTripSeating(trip Trip) error {
    // Flatten all toStops into on array
    var toStops []RouteToStop
    for i := range trip.Route.Stops {
        for j := range trip.Route.Stops[i].ToStops {
            toStops = append(toStops, trip.Route.Stops[i].ToStops[j])
        }
    }
    // Find boarding and unboarding number at each stop
    for i := range trip.Route.Stops {
        for j := range toStops {
            for k := range trip.Bookings {
                if !trip.Bookings[k].IsPaid {
                    continue
                }
                if *trip.Bookings[k].RouteToStopID == toStops[j].ID {
                    occupiesSeatCount, err := getOccupiesSeatCount(trip.Bookings[k].Customers)
                    if err != nil {
                        return err
                    }
                    if trip.Route.Stops[i].Order == toStops[j].RouteStop.Order {
                        trip.Route.Stops[i].Boarded += occupiesSeatCount
                    } else if trip.Route.Stops[i].Order == toStops[j].Order {
                        trip.Route.Stops[i].Left += occupiesSeatCount
                    }
                }
            }
        }
    }
    // Loop through all the stops
    // Find all toStops that start at a stop and end after that stop
    // Assign the current boarded value to toStop if it is greater than the
    // toStop's value
    var current int64
    for i := range trip.Route.Stops {
        current += trip.Route.Stops[i].Boarded - trip.Route.Stops[i].Left
        for j := range toStops {
            if toStops[j].RouteStop.Order <= trip.Route.Stops[i].Order && toStops[j].Order > trip.Route.Stops[i].Order {
                if current > toStops[j].Booked {
                    toStops[j].Booked = current
                }
            }
        }
    }
    // Assign booked amounts back into original object
    for i := range trip.Route.Stops {
        for j := range trip.Route.Stops[i].ToStops {
            for k := range toStops {
                if toStops[k].ID == trip.Route.Stops[i].ToStops[j].ID {
                    trip.Route.Stops[i].ToStops[j].Booked = toStops[k].Booked
                }
            }
        }
    }
    return nil
}

```

---
Tags: algorithms
---


# Question
Title: Returning more than one value from a function without overhead
In stack languages (e.g. PostScript, Forth), return values are passed on the stack - zero, one, even a variable number.
Python supports tuples of values there, frequently used "without tuple syntax", but creating a tuple regardless (garbage if not kept but unpacked immediately).

Is there any non-stack language handling multiple return values without overhead?
Handling a variable number of return values without overhead?

# Answer
Modern compilers are quite capable of optimizing a tuple return value so that the result is passed in registers, or in an unpacked form on the stack.

In addition, even when this is not the case, worrying about the overhead is misplaced. If the tuple fits in primary cache, chances are nobody is going to notice the difference.

It was true in 1970 that the programmer had to understand the CPU and memory they were using, because every CPU cycle and every byte of memory was precious. That is why languages such as C were so successful – one can basically predict the machine code that a C compiler generates.

Nowadays the typical programmer only has a vague idea of what the compiler, the optimizer and the CPU actually do. The bottleneck is not in the CPU cycles or bytes of memory, but in the software development time. One should worry about having a programming language that allows one to *easily* return two values, but not *how* those two values are returned.

If you happen to be programming an embedded device or a super-computer in which 1% saving of electricity translates to many thousands of dollars in reduced costs, then of course you're playing a different game.
> 2 votes

# Answer
Swift allows a single return value. However, a “tuple”, including one with unnamed components, is one of the basic types (struct, class, enum, tuple and closure; int, double, string and arrays are really structs) so that is not a problem. For a tuple, obviously it’s a bigger value than a single value and needs more code, but the fact that there is a tuple doesn’t cause overhead.

Now tuples have a fixed number of elements and fixed element types. If you wanted to return a different number of items or items with different types, you would return an enum, which is kind of a mix between C enum and C Union. There’s a bit of overhead because the function must return which kind of enum it is, and possibly more overhead if the size of the enum cases is different.
> 1 votes

---
Tags: programming-languages
---


# Question
Title: Is there a language $L$ such that $L \in DSPACE(1) \setminus DTIME(1)$?
It is a very straightforward question.

I know that the following holds, and I know why it holds:

$DTIME(f(n)) \subset DSPACE(f(n))$

However, is there a language $L \in DSPACE(1) \setminus DTIME(1)$? The "1" is supposed to represent a constant complexity.

It seems to me there is not such language but I don't know how to prove it.

# Answer
> 2 votes
No. Consider the language

$$L = \\{x \in \\{0,1\\}^\* \mid x \text{ has even parity}\\},$$

i.e.,

$$L = \\{x\_1 \cdots x\_n \mid x\_1 + x\_2 + \cdots + x\_n \equiv 0 \pmod 2\\}.$$

This language is in $\textsf{DSPACE}(1)$ (it can be recognized by a DFA with 2 states, so you only need 1 bit of state), but it is not in $\textsf{DTIME}(O(1))$ (you need to read the entire string to determine its parity, which takes time $\Theta(n)$).

FYI, $\textsf{DSPACE}(O(1))$ is exactly the set of all regular languages. $\textsf{DSPACE}(1)$ is normally taken to be synonymous with $\textsf{DSPACE}(O(1))$. $\textsf{DTIME}(O(1))$ is boring, as it is not possible to read the entire input in $O(1)$ time. It is known that every language in $\textsf{DTIME}(O(n))$ is regular (in fact every language in $\textsf{DTIME}(o(n \log n))$ is regular). See https://math.stackexchange.com/q/84040/14578.

Here is a very nice overview of complexity classes that contains the above result about $DSPACE(O(1))$ and regular languages:

Classifying Problems into Complexity Classes. William Gasarch. November 21, 2015.

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


# Question
Title: Prove the existence of a language L over the alphabet Σ = {1} such that L ∌ RE and L ∌ CoRE
I attempted to create a language $L\_1$ = {$\<M\>| L(M) = 1^\*$} and prove using a reduction that $L\_1$ ∌ RE and $L\_1$ ∌ CoRE by showing that $HP ≤ L\_1$ and $\overline{HP}$ $≤ L\_1$. But my instructor said this isn't correct.

# Answer
Both reductions look fine and are easy to come up with. You need to ask your instructor what is wrong with your suggested reductions.

A reduction from $HP$ to $L\_1$ operates as follows. Given input $\langle M, w\rangle$, the reduction outputs $\langle T\rangle$, where $T$ is a machine that rejects every input not of the form $1^\*$, and for every input $x$ of the form $1^\*$, it simulates the run of $M$ on $w$, and accepts $x$ only when $M$ halts on $w$.

Then, a reduction from $\overline{HP}$ to $L\_1$ operates as follows. Given input $\langle M, w\rangle$, the reduction outputs $\langle T\rangle$, where $T$ is a machine that operates as follows. On input $x$ for $T$, $T$ simulates the run of $M$ on $w$ for $|x|$ steps. If within the simulation, $M$ does not reach $q\_{acc}$ or $q\_{rej}$, then $T$ accepts $x$. Otherwise, $T$ rejects $x$.

I leave correctness to you, and note that both reductions are valid when $T$ is a machine over an unary alphabet $\Sigma = \\{ 1\\}$. I think one of your suggested reduction assumes that the alphabet of $T$ is not unary, and I suspect it is the one from $\overline{HP}$, but I cannot tell for sure without seeing your solution.
> 0 votes

# Answer
Your language is neither in RE nor in co-RE, and the reductions you have mentioned prove this. However, it is unclear to me whether your language is using only the alphabet $\\{1\\}$. This depends on how your coding of TMs which underlies $\langle \cdot \rangle$ works. To the extent that you have a concrete definition of $\langle \cdot \rangle$ in play, I'd guess that it uses more symbols than just $1$ (unless you enjoy suffering).

Your instructor may want you to add some argument over why we can just use $\\{1\\}$ as alphabet, since we only care about computability here.
> 0 votes

---
Tags: formal-languages, turing-machines
---


# Question
Title: How to find a satisfying assignment in polynomial time without the use of randomness?
Assume that we are given a formula in 3-CNF such that at least 1% of the complete assignments satisfy it.

My question is how to find a satisfying assignment in polynomial time without the use of randomness? Prove the correctness and the upper bound on the running time for the algorithm that you suggest.

# Answer
For refresher, let's first remember (Wikipedia) that we can convert any Boolean expression into conjunctive normal form, which is defined as conjunction ("AND" $\land$) of one or more disjunctions ("OR" $\lor$) of one or more literals, and governed by six context-free grammar rules. Naively this is exponential in length, but we can efficiently reduce this to linear length by preserving satisfiability instead of equivalence (Wikipedia).

In this answer, we want to elaborate the answer from 2010 on the CS Theory site.

> If $0\<\epsilon\<1$ is a constant (or $1/polylog(n)$), and you are promised that at least $\epsilon2^n$ of all possible assignments are satisfying the input 3CNFs, then you can find such an assignment in deterministic polynomial-time.

We interpret $n$ as $k$ since it is standard, 3CNFs as k-CNFs since it is relevant to the time complexity as the number of literals increases, $1/polylog(k)$ as $1/k$ since it is actually $1/polylog(2^k) = 1/k$. In our case $\epsilon = 0.01 = 1\\%$ and $k = 3$, we are promised that at least $0.01 \times2^k$ of all possible assignments are satisfying the CNF, and we want to prove we can find such an assignment in deterministic polytime.

> The algorithms is not difficult:

The noun is meant to be singular instead of plural.

> Claim: Under the promise stated, there must exist a constant size set $S$ of variables that hits all clauses in the 3CNF, in the sense that every 3-clause must contain a variable from $S$.

The set $S$ contains the literals that hit all disjunctive clauses (first sentence of the refresher) in the CNF. For example, $S = \\{B, \neg C\\}$ means $B = true$ and $C = false$, hitting $(A \lor B \lor C)$, $(A \lor B \lor \neg C)$, $(A \lor \neg B \lor \neg C)$, $(\neg A \lor B \lor C)$, $(\neg A \lor B \lor \neg C)$, and $(\neg A \lor \neg B \lor \neg C)$, but not hitting $(A \lor \neg B \lor C)$ and $(\neg A \lor \neg B \lor C)$. The claim here is that the smallest size of $S$ is constant (only inversely proportional to $\epsilon$) instead of non-constant (proportional to $k$).

> Proof of claim (sketch): Otherwise, there must exist a large enough family of 3-clauses from the 3CNF, in which each variable occurs only once. But this family, when sufficiently large, has already less than $\epsilon$ fraction of satisfying assignments. QED

This is a proof by contradiction. We know the size of $S$ is at least constant and at most linear, since there are only $k$ literals. We know the number of clauses in the CNF is linear (last sentence of the refresher). If the smallest size of $S$ is nonconstant, its fixed assignments will only hit the clauses in the CNF a sublinear number of times statistically (side note: constant smallest size -\> linear number of times), but this means the number of satisfying assignments is also sublinear, contradicting the promise that it is linear. Therefore, the smallest size of $S$ is constant.

> Thus, you can run over all possible (constant number) of assignments to $S$. Under every fixed assignment to $S$, the 3CNF becomes a 2CNF, by the assumption that $S$ hits the original 3CNF. Now, you can use the known polytime deterministic algorithm for finding a satisfying assignment for 2CNF formulas. Overall, you get a polynomial time upper bound.

We can reduce 3CNF to 2CNF according to the laws of Boolean algebra (Wikipedia) after choosing a fixed assignment from $S$. We observe that "false or" can be reduced through removal, as well as "true and". We also observe that "true or" is immediately true, and "false and" is immediately false. The polytime algorithm for 2CNF is linear (Wikipedia).

Here's a distributive law example $A \lor (B \land C)$, we will work with its CNF form.

We know $S = \\{A\\}$ works, as well as $S = \\{B, C\\}$. Let's choose a fixed assignment $B$ from $S = \\{B, C\\}$ and reduce the 3CNF.

$(A \lor B) \land (A \lor C) = (A \lor true) \land (A \lor C) = (A) \land (A \lor C)$

Here's an XOR example $A \oplus B \oplus C$, we will work with its CNF form.

We know $S = \\{A, \neg B, \neg C\\}$, $S = \\{A, B, C\\}$, and some others work. Let's choose a fixed assignment $A$ from $S = \\{A, \neg B, \neg C\\}$ and reduce the 3CNF.

$(A \lor B \lor C) \land (A \lor \neg B \lor \neg C) \land (\neg A \lor \neg B \lor C) \land (\neg A \lor B \lor \neg C)$

$= (true \lor B \lor C) \land (true \lor \neg B \lor \neg C) \land (false \lor \neg B \lor C) \land (false \lor B \lor \neg C)$

$ = true \land true \land (\neg B \lor C) \land (B \lor \neg C)$

$ = (\neg B \lor C) \land (B \lor \neg C)$

> The algorithm for 2SAT is I think already in S. Cook famous 1971 paper.
>
> The algorithm for 3CNFs is from: L. Trevisan *A Note on Deterministic Approximate Counting for k-DNF* In Proc. of APPROX-RANDOM, Springer-Verlag, page 417-426, 2004
>
> The original paper showing the result for 3CNF is: E. Hirsch, *A fast deterministic algorithm for formulas that have many satisfying assignments*, Journal of the IGPL, 6(1):59-71, 1998

Read the above references and other references as may be necessary.
> 1 votes

# Answer
As mentioned by Clement C. on CS Theory, this is answered at Conditions for tractability of 3SAT-Satisfiability. You can even replace 1% with any other positive constant.
> 2 votes

---
Tags: satisfiability, polynomial-time, 3-sat, constraint-satisfaction
---


# Question
Title: Efficient way to implement a bit-wise counter that becomes 1 every (k*n)+i times
My question is about LeetCode "137.Single Number II":

> **137.Single Number II**
>
> Given an integer array nums where every element appears three times except for one, which appears exactly once. Find the single element and return it.
>
> You must implement a solution with a linear runtime complexity and use only constant extra space.

Is there a generalized way to solve this and similar questions with the minimum number of bit-wise operations? By similar questions, I mean finding a number that appears k' times where other numbers appear k times.

More detail:

To solve this, I implemented a counter such that bit *i* of the counter becomes 1 only when 1 appears 3k+1 times in bit *i* of nums. To do so, I used two integers, A and B, to keep the 1 bit count for each bit *i*. I wrote down a possible sequence for bits in A and B so I could use A as the counter (there were possible other sequences): AiBi = 00 -\> 10 -\> 01 -\> 00 -\> .... Then, I used a similar approach as calculating a Logic Gate to find bit operations that resulted in the above sequence:

```
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        A = 0
        B = 0
        for num in nums:
            A, B = ((~(A|B))&num)|(A&~num),(A&num)|(B&~num)
        return A

```

With the same approach, I can find any number that repeats k times if all other numbers repeat k' times.

Then I saw this solution:

```
class Solution:
  def singleNumber(self, nums: List[int]) -> int:
    ones = 0
    twos = 0

    for num in nums:
      ones ^= (num & ~twos)
      twos ^= (num & ~ones)

    return ones

```

This is more efficient and beautiful than mine because it does 6 bitwise operations per num; mine does 10. What is the most efficient way to implement such counter? How could I know mine was not efficient?

# Answer
It's hard to find the exact optimal sequence of instructions to accomplish some effect. I don't know of any systematic way, other than techniques like superoptimization, which essentially do a brute-force search over all possibilities.
> 1 votes

---
Tags: counting, bit-manipulation, optimal-strategy
---


# Question
Title: How to decide between pre-emptive split or non pre-emptive split and pre-emptive or non pre-emptive merge for a BTree?
I am trying to implement a BTree. As far as I understand the lower the height of the Tree the faster the search (This could be wrong, please correct me if it is).
Is *pre-emptive split* with *non-pre-emptive merge* the best or *non-pre-emptive split* with *pre-emptive merge* or the other 2 combinations left? Which offers better performance and why? I search online I could not find any article that discussed anything regarding this.
After this I need to implement insert. So, I hoping someone can impart some knowledge on which is better?

So, far I do not have much code except the following because I cannot decide which method I should choose and Why? I want fast insertion deletion and search.

```
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <stdbool.h>
#include <string.h>

static enum TreeProperties {
    MIN_CHILDREN = 2,
    MAX_CHILDREN = 6,
    MAX_KEYS = MAX_CHILDREN - 1,
    MIN_KEYS = MIN_CHILDREN - 1, // except root
    SPLIT_KEYS = MAX_KEYS - MIN_CHILDREN,
    SPLIT_KEY_INDEX = MIN_CHILDREN,
    SPLIT_LINKS = SPLIT_KEYS + 1,
    SPLIT_LINK_INDEX = SPLIT_KEY_INDEX + 1,
    MAX_LINKS = MAX_CHILDREN
};

typedef struct BTreeNode {
    struct BTreeNode *links[MAX_LINKS];
    int keys[MAX_KEYS];
    size_t keyCount;
}BTreeNode;

#define firstLink links[0]

/* New node allocation */

static inline size_t childrenNum(BTreeNode *node) {
    return node->keyCount + 1;
}

static inline BTreeNode *_createNode() {
    BTreeNode *newNode = (BTreeNode*)malloc(sizeof(BTreeNode));
    if(!newNode) {
        fprintf(stderr, "New node init failed: out of memory\n");
        exit(EXIT_FAILURE);
    }
    memset(newNode->links, 0, sizeof(BTreeNode)*MAX_CHILDREN);
    return newNode;
}

BTreeNode *BTree_createEmptyNode() {
    BTreeNode *newNode = _createNode();
    newNode->keyCount = 0;
    return newNode;
}

BTreeNode *BTree_createRightSplitNode(BTreeNode *nodeToSplit) {
    BTreeNode *newNode = _createNode();
    memcpy(newNode->keys, nodeToSplit->keys + SPLIT_KEY_INDEX, sizeof(newNode->keys[0]) * SPLIT_KEYS);
    if(nodeToSplit->firstLink) {
        memcpy(newNode->links, nodeToSplit->links + SPLIT_LINK_INDEX, sizeof(BTreeNode*) * (SPLIT_LINKS));
        memset(nodeToSplit->links + SPLIT_LINK_INDEX, 0, sizeof(BTreeNode*) * SPLIT_LINKS);
    }
    newNode->keyCount = SPLIT_KEYS;
    nodeToSplit->keyCount = MIN_KEYS;
}

/* End new node allocation */

/* Search */
static bool isKeyInNodeOrGiveNextLink(int key, BTreeNode *current, size_t *idx /*, size_t * parentLinkIdxToKeyNode*/) {
    *idx = 0;
    while (*idx < current->keyCount && key > current->keys[*idx]) {
        if(current->keys[*idx] == key ) {
            return true;
        }
        //*parentLinkIdxToKeyNode = *linkIdx;
        (*idx)++;
    }
    return false;
}

BTreeNode* BTree_search(int key, BTreeNode *current) {
    size_t i;
    while(current) {
        if(isKeyInNodeOrGiveNextLink(key, current, &i)) return current;
        current = current->links[i];
    }
    return NULL;
}

```

# Answer
The reason it is not debated is because it is obvious, the reason that B-tree was invented, and subsequently B\* tree is to reduce the frequency of rebalancing. Splitting and merging both involve rebalancing, therefore the more it is delayed the better.

However, there is an exception to ordinary splitting rules when bulk loading (Wikipedia), which is $O(n)$ similar to heapify:

> A common special case is adding a large amount of pre-sorted data into an initially empty B-tree. While it is quite possible to simply perform a series of successive inserts, inserting sorted data results in a tree composed almost entirely of half-full nodes. Instead, a special "bulk loading" algorithm can be used to produce a more efficient tree with a higher branching factor.
>
> When the input is sorted, all insertions are at the rightmost edge of the tree, and in particular any time a node is split, we are guaranteed that no more insertions will take place in the left half. When bulk loading, we take advantage of this, and instead of splitting overfull nodes evenly, split them as unevenly as possible: leave the left node completely full and create a right node with zero keys and one child (in violation of the usual B-tree rules).
>
> At the end of bulk loading, the tree is composed almost entirely of completely full nodes; only the rightmost node on each level may be less than full. Because those nodes may also be less than half full, to re-establish the normal B-tree rules, combine such nodes with their (guaranteed full) left siblings and divide the keys to produce two nodes at least half full. The only node which lacks a full left sibling is the root, which is permitted to be less than half full.
> 1 votes

---
Tags: b-tree
---


# Question
Title: Topological/metric space formed by behaviors of distributed system: Safety and Liveness
In the book **A Science of Concurrent Programs** Leslie Lamport describes alternative way how to look at **safety** and **liveness** properties in distributed algorithms.

> **A.5 Another Way to Look at Safety and Liveness** This section provides a different view of safety and liveness based on viewing behavior predicates as sets of behaviors. This view was first recognized by Gordon Plotkin. I find that it helps me understand safety and liveness. To understand it, we first need some more math.

They build a metric space where distance between behaviors is defined as $\delta(x, y) = 1/(1 + commonPrefixLength(x, y))$

Where can I read about this topological/metric space?

I am interested, in particular:

1. What would be the open sets? All behaviors starting with the finit prefixes?
2. What would be a closed set? In my understanding, open set will be also closed. Given an open set $U$ of behaviors starting with prefix `a,b,c`, then any behavior outside of this set, for example, `a,b,x,...` will belong to another open set, and therefore will not be a limit point of $U$.
3. What would be a dense set? I think dense set will be a set consisting of all behaviors ending with stuttering steps - infinite tails where state of the system does not change.

# Answer
The standard reference for the topological characterisation is Bowen Alpern and Fred B. Schneider. Defining liveness. *Information Processing Letters*, 21(4): 181–185, October 1985.

One notable difference to Lamport's characterisation is that Alpern & Schneider don't insist on stuttering closure. If I recall correctly, if one wanted to characerise both versions of safety properties via closures, one would say that a Lamport safety property is a set of behaviours closed under all forms of **stuttering** (finite, anywhere in a behaviour, and infinite, at the end). In Alpern & Schneider's setting safety properties are those sets of behaviours closed under (a) **prefix** (similar to closure under infinite stuttering only) and **limits** (of sequences of behaviours that agree on ever longer prefixes).
> 2 votes

---
Tags: distributed-systems, automated-theorem-proving, tlaplus
---


# Question
Title: Prove that there aren't any complete languages
Prove that there isn't a complete language over a given alphabet $\Sigma$. That is, there is no $C \subseteq \Sigma^\*$ such that every $L \subseteq \Sigma^\*$ is Turing-reducible to $C$.

**Attempt:** Let $L$ be a language and let $\overline{L}$ be its complement. And let's say there is a reduction between $L$ and $\overline{L}$. So, we can say that if there is a word $w$ in $L$ it's also in $\overline{L}$. But that's a contradiction because $\overline{L}$ is all words that are not in $L$.

I'm not sure if this answer is correct though.

# Answer
Doesn't this follow by a counting argument? Fix a language $C\subseteq \Sigma^\*$. On the one had, the number of languages that are Turing-reducible to $C$ is at most $\aleph\_0$. Indeed, there are only countably many Turing machines $M\_C$ with access to the oracle $C$ (see @Ariel's answer here). On the other hand, there are $2^{\aleph\_0}$ languages $L$ over $\Sigma$. Hence, for every language $C\subseteq \Sigma^\*$, there is a language $L\subseteq \Sigma^\*$ that is not Turing-reducible to $C$.
> 1 votes

# Answer
I don't think your attempt works. $A \leq\_T B$ doesn't imply $A \cap B \neq \emptyset$, take for example $$A = a^\*, B = b^\*.$$ We have $A \cap B = \emptyset$ as well as $A \leq\_T B$.

Also, it generally *is* the case that $L \leq\_T \overline{L}$ if I'm not mistaken. Given $L \subseteq \Sigma^\*$, define the oracle-machine $M\_O$ with oracle $O$ deciding $\overline{L}$ as follows, given $w \in \Sigma^\*$

* run $O$ on $w$
* accept $w$ if $O$ rejects $w$
* reject $w$ if $O$ accepts $w$

It can be verified that $L(M\_O) = L$, thus $L \leq\_T \overline{L}$.
> 1 votes

---
Tags: formal-languages, turing-machines, turing-completeness
---


# Question
Title: Bound $T$ asymptotically tight | Recursive trees
> Let $\alpha \in (0, 1),\space l \geq 2$ and $T: \mathbb{N}\rightarrow\mathbb{R}^+$ such that,
> $T(n) = \begin{cases} n^l + T(\alpha n) + T((1-\alpha)n) & : n \> 1 \\1 : n=1 \end{cases}$
> Bound $T$ asymptotically tight.

So I understand that I need to split into cases, the first one is where $\alpha \< \frac{1}{2}$ and $\alpha \geq \frac{1}{2}$.
However, I struggle to bound $T$ tightly at each case (I only know how to bound it from one side).
I'd like to understand the general idea\strategy in situations like this.

# Answer
We can directly approach this problem using the recurrence tree method. Let us now denote $1-\alpha$ as $\beta$ for notational clarity. For any constant $l\ge2$ we have, $\alpha^l+\beta^l \< 1$.

$T(n)$ ----------------------- work = $n^l=n^l(\alpha^l+\beta^l)^0$

/ \

$T(\alpha n)$ $T(\beta n)$ ------------ work = $(\alpha n)^l+(\beta n)^l=n^l(\alpha^l+\beta^l)$

/ \ / \

$T(\alpha^2 n)$ $T(\alpha\beta n)$ $T(\alpha\beta n)$ $T(\beta^2 n)$ --- work = $\small(\alpha^2 n)^l+(\alpha\beta n)^l+(\alpha\beta n)^l+(\beta^2 n)^l=n^l(\alpha^l+\beta^l)^2$

$\vdots$ $\vdots$ $\vdots$ $\vdots$

---

Thus, $T(n) \le \sum\limits\_{i=0}^{\log\_{1/\max(\alpha,\beta)} n}n^l(\alpha^l+\beta^l)^i \le \sum\limits\_{i=0}^{\infty} n^l(\alpha^l+\beta^l)^i = \frac{n^l}{1-(\alpha^l+\beta^l)} = O(n^l)$

Similarly, $T(n) \ge \sum\limits\_{i=0}^{\log\_{1/\min(\alpha,\beta)} n}n^l(\alpha^l+\beta^l)^i \ge n^l = \Omega(n^l)$

Therefore, $T(n) = \Theta(n^l)$

PS: One can derive the tight expressions for both the GP series, but the amsymptotic bounds remain the same, so I have opted for very loose bounds.
> 2 votes

# Answer
Using the Akra-Bazzi method we have that $ \alpha^p + (1-\alpha)^p = 1 $ for $p=1$, and that: $$ \int\_1^n \frac{x^l}{x^{p+1}} \\, \text{d}x = \int\_1^n x^{l-2} \\, \text{d}x= \frac{x^{l-1}}{l-1} \\,\bigg|\_{x=1}^{n} = \Theta(n^{l-1}). $$

Hence: $$ T(n) = \Theta\Big( n^p \cdot \big(1 + \int\_1^n \frac{x^l}{x^{p+1}} \\, \text{d}x ) \Big) = \Theta\big( n \cdot (1 + n^{l-1}) \big) = \Theta(n^l). $$
> 2 votes

---
Tags: asymptotics, runtime-analysis, recursion, lower-bounds, upper-bound
---


# Question
Title: Prove the relation between space complexity and time complexity of the graph search which uses "the explored set"
I was referring to the textbook Artificial Intelligence: A modern approach 3rd by Stuart Russell and Peter Norvig.

what to prove about the general "graph search": (Here I assume "within a factor of b" means multiplier $b$ instead of addition $\pm b$ based on the complexity context. So if time complexity is $O(b^d)$, then space complexity is $O(b^d)\sim O(b^d\cdot b)$ although here $b$ is constant. Here I use $\sim$ to indicate the range instead of the asymptotical relation)

> As for space complexity: for *any kind of graph search*, which stores every expanded node in the **explored set**, the space complexity is always **within a factor of b** of the time complexity

$b$ is defined in 3.4.1 Breadth-first search:

> For these reasons, complexity is expressed in terms of three quantities: **b, the branching factor** or maximum number of successors of any node; d, the depth of the shallowest goal node (i.e., the number of steps along the path from the root); and m, the maximum length of any path in the state space.

---

1. pseudocodes for the general "graph search" offered by the textbook

> As the saying goes, algorithms that forget their history are doomed to repeat it. The way to **avoid exploring redundant paths** is to remember where one has been. To do this, we augment the TREE-SEARCH algorithm with a data structure called the **explored set** (also known as the closed list), which remembers every expanded node. Newly generated nodes that match previously generated nodes—ones in the explored set or the frontier—can be discarded instead of being added to the frontier. The new algorithm, called GRAPH-SEARCH, is shown informally in Figure 3.7. The specific algorithms in this chapter draw on this **general** design.

Here I show the text version to help the search while keeping the image due to the format like bold, italics will help understanding the problem.

```
function TREE-SEARCH(problem) returns a solution, or failure
   initialize the frontier using the initial state of problem
   loop do
      if the frontier is empty then return failure
      choose a leaf node and remove it from the frontier
      if the node contains a goal state then return the corresponding solution
      expand the chosen node, adding the resulting nodes to the frontier
function GRAPH-SEARCH(problem) returns a solution, or failure
   initialize the frontier using the initial state of problem
   initialize the explored set to be empty
   loop do
      if the frontier is empty then return failure
      choose a leaf node and remove it from the frontier
      if the node contains a goal state then return the corresponding solution
      add the node to the explored set
      expand the chosen node, adding the resulting nodes to the frontier
         only if not in the frontier or explored set
Figure 3.7 An informal description of the general tree-search and graph-search algorithms. The parts of GRAPH-SEARCH marked in bold italic are the additions needed to
handle repeated states.

```

The space complexity is caused by the frontier and the explored set.

* The book doesn't pay much attention to the general "graph search"
    > For *the most part*, we describe time and space complexity for **search on a tree**; for a graph, the answer depends on how “redundant” the paths in the state space are.
2. For BFS tree, the textbook says about its time complexity:

> Now suppose that the solution is at *depth d*. In the worst case, it is the *last node* generated at that level. Then the **total number of nodes** generated is $$b + b^2 + b^3 + \cdots + b^d = O(b^d)$$

and about its space complexity:

> For breadth-first graph search in particular, every node generated remains in memory. There will be $O(b^{d−1})$ nodes in the explored set and $O(b^{d})$ nodes in the frontier, so the space complexity is $O(b^{d})$, i.e., it is dominated by the size of the frontier. Switching to a tree search would not save much space, and in a state space with many **redundant paths**, switching could cost a great deal of time

pseudocodes offered by the textbook (The above "$O(b^{d})$ nodes in the frontier" is ensured by tree which won't repeatedly access one same vertex)

```
function BREADTH-FIRST-SEARCH(problem) returns a solution, or failure
   node <-a node with STATE = problem.INITIAL-STATE, PATH-COST = 0
   if problem.GOAL-TEST(node.STATE) then return SOLUTION(node)
   frontier <- a FIFO queue with node as the only element
   explored <- an empty set
   loop do
      if EMPTY?(frontier ) then return failure
      node <- POP(frontier ) /* chooses the shallowest node in frontier */
      add node.STATE to explored
      for each action in problem.ACTIONS(node.STATE) do
         child <- CHILD-NODE(problem, node, action)
         if child.STATE is not in explored or frontier then
            if problem.GOAL-TEST(child.STATE) then return SOLUTION(child)
            frontier <- INSERT(child,frontier )
Figure 3.11 Breadth-first search on a graph

```

* relation between BFS and the general graph search

    > Breadth-first search is an instance of the general graph-search algorithm (Figure 3.7) in which the **shallowest unexpanded node** is chosen for expansion. This is achieved very simply by using a FIFO queue for the frontier.

    I can understand the calculation of BFS tree complexity. But I have the confusion about its interior "general graph-search algorithm".
    * Here both complexities are based on "the **total number of nodes**" for tree with the *same* $O(b^d)$. Then for the general graph, it should have one radial structure similar to the tree but having less children to avoid **repeatedly visiting one same vertex** (this is where **redundant paths** occur).

    > If you are concerned about reaching the goal, there’s **never any reason to keep more than one path** to any given state, because any goal state that is reachable by extending one path is also reachable by extending the other.

    Redundant paths *doesn't increase the number of nodes*, but it may decrease the number of nodes (i.e. frontier nodes may be all have been visited before, so no $O(b^d)$. Then space complexity becomes $O(b^{d-1})$ which is less than time complexity $O(b^d)$) compared with tree which won't repeatedly visiting one same vertex. So its space complexity should be *less* than time complexity instead of "within a factor of b".

    Then it seems that "within a factor of b" may mean that if time complexity is $O(b^d)$, then space complexity is $O(b^d\cdot \frac{1}{b})\sim O(b^d)$ instead of $O(b^d)\sim O(b^d\cdot {b})$

Q:

Does the try in the last bullet point about redundant paths and the relation "a factor of b" right? If not, what is the cause of the relation "a factor of b" in "any kind of graph search which stores every expanded node in the **explored set**"?

**Edited**:

Here I offer the summary of the chat related with the answer inspired by this advice:

chat\_1 (this room has been removed maybe by the moderator due to that it is "not worth retaining which are inactive for 7 days")

1. The reason why thinking "a factor of $b$" as multiplying $b$ is wrong:

> 1. the first paragraph says the worse upper bound by multiplying $b$ is strange, so "a factor of $b$" doesn't mean that.
2. The rest is a bit "sidetracked" because I made one mistake and the edited answer has solved with the problem. The mistake is:

> instead of *thinking of the outer loop as one minimal unit* (this is what I thought before which may be *wrong* after rethoughts)
3. To help future readers understand some edits of the answer as advised by this chat message, I added the summary of one edit referred to in the above chat message here.

> every explored edge is incident to *at least one* node in $N\_x$

This is implied in this comment. Since maybe we may have redundant paths, edge may be incident to 2 *visited* nodes in $N\_x$.

chat\_2:

1. We can derive space complexity $S(n)$ is $\Theta(f(n))$
2. For "proportional", it is not totally same as linear. And for its formula, Kenneth Kho and I both think that $c\_2,c\_4$ can be any number instead of $c\_2,c\_4\>0$ to keep the *symmetric* property of "proportional".

But we shouldn't do strict algebraic calculation here. Based on the symmetric and transitive property implied in the answer which can be proved, "the running time is proportional\* to $k$" implies $k$ is proportional to the running time by the symmetric property and "the space complexity is proportional to $k/b$ or larger" implies "the space complexity is proportional to $f(n)/b$ or larger" by the transitive property.

The above point 2 in chat\_2 have been verified by Kenneth Kho although temporarily not having got the answer poster's verification.

# Answer
> 2 votes
The usage of "within" is a bit confusing, but I think it means the space complexity is never smaller than the time complexity divided by a factor of $b$. The space complexity of an algorithm is always smaller than its running time (since allocating/using $x$ space requires at least $c\cdot x$ time for some constant $c$), so giving an upper bound that is larger than this "trivial" upper bound would not be useful.

To show this, let's take a different perspective on the GRAPH-SEARCH function. Let $N\_x$ be the set of nodes stored by the algorithm: the union of the explored nodes and the frontier. Note that GRAPH-SEARCH does the following repeatedly (until a termination condition is reached):

> Explore an edge $e$ of the graph that is incident to a node in $N\_x$ and has not been explored yet, and add the node on the other end of $e$ to $N\_x$.

($N\_x$ is a set, so the line above does not always increase the size of $N\_x$)

Now suppose the algorithm has explored $k$ edges. On a graph with branching factor $b$, the size of the explored set (i.e. $|N\_x|$) is at least $k/b$. Why? Well, every explored edge is incident to at least one node in $N\_x$ and each of the nodes in $N\_x$ is incident to at most $b$ edges, so $k\leq |N\_x|\cdot b$.

To link this back to the time and space complexity of the algorithm, note that GRAPH-SEARCH does a constant amount of operations in between the exploration of two edges. This means the running time is proportional\* to $k$. Similarly, the space complexity is proportional to $|N\_x|$. The inequality above then means the space complexity is proportional to $k/b$ or larger, and as the running time is proportional to $k$, the space complexity is proportional to $f(n)/b$ or larger, where $f(n)$ denotes the running time of the algorithm.

---

\*: I say "proportional" because asymptotic notation ($\Theta, O, \Omega$ and such) does not technically work here. Feel free skip the explanation below and just interpret it as asymptotic notation except with some nitpicking.

I use the notion of proportional, because

1. We do not know what the exact amount of time of a single operation, or the exact amount of space used, or the relation between these values, other than that we assume (as usual) they are some fixed constant. This means that while $|N\_x|$, $b$, and $k$ are exact and we can prove $|N\_x|\geq k/b$, we cannot derive an exact relation between space and time complexity of the algorithm from this formula.
2. While we can consider the asymptotic behaviour of time- and space complexity, we cannot do the same for $b$, as it is a parameter that is not a function of $n$, so does not have asymptotic behaviour.

By $A$ is "proportional" to $B$, I mean that there are constants $c\_1,c\_2,c\_3,c\_4\>0$ such that (for all values of $A,B$) we have $c\_1\cdot B + c\_2 \leq A \leq c\_3\cdot B + c\_4$. The difference between this notion and asymptotic notation ($\Theta, O, \Omega$ and such) is that $a,b$ do not have to be functions of a variable $n$ that represents the input size, although

---
Tags: algorithm-analysis, runtime-analysis, trees, search-algorithms, graph-traversal
---


title: Big O notation of $O(n/(m-n))$

text:
# Question
Title: Big O notation of $O(n/(m-n))$
I'm new to the complexity theory and have a basic question about the big-O notation that I encountered.

I came across a complexity of $O\big(\frac{n}{m-n}\big)$, where both $n$ and $m$ are independent variables in my algorithm (assuming $m \geq n$). Since I haven't encountered the subtraction of two variables in the denominator before, I'm curious if it can be simplified further, perhaps to $O\big(\frac{n}{m}\big)$ or other nicer forms. I've thought about it for some time, and maybe dividing the fraction by $n$ gives $O\big(\frac{1}{\frac{m}{n}-1}\big) = O\big(\frac{1}{\frac{m}{n}}\big) = O\big(\frac{n}{m}\big)$, but not sure if this is correct.

Additionally, I'm wondering about the whether containing expressions like $m-n$ is common or not. Any help or advice on this would be greatly appreciated :)

# Answer
You cannot make a better conclusion in the general case:

* if $m$ is almost $n$ (not equal to $n$, otherwise $\frac{n}0$ is not defined), then it is $\mathcal{O}(n)$;
* if $m$ is big enough compared to $n$ (meaning $m\geqslant (1 + \varepsilon) n$, with $\varepsilon \> 0$ being a constant), then it is $\mathcal{O}(1)$.

You cannot conclude that it is $\mathcal{O}\left(\frac{n}{m}\right)$ in the general case, because you neglected $1$ in front of $\frac{m}{n}$, but you cannot always do that, for example when $m = n+1$.
> 2 votes

# Answer
n / (m-n) is undefined for m = n. It is equal to +/- n if m = n +/- 1. But for example for m = 0 or m = 2n it is just +/- 1.

You can’t really simplify this. For fixed n, you have a function that goes from 1 to n in a hyperbola, then from -n to -1 and getting still closer to 0, also in a hyperbola. Look out if n, m are dependent of each other or if the result is used in some interesting way.
> 1 votes

---
Tags: complexity-theory, asymptotics, big-o-notation
---


title: PSPACE and Polynomial reduction

text:
# Question
Title: PSPACE and Polynomial reduction
thanks for your help. This is my first question, so I am very sorry for the bad presentation of the question.

I am studying computer science and this is the question I have been asked for the course of Theory of computation and complexity

**Edited question**

1.For every two languages $A,B∈PSPACE$, there is a language $C∈PSPACE$ such that $A≤\_PC$$B≤\_PC$

2.For every two languages $A,B∈PSPACE$ , there is a language $C∈PSPACE$ such that $C≤\_PA$$B≤\_PC$

3.For every two languages $A,B∈PSPACE$, there is a language $C∈PSPACE$ such that $C≤\_PB$$C≤\_PA$

What I have tried is:

1. Correct, we'll take $C∈PSPACE-Complete$ then $C∈PSPACE$ and every $L∈PSPACE$ is $L≤\_PC$
so in particular for languages $A,B∈PSPACE$ there $C≤\_PB$$C≤\_PA$
2. Not correct , we'll take $B∈PSPACE-Complete$ then $B∈PSPACE$ , $A∉PSPACE-Complete$ and $A∈PSPACE$. if $C∈PSPACE$ and $C≤\_PA$$B≤\_PC$, then $C ∈PSPACE-Complete$ and $A ∈PSPACE-Complete$ , Contradiction to the the fact $A∉PSPACE-Complete$!
3. Not correct , If A or B are trivial then there is no C that $C∈PSPACE$ such that $C≤\_PB$$C≤\_PA$

Can you please help me determine which of them are correct and which are not (can be several that are correct), and why?

# Answer
Regarding 1: choose $C = \\{0x \mid x \in A \\} \cup \\{1x \mid x\in B\\}$.

Regarding $2$: $B \le\_P \emptyset \implies B=\emptyset$ however $\\{\varepsilon\\} \le\_P B \implies B \neq \emptyset$.

Regarding $3$: the statement is not well-formed.
> 1 votes

# Answer
1. Correct: you can choose $C$ to be any $\text{PSPACE-complete}$ language.
2. The only known counter-examples to this claim are ones where $C$ or $A$ are trivial, and hence, sadly, a counter-example would be one of these boring edge cases (I encourage you to check what happens if you consider $\emptyset$ or $\Sigma^\*$). It is worth mentioning however that if $C$ and $A$ are assumed to be nontrivial, then the claim essentially suggests that languages in $\text{PSPACE}$ are in a sense dense w.r.t PTIME reductions, and I believe this was the intention behind the claim. Yet, we don't know whether this is true or false as the claim then is equivalent to $\text{P} = \text{PSPACE}$, which is open.
3. The claim does not compile.
> 1 votes

---
Tags: complexity-theory, computability, reductions, space-complexity
---


title: Sorting with element merging

text:
# Question
Title: Sorting with element merging
I'm seeking information about a specific sorting algorithm. This algorithm performs pairwise comparisons and distinguishes between three states:

a \> b: In this case, standard sorting logic proceeds (b precedes a).
a \< b: As usual, a precedes b.
a = b: when elements are considered equal, both a and b are "fused" through some operation, resulting in a single element, denoted as c. This fused element c participates in subsequent comparisons as if it were the original a or b. (the list is left with one less element). The sorting order/size of c is the same as a or b.

My specific questions are:

Is there a recognized name or classification for this type of sorting algorithm?

Are there any known examples or applications of this algorithm in practice?

If not, where should I look. I have interest in something like sorting networks with fusion, or optimizing some known sorting algorithm for this purpose.

My main concern with existing sorting algorithms is their assumption of a constant number of elements. When the logic relies on previously sorted elements being larger/smaller than the compared element, removing elements during the process might invalidate previous comparisons.

# Answer
I think you can modify standard sorting algorithms to handle these goals.

One simple approach: whenever you find two elements $a,b$ with $a=b$, delete one of the two elements.

Another slightly more sophisticated approach: Construct a union-find data structure, where initially each element of the array is in its own set. Whenever you find two elements $a,b$ with $a=b$, call $\text{Union}(a,b)$ to merge those two set into a single set, and delete one of those two (whichever was not chosen as the representative for the union). Whenever you compare two elements, you are effectively comparing two sets by comparing their representatives.

How to delete an element: one approach is to sort them all, without deleting, then at the end remove all duplicates. Another approach have a separate bitmap of booleans, of the same length as the initial array, where each boolean is a flag that indicates whether that element has been deleted. To delete an element, set the flag to true. Periodically (say, once every $n$ steps), scan through the array and remove all items that are flagged for deletion. In some sorting algorithms, the deletion can be combined naturally with the work that's already being done: for instance, in QuickSort, the partition operation can naturally delete all items flagged for deletion, and in MergeSort, the merge operation can skip over all items flagged for deletion.
> 1 votes

---
Tags: algorithms, sorting
---


title: Why the Chomsky Hierarchy?

text:
# Question
Title: Why the Chomsky Hierarchy?
The hierarchy

$$\text{regular languages $\subset$ deterministic context-free languages $\subset$ context-free languages $\subset$ context-sensitive languages $\subset$ recursively enumerable languages}$$

has an 'extra level' with respect to the Chomsky Hierarchy.

***Why is the Chomsky hierarchy taught, as opposed to some other hierarchy?***

# Answer
It is an arbitrary choice, based on a judgement call of the instructor about which levels of the hierarchy are most useful to focus on.

I think one could make a good argument for focusing on the even simpler hierarchy

$$\text{regular languages} \subset \text{context-free languages} \subset \text{recursively enumerable languages},$$

as most automata theory courses focus primarily on those three categories. Many of them devote considerably less time to context-sensitive languages and to deterministic context-free languages.

Generally, regular languages are considered valuable to study because they form the foundation of lexing (for compilers), for pattern-matching (for everyone who uses regexes), and for finite-state automata; and because they have an elegant theory that is is perhaps easiest to learn.

Generally, context-sensitive languages are considered valuable to study because they form the foundation for parsing.

Generally, recursively enumerable languages are considered valuable to study because they form the foundation for a study of decidability and computability.
> 1 votes

---
Tags: formal-languages, automata, chomsky-hierarchy
---


# Question
Title: What is the Chomsky level of pattern matching?
Pattern matching in programming languages as for example in Racket is some kind of parsing. Which level in the Chomsky hierarchy does this parsing technique have? Is it type-3 like regular expressions or type-2 or even lower?

# Answer
> 1 votes
It depends on what types of patterns are supported. If it is only classical regular expressions, as in theoretical computer science, it is the regular languages. If it is Perl-compatible regular expressions (PCRE), then it is the context-sensitive languages; see Which languages do Perl-compatible regular expressions recognize?.

See also When is a regexp not a Regular Expression? and Expressiveness of modern regular expressions and How much more powerful are regexes in modern programming languages compared to regular expressions from the theory of computation? and What can be proven regarding the differences in power between unary ECMAScript regex functions and primitive recursive functions?.

---
Tags: chomsky-hierarchy
---


# Question
Title: Not understanding example of a Pushdown Automata
The first example of a (nondeterministic) pushdown automata given in Linz' *An Introduction to Formal Languages and Automata* is the following:

**Example 7.2:** consider

* $Q = \\{q\_0,q\_1,q\_2,q\_3\\}$,
* $\Sigma = \\{a,b\\}$,
* $\Gamma = \\{0,1\\}$,
* $z = 0$,
* $F = \\{q\_3\\}$,

with $q\_0$ the initial state and

* $\delta (q\_0,a,0) = \\{(q\_1,10),(q\_3,\lambda)\\}$,
* $\delta (q\_0,\lambda,0) = \\{(q\_3,\lambda)\\}$,
* $\delta (q\_1,a,1) = \\{(q\_1,11)\\}$,
* $\delta (q\_1,b,1) = \\{(q\_2,\lambda)\\}$,
* $\delta (q\_2,b,1) = \\{(q\_2,\lambda)\\}$,
* $\delta (q\_2,\lambda,0) = \\{(q\_3,\lambda)\\}$.

The author states

> The crucial transitions are $$δ (q\_1, a, 1) = \\{(q\_1, 11)\\},$$ which adds a $1$ to the stack when an $a$ is read, and $$δ (q\_2, b, 1) = \\{(q\_2, λ)\\},$$ which removes a $1$ when a $b$ is encountered. These two steps count the number of $a$’s and match that count against the number of $b$’s.

---

***How does the automata count the number of $a$'s and $b$'s?***

What *exactly* does the transition $δ (q\_1, a, 1) = \\{(q\_1, 11)\\}$ do to the stack? If the transition is crucial in counting the $a$'s, then I'd imagine it 'enqueues' another $1$ into the stack e.g. the stack goes from $110...$ to $1110...$

However, I fail to see how the formal definition of the pushdown automata would keep track of the stack, as we are only given the stack alphabet $\Gamma$ and the stack starting symbol $z$, so the information regarding what the stack contains at each point in time is not 'saved'.

# Answer
the stack is kept track of by a so called "configuration". Imagine, that the configuration represents a complete description of your machine at a point in time. The transition function only needs to tell you, how the configuration might *change* during the computation.

For a PDA $A = (Q, \Sigma, \Gamma, \delta, q\_0, z, F)$, a config needs to keep track of the current state, remaining input, and stack. So a config is a 3-tuple $$(q, u, v)$$ where $q \in Q$ is a state, $u \in \Sigma^\*$ is the remaining input and $v \in \Gamma^\*$ is the stack. Now $$\delta(q, a, v) \ni (q', v')$$ can be read as "if in state $q$ you read $a$ and your stack top is $v$, you might change to state $q'$ by popping $v$ and pushing $v'$". Using our configs we can write $$(q, au, vs) \vdash (q', u, v's) \iff \delta(q, a, v) \ni (q', v')$$ where $C \vdash C'$ represents one step in the computation, the machine changes from $C$ to $C'$ in one step. So a computation for $aaabbb$ in your example machine might look something like this:

* $(q\_0, aaabbb, 0) \vdash (q\_1, aabbb, 10)$
* $(q\_1, aabbb, 10) \vdash (q\_1, abbb, 110)$
* $(q\_1, abbb, 110) \vdash (q\_1, bbb, 1110)$
* $(q\_1, bbb, 1110) \vdash (q\_2, bb, 110)$
* $(q\_2, bb, 110) \vdash (q\_2, b, 10)$
* $(q\_2, b, 10) \vdash (q\_2, \lambda, 0)$
* $(q\_2, \lambda, 0) \vdash (q\_3, \lambda, \lambda)$

We say that the PDA accepts $w \in \Sigma^\*$ iff $(q\_0, w, z) \vdash^\* (q\_f, \lambda, \lambda)$ and $q\_f \in F$, so your PDA accepts $aaabbb$.

Hope that helps :\]
> 1 votes

---
Tags: automata, pushdown-automata
---


# Question
Title: Proof of correctness for Binary Search algorithm to find length of array for unknown length
For the algorithm provided in answer to this question, how would I go about proving the correctness of the algorithm?

The referenced question is:

“You are given an array $A$ of length $n$. Each value is $1$. However, you do not know what the value of $n$ is. You are allowed to access an element $i$ of the array by calling $A\[i\]$. If $i \< n$, this will return $1$, and if $i \geq n$, this will return a message saying that the location does not exist (you can think of this as an error message, but it will not crash your program). Describe an $O(\log(n))$ algorithm to determine the value of $n$.”

Here is the algorithm given to solve the problem:

```
def length(L):
    lo = 0
    hi = 1

    while 1:
        hi *= 2

        try:
            L[hi]
        except IndexError:
            break

    while lo < hi:
        mid = (lo + hi) // 2

        try:
            L[mid]
            lo = mid + 1
        except IndexError:
            hi = mid

    return hi

```

I tried proving it by strong induction on the length of the array, where `hi` would be equal to the length (i.e., at the end of the algorithm, hi would be set to the last out of bounds element and would therefore be the length of the array), but the proof didn’t really make sense

# Answer
> 2 votes
The length of the array is $n\_{min} \le n \le n\_{max}$. Initially all you know is that $n\_{min} = 0$ and $n\_{max} = \inf$. Every step of the algorithm gives you more information. If $n\_{min} = n\_{max}$ then you know n. You need to examine the steps of the algorithm and show that it ends with that condition.

PS. You should think about setting lo = hi whenever accessing hi succeeds.

---
Tags: algorithms, correctness-proof, divide-and-conquer, binary-search
---


# Question
Title: Regular expression for all strings not containing $aba$
This is my first post here. We are currently studying regular expressions, and I have been tasked to write a regular expression for the language of all words which do not contain the substring $aba$, for the alphabet $\Sigma=\\{a,b\\}$.

We were firstly tasked to write a regular expression for all words which *do* contain the substring $aba$, and I came up with:

$$(a+b)^\*aba(a+b)^\*$$

However, I don't know how to write the second one because I can't think of a way to formalize something which *cannot* be included in the regex.

# Answer
A word doesn't contain $aba$ if after every $ab$, the word either terminates or contains $b$. Imagine that you start reading your word from left to right. Denoting by $\newcommand{\eos}{\\#}\eos$ the "end of string" symbol, one of the following must be a prefix of your string: $$ \eos \\ a\eos,aa\eos,aaa\eos,\ldots \\ ab\eos,aab\eos,aaab\eos,\ldots \\ abb,aabb,aaabb,\ldots \\ b $$ Furthermore, each of these prefixes $p$ not ending with $\eos$ satisfies the following: a word $w$ doesn't contain $aba$ iff $pw$ doesn't contain $aba$. This leads to the following unambiguous regular expression: $$ (a^+bb + b)^\*(\epsilon + a^+ + a^+b) $$ You can simplify it further if you're fine with ambiguous regular expressions; I leave such simplifications for you to ponder, if you are so inclined.
> 2 votes

# Answer
Think of all the possible combinations you can make which are not aba:

* Whenever we get "ab" we must either end the string or add a "b" by force: **a+bb**
* If we are starting from **b** then we can append as many a's as we want at the end: **b+a*bb**
* Joining both together: **( a+bb + b+a*bb )\* a\*b\***
* The a\* at the end is for the edge case where we have all a's or when we have ab.
> 1 votes

# Answer
Such a word contains atleast 2 consecutive $b$'s whenever a $b$ occurs in the middle of the word, or the word ends with a single $b$. We thus replace the language of all words made of some number of $a$s or $b$s, represented by $(a^\ast + b^\ast)^\ast$, with the language of words made of $a$s or atleast two $b$'s, which is $$(a^\ast+ bb b^\ast)^\ast$$ However, we can optionally have a single $b$ at the end or the beginning, so we add that as $$ (\varepsilon+b) \cdot (a^\ast+ bb b^\ast)^\ast \cdot (\varepsilon+b)$$
> 1 votes

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


title: The cost of an algorithm

text:
# Question
Title: The cost of an algorithm
Please tell me what is the correct formula for calculating the cost of an algorithm? I used this: number of calculated functions + 4 * number of calculated function gradients + 8 * number of calculated Hessian matrices of the function. I use this formula to calculate the cost of Newton's method of finding the minimum of a function.

Update: I'm multiplying the number of gradients by 4 since it's a vector consisting of the derivative of a function with respect to coordinates (I'm considering a plane, meaning (x,y) coordinates). I multiply the number of Hessian matrices by 8, since for it we need second derivatives.

For a better understanding of my question, I will attach part of the code.

```
struct hesse
{
    double a, b, c, d;
    void init(point A)
    {
        count_h += 1;
        a = kvadrdxx(A);
        d = kvadrdyy(A);
        b = kvadrdxy(A);
        c = kvadrdxy(A);
    }
    void inverse()
    {
        double det = (a * d - b * c);
        if (det != 0)
        {
            a = a / det;
            b = b / det;
            c = c / det;
            d = d / det;
            std::swap(a, d);
            c = -c;
            b = -b;
        }
    }
    void pol()
    {
        double nu = 0;
        while (a <= 0 || (a * d - b * c) <= 0)
        {
            nu = nu + 0.1;
            a = a + nu;
            d = d + nu;
        }
    }
    point operator*(point A)
    {
        point p(0, 0);
        p.x = a * A.x + b * A.y;
        p.y = c * A.x + d * A.y;
        return p;
    }
};

point newton(point& X0, double e)
{
    point pk(0, 0);
    point X = X0;
    point gr1(kvadrdx(X0), kvadrdy(X0));
    double norm_antigr = my_norm(gr1);
    hesse h;
    while (norm_antigr > e)
    {
        count_it += 1;
        out.push_back(X);
        h.init(X);
        h.pol();
        h.inverse();
        pk = (h * gr1) * (-1);
        X = X + pk;
        point gr(kvadrdx(X), kvadrdy(X));
        gr1 = gr;
        norm_antigr = my_norm(gr1);
    }
    out.push_back(X);
    return X;
}

```

# Answer
> 1 votes
To calculate the cost of an algorithm, measure its execution time in seconds. Then you either take the cost of a new computer, calculate for how many seconds it runs your algorithm during its life, adding cost for the space where it lives and electricity. Or you ask a cloud service provider what it costs to rent their computers per hour, and calculate the cost from there.

If by “cost” you mean something other than dollars, pound, euros, yen or yuan, please clarify.

---
Tags: optimization
---


# Question
Title: "Consecutive statements" in Static control Part(SCoP)
**Context:**

I was reading a research paper related to polyhedral representation(citation given in last). Got confused while trying to understand the notation by implementing them with example code.

**Paper Citation:**

> Bastoul, Cédric & Cohen, Albert & Girbal, Sylvain & Sharma, Saurabh & Temam, Olivier. (2003). Putting Polyhedral Loop Transformations to Work. LNCS. 2958. 209-225. 10.1007/978-3-540-24644-2\_14.

**Problem Description:**

*From the paper; Page no: 6, Point: 3, 2nd paragraph*

> Let us now introduce the representation of a SCoP and its elementary transformations. A static control part within the syntax tree is a pair `( S , i_gp )`, where S is the set of consecutive statements in their polyhedral representation and `i_gp` is the vector of global parameters of the SCoP. Vector `i_gp` is constant for the SCoP but statically unknown; yet its value is known at runtime, when entering the SCoP. d\_gp = dim(i\_gp ) denotes the number of global parameters.

`( S , i_gp ):` They specifically mentioned S is the set of **consecutive** statements.

**Example case:**

In my example code below, I have included **three statements: S1, S2, and S3**. Additionally, there are **two parameters, N and M**, and one constant, C.

```
for (int i = 0; i < N; i++) {
    A[i] = B[i] + C;       // Statement 1
    D[i] = A[i] * E[i];    // Statement 2
    if (i < M) {
       F[i] = D[i] - G[i]; // Statement 3
    }
}

```

**So my doubts are:**

1. **Are S1 and S2, which are consecutive and right after one another, the only members of set `S`?**
2. If the answer to question 1 is NO, meaning all statements (S1, S2, S3) belong to the set S, then what is meant by **'consecutive'** in this context?
3. In the code below, **are all statements S1, S2, S3, and S4 part of the set `S`?** If not, please could you let me know which statements are member of `S`?

```
for (int i = 0; i < N; i++) {
    A[i] = B[i] + C;       // Statement 1 in the outer loop
    for (int j = 0; j < M; j++) {
        D[i][j] = A[i] * E[j]; // Statement 2 in the inner loop
        if (j % 2 == 0) {
            F[i][j] = D[i][j] + C; // Statement 3 in the inner loop, conditional
        }
    }

    G[i] = A[i] - C;       // Statement 4 in the outer loop
}

```

# Answer
> 0 votes
According to Section 2.1 in the paper provided:

> Loops are normalized and split in two categories: loops from 0 to some bound expression with an integer stride, called `do` loops; other kinds of loops, referred to as `while` loops. A *static control part* (SCoP) is a maximal set of consecutive statements without `while` loops, where loop bounds and conditionals may only depend on invariants within this set of statements. These invariants include symbolic constants, formal function parameters and surrounding loop counters: they are called the *global parameters* of the SCoP, as well as any invariant appearing in some array subscript within the SCoP. A static control part is called *rich* when it holds at least one non-empty loop; *rich* SCoPs are the natural candidates for polyhedral loop transformations. We will only consider *rich* SCoPs in the following.

We conclude that in the first code snippet below, S1, S2, and S3 are part of the same non-*rich* SCoP, since the SCoP do not hold at least one non-empty loop.

```
for (int i = 0; i < N; i++) {
    A[i] = B[i] + C;       // Statement 1
    D[i] = A[i] * E[i];    // Statement 2
    if (i < M) {
       F[i] = D[i] - G[i]; // Statement 3
    }
}

```

We conclude that in the second code snippet below, S1, S2, S3, and S4 are part of the same *rich* SCoP, since the SCoP holds at least one non-empty loop, a `for` inner loop which is considered of type `do` instead of `while` for our purposes.

```
for (int i = 0; i < N; i++) {
    A[i] = B[i] + C;       // Statement 1 in the outer loop
    for (int j = 0; j < M; j++) {
        D[i][j] = A[i] * E[j]; // Statement 2 in the inner loop
        if (j % 2 == 0) {
            F[i][j] = D[i][j] + C; // Statement 3 in the inner loop, conditional
        }
    }
    G[i] = A[i] - C;       // Statement 4 in the outer loop
}

```

---
Tags: optimization, sets, loops, loop-invariants
---


# Question
Title: Mitchell FPL 3.6.2 (Show that equation does not hold in initial algebra)
Mitchell specifies a set data type: ie, an algebraic specification for set. He then asks to prove that the equation

*union s s' = union s' s \[s, s': set\]*

does not hold in the initial algebra. He suggests that we use the following result: two terms are provably equal iff they reduce to a common term. Here are the relevant reduction steps:

*union empty s -\> s*

*union (insert y s) s' -\> insert y (union s s')*

attempt: we can destruct on s, s' ( a previous result shows that all sets are constructed from the empty set and the insert constructor, which takes a nat and adds it to a set to produce a new set). In the case that both s, s' are nonempty, we apply the relevant reduction steps and obtain

*insert y (union P s')* from the LHS

*insert x (union Q s)* from the RHS

Further, Mitchell also proves that all sets (according to his specification) are finite. So after a finite number of times this process terminates for both LHS and RHS. Then, we see that the resulting terms are both in normal form, but not syntactically identifical, hence by hypothesis, not provably equal from the specification.

Qa: for destructing, I have not treated the cases where s, s' are both empty, in which case, they reach a common term. It seems intuitive that they must reach a common term in all four cases in order for me to say that LHS, RHS both reduce to a common term but this is not what the theorem says, which perhaps suggests that I shouldn't have destructed? But I don't see any other way to go about this.

Qb: supposing this works, we have shown that the specification does not prove the given equation. Mitchell does say that initial algebras satisfy the least number of possible equations (they are somewhat like free groups). He also says intial algebra satisfies M= N iff every ground instance of M=N is provable from the specification, where a ground instance is just a substition of all variables in the term to a closed/variable free term. Perhaps I can just stubstitue x with say "3" and y with "4" and then conclude? Or how would I go about this?

# Answer
> 3 votes
If all you need to show is that `union a b = union b a` is not provable, where `a` and `b` are variables, it suffices to find one particular instance where the equation does not hold, so how about:

```
union (insert 42 empty) (insert 13 empty) = union (insert 13 empty) (insert 42 empty)

```

The left-hand side rewrites to `insert 42 (insert 13 empty)` and the right-hand side to `insert 13 (insert 42 empty)`. These are reduced and not equal so we are done.

---
Tags: semantics, operational-semantics
---


title: Efficient streaming sort

text:
# Question
Title: Efficient streaming sort
Consider following task:

> we have an input of N+1 lines, where first line contains N ≤ 150000 - number of items, and then we have N lines, each one contains one item, which is a tuple (number id, number m), id ≤ 10^7, m ≤ 100.
> We have to perform a stable sort on this sequence and print the result.
>
> Sample input:
>
> ```
> 8
> 1 2
> 16 3
> 11 2
> 20 3
> 3 5
> 26 4
> 7 1
> 22 4
>
> ```
>
> Sample output:
>
> ```
> 3 5
> 26 4
> 22 4
> 16 3
> 20 3
> 1 2
> 11 2
> 7 1
>
> ```

My current naive implementation was just allocate vector of size N, fill it, and then run any stable sort algorithm on it. In following example (all examples are written in Rust) I'm just adding row number as part of the sorting key and then perform quick sort:

```
use std::io::{self, BufRead};
use std::cmp::Ordering;

fn main() {
    let stdin = io::stdin();
    let mut lines = stdin.lock().lines();
    let n: usize = lines.next().unwrap().unwrap().parse().unwrap();
    let mut tuples = Vec::with_capacity(n);

    for i in 0..n {
        let line = lines.next().unwrap().unwrap();
        let mut line = line.split_whitespace();
        let id: u32 = line.next().unwrap().parse().unwrap();
        let m: u8 = line.next().unwrap().parse().unwrap();
        tuples.push((id, m, i));
    }

    tuples.sort_unstable_by(|a, b| {
        let cmp = b.1.cmp(&a.1);
        match cmp {
            Ordering::Equal => a.2.cmp(&b.2),
            other => other
        }
    });

    for (id, m, ..) in tuples {
       println!("{} {}", id, m);
    }
}

```

My second implementation used `BTreeSet`, but it wasn't a success, and it have taken much more time than first naive one.

My third idea was using idea from insertion sort to keep array sorted from the scratch. When we get yet another element from the stream we just seek the position where it should be placed and then insert in there. When all elements are processed we already have a final array. Here is a sample implementation:

```
use std::io::{self, BufRead};
use std::cmp::Ordering;

struct TeamResult {
    id: u32,
    m: u8,
}

impl TeamResult {
    pub fn new(id: u32, m: u8) -> Self {
        Self {
            id,
            m
        }
    }
}

impl Ord for TeamResult {
    fn cmp(&self, other: &Self) -> Ordering {
        other.m.cmp(&self.m)
    }
}

impl PartialOrd for TeamResult {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(&other))
    }
}

impl PartialEq for TeamResult {
    fn eq(&self, other: &Self) -> bool {
        self.m.eq(&other.m)
    }
}

impl Eq for TeamResult { }

fn main() {
    let stdin = io::stdin();
    let mut lines = stdin.lock().lines();
    let n: usize = lines.next().unwrap().unwrap().parse().unwrap();
    let mut tuples = Vec::with_capacity(n);

    for i in 0..n {
        let line = lines.next().unwrap().unwrap();
        let mut line = line.split_whitespace();
        let id: u32 = line.next().unwrap().parse().unwrap();
        let m: u8 = line.next().unwrap().parse().unwrap();

        let item_to_insert = TeamResult::new(id, m);
        let index_to_insert = search_pos(&tuples[0..i], &item_to_insert);
        tuples.insert(index_to_insert, item_to_insert);
    }

    for x in tuples {
        println!("{} {}", x.id, x.m);
    }
}

fn search_pos<T: Ord>(a: &[T], value: &T) -> usize {
    let len = a.len();

    if len == 0 {
        return 0;
    }

    if value < &a[0] {
        return 0;
    }

    if value > &a[len - 1] {
        return len;
    }

    let mut lo = 0;
    let mut hi = len - 1;

    while lo < hi {
        let mid = (hi + lo) / 2;

        match value.cmp(&a[mid]) {
            Ordering::Less => hi = mid - 1,
            Ordering::Greater => lo = mid + 1,
            Ordering::Equal => {
                lo = mid;
                break;
            }
        };
    }

    while lo <= hi && value >= &a[lo] {
        lo += 1
    }

    lo
}

```

However, it was even slower than a BTree one and it timed out.

I wonder what are theoretical and practical optimal implementations?
I mean I think that in theory BTree should be faster on this task, but in practice simple array sort beats it.

# Answer
> 1 votes
First, it should not be surprising that if you want to sort some numbers, a dedicated sorting algorithm is faster than using a data structure that is capable of sorting *and also doing other things* (finding given elements efficiently, inserting new elements efficiently, removing elements efficiently). (That said, you should find that the difference is "only" a constant factor, at least for sufficiently large inputs.)

Since the maximum m value is very small, you can just use a slight variant of counting sort, which takes $O(n+m)$ time and memory. Declare an array `freq[]` of size 101, then in a first pass through all the numbers, increment the corresponding element of `freq` for each number: this is to decide the bucket sizes. Then allocate a fresh length-$n$ buffer `output[]`, and make a pass through the 101 elements of `freq`, changing each element to the total so far: after doing this, `freq[i]` conceptually points to one past the *end* position of a block within `output[]` that is large enough to hold all input numbers having key equal to i. Now make a final pass *in reverse order* through the n input elements, writing each to the next free space available within its block and decrementing the position accordingly. (Literally `for (int i = n - 1; i >= 0; --i) output[--freq[input[i].m] = input[i].id;` in C++.)

There are no truly "streaming" sorting algorithms, since the very last number read could be smaller than all the others, meaning you have to either buffer them, or save partial results to disk.

# Answer
> 1 votes
Here is an algorithm to consider https://www.ncbi.nlm.nih.gov/pmc/articles/PMC8982863/

---
Tags: algorithms, algorithm-analysis, sorting, mathematical-programming, streaming-algorithm
---


title: Splitting summations?

text:
# Question
Title: Splitting summations?
From CLRS *Introduction to Algorithms*, Appendix A, page 1152. They discuss a method called "Splitting Summations", where they split the summation and bound each term separately. For example,

$$\begin{align\*} \sum\_{k=1}^{n} k &= \sum\_{k=1}^{n/2} k + \sum\_{k=n/2 + 1}^{n} k\\ &\geq \sum\_{k=1}^{n/2} 0 + \sum\_{k=n/2 + 1}^{n} (n/2)\\ &= (n/2)^2\\ &= \Omega(n^2)\\,\end{align\*}$$

I get step 1, that makes sense, but I didn't understand step 2 where they have replaced $k$ with $0$ in one part and $k$ with $n/2$ in the other. Why did they do this?

Thanks!

# Answer
> 3 votes
In the first sum, you know that k ≥ 0. In the second sum, you know k ≥ n/2. Therefore, adding k in the first sum is ≥ adding 0 in the first sum, and adding k in the second sum is ≥ adding n/2 in the second sum.

You can adapt this for example to show that the sum of $k^5$ for 1 ≤ k ≤ n is $O(n^6)$: You have n/2 terms each at least $n^5/32$, for a total of $n^6/64 = O(n^6)$. Or a lower bound for n!, where you have a product including n/2 terms each larger than n/2, so n! \> $(n/2)^{n/2}$.

# Answer
> 0 votes
Here you want to obtain a lower bound (big-omega) for your sum expression. The idea is to carefully split the summation into two parts so that it leads to your desired result, which is $\Omega(n)$ in this case. Here, they have split the sum into two halves. For the first half, they have replaced all entries with 0, which is smaller than all of them. Similarly, for the second half, they have replaced all with $n/2$, which is smaller than all integers between $n/2+1$ and $n$. Thus, the first sum vanishes while the second sum simplifies to $(n/2)^2$, and we get the required result.

Now to answer the 'why' of your question: Simply because it works! One can, in fact, use any constant $c \> 1$ and get the same result.

$\sum\limits\_{k=1}^{n} k = \sum\limits\_{k=1}^{n-\lceil n/c\rceil} k + \sum\limits\_{n-\lfloor n/c\rfloor + 1}^{n} k \ge \sum\limits\_{k=1}^{n-\lceil n/c\rceil} 0 + \sum\limits\_{n-\lceil n/c\rceil + 1}^{n} \lceil n/c\rceil = (\lceil n/c\rceil)^2 \ge (n/c)^2 = \Omega(n^2)$

---
Tags: asymptotics
---