# Question
Title: Given computable function, what are conditions for computability of inverse function?
If $f:\mathbb{N}\rightarrow\mathbb{N}$ is computable and has an inverse, under what conditions is $f^{-1}$ also computable? I couldn't find that in a textbook, and googling gets some vague suggestions about bijective, but I couldn't find a clearly stated theorem to that effect. Offhand, bijective seems sufficient but not necessary, e.g., $f(n)=2n$ isn't surjective but is computably invertible (for a total function inverse, use lifted domain $\mathbb{N}\_\perp$ and map odd numbers back to $\perp$). In addition to an answer, a reference to a theorem/proof would be great, or just the name of a relevant theorem so I can successfully google it.

This question came to mind regarding the following thought (which I also wasn't able to find in a textbook or google anything about). The distinction between $f$ computable and $f^{-1}$ not, versus both computable, seems kind of analogous to an r.e. versus recursive distinction. Can that be expressed rigorously?

For example, consider $f:E\rightarrow E$, with $f\in D=\[E\rightarrow E\]$ the (Scott- or Lawson-continuous) function space domain of some domain $E$. Let $K\_D$ be $D$'s compact elements, $\downarrow f=\lbrace g\in K\_D\mid g\sqsubseteq f\rbrace$, whereby $f=\sqcup\downarrow f$, all in the usual way. Then $f$ is computable if an enumeration of $\downarrow f$ is r.e. Similarly, $f^{-1}$ is computable if an enumeration of $\downarrow f^{-1}$ is r.e. So if both are computable, meaning both enumerations r.e., then that seems (to me at least) kind of analogous to recursive.

Of course, it's not quite the same thing as recursive, since if $\mathbb{N}\_f\subseteq\mathbb{N}$ is an enumeration of $\downarrow f$, and similarly for $\mathbb{N}\_{f^{-1}}$, then $\mathbb{N}\_{f^{-1}}\neq\mathbb{N}\setminus\mathbb{N}\_f$ (at least I don't suppose so). But there seems to be some kind of analogous idea trying to express itself. So how could you formulate that kind of thing rigorously? Among the first steps, I'd think you'd want to express $\mathbb{N}\_{f^{-1}}$ in terms of $\mathbb{N}\_f$, but I'm not seeing how to go about setting that up (any suggestion how to do that?).

So, is this idea also well-known and discussed? A textbook or google reference (or google-able search term) would be great. Thanks.

# Answer
> 10 votes
Let us say that a computable function $f$ is invertible if there is another computable function $g$ that on input $y$ either finds $x$ such that $f(x) = y$ or returns $\bot$ when $y$ has no preimage.

For this definition, one can show that a computable function $f$ is invertible if and only if its range is decidable, that is, we can decide whether a given input has a preimage under $f$.

# Answer
> 1 votes
Also note that if the function is injective and not necessarily surjective, then the inverse will be partial computable

---
Tags: computability
---


# Question
Title: Can we prove the greedy algorithm archives 1.5-approximation for the Minimal Dominating Set Problem?
The following approximation algorithm for the *Minimal Dominating Set Problem* is said by a fellow student to be a 1.5-approximation:

1. Start with empty set $S$
2. As long as not all vertices are covered:
    * Add a vertex that is not in $S$ with the most uncovered neighbors including itself.
    * Mark it and all its neighbors as covered
3. return $S$

I can't find a proof for the approximation ratio however and my own attempts to prove it have failed so far since I lack the right approach to proof something like this.

# Answer
> 3 votes
This claim is incorrect. The diagram below shows a small counterexample:

Consider two different runs of the greedy algorithm that break ties in different ways:

1. Run 1 chooses the 6 red vertices in order from darkest to lightest, then chooses the yellow vertex.
2. Run 2 chooses the 3 green vertices in order from darkest to lightest, then chooses the yellow vertex.

(Check for yourself that each run is a valid possible execution of the algorithm.) The first run chooses a solution of size 7; the second, an (optimal) solution of size 4. $7/4 = 1.75 \> 1.5$, meaning the greedy algorithm is capable of producing a solution that violates the claimed bound.

---
Tags: graphs, approximation, greedy-algorithms
---


# Question
Title: What is a contracting grammar (in opposition to a non-contracting grammar)?
In the Chomsky hierarchy what is corresponding to a contracting grammar?

I can find references to non-contracting grammars (which can be transformed into context-sensitive grammars accordingly to what Wikipedia is saying: https://en.wikipedia.org/wiki/Noncontracting\_grammar), but I don't know what would correspond to a contracting grammar

My guess would be unrestricted grammars (Type-0 in the Chomsky hierarchy) but I would like confirmation.

# Answer
You are right. Unrestricted grammars (type-0) have productions $\alpha\to\beta$ with $\alpha$ containing at least one nonterminal.

For noncontracting (or monotonic) the condition $|\alpha|\le |\beta|$ is added.

I would not use the term "contracting" for what you try to express, though. That suggests that strings become shorter during derivations. Which is hard if one starts with a single symbol axiom. "not necessarily contracting" perhaps?

A similar problem occurs with automata terminology. A nondeterministic finite state automaton may very well be deterministic.
> 1 votes

---
Tags: formal-grammars, chomsky-hierarchy
---


# Question
Title: What does actually reasonable mean when we say "reasonable model of computation"?
I have seen in many text when the author says "reasonable model of computation". What does it really mean?

# Answer
It doesn't have a precise meaning. What an author considers "reasonable" largely depends on the context. It is usually meant to exclude certain pathological cases.
> 4 votes

# Answer
In computational complexity theory, Peter van Emde Boas formulated the *Invariance Thesis* saying that:

> 'Reasonable’ models of computation can simulate each other within a polynomially bounded overhead in time and a constant-factor overhead in space.

See eg Cambridge Encyclopedia of Philosophy.

Reading this thesis as a definition, one can call a *reasonable model of computation* a model of computation that is equipped with a time complexity measure which is polynomially equivalent to counting steps on a Turing machine (ignoring space complexity for the moment).

I have used the term in this sense in my own work here.
> 3 votes

---
Tags: turing-machines
---


# Question
Title: Is maximal independent set on maximal planar graphs still NP-complete?
We know that finding the size of the maximal independent set of a planar graph is NP-complete. I'm curious about whether it remains NP-complete for maximal planar graphs, i.e., the graphs in which adding any edge will destroy its planarity, or equivalently, all edges of whose faces are bounded by three edges.

I've asked the AI Chat robot of DeepAI (https://deepai.org/chat), and it says the problem is in P. This is the algorithm it provided:

> There is a simple polynomial-time algorithm to find the maximal independent set in a maximal planar graph. Here are the steps of the algorithm:
>
> 1. Create a planar embedding of the maximal planar graph if not already given.
> 2. Identify any vertices of degree two (called degree-2 vertices).
> 3. Remove any degree-2 vertices from the graph and add them to the independent set.
> 4. Repeat steps 2-3 until no degree-2 vertices remain.
> 5. Pick any vertex of degree at most three (called a low-degree vertex) and remove it from the graph. Add it to the independent set.
> 6. Update the degrees of the neighbors of the removed vertex.
> 7. Repeat steps 5-6 until no low-degree vertices remain.
> 8. Identify any isolated vertices and add them to the independent set.
> 9. Output the set of vertices collected during the algorithm as the maximal independent set.
>
> The algorithm works because of the special structure of maximal planar graphs. In step 3, removing a degree-2 vertex does not affect the planarity of the graph, as the two neighboring vertices can be connected directly. In step 5, removing a low-degree vertex can also be done without affecting the planarity of the graph because the remaining neighbors can be connected to maintain planarity. Finally, step 8 ensures that any isolated vertices are automatically included in the independent set, as they cannot be adjacent to any other vertex in the graph. The algorithm runs in O(n) time, making it efficient for large graphs.

However, I'm skeptical about this algorithm. Two low-degree vertices might be adjacent, so step 5 may put two adjacent vertices in the independent set. I asked it who proposed this algorithm, and it says Robert E. Tarjan proposed this algorithm in the paper "A class of algorithms which traverse a planar graph from both ends", but I can't find this paper. Now I'm very confused about whether on earth this problem can be solved in polynomial time, and I have no clue about how to sort it out by myself. Can you help me?

**Edit 2023/3/14**: I've studied a proof of NP-completeness of maximal independent set on 2-connected cubic planar graphs. The proof is given in the paper "Face covers and the genus problem for apex graphs" (https://users.fmf.uni-lj.si/mohar/Papers/ApexGenus.pdf, page 10-11). The author proposed a reduction from planar 3-SAT. Suppose there is a 3-SAT formula of $n$ variables (denoted $v\_1,v\_2,\cdots,v\_n$) and $m$ clauses (denoted $c\_1,c\_2,\cdots,c\_m$). The *incidence graph* of the formula consists of $n+m$ vertices, in which each variable and clause has a corresponding vertex. An edge $(v\_i,c\_j)$ is in the graph if and only if $v\_i$ or $\neg v\_i$ appears in $c\_j$. It is proved that when the incidence graph is planar, 3-SAT remains NP-complete. Then the paper introduced a variation of the incidence graph: each clause vertex is replaced by a triangle that is consists of three variables in the clause, and each variable vertex is replaced by a cycle of length $2k$, where $k$ is the number of times the variable occurring in any clause. The cycle consists of vertices indicating the sign (positive or negative) of the variable in the corresponding clauses. If a vertex $x\_i$ occurs in $k$ clauses $c\_1,c\_2,\cdots,c\_k$, then the cycle of $x\_i$ consists of $2k$ vertices: $c\_1^{\mathrm{pos}},c\_1^{\mathrm{neg}},c\_2^{\mathrm{pos}},c\_2^{\mathrm{neg}},\cdots,c\_k^{\mathrm{pos}},c\_k^{\mathrm{neg}}$. Now we construct the edges. If variable $x\_i$ occurs in clause $c\_j$ without being negated, then add an edge between the corresponding variable vertex in the clause triangle and $c\_j^{\mathrm{neg}}$ in the vertex cycle. If $x\_i$ is negated, then then add an edge between the vertex in the clause triangle and $c\_j^{\mathrm{pos}}$. The resulting graph is 2-connected, cubic and planar (we can see the planarity because every vertex in the original incidence graph is "inflated" to a triangle or a cycle).

Here is an example. Suppose we have the following formula $$\begin{aligned} F&=(x\_1\lor \neg x\_2\lor x\_3)\quad&(c\_1)\\ &\land(\neg x\_1\lor x\_3\lor \neg x\_4)\quad&(c\_2)\\ &\land(x\_2\lor \neg x\_3\lor x\_4)\quad&(c\_3) \end{aligned}$$ Then its graph is as follows:

Obviously, for a $m$-clause formula, its graph contains $6m+3m=9m$ vertices. To form an independent set, we can pick at most one vertex from a triangle and $k$ vertices from a cycle. If in the cycle of $x\_i$, we pick $c\_j^{\mathrm{pos}}$ ($c\_j^{\mathrm{neg}}$) in the independet set, then $x\_i$ is assigned true (false). When precisely $k$ verices are picked in an $2k$-length cycle, the assignment of the corresponding variable is well-defined, i.e., all true or all false in the entire formula. When a vertex in a triangle is picked, it means this clause is satisfied. An edge between (say) $x\_1$ in the triangle of clause $c\_1$ and $c\_1^{\mathrm{neg}}$ in the cycle of $x\_1$ indicates that $x\_1=0$ doesn't satisfy the clause (because the two vertices can't be selected simultaneously). Hence, when precisely $4m$ vertices are selected in the independent set, i.e. half are selected in cycles and one in each triangle, the formula is satisfied. So, deciding the satisfiability of the 3-CNF formula is now converted to deciding whether there is an independent set of size $4m$ in the graph.

However, I'm not able to derive a maximal planar graph from the incidence graph. I think there must be some relationship in the graph indicating that a variable can't be true and false simultaneously. Let's say there are two variables, $x\_1$ and $x\_2$, and four vertices, $x\_1,\neg x\_1,x\_2,\neg x\_2$. There must be edges $(x\_1,\neg x\_1)$ and $(x\_2,\neg x\_2)$ to make sure that $x\_1$ and $\neg x\_1$ (as well as $x\_2$ and $\neg x\_2$) don't occur simultaneously in the independent set. To make the graph maximally planar, the graph must be isomorphic to $K\_4$; but the size of the maximal independent set in $K\_4$ is $1$, while we require the size to be $2$ to assign each variable a value. Generally speaking, there seems to be too many constraints in a maximal planar graph to reduce a planar 3-SAT instance. I also searched for a polynomial-time algorithm for maximal independent set in maximal planar graphs, but found none.

Furthermore, I found an interesting fact at https://graphclasses.org/classes/gc\_981.html (thanks to @pcpthm for proving the link). Maixmal independent set on every "minimal superclass" of maximal planar graphs listed in the page turns out to be NP-complete, while for every maximal subclass it can be solved in polynomial time. So it seems that maximal planar graph is at a somewhat "intermediate" position.

# Answer
> 3 votes
This is more of a comment, but I want to append an image. The following graph is maximal planar and every node has degree 4, thus the proposed algorithm does not work. The maximal independent set of this graph has 2 nodes.

As I said, this is more of a comment / not an answer.

---
Tags: complexity-theory, graphs, np-complete, independent-sets
---


# Question
Title: How do you calculate the amount of iterations the loop "for (i = 1; i < n^3; i += n)"
How do you calculate the amount of iterations the following loop will have in terms of n?:

```
for (i = 1; i < n^3; i += n) {
    }

```

I've gotten as far as: $$i=(x-1)n+1\ for\ current\ iteration=x$$ $$Total\ iterations=x\ when\ n(x-1)+1\geq n^3\>n(x-2)+1$$

# Answer
> 0 votes
**Hint:**

$$i=1,1+n,1+2n,1+3n,\cdots1+(n^2-1)n,1+n^2n\cdots$$

---
Tags: runtime-analysis
---


# Question
Title: 3-Dimensional Matching $\leq$ $_{p}$ subset sum Explanation
excuse me, could someone explain to me the reduction of the problem 3-dimensional matching to subset sum? I was reading Jon Kleinberg's design algorithms book and when I came across this reduction I didn't understand how it really works:

"So consider an instance of 3-Dimensional Matching specified by sets $X,Y,Z$, each of size n, and a set of m triples $T$ $\subseteq$ $X x Y x Z $. A common way to represent sets is via bit-vector:Each entry in the vector corresponds to a different element, and it holds a 1 if and only if the set contains that element. We adopt this type of approach for representing each triple t = $(x\_i,y\_j,z\_k)$ $\in$ $T$: we construct a number $w\_t$ with $3n$ digits that has a 1 in position $i,n+j$ and $2n+k$, and a 0 in all other positions. In other words, for some base $d\>1$, $w\_t = d^{i-1} +d^{n+j-1}+d^{2n+k-1}$."

To begin with, it is not very clear to me what $X,Y,Z$ sets are or what they represent, as I understand they represent certain digits, but I cannot understand how these inputs work or what they really represent.

In the case of the elements of $T$, according to what I see, they are the elements of the "original" set of Subset Sum represented with vectors.

Now if we wanted to know if in the set A = {1,2,4,10,200}, there is a subset of A whose sum is 16, how could we use the 3dm to represent this example, who would be $X,Y,Z$ and how would it be? represents each number in its vector form?

I'm really stuck with this part. I would really appreciate it if you could help me. Thank you for your consideration.

P.S: I would also greatly appreciate recommendations for other books or resources where the examples of reductions are explained in a little more detail.

# Answer
When you want to prove a reduction is true (such as this from 3-Dimensional Matching to Subset Sum), what you want to show is that you can take any input for 3-Dimensional Matching and turn it into an input for Subset Sum - not the other way around, as you seem to want.

So, to explain (as it seemed as though you were somewhat uncertain as to how the 3-Dimensional Matching problem is defined): It is an extension of the matching problem in bipartite graphs, only that the graph now is tripartite and each edge consists of three vertices instead of two (i.e. it's a hypergraph). It is known that 3-Dimensional Matching is NP-complete, even with these restrictions:

* Each color class (i.e. $X,Y,Z$) consists of exactly $n$ vertices
* You are tasked to find a matching consisting of $n$ edges (i.e. a perfect matching)
* Every vertex has degree 3 (which implies that the number of edges is exactly $3n$)

As such, you can transform an instance of 3-Dimensional Matching into an instance of Subset Sum by associating each edge with a $3n$-digit number that has a $1$ in the three positions corresponding to the vertices making up the edge, and a 0 everywhere else. You then ask for a subset of the numbers that add up to the number $11\ldots 11$ ($3n$ 1's).

NB: You need to work in base at least 3, if you work in binary it and add together 3 numbers that all have a $1$ in the same position, you naturally get a $1$ in that position. We want to make sure that the subset adding up to $11\ldots 11$ actually corresponds to a perfect 3-D matching.
> 1 votes

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


# Question
Title: Scheduling and Resource Management in OS
The below text is taken from the book : Operating Systems: Internals and Design Principles by William Stallings, 8th edition, page 68.

> Scheduling and Resource Management
>
> A key responsibility of the OS is to manage the various resources available to it (main memory space, I/O devices, processors) and to schedule their use by the various active processes. Any resource allocation and scheduling policy must consider three factors:
>
> * Fairness: Typically, we would like all processes that are competing for the use of a particular resource to be given approximately equal and fair access to that resource. This is especially so for jobs of the same class, that is, jobs of similar demands.
> * Differential responsiveness: On the other hand, the OS may need to discriminate among different classes of jobs with different service requirements. The OS should attempt to make allocation and scheduling decisions to meet the total set of requirements. The OS should also make these decisions dynamically. For example, if a process is waiting for the use of an I/O device, the OS may wish to schedule that process for execution as soon as possible to free up the device for later demands from other processes.
> * Efficiency: The OS should attempt to maximize throughput, minimize response time, and, in the case of time sharing, accommodate as many users as possible. These criteria conflict; finding the right balance for a particular situation is an ongoing problem for OS research.

I cant understand the meaning of Differential Responsiveness, can somebody please explain it to me ?

# Answer
Not every job that a computer has to do has equal importance or urgency.

An example is different I/O devices which work at different speeds. A network interface, for example, generally runs at a much higher bandwidth than a keyboard or mouse, so servicing the network interface would typically be a higher priority task than servicing a keyboard. But, on the other hand, servicing a real-time clock might be even higher priority than those, so that the computer keeps good time.

This is even more critical in real-time systems, where for some computations, a late answer is a wrong answer. An obvious example is software that controls a physical device, such as in a vehicle control system; a late response could mean catastrophe.
> 2 votes

---
Tags: operating-systems
---


# Question
Title: Finite state machine that accepts every word with at least one c, or different value of parity of the counts of a's and c's
few weeks ago I had an exam in automata theory course and I've been asked to write the following non-deterministic finite automata

> Write a NFA which accepts the following language - the language contains all the words (above `{a, b, c}`) with at least 1 appearance of the letter c, **or** the parity of the count of the letter a is different from the parity of the letter c.

and I answered with the following state machine:

which was totally incorrect, and I'm trying to understand why. I do know there's a possibility to solve that question with 2 states machine, but I'd like to stick with the current solution. I do understand that the arrow from q2 to itself should contain c also, but does it makes the machine completely inaccurate? how would you rank that kind of solution from 1 to 20?

# Answer
Observe that the language can alternatively defined as the set of strings where the count of $a$ is odd or there is at least one $c$. If we have any $c$ in the string, the parity of $a$ doesn't matter – hence the parity of $a$ matters only when there are no $c$ in the string so the parity of $c$ is even. You can construct a three-state automaton fairly close to your current one:

* $q\_0$ is the initial state: even number of $a$ and no $c$ has been read. Non-accepting.
* $q\_1$ is the state where an odd number of $a$ has been read, but no $c$. Accepting.
* $q\_2$ is the state where a $c$ has been read. Accepting.

Since all strings containing any $c$ must be accepted, reading $c$ from any state should result in $q\_2$. We are going to accept the string anyway, so we can stop tracking the $a$ parity, and any symbol in $q\_2$ loops back to $q\_2$. Apart from that, tracking the parity of $a$ is done like you do it between $q\_0$ and $q\_1$.

I don't believe a two-state DFA or even NFA exists for this language, as it must have at least two accepting states: one that cannot be exited (for strings that contain any $c$) and one that can be exited (for strings that contain an odd number of $a$, no $c$). However, there are clearly non-accepted strings too, so a non-accepted state is also needed.
> 2 votes

# Answer
You can solve the second clause with two states with meanings "same parity" vs. "different parities", both $a$ and $c$ switching between both.

But I don't see how to avoid two additional states ("odd $a$, no $c$" and "even $a$, no $c$") to handle the "at least one $c$" clause.
> 0 votes

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


title: Acyclic boolean circuit (DAG)

text:
# Question
Title: Acyclic boolean circuit (DAG)
If a function `f` has a `while loop` or `for loop`, can I compile this function into an `acyclic boolean circuit` that ensures that each gate is topologically ordered, i.e. there is no feedback? If so, how exactly is that done, by loop expansion? And if compiling the function as a `cyclic boolean circuit` is allowed, does it simplify the circuit structure?

I would appreciate your answer. Thanks!

# Answer
> 0 votes
If your circuit can contain registers (or some other form of memory or state) (e.g., sequential logic), then yes, you can. You store the value of all variables in the registers, and you build a circuit that computes the next value of those variables after one iteration of the loop, and then the circuit runs over and over again.

If your circuit cannot contain registers or state, but only logic gates (i.e., combinational logic), then no, you cannot.

---
Tags: circuits, boolean-complexity
---


title: Find the largest caterpillar subtree

text:
# Question
Title: Find the largest caterpillar subtree
I have a problem to solve, but I am having some issues with it...

Find an algorithm with time complexity O(V+E), where V and E stand for vertices and edges respectively. The algorithm searches a tree graph for a subgraph. The subgraph is supposed to be the so called caterpillar graph, i.e. a path with "legs" or "hair" like the one in the picture (the "legs" or "hair" must be of length 1 from the base path).

What's more, the algorithm has to find a caterpillar subgraph with the highest number of vertices. Could anyone please help me? Also sorry for my bad English.

# Answer
I will show how to find the size of the largest caterpillar subtree, finding a caterpillar of that size can be done by keeping track of the decisions made in the formulas, similar to dynamic programming.

Select a vertex $r$ as the root of the tree. Let $C(v)$ be the size of the largest caterpillar in the subtree of $v$ such that the stalk of the caterpillar can be extended to include $v$. (in other words: the largest caterpillar such that $v$ is adjacent to an endpoint of the stalk in this caterpillar.) Because it needs to be possible to extend the stalk, there is at most one subtree of $v$ where the caterpillar for $C(v)$ can have more than one vertex. This gives the following recursive formula for $C(v)$, which we define for all vertices in tree except the root $r$: $$C(v)= \begin{cases} \max\_{c\in \mathrm{children}(v)} C(c) + |\mathrm{children}(v)| - 1& \text{if $v$ has at least one child} \\ 1 & \text{if $v$ is a leaf}\end{cases}.$$

The value $C(v)$ can be computed for all vertices in $O(V+E)$ time by traversing the tree from leaf to root. Of course, now we have only considered caterpillars where $v$ is adjacent to the endpoint of a stalk. Given $C(v)$, we can compute the size of the largest caterpillar such that $v$ lies on the stalk and the stalk lies in the subtree of $v$: $$C'(v)=\begin{cases} C(v)&\text{if $v$ has at most one child} \\ \max\_{c,c'\in \mathrm{children}(v), c\neq c'} C(c)+C(c') + \mathrm{degree}(v)-2& \text{otherwise}\end{cases} .$$ Now the maximum value of $C'(v)$ gives the number of
> 1 votes

---
Tags: algorithms, graphs, trees, search-algorithms, graph-traversal
---


# Question
Title: Finding 2 points that are k'th closest and their distance is minimal among such points with Chebyshev distance
Let $p\_1,p\_2 \dots p\_n$ be $n$ points in 2D such that $p\_i= ( x\_i,y\_i) $

Let $d(p\_i,p\_j)= \max (|x\_i-x\_j|,|y\_i-y\_j|)$, or better known as Chebyshev distance. Find a point $p\_i$ such that the distance to it's kth closest point is minimal among all $i$ in $\mathcal{O} ( n\log ^2 n) $. Edit: $ 1 \le k \le n$

I tried calculating all possible distances which gives me $\binom{n}{2}$ choices which means it's not the way.

Next I tried sorting all $x$ values and $ y$ values separately, then the kth closest is either 1 of the 2k closest x or 1 of the $2k$ y closest.

Those are 4 sorted sub arrays and we can merge them in $ O(n)$ to find the kth closest of each element, but then finding the minimum for $n$ elements would again result in $O(n^2)$.

# Answer
With a 2-D orthogonal range counting query data structure, you can calculate how many points have a distance less than a specified value from a given point. Here, the query range is a square centered at the source point.

By performing binary searching on the distance, you can find the $k$-th closest distance from a point. Compute that for every point and return the smallest result.

By using a Wavelet tree, the 2-D orthogonal counting query takes $\Theta(\log n)$ time after preprocessing the points to map coordinates to the range $\[1, n\]$. A binary search needs $O(\log k)$ queries. Therefore, the overall problem can be solved in $O(n \log^2 n)$ time.
> 0 votes

---
Tags: computational-geometry
---


# Question
Title: Applying FP/Categorical terminology to non-FP languages
In my continuing effort to finally wrap my brain around advanced FP/categorical concepts, I've been reading dozens of articles and tutorials; what I have concluded is that:

1) Category Theory and Software Engineering use the same words in different ways; or, I think, Software Engineering uses category theory terms far too loosely. (Functor, Monad, Applicative, and so forth.)

2) The operations around functors/monads are like pizza toppings: Every single library/tutorial has its own terminology that is borrowed somewhat incorrectly from every other, and no one can agree on anything.

3) Using Haskell to explain these concepts is useless to anyone who doesn't already know Haskell, because Haskell is built to make implementing them so trivial that it doesn't translate back out to languages that don't.

To that end, I want to lay out what I THINK the full set of terminology is in a non-Haskell-ish language (a pseudocode that resembles Javascript, sort of), and the numerous variations I've seen, and invoke Cunningham's Law to ask people to correct me when (not if) I demonstrate I am still not grokking it.

I will update the post with corrections where possible, but if you're coming to this later please be sure to read the comments, too.

---

If you want to translate your basic category of types into a category with "more contextually useful stuff" (which could be logging, null/optional handling, IO awareness, etc.), there are a couple of things you need, in practice.

First, you need an operation that lifts a value from your type to your enhanced type; category theory canonically calls this `unit`. Haskell calls it `return`. In a non-typeclass language, it's usually implemented as the constructor of an class that represents "type plus context"; Eg, `Maybe::constructor(val)`. I have also seen `pack`, `lift`, and `of` as static method names here that wrap the constructor. I've even seen `join`, which seems confusing with `join` as an alias of `bind` (below).

Second, you need a way to lift a unary function that takes a type T and returns the same type T to one that takes an enhanced version of T and returns an enhanced version of T. Haskell calls this `fmap`. Non-functional languages variously call it `map`, `apply`, `then` (if dealing with promises) or other things and assume that it will *also* be invoked when passed. So you end up with no simple lifting function, but a "lift and use" operation.

The combination of `unit` and `fmap` constitute a *functor*, because they're lifting a type and function to the enhanced type category.

You also need a way to convert the enhanced value back to unenhanced; In Haskell this is just referencing the value. In Rust it's called `unwrap`. Other names I've seen include `flatten`, `value`, `get`, etc. Sometimes there are multiple of these, such as Java's `orElse` and `orElseGet`, but those are convenience utilities not part of the core definition. Other non-core operations that vary depending on the type of enhancement may be `isNothing` (Maybe), `logs` (for a Writer), or some IO related stuff.

Third, you need a way to convert a unary function that takes a type T and already returns an enhanced T, and allow it to take an enhanced T as its parameter. This is a different operation from `fmap`. Haskell and others call this `bind`. In less powerful languages I've seen this also called `flatmap`, `map`, `join` and `chain`. (`flatmap` because it first calls `flatten` to extract the value, and then calls `fmap`, then rewraps it into an Enhanced T.)

In canonical Javascript, `then` works with *either* a T-\>T or a T-\>Enhanced function, effectively combining `fmap` and `bind` into a single function named `then`. Whether this is wise or not is a subject of some debate.

A function from T to Enhanced is (half of) a functor. `bind` allows you to combine those together in a way that follows the monoid laws. Thus, `bind` is a monad (a monoid for (endo)functors). Strictly speaking, from a category theory point of view only `bind` is a monad. In Software Engineering, though, it's quite common to refer to the whole set of things as a monad, since they're usually implemented as methods. `bind` also gets called `join` or `chain` in other languages. That is:

```
class Enhanced {

    private value;

    // These two are technically a functor.
    func constructor(value) { ... }

    static func fmap(function from T to T) returns function from Enhanced<T> to Enhanced<T>

    // Doesn't have a name in Haskell, but object-y languages always have it:
    public func value() returns the value itself

    // Also called `apply` in some versions.
    public func map(function from T to T) returns the result of applying the function to value

    // Strictly speaking, this is the monad.
    // Also called `join` or `chain`.
    public function bind(function from T to Enhanced<T>) returns the result of applying the function to value, but wrapped in Enhanced

}
// Colloquially, programmers call the whole thing a "monad", aka a monad pattern.

```

Which is equivalent to the following in a more type-robust functional language (Haskell, F#, etc.):

* `Maybe value` ; `Either value`; or various other type constructors, equivalent of unit or the object constructor.
* `fmap`, which can be a free-standing function because of more robust typing
* `bind`, but it is so common it gets turned into an operator \>== and the type system figures out which bind to use, since there's several.

Fourth, you need a way to lift non-unary functions. Haskell auto-curries everywhere so... it just sorta falls out naturally. In other languages it's generally a separate function (or static method), `liftA2` for a 2-argument version, `liftA3` for a 3-argument version, etc. That function is equivalent of `fmap` (or is it `bind`? Not sure here?) but for a binary and trinary function, respectively.

I... don't quite grok how you would then incorporate a `liftA2`ed function into an enahnced type, other than manually currying it.

Which then means if you want to have, as an example, a zero-division-safe arithmetic, you'd do:

```
func add(x, $y) => x + y;
func sub(x, $y) => x - y;
func mult(x, $y) => x * y;

func div(x, y) => {
    if (y == 0) return new Maybe();
    return Maybe(x / y);
};

func liftA2(fn) {
    // I am definitely wrong here.  Please advise.
    return func (a, b) => Maybe(a).map(fn).bind(b);
}

maybeAdd = liftA2(add);
maybeSub = liftA2(sub);
maybeMult = liftA2(mult);

```

At this point I run out, because I feel I'm missing a step along the way here. I suspect something related to Applicatives, because I haven't fully wrapped my head around those. (I haven't gotten to that chapter in Bartzoz's book yet.)

So that's where I am. Can anyone advise on where I'm going off the tracks and what the next piece of railroad tie is?

# Answer
> 1 votes
Let me comment on your description. To make notation more definite, I will talk about types `T` and `E(T)`, where `E` stands for your "enhanced context". For example, `E` could be `List` or `Promise` or something else.

> The combination of unit and fmap constitute a functor

Usually `unit` is not required for a functor, just `fmap`. If you have `unit` then it is called a "pointed functor".

> You also need a way to convert the enhanced value back to unenhanced

If you have a function `E(T) -> T`, the functor `E` is called "co-pointed". But this is not always possible. An example is `List`: you cannot always extract values from a list because a list could be empty. So, `List` is a pointed but not a co-pointed functor. You cannot have a function `List(T) -> T` that always returns a result for arbitrary types `T`.

Most often, it makes sense to extract values into another "enhanced context", i.e., into another functor. For example, you try to extract a value but if it is not possible you generate an error.

> flatmap because it first calls flatten to extract the value, and then calls fmap

It's the other way around: it first calls `fmap` and then `flatten`. The function `flatten` does not actually extract values from a functor, it has the type signature `E(E(T)) -> E(T)`.

About this:

```
func liftA2(fn) {
  // I am definitely wrong here.  Please advise.
  return func (a, b) => Maybe(a).map(fn).bind(b);
}

```

This looks almost correct. The operation `liftA2` needs to transform a function of type `(A, B) -> C` into a function of type `(E(A), E(B)) -> E(C)`. You can indeed implement this operation using `bind` and `fmap`. I'm not sure what programming language you are using where you had functions like `func add(x, $y) => x + y`, so I can't tell you how to write the code correctly in that language. In Haskell this would look like:

```
liftA2 :: (a -> b -> c) -> E a -> E b -> E c
liftA2 f ea eb = bind (\k -> fmap k eb) (fmap f ea)

```

But this is probably too terse to be clear.

"Applicative functor" is such `E` that has `liftA2` (but does not necessarily have to be a monad).

So, generally you are on the right track. You are listing the various properties of functors. There are about four or five useful kinds of functors that you will eventually discover.

One way of proceeding systematically is to begin with the "map/filter/reduce" style of programming. First, you find that you can write iterative code without explicit loops, just using `map`, `filter`, `fold`, `zip`, and `bind`. Then you study the properties of those functions: what laws do they need to satisfy in order to be useful for programming, and what data structures can support those functions. You will find, for example, that `List` has all those methods but the simple type `E(a) = Maybe (a, a)` does not have `bind` that could satisfy the laws.

Category theory is not of very much help at this point, other than providing language to talk about "functors" and "natural transformations".

# Answer
> 0 votes
> Can anyone advise on where I'm going off the tracks
>
> You also need a way to convert the enhanced value back to unenhanced

No, generally speaking you don't have such conversion. For example, in JS you cannot get a value out of a Promise, you have to resolve the Promise `.then(f)`. Same goes for Haskell, you cannot (without unsafe stuff) get a value `a` out of a Monad say `IO a`, since there is no monad interface function like: `m a -> a`. However, you can use `>>=` (bind) `m a -> (a -> m b) -> m b` to chain computations on such values, by providing a function `a -> m b`.

---
Tags: programming-languages, functional-programming, category-theory
---


# Question
Title: Prove optimality of greedy strategy for fewest number of stops
Here is the problem. Suppose you have to drive from Eindhoven to the south of France. Your start and destination are fixed and the route is fixed as well. You start with a full petrol tank, but since the distance is quite long you will need to fill up your tank several times. There are $n$ petrol stations along the way, and your goal is to stop at as few petrol stations as possible.

A natural greedy approach would be to make your first stop at the furthest petrol station, $s$, that is reachable from Eindhoven, then fill up your tank, drive again to the furthest reachable petrol station, and so on, until you can reach your destination. Prove or disprove that this is a good greedy choice. In other words, prove or disprove that there is an optimal solution for this problem that includes a stop at petrol station $s$.

Here is my solution. I prove the greedy strategy leads to an optimal solution. Let $OPT$ be the optimum solution, the set of all stations stopped at whose cardinality is minimal, and let $s$ be the first furthest station reachable from Eindhoven. I consider two cases. The first being that $s \in OPT$. In this case we are done. Now I consider the case where $s \notin OPT$. Then, some other station $s'$ was stopped at, sooner than $s$, since $s$ is the furthest station from Eindhoven. Now, stopping at an earlier station does not decrease the minimum number of stops required and so replacing $s'$ with $s$ leads to another solution $OPT^\* = \\{ OPT \setminus s' \\} \cup \\{ s \\}$ which is no worse, i.e.:

$size(OPT^\*) \leq size(OPT)$

Implying that the optimal solution $OPT$ can potentially be improved by using the greedy choice, contradicting the fact that $OPT$ is optimal and so $OPT$ must contain the greedy choice, i.e. $s \in OPT$. This concludes the proof. A proof could have also been obtained using the "greedy stays ahead" method, but I preferred to use the "cut and paste" reasoning.

Now, what could possible alternative approaches be to solving this problem? For example, a solution using the greedy stays ahead approach would be welcome. Also, if there are any errors with the reasoning it would be appreciated if these are pointed out :).

This problem comes from an algorithms course: https://www.win.tue.nl/~kbuchin/teaching/2IL15/

The problem set itself can be found at: https://www.win.tue.nl/~kbuchin/teaching/2IL15/Homework/hw-A1.pdf

The author of the problem set is Kevin Buchin.

# Answer
> 3 votes
As D.W.'s answer points out, there are a few places where the "proof" in the question is not satisfactory. It is not that straightforward to "justify that stopping at an earlier station does not decrease the minimum number of stops" rigorously, even though it might look obvious.

---

A clearer and easier approach is to prove no other solution can get (strictly) ahead of the greedy algorithm.

Assume the destination, the south of France is indeed reachable and at least one stop is needed. (Otherwise, the case is trivial.)

Suppose the greedy itinerary stops at (petrol) station $s\_1,s\_2,\cdots, s\_k$, reaching $s\_{k+1}$, the destination. Suppose another itinerary stops at station $t\_1$, $t\_2$, $\cdots$.

Let us show that $t\_i$ is well-defined and $t\_i$ is not closer to the destination than $s\_i$ for all $i$, $1\le i\le k$.

Let us do induction on $i$.

* The base case $i=1$ is true obviously.
* Suppose the case $i$ is true, i.e., $t\_i$ is as least as far away from the destination as $s\_i$, where $1\le i\<k$. Since we can only reach as far as $s\_{i+1}$ starting from $s\_i$ with a full tank as dicataed by the greedy nature, the other itinerary can reach at most as far as $s\_{i+1}$ starting from $t\_i$. That means the other itinerary must make another stop, i.e. $t\_{i+1}$. Moreover, $t\_{i+1}$ is not closer to the destination than $s\_{i+1}$. Our induction is complete.

In particular, letting $i$ be $k$, we know the other itinerary must stop at $k$ stations at least.

# Answer
> 3 votes
I don't consider this to be a sufficient proof. There are a number of problems with this proof:

> Let OPT be the optimum solution

No, you can't make such a definition, as there could be multiple optimal solutions. You might mean to let OPT be any optimum solution.

> In this case we are done.

You need to explain why you are done.

> Now, stopping at an earlier station does not decrease the minimum number of stops required

This needs to be justified.

> contradicting the fact that OPT is optimal

No, there is not necessarily any contradiction. You could have $size(OPT^\*) = size(OPT)$, and both OPT and OPT\* could be optimal.

# Answer
> 2 votes
The usual method is: You prove that there is an optimal solution. (If you want to minimise X and find that X = 1 + epsilon for some epsilon, there might be no optimal solution, or a value that you want to maximise might be arbitrarily large.) Usually there is an optimal solution.

Then you assume that you have any optimal solution O, you have a greedy solution G, and if O ≠ G then you show how you can change O to get a different solution O', which is more similar to G, and still optimal. And then you have to show that repeatedly finding optimal solutions closer and closer to the greedy solution will eventually find a greedy solution.

In your case you want to minimise the number of tank stops, which is a non-negative integer. Such a problem always has an optimal solution with 0, 1, 2, 3, ... tank stops.

Start with an optimal solution O and the greedy solution G. If they are the same then G is optimal. Otherwise there is a smallest i such that the i-th stop of the optimal solution $O\_i$ is different from the i-th stop of the greedy solution $G\_i$. $O\_i$ is not later than $G\_i$ because the greedy solution and the optimal solution started at $O\_{i-1} = G\_{i-1}$ and the greedy solution couldn't go further than $G\_i$, so neither can the optimal solution. If $O\_i$ is before $G\_i$ then we change the optimal solution to go to $G\_i$ instead. It is possible because the greedy version did, and you are in the same state, so you can proceed your optimal solution. The first difference has been moved, so eventually you will get O = I.

When this doesn't work: If the amount of fuel you can pack into your tank is different per station. If your greedy strategy encounters a gas station that only allows you 20 litres of fuel, then it is quite possible that stopping one station earlier and filling your tank is better. In this case modifying the optimal solution to make it more similar to the greedy one fails.

# Answer
> -2 votes
Here’s a slight change to make “greedy” fail: all the gas stations only take banknotes of 10 euro or higher paid in advance, and only allow to pay for gas that fits in your tank.

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


# Question
Title: DFA that accepts strings whose 10th symbol from the right end is 1
Problem is "Constructing a DFA accepting set of all strings whose 10th symbol from the right end is $1$ over $\\{0,1\\}$"

The NFA is easy

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

but DFA has to have minimum $2^{10}$ states. I've tried to see the pattern by constructing 2nd and 3rd symbol from the right.

I mean, when it is the 2nd from the right we need $4$ states checking the remainders, and it has $2$ final states; when it is $3$, we check for the remainders of $8$ and it has $4$ final states.

Therefore, we can observe that 10th symbol one will have $2^{10}$ states checking the remainders of $2^{10}$ and it will have $2^{9}$ final states. Besides that, I cannot see a way to visualize it graphically as it is asked in the question. Anyone brighter?

# Answer
> 6 votes
> I cannot see a way to visualize it graphically as it is asked in the question.

It is not necessary nor required of you to visualize or draw a wanted dfa. The exercise only asks you to "construct a DFA accepting ...". The meaning of constructing a DFA is specifying/describing/defining the 5-tuple, $(Q,\Sigma, \delta, q\_0,F)$ in the definition of a DFA. Or whatever definition that is used in your course. If you can draw a graph of the DFA, that is great. However, you don't have to unless you are asked specifically to include a graph.

Let us describe a desired DFA as follows.

* The states $Q=\\{q\_0, q\_1, \cdots, q\_{1023}\\}$.
* The alphabet $\Sigma=\\{0, 1\\}$.
* The transition $\delta(q\_i, \sigma)=q\_{(i\\%512\<\<1) + \sigma}$ for any state $q\_i$ and any $\sigma\in\Sigma$. Or, what is equivalent, $$\delta(q\_{(d\_9d\_8d\_7d\_6d\_5d\_4d\_3d\_2d\_1d\_0)\_2},\sigma)=q\_{(d\_8d\_7d\_6d\_5d\_4d\_3d\_2d\_1d\_0\sigma)\_2}$$ where $(d\_9d\_8d\_7d\_6d\_5d\_4d\_3d\_2d\_1d\_0)\_2$ is the binary representation of the subscript, with some leading $0$s possibly.
* The initial state is $q\_0$.
* The accept states are $q\_{512}, q\_{513}, \cdots, q\_{1023}$. Put it in another way, a state $q\_i$ is an accept state iff the binary representation of $i$ has $10$ digits, with the most significant digit being $1$.

It is straightforward to check the DFA constructed above accepts all strings whose 10th symbol from the right end is $1$ and no other strings.

By the way, the DFA above that has $2^{10}$ states is the minimum DFA wanted, as you have noted. It is a nice example that indicates that the minimum DFA that is equivalent to an $n$-state NFA may require $2^n$ states.

# Answer
> 8 votes
It is easy to prove that you need at least $2^{10}$ states. Suppose you need fewer states. Then after feeding $2^{10}$ different sequences of length ten, there exist two sequences ending in the same state. But these two sequences differ at some point, so if you feed the same further symbols (possibly none) to the two sequences, the states will remain equal, but the symbols will differ when becoming the last tenth symbol. So it's wrong, and you need at least $2^{10}$ states. No one can be smarter. Pigeonhole principle.

# Answer
> 5 votes
Those state diagrams can be constructed inductively, so it seems. Their structure is (in another context) known as De Bruijn graph.

I sincerely hope you are not actually forced to draw some thousand states though.

Picture below is part of a diagram from the wikipedia page mentioned above (David Eppstein, public domain).

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


# Question
Title: Greater than or equal to operation (32-bit ALU)
I'm trying to construct a **greater than or equal to** operation by adding some logic gates or building blocks (i.e. multiplexor and decoder) to my current 32-bit ALU

I'm not quite sure how to do this and nothing on google comes up for this operation from what I could tell.

ALU Design:

**Question:** How do I add a greater than or equal to operation to the current ALU? Also can you explain the changes you make so I can understand what's going on, thank you!

# Answer
David Richerby's comment is right, in that the typical way it's "done" is to perform a subtraction and examine the "carry out" bit.

But I think it's worth stepping back for a moment and making a general comment about modern ALU design which may help you.

Thanks to Moore's Law, the number of transistors (and hence gates) required to implement a functional unit is not a serious limitation. Moreover, integer ALUs are not even close to the most power-hungry components of a modern CPU. So the main thing that needs to be conserved in a modern integer ALU design is propagation delay.

For essentially-single-cycle operations such as logic and add/subtract arithmetic, many modern integer ALUs are designed so that all potential operations are performed in parallel, and the "correct" one is selected with a multiplexer. This has the advantage that some of the multiplexer logic can be performed in parallel with the ALU operation, which again saves on propagation delay.

The same technique is used in floating point, incidentally. When performing an IEEE-754 floating point operation, the typical final step is that the result needs to be rounded correctly, using some logic which involves testing the answer and the FPU's current rounding mode. Many "real" FPUs essentially duplicate circuitry for some of the operations, performing three versions in parallel ("round up", "round down", and "pass through") and using a final multiplexer stage to decide which one to keep.

Of course, in real CPUs, ALUs typically aren't designed at the gate level these days, they are designed at the transistor level. So, for example, the multiplexer stage is probably achieved with high-impedance outputs followed by an amplifier stage to clean up the signal.
> 4 votes

# Answer
32bits might be a stretch for Manchester Magnitude Comparator chain, but a repeater or three won't add much delay.

At each slice, let A vs B select 00 EQ, 01 LT, 10 GT, 11 EQ. Let output EQn+1 propagate to the next slice's pair of EQ inputs.

Setup any magnitude comparison \< = \> using controls LT EQo GT. Or use EQ as A-B's Borrow, B-A's Reverse Borrow, or Carry (with B XORverted).

Combinatorial MUX will ripple, so use transmission gates. Switches can be prefixed to pass a series current that solves many (eight or more) slices in one go. I prefer 74CBT3253. 6nS switch, 250pS propagate, 5 ohms.
> 0 votes

---
Tags: computer-architecture, logic
---


# Question
Title: Subquadratic multiplication of polynomials in the max-plus/tropical semiring
Is there an algorithm to multiply two polynomials with coefficients in the max-plus semiring $(\mathbb{Z}\cup\\{-\infty\\}, \max, +)$ which is faster than the trivial one? I'm interested in the coefficients of the product, so I can't ignore the differences between two polynomials which specify the same function. This makes some nice results like the fundamental theorem of algebra (for the tropical semiring) not immediately useful.

The obvious candidates like Karatsuba don't work (the Grothendieck group of $(\mathbb{Z}\cup\\{-\infty\\}, \max)$ is trivial, so you can't extend the semiring to a ring), but I also haven't been able to come up with a reason why it shouldn't possible.

You can assume the coefficients are monotonically increasing if it makes the algorithm easier/faster.

# Answer
> 1 votes
The problem is computing the array $C$ defined as $C\_i = \max\_{j+k=i} (A\_j + B\_k)$ given arrays $A$ and $B$. It is called the *max-plus convolution*, or *MaxConv* problem. Note that the equivalent *min-plus convolution* problem is also used in literature.

There is a sub-quadratic time reduction from the 3SUM problem to this problem \[1\]. The popular *3SUM conjecture* states there is no truly sub-quadratic ($O(n^{2-\epsilon})$ for $\epsilon \> 0$) algorithm for the 3SUM problem. Therefore, no truly sub-quadratic algorithm is known for the max-plus convolution problem.

If the arrays are monotone, and all values are integers bounded by $O(n)$, subquadratic algorithms are known. Recently, Chi et al. \[2\] presented an $\tilde{O}(n^{1.5})$-time algorithm for this problem. Note that "monotonically increasing" and "monotonically decreasing" variants are equivalent because we can reverse both arrays as well as the resulting array.

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


# Question
Title: Solving the recurrence T(n) = 3T(n-2) with iterative method
It's been a while since I had to solve a recurrence and I wanted to make sure I understood the iterative method of solving these problems. Given:

$$T(n) = 3T(n-2)$$

My first step was to iteratively substitute terms to arrive at a general form:

$$T(n-2) = 3T(n-2 -2) = 3T(n-4)$$ $$T(n) = 3 \*3T(n-4)$$

leading to the general form:

$$ T(n) = 3^k T(n-2k) $$

Now I solve $n-2k = 1$ for $k$, which is the point where the recurrence stops (where $T(1)$) and insert that value ($n/2 - 1/2 = k$) into the general form:

$$T(n) = 3^{n/2-1/2}$$ $$T(n) = O(3^n)$$

I'm not sure about that last step:

I would just "argue" that as $n \to \infty$ one can ignore $-1/2$ and $n/2 \to n$ ? Is that assumption correct?

# Answer
> 7 votes
Note that $3^{n/2-1/2} = \frac{1}{\sqrt{3}} 3^{n/2} = \frac 1{\sqrt{3}} \sqrt{3^n}$. So the $-\frac 12$ indeed becomes a constant factor that is absorbed by the $O()$, but $\frac n2$ in the exponent changes the base and changing the base changes the $O$-class.

The correct answer thus is $T(n) = O(3^{n/2}) = O(\sqrt{3^n})$.

# Answer
> 6 votes
Everything was correct up until the last step...you found:

$$ T(n) \propto 3^{\frac{n}{2}- \frac{1}{2}} = \left(3^{n - 1}\right)^{\frac{1}{2}} = \frac{1}{\sqrt{3}}\left(\sqrt{3}\right)^n $$

# Answer
> 0 votes
**More rigorously:**

First note that the recurrence only involves terms that are two units apart, so there will be a solution for the even $n$ and an independent one for the odd.

Let first $n:=2m$. We have

$$T(2m)=3T(2m-2)=3^2T(2m-2\cdot2)=\cdots3^mT(0)$$

or

$$T(n)=3^{n/2}T(0)=(3^{1/2})^nT(0)=\sqrt3^nT(0).$$ And similarly for odd $n$,

$$T(n)=\sqrt3^{n-1}T(1).$$

This is captured by

$$T(n)=\Theta(\sqrt3^n).$$

---
Tags: asymptotics, recurrence-relation
---


# Question
Title: Minimum amount of parties containing round tables for everyone to meet each other
So the problem is: There is a group of n people that want to meet each other and everyone is divided into pairs, so everyone has a partner that they know. Now there will be parties at which they can get to know each other. At every party there can be as many round tables as needed, at which people can sit. When they sit at the table, they get to know their left and right neighbour. What is the minimum amount of parties that need to be held for everyone to meet each other (except their own partner)?

It is assumed that n is a power of 2 in this case.

How could I start implementing such an algorithm? I've looked at the round robin tournament algorithm but this seems to be too different to be useful. I was thinking something along the lines of dividing the n people into groups so that everyone is in a seperate group from their partner.

# Answer
Suppose $n=2^k$.

Each person should get to know $2^k-1-1=2^k-2$ unknown people. At each party, each person get to know at most two unknown people. Hence, each person must join at least $\frac{2^k-2}2=2^{k-1}-1$ parties. So there must be at least that many parties.

---

The question is then whether that many parties are enough for all people to get to know each other. The answer is yes.

Let us divide and conquer, for $k\ge1$.

If $k=1$, no party is needed.

Assume $k\ge2$. Let us divide all people evenly into $2$ groups, keeping every pair of partners in the same group so that we have two groups of $2^{k-1}$ people each.

Suppose we have held $2^{(k-1)-1}-1=2^{k-2}-1$ parties for each group so that in each group, people know each other. We can consider those parties as $2^{k-2}-1$ parties for all $2^k$ people by holding two parties, one for each group together as one party for all $2^k$ people.

Our goal is to hold another $2^{k-2}$ parties so that everyone in one group get to know everyone in the other group.

Let $a\_1, a\_2, \cdots, a\_{2^{k-1}}$ be the people in one group and $b\_1, b\_2, \cdots, b\_{2^{k-1}}$ be the people in the other group. For $j$-th party, $1\le j\le 2^{k-2}$, we can arrange all people at one round table as follows: $$a\_1,b\_{1+2j}, a\_2, b\_{2+2j},a\_3, b\_{3+2j},\cdots,a\_{2^{k-1}}, b\_{2^{k-1}+2j}$$ where $b\_m$ means person $b\_{m- 2^{k-1}}$ when $m\>2^{k-1}$. Put it in another way, we can line up $a\_1, a\_2, a\_3,\cdots, a\_{2^{k-1}}$ as well as $b\_1, b\_2, b\_3,\cdots, b\_{2^{k-1}}$ first. Then interweave/zip two lines of people, starting with $a\_1$ and $b\_{1+2j}$.

You can verify the arrangements above let everyone in one group know everyone in the other group. Our goal is archived. So with $2^{k-2}-1+2^{k-2}=2^{k-1}-1$ parties, all people can get to know each other.
> 1 votes

---
Tags: divide-and-conquer
---


# Question
Title: Help with time complexity of a given code
Given the following code:

```
void aux(int n){
   while (n > 0) {
   printf("%d", n);
   n--;
  }
}
long f1(int n)
{
  long sum = 0;
  for (int i = 1; i * i <= n; i++) {
    for (int j = 1; j <= i; j++) {
      aux(i * j);
      sum += i * j;
     }
  }
 return sum;
}

```

I have calculated the time complexity of aux and I found it is $\Theta(n)$. Then I tried to find the time complexity of f1 and got the following expression:

$$ \sum\_{j=1}^1 j + 2\sum\_{j=1}^2j + 3\sum\_{j=1}^3 j +...+ \sqrt{n} \sum\_{j=1}^{\sqrt{n}} j $$

The right answer here is $\Theta(n^2)$ but I'm really not sure why that is the case. Can anyone explain if the expression I've got is correct, and if so why it is equal to the time complexity above?

# Answer
> 1 votes
Let $n=m^2$.

$$ \sum\_{j=1}^1 j + 2\sum\_{j=1}^2j + 3\sum\_{j=1}^3 j +...+ m \sum\_{j=1}^{m} j \\\=1 + 2\cdot3 + 3\cdot6 +...+ m \frac{m(m+1)}2\\\sim\frac{m^4}8=\Theta(m^4)=\Theta(n^2) $$

by Faulhaber.

---

More precisely,

$$\frac{3m^4+10m^3+9m^2+2m}{24}=\frac{m(3m+1)(m+1)(m+2)}{24}.$$

---
Tags: time-complexity, c
---


# Question
Title: Route planning on line segments which can be connected or not
I have several lines that are shown in different colours, do not know which are connected to each other in advance. I want to do path planning only using these lines, i.e., route planning. If I am able to construct a graph using these line segments, I can use graph search techniques, e.g., A\*, to find the path between provided two start and target points.

**Quation**: What could be the optimal way to construct a graph using these line segments? Each such line segment consists of a set of points along the line.

After @Yves Daoust suggestion I got want I want, many tanks

# Answer
> 3 votes
**Hint:**

Possible first steps are binarization, then thinning.

After that, it is no big deal to find the junctions and to follow the edges between them.

---

A piece of caution: thinning tends to turn the lane crossings to double junction points instead of a single. These configurations can be a little tricky to handle.

---
Tags: algorithms, graphs, shortest-path, graph-traversal
---


# Question
Title: Determine bijective mapping using minimal number of lookups in subset mapping - standard problem / perspectives?
This seems like it should be a "textbook"/standard problem but I wasn't able to find anything about it, so I'd like to know if anyone else has seen something like it before or can suggest more keywords I could search for / perspectives I could view it from:

### Informal problem statement

Informally, the situation is that we have a bunch of input values and an unknown (to us) mapping we want to determine which maps them to output values. We can gain information on the mapping by calling a fairly expensive query/lookup function with one or multiple input values and it will return the corresponding output values in a random order (so we don't know which given input corresponds to which output unless we called it with only one input). The task is to come up with an algorithm that completely determines the mapping using the **least** number of calls to the query/lookup function.

### Formal problem statement

So, formally, we have an input set $X = \\{ x\_1, …, x\_n \\}$ and an output set $Y = \\{ y\_1, …, y\_n \\}$. There is an unknown bijective mapping $f: X \rightarrow Y$ between them that we want to determine by making as few calls to a function $q: \mathcal{P}(X) \rightarrow \mathcal{P}(Y); \ \\{ x\_i, x\_j, … \\} \mapsto \\{ f(x\_i), f(x\_j), … \\}$ as possible, where $\mathcal{P}(S)$ denotes the power set (set of all subsets) of $S$.

## Question

I already have a fairly naive algorithm for it based on the idea that we can find out a part of the mapping whenever a single value is shared between two input sets that the query function was called with, because then we can find the corresponding output value by looking at which value appears in both query function results. By developing this a bit further, e.g. a 38-element mapping can be fully determined with only 11 calls.

But as I wrote at the beginning, my question is really if this is some kind of standard problem or if there are any perspectives I could view it from to reduce it to one.

# Answer
> 1 votes
# An algorithm

I have never seen this problem before, but I can suggest a randomized algorithm for this problem.

* Create a bipartite graph, with left vertices $X$ and right vertices $Y$, and initially containing all edges $X \times Y$.
* Repeat the following until the algorithm terminates:

+ Pick a random set $S$ of $n/2$ values from $X$. Query $S$, to learn the set $F(S)$.
    + For each $x \in S$ and each $y \notin F(S)$, remove the edge $(x,y)$ from the graph. For each $x \notin S$ and each $y \in F(S)$, remove the edge $(x,y)$.
    + Run a bipartite matching algorithm on this bipartite graph. If the graph has only a single perfect matching, output it as the mapping and terminate. Otherwise, continue on to the next iteration. \[An alternate version of this step: If each vertex has degree 1, i.e., maps to exactly one other vertex, then output the mapping given by this graph and terminate; otherwise continue on to the next iteration.\]

# Correctness

Hopefully it is clear why this algorithm is correct, i.e., if it terminates, then it outputs the correct solution.

# Running time

How efficient is this algorithm? I argue that the number of iterations of the loop is $O(\log n)$. It follows that the number of queries to the lookup function is $O(\log n)$. Why? Well, consider a single $x \in X$, and a $y \in Y$ such that $y \ne f(x)$. Thanks to the random choice of $S$, $\Pr\[x \in S\] \approx 1/2$, and of those, $\Pr\[y \notin F(S)\] \approx 1/2$, so after one iteration, the probability that the edge $(x,y)$ remains in the graph is about $3/4$; and this probability drops to $(3/4)^r$ after $r$ repetitions of the loop. In particular, after $r = 4.8 \lg n + 2.4 c$ repetitions, then the probability that $(x,y)$ remains is about $2^{-2\lg n - c} \approx 2^{-c}/n^2$. Using a union bound and summing over all $y \in Y \setminus \\{f(x)\\}$, we find that the probability that $x$ has an edge to any vertex other than $f(x)$ is at most $2^{-c}/n$. Using a union bound again and summing over all $x \in X$, we find that the probability that the graph has any edge other than $\\{(x,f(x)) \mid x \in X\\}$ is at most about $2^{-c}$.

In short, after $4.8 \lg n + 2.4 c$ queries to the lookup function, this will almost surely terminate with the correct solution: the probability it doesn't is at most $2^{-c}$, i.e., exponentially small. Most of the time, it will terminate within about $4.8 \lg n$ repetitions.

# Optimality

Could there be a better algorithm? It's possible, but I have an information-theoretic heuristic which suggests to me that this is approximately optimal. In particular, if we query the lookup function with a set of size $k$, then out of the $n!$ possible mappings, only $k! (n-k)!$ will remain consistent with the output of the lookup function. Therefore, the result from this query can be expected to give us about $\lg(n!) - \lg(k! (n-k)!)$ bits of information. This is $\lg {n \choose k}$. Heuristically, it seems natural to choose $k$ to maximize the number of bits of information provided by the oracle. The value of $k$ that maximizes ${n \choose k}$ is $k=n/2$, and then

$$\lg {n \choose k} = \lg {n \choose n/2} \approx n - 0.5 \lg n + 1.$$

So each query can provide at most about $n$ bits of information. Moreover, there are $n!$ mappings, so it requires $\lg(n!)$ bits of information to specify a mapping; since $\lg(n!) \approx n \log n -n + O(\log n)$, it follows that we need at least about $\log n - 1$ queries to uniquely recover the mapping. So the algorithm above should be close to optimal.

---
Tags: algorithms
---


title: Pushdown Automata Construction

text:
# Question
Title: Pushdown Automata Construction
I had an assignment in which I had to design a pushdown automata that recognizes the language ${w \in \[a,b,c\]^\*|w }$ have the same number of "ab" and "ba".

Tried to make a pushdown automata that if reads first ab pushes 1 to the stack and then if finds "ba" then pops it (and again reads "ab" and then "ba" , push / pop ) and the same if reads first "ba" and pops if finds "ab",but this approach fails for the case : ${baababbabaab}$ and many more cases. If someone could find whats wrong with my approach

# Answer
To see what goes wrong with your approach, it's best to scale down a bit.

As you've defined it, the string $aba$ lies in the language. You should try to come up with a way to make your automata accept this string.
> 1 votes

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


# Question
Title: If $NP^{NP} = NP$, then the polynomial hierarchy collapses to it's first level. How to prove it?
From this link Does $NP^{NP}=NP$?

I learned that if $NP^{NP} = NP$, then the polynomial hierarchy collapses to it's first level.

But how to prove it？

# Answer
Prove that $\Sigma\_i^P = NP$ for $i \ge 2$ by induction on $i$. The base case is $i=2$ and is trivial since, by hypothesis, $\Sigma\_2^P = NP^{NP} = NP$. For the inductive step, suppose that $\Sigma\_i^P = NP$ and notice that $\Sigma\_{i+1}^P = NP^{\Sigma\_i^P} = NP^{NP}= NP$.

Now, for $i \ge 2$, you can observe that $NP \subseteq \Delta\_{i}^P \subseteq \Pi\_i^P \subseteq \Delta\_{i+1}^P \subseteq \Sigma\_{i+1}^P = NP$.
> 3 votes

---
Tags: complexity-theory, np-complete, np
---


# Question
Title: Correct Term for describing "diamond" subgraphs in a Directed Acyclic Graph
I am trying to research handling a specific type of possible subgraph in directed acyclic graphs.

However, I am struggling to find the correct term to use. If we consider the subgraph S to be in a DAG G. Where S is made up of 2 paths, starting at a common node and ending at a common node. Thus forming a "diamond" shape when arranged the starting node to the ending node.

For example:

So, what would be the correct term for describing subgraphs that fit this condition when describing the graph? Is there even such a term, let alone existing literature?

Thank you.

# Answer
> 2 votes
Everyone will know what you mean by "diamond", in computer science, if you define it up front. See, for example: multiple inheritance.

I don't think there is a standard name for this structure. But also, the term "diamond" doesn't always refer to this, even in mathematical objects that can be represented as directed acyclic graphs.

For example, I have seen the lattice $\mathcal{M}\_3$ referred to as "the diamond", for obvious reasons when you look at its Hasse diagram.

If it has a domain-specific interpretation, of course, then you should use that (e.g. if it's a "unique implication point" in clause learning).

---
Tags: graphs, terminology, graph-traversal, dag
---


# Question
Title: The existence of solution of a multivariate polynomial
Given a multivariate polynomial of degree 4 on $v$ (real) variables such that there are $N$ terms in the polynomial. Is there an efficient algorithm to verify if it has a solution?

Not aware of any algorithm for this problem. Can someone please comment.

I think the solution itself can be calculated by Newton Raphson algorithm (but I am unaware of its running time complexity).

# Answer
No. The problem is NP-hard.

It is NP-hard to test whether a system of quadratic equations has any solution. See Reduction from vertex-cover to system of quadratic equations, Determine whether the system of equations is underdetermined or overdetermined (related: 3-SAT and Systems of Nonlinear Modular Equations).

Let $f\_1(x)=0$, ..., $f\_k(x)=0$ be a system of quadratic equations, where each $f\_i$ is a multivariate quadratic polynomial on the variables. Define

$$g(x) = f\_1(x)^2 + \dots + f\_k(x)^2.$$

Then the single equation $g(x)=0$ has a solution if and only if the system of quadratic equations $f\_1(x)=0$, ..., $f\_k(x)=0$ has a solution. Moreover, $g$ has degree 4.

This reduction proves that your problem is NP-hard.
> 2 votes

# Answer
Mainly there are two methods, estimation of Eigenvalues of a matrix is the command method we use.

```
    #include <iostream>
    #include <Eigen/Core>
    #include <Eigen/Geometry>
    #include <Eigen/Dense>
    #include <unsupported/Eigen/Polynomials>
    #include <cmath>
    #include <vector>
    #include <complex>

    template<typename T>
    class RootFinder {
        public:
            RootFinder() = default;
            ~RootFinder() = default;

            inline std::vector<std::complex<T>> calculateEigenValuesOfMatrix(Eigen::MatrixXd A){
                Eigen::EigenSolver<Eigen::MatrixXd> ES(A);
                std::vector<std::complex<T>> eigen_values;
                for(int i =0;i<ES.eigenvalues().rows();++i){
                    eigen_values.push_back(ES.eigenvalues()[i]);
                }
                return eigen_values;
            };

            inline std::vector<std::complex<T>> calculateRootsOfPoly(Eigen::VectorXd coeffs){
                Eigen::PolynomialSolver<T, Eigen::Dynamic> solver;
                solver.compute(coeffs);
                const typename Eigen::PolynomialSolver<T, Eigen::Dynamic>::RootsType & r = solver.roots();
                std::vector<std::complex<T>> roots;
                for(int i =0;i<r.rows();++i)
                {
                    roots.push_back(r[i]);
                }
                return roots;
            };

        private:

    };

```

Here some of example how to use this method to find root of any higher order polynomial https://github.com/GPrathap/motion\_planning/blob/main/motion\_planning\_alg/src/main.cpp

For more information check these slides: https://github.com/GPrathap/motion\_planning/blob/main/lectures/mpav\_pontryagin\_s\_optimal\_control\_theory.pdf (page 20)
> -1 votes

---
Tags: algorithms
---


# Question
Title: What is a heuristic in human computer interaction?
I have found multiple definitions of what a heuristic is, and I have found multiple computer science-related definitions.

In my university course, the lectures cite the Nielson Norman Group defining a heuristic as an area of measurement. On Wikipedia, a heuristic is defined as a problem-solving technique. These definitions do not seem to be referring to the same thing.

In the context of human-computer interaction, what is a heuristic?

# Answer
you might aswell ask this qustion over at https://ux.stackexchange.com/. But you are a CS guy so you probably didn't touch that UX part yet.

Heuristics as defined by Nielson et al. can be used to evaluate the usability of a user interface. They describe common-sense approaches to identify usability issues with user interfaces. Therefore these heuristics are "problem-solving technique": A technique to identify problems in user interfaces.

As children grow up, they learn heuristics like "if it smells bad - don't eat it" or "if something is red - be careful, it might be hot".

And for UI heuristics it is similar: "If the error message does not say what the problem is - users will not be able to solve it.", "If I can see/visit/input forms that dont apply to me - Users will get lost." or "If I cant use or customize keyboard shortcuts - experienced users can not start to work more efficiently."

These ARE concrete heuristics - each is a technique to identify (and solve) usability problems in user interfaces.
> 3 votes

---
Tags: terminology, heuristics, definitions, user-interface, human-computing
---


title: Does ChatGPT use specific sub-programs

text:
# Question
Title: Does ChatGPT use specific sub-programs
I have had a somewhat hard time trying to understand how ChatGPT can "solve" some tasks that cannot be entirely cast as language-model-based rephrasing of textual subsets of the internet directed by a textual query.

For example, ChatGPT seems to be able to do calculations, even if not always appropriately used, execute code, extract literature references from input text, etc.

It seems to me that it is not simply one huge neural network, but has access to some additional programs like a calculator or some interpreters for programming languages, etc. So it would be more like a human-machine interface.

To which extend is my interpretation correct?

# Answer
> 2 votes
> It seems to me that it is not simply one huge neural network, but has access to some additional programs like a calculator

I'd add to D.W.'s answer that OpenAI's CEO explicitly mentioned today in the GPT-4 announcement video that GPT-4 isn't hooked up to a calculator.

# Answer
> 2 votes
ChaGPT's own words:

"The cosine of 2.325 radians is approximately equal to -0.695206961. You can use a calculator to find the value or use the cosine formula:

cos(2.325) = cos(2.3 + 0.025) = cos(2.3)cos(0.025) - sin(2.3)sin(0.025)

Using a calculator, we can find that cos(0.025) ≈ 0.999687. Also, from the previous calculation, we know that cos(2.3) ≈ -0.746630108 and sin(2.3) ≈ -0.665122709. Substituting these values in the formula above, we get:

cos(2.325) ≈ (-0.746630108)(0.999687) - (-0.665122709)(0.025) ≈ -0.745952881 - (-0.016628068) ≈ -0.695324813

Rounding this value to 10 decimal places gives us -0.695206961."

By the way, $\cos(2.325)=-0.68470850929173064765331747989949$.

Notice the gross confusion and sign error between the sine and cosine of $2.3$.

# Answer
> 1 votes
No, your interpretation is not correct. One way to think of GPT-3 is as a predictor: given some words, it tries to predict what words come next. Another way to think of GPT-3 is as a "bullshitter": it tries to predict some words that will superficially sound plausible. It has no deep knowledge or ability to do additional computation beyond what is inherent in that capability. It does not have access to additional programs -- it is simply one big neural network. I realize it might look like ChatGPT has a lot of capability, but that is just us getting fooled into ascribing something that's not actually there.

See https://en.wikipedia.org/wiki/GPT-3 and https://en.wikipedia.org/wiki/ChatGPT.

---
Tags: machine-learning, neural-networks, natural-language-processing, computer-vs-human
---


# Question
Title: How do type classes make ad-hoc polymorphism less ad hoc?
The title of the paper that introduced type classes is "How to make *ad-hoc* polymorphism less *ad hoc*".

It seems the type classes approach is being compared to how OOP does ad-hoc polymorphism.

As far as I can tell, the paper never explains *how* type classes are less ad hoc than OOP techniques like V-tables or prototype chains, or even has any comparison at all of the trade-offs between the two approaches.

What is non-ad-hoc about ad-hoc polymorphism via type classes?

> Note: this is a somewhat objective question, as "ad-hoc" is here a technical term. From the paper, "Ad-hoc polymorphism occurs when a function is defined over several different types, acting in a different way for each type."

**UPDATE** Re object-oriented programming: that is not within the scope of the paper. The paper calls out that type classes are related to OO in section 1 but doesn't compare against OO aside from a short comparison of dictionary-passing and v-tables in section 2. Instead, the paper illustrates the problem it attempts to solve using examples from Miranda and SML.

# Answer
> 2 votes
The paper is valuable but does not show how to make ad-hoc polymorphism less ad hoc.

I'll review the terminology and then apply it

## Terminology

For the definition of "ad-hoc" polymorphism, the reader is pointed to Strachey's Fundamental Concepts in Programming Languages of 1967. Strachey does not hyphenate "ad hoc" and defines it as follows:

> There seem to be two main classes \[of polymporhpism\], which can be called ad hoc polymorphism and parametric polymorphism ... In ad hoc polymorphism there is no single systematic way of determining the type of the result from the type of the arguments. There may be several rules of limited extent which reduce the number of cases, but these are themselves ad hoc both in scope and content ... Parametric polymorphism is more regular and may be illustrated by an example ...

Wadler's "Ad hoc" is not defined in the "Making" paper, so I assume what Wadler means is a pretheoretic notion of "ad hoc". Merriam-Webster's definition of the adverb form "ad hoc" seems apt: "for the particular end or case at hand without consideration of wider application".

## Applying the terminology

"ad-hoc" and "ad hoc" as given in the paper appear to be synonyms. So the claim that the paper shows how to make ad-hoc polymorphism less ad hoc is either trivially false or too vague to engage with. The paper might as well be promising to make cheese less cheesey. It's still a great paper!

## Why it matters that ad-hoc polymorphism was not made less ad hoc

If we use the terminology in the paper, it's easy to trick ourselves into thinking we are talking about something when we talk about systematic ad-hoc polymorphism. But "systematic ad-hoc polymorphism" is an oxymoron, at least using the definition given.

This leaves open the following possibilities, even without engaging with object oriented programming:

* type classes are a distinct mechanism for polymorphism that is not parametric polymorphism
* OR type classes are "just" parametric polymorphism. This would explain (for example) why a similar effect to type classes can be achieved using implicit parameters ("Type Classes as Objects and Implicits”)

---
Tags: type-theory, haskell, abstract-data-types
---


# Question
Title: If a user confirmed a booking or transaction on the database system, but it failed and it falls over to the replica, what if the transaction is lost?
This is an overall system design and DBMS question:

If the user books a ticket or an item on a website, how do we solve the issue of confirming a ticket is sold to the user, but the main Database System breaks down, and the secondary DMBS doesn't have that information yet?

Is the most common solution just to not commit the transaction until both the master and slave DBMS has confirmed?

# Answer
Generally speaking, things like orders are not confirmed until some trace of them is recorded in the database.

Database disks are usually mirrored at the hardware level (with transactional guarantees of mirroring provided by the disk array controller), and the database may be completely replicated across machines or physical sites.

The process of placing an order like a consumer web order is rarely a one-shot process. There is the establishment of an account, then an order, then payment (often via a third party computer system), before the customer is told that their order is actually lodged.

It's actually quite hard to imagine plausible circumstances in which no recoverable trace is left either of an order itself, or something that can identify customers who may have placed an order immediately prior to a failure (who can then be put on notice that something may have been lost).

Obviously there is the theory that if *all* database infrastructure is totally wiped out, then the order and all its traces must be lost, even after confirmation occurred. But you're talking about a TV-newsworthy catastrophe, like a nuclear blast with extensive physical destruction that utterly carries away all the machinery in many buildings.

There are far more common risks to orders than this, including erroneous computer logic that erases data, "fat finger" operators, or just a delivery package lost in the post.

The bottom line is that common techniques exist to ensure that records are guaranteed as long as the hardware is guaranteed, and the hardware can easily be guaranteed to a level that overwhelms the reliability of other aspects of any system which distributes goods or services.
> 1 votes

# Answer
There is no single answer that is always used; there is a tradeoff between consistency, availability, and ability to handle failures. Most databases ensure that the data is stored persistently on disk before reporting that the transaction is confirmed, so even if the main database fails, if it has accepted the data, then the data will be there on disk.

Of course you *could* avoid committing until both replicas have confirmed, but then the system would not be available if either replica cannot be reached; or you could continue as soon as the master has accepted the data, but then the secondary replica could become out of sync. I suggest learning about the CAP theorem and fundamental tradeoffs in database systems.

There will always be some failures that we cannot or do not prevent through technical means. So, they might be addressed by ad-hoc methods (e.g., the customer could call customer support).
> 0 votes

---
Tags: databases, transactions
---


# Question
Title: Strictness in both arguments but not in each individually
I'm learning about strict functions in Haskell.
A function f is strict if f ⊥ = ⊥
Some functions are strict only in the first argument (for e.g. const), others are strict in the second (for e.g. map).
I'm trying to think of a function which is strict in only both arguments at the same time, so
f x ⊥ is not bottom
f ⊥ y is not bottom
but
f ⊥ ⊥ is bottom
and I can't come up with any such function. Is this possible?

It feels like it isn't, but I'm a bit confused. Also because of currying, we can think of the function as only taking one argument at a time and then returning a function that takes the second argument. Do we only talk about strictness in one argument at a time?

# Answer
That's a very good question! It turns out the answer is both yes and no.

A classic example of a function we'd like to write is Plotkin's parallel or. We know from basic boolean logic that both `or True _` and `or _ True` are always true, regardless of the value of `_`. So we'd like to write a function `or` that takes two arguments, and `True` if either argument is `True`, returns `False` if both arguments are `False`, and only doesn't terminate if neither argument terminates. But can we?

It turns out that in the lambda calculus, it's impossible to write such a function. The lambda calculus is said to be *inherently sequential*. I've written a bit about this in the past in Why are there two not operators in lambda calculus?, on a related example.

If you think in terms of Turing machines, it *is* possible to write a machine that performs parallel `or`. Consider a machine with two inputs: a description of a machine $M\_1$ that calculates the first argument, and a description of a machine $M\_2$ that calculates the second argument. The machine simulates one step of $M\_1$, then one step of $M\_2$, then again one step of each machine in turn, until one of the machine halts. If the first machine to halt outputs `True`, output `True` and stop, otherwise keep simulating the other machine and return its output (if it ever terminates).

This illustrates an important aspect of the Church-Turing thesis. All definitions of things we'd sensibly want to call “this can be computer” turn out to be equivalent, as long as the intuition of computability is only about taking inputs and returning a result. If we throw other things into the mix, such as looking at computations in progress and giving it a meaning other than the final output, then models of computation are not equivalent. In particular, there isn't an equivalent of the Church-Turing thesis for concurrent computation: different models often have subtle differences in terms of expressivity.
> 17 votes

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


# Question
Title: Is there a "Standard Algorithm" language, as used in academic papers?
In many academic papers algorithms are described. They seem to use similar "syntax".

Is there a standard for this language? If I want to describe an algorithm, would I improvise my description?

For example, note that papers in general use

```
a <-- b

```

to assign a, not a = b. But where is that standard?

# Answer
> 30 votes
No. There is no universal standard. There are some conventions that have become more popular over time, through gradual evolution.

A good starting place to look would be to look at the pseudocode notation used in a few common algorithms textbooks, pick one you like, and try to emulate it. Probably anything done in a popular and well-regarded textbook is going to be reasonable and understandable to others.

# Answer
> 25 votes
The word you are looking for is **pseudocode.** :) There is no official standard, but as you have observed, there are general conventions that most people follow. Partly this is dictated by popular LaTeX packages (see, for example, this guide).

It's worth noting that the point of pseudocode is not to be formally specified, but to be *human-readable*. As a result, it is unlikely that all aspects of it could be standardized. For example, in pseudocode one sometimes takes a shortcut like:

```
for all vertices v reachable from u, do:
   ...

```

with the understanding that we can implement this using a DFS or a BFS. To a human reader, this is often clearer than writing out the DFS or BFS explicitly. In short, **pseudocode cannot be fully standardized, because its goal is to be read and easily understood by a human.**

That being said, there are some conventions that most pseudocode follows, which are considered easier to read than the alternatives. A short list is:

* Pseudocode is generally written imperatively, that is as a set of functions or procedures which consist of sequentially composed instructions, `if`-`then` blocks, `while`, and `for` loops.
* For variable assignment, $a \gets b$ or $a := b$ is generally preferred to $a = b$ as it distinguishes assignment from equality
* Mathematical expressions are usually written as formulas rather than programmatically: e.g. "while $n \le \sqrt{m + 1}$" is preferred over `while (n <= sqrt(m + 1))`.
* Data structures are named explicitly using standard naming conventions: for example, "dynamic array" for a growable, O(1) accessible list rather than something like "vector".
* Function calls and control flow jumps are usually made explicit using a keyword: e.g. "return $x$", "call $f(x, y)$", "break", and "continue". "goto" and "label" are also sometimes used, though probably somewhat discouraged.

# Answer
> 7 votes
There is no common standard because for languages of any kind (both in theoretical CS, i.e. more abstract languages like lambda calculus; as well as in practical programming languages used to write actual code) there always is a preferred mode of usage, or a type of problem where using a particular language would make most sense, compared to other languages.

As an example: you can use any Turing-complete language to solve any kind of problem we can think about; and basically everything that's worth talking about in this context is Turing-complete. So all languages can perform the same work. But depending on the problem to solve, using, say, a purely functional language like Haskell may be super easy and elegant, while solving the same problem in a purely imperative language like C might be very hard or at least annoying. And vice versa of course; you would program a Kernel driver in C, but not in ProLog.

The same goes for papers. Sometimes it may be perfectly optimal to use lambda calculus to talk about some problem; but sometimes you might be better off with a very basic imperative "language" which basically just formalizes natural language a little bit. You would use, for example, lambda calculus if the problem you wish to solve somehow benefits from the semantics of that language (and any proofs/theorems that are already established). But if you just wish to use a quick pseudo language to make some ideas clearer, a simple intuitive imperative notation with intuitive semantics may be just fine.

Finally, you can also whip up a quick DSL (domain specific language) which not only contains abstract language semantics, but also somehow includes features of the domain in the notation. For example, most of the symbols, conventions and semantics used in maths itself are, basically, a DSL - and if you compare that to notation for *physical* math, you will find so many differences that a person familiar with the one might be incapable to understand the other, albeit the other makes much more sense for that particular domain.

And within all these languages, the textual representation is usually a matter of taste and convention, which may be different in different special areas of CS; or even from country to country.

# Answer
> 6 votes
As others note, there won't be any one universal standard for pseudocode.

That said, Rosen's *Discrete Mathematics* has a particularly well-defined system for pseudocode (in Appendix 3), and if you were looking for a particular grammar, then it could be a good model.

# Answer
> 4 votes
There is no official standard, but I would argue that algorithm pseudocode conventionally follows much of the syntax of Dijkstra's Guarded Command Language, with influence from other structured programming syntaxes of the late seventies and early eighties, and often used explicitly in texts such as Carroll Morgan's *Programming From Specifications* (1990–1998). Because there is no officially maintained standard for pseudocode, and many CS papers do not explicitly place their algorithm description within a syntax and semantics, the relationship is not one of strict conformance, but of family resemblance.

The formatting provided by the standard LaTeX packages for algorithms are also strongly influenced by this syntax, and this tooling infrastructure helps continue the convention.

Some examples:

* Using symbols like $\geq$ instead of the more common executable programming language syntax of `>=`
* The use of logical predicates with richer set theory syntax as guards
* The use of structured programming era style blocks for conditionals and loops, with named `if/end if` and `do / od` pairs, rather than braces, as in C-style languages, or whitespace syntax, as in Python.

There are some counter-examples, including the use of $\leftarrow$ rather than `:=` for assignment, as in GCL. I suspect this is because of a certain continuity of mathematical style and because it saves slightly on horizontal space when formatting pages close to the page limit of publications and conferences. Some more careful close reading of papers historical and present could help trace the style lineage more precisely.

# Answer
> 2 votes
The type of pseudocode I’ve most commonly seen is loosely based on ALGOL, sometimes falling back to natural language or algebraic notation.

For example, compare this sample (from Wikipedia) of Algol-60:

```
BEGIN
INTEGER p, q;
y := 0; i := k := 1;
     for p := 1 step 1 until n do
         for q := 1 step 1 until m do
             if abs(a[p, q]) > y then
                 begin y := abs(a[p, q]);
                     i := p; k := q
                 end
 END Absmax

```

With this pseudocode from the second paper I checked at random:

```
Notation: The flight corridor ℬ; global guide path ;
Initial and goal position: 0, g; local guide point h
Input: , 0, g
Output: ℬ

2  Initialize ℬcur = GenerateOneSphere(0);
3  ℬ.PushBack(ℬcur);
4  while True do
5      h = GetForwardPointOnPath(, ℬcur);
6      ℬcur = BatchSample(h, ℬcur);
7      ℬ.PushBack(ℬcur);
8      if g ∈ ℬcur then
9          break;
10     end
11 end
12 WaypointAndTimeInitialization(ℬ);

```

This doesn’t quite match the formatting of the original (Algorithm 1 on page 4), such as the syntax highlighting, and it introduces mathematical notation such as  that very few programming languages support (Haskell being one that can), but you can see the similarities.

In particular, it retains the semicolons and `end` statements of ALGOL, even though only parsers that ignore whitespace need them, and they are completely redundant in pseudocode written for human eyes. This listing does not use the `:=` assignment operator, but I have seen many that do. Because `=` sometimes means assignment, and sometimes a test for equality, you need to be careful to be unambiguous. This is likely one reason for the use of the left arrow (one of whose most influential users was Donald E. Knuth).

---
Tags: algorithms, pseudocode
---