# Question
Title: translating operations per second (OPS) to floating point operations per second (FLOPS)
I have some algorithmic complexity estimates in Giga Operations Per Second (GOPS) and I would like to compare those with the capabilities of state-of-the-art processors. However, the processor performance is commonly measured in FLOPS.

According to this (Eq.4) FLOPS\_core = OPS * FLOPs/operation

1. What would be a reasonable value for FLOPs/operation ?
2. Can I translate the complexities to fixed point operations per second?

# Answer
Processors without built-in floating point arithmetic usually require say 50 non-floating point operations to implement a floating point operations.

Processors with built-in floating point arithmetic usually have about equivalent or slightly higher non-floating point capabilities, but slightly lower (say five times lower) fixed point, non-integer capabilities.

You should also look at memory bandwidth which can be much more important. And every bit of code is different, so just plugging in numbers into formulas is not *very* informative. It *may* give you enough information to decide "it may be worthwhile to try to implement this algorithm on a 1999 supercomputer on my 2021 iPhone" or not.

But you really, really, really need to look at your particular problem. You can't solve this with tables, you solve it by measuring.
> 1 votes

# Answer
If you don't care too much about accuracy, FLOPS and OPS are roughly equivalent.

If you do care, then neither FLOPS nor OPS are precise enough.
> 1 votes

---
Tags: complexity-theory, time-complexity, computer-architecture
---


# Question
Title: Help me solve recursion equation by using recursion tree method
Hello I am trying to solve this recurrence equation using the recursion tree method:
T (n) = T (n −1) + n^2 In particular, what is big-O of T (n)?

Here is what I have done so far:

I am not sure if I drew the tree correctly, and I don't know how to figure out the runtime. If someone could draw out the tree, and explain how to get the overall runtime that would be helpful.

Thanks

fyi this is repost of this post with my work added. Moderators feel free to delete the old post.

# Answer
> 0 votes
The recurrences of the form

$$T(n)=T(n-1)+f(n),\\T(0)=T\_0$$ are solved by

$$T(n)=T\_0+\sum\_{k=1}^n f(n)$$

as you can check by induction.

(Because $T(n)=T(n-1)+f(n)=T(n-2)+f(n-1)+f(n)=T(n-3)+f(n-2)+f(n-1)+f(n)=\cdots$.)

---

From the above formula, we can obtain the asymptotic expression in an empirical way.

As the terms $n^2$ go growing, one can assume that the *average* resembles $n^2$ and we try the ansatz $\dfrac{T(n)}n=an^2$.

This leads to $$an^3=a(n-1)^3+n^2=an^3+(1-3a)n^2+3an-a,$$

which simplifies most when $a=\dfrac13$: $$0\sim n-\frac13.$$

As this residual is of a lower degree, we conclude

$$T(n)\sim\frac{n^3}3=\Theta(n^3).$$

Another method is to replace the sum by an integral.

---
Tags: runtime-analysis, recurrence-relation
---


title: Finding one face in planar graph

text:
# Question
Title: Finding one face in planar graph
Given a planar graph (represented using adjacency lists) we want to find a set of vertices which are around one (random) face. We know that the graph contains at least one triangle.

How do we find such a face?

# Answer
> 1 votes
It depends. If you have a planar embedding, and you want to find faces on it, just pick an edge, and keep walking on the face that's on the 'left' side of the edge when looked at in the direction you were walking. If you want to find a cycle of nodes for which there *exists* a planar embedding in which those cycles are a face, that's even easier, because in planar graphs, *every* cycle is a face in *some* embedding.

Here's a simple algorithm for finding a cycle, but you can think of your own one. Suppose you have a graph that you know is planar, and you want to find a face. Start at some vertex $v$ and perform a breadth-first search. In iteration $k$, you find the vertices at distance $k$ from $v$ and for each vertex at distance $k$ that you add, you count how many nodes at distance $k-1$ were connected to that node. If there is just one, then continue. Otherwise, if two nodes at distance $k-1$ are connected to a node $w$ at distance $k$, then you have found a cycle in the graph (it is possible that you count three or more, in that case, select two). Node $w$ lies on a face in the graph, in *some* planar embedding of the graph. It may lie on the same face as $v$, but not necessarily, for example, you can have a cycle with a tail, and you accidentally started in the tail.

To find a face, backtrack from $w$ within the nodes that you explored so far with your breadth-first search: first, two nodes $x\_1, x\_2$ at distance $k-1$ (like I described above). Then, in each iteration, for $x\_1$, find *the* node $x\_1'$ which is connected to $x\_1$ and is at distance $k-2$ from $v$ (why is there guaranteed to be only one? Because we identified $w$ as most nearby node with two paths leading to it from $v$), and repeat this until at some distance $d$ you find that your $x\_1$ ancestor and your $x\_2$ ancestor are the same node $y$.

You now have a face! That is, a cycle for which there is *some* planar embedding. The face has $w$ on one side, $y$ on the other side, and they are connected with two paths. One path is the series of $x\_1$ nodes that you just found, and the other is the series of $x\_2$ nodes. If you found $y=v$, then $v$ is on the face. You are not guaranteed to find a face with $v$ on it, but are other algorithms that find one if there is one. I can modify this algorithm to do that, and I'm sure you can too.

# Answer
> 0 votes
In my planar\_graph\_playground repo undirected\_graph.js function planar\_face\_traversal(G, ptfv) traverses all faces of embedded graph G, and calls all functions passed in planar face traversal visitor "ptfv".

"is\_embedding(G)" is a nice simple example using above function:

```
function is_embedding(G) {
    var nfaces = 0;

    planar_face_traversal(G, {begin_face: function () {
        nfaces += 1;
    }});

    return n_vertices(G) - n_edges(G) + nfaces === 2;
}

```

Another example is "dual\_graph(G)" creating the dual graph of planar embedding G.

Undirect graph library is available in JavaScript/NodeJS, C++ and Python in same repo.

Here can be seen how "forall\_edges(G, ...)" differs for the 3 languages:

Last, but not least, I use planar face traversal for "six\_coloring(G)" faces of planar embedding PostScript output:
(planar graphs are 4 colorable, and there is a linear time algorithm to 5 color a planar graph. "six\_coloring(G)" is just simpler algorithm)

---
Tags: graphs, planar-graphs
---


# Question
Title: Where is found the original library of the PBFT consensus algorithm?
In the PBFT paper written by Miguel Castro it has been mentioned:

(In Abstract:)

> "BFT has been implemented as a generic program library with a simple interface."

(Also in page 71:)

> "The algorithm has been implemented as a generic program library with a simple interface. Thelibrary can be used to provide Byzantine-fault-tolerant versions of different services ... The library is implemented in C++."

Where is this library found? if it is an open source code.

While there are several implementations of the PBFT consensus in github repositories , I could not find the original library in github.

I'd intend to use the PBFT original code in a distributed network.

**P.S.** If this site is not the related one to post this question, please let me know the relevant site.

# Answer
> 1 votes
I believe this link on the Internet Archive is the earliest available snapshot of the webpage that contains links to the requested source code.

---
Tags: algorithms, distributed-systems, consensus, byzantine
---


# Question
Title: Prove or give a counterexample of o(f) = O(f) − Θ(f)
Prove or give a counterexample: for every function f from non-negative integers to non-negative reals, o(f) = O(f) − Θ(f). Here “−” denotes the set minus operation. I try to make some tryout but failed to make the abstract function f to into working, can someone give me some Hints or solutions?

# Answer
Consider $f(n) = n^2$ and $g(n) = \left\\{\begin{array}{ll}n & \text{if }n\text{ is even}\\n^2&\text{otherwise}\end{array}\right.$.
> 0 votes

---
Tags: algorithms, algorithm-analysis
---


# Question
Title: Running time of SAT and other EXPTIME algorithms
I need to propose an algorithm for a NP-hard problem. I use dynamic programming which leads to a running time $O(2^s\cdot n^2), s\leq n.$ The algorithm aims to finding a path in a graph $G(V, E)$ (in which each of the n nodes is colored in one of the $s$ colors) containing all the $s$ colors which are represented a single time in the path. If we take a SAT solver approach, we get an exponential running time $O(2^n).$ I do not know if the running time of the SAT is correct, i.e. I do not see if I miss a polynomial factor such as $n^2$ which I get by the dynamic programming. I want to understand the difference in the running time of the two approaches. First, I have a naive question.

The time complexity $O(2^s\cdot n^2)$ contains a polynomial term. Can we say that $O(2^s\cdot n^2)$ remains exponential even though it contains a polynomial term ?

By definition of the EXPTIME algorithms we know that the running time is $O(2^{p(s)})$ where $p(s)$ is polynomial. This is in line with the SAT but not with the one I get from the dynamic programming. Can one maybe claim that the SAT provides the lower bound of EXPTIME algorithms ? Thanks.

# Answer
> 1 votes
You have the definition of EXPTIME wrong. The definition refers to the length of the input. Neither $s$ nor $n$ are the length of the input.

The definition of EXPTIME says that the running time is $O^{p(\ell)}$ where $\ell$ is the length of the input. A challenge for you: What is the length of the input, in terms of $s,n$? Think about what constitutes the input, and how many bits it takes to represent all of the elements of the input.

---
Tags: time-complexity, np-complete, satisfiability
---


# Question
Title: DP for Weighted Interval Scheduling: why is sorting by finish time necessary?
**Problem** : In the weighted interval scheduling problem, we want to find the maximum-weight subset of nonoverlapping jobs, given a set $J$ of jobs that have weights associated with them. Job $i \in J$ has a start time $s\_i$, a finish time $f\_i$, and a weight $w\_i \> 0$. We seek to find an optimal schedule — a subset $\cal{O}$ of non-overlapping jobs in $J$ with the maximum possible sum of weights.

**Dynamic Programming Solution**: In almost all textbooks or materials I could get access to, a DP algorithm is given as follows: First all jobs are sorted in order of ascending finish time: $f\_1\le f\_2 \le \dots \le f\_n$. Let $OPT(i)$ be the maximum total weight of non-overlapping jobs in $\\{1,2, \cdots ,i\\}$, $p\_i$ be the largest index $j \< i$ such that job $j$ and $i$ are compatible. Then we see that $$OPT(i) = \max\\{{w\_i + OPT(p\_i), OPT(i-1)}\\}$$

**My question**: I think I could understand why this DP algorithm works. However I didn't see the necessasity for the sorting step. What if we sort the finish time in ascending order instead? As far as I can see, it's also correct.

# Answer
> 4 votes
**Simple answer** No, we cannot sort start time in ascending order to get a reasonable dynamic programming algorithm.

**A counterexample**

As illustrated above, we are given four jobs aligned in order of ascending start time, each labeled with its wight. Though some computation, we have $p\_4=3$ and $OPT(4)=1+OPT(3)$. By definition, $OPT(3)$ equals to the optimal value in $\\{1,2,3\\}$. By selecting job $1$ and job $2$, $OPT(3)$ is maximized and is equal to $3$. Then the optimum subset of the four jobs would be $\\{1,2,4\\}$, which is not a compatible set.

**Necessity** for sorting by finish time in ascending order: By sorting finishing time in ascending order, we ensure that for job $i$, $\\{1,2,\dots, p\_i\\}$ is compatible with $i$ since they all finish before the start of $i$. But if we sort start time in ascending order instead, we cannot ensure that. As shown in above counterexample, $p\_{4} = 3$, thus $\\{1,2,\dots, p\_4\\}=\\{1,2,3\\}$ is not compatible with $4$. Suppose that $i$ is in the optimal solution $\mathcal{O}\_i$ for $\\{1,2,\dots, i\\}$, then the optimal solution $\mathcal{O}\_{p\_i}$ for $\\{1,2,\dots, p\_i\\}$ is also included in $\mathcal{O}\_i$. specifically, we have $\mathcal{O}\_{i} = \mathcal{O}\_{p\_i}\cup \\{i\\}$. Since we couldn't ensure that $i$ and $\mathcal{O}\_{p\_i}$ are compatible, we may get an invalid solution, which also can be seen from above counterexample.

# Answer
> 0 votes
Sorting step is necessary however like you mentioned, it can be sorted in ascending order too. Just that the traversal will have to be from end to beginning then (instead of descending sort which has beginning to end traversal)

---
Tags: algorithm-analysis, dynamic-programming, scheduling
---


# Question
Title: Practice question on the applications of flows and cuts
This question is from Erickson's textbook on algorithms, p. 376, question 18.

> Faced with the threat of brutally severe budget cuts, Potemkin University has decided to hire actors to sit in classes as “students”, to ensure that every class they offer is completely full. Because actors are expensive, the university wants to hire as few of them as possible.
>
> Building on their previous leadership experience at the now-defunct Sham-Poobanana University, the administrators at Potemkin have given you a directed acyclic graph $G = (V, E)$, whose vertices represent classes, and where each edge $i \rightarrow j$ indicates that the same “student” can attend class $i$ and then later attend class $j$. In addition, you are also given an array $cap\[1\cdots V\]$ listing the maximum number of “students” who can take each class. Describe an analyze an algorithm to compute the minimum number of “students” that would allow every class to be filled to capacity.

My best solution is $O(cV^3)$, where $c$ is the max of class capacities $\max\_i \\{ cap\[i\] \\}$. **Is there a better solution?** Because I have a feeling there is.

---

**My solution:**

1. Initialise $x$, the minimum number of students to fill each class to capacity, as 0.
2. For each vertex $i, j$ where $i \neq j$, combine all the $i \rightarrow j$ edges into a single edge with capacity equals the number of original $i \rightarrow j$ edges.
3. Set the capacity of each vertex $v$ as $cap\[v\]$.
4. Since this is a DAG, there are source vertices and sink vertices. Add a vertex $v\_\text{in}$ with outgoing edge of infinite capacity to each source vertex. Add outgoing edge of infinite capacities from each sink vertex to a another new vertex $v\_\text{out}$.
5. Find the max $(v\_\text{in}-v\_\text{out})$ flow. $|f|$. Increment $x$ by this value $|f|$. Decrement the capacity of each vertex and edge in the graph by the component flow through it.
6. Remove $v\_\text{in}, v\_\text{out}$, and their edges. Remove all vertices and edges with capacity zero.
7. Repeat steps 4 to 6 until no vertices are left in the graph.

**Time complexity:**

This solution runs Orlin's $x$ times, but $x$ is bounded from above by the maximum of class capacities, previously denoted $c$. So, $O(cVE) = O(cV^3)$.

# Answer
You can use the min-cost max-flow algorithm to solve this more efficiently. (The Ford Fulkerson algorithm is only changed slightly to achieve this for DAGs). In your graph construction, instead of adding edges from a dummy source to all "source-vertices" on the original graph, add them to all vertices instead; do the same for the dummy sink.

For each edge added from the dummy source, give it some positive cost and keep the cost of all other edges 0. With this new graph, solve the min-cost max flow problem to get the desired result.

min cost max flow has the same complexity as max flow so your answer should be $\mathcal{O}(V^3)$.
> 2 votes

---
Tags: algorithms, graphs, algorithm-analysis, network-flow
---


title: Tiling a simple polygon with hexagons

text:
# Question
Title: Tiling a simple polygon with hexagons
Let $T$ be a hexagonal tiling of the plane and assume we are given a simple polygon $P$ (we define $P$ as the union of the points on its boundary and its interior). The task is to find the subset of $T$ that intersects $P$ as fast as possible.

We can assume that the diameter of the hexagons are some fixed constant $c$, and that $c$ is proportional to the area or perimeter of $P$ if this makes things easier.

For instance, is it possible to derive an algorithm that does this in time polynomial in the perimeter or area of $P$?

I previously posted this on Math.SE, and received the following comment from Cheerful Parsnip:

> One idea: first find a single hexagon that meets the polygon. Then do breadth first search on the set of adjacent hexagons to keep enlarging the set of hexagons that meet the polygon.

However the complexity (and correctness) of doing so is not clear to me.

# Answer
> 1 votes
Checking if two polygons intersect is equivalent to checking if a point lies inside their Minkwoski sum. Illustration with a triangle:

The Minkowki sum of a polygon and a convex hexagon is found in linear time in the number of vertices (see http://acg.cs.tau.ac.il/courses/algorithmic-robotics/spring-2011/slides/ms.pdf, slide 16).

Now the problem is reduced to finding all points of a regular grid that fall inside a polygon. You can do that by triangulating the polygon, in time $O(n\log n)$ by sweepline (in theory $O(n)$ is possible for a simple polygon, but not in practice).

Then finding the range of grid lines that cross a triangle is done in constant time, these lines are enumerated in time equal to their number (triangle height over grid spacing), and the internal grid points are enumerated in time equal to their number (triangle area over grid cell area).

# Answer
> 0 votes
Yes, you can do it in approximately $O(\mathcal{A} + \mathcal{P} + n \log n)$ time, where $\mathcal{A}$ is the area of $P$, $\mathcal{P}$ is the perimeter of $P$, and $n$ is the number of vertices, using a sweep-line algorithm.

Sweep a vertical line, from left to to right. We have an event at each vertex of $P$ and at every $c/2$ units (representing the centers of the hexagons). At each time instant, the vertical sweepline is somewhere, and we keep track of all edges or vertices of $P$ that intersect the sweepline, stored in sorted order based on their $y$-coordinate. Assuming we're given all of the vertices of $P$ in sort order around its perimeter, it is easy to maintain the sweepline at each step. Now whenever the sweepline touches the center of hexagons, it is easy to enumerate all hexagons that intersect $P$ and intersect the sweepline.

If you store the edges/vertices that intersect the sweepline in a self-balancing binary tree, you can update them in $O(\log n)$ time each time the sweep line advances to a new vertex of $P$; and in each step, you can enumerate the hexagons that intersect $P$ and the sweepline in time linear in the number of such hexagons. The total number of hexagons that are outputted by this algorithm is linear in $\mathcal{A}+\mathcal{P}$, so the total running time is $O(\mathcal{A}+\mathcal{P} + n \log n)$.

There might be ways to do it in linear time (e.g., using polynomial triangulation or something). I am not sure.

---
Tags: algorithms, reference-request, computational-geometry
---


# Question
Title: Recurence Relation, specifically understanding substitution rule used
This is a pretty vague question and can be applied to many math problems not just recurrence relations.

Above I fully understand, setting up the recurrence relation from the algorithm given. And how the next step would be plugging and chugging to find a pattern that we can use.

So as shown above, we do not know what `M(n-1)` is but we do know what `M(n)` is equal to. So every guide just makes `M(n) -> M(n-1)` by substracting `1` in the original `M(n)` and then substracting `1` in `M(n-1)` as well, making the new equation `M(n-1) = M((n-1)-1)+1` so now we "know" what `M(n-1)` is now and can substitute it in the original equation `M(n) = M(n-1)+1 ---> M(n) = [M((n-1)-1)+1]+1` . And this is where I have my question, to me this seems like math magic just subtracting `1` inside the `M(n)` parenthesis only, what substitution rule is being used here? Am I just horribly overthinking it?

# Answer
$$M(n)=M(n-1)+1$$

can be written

$$M(k)=M(k-1)+1$$

or with any other expression as the argument. E.g.

$$M(n-1)=M(n-1-1)+1.$$

By combining,

$$M(n)=M(n-1)+1=M(n-1-1)+1+1.$$

Repeating,

$$M(n)=M(n-1-1-\cdots1)+1+1+\cdots1.$$

In the end,

> $$M(n)=M(0)+n.$$
> 0 votes

# Answer
I don't know exactly what the question is. Plugging in is mainly used to see the pattern, in your case you might have noted that $M(1)=1$, $M(2)=2$, and so on.

If you want to prove that $M(n)=n$, it's easiest to proceed with induction. The base case is already stated in your first figure and the inductive step isn't very hard either.

But the most difficult thing is often to find a non-recurrent version of $M$ to prove the equivalence to, and her unrolling helps.
> 0 votes

---
Tags: algorithm-analysis, recurrence-relation
---


# Question
Title: What is the asymptotic runtime of the below equation?
What is the asymptotic of ${n \choose 3} \log ^4n$ ? I know that ${n \choose 3}$ is in $\cal O (n^3)$, but what about the term $log^4n$ and what about the product of the two?

# Answer
Let us establish a product rule.

Assume that $F(n)=O(f(n))$ and $G(n)=O(g(n))$. This means that

$$\exists N\_f,c\_f:\forall n\ge N\_f: F(n)\le c\_f f(n),$$ $$\exists N\_g,c\_g:\forall n\ge N\_g: G(n)\le c\_g g(n).$$

From this we draw that, with $N=\max(N\_f,N\_g)$ and $c=c\_fc\_g$

$$\exists N,c:\forall n\ge N: F(n)G(n)\le c f(n)g(n).$$

---

Notice that a similar proof holds for the addition.
> 0 votes

# Answer
N over 3 is O(n^3), and log^4(n) is log^4(n). The whole formula is O(n^3 log^4 n). That’s it. Can’t be simplified any further.

It’s asymptotically less than O(n^(3+eps)) for any eps \> 0, or less than O(n^3 log^(4+eps) n) or O(n^3 log^4 n log log log n).
> 0 votes

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


# Question
Title: is it possible to compress a sequence of progressive unique numbers dramatically?
Let's say I have a 60 set of numbers from **0-100,000** so like `[81, 98, 115, 189, 254, ... , 97866, 98441, 99671]` all unique and progressively increasing. Would it be mathematically possible to compress this sequence by 80-90%? so far I've tried gzip which only compresses at 50% and other algorithms the best one I found was at 0.68% almost 0.69%. Though I have not tried mixing this algorithms together to get to 80-90% but is this mathematically possible?

The current limit I am currently trying to achieve is a byte representation that is below the number of sets I have. So for example this set `[81, 98, 115, 189, 254, ... , 97866, 98441, 99671]` can be translated to something with the size of 50 bytes that is below 60 so that would do great for me

also I know of subtracting the lower value to the other value, example : \[81, 98, 115\] → \[81, 17, 17\] but this doesn't really work for what I am after.

# Answer
From a counting point of view, there are $\binom{100000}{60}$ such sequences and so, numbering them, you could theoritically compress it down to $\log\_2\binom{100000}{60}$ bits but not further. This is roughly equal to 90 octets.
> 4 votes

# Answer
To expand on Nathaniel's answer, you can number the subsets efficiently using the combinatorial number system.

In short, say your subset is $\[c\_1, c\_2,\ldots, c\_k\]$ (where $k=60$). Compute $N = \binom{c\_1}{1}+\binom{c\_2}{2}+\ldots+\binom{c\_k}{k}$. (note that we use the convention that $\binom{n}{m} = 0$ for $n\<m$). This number $N$ represents your subset, and you can simply store that.

Now the other way around, we want to be able to recover the subset from this number $N$. We'll start by finding the maximum value $c\_k$. To do so, find the largest value of $c$ among $k-1,k,k+1\ldots$ for which $\binom{c}{k} \leq N$. This is the largest element in the subset (i.e. this is $c\_k$). Now replace $N$ with $N-\binom{c\_k}{k}$, then replace $k$ with $k-1$ and repeat the procedure until $k$ reaches $0$.

To make this efficient (time wise) you might want to give some thought about how you compute the binomial coefficients. Perhaps the most hassle-free approach is to compute them when needed by a recursive function with memoization (that way you can harvest some of the computation done for previous binomial coefficients when computing a new one, and don't spend too much time computing coefficients you won't end up needing).
> 1 votes

---
Tags: data-compression
---


# Question
Title: Fast identification of prime power factors?
For a given integer exponent $e$, I want to identify all factors of an integer $n$ which are of the form $p^{e}$, where $p$ is a prime. So, for $e = 1$, this is equivalent to getting the unique prime factors, for $e = 2$ it's extracting all of the square factors, etc.

Currently, I am doing this by iterating over the powers of primes and doing trial division; that gets cheaper as $e$ gets larger, as there are fewer prime powers small enough to be candidate factors; given that factoring in general can be done more efficiently than just using trial division, is there an obvious way to speed up this restricted case?

# Answer
> 4 votes
In the worst case, this is probably about as hard as factoring. As far as we know, factoring squarefree integers is about as hard as factoring integers in general, so for the case $e=1$, this is likely to be about as hard as factoring. And, of course, it isn't any harder than factoring, since factoring immediately gives you the answer to your problem.

Factoring is hard for large numbers, but if the number isn't too large, then it's feasible to use a standard factoring algorithm to factor the number and then find the $e$th powers. This will be far faster than doing trial division with powers of primes for small values of $e$.

For sufficiently large values of $e$, trial division by small primes will be faster. (It's probably best to use trivial division to find small prime factors, then for each small prime factor, test if the corresponding prime power is a divisor.) But better still is to use ECM factoring to find all small prime factors of $n$, then for each small prime factor $p$, test if $p^e$ is also a factor. (You might use trial division to check for very small prime factors first, before running ECM.) ECM factoring is the state-of-the-art method to find small factors of a large number.

References:

# Answer
> 1 votes
If you don’t want to do anything more difficult than trial division:

For the exponent 1 this is practically the same as factoring.

For an exponent e \>= 2: You can use trial division by primes 2, 3, 5 etc and when you find a prime factor, you check if it is a high enough exponent, and remove the factor from the number.

But when you would check if your number x is divisible by p, and p^(e+1) \> x: x might be a prime raised to the power e, so you check if x is an exact e-th power, and if it is you have found a p which can be raised to the power e.

If x is not an e-th power, then the smallest number with a factor p^e but not an e-th power would be the number p^(e+1) \> x, so there is no power of e is a factor.

Say we have e=4 and x about 10^15: Once we want to test p \> 1000 where p^5 \> x, we check whether x is a 4th power like x = a^4 in which case a is the remaining 4th power factor, or there is no fourth power factor.

If we didn’t eliminate smaller prime factors, then we would in the case e=4 have to check until 2p^4 \> x, in this case about p = 4800. And finding smaller prime factors reduces x.

But when you check the prime p after eliminating all smaller prime factors, then the smallest numbers with a factor q^e are q^e itself

---
Tags: primes, factoring
---


# Question
Title: Set of Turing machines that accepts at least one input in bounded time
What is known about the languages:

$$S\_f = \\{ \[M\] \ | \ \exists{x} \ \text{s.t.} \\ M \ \text{accepts} \ x \ \text{in} \ f(|\[M\]|) \ \text{steps}, \\ \ |x| \leq f(|\[M\]|) \\}$$

I used to think that in order to check whether a string $\[M\]$ is in $S\_f$ you cannot avoid simulating $M$ on all possible $x$ whose length is less than $f(|\[M\]|)$.
But for a polynomial $f$, verifying a candidate solution $x$ takes polynomial time so that $S\_f \in NP$, while trying all of them is exponential, which would prove $P \neq NP$ ...

So my reasoning is spectacularly wrong, but I can't find out why:

1. Maybe $S\_f$ is in fact not in $NP$ when $f$ is polynomial?
2. Maybe it is possible to check whether a string $\[M\]$ is in $S\_f$ without trying most of the possible $x$?
3. Something else?

# Answer
> 1 votes
Your reasoning is wrong because you assert something without proof. You just assert that the only way to do it is to try all $x$, but there is no justification given for this assertion, and we don't know whether that assertion is true. Just because you can only think of one way to solve a problem, doesn't mean it is the only way. There could be another way that you haven't thought of yet. As you indicate, given the relationship to the P vs NP question, your assertion amounts to assuming something that we don't have a proof of. It'd be like saying "Well, P is different from NP, because the only way to solve a NP-complete problem is to try all possible solutions". We have no proof of such a claim (and indeed, such a claim is unlikely to be true).

You might also be interested in the strong exponential time hypothesis. That too is unproven, but it represents a more precise formalization of a conjecture that might well be true, and is closely connected to the topic you are asking about.

---
Tags: complexity-theory, time-complexity, turing-machines, p-vs-np
---


# Question
Title: Logical Consequence - Equivalent Assertions
I have the following slide in my notes and I'm having trouble understanding how the three assertions are equivalent. I understand to a degree how the 2nd and 3rd assertions are equivalent, but the equivalence between the 1st and 3rd as well as the 1st and 2nd isn't really explained well here. Am I missing something? Is the first exercise relevant to this problem?

# Answer
Yes they all are equivalent. Using **standard rules of inference i.e. Modus Ponen, Modus Tollen, Hypothetical syllogism and Fallacies**, which are just ways to infer logical consequences of a set of formulas, you can resolve a set of clauses(formulas) to get a resolvent. In this case using the rules of inference, one needs to arrive at the given resolvent clause $G$ to show that it is satisfiable.

Let's try to prove $Q$ is a logical consequence of $\left \\{ P, P\rightarrow Q \right \\}$ using all three methods.

**Method 1**

$\left \\{ P, P\rightarrow Q \right \\} = \left \\{ P, \sim P\vee Q \right \\}$.

Taking Logical AND of these clauses we get

$P\wedge \left ( \sim P\vee Q \right )\Rightarrow \left ( P\wedge\sim P \right )\vee \left ( P\wedge Q \right )\Rightarrow P\wedge Q$.

Here we get the $Q$ as one of the resolvents which is enough to prove that $Q$ is a logical consequence of the given set of formulas, why you may ask, because you started with a conjunction of a set of formulas and ended up with another conjunction of a set of formulas, using laws of logic, and if the former was true the latter has to be true and hence $Q$ is true as well. Similarly $P$ is a logical consequence, although a trivial one.

**Method 2**

We go by the definition, and using above calculations we arrive at $ P\wedge Q$. Now we need to check $ P\wedge Q\rightarrow Q $

$\left ( P\wedge Q \right )\rightarrow Q \Rightarrow \sim \left ( P\wedge Q \right )\vee Q\Rightarrow \sim P\vee \sim Q\vee Q\Rightarrow T$

**Method 3**

Again by definition, and using above calculations we arrive at $P\wedge Q\wedge \sim P\Rightarrow Q\wedge F\Rightarrow F$. This is simply negation of the formula used in method 2.

For method 2 and 3 yes you can use the truth table and yes it is tedious so you can use laws of logic, but even using that you'll end up with additional steps to prove it completely(as done in calculations above), and hence we have the standard rules of inference which help you come to the conclusion in a much more concise manner.
> 0 votes

---
Tags: satisfiability, artificial-intelligence, sets, propositional-logic, equality
---


# Question
Title: Search for largest element in 1st monotonic subarray with an array consisting of 3 monotonic subarrays
Consider an array A\[1..n\] that first increases up to some point p then it decreases until some point q and then increases again. That is A\[k\] \< A\[k + 1\] for all k in \[1..p\] and \[q..n\] and A\[k\] \> A\[k + 1\] if p \< k \< q.

Suppose we are searching for the element A\[p\] or the index p, whats the fastest possible algorithms

My Approach: For a similar problem with 2 consecutive monotonically increasing and decreasing arrays you could apply binary search to find the element with the condition A\[p\]\>A\[p-1\] and A\[p+1\]. Even though the condition still holds true for 3 consecutive monotonically increasing and decreasing sub arrays, it would not be possible to aim search at left or right from the mid point in a binary search.

A linear search based approach is obvious but is it possible to do this with lesser complexity?

# Answer
> 2 votes
No. It can't be done in sublinear time. I'll prove that any algorithm whose worst-case running time is $n/3-1$ or less, must be incorrect on some input. It follows that every correct algorithm has worst-case running time at least $n/3$, i.e., at least linear.

Consider any deterministic algorithm whose worst-case running time is $n/3-1$ or less. Consider running this algorithm on the array $\[1,2,3,\dots,n\]$ until termination. Because its worst-case running time is less than $n/3$, it follows that the algorithm examines less than $n/3$ elements of the array. This implies that there must exist three adjacent elements of the array it hasn't looked at, let's call them $A\[u\]$, $A\[u+1\]$, and $A\[u+2\]$. Since the algorithm hasn't looked at them, we can replace the values of those elements arbitrarily, and the algorithm will produce the same output regardless of how we change them. Now consider the two inputs $\[1,2,\dots,u,0,u+2,u+3,\dots,n\]$ and $\[1,2,\dots,u,u+1,0,u+3,\dots,n\]$. By the previous remarks, the algorithm yields the same output on both inputs. However, the correct answer for these two inputs is different (the correct answer is $u-1$ for the first and $u$ for the second). It follows that the algorithm produces the wrong output for at least one of these two inputs, i.e., there exists an input where this algorithm is incorrect.

This proof technique is sometimes known as an "adversary argument". We come up with an "adversary" that constructs inputs that the algorithm is sure to handle incorrectly.

# Answer
> 0 votes
After some arguments why you can't generally do better:

What if $A\[n\] \lt A\[1\]$?
Every element smaller $A\[1\]$ is to the right of $p$, every element greater $A\[n\]$ is to the left of $q$.

---
Tags: algorithms, algorithm-analysis, search-algorithms
---


# Question
Title: Implementation check for Kruskal's algorithm used for maze generation
I have a pathfinding project and I want to use Kruskal's algorithm as a maze generator. I am using a rank-based disjoint set data structure to detect cycles, which seems to be the standard way.

However, the mazes that I generate cannot be solved. Which leads me to think that there might be something wrong with my implementation logic.

```
init_walls() //m by n grid of walls
MST = {}

add each node to MST

while MST is not empty
    node = random_node()
    neighborNode = random_neighbor(node) //up, down, left or right

    if find(node) not equal to find(neighborNode)
        convertWallToPassage(neighborNode)
        union(node, neighborNode)

    delete node from MST

```

`find` and `union` are standard operations in the disjoint set used to detect cycles. If two nodes have the same parent, then they are in the same set and hence forms a cycle. I wonder if there is a gap in my logic, or is my approach flawed?

# Answer
> 1 votes
Kruskal's algorithm iterates through edges, not through vertices. I think it would be better if it looked like:

```
init_walls() //m by n grid of walls

W = set of all walls
p = 0 //counting the number of passages created

While p < m × n - 1
      (u, v) = random_wall()

      if find(u) ≠ find(v)
           convertWallToPassage(u, v)
           union(u, v)
           p = p + 1

      delete (u, v) from walls

```

Here, $m\times n$ represents the number of nodes in an $m$ by $n$ grid. You could use the halting condition `W is empty`, but it is well known that a connected acyclic graph has one more node than edges.

---
Tags: shortest-path, maze
---


# Question
Title: Algorithm to find if there exists an assignment such that all equality and inequality constraints are satisfied
I have a problem in a Data Structures course I am taking. The question is as follows:

Given a number of variables $x\_1,\dots,x\_n$ and given $m$ equality and inequality constraints (in total $m$ constraints). Find if there exists a valid assignment that satisfies all constraints in $O((m+n)\log^\*n)$ and in $O(m+n)$.

For example $x\_1=x\_2,x\_2=x\_3,x\_1\neq x\_3$ doesn't have a valid assignment.

I believe this question is a known one but I can't find it's name or know what to search for.

My idea is:

1. Assign a $null$ value to all variables.
2. For each $1\le i \le n$:

* If $x\_i=null$ then assign $x\_i \leftarrow i$.
* Go over all of $x\_i$ equality constraints and assign for each index $j$ the value $x\_j \leftarrow x\_i$.

3. Go over all of the inequality constraints and check if they hold. If at least one doesn't hold, return that there is no such valid assignment. If all of them hold return the current assignment that we have.

Using that algorithm we can guarantee that all equality assignment will be satisfied. Thus checking if the inequality assignments hold is enough to check if a valid assignment is possible.

Analyzing this algorithm. Let $m\_i$ be the number of equality constraints on $x\_i$ and let $m\_i'$ be the number of inequality constraints. Therefore $\sum\_{i=1}^{n}(m\_i + m\_i')=m$. The first step costs $n$ operations. The second step costs $\sum\_{i=1}^{n} m\_i$. The third step costs $m-\sum\_{i=1}^{n} m\_i$.

In total we get $n + (\sum\_{i=1}^{n} m\_i) + (m - \sum\_{i=1}^{n} m\_i)=n + m\in O(n+m)$.

I am not sure if this satisfies the second request of the question as I am not sure my calculations are valid. I would appreciate if someone can refer me to a source on this question or tell me if my calculation is correct. I would also appreciate if someone can help me offer a solution that'll take $O((m+n)log^\*n)$.

Thanks in advance.

# Answer
Your algorithm may fail in some situations.

For example, $x\_1=x\_2$, $x\_2=x\_4$, $x\_3=x\_4$, and $x\_1\not=x\_2$.

1. $i=1$, $x\_1\leftarrow1$, $x\_2\leftarrow1$.
2. $i=2$, $x\_4\leftarrow1$.
3. $i=3$, $x\_3\leftarrow3$, $x\_4\leftarrow3$.
4. $i=4$, $x\_2\leftarrow3$.

At the end, the only inequality $x\_1\not=x\_2$ is satisfied. So your algorithm will not report that "there is no such valid assignment".

---

For this exercise, you are supposed to use disjoint data structure.

Consider the set that contains $1,2,\cdots, n$. For $i$ from $1$ to $n$, let $\text{parent}(i)=i$.

Process all equalities first. For each equality $x\_j=x\_j$, join $i$ and $j$.

Then for each inequality $x\_i\not=x\_j$, check if $\text{find}(i)\not=\text{find}(j)$. If both sides are equal, return "there is no such valid assignment".

If the algorithm has not returned yet, return the assignment where $x\_i\leftarrow \text{find}(i)$ for all $i$.

---

The algorithm runs in $O((m+n)\log^\*n)$ time, assuming the $\text{find}$ operation is implemented properly.
> 0 votes

# Answer
To complement John L.'s $O((m+n)\log^\*n))$ solution, here is a simple $O(n+m)$ time solution:

Construct the graph $G$ (as an adjacency list structure) whose vertices correspond to your variables and edges correspond to equality constraints. Compute the connected components of this graph and a an array which to each variable index associates a number corresponding to its component.

Now for each inequality constraint, check if the two variables are in different components of $G$. If that is always the case then there is a satisfying assignment (which is actually given by the array you computed), otherwise there isn't.
> 1 votes

---
Tags: algorithms, data-structures
---


# Question
Title: Show this 2D Grid Set Cover-ish problem is NP-Complete?
Given a $n \times m$ rectangular grid of cells each with an integral weight: $w\_{i,j}$ and two integer parameters $w \ge 2$ and $h \ge 2$ (for group width and height respectively). Select the subset of cells that maximizes the combined weight of the selected cells and is constrained such that each selected cell is a part of at least one fully selected 'group' of size $w \times h$.

For example, if in the following 5x5 grid of weights we are required to select 2x2 groups of cells ($n = m = 5, w = h = 2$) We can use the selection on the right to get the maximum value of 13.

This specific small example hides a bit of the complexity of the problem which arises when individual 'groups' need to work together to overcome negative weights in their overlap, and when $w$ and $h$ are larger.

How can I show that the decision problem variant of this optimization problem is NP-Complete? Is it possible when $w = h = 2$ or do they have to be larger?

---

This problem can be cast as a straightforward integer programming problem. For example using an auxiliary variable on each group (there would be $n-w+1 \times m-h+1$ of these auxiliary variables), and having two sets of constraints first saying that each group can only be selected if all of its constituent cells are selected and secondly saying that each cell can be selected if at least one of its containing groups is selected. This is of course not really relevant to showing the problem is NP-complete though.

This does seem very similar to a set cover-ish problem and I've tried from that angle for a bit with no success. The part that I've struggled with is the restriction on the sets themselves how they consist of overlapping areas. If the 'groups' were arbitrary (not rectangular) then it is much easier to show as NP-complete.

I have played a little bit with a dynamic programming solution (which could disprove that it is NP-complete!), but I was only able to get that to work for the one dimensional case.

I am also interested in any references to problems like this.

# Answer
> 0 votes
A straightforward reduction follows from Fowler, Paterson, and Tanimoto "Optimal packing and covering in the plane are np-complete" 1981.

The details are in the paper. Summarized: To transform 3-SAT into this problem fill a large grid with negative values, then place large positive valued cells in specific locations. Using $w=h=3$ we can create a situation where the positive valued cells create 'loops' of even numbered cells which correspond to literals. The clauses correspond to specific cells which will be covered by one of the loops if satisfied, or else require an additional 3x3 area to be selected if not satisfied (thereby reducing the total value). In fact, an efficient algorithm for this particular problem would identify not only if a satisfying result existed for any 3-SAT instance - but also the 'most satisfying' result.

---
Tags: np-complete, reductions
---


# Question
Title: What is the difference between available expressions analysis and very busy expressions analysis?
I am having trouble understanding the conceptual meaning of the two kinds of analysis. I know the equations and how to solve the problems and I know how one is a forward data-flow analysis while the other is a backwards data-flow analysis, but there is still something missing in the explanations I have seen so far, in a higher level.

# Answer
The difference is in the Gen for these Analyses.

Gen(VBE) :

gen VBE (\[x = e ;\] l ) = AExp(e)

gen VBE (\[while (b) … \] l ) = AExp(b)

gen VBE (\[if (b) … \] l ) = AExp(b)

gen VBE (\[… \] l ) = ∅

Gen(AE) :

gen AE (\[x = e ;\] l ) = {a’ ∈ AExp(e) | x not in vars(a’ ) }

gen AE (\[while (b) … \] l ) = AExp(b)

gen AE (\[if (b) … \] l ) = AExp(b)

gen AE (\[… \] l ) = ∅

Thus, for a statement: **x = x + y**

**x + y** is generated for VBE but not for AE.
> 0 votes

---
Tags: static-analysis
---


# Question
Title: reverse single edge in DAG and keep it a DAG
If I reverse a single edge in a DAG, how can I efficiently propagate the effects of that (e.g. change other edges) such that I don't introduce any cycles by said reversal? Is there a named algorithm for this that I should look up? I see some other questions about reversing an entire DAG; I'm only concerned with a single edge plus its necessary influence, which I hope is not the entire graph in a typical case.

To add more context: I'm working with some disjunctive job-shop representations. Example: https://acrogenesis.com/or-tools/documentation/user\_manual/manual/ls/jobshop\_def\_data.html . I want to minimize the number of updated edges. And after the update, I still need all of the nodes in the graph to be accessible through some path.

# Answer
> 0 votes
I would suggest the following:

If you know a topological sorting $(s\_0, …, s\_{n-1})$ of your DAG and you want to reverse the edge $(s\_i, s\_j)$, $i \< j$:

```
Input: DAG G = (S, A), topological sorting (s0, s1, …, s{n-1}), indices i < j

for each k from i to j - 1 do
    if (s_k, s_j) ∈ A then reverse (s_k, s_j)

```

Given the definition of the topological sorting, the resulting graph would be a DAG. Indeed, the order $(s\_0, …, s\_{i-1}, s\_j, s\_i, s\_{i+1}, …, s\_{j-1}, s\_{j+1}, …, s\_{n-1})$ would be a topological sorting.

# Answer
> 1 votes
I believe this can be formulated as a min-cut problem, and thus solved with an algorithm for max-flow.

Suppose you want to reverse the edge $s \to t$, and turn it into the edge $t \to s$. That will pose a problem for every other path $s \leadsto t$, because each such path will create a cycle in the graph. So, we can reformulate the problem as follows. Delete the edge $s \to t$. Now, find a minimum set of edges to remove, so that if we remove them, there are no remaining paths $s \leadsto t$.

This is exactly a min-cut problem. In particular, this is the problem of finding a $(s,t)$-minimum cut in the graph (after deleting the edge $s \to t$, and treating each remaining edge as having capacity 1). Thanks to the max-flow min-cut theorem, you can solve such a min-cut problem with any algorithm for max flow.

---
Tags: graphs, dag
---


title: Proving that this matching is stable

text:
# Question
Title: Proving that this matching is stable
Consider the stable marriage problem with $n$ men and $n$ women. Let $A$ and $B$ be two stable matchings, and suppose that we form a new matching $C$ by assigning to each men his favorite partner between the ones he gets in $A$ and $B$. Prove that $C$ is also a stable matching.

This is my attempt. I'm stuck at proving that there are no unstable pairs. By contradiction, let $(m\_1, w\_1)$ and $(m\_2, w\_2)$ be the unstable pair in $C$, i.e., $m\_1$ prefers $w\_2$ over $w\_1$ and $w\_2$ prefers $m\_1$ over $m\_2$. I think we have to consider two cases: when $(m\_1, w\_1)$ and $(m\_2, w\_2)$ happen in the same matching or in different ones, but I don't know what to do from here.

# Answer
First, you need to prove that $C$ is a matching: suppose it is not a matching. That means that there exists two men $m\_1$, $m\_2$ matched with the same woman $w$.

It follows that, without loss of generality, $m\_1$ is matched with $w$ in $A$ and $m\_2$ is matched with $w$ in $B$. Without loss of generality again, suppose $w$ prefers $m\_1$ to $m\_2$.

Then it means that $B$ is not stable, because $m\_1$ prefers $w$ to its partner in $B$, and $w$ prefers $m\_1$ to $m\_2$. We conclude that $C$ is indeed a matching.

Second, you need to prove that $C$ is stable: suppose it is not stable. Let $(m\_1, w\_1)$ and $(m\_2, w\_2)$ be the unstable pair in $C$, i.e., $m\_1$ prefers $w\_2$ over $w\_1$ and $w\_2$ prefers $m\_1$ over $m\_2$. WLOG, $(m\_1, w\_1)$ was a pair in $A$. Two cases are possible:

* either $(m\_2, w\_2)$ was also a pair in $A$ (can you see the contradiction?);
* or $(m\_2, w\_2)$ was a pair in $B$. Consider then $w\_3$ such that $(m\_1, w\_3)$ is a pair in $B$. Again, can you see the contradiction? (what is the ranking of $w\_1$, $w\_2$ and $w\_3$ for $m\_1$?)
> 2 votes

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


# Question
Title: Why HC-k-regular-(n-even) being NP-Complete implies HC-k-regular is NP complete?
In \[1\], Corollary 2.3, after proving that HC-k-(n-even) for a fixed k \>= 3, the paper says that HC-k-regular being NP Complete is *an inmediate consequence of the former*.

Where: HC-k-regular-(n-even) means if the graph has a hamiltonian cycle in a k-regular graph with an even number of nodes.

And HC-k-regular means the graph has a hamiltonian cycle in a k-regular graph.

I don't understand how or why "HC-k-regular-(n-even) is NP Complete" implies "HC-k-regular is NP Complete". Why graphs with odd number of nodes are not considered in an explicit way?

---

\[1\] Complexity of the hamiltonian cycle in regular graph problem

# Answer
> 2 votes
Hmmm, I think by definition "HC-k-regular-(n-even) is NP-Complete" implies "HC-k-regular is NP-hard", since every NP problem can be reduce to an instance of HC-k-regular-(n-even) problem, which is also a HC-k-regular instance. Together with the obvious result that "HC-k-regular is NP", we can get the conclusion "HC-k-regular is NP-Complete". More intuitively, it's something like "${\sf SAT} \cup 0^n$ is NP-Complete".

---
Tags: graphs, np-complete, hamiltonian-circuit
---


# Question
Title: Is it true that everything is a side effect in C?
I'm just a beginner, I've started learning programming, CS, math, and Unix. I know how to code in Pascal and also study C. In the university a professional programmer, who teaches coding, said that literally everything in C is a side effect.

> Accessing a volatile object, modifying an object, modifying a file, or calling a function that does any of those operations are all side effects, which are changes in the state of the execution environment.(from the internet)

And he says that even printf() has a side effect. E.g.

```
printf('Hello, world\n');

```

returns 13 and also prints "Hello, world", or that there's no "assignment statement" in C, only "assignment operator/operation", so we can do thing like this:

```
x = (y = 1) - 3;

```

which actually causes a side effect. It's not the same as

```
a := b;

```

in pascal. Or this:

```
a[foo(x)] += y;

```

is not the same as

```
a[foo(x)] = a[foo(x)] + y;

```

because foo(x) might return different numbers.

It confuses me. I know that side effects are not usually good because it muddles readability of the code and sometimes makes it behave unexpectedly. Please, clarify what actually happens here.

# Answer
I found the following definition, which IMO is relevant:

"A side effect is when a function relies on, or modifies, something outside its parameters to do something. For example, a function which reads or writes from a variable outside its own arguments, a database, a file, or the console can be described as having side effects."

The operations listed fall in this category.

---

As regards the assignment, I would rather say that the C assignment is an *operator*, as it creates an expression with an rvalue (like c= a + b, c= (a = b) has meaning). Pascal's assignment is an *operation*. I would not say that assignment in itself has (or is ?) a side effect.
> 2 votes

---
Tags: programming-languages, c
---


# Question
Title: Faster Algorithm for sampling a point from the array
Let $M$ be a collection of elements given in the form of the array such that membership of any element can be done in $O(1)$ time. Which means elements of array $M$ are $\\{1,2,\cdots,n\\}$ such that $1$ is stored at $M\[1\]$ and $2$ at $M\[2\]$ and so on. The goal is to sample an element from the array $M$.

Note that we have to design an algorithm multiple times (say $k$ times) in such a way that in each repetition we get a different element as a result.

Sampling means the probability of picking any element from $M$ is $\frac{1}{|M|}$.

My idea is as follows: create another array $F:=\[\frac{1}{|M|},\frac{1}{|M|},\cdots,\frac{1}{|M|}\]$, which means assigning equal weights to each element.

There are several existing algorithms now which can sample an element from $M$ in expected time $O(1)$ (Say Algorithm 1 Algorithm).

If I run the same algorithm 1 again then the same element may get picked so I have to update something in the array $F$ this update should be in $O(1)$ time.

*I am looking for an algorithm that gives $O(k)$ time for $k$ repetitions other than constructing array $F$.*

How to modify the above algorithm such that next time I get a different answer?

**EDIT:** For any $a\in \\{1,2,...,n\\}, $Pr\[Output\_1=a\] = $\frac{1}{|M|}$ and Pr\[Output\_i=a|Output\_i-1 =a\_i-1,...,Output\_1=a\_1\]. Output\_i denotes the output of the algorithm in the $i$th iteration and Pr denotes the probability.

# Answer
> 1 votes
```
return M[(i - 1) % n + 1]

```

for $i=1,2, \cdots k$ does the trick.

---
Tags: algorithms, sampling
---


# Question
Title: Non-regular language whose prefix language is regular but not the whole set of words
I've seen some questions regarding the regularity of prefix language of non-regular languages (for examples, here and here). In both cases, the prefix language ended up just being the whole set of words $\Sigma^\*$, for $\Sigma$ the alphabet over which the languages are defined.

So I was thinking of examples where $\mathit{pref}\\,(L)$ would be regular, but different from $\Sigma^\*$, for $L$ some non-regular language. For a regular $L$, I could just take a finite language, but, for a non-regular language, I have yet to find an example.

Note that all languages over a unary alphabet are excluded, by one of the examples given in this question.

An example where $\mathit{pref}\\,(L)$ would not be regular would be $L=\\{0^{n^2}1,\\,n\in\mathbb{N}\\,\\}$, whose prefix language is $\mathit{pref}\\,(L)=\\{0\\}^\*\cup L$.

# Answer
If there are no further rules, then there is a simple solution. In any existing example double all symbols in each string. That is, change the symbols $0$ and $1$ by the pairs $00$ and $11$. Formally that is an homomorphism.

Now the resulting language has no longer all strings as prefix. It also does not change context-freeness or regularity.
> 14 votes

# Answer
Here's a quite simple example: the language $\\{a^m b^{mn} : m, n \in \mathbb{N}\\}$ is not regular, but its prefix language is recognised by the regular expression $\epsilon \mathop{|} a a^{\*} b^{\*}$.
> 13 votes

# Answer
#### Several simple examples

The language $\\{(01)^{n^2}: n\ge0\\}$ is nonregular, but its prefix language is $(\epsilon+0)(10)^\*(\epsilon + 1)$.

The language $\\{0^n1^m: 0\le n\le m\\}$ is nonregular, but its prefix language is $0^\*1^\*$.

Given a non-regular language $N$ such that $\mathit{pref}(N)$ is regular, we have

* $wN$ is a non-regular language, whose prefix language is regular but does not contain $1$, for any word $w$ that start with 0.
* $N\_\overline\sigma=\\{u\in N\mid u\text{ does not start with } \sigma\\}$ must be nonregular for some symbol $\sigma$, $\mathit{pref}(N\_\overline\sigma)$ is regular but does not contain $\sigma$.
* $N\_\sigma=\\{u\in N\mid u\text{ starts with } \sigma\\}$ must be nonregular for some symbol $\sigma$, $\mathit{pref}(N\_\sigma)$ is regular but does not contain $\sigma'$ where symbol $\sigma'\not=\sigma$.

#### Any infinite prefix language is the prefix language of a nonregular language

Call a language a prefix language if any one of the following three equivalent conditions holds

* it is the prefix language of some language.
* it is the prefix language of itself.
* it is prefix-closed, i.e., it contains all prefixes of any string in itself.

Let $P$ be some language.
**Claim**: $P$ is an infinite prefix language $\iff$ there is a nonregular language $N$ such that $\mathit{pref}(N)=P$.

**Proof**:
"$\impliedby$" As a nonregular language, $N$ must be infinite. Since $N\subseteq P$, $P$ is infinite.

"$\implies$" There is a sequence of words $s\_0, s\_1, s\_2,\cdots $ in $P$ such that for all $n$, $|s\_n|=n$, $s\_n$ is a prefix of $s\_{n+1}$ and there are infinitely many words in $P$ that start with $s\_n$. Let us prove this by induction on $n$.

* $n=0$, $s\_0$ is the empty string.
Since $P$ is infinite, it is trivially true.
* Suppose it is true for $n$.
There are infinitely many words in $P$ that start with $s\_n$. A word that starts with $s\_n$ must start with $s\_n\sigma\_i$ for some $i$, where $\Sigma=\\{\sigma\_1, \cdots, \sigma\_k\\}$ is the alphabet. Hence for some $i$, there are infinitely many words in $P$ that start with $s\_n\sigma\_i$. Let $s\_n\sigma\_iw$ be one of them, where $w\in\Sigma^\*$. Since $P$ is prefix-closed, $s\_n\sigma\_i\in P$. Let $s\_{n+1}=s\_n$ and the induction step is complete.

Consider $N\_J=P\setminus\\{s\_i:i\in J\\}$, where $J$ is a set of some odd numbers. There are uncountable many $N\_J$'s. Since there are only countable many regular languages, there exists $N\_K$ such that $N\_K$ is nonregular. Since $N\_K$ contains $s\_i$ for all even $i$, $\mathit{pref}(N\_K)=P$. $\quad\checkmark$

**Corollary**: Every regular infinite prefix language is the prefix language of a nonregular language.

Note that if the prefix language of a nonregular language is regular, it must be a regular infinite prefix language.
> 8 votes

# Answer
I'd take the language $(01)^n 0^m$ where m = 0 or 1, and 2n + m is a prime number. That is a string alternating between 0 and 1, and the length is a prime number. The prefix language is the regular language of alternating 0's and 1's.

You can take any regular language L and then create a language L' consisting of strings in L with certain lengths where the length restriction makes it irregular.
> 5 votes

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


# Question
Title: Is Big-Theta a more accurate description of worst case run time than Big-O?
Question I was asked: Does it make a difference if I say "The worst case run time is $O(n^2)$ vs the worst case run time is $\Theta(n^2)$?"

To me, the only difference is that when we say $O(n^2)$, the function may also be $O(n)$, we do not know. But when we say $\Theta(n^2)$, we know for a fact the function is $O(n^2)$ and $\Omega(n^2)$, because it is bounded by $c\_1n^2\leq f(n)\leq c\_2n^2$ (correct me if I am wrong).

Therefore, can we not say that $\Theta(n^2)$ gives us a more accurate (or at least equal) sense of worst-case run time than $O(n^2)$?

# Answer
> 9 votes
Yes. Your understanding is correct on all points!

# Answer
> 8 votes
O(f(n)) is also used when there is no simple function that your runtime is close to. For example: Find the smallest prime factor of n by trial division, finishing when a factor is found: There are O(n^1/2) tests if you divide by all integers up to the square root of n. But for even n there is only one test, and similar if n has any small factor.

So you can’t give any reasonable Theta unless you say f(n) = Theta(f(n)) which is true but pointless.

There is also the possibility that I can *prove* that a function is for example $O(n^2)$. I may suspect it is actually smaller, it may actually be $O(n)$ but I cannot prove it. Obviously in that situation I can also not prove that it is $\Theta(n^2)$ \- because it isn't true.

# Answer
> 0 votes
You answer yourself by saying that $\Theta$ is the conjunction of $O$ and $\Omega$. So yes of course, $\Theta$ is more informative than $O$ alone.

Make sure anyway that you don't confuse the asymptotic behavior of the algorithm complexity, and that of its worst-case complexity.

E.g. the running-time of QuickSort is $O(n^2)$ and $\Omega(n\log n)$, while its worst-case running-time is $\Theta(n^2)$.

---
Tags: asymptotics, runtime-analysis, big-o-notation, notation
---


# Question
Title: Does the even-odd rule ever have false positives for deciding a point in a complex polygon?
The wikipedia for even-odd rule says

> On a simple curve, the even–odd rule reduces to a decision algorithm for the point in polygon problem.

On a complex polygon, there are clearly false negatives in the holes. For example, the hole in the middle of a pentagram is within the boundary of the polygon, but any ray to the hole intersects an even number of lines.

However, I can't think of a way to put a point outside the boundary of a complex polygon that has an odd numbered ray. Are there any false positives like this?

# Answer
> 1 votes
No, there is no "false positive".

#### What is the meaning when a rule *determines* the "insideness"?

> The SVG defines the even–odd rule by saying:
>
> This rule determines the "insideness" of a point on the canvas by drawing a ray from that point to infinity in any direction and counting the number of path segments from the given shape that the ray crosses. If this number is odd, the point is inside; if even, the point is outside.

The correct interpretation of
$\quad$ "this rule **determines** the 'insideness' of a point ..."
is
$\quad$ "this rule **defines** the 'insideness' of a point ...".

Since it is a *definition*, the rule cannot have false negatives nor false positive.

#### Are all definitions for "insideness" equivalent? No.

Suppose we are given a closed curve on a plane.

If the curve is simple, i.e., it does not intersect itself, it divides the plane into three parts: itself, an inside part and an outside part. There is no question.

However, when the curve intersects itself, there are several reasonable choices to define what is "inside" and what is "outside" with respect to the curve.

The natural definition is to define a point not on the curve

* as outside if it is connected to the infinity. This condition is the same as it can be moved to infinity without passing through the curve or it is not confined/surrounded by the curve.
* Otherwise, it is inside.

This definition will be called "the natural rule". Only the "outermost perimeter" of the curve is significant for this rule; the "inner segments" of the curve is irrelevant.

Another definition is "the even-odd rule".

A third definition is "the non-zero winding rule".

These three definitions may not agree on which points are inside or outside, as shown by the illustration above provided by Wikipedia.

#### However, what is "really" outside is outside by any rule.

Your question is asking, given a closed curve, whether a point that is outside by the natural rule could possibly be identified as inside by the even-odd rule.

The answer is no since the outside part defined by the natural rule is "really" outside. It is outside by any rule. We would not adopt a potential rule if it could identify a point that is outside by the natural rule as inside.

#### Is the even-odd rule consistent? Yes.

Another basic requirement of a rule is, of course, it should be consistent. Given any point not on the curve and any possible way of applying the same rule, the verdict should be either inside always or outside always.

Let us understand why the even-odd rule is consistent.

Given a closed curve that intersects itself, we can split it naturally into simple closed curves ("simple" means non-self-intersecting) that touches each other only at finitely many points. For example, the curve on the left side is split into 5 distinctively colored closed curves as illustrated in the middle part, each of which does not intersect itself. Fill the inside area of each simple closed curve with the same color of that curve.

Let $P$ be any point on the plane.

Following Yves's suggestion, let us draw a curve $\mathscr C$ (which is more general than a ray) from $P$ to infinity. Since the number of path segments from the given curve $\mathscr C$ crosses is the same as the number of intersection points between $\mathscr C$ and the given curve, let us check the intersection points instead.

For simplicity, assume

* $\mathscr C$ does not pass any point that is shared by two or more colored area, i.e., any point that are shared by two or more simple closed curves. If it does, we can perturb $\mathscr C$ around any of those points so that it will not pass them. The perturbation can be made as arbitrarily small as wanted. (If $\mathscr C$ must be a ray, perturb the slope of $\mathscr C$.)
* When $\mathscr C$ passes a point on the given curve, it will enter immediately an neighborhood that is enclosed by a different simple closed curve, leaving its previous neighborhood. If it does not, we can perturb $\mathscr C$.
In particular, $\mathscr C$ intersects the given curve on finitely many points.

Let us follow the curve starting at $P$, going to infinity.

1. At first, if the starting point $P$ is in a color area, it will exit that area first, intersecting the enclosing simple closed curve once. This event, if it happens, contributes exactly one intersection point.
2. After the previous step, $\mathscr C$ enters a colored area. It must exit that area next into an uncolored area. Then it enters another colored area. It must exit that area next into another uncolored area. After a number of such entering-exiting pairs, it goes to infinity without intersecting the given curve anymore.
For each pair of entering and exiting, there is a pair of intersection points: the point where $\mathscr C$ enters and the point where $\mathscr C$ exits. As pairs of points, these intersection points do not affect the parity of the number of intersection points between $\mathscr C$ and the given curve.

Hence, if the starting point is in a colored area, the parity is odd. Otherwise, it is even. The parity of the number of intersection points between $\mathscr C$ and the given curve depends only on the starting point $P$, not depending on how we draw $\mathscr C$.

In particular, if there is a curve from $P$ that goes to infinity without intersecting the given curve, then any curve from $P$ that goes to infinity will intersect the given curve an even number of times. In that case, the even-odd rule considers $P$ outside with respect the given curve.

However, a rigorous proof for this consistency might be well beyond the usual course of study. It is *highly nontrivial* to prove rigorously even the easy and obvious fact that a simple closed curve divides the plane into an inside part and an outside part. Fortunately, a rigorous proof is not necessary for intuitive and effective understanding here, either.

# Answer
> 1 votes
The odd-even rule does not require a half-line from the test point, any continuous curve can do (you can deform any area of the plane).

If there is a curve from the point that goes to infinity without meeting the polygon boundary, then the point is outside *in the ordinary sense*. In that case, the number of intersections is zero, an even number, so the odd-even rule holds.

---

On the opposite, for a point that is inside *in the ordinary sense*, there cannot be a curve that goes to infinity without crossing the outline, but the number of intersections can be even or odd.

---
Tags: terminology, computational-geometry, polygons
---


# Question
Title: Minimal-length strings which are substrings of no string in a given CFL
Is there an algorithm for enumerating a sequence of minimal-length substrings composed of terminal symbols within some CFG which are not substrings of any string in the language defined by that CFG? In other words, given a CFG, $G=(V,\Sigma ,R,S)$, find a sequence of increasing-length strings $E = \\{e \in \Sigma^+ \mid \forall \sigma \in \mathcal{L}\_G, e$ is not a substring of $\sigma\\}$.

# Answer
> 1 votes
Here is a possible approach. Enumerate lengths in increasing order (length 0, length 1, length). For each length, enumerate all strings in lexicographic order, as follows.

Let's take length 4 as illustration. First, check whether any member of $L$ has any substring of the form `a???` (where `?` is a wildcard that can match any symbol). If not, then you can output `aaaa`, `aaab`, ..., `azzz`, then move on to checking whether any member of $L$ has any substring of the form `b???`. If yes, then move on to checking whether any member of $L$ has any substring of the form `aa??`. Repeat iteratively. In this way, you walk through possible prefixes in lexicographic order, in a breadth-first manner.

How do you check whether any member of $L$ has any substring of the form `a???`? This amounts to testing whether there is any string in both $L$ and $\Sigma^\* a \Sigma^3 \Sigma^\*$, i.e., whether $L \cap \Sigma^\* a \Sigma^3 \Sigma^\* \ne \emptyset$. Note that $L$ is context-free and $\Sigma^\* a \Sigma^3 \Sigma^\*$ is regular, so their intersection is context-free (and you can easily construct a PDA or context-free grammar for it using standard methods), and thus you can test whether it generates a non-empty language (using standard methods). Each check will take about $O(|G| \ell^2)$ time, where $|G|$ is the size of the context-free grammar $G$ for $L$ and $\ell$ is the length of strings you are enumerating.

---
Tags: formal-languages, context-free, formal-grammars
---


title: does finite automata have memory?

text:
# Question
Title: does finite automata have memory?
I've learned that finite automata doesn't have memory and hence languages, where there are comparison within the string, can't be considered regular.

In our university there was a question where the following language was considered as *regular* in the solutions: $\\{WXW^R | W,X ∈ \\{0,1\\}^\*\\}$

here, $W^R$ is the reverse of $W$.

To compare $W^R$ and $W$ wouldn't we have to store $W$ in memory which I know doesn't exist in finite automata machines. Or what actually happens?

# Answer
> 2 votes
A finite automaton has no memory other than which state is the current state.

The strings in the language consist of some substring, then another substring, then the reverse of the first substring. One way to recognize this language would be to check whether the end of the string matches the start of the string, which requires storing it.

However, the way the language is described is meant to trick you. The first substring may be empty (0 chars long). *Every* string starts with an empty string and ends with the reverse of it! So every string is in the language. Can you make a DFA that recognizes every string? Of course you can.

Even if we said that W must contain at least 1 character, the language would contain every string that starts and ends with the same character, which is also recognizable by a DFA. If W must contain at least 2 characters, it's still recognizable by a more complicated DFA as the DFA can branch off for each combination of characters, and then each branch can check for those characters at the end. Only if there's some rule that allows W to be infinitely complex (e.g. any number of $a$ followed by a $b$) can it not be recognized by a DFA.

# Answer
> 1 votes
The "and hence..." is incorrect. There might be other ways to determine whether a string is in the language, that doesn't require comparison.

For the particular language you cite, try to come up with an example of a string that is *not* in that language. That might make it clearer why it is regular, and why the "and hence" is faulty.

---
Tags: finite-automata
---


title: Proof for Language: L1 ∪ L2 ⊆ L1L2

text:
# Question
Title: Proof for Language: L1 ∪ L2 ⊆ L1L2
I have a question for my thesis research, but I am not able to find proof of this. Does anyone have any idea on what should be approach be in order to prove this?

Question: `Prove that L1 ∪ L2 ⊆ L1L2, if λ ∈ L1 ∩ L2`

# Answer
> 0 votes
To prove $L\_1 \cup L\_2 \subseteq L\_1L\_2$

you prove that $\forall x. (x\in L\_1 \cup L\_2) \rightarrow(x\in L\_1L\_2)$

To prove *that*, you prove that

$\forall x. (x\in L\_1) \rightarrow(x\in L\_1L\_2)$

and

$\forall x. (x\in L\_2) \rightarrow(x\in L\_1L\_2)$

Can you see where to go from there?

---
Tags: formal-languages, automata
---


# Question
Title: Reducing a known NP-hard problem to a custom 4D planning problem
I'm interested in characterizing the complexity of a decision problem related to path planning. For instance, consider the following problem: *Given the current location and battery charge of an outdoor robot, does a trajectory exist such that the robot reaches a goal region without running out of energy?*

I assume the outdoor environment is made of different types of terrain each affecting the robot's energy consumption differently (ex: grass, sand, mud, etc.). The robot can also visit charging stations along the way, but these stations are only operational at certain times of the day. As such, the configuration space of the overall planning problem has 4 continuous dimensions: the 2D position of the robot in the map, the time of the day and the robot's energy level. I assume that the robot's state is fully observable, the state dynamics are deterministic, and the entire map & charging station schedules are known ahead of time.

Intuitively, this seems like a hard decision problem. However, I'm struggling to find a valid reduction from a known NP-hard or NP-Complete algorithm. My best lead at the moment is the generalized mover's problem, which is PSPACE-hard (which implies NP-hard). The piano mover's problem is a similar formulation. However, there is a difference between the mover's problem and my problem: the mover's problem assumes a goal *state* (instead of a goal *region*). Does this matter?

Is the mover's problem an appropriate NP-hard problem to reduce to my problem? If not, what other known problem could I reduce from?

# Answer
I see no reason to expect this to be NP-complete. If you discretize the state space, it is solvable with dynamic programming (in fact, reachability analysis on the state space suffices).
> 1 votes

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


title: How to solve T(n)=2T(√n)+(loglogn)^2?

text:
# Question
Title: How to solve T(n)=2T(√n)+(loglogn)^2?
Trying to solve the recurrence, but no clue how to deal with the (loglogn)^2 part

# Answer
> 0 votes
**Hint:**

Assuming base $2$ logarithms, we can write

$$\begin{align}T(65536)&=2T(256)+4^2\\\&=4T(16)+2\cdot3^2+4^2\\\&=8T(4)+4\cdot2^2+2\cdot3^2+4^2\\\&=16T(2)+8\cdot1^2+4\cdot2^2+2\cdot3^2+4^2\end{align}$$

Hence, generalizing the pattern, you see the sum

$$\sum\_{k=1}^{\lg(\lg(n))}{k^22^{\lg(\lg(n))-k}}=\lg(n)\sum\_{k=1}^{\lg(\lg(n))}{k^22^{-k}}$$ appear, as well as a term $$\lg(n)T(2).$$

---
Tags: recurrence-relation, recursion, master-theorem
---


# Question
Title: what will be the time complexity of the following procedure?
```
flag=true
for x=1 to n do
{
  for i=1 to n do
  {
    for j=1 to n do
    {
      if flag=true then
      {
        for m=1 to k do
        {
          for l=1 to k do
          {
            some statements.... taking constant time
          }
        }
      }
      some other statements....taking constant time
    }
  }
  flag=false
 }

```

What will be the time complexity of the procedure? Will it be O(n^3+ (n^2)(k^2)) or O((n^3)(k^2))?

# Answer
When flag is true, the body of the third for takes time `ak²+b`; otherwise it takes `c`. So the total running time is

```
n²(ak²+b) + (n-1)n²c + d = O(n²k² + n³).

```
> 0 votes

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


title: Potential Method For Decimal Counter

text:
# Question
Title: Potential Method For Decimal Counter
There is a counter that counts the number of items in the store. For every increase in item or item that has been inserted, the cost is a + kb where k is the number of digits that has been changed in the counter. For example, from 2999 to 3000 we have a + 4b as 4 digits has been changed and from 999 to 1000, we also have a + 4b similarly. I want to find a potential method that gives amortised cost for insert as "a + 10b/9. I know that I have to find a potential function that decreases as much as the costliest insert operation. The more 9s at the end, the more costly the operation is what I know. I have tried some potential functions such as "number of 9s in the counter" as well as "Difference between last digit and 0". The answer needed is a fraction so I am certain the potential function involves a ratio of some kind but I cannot see it. Appreciate any guidance for this problem.

# Answer
> 0 votes
Let $n = \sum\_{i=1}^\infty d\_i 10^{i-1}$ with $d\_i \in \\{0, \dots, 9\\}$ and define $\Phi(n) = \frac{b}{9}\sum\_{i=1}^\infty d\_i$. In other words, $\Phi(n)$ is the sum of the digits of $n$, scaled by a factor of $\frac{b}{9}$.

Consider now an increment from $n$ to $n+1$ and let $k \ge 1$ be the number of affected digits. Following this increment, $d\_k$ becomes $d\_{k}+1$ while all $d\_i$ with $i\<k$ change from $9$ to $0$. Thefore: $$\Phi(n+1) - \Phi(n) = \frac{b}{9} \bigg( 1 - 9 \cdot(k-1) \bigg) = \frac{b}{9}-(k-1)b,$$

and the amortized cost is: $$ a+kb + \Phi(n+1)-\Phi(n) = a + kb + \frac{b}{9} - (k-1)b = a + \frac{10 b}{9}. $$

---
Tags: amortized-analysis
---


# Question
Title: In the Master Theorem, if one term is smaller than another, can we drop it from the equation and use big O instead of theta?
#### Considering the runtime analysis (with the master theorem) of the function below

$T(n) = 12T(\frac{n}{4}) + 2\sqrt{n} + \log^4(n)$.

---

As I could not figure out a way to get the equation in the form $T(n)=aT(\frac{n}{b}) + \theta(n^d)$, I aimed to get the equation in the form of $T(n)=aT(\frac{n}{b})+\theta(n^k\log^pn)$ as listed here.

My idea is to drop the $2\sqrt{n}$ term (as $\forall n\>\approx 2.5: \log^4(n)\>2\sqrt{n}$), and then give the final runtime analysis in big O notation as opposed to $\theta$ notation. **Is this a valid solution?**

---

*Note: this is **similar** to a problem in a homework assignment I am doing, but I have changed things in the equation as I am solely posting to help my understanding and not to cheat.*

# Answer
> 1 votes
I suspect you have missed that $\sqrt{n} = n^{1/2}$.

---
Tags: runtime-analysis, master-theorem
---


# Question
Title: Algorithm To Process Purchases Efficiently and Apply Constraint
I am working on a problem where I have to completely scan a large unordered log file which contains purchasing details of customers. The file structure is as follows:

```
customerId  itemId  cost

```

The customer could have purchased the same item more than once in a day and at different times so there will be multiple entries for a customer and item combination. At the end of the processing, the program should print the customerId and the total cost of all their purchases, *but* with a discount applied so that the cost of the most expensive item is removed.

My algorithm is as follows:

1. Create a map, call it M-1, with the customerId as key and a running total cost as the value i.e. customerid -\> running\_total\_cost.
2. Create another map, call it M-2, with the key as (customerId and itemId) and for the value the running subtotal. That is, it keeps a tab on how much of this item this customer has bought.
3. For each line in the file, upsert into M-1 the customerId and add the cost of this item to the running total. Also upsert an entry in M-2 containing the running total of this customer and item purchased. So M-1 has this structure:

```
customerId  RunningTotal

```

And M-2 has this structure

```
customerId ItemId RunningTotal

```
4. After the file has been completely processed in step 3, for each entry in M-1, get the customerId and look-up the customer in M-2. In M-2, run a loop so that it finds the most expensive purchase this customer made. This can be done by creating a temporary variable and looping through the purchases the customer made and comparing the current value of this variable with the next value. Replace the value of the variable with the new highest total At the end, the highest value will remain.
5. Print table

My question is whether this can be processed any faster than this?

**UPDATE**

I believe I have an optimal solution for this now. The algorithm is as follows:

1. Make one pass through the file. For each line, create a map with the following structure

```
Map[CustomerId, Map[ItemId, subtotal]]

```
2. After processing the file completely and making the above map, then do the following loop

```
for each customerId
  count = 0
  total = 0
  highestSubtotal = 0
  for each itemId
     total += subtotal
     highestSubtotal = max(highestSubtotal, subtotal)
     count += 1
print CustomerId, if count > 1 then total - highestSubtotal else total

```

I don't think I can optimise that anymore unless anybody can think of something else.

# Answer
For each customer, keep track of the most-expensive item they've ordered and the total cost of all other items they've ordered. This can be stored in a hashmap that is maintained in memory. Then you can scan through your log file sequentially, updating the in-memory hashmap at each step.

This requires memory proportional to the number of customers, not the number of lines in the log file. You mentioned there are about 25M customers, and so it should be no problem to store a hashmap with 25M entries in main memory.

If that consumes too much memory, you can use your other solution of sorting the file by customerId (using an external sort if needed), then process each customer separately. That will require approximately zero memory.
> 1 votes

# Answer
The algorithm I posted above doesn't work. It's the same as trying to load all the file upfront which blows up as the heap memory is exhausted.

Another solution would be to sort the file before processing it. The UNIX sort command is able to sort files much bigger than the RAM available on the machine. It does this using external sort I believe.

So my new solution is to sort the file first on the customerId. This ways a one pass can be done on the file and the data for each customer calculated on the fly. As each customer is encountered in order, before computing the next customer's data the memory consumed for the previous customer is freed.
> 0 votes

---
Tags: algorithms
---


# Question
Title: Why are regular expression quantifiers greedy by default?
I can't count the number of times I've seen questions on StackOverflow related to regular expressions where the problem was due to the programmer not understanding the impact of greedy quantifiers. Most recently, Python regex issue — \[\S\s\]\* vs \d\*.

I wonder why regular expression quantifiers were defined to be greedy. It seems like this is less intuitive than non-greedy regular expressions. If someone writes a regexp like

```
BEGIN(.*)END

```

they intuitively expect the capture group to grab everything between adjacent `BEGIN` and `END` brackets. But if there are multiple `BEGIN...END` pairs, it will span all of them. You have to write

```
BEGIN(.*?)END

```

to express this. And I think non-greedy quantifiers like this didn't even exist until PCRE -- matching this was even more complicated then.

Non-greedy quantifiers are not a magic bullet solution for all such problems, but it seems like there would be fewer problems if they were the default.

EDIT:

I think I see a possible reason. If there's nothing after the quantifier, you usually want it to be greedy. My original answer to the above question had a bug, the regexp ended with `Answer:\s*(.*?)`. By making this non-greedy, the last capture group matched an empty string rather than everything after the final `Answer:` prefix.

And also consider the `\s*` there -- we want that to capture all the whitespace after the prefix, before grabbing the text in the capture group.

So the appropriate default really depends on what (if anything) is after the quantifier. And greediness is also often only an issue with `.*`, not if you quantify something more specific than `.`.

Is this all there is to it?

# Answer
A regular expression, as the term is used here, is a mathematical construct; it is the formalism used to define regular languages. In that context, the Kleene star operator is neither greedy nor abstemious. Rather, it is *non-deterministic*: it will match as many times as necessary.

It's worth pointing out here that regular expressions define a "language", *not* a substring. In that sense, the regular expression matches (or recognises) the entirety of a sentence.

Using regexes to find substrings was a (very useful) adaptation of a theoretical concept to practical programming problems. But it introduces an ambiguity which was not present in the original: if the regex can match more than one different substring, which one should it choose?

The original regex libraries all chose the first matching substring (in a left-to-right scan), and of those matches which all start at the same position, they chose the longest one. These are the Posix semantics for regular expressions, which also define how subpatterns ("captures" between parentheses) correspond to substrings of the matched string. ("Captures" form no useful part of the theoretical model of regular expressions.)

The regular expression formalism has the enormous advantage that it can be compiled into a Deterministic Finite Automaton (DFA) which can then be used to perform a match -- or even a substring search -- in linear time. In effect, the DFA recognizes all possible matches in parallel; it is easy to make it recognize the longest match, by simply continuing until no further advance is possible. It would also be easy possible to recognize the shortest match, although that is not as common as you might think. (Consider, for example, recognizing numeric or identifier-like tokens: you really want to match the longest possible string.)

However, implementing abstemious repetition is not the same as implementing shortest match. Rather, it requires ordering possible matches by examining a subcomponent of the match. Since regular expressions do not need to be deterministic in submatches (and usually are not), ordering by subcomponent is non-trivial; it requires significant extra memory and time because many alternative partial matches may need to be remembered during the scan.

Once you have substring matches, possibly with captured submatches, you need to start worrying about resolving these ambiguities. And the Posix semantics are not always what are desired. Sometimes -- often, even -- one would want to find the shortest matching substring. (As in the `BEGIN.*?END` example you mention.)

Consequently, many regex libraries do not use this algorithm, preferring a backtracking recursive solution. One of the advantages of the backtracking algorithm is that it can cope with a number of extended regex operators which cannot be implemented with a DFA, including back-references which are not even context-free (in general). On the flipside, these operators can introduce pathological slow-down, and it is relatively easy to craft regexes which take exponential time to do a search. If you allow user-supplied ("tainted") regexes, this is a vector for DoS attacks. Even if you don't allow tainted regexes, you sometimes have to think carefully about how to write a given regex in order to produce as efficient a search as possible.

Over the years, regexes have drifted further and further away from their theoretical regular language roots. However, there are still contexts in which the original formulation and its guaranteed linear time complexity are useful:

* Lexical scanners, in which the regular expressions are not dynamic and therefore are usually compiled into the scanner. Since simple regular expressions are perfectly adequate for tokenising most programming languages, the efficient linear-time algorithm is preferred.
* As mentioned, tainted regular expressions, such as on-line search engines. See, for example, Russ Cox's `re2` library, based on a (re-)discovery of the linear-time algorithm, which he wrote in order to protect the Google Code search engine from potential denial of service attacks.
> 9 votes

# Answer
@rici wrote a very good answer. I actually intended to write a comment but I write it as answer instead.

I can think of only these reasons: first POSIX as mentioned before. Second a misunderstanding. Third, formal language theory could have influenced it.

**For the first reason,** my subjective opinion is, the best way of implementing POSIX is ignoring it. Its usability level is outdated. But that's not the debate.

**For the second reason,** the misunderstanding is that the original concept of `.*` – matching any text until end of line/string – would necessitate greedy semantics. But it may as well be lazy (frugal, abstemious) and still match at the end of the string. The end of (search) string would be a special generic character which is invisible (and not encoded in bits) but exist after the last encoded string character. This special character is an assertion which matches, if nothing else in the regex can match anymore at the current point in search (subject string).

So while regular languages indeed were invented for verifying (deciding) whole strings, not just parts within them, adapting them to search within strings requires the above mentioned adaption which is what humans probably intuitively understand. So `a*` would mean `a*(?!a)` but not `a*(?=)` as it is usually translated.

**For the third reason,** greedy quantification is required if you need to match a full list of consecutive repeated patterns when you don't have anchors or assertions available (as was the case in the early regex versions) while ignoring anything between these repeated patterns. That said, greedy quantifiers are semantically rather not suited for search within strings but rather for verification of entire strings. (EDIT: I saw that greedy quantification also is exploited to do backwards search (from right to left) when used in assertions.) And this "verification" is what regular languages are doing in formal language theory. In terms of traditional formal language theory, `a*` is understood as `\Aa*\Z` in practice. Under these semantics, having greedy quantifiers are probably more performant because they are looking at the end of string to match the subsequent part of the regex instead of trying to match the subsequent part at every visited non-deterministic branch point.

#### Conclusion (my usability perspective)

I don't see "greedy by default" to make sense in practice because it's not the common case for the application in searching/tokenization. I very rarely *require* greedy quantifiers for searching (probably never?). Backwards search is a use case for greedy quantification but how often appears backwards search compared to forwards search? Greedy quantifiers make sense if you want to get the last match of a subsequent regex part in the entire subject string but most of use cases known to me match things locally.

My honest recommendation is to blatantly ignore POSIX RegExp standards for usability's sake, write new history and turn the quantifier convention into lazy by default. \[Probably also non-backtracking as default, but another story.\]
> 2 votes

---
Tags: regular-expressions
---


# Question
Title: Trading time for work; does this concurrency phenomenon have a name?
Recently, my girlfriend and I were trying to get out of the house, when I encountered a phenomenon which I thought might be analogous to a tradeoff in concurrent systems.

Here's the real world setup.

### Processes

* `Process A`: Girlfriend orders coffee on phone.
* `Process B`: Girlfriend gets ready at apartment, and *ideally* drives car to pick me up at coffee shop.
* `Process C`: I fetch coffee, and *ideally* get picked up by girlfriend at coffee shop.
* `Process D`: We commute together.

### Dependencies

* `Process A` must complete before `Processes B and C`.
* `Process B and C` must complete before `Process D`.

### Phenomenon

On the day:

* My girlfriend orders coffee (`Process A`) and begins getting ready (`Process B`).
* I leave the apartment to fetch coffee while my girlfriend is getting ready (`Process C`).
* However, my girlfriend takes longer than expected to get ready, so instead of getting picked up at the coffee shop shortly after dealing with payment, I wait.
* Then, we commute (`Process D`).

### What's suboptimal?

Resources, namely me walking, are not used minimally. In retrospect, we determine the optimal solution given the knowledge that my girlfriend will take longer to get ready is to simply wait. Once she finishes getting ready, we ought to drive to the coffee shop together to fetch the coffee and commute from there.

Processes are appropriately recognized as able to be parallelized. But, because of resource sharing, will only yield the desired improvements under ideal circumstances wherein girlfriend arrives by car at coffee shop shortly after coffee has been fetched. Unless this circumstance is realized, the time to complete `Processes A - D` becomes primarily determined by `Process B` and optimization of `Process C` is not concerning.

More generally, we determine a sequential solution makes better use of resources than the concurrent solution.

If processes are performed...

```
A -> B -> C -> D

```

we will most likely prefer that outcome to the original...

```
     -> B -
A - |      | -> D
     -> C -

```

... (in part) because, even though time is slightly less optimized, work is better shared.

Does this phenomenon have a name? In what areas of computing might this tradeoff be more common or concerning? What are common software analysis strategies that may help?

**Note:** I can contrive examples with more significant effects, even ones that do not produce optimal runtime (though that may be another phenomenon). But, (a) this is partially a playful barb at my gf's planning and (b) I thought this might resonate with some folks.

# Answer
Such considerations are known as Critical Path analysis. They allow to describe the temporal dependencies and find the fastest solution, as well as detect bottlenecks or near-bottlenecks.

https://en.wikipedia.org/wiki/Critical\_path\_method
> 3 votes

# Answer
So your situation in computing terms: You have two task A and B that could be calculated in parallel. A produces a result X at no cost at the end of A. B requires X at the first step. B has the choice of waiting for A to finish, or calculating X itself.

It is not uncommon that trying to parallelise tasks involves duplicating some work. There is no particular name for this.

(A much worse case is the alpha-beta algorithm for chess. Each calculation makes the next calculation more efficient. But if you perform multiple calculations in parallel, you can’t take advantage of that).
> 1 votes

# Answer
In the absence of a direct answer, here are some ideas.

I would say this is essentially a job scheduling problem with multiple optimization criteria:

* total completion time
* resource utilization

The mathematical discipline that studies such problems is scheduling theory, a subdiscipline of operations research; I'm not really familiar with the field, but if you're looking for standard terminology, I'd look there.

Many others have been working on scheduling problems, with their own approach, and no doubt some of them have their own terminology.

For instance, I used to work on a Petri net editor that can be used to draw your examples (as Petri nets), and, after assigning expected processing times to the individual tasks, simulations can be run to calculate average completion times and resource utilization for each resource. It is by no means the only software tool with such capabilities. Its designer, a professor in computer science (now retired), spent considerable effort on problems in logistics and job scheduling, and this was one of his efforts to provide practical tooling for modeling and optimizing such problems. This approach is different from the one taken in operations research, and it has its own merits and limitations.
> 1 votes

---
Tags: parallel-computing, concurrency, process-scheduling
---