title: Decision vs Optimisation Problem in P

text:
# Question
Title: Decision vs Optimisation Problem in P
If a decision problem is in **P**, is the associated optimization problem then also efficiently solvable?

I always thought that this is the case but according to Wikipedia page on Decision Problems the complexity of a decision and function problem might differ and to me a function problem was always a special case of an optimization problem, hence I was under the impression that if the decision problem is efficiently decidable the same applies to the corresponding optimization problem.

# Answer
Let us consider a generic optimization problem:

> Maximize $f(x)$ subject to the constraint $x \in \mathcal{D}$.

The corresponding decision version is

> Given $\mathcal{D}$ and $T$, is there $x \in \mathcal{D}$ such that $f(x) \geq T$?

In most cases, the range of $f(x)$ is at most exponential in the description length of $\mathcal{D}$, and so the optimization problem reduces to the decision version via binary search. For example, if $0 \leq f(x) \leq n$, then we first ask whether there is a solution with $f(x) \geq n/2$; depending on the answer, we ask whether there is a solution with $f(x) \geq n/4$ (if the answer was negative) or with $f(x) \geq 3n/4$ (if the answer was positive); and so on.

Conversely, if we can solve the optimization problem then we can easily answer the decision problem, and so the two are essentially equivalent.
> 2 votes

# Answer
Take a peek at Bellare and Goldwasser's The Complexity of Decision versus Search SIAM J. on Computing 23:1 (feb 1994), a version for class use is here. Short answer: If the decision problem is in NP, they are "equivalent" (the optimization problem can be solved using a polynomial number of calls to the decision problem), if the decision problem is harder (and some quite plausible conjectures pan out) they aren't.
> 1 votes

# Answer
Consider the **Travelling Salesman Problem (TSP)**.

*Decision Version* (DV): Given an undirected weighted graph $G$, does there exist a Hamiltonian cycle of weight at most 'w' in the Graph?

*Optimization Version* (OV): Given an undirected weighted graph $G$, find the hamiltonian cycle of minimum weight?

**Case 1:** If **P $=$ NP**.

Since there is a polynomial-time reduction from DV to OV and vice-versa (link), both the problems are in P. Here, the complexity of both the problems are the same.

**Case 2:** If **P $\neq$ NP**

Here, we will show that the complexity of both the problems are different.

Note that the Decision version of TSP is in NP since given a sequence of vertices, we can verify in polynomial time if the sequence is a hamiltonian cycle of weight at most 'w'.

However, for the Optimization version of TSP, how will you know if it belongs to NP. In other words, given a Hamiltonian cycle of 'w', how can you verify if it is the optimal one? As per my thinking, to verify its optimality you must know the optimal solution. Since P $\neq$ NP, we can not find the optimal solution in polynomial time. Therefore, we might not be able to say if TSP is in NP.

Thus, the complexity of Decision Version and Optimization Version could be different.
> 0 votes

---
Tags: complexity-theory
---


# Question
Title: Is $L = \{ w : \#_a(w) = \#_b(w) \}$ regular?
Is $L = \\{ w : \\#\_a(w) = \\#\_b(w) \\}$ regular? I do not think it is. I recently posted a question and from there I was thinking if this language is regular.

If we assume on the contrary, then there exists a pumping length $p$. In that case, the word looks like $xyz$ where $|xy| \leq p$. If $y$ does not have the same number of $a$'s and $b$'s then $xy^iz$ for $i\>1$ will give us a contradiction. Otherwise $y$ has the same number of $a$'s and $b$'s. *This does not lead me to anywhere.* I tried creating cases where this would fail -- seems like there isn't any.

This link answers it, but I do not understand what they mean by "a regular language is one that uses finite memory". I have encountered similar reasoning before, I have not been able to figure it out.

This answer seems to check if a number satisfies the criteria using regex. Is that a different form of regex?

# Answer
> 1 votes
This can also be proved easily using Myhill-Nerode theorem.

> **Myhill-Nerode Theorem**: Given a language $ L \subseteq \Sigma^\* $, Suppose $$ \forall x,y \in S, (x \neq y) \wedge (\exists z \in \Sigma^\* ,L(xz) \neq L(yz)) $$ where S is an infinite set. Then L is not a regular language.

(Here $L(w) = 1$ if $w \in L$ and $L(w) = 0$ if $w \notin L$.)

For the given problem, We have $L=\\{w:\\#\_a(w)=\\#\_b(w)\\}$.

Take $S = a^\*$ (note: the set $S$ is infinite).

Now take any two distinct elements from set $S$, $x=a^i$ and $y=a^j$, and take $z=b^i$.

So $xz \in L$ and $yz \notin L$.

Hence, we will get an infinite number of distinct quotients as $S$ is an infinite distinctive set.

Thus, $L$ is not regular.

# Answer
> 0 votes
Use the pumping lemma: If $L$ is regular, there is a constant $N \ge 1$ such that any string $\sigma \in L$ can be divided as $\sigma =\alpha \beta \gamma$ with $\lvert \alpha \beta \rvert \le N$, $\beta \ne \varepsilon$ so that for all $k$ the string $\alpha \beta^k \gamma \in L$.

Proof is by contradiction. Assume your $L$ is regular, let $N$ be the lemma's constant and pick $\sigma = a^N b^N \in L$, $\lvert \sigma \rvert = 2 N \ge N$. You see that $\alpha \beta$ is just 'a', so leaving out $\beta$ (i.e., $k = 0$) destroys the balance between 'a' and 'b', the result is not in $L$. Contradiction.

---
Tags: automata, finite-automata, regular-expressions, pumping-lemma
---


# Question
Title: Which graph partitioning algorithm can solve this problem?
**In brief:**
Here I have a cyclic graph above. I want to partition the graph vertices into `3` clusters. (With the mindset of cluster-wise "load balancing")
*Constraint*: All the vertices in each cluster should be directly connected.
*Goal*: the deviance of the cluster-sums should be as small as possible. (In other words, the sum of loads of all clusters should be as balanced as possible.)
**Examples:**
*An infeasible example*: `ADG` `CE` `BF`. Reason: The vertices are not directly connected within each cluster.
*A feasible but bad example*: `AB` `CD` `EFG`. Reason: The load is not optimally balanced (Difference `14` `14` `59` is too large).
*The optimal solution*: `ABCD` `EF` `G`. Reason: the difference among three cluster-sums (`28` `29` `30` respectively) is the smallest.

Which algorithm can get the optimal solution?

# Answer
Your problem is $\text{NP}$-hard. To see why, consider the version of the 3-Partition problem where we're given multiset $ X = \\{ x\_1, x\_2, \ldots, x\_{3n}\\}$ of $3n$ nonnegative integers, and we need to decide whether $X$ can be partitioned into three disjoint multisets with the same sum each. Clearly, an instance $X = \\{ x\_1, x\_2, \ldots, x\_{3n}\\}$ of the 3-Partition problem can be translated in polynomial time into a complete graph $G = \langle V, E \rangle$, where $V = \\{ v\_i\\}\_{i\in \[3n\]}$ and for each $v\_i$, we have that the weight $w(v\_i) = x\_i$. That is, we view the integers as $3n$ vertices, and every two vertices are connected with an edge. Obviously, a balanced 3-clustering of $G$ corresponds to an appropriate 3-partition of the multiset $X$.
> 1 votes

---
Tags: algorithms, graphs, computational-geometry
---


# Question
Title: What does it mean that a set of intervals is sorted by the right and left endpoints?
While reading a paper (On the k-coloring of intervals), I came upon the following description:

"Input: An integer k, and a set of n intervals sorted by right and left endpoints. The intervals are indexed in order of increasing right endpoint, and it is assumed that all endpoints are positive integers."

What does it mean that they are sorted by "right and left endpoints"? Does it mean that each interval is on the form (left endpoint, right endpoint)?

# Answer
Yes, you are right. The intervals are of the form (left endpoint, right endpoint).

First, consider the following statement:

> The intervals are indexed in order of increasing right endpoint

It means that given a set of intervals $I\_{1}, \dotsc, I\_{n}$, the $(\textrm{right endpoint of }I\_{i})$ $\leq$ $(\textrm{right endpoint of }I\_{j})$ for any $i \leq j$ and $i,j \in \\{1, \dotsc,n\\}$.

Similarly, you can define the sorted order based on the left endpoints. However, the sorted order based on these two criteria could be different.

---

Now, consider the following statement:

> a set of n intervals sorted by right and left endpoints

This statement is a bit unclear since the sorted order by left endpoints could be different from the sorted order by right endpoints. However, in Section 1(Introduction) of their paper, they also mention the following statement: "*set of $n$ sorted intervals (the $2n$ endpoints of the intervals are sorted).* ". Therefore, the sorting by "right and left endpoint" simply means that you are sorting the set of all $2 \cdot n$ points together, i.e., the set: $\\{ \ell\_{1}, r\_{1}, \dotsc, \ell\_{n}, r\_{n} \\}$ is given in sorted order irrespective of point being a left or right endpoint. Furthermore, using this sorted set you can easily recover the sorting of intervals based on (right endpoint) or (left endpoint) in linear time i.e., $O(n)$. This does not change the running time of their coloring algorithm which is $O(n + k)$.
> 1 votes

---
Tags: algorithms, graphs, colorings, intervals, union-find
---


# Question
Title: Is this adjustment to an rms calculation valid?
I want to calculate the RMS AC value of a signal made up of several thousand readings every second. The processor that I am using doesn't have enough memory to store a whole second of data, so I want to calculate it the sum of squares the fly.

This is the normal formula to calculate the RMS AC value, where you have to know the mean for the whole second before you can calculate the RMS:

> ac\_rms = sqrt (sum(square(reading-mean)) / n)

Would I get the same result if I instead use the mean from the previous second, and then apply a correction afterwards?

> ac\_rms = sqrt (sum(square(reading-prev\_mean)) / n) - abs(mean - prev\_mean)

# Answer
> 1 votes
You're looking to compute the rolling standard deviation (i.e., a streaming/online algorithm for the standard deviation). The standard method is to use Welford's method, or a variation.

For the standard deviation, see https://jonisalonen.com/2014/efficient-and-accurate-rolling-standard-deviation/. This is a minor adjustment to Welford's method (which computes the running variance) to reflect that you want the standard deviation rather than the variance. See also https://en.wikipedia.org/wiki/Algorithms\_for\_calculating\_variance.

---
Tags: mathematical-programming
---


# Question
Title: Decidability of whether $w \in L(M_1) \setminus L(M_2)$
I'm studying for my finals and I came across this question from past exams:

> Is the following language decidable? $$ L = \\{ \langle M\_1,M\_2,w \rangle \mid w \in L(M\_1) \setminus L(M\_2) \\}. $$

How can I be sure of my answer? Is there any way to know for sure?

# Answer
> 0 votes
Intuitively, $L$ is not decidable as given $\langle M\_1, M\_2, w\rangle$ we need to decide whether

1. $w\in L(M\_1)$, and
2. $w\in \overline{L(M\_2)}$.

The first condition smells like deciding the language $A\_{TM} = \\{ \langle M, w \rangle: \text{ $M$ accepts $w$}\\}$, and the second condition smells like deciding $\overline{A\_{TM}}$. To make sure that the intuition got it right, you need to **prove formally** undecidability for $L$, here is a hint.

**Hint:** show that there is a reduction from some undecidable language to $L$. It is sufficient to capture the hardness of one the above conditions. Thus, to make things simpler, think how you can fix one of the machines $M\_1$ or $M\_2$ in the reduction's output, so that one of the conditions holds trivially. I leave the rest to you.

---
Tags: turing-machines, undecidability, proof-techniques
---


title: Building a perfect hashing table

text:
# Question
Title: Building a perfect hashing table
My understanding is that one way to build a perfect hash, as per CLRS, is to use two levels of hashing, with universal hashing functions at each level.

More specifically, CLRS shows that assuming $n$ is the total number of keys, and $n\_j$ the number of keys hashed to the value $j$ for the second level, we can then make $m=n$ and $m\_j=n\_j^2$ to **guarantee** that the **expected number** of collisions is \< 1/2 in the second level.

However, as far as I understand, **collisions** are **still possible** in this second level, so to truly have **no collisions** in this 2nd level, one may need to try a few hash functions in this level **for each value of $j$**.

Is my understanding correct? If so, CLRS does not seem to elaborate much on this algorithm. Is it fair to assume that a simple sequence of random "try and error" (i.i.d sampling) of hash functions (in this 2nd level) is "as good as it gets" at least for this perfect hashing design?

# Answer
> 2 votes
As mentioned by the OP in the comments, CLRS is using the ideas of Fredman, Komlós and Szemerédi, Storing a Sparse Table with $O(1)$ Worst Case Access Time.

Corollary 4 gives a range of parameters for which the construction succeeds with probability $1/2$; this could be amplified to any constant with minimal loss of parameters.

Lemma 2 shows how to derandomize the construction, but the resulting algorithm isn't practical.

You can also probably choose parameters for which the construction succeeds with high probability, in which case you can try your luck and not even check the hash function.

# Answer
> 1 votes
`... collisions are still possible in this second level`

For each slot of the first-level hash table (which contains more than 1 keys), we will need to decide a hash-function. Since we want perfect-hashing, we want this function to give no collision. Theorem 11.9 (quoted below) guides us that it is in-fact possible to find such a function in a universal-class, with probability atleast 1/2 (meaning, atleast half of them are collision-free for this slot's keys). So, with a very few random trials, we can hope to succeed in finding such function. With each trial, we need to check all keys in that slot to know if this is the one which works. And this task needs to be repeated for all slots of first-level table.

So, collisions are possible if we simply pick this second-level hash function randomly, without checking/ensuring as above. A collision-free function can be found with a one-time exercise (since keys are static) as above.

`... so to truly have no collisions in this 2nd level, one may need to try a few hash functions in this level for each value of j.`

True, for each value of j. Each slot contains different set of keys, and so the non-collision function needs to be worked out separately for each slot's set of keys.

`Is it fair to assume that a simple sequence of random "try and error" (i.i.d sampling) of hash functions (in this 2nd level) is "as good as it gets" at least for this perfect hashing design?`

Since our aim is no collisions at the second-level, I think the individual sets of keys in each slot does require the trial-error, because the hash functions outcome really depends upon the input keys. (I have not yet checked the Fredman's (et al.) paper you referenced).

Theorem 11.9, quoted (CLRS): "If we store $n$ keys in a hash table of size $m=n^2$ using a hash function $h$ randomly chosen from a universal class of hash functions, then the probability of there being any collisions is less than 1/2."

# Answer
> 0 votes
Suppose that your hash $h$ function maps $\\{1,\ldots,m\\}$ to $\\{1,\ldots,n\\}$, where $m \> n$. According to the pigeonhole principle, there exist two inputs $a \neq b$ such that $h(a) = h(b)$. In other words, collisions are unavoidable.

The point of hashing is not that it avoids collisions. Instead, if you choose a random (or random enough) hash function, then collisions are unlikely.

Furthermore, algorithms that use hashing are able to handle collisions. Their performance degrades with the number of collisions. If parameters are chosen so that the average number of collisions is small, then these algorithms will be efficient despite the collisions.

---
Tags: hashing
---


# Question
Title: Big Oh rules - How to argue in case of negative base
Let us say you have a function $C\_n = (-2)^n + 2^n$. It would seem that it would be correct to assume that the running time of this algorithm would be $O(2^n)$. However, how would I go about arguing this? The rule I had in mind would be that $a^n$ is $O(b^n)$ if $0 \< a \leq b$. But since $a$ is $\< 0$, this rule cannot be applied. How would one argue the relevancy of the roots in cases like this, where the specific conditions do not hold up?

# Answer
If $C\_n = -2^n + 2^n$, then this just simplifies to $C\_n = 0$, so I assume that you mean $C\_n = (-2)^n + 2^n$. Then:

$$ C\_n \le |-2|^n + 2^n = 2^{n+1} = O(2^n). $$
> 1 votes

# Answer
> Let us say you have a function $C\_n = (-2)^n + 2^n$. It would seem that it would be correct to assume that the running time of this algorithm would be $O(2^n)$.

You mention *the running time of this algorithm*, but the text doesn't mention any algorithm. *Asymptotic analysis is about real-valued functions.* It has nothing to do with algorithms. Asymptotic analysis can be used to understand the running time of algorithms, but it exists separately of algorithms. Moreover, it is often applied outside the realm of algorithms. For example, the number of primes in the interval $1,\ldots,n$ is $\Theta(n/\log n)$ (the prime number theorem); $n! \sim \sqrt{2\pi n}(n/e)^n$ (Stirling's approximation); and so on.

Furthermore, in most reasonable computation models, $C\_n$ is not the running time of any algorithm. Indeed, $C\_1 = 0$ whereas $C\_2 = 8$. This suggests that the algorithm is told the length of the input, and based on that, it can decided to immediately halt when $n = 1$ (more generally, when $n$ is odd), and to do some computation when $n = 2$ (more generally, when $n$ is even). The algorithm must be told the length of the input, since without observing the input, it cannot tell whether $n=1$ or $n=2$ in zero time units.

Algorithms which depend arbitrarily on the length of the input do exist and are being studied (they are called *non-uniform* algorithms), but actual algorithms implemented on a computer are typically not of this kind.

> However, how would I go about arguing this?

You would use the definition. Here is one popular definition of big O notation: if $f,g\colon \mathbb{N} \to \mathbb{R}\_+$ (where $\mathbb{R}\_+$ stands for the *non-negative* real numbers) then we say that $f(n) = O(g(n))$ if there exist $M,N\>0$ such that $f(n) \leq Mg(n)$ for all $n \geq N$. Using this definition, we can easily see that $C\_n = O(2^n)$: take $M=2$ and arbitrary $N$.
> 0 votes

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


# Question
Title: One-dimensional packing problem: Optimal decomposition of music structure
I am currently working on my Master thesis on the visualization of music structure and I'm looking to find an optimal description of repetitions found in a piece of music.

## Problem Description

Given a section range in a song in seconds (or samples) , e.g. \[10,20\], I can look up where this section is repeated. Then we end up with a set of repeating sections like: \[\[10,20\], \[40,50\], \[70,80\]\]. We call this a **group**. A group has a certain **fitness** given to it.

*(As a sidenote, the fitness of a group is defined as a combination of the sum of similarity values and how much of the song they cover alltogether)*

Our goal is to find a set of **disjoint** groups that altogether have the **highest fitness**; the optimal decomposition of the repetitions. Below are two different valid decompositions of the same song, one course, and one fine decomposition.

We are provided with a set of all candidate groups, here's a small selection, sorted top to bottom by fitness:

## Current Greedy Method

1. Sort all candidates by fitness
2. Pick group *G* with the highest fitness
3. Remove any groups from candidates if they have overlap with *G*
4. Repeat from step 2 until no candidates are left

## Bonus

Sometimes the candidates overlap every so slightly, which in the context should perhaps not immediately lead to disqualification.

There are options to relax the no-overlap rule. Note that each of the sections in a group has a different brightness. This brightness corresponds to a confidence, so in a group some sections are more certain to be proper repetitions than others.

For a group of sections *G* that we wish to add to a set of groups of sections *S*, we can:

* simply remove sections from *G* if they overlap with any sections in *S*
* trim the sides of to-be-added sections from *G* if they overlap with any sections in *S*
* keep the overlapping sections in *G*

I hope this problem is interesting enough to you to give it a shot! Thank you!

# Answer
> 3 votes
If $n'$ is the number of groups, this problem admits no $2^{o(n')}$-time algorithm for any choice of a constant $\epsilon \> 0$, unless the exponential time hypothesis (ETH) fails.

Let $G = (V, E)$ be an undirected graph with $n$ vertices $v\_1, \dots, v\_n$ and $m$ edges $e\_1, \dots, e\_m$.

Construct an instance of your problem by creating $n'=n$ groups as follows:

* For each vertex $v\_i \in V$, add a new group with fitness $1$ containing all intervals $\[j-1, j\]$ where $j$ is such that $v\_i$ is an endpoint of $e\_j$.

Any independent set $S \subseteq V$ of $G$ induces of collection of non-intersecting groups (except for the boundaries of the intervals) with total fitness $|S|$. On the converse, any subset of $S'$ non-intersecting groups must have total fitness $|S'|$ and induces an independent set of size $|S'|$ in $G$.

The claim follows since, assuming the ETH, there exists no $2^{o(n)}$-time algorithm for independent set.

Moreover, assuming $\mathsf{P} \neq \mathsf{NP}$, the above reduction also shows that for any constant $\epsilon\>0$ there exists no polynomial-time $n^{1-\epsilon}$-approximation algorithm for your problem, even in the special case of unitary fitness. See, e.g., here.

---
Tags: algorithms, heuristics, packing, decomposition, optimal-strategy
---


title: Finite languages $L\in RE$

text:
# Question
Title: Finite languages $L\in RE$
I want to check if I understood it in the right way. In some example where $L\in RE$ the explanation deal with 2 cases: 1st when $L$ finite and 2nd when $L$ infinite. In the second case $L\in R$, isn't? Is it possible somehow that $L\in RE\setminus R$ be finite?

# Answer
> 1 votes
The answer is no. Every finite language is regular, and thus decidable. Therefore the existence of a finite language $L$ in $ \text{RE} \setminus \text{R}$ is impossible. However, note that there languages $L$ in $\text{RE}\setminus \text{R}$ (e.g., $Halt\_{TM}$), and by what we have seen previously, such languages have to be infinite.

---
Tags: complexity-theory, formal-languages, regular-languages
---


# Question
Title: Is there an algorithm that can ensure everyone gets bussed to their destination on time, while minimizing the time spent on a bus?
Suppose I am a bus transportation company. I have n buses. I want to change the bus routes so that the "average" commuter spends as little time on the bus as possible, while being able to arrive at as close to their final bus station at their desired time as reasonably possible.

**Inputs:** Origin bus stations, destination bus stations, and desired time of arrival for each passenger.

**Constraints:** The average commuter shall arrive no earlier than 15 minutes prior to their desired time of arrival.

As far as I am aware, no readily available (commercial or otherwise) solution exists.

# Answer
> 1 votes
This problem is NP-hard. You can reduce the Hamiltonian-Cycle problem to this problem. Given an instance of the Hamiltonian-Cycle problem, fix a vertex $v$. Assume there is exactly one bus and $2n - 2$ passengers, where $n$ is the number of vertices in the graph. We set the passengers such that one passenger wants to travel from $v$ to each other city in the graph and one to travel from each other vertex to $v$.

Claim. The given graph admits a Hamiltonian-Cycle, if and only if the total travelled distance is $2\frac{n (n-1)}{2}$.

Proof. An optimal route is a Hamiltonian-Cycle from $v$ \[try to see why\]

# Answer
> 0 votes
I have a feeling that the best solution is reinforcement learning. Simply put, with the data in hand (or simulated data), label the rewards as median or mean time spent on the bus and median or mean amount of time before desired time of arrival, with a possible consequence that arrival after the median time results in no long-term reward (we don't want commuters to be late.)

---
Tags: algorithms
---


# Question
Title: Fastest way to solve a system of linear equations
I have to solve a system of up to 10000 equations with 10000 unknowns as fast as possible (preferably within a few seconds). I know that Gaussian elimination is too slow for that, so what algorithm is suitable for this task?

All coefficients and constants are non-negative integers modulo p (where p is a prime). There is guaranteed to be only 1 solution. I need the solution modulo p.

# Answer
> 13 votes
A LU decomposition of a $n \times n$ matrix can be computed in $O(M(n))$ time, where $M(n)$ is the time to multiply two $n \times n$ matrices. Therefore, you can find a solution to a system of $n$ linear equations in $n$ unknowns in $O(M(n))$ time. For instance, Strassen's algorithm achieves $M(n) = O(n^{2.8})$, which is faster than Gaussian elimination. See https://en.wikipedia.org/wiki/Invertible\_matrix#Blockwise\_inversion.

Rather than trying to implement this yourself, I would suggest using a library: e.g., a BLAS library.

# Answer
> 5 votes
There is what you want to achieve, and there is reality, and sometimes they are in conflict. First you check if your problem is a special case that can be solved quicker, for example a sparse matrix. Then you look for faster algorithms; LU decomposition will end up a bit faster. Then you investigate what Strassen can do for you (which is not very much; it can save 1/2 the operations if you multiply the problem size by 32).

And then you use brute force. Use a multi-processor system with multiple threads. Use available vector units. Arrange your data and operations to be cache friendly. Investigate what is the fastest way to do calculations modulo p for some fixed p. And you can often save operations by not doing operations modulo p (result in the range 0 ≤ result \< p) but a bit more relaxed (for example result in the range -p \< result \< p).

# Answer
> 3 votes
The best way to solve big linear equations is to use parallelisation or somehow to distribute computations among CPUs or so.

See CUDA, OpenCL, OpenMP.

A lot of people suggests `Strassen's algorithm` but it has a very big hidden constant which makes it inefficient.

By the way: your linear equations might be very sparse(a lot of zeros), there are few very neat optimisations to solve them in parallel.

# Answer
> 2 votes
In real problems when the size is large ($n\>100000$) the best approach is the numerical solution of the system by an iterative method like GMRES, CG, BiCG, etc. All those algorithms depends strongly on matrix-vector products, so the complexity is as much as $O(n^2)$ which performs better than a direct solution by a LU decomposition with complexity of $O(n^3)$.

Sometimes the scale of the problem is not large enough to the proposed methods to be an improvement compared to LU decomposition, so there is a work you have to do in balance the applicability of the methods.

---
Tags: algorithms, linear-algebra, matrices, numerical-algorithms
---


# Question
Title: How do I use the Myhill-Nerode theorem to show that a language is not regular?
My language is the repetition of 0 to a length that's a power of 2:

$L = \\{ 0^k \mid k=2^n, n \geq 1 \\}$

I want to know how to use the Myhill-Nerode theorem to show that this language is not regular.

This is my first attempt at doing this although I am confident that I am wrong:

$j, p = 2^h$ for 2 distinct values of $h$, $h \in \mathbb{N}$:

$a = 0^{j/2}$

$b = 0^{p/2}$

$c = 0^{j/2}$

$ac = 0^{j/2}0^{j/2} = 0^j$ is in my language since $j$ is of the form $2^n$

$bc = 0^{p/2}0^{j/2}$ is not guaranteed to be in my language for every $p$ and $j$, since $j \ne p$

Thus my language must not be regular since $ac$ is in it but $bc$ is not.

# Answer
> 3 votes
If you want to use Myhill-Nerode to show that a language is not regular, you need to prove that there are infinitely many equivalence classes.

Basically here, it suffices to prove that each $0^j$ is in a different class.

For instance $0^9$ and $0^{10}$ are not in the same class, because $0^90^7\in L$ while $0^{10}0^7\notin L$. Try to write the general proof for any $0^i$ and $0^j$ with $i\neq j$.

# Answer
> 1 votes
Just to make a more precise argument according to the definition below:

> **Myhill-Nerode Theorem**: Given a language $ L \subseteq \Sigma^\* $, Suppose $$ \forall x,y \in S, (x \neq y) \wedge (\exists z \in \Sigma^\* ,L(xz) \neq L(yz)) $$ where S is an infinite set. Then L is not a regular language.

For the given problem, We have $L(w) =\\{ 0^k | k = 2^n, n \geq 1\\}$.

Take $S = L$ (note: the set $S$ is infinite and **not necessarily regular**!).

Now take any two distinct elements from set $S$, $x=0^{2^i}$ and $y=0^{2^j}$, and take $z=0^{2^{i+1}-2^{i}} = 0^{2^i}$.

Then $xz = 0^{2^i}.0^{2^i} = 0^{2^{i+1}} \in L$. So $xz \in L$.

Now $yz = 0^{2^i}.0^{2^j} = 0^{2^i+2^j}$

Here, we have two cases:

case 1: if $i \> j$: we have, $yz = 0^{2^j.(2^{i-j}+1)} \notin L$ since $(2^{i-j}+1)$ is odd.

case 2: if $j \> i$: Similar to the previous argument we have, $yz = 0^{2^i.(1+2^{j-i})} \notin L$ since $(2^{i-j}+1)$ is odd. Thus, $yz \notin L$

Hence, we will get an infinite number of distinct quotients as $S$ is an infinite distinctive set.

Thus, $L$ is not regular.

(Remark: This can be extended to any language of the form $\\{a^{x^i}|i \geq 1 \wedge a \in \Sigma\\}$ for any $x\in \mathbb{N}$)

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


# Question
Title: Producing a total or partial order from an inconsistent relation
Imagine I want to construct a total order from a set of elements, $E$, but the comparison function produces results that are non-deterministic. I produce a list of element pairs (e, e) through repeated application of the comparison function, such that each element in the set is represented at least once.

How can I use this input to produce a total order? What is the class of algorithms that can be applied here?

---

For greater clarity, I'll provide a concrete example.

### What are the best pizza toppings?

My set of elements $E$ includes some popular pizza toppings: pepperoni, cheese, mushroom, pineapple, bellpepper, olive.

Then for each of my friends, I pick randomly sized subsets of toppings and ask my friend to put them in order from best to worst. My friends dutifully reply, and create the input for my algorithm:

* cheese, pepperoni, olive
* cheese, pineapple, mushroom, olive
* bellpepper, mushroom, olive
* pepperoni, cheese, olive
* cheese, bellpepper

There does seem to be a fuzzy order here (everyone agrees olives are the worst) but my friends have not arrived at consensus about which is the better pizza topping: cheese or pepperoni. Considering where items occur in the inputs, and how frequently they occur, I would probably produce an order something like this.

* cheese \> pepperoni \> bellpepper \> pineapple \> mushroom \> olive

I'm just not sure how to go about formalizing this and making it work for much larger inputs.

---

I think the solution probably involves graphs and weighted edges, but I lack sufficient familiarity with graph algorithms to recognize whether this is a named area of study. I already came across "topological sorting" but that only works for directed *acyclic* graphs, and I am specifically interested in inputs that cannot produce a DAG.

I also noticed that this problem seems similar to voting for elected representatives. Is it, in fact, the same class of problem?

# Answer
It's hard to say without more context and more modelling. It will require some assumptions on how the results of the comparison function relate to the (hidden) desired total order.

It's possible you might want the Bradley-Terry-Luce model. If so, there are many standard algorithms. See also https://cs.stackexchange.com/a/85204/755.

It's possible you might want some ranking system, like Elo, etc.

It's possible you might want a ranked voting system, such as IRV, Condorcet method, Borda count, or any of many others. They all have various flaws and tradeoffs. There is a proof that no system will have all the properties we might want -- see, e.g., Arrow's theorem and the problem of non-transitivity (that even if each of your friend's individual preferences is transitive, i.e., a total order, then there is no guarantee that there exists a global total order that is consistent with all of them).
> 2 votes

---
Tags: algorithms, order-theory, ordering
---


# Question
Title: Proving $\{0^{2^n}\}$ is not regular using pumping lemma
I am currently learning the pumping lemma, and encountered the following question, which I am unable to solve:

> Prove that $L = \\{ 0^n \mid \text{$n$ is power of 2}\\}$ is not regular.

I considered $w = 0^{2^n}$, where $n$ is the pumping lemma constant. Then I divided $w$ into $xyz$, where $y \ne \epsilon$ and $|xy| \leq n$. Hence, $|y|$ will be between 1 and $n$. So, $|xy^kz|$ satisfies $L$ if $|y| = 2$ for all values of $k$ and it is within the bound. So, how is $L$ irregular?

The question is to prove it is irregular but here it is coming as regular.

# Answer
If you choose $k = 2$ then, writing $|y| = m$, we get $$ xy^2z = 0^{2^n+m}. $$ Since $1 \leq m \leq n$, we have $$ 2^n \< 2^n+m \leq 2^n+n. $$ Cantor's theorem shows that $n \< 2^n$, and in particular, $$ 2^n \< 2^n+m \< 2^{n+1}. $$ Therefore $xy^2z \notin L$.

---

Let me take this opportunity to mention another misconception. *There are some non-regular languages which satisfy the pumping lemma.* Therefore the fact that you couldn't prove that a certain language is non-regular using the pumping lemma *does not imply* that the language is regular.
> 1 votes

---
Tags: formal-languages, regular-languages, pumping-lemma
---


# Question
Title: Determine the number of reachable states in a subset construction?
Is there a polynomial time algorithm to determine the number of reachable states in the subset construction of a NFA to a DFA without having to construct the entire DFA?

# Answer
Start with a 3SAT instance $\phi$ on $n$ variables with $m$ clauses $C\_1,\ldots,C\_m$. For each clause $C\_j$, we construct an NFA $A\_j$ which reads a binary input string, interpreting its first $n$ symbols as encoding a truth assignment, and checks whether the clause is satisfied. If $C\_j$ is satisfied, then on the $(n+1)$'th symbol it branches to $n$ new states.

Now consider an NFA consisting of the NFAs $A\_1,\ldots,A\_m$ together with an initial state with $\epsilon$-transitions to the starting states of $A\_1,\ldots,A\_m$ (alternatively, if you allow multiple initial states, you can just put all of them together). If $\phi$ is satisfiable then the number of reachable states in the corresponding DFA will be at least $n^m$, otherwise it will be at most $n^{m-1} + 2^m n + 1$.
> 3 votes

---
Tags: finite-automata
---


# Question
Title: How can I prove or disprove that the following function is bijection?
For a research project, I tried to prove or disprove that a function called xxhash128\_low is a bijection from 64 bit unsigned integer to 64 bit unsigned integer. I have shown that it is sufficient to prove that the following critical code is a bijection:

```
Input: a 64-bit integer x
0. Let c=0x9e3779b185ebcaa7
1. Let x_low= the 8-low bytes of c*x.
2. Let x_high= the 8-high bytes of c*x.
3. w= x_high+2*x_low.
4  y= shift right 3 bits of w.
5. return x_low XOR y.

```

What I have proved till now: returning only the low 64 bits, x\_low, can be shown to be a permutation. Also, y can be expressed as a function of x\_low (i.e., y=f(x\_low)).

# Answer
Originally, the hash function was defined as follows:

* Input: a 64-bit unsigned integer $x$.
* Calculate $(9E3779B185EBCB87)\_{16} \cdot x = 2^{64} x\_h + x\_l$, where $x\_l,x\_h$ are 64-bit unsigned integers.
* Output $x\_l \oplus \lfloor (x\_h + 2x\_l)/8 \rfloor$.

Under this definition, there is a collision: both $(2DCE4F983BBEB685)\_{16}$ and $(72E04DBED1540FE1)\_{16}$ map to $(A5C53FE6E277BD92)\_{16}$.

You can find such collisions using a cycle detection algorithm.
> 2 votes

---
Tags: hash, bit-manipulation
---


# Question
Title: What is the name of this type of program optimization where two loops operating over common data are combined into a single loop?
On an imperative programming language, let us consider the following program:

```
for i in 0..N { // N is the length of the arrays A, B, C.
  A[i] = A[i] + B[i];
}
for i in 0..N {
  A[i] = A[i] + C[i];
}

```

This program just sums three arrays $A + B + C$ component-wisely and store it to $A$.

We can easily transform this program into the following equivalent one:

```
for i in 0..N {
  let tmp = A[i] + B[i];
  A[i] = tmp + C[i];
}

```

I think the latter code is more efficient than the former because we can decrease the number of memory accesses.

Now I have a question.

What is the name of this type of program transform or program optimization? Can we also call this deforestation?

# Answer
It's called "loop fusion".

It's often more efficient, in the sense of doing more work per loop iteration and sometimes (as you say) other advantages. On the other hand, the fused loop in your example may also put more pressure on the CPU's cache prefetch system. So do test it before declaring it more efficient.
> 18 votes

---
Tags: terminology, compilers, functional-programming, efficiency, program-optimization
---


title: Reduction as a flowchart

text:
# Question
Title: Reduction as a flowchart
I'm trying to understand the reduction as a flowchart graph.

Let's say the boxes $A$ and $B$ are TMs/Functions and $x$ is the input. Is this plot represent reduction from $A$ to $B$ ($A\le B$) or from $B$ to $A$ ($B\le A$)? Or maybe it can be both of the way depending on the context?

# Answer
Let's say that $f:\Sigma^\* \to \Sigma^\*$ is a reduction from $A\subseteq \Sigma^\*$ to $B\subseteq \Sigma^\*$. A flowchart graph of $f$ looks like:

Indeed, $f$ maps all words in $A$ to $B$, and all words in $\overline{A}$ to $\overline{B}$.

The closest flowchart to the image that you attached corresponds to the reduction theorem, to be explined below. (You explicitly stated that the rectangles in the graph correspond to machines).

**The Reduction Theorem:** if there is a reduction from $A$ to $B$, then it holds that i) $B\in \text{R} \to A\in \text{R}$, and ii)$B\in \text{RE} \to A \in \text{RE}$.

**Sketch of The Proof:** The proof of the theorem goes as follows. Let $M\_f$ be a machine that computes a reduction $f$ from $A$ to $B$, and let $M\_B$ be a machine that decides (recognizes, respectively) $B$. Then, a machine $M\_A$ that decides (recognizes, respectively) $A$ operates as follows. On input $x$, $M\_A$ computes $f(x)$, and then it simulates the run of $M\_B$ on $f(x)$ and answers the same. The following is the flowchart corresponding to the proof.

Note that in both graphs, the arrow is to the rectangle corresponding to the language we are reducing to, $B$.
> 1 votes

# Answer
The arrow is going from $A$ to $B$. It means you are solving problem $A$ using problem $B$. So, it is a reduction from $A$ to $B$
> 1 votes

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


# Question
Title: Finding a grammar for $L=\{a^nb^mc^rd^s| n+m<r+s\}$
I am trying to find a grammar for $L=\\{a^nb^mc^rd^s| n+m\<r+s\\}$, which has the hint of it having "some similarity" to $L=\\{a^ib^j|i\<j\\}$

This last one is quite easy to get ($S\to aSb | Sb | b$), but still I am unsure on how to proceed.

I expect to manipulate the language by differentiating cases, and for example I found that if $n\>m$, I will have to solve $a^{m+k}b^mc^rd^s, k\ge1$, and if $n\<m$, I will have to solve $a^nb^{n+k}c^rd^s, k\ge1$, but, still I don't see the recursivity.

# Answer
Any word $w$ in $L$ can be split into two words $w$ and $w'$ such that $w \in \\{a^n b^m c^r d^s \mid n + m = r+ s \\}$, $w' \in \\{c^r d^s \mid r+s \> 0\\}$ and if the last symbol of $w$ exists and is $d$, then the first symbol of $w$ is $d$. On the other hand, every choice of $w$ and $w'$ that satisfies the above constrains induces a word $w w' \in L$.

In the following grammar the first two productions take care of generating $w'$, while the other productions generate $w$. In particular the nonterminal $X\_\alpha^\beta$ with $\alpha \in \\{a,b\\}$ and $\beta \in \\{cd\\}$ will generate all the words in $w \in \\{a^n b^m c^r d^s \mid n + m = r+ s \\}$ such that (i) if $\alpha=b$: then $n=0$ and (ii) if $\beta=c$ then $s=0$.

$$ \begin{align\*} S &\to Sd \mid X\_a^dd \mid Yc \mid X\_a^cc \\ Y &\to Yc \mid X\_a^cc \\ X\_a^d &\to aX\_a^d d \mid X\_a^c \mid X\_b^d \\ X\_a^c & \to aX\_a^cc \mid X\_b^c \\ X\_b^d &\to b X\_b^d d \mid X\_b^c \\ X\_b^c &\to bX\_b^cc \mid \varepsilon \end{align\*} $$
> 1 votes

---
Tags: formal-languages, formal-grammars
---


# Question
Title: Is it valid to make an admission of a topological space by a "partial quotient map"?
It is well-known that the Sierpiński space, $\\{F,T\\}$ endowed with topology $\\{\emptyset, \\{F\\},\\{F,T\\}\\}$, is admissible. I tried to implement it in Haskell.

First I implement $\mathbb{N}$ (including zero; some topologists might prefer denoting it by $S\_\omega$) by Peano definition:

```
data Peano = Zero | Succ Peano deriving (Eq, Ord)

```

This encodes $\mathbb{N}$, but there is one additional value lurking behind: `fix Succ`. I denote it by $\omega$, and I denote $\mathbb{N} \cup \\{\omega\\}$ by $\overline{S\_\omega}$. We observe that $\overline{S\_\omega}$ is in order topology.

I abuse this fact and implement the Sierpiński space by taking a quotient space. The quotient map $q$ is:

$$ q(o) = \begin{cases} F & \text{if } o \< \omega \\ T & \text{o.w.} \end{cases} $$

In Haskell, This can be realized by:

```
newtype Sierpinski = Sierpinski Peano

instance Eq Sierpinski where
    Sierpinski m == Sierpinski n = let
        q m = case m of
            Zero   -> False
            Succ n -> q n
        in q m == q n

```

But to think about it, `q` doesn't halt on $\omega$. In other words, `q` is partial, and doesn't match $q$. Is this really a valid implementation of the Sierpiński space?

# Answer
> 1 votes
When we implement a space we do not actually implement the space itself, but rather a *representation* of it. That is, an implementation of $X$ consists of a datatype $T$ and a partial surjection $\delta : T \to X$, as in Type Two Effectivity. When $\delta(p) = x$ we say that the datatype value $p \in T$ *represents* or *realizes* the point $x \in X$. Cruicially, there may be many values that represent the same point. Only $T$ exists in the computer, $X$ and $\delta$ are mathematical objects. A particularly well-behaved kind of representation is an admissible one, as you mention.

In your case, you correctly implemented an admissible representation of the Sierpinski space: $X$ is the Sierpinski space, $T$ is `Sierpinski`, and the surjection $\delta$ maps $\omega$ to $\bot$ and $\mathtt{Succ}^n \\,\mathtt{Zero}$ to $\top$. *There is no need for further quotienting*.

The attempt to define `==` on `Sierpinski` is *not* about quotienting, but rather trying to define the characteristic map $\mathrm{eq} : X \to \\{0,1\\}$ of equality as a map into Booleans, which is only possible when the space is discrete. You discovered that the Sierpinski space is not discrete.

If we have a representation $\delta : T \to X$ then we can form the representation of a quotient $Y = X/{\sim}$ as $\delta' : T \to Y$ where $\delta'(p) = \[\delta(p)\]\_{\sim}$. That is, quotienting affects the map but not the datatype.

# Answer
> 0 votes
Maybe? It depends on your definition of a quotient space. I would say no based on context I think? This is not an over approximation but it is a correct under approximation, albeit not a very useful under approximation. There is a sense in which you $q$ implementation is the best computable approximation of that function that it is the "greatest" computable function consistent with the corresponding classical function.

Domain theoretically, which I claim is the correct tool to use to answer this question, $q(\omega) \not= T$ but instead $q(\omega) = \bot$.

Further, keep in mind that actually Peano has a whole host of other values you didn't account for from a domain theoretical perspective such as $\bot$, $Succ(\bot), Succ(Succ(\bot))$, etc...

So anytime we try to implement a topology in Haskell like this what we're really trying to do is use the actual topology we get from the Haskell values to implement a subspace topology or some kind of embedding. This is known as an over approximation. So for instance we say we implement the natural numbers with the discrete topology using the Peano definition you gave above but we also claim this same type implements other richer topologies like the topology induced by the actual domain for that type or the extended natural numbers as you pointed them out. (P.S. using strictness annotations you can restrict some of these values to get closer to discrete topologies). Sometimes however we just want to implement all of the things we can implement and just accept we can't represent all the classical objects. We do this with the exact reals for instance which are the best computable approximation of the classical reals. This is an example of under approximation.

With quotient spaces things get even more tricky in what hoops we have to jump though to say we've implemented such a space. Mathematically you can quotient by any equivalence relation but with a computer we're generally limited to working only with the decidable equivalence relations. In domain theoretical language that means the equivalence relation must be a continuous function. Another way to implement an equivalence relation is to define a mapping to canonical members which is really what you've done here and you've defined the induced equivalence relation from it. But again you can only define the best computable approximation of the needed mapping here. The issue is that the actual function you need is not continuous/computable.

So we have to make a choice, what counts as a valid approximation? Well the reason we want to call this a quotient space is so that we can think of it as one and apply the theorems and reasoning that come along with thinking about this as a quotient space right? The only way the classical theorems about quotient spaces go though when talking about computable approximations is if we restrict ourselves to decidable/continuous equivalence relations (or equivalently canonicalization maps).

But you could say "well I only really care about the parts that are possible to compute". It turns out this is actually pretty useful sometimes. When working with such approximations as in the above any theorem you use from classical topology that goes wrong will cause an infinite loop but it won't result in your program outputting an incorrect result despite your correct classical proof! So if infinite loops are acceptable behavior in the cases that you can't compute something this is totally acceptable. One paper that springs to mind that does such a thing is A Simple Differentiable Programming Language where they give themselves an out anywhere a discontinuity is hit. For that use case this is a good enough approximation, for others its not.

So the thing to keep in mind is that with computers we're almost always approximating more exotic mathematical structures unless you really are trying to work with a domain in which case that's exactly what Haskell does. The question is then how good of an approximation is acceptable? Do you need an over approximation or is an under approximation good enough?

---
Tags: computability, topology
---


# Question
Title: Reduction from $A$ to $B$ as execution of Turing machines
As explained in answers to this question, reduction from $A \le B$ can be represented in the following way.

But in this example:  from here

At least as I understand it: The reduction is from $\overline{HP}$ to $L\_2$, so $A$ is $\overline{HP}$ and $B$ is $L\_2$. But it's implemented in the way that $M'$ is TM of $L\_2$ and $M$ is TM of $\overline{HP}$, and $M'$ execute $M$ (I mean $L\_2$ is the external and $\overline{HP}$ is the internal).

Where am I wrong?

# Answer
What confuses you is that the words in the languages are encodings of machines that simulate runs of other machines, but at the end of the day, these are just words. Specifically, given input $x = \langle M, x\rangle$ for the reduction, the reduction itself does not simulate the run of $M$ on $x$, the reduction only outputs $f(x) = \langle M'\rangle$ which is an encoding of a machine. The machine $M'$, by definition, simulates the run of $M$ on $x$, given any input $w$ for $M'$. You can think of this reduction as a python code $f$ that is given as input another python code $M$ and an input $x$ for $M$. Then, $f$ halts and outputs a python code $M'$. Note that $M'$ may never halt on any input $w$, but this is okay as $f$ never runs $M'$.

Please note that the first attached figure is irrelevant here as it does not describe how the reduction operates (how $M\_f$ computes $f(x)$, given $x$), it only describes how you can define a machine $M\_A$ for $\overline{HP}$ assuming that you already have: 1) a machine $M\_B$ for $L\_2$, and 2) a machine $M\_f$ that computes the reduction $f$.
> 1 votes

---
Tags: complexity-theory, turing-machines, computability, reductions
---


title: Trapezoidal decomposition of a graph

text:
# Question
Title: Trapezoidal decomposition of a graph
When we plan the motion of a robot we may apply the *trapezoidal decomposition* of free space. While applying the trapezoidal decomposition we add nodes to both the centers of trapezoids and vertical walls.

When a robot wants to traverse between obstacles it avoids the obstacles by following the nodes added. The nodes create a graph which provides a smooth traverse between the obstacles (at least so we assume). In this case we assume that we are creating a graph using all nodes.

Is it possible to plan a graph with only using the center of trapezoid or the center nodes of vertical walls?

My idea is; it depends on the situation (the position of obstacles, the shape of the robot etc.) But I could not image such graph which could be changed to a new graph with only using the nodes on the vertical walls. If we design the example do we need to increase the number of edges?

I think it is not necessity to increase the number of edges to manage to use only vertical walls' nodes, but I could not figure out how it could be possible exactly.

# Answer
In order to get valid paths in the free space from paths in the graph $G=(V,E)$ that is constructed via the trapezoidal decomposition, we require that all edges of $G$ lie inside the free space.

The segment between two centers of adjacent trapezoids is not always fully contained inside the free space. For example, consider a square and take a slightly smaller square with the same center as the obstacle. So, using only the nodes at the center of the trapezoid is not sufficient to find paths in the free space.

On the other hand, any segment between a pair of nodes centered at a vertical boundary of the same trapezoid is fully inside the free space, since trapezoids are convex. So, the graph $G'=(V',E')$ with as vertices the centers of the vertical boundaries with an edge between every pair of vertices that lies on the boundary of the same trapezoid lies fully within the free space.

---

So, why bother using the graph $G$ and not $G'$? One issue with $G'$ is that a trapezoid with $d$ adjacent trapezoids means $G'$ has the complete graph on $d$ nodes as a subgraph, which has $\Theta(d^2)$ edges. So in the worst case, finding a path in $G'$ takes at least $\Omega(n^2)$ time, where $n$ is the number of in the decomposition. On the other hand, $G$ has at most $2$ edges for each vertical trapezoid boundary, so at most two per vertex of the obstacle boundary, which means it has $O(n)$ edges and we can find shortest paths in $O(n\log n)$ using Dijkstra.
> 2 votes

---
Tags: computational-geometry, graph-traversal, robotics
---


# Question
Title: Is my algorithm to find the median of 2 sorted arrays O(log(m + n))?
I came up with a solution for LeetCode Problem 4:
Median of Two Sorted Arrays

The expected efficiency of this should be $O(\log(m+n))$, where $m$ and $n$ are the lengths of `nums1` and `nums2`.

For my solution I decided only to process only the first half of `nums1` and `nums2`.
Does that count as logarithmic time, or is it still linear time?

My Java code:

```
class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        // Don't need the entire array - only the first half
        int maxSize = nums1.length + nums2.length;
        int size = maxSize / 2 + 1;

        // Merged array and its index
        int[] merged = new int[size];
        int m = 0;

        // Left index, right index
        int l = 0;
        int r = 0;

        // Build the merged array
        while (m < merged.length) {
            if (l >= nums1.length) {
                // Left array exhausted - just add the right array
                merged[m] = nums2[r];
                m++;
                r++;
            } else if (r >= nums2.length) {
                // Vice versa
                merged[m] = nums1[l];
                m++;
                l++;
            } else {
                // Compare left and right
                int a = nums1[l];
                int b = nums2[r];

                if (a > b) {
                    merged[m] = b;
                    m++;
                    r++;
                } else {
                    merged[m] = a;
                    m++;
                    l++;
                }
            }
        }

        // Debug
        // for (int x : merged) {
        //     System.out.print(x + ", ");
        // }
        // System.out.println();

        // Find median based on the first half
        if (maxSize % 2 == 0) {
            // Divide with 2.0 instead of 2: important!
            return (merged[size-1] + merged[size-2]) / 2.0;
        } else {
            return merged[size-1];
        }
    }
}

```

Pseudocode:

> * Make a new array $m$, which is the size of the first half of both arrays combined
> * Merge both arrays together in the correct order into the array $m$
> (note that this will not fully iterate the first or second array, since $m$ is only the size of the first half of both combined arrays)
> * Return the last element of 'm', or the average of the 2 last elements of $m$ (the median of both sorted arrays)

Leetcode result:

```
Runtime: 2 ms, faster than 99.75% of Java online submissions for Median of Two Sorted Arrays.
Memory Usage: 40.1 MB, less than 81.65% of Java online submissions for Median of Two Sorted Arrays.

```

# Answer
> 1 votes
Judging from your description and your code, you are basically doing a merge of the two array but stop at the median. This means that your main loop (body) is executed $(m + n) / 2 \in O(m + n)$ times, which is linear in $m + n$. You could also figure that one out experimentally by trying your algorithm on a range of different inputs and plotting the time taken against $m + n$, I guess.

If you want to find a solution which takes $O(\log (m + n))$ time you could try working backwards: A binary search over a (sorted) array of length $n$ takes $O(\log(n))$ time.

---
Tags: algorithm-analysis
---


# Question
Title: Is there a computationally optimal point-in-polygon solution (for a dynamic scenario)?
I am approaching a problem where, among other things, I will have to repeatedly check if a point is within a (set of) polygon(s) in the 2D plane.

* the polygons are either convex or star-shaped with a non-singular kernel
* if multiple polygons, they touch each other (have at least a side in common with another polygon of the set)
* the point moves accoring to a phisical process, so it will not "jump" in the plane, but its movement in the plane will be continuous
* another system will keep the point within the area defined by the union of said polygons, but this might occasionally fail
* I need to know which polygon is bounding the point
* Polygons are given in advance and output of a pre-process that can be expanded

I know these solutions, in particular the "draw a line starting from your point and count the intersections" and the "sum the angles for each subsequent pair of vertices and check if it is 2$\pi$", but:

* both solutions require a lot of computation if one has complex polygons and several polygons
* those solutions are for the general case, where there is no dynamics involved, but a static point in a static polygon.

Is there a computationally optimal solution for the scenario I am considering? I think that leveraging the solution of the previous timestep should help in skipping/avoiding some computations in the next cycle, meaning that a "full" solution needs to be computed only at initialization.

Or am I stuck with running a full check at each cycle?

# Answer
> 1 votes
I can list three candidate approaches. I'm not sure how to choose among them -- you might need to experiment among them to see which will work best in your situation.

# Approach #1: sweepline algorithm

This can be solved with a straightforward application of a sweepline algorithm.

Sweep a vertical line from left to right, with increasing $x$-values. At any value of $x$, you'll have a binary search tree that, given $y$, lets you look up which polygon the point $(x,y)$ is contained in. There are two key ideas in sweepline algorithms: you only need one tree for each interval of $x$-values between two adjacent "events" (here each event is an intersection of two line segments from the exteriors of the polygons), so you only need only $O(n)$ binary search trees; and, each binary search tree differs from the previous one by a single insertion or deletion, so you don't need to store all of them separately, but you can store them jointly using a persistent data structure.

Now this makes it easy to solve your problem. At any moment in time, we know the $(x,y)$ position of the point and can look up which polygon it is contained in and a trapezoid inside that polygon it is contained in. As the point moves, once it leaves that trapezoid, we can query the data structure again. Each lookup into the data structure takes $O(\log n)$ time, so will be efficient.

# Approach #2: Graph of polygons

As a precomputation, build an undirected graph of polygons, where each polygon is a vertex, and two polygons are joined by an edge if they are adjacent (overlap in a point or line segment). Store this graph in an adjacency list representation. Also, find the polygon that contains the initial position of the point by any algorithm (e.g., linear scan over all polygons).

Note that you can answer point-in-polygon queries (given a point and a polygon, is the point inside that polygon?) in time linear in the number of vertices of the polygon.

Now, the algorithm is simple. Watch the movement of the current point, and as soon as it leaves the current polygon, check which polygon it has moved into by doing a point-in-polygon query on each adjacent polygon. Thus, when it leaves the current polygon, the work is proportional to the number of neighboring polygons, not to the total number of polygons.

There are various optimizations and improvements available:

* Optimization 1: We can speed up the process of finding when the point leaves the polygon it is currently inside. If we are guaranteed that once the point leaves a polygon, it will never come back to it, then we can use binary search over time to find the first instant when it has left the polygon. Each iteration of binary search requires one point-in-polygon query and we do logarithmically many iterations. If we don't have that guarantee, but we have an upper bound on the speed and/or acceleration and/or turning radius for the movement of the point, we can compute a lower bound on the time to leave the current polygon and return to it (based on the current position of the point and the polygon it is contained within), and use a modified binary search where we avoid jumping further into the future in any one step than given by that bound.
* Optimization 2: We can sort each adjacency list. Consider the adjacency list for polygon $P$. Suppose the perimeter of $P$ has length $\ell$. If you walk along the perimeter of $P$ starting at some point on the perimeter and returning to it, this maps each point on the perimeter to a number in the range $\[0,\ell)$, which gives a total order on points on the perimeter. This yields a total order on the polygons adjacent to $P$: map each neighboring polygon to the points of intersection on the perimeter of $P$, map those to numbers/intervals in $\[0,\ell)$, then sort by that. (We can resolve ties as follows: if two neighboring polygons both overlap with $P$ at the same point $p$, where $p$ is on some face of $P$, then imagine extending outward by a tiny bit $\epsilon$ from that face and look at the intersection with those two polygons.) So, sort each adjacency list in this way, as part of the precomputation/setup phase.

This now speeds up the process of determining which new polygon the point has entered, when it leaves the current one: instead of using a number of point-in-polygon tests that is linear in the number of neighboring polygons, it goes by the log of the number of neighboring polygons.
* Optimization 3: Compute the bounding box for each polygon. Now, before doing a point-in-polygon test, you can first check whether the point is in the bounding box, which will enable quickly rejecting some polygons.

You could also use this to speed up finding the polygon the initial position is within. Store all bounding boxes in some appropriate data structure (e.g., a quadtree). Now, given a point, use that data structure to enumerate all bounding boxes it is contained in, then test each with a point-in-polygon test.

# Approach #3: Graph of triangles

During a precomputation, triangulate each polygon, i.e., decompose it into a union of triangles. Now combine all these triangles, build a graph of triangles, and proceed as in approach #2, but using triangles instead of objects.

This replaces each point-in-polygon test with a point-in-triangle test, which is much faster; but because the point will traverse many more triangles than polygons, the number of iterations might be much larger. I'm not sure which approach will be faster in the end.

Also, the type of triangulation used might affect performance. I'm not sure whether it is better to choose a triangulation that minimizes the variance of the degrees in the graph or one that maximizes the variance (e.g., a fan decomposition).

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


title: Use DFA minimization on LR(1) states

text:
# Question
Title: Use DFA minimization on LR(1) states
I have recently started reading more about context-free parsing techniques, in particular LR parsing.

As I have read, LR state transition graph (or table(s)) used for finding handles in sentential form is created by first constructing NFA from grammar rules (with included position in the rule - dot and possibly lookahead terminal) and then by converting the NFA to DFA with powerset/subset algorithm to remove non-determinism.

LR(1) state transition graph is usually an order of magnitude larger than LR(0)/SLR(1)/LALR(1).

Is it worthy or even practically possible to use DFA minimization (either Hopcroft or Moore or Brzozowski) on LR(1) state transition graph to get a minimal LR(1) graph? I haven't found any literature mentioning this.

Also, is there an algorithm to convert NFA directly to minimal DFA? Perhaps by constructing NFA state subsets in some particular order?

# Answer
The following paper uses DFA minimisation for a minimal LR(1) parser: https://www.researchgate.net/publication/258746690\_An\_LR\_parser\_with\_less\_states
> 1 votes

# Answer
As shown here, minimizing the states in an LR(1) parser is NP-hard. The basic idea is that given an arbitrary graph, you can construct a grammar such that for every node in the original graph, the LR(1) parser contains a corresponding state in its state graph, and two states can be merged if and only if there is no edge between them in the original graph. Then finding the minimum number of states for the LR parser is equivalent to finding a minimum coloring for the original graph.

For example, consider the following grammars

```
S = 1Xa
S = 1Yb
S = 2Xc
S = 2Yd
X = @
Y = @

```

and

```
S = 1Xa
S = 1Yb
S = 2Xc
S = 2Ya
X = @
Y = @

```

where 1, 2, @, a, b, c, d are arbitrary distinct tokens. In the first case, you'll end up with two states that can be merged, while in the second case, there will be a reduce-reduce conflict with the `a` token if you try to merge them.
> 1 votes

---
Tags: context-free, finite-automata, nondeterminism, lr-k
---


title: Finding n farthest leaves in a tree

text:
# Question
Title: Finding n farthest leaves in a tree
Given a tree $T$, I want to find a subset $N$ of $n$ leaves that are farthest apart. I.e., I want to find $N$ that maximizes function:

$$f(N)=\sum\limits\_{x\_1,x\_2 \in N, x\_1 \neq x\_2}{dist(x\_1,x\_2)}$$

where $dist(x\_1, x\_2)$ is the number of edges in a path between two vertices/nodes $x\_1$ and $x\_2$.

What algorithm can I use?

# Answer
> 3 votes
If you have a binary tree, you should be able to solve this using dynamic programming.

Let $A\[v,j,k\]$ denote the maximum possible value of the objective function

$$f'(N) = \sum\_{x\_1,x\_2 \in N} \text{dist}(x\_1,x\_2) + k \sum\_{x \in N} \text{dist}(v,x)$$

where $N$ ranges over all subsets of exactly $j$ leaves from among those that are descendants of $v$ (i.e., leaves of the subtree rooted at $v$).

If $v$ is a leaf, it is easy to compute $A\[v,j,k\]$ for all $j,k$.

If $v$ has one child $v'$, it is easy to compute $A\[v,j,k\]$ for all $j,k$ from $A\[v',\cdot,\cdot\]$.

So now suppose $v$ has two children $v',v''$. Then we can work out a recursive equation for $A\[v,j,k\]$ in terms of values $A\[w,\cdot,\cdot\]$ where the $w$'s are descendants of $v$:

$$A\[v,j,k\] = \max A\[v',j',k+j''\] + A\[v'',j'',k+j'\] + 2 j' j'' + jk$$

where $j',j''$ range over all values such that $j'+j'' = j$, $0 \le j',j'' \le j$. The intended meaning is that $j'$ counts the number of leaves in $N$ that are descendants of $v'$ and $j''$ counts the number of leaves in $N$ that are descendants of $v''$. In other words, we split $N=N' \cup N''$ where $N'$ contains $j'$ leaves from the descendants of $v'$, and $N''$ contains $j''$ leaves from the descendants of $v''$; then (loosely speaking) we compute the maximum value of $f'(N)$ in terms of the maximum values of $f'(N')$ and $f'(N'')$. The $2jj'$ term counts distances of the form $\text{dist}(x\_1,x\_2)$ where $x\_1 \in N'$ and $x\_2 \in N''$. The $jk$ term accounts for the fact that the $j$ root-to-leaf paths all need to be extended by one edge (thank you @j\_random\_hacker).

---

If you have an arbitrary tree (not necessarily a binary tree), you can convert it to a binary tree as follows: whenever you have a node $v$ with $m$ children, create a little binary tree with $m$ leaves, then put $v$ at the root of that binary tree and paste the children of $v'$ in at its $m$ leaves. Put a distance of 0 on all the edges of that new little binary tree except the top level. Repeat recursively.

In this way you obtain a binary tree where every edge has a distance of either 0 or 1 on it, and the distance between two vertices $v,w$ is the sum of the distances on the edges in the path between $v$ and $w$. Now you should be able to generalize the above algorithm to that case. I'll let you handle the details.

---
Tags: algorithms, trees
---


# Question
Title: Which pretrained model will be best for my dataset?
I am trying to build a classification algorithm having 28 classes. These classes consists of **Logo** of companies like adidas , Nike etc. I have very low dataset below than 100 images and greater than 70 images. I have trained CNN model but not got decent results . Accuracy is not good. I want to switch on pretrained model. I don't know which pretrained model should I use either VGG , ResNet etc. because I saw on Internet that you may use Pretrained model on similar dataset but I have logo of companies , I don't know that any pre trained model is trained on such similar type of objects or not. How should I choose pre trained model that will performs well on my dataset.

# Answer
> 2 votes
There's no general answer. In this field, you'll just have to try multiple approaches and see how well they work. We usually won't know what will work best until we try it.

I can suggest three candidate approaches:

1. Get more data.
2. Use a pre-trained model and fine-tune it. You can use any state-of-the-art model, pick a version that was pre-trained on ImageNet, and then fine-tune it (either fixing the first n-1 layers and training only the last layer; or training all layers, but with a smaller step size).
3. Use few-shot learning. This will probably require more sophisticated methods and more study.

Aggressive data augmentation might be useful.

---
Tags: machine-learning, neural-networks, computer-vision, image-processing, python
---


# Question
Title: Approximate max weight path in directed graph
## Context

This question is related to the fact one can't use Bellman-Ford to find max weight paths in directed graphs with cycles. The reason is that giving a new graph $\tilde{G}$ with negative weights (e.g. $\tilde{w}\_{ij} = - w\_{ij}$) will result in cycles with negative sum, thus no minimum cost walk exists in $\tilde{G}$.

## General question

How well can we approximate the maximum weight path between $i$ and $j$ in $G$, using the shortest path algorithm on a graph $\tilde{G}$ with transformed weights $\tilde{w}\_{ij}$ ? In my case, one has $w\_{ij}\in\mathbb{N}\setminus\\{0\\}$. The transformed weights $\tilde{w}\_{ij}$ can be obtained using any function, but I assume a decreasing function $f$ is well adapted so that $w \< w' \iff f(w) \> f(w')$.

## My approach

I am currently trying to use $f(w) = \dfrac{1}{w}$, in this context we have two important paths given a fixed path length $L$.

Denote a path $p = (i\_0i\_1, i\_1i\_2, i\_2i\_3, \dots i\_{L-1}i\_L$) with weights $W = (w^{(1)}, w^{(2)}, w^{(3)}, \dots, w^{(L)})$,

denote the maximum weight path of length $L$ by $p^\*$ with weights $W^\*$ achieving $$ W^\* = \arg\max\_W\\{\mathtt{Cost}(W)\\} = \arg\max\_W \sum\_{k=1}^L w^{(k)}$$ and the path $p\_\*$ achieving minimum transformed cost with weights $W\_\*$ $$ W\_\* = \arg\min\_W \sum\_{k=1}^L \tilde{w}^{(k)} = \arg\min\_W \sum\_{k=1}^L f(w^{(k)}) = \arg\min\_W \sum\_{k=1}^L \dfrac{1}{w^{(k)}}$$

## Specific question

In this specific context, do we have the approximation $\mathtt{Cost}(W^\*) \approx \mathtt{Cost}(W\_\*)$ ?

Or is it "very wrong" to replace $W^\*$ by $W\_\*$ ? What would be the distribution of the **relative error** defined as $$E\_r = \dfrac{\lvert\mathtt{Cost}(W^\*) - \mathtt{Cost}(W\_\*)\rvert}{\mathtt{Cost}(W^\*)}$$

## Statistical analysis

I have tried a quick statistical analysis as follows:

* Letting $L\in\\{3,4,5,6,7,8\\}$
* sampling $w \sim \mathrm{Uniform}(1,w\_{\max})$
* The value for $w\_{\max}$ was also picked from the set $\\{50, 100, 150, 200, 500\\}$
* for each combination of $L,w\_{\max}$ I computed $10^5$ values of $W^\*, W\_\*$ using $10^3$ candidate weights $W\_i$

**The results:**

* In $80.8\\%$ of cases we have $\mathtt{Cost}(W^\*) = \mathtt{Cost}(W\_\*)$ and even better $W^\*=W\_\*$
* When computing the **relative error** $E\_r$ one finds that $82.6\\%$ of error values are less than $0.001$, $89.7\\%$ less than $0.01$ and $99.9\\%$ less than $0.1$

The histogram for $E\_r \> 0$ is as follows

# Answer
You can't. That approach is a dead end. Finding the maximum (simple) path is NP-hard, by reduction from Hamiltonian cycle. See, e.g., How to prove NP-hardness of a longest-path problem?, How is the Longest Path Problem NP complete?, Longest cycle in a digraph, https://en.wikipedia.org/wiki/Longest\_path\_problem. It is also known to be hard to approximate, so you shouldn't expect any such simple approach to give a good approximation for all graphs.
> 1 votes

---
Tags: algorithms, graphs, approximation, statistics
---


# Question
Title: Is there another type of list than arraylist and linked-list?
My question is not about how arraylists or linked-lists work, but why there aren't other types of lists.

From my understanding, memory is accessed linearly by adresses. Thus, you have the choice to use property for your list or not to.

In the case of a arraylist, you know where an item lies by looking where the element at *index* 0 is and then adding *element-index* x *item-size*, so you have constant access time.
For the case of a linked-list, you don't use the structure of memory and need to follow a sequence of pointers, but rearranging the list is easy.

Does this already explain why these 2 types of lists are all that's possible? Or is there another non-existence proof? Are there other types of lists I just don't know of yet?

# Answer
> 1 votes
A "list" or "sequence" is an ordered collection of elements.

So there are a lot of lists.

In addition to an Array and a Linked List:

# Answer
> 2 votes
Yes, there are many types of lists depending on the arrangement of objects and the complexity of different types of operations. For example:

1. **Binary Tree or d-ary tree** is a hierarchical structure that stores nodes in the form of parent and child nodes.
2. **Directed or Undirected Graph** can be represented using adjacency list data structure which represents all possible connections between a set of objects. In other words, it is an array of lists.
3. **Doubly Connected Edge List** is used for performing fast operations on planar graphs and 3-dimensional polytopes.
4. **Skip List** is a randomized data structure that provides $O(\log n)$ insertion in a linked list

Likewise, you can even design your own data-structure based on different requirements. It is all about how you arrange and connect the objects.

---
Tags: data-structures, arrays, linked-lists, lists
---


# Question
Title: State whether the language is in $R$, $RE$, etc. The intuition for the solution
I saw the solution but can't understand the intuition of the following question:

Let's define $$L^{\ge k} = \\{w\in L : |w| \ge k\\}$$ and $$L=\\{\langle M\rangle | \exists k:L(M)^{\ge k} = \overline{HP}^{\ge k} \\}$$

$L\in R$ because $L=\emptyset$, the proof is a bit long and anyway I understood most of the steps, My question is about the intuition, what is the hint here that $L=\emptyset$ or any other hints for the solution?

EDITED

$$ \overline{HP}=\\{(\langle M\rangle, w)\mid M(w) \text{ doesn't halt}\\} $$ It's the complementary language of $$ HP=\\{(\langle M\rangle, w)\mid M(w) \text{ halts}\\} $$

# Answer
> 1 votes
The intuition is that finite languages are very simple in the sense that throwing a finite number of words from a language does not affect membership in $\text{R}$ or in $\overline{\text{RE}}$, etc. Therefore, since $L^{\geq k}$ is the result of throwing a finite number of words from $L$, we get that:

1. $L(M)^{\geq k} \in \text{RE}$, and
2. $\overline{HP}^{\geq k} \notin \text{RE}$.

So the language $L = \\{ \langle M \rangle: \exists k: \ L(M)^{\geq k} = \overline{HP}^{\geq k}\\}$ must be empty.

---

Formally speaking, we have the following claims:

**Claim 1:** For every non-trivial language $A$, and every finite strict subset $B\subsetneq A$, it holds that $A \leq\_m A \setminus B$.

**Hint for the proof of claim 1:** $B$ is finite and thus decidable. Therefore, given input $x$ for the reduction, we can check whether $x\in B$. Then you can proceed easily. Think where to map inputs $x$ from $B$, and where to map inputs $x$ from $\overline{B}$.

We also have the following similar claim which could be useful.

**Claim 2:** For every non-trivial language $A$, and every finite strict subset $B\subsetneq A$, it holds that $A\setminus B \leq\_m A $.

Given the above claims, we're done. Indeed, $\overline{HP} \notin \text{RE}$, and for every $k$, $\overline{HP}^{\geq k} = \overline{HP}\setminus \\{w\in \overline{HP} : |w| \< k\\}$. That is, $\overline{HP}^{\geq k}$ equals a non-trivial infinite language minus a finite subset, and so by claim 1, $\overline{HP}^{\geq k} \notin \text{RE}$. Also, it holds that $L(M)^{\geq k} \in RE$ for every machine $M$ (this is easy, you can prove that directly using standard closure properties and the fact that $L(M)^{\geq k} = L(M)\setminus \\{ w\in L(M): |w| \< k\\}$. Alternatively, you can use claim 2 but you have to be careful regarding the edge cases where $L(M)$ is trivial, etc.). Therefore, it cannot be the case that there is a machine $M$ with $L(M)^{\geq k} = \overline{HP}^{\geq k}$.

# Answer
> 1 votes
You could start from the fact that the language $HP$ of the Halting problem is r.e. If its complement $\overline{HP}$ were r.e. too then that would mean that $HP$ is recursive (in $R$) which is impossible.

Next, if there were at least one $k$ such that $L(M)^{\ge k} = \overline{HP}^{\ge k}$ then we could use this Turing machine $M$ to prove $\overline{HP}$ is r.e. as follow.

Split $\overline{HP}$ into two parts as

$$\overline{HP} = \\{s \in HP : |s| \< k\\} \bigcup \overline{HP}^{\ge k}$$ or $$ \\{s \in HP : |s| \< k\\} \bigcup L(M)^{\ge k}$$
The left set is in $R$ and $L(M)^{\ge k}$ is r.e, and hence $\overline{HP}$ is r.e. We have a contradiction. Therefore there is no such $k$ and hence $L$ is empty, that is in $R$.

---
Tags: complexity-theory, formal-languages, computability, halting-problem
---


# Question
Title: How do these additional cases fit into this Theorem about the optimal substructure of a longest common subsequence?
Theorem 15.1 (Optimal Substructure of an LCS)

> **Theorem** Let the $X=(x\_1,x\_2,\dots,x\_m)$ and $Y=(y\_1,y\_2,\dots,y\_n)$ be sequences, and let $Z =(z\_1,z\_2,\dots,z\_k)$ be any LCS.
>
> 1. If $x\_m = y\_n$, then $z\_k = x\_m = y\_n$ and $Z\_{k-1}$ is an LCS of $X\_{m-1}$ and $Y\_{n-1}$.
> 2. If $x\_m \neq y\_n$, then $z\_k \neq x\_m$ implies that Z is an LCS of $X\_{m-1}$ and Y.
> 3. If $x\_m \neq y\_n$, then $z\_k \neq y\_n$ implies that Z is an LCS of X and $Y\_{n-1}$.

format copied from related post

The above cases are intuitive and easily provable.

I do not understand additional cases not explicitly mentioned in the theorem:

What happens here:

$x\_m \neq y\_n$ and $z\_k \neq x\_m \neq y\_n$

The above statement combines cases 2 and 3. Does that mean Z is an LCS of both LCS of $X\_{m-1}$ and Y AND X and $Y\_{n-1}$? That doesn't make sense to me.

# Answer
If $x\_m = y\_n$ then *any* longest common sequence must end with $x\_m = y\_n$. This is what the first item covers.

If $x\_m \neq y\_n$, then there are three types of longest common sequences:

* Longest common sequences ending in $x\_m$.
* Longest common sequences ending in $y\_n$.
* Longest common sequences ending in neither.

These are all the cases. There is no other case.
> 1 votes

---
Tags: algorithms, dynamic-programming
---


# Question
Title: Is it possible to use an adjacency matrix for Bellman-Ford algorithm?
I have created a function that generates a complete, directed, and weighted graph, represented in an adjacency matrix but most Bellman-Ford implementations use an adjacency list. Is it even possible to use an adjacency matrix for Bellman-Ford without increasing significant time complexity? What would be the simplest way to use my graph-generating algorithm to the Bellman-Ford algorithm? Am I required to convert my matrix into a list?

# Answer
It is possible to use an adjacency matrix, but you will increase the runtime in most cases.

The main core of the algorithm is, that you iterate over all edges and try to relax the distance approximations. If you have an adjacency list, you can efficiently iterate over all edges in $O(|E|)$ time, and get the the worst case complexity $O(|V| \cdot |E|)$ in total.

If you however use an adjacency matrix, in most cases you cannot iterate over all edges as efficiently. You could iterate over all entries in the matrix, and check for each one if the edge exists (e.g. check if the distance stored is infinity), however that will require $O(|V|^2)$ time and therefore lead to a total complexity of $O(|V|^3)$.

If you have a dense matrix $|E| \approx |V|^2$, then this will result in the same time complexity $O(|V| \cdot |E|) = O(|V|^3)$, but if you have a sparse graph, $|E| \approx |V|$, then iterating over all edges will take significant slower and you get the complexity $O(|V|^3)$ even though with a with an adjacency list you would have the complexity $O(|V| \cdot |E|) = O(|V|^2)$.

So it would be better, to simply convert the adjacency matrix into an adjacency list, or just a simple list of all edges.
> 0 votes

---
Tags: algorithms, graphs
---


# Question
Title: Finding which functions are bounded by $O(n^2)$
I am asked to select the functions that are bounded by the Big-Oh function O(n^2): $f(n) \in O(n^2)$.

1. $f(n) = \sum\_{i=1}^{n} n$
2. $f(n) = \sum\_{i=1}^{n} i$
3. $f(n) = n + n^2$
4. $f(n) = 1$

I choose the answers 1, 2, and 4:

1. Simplifies to $n \cdot n = n^2$, which is **bounded** by $O(n^2)$
2. Simplifies to $\frac{n(n + 1)}{2} = n^2/2 + 1/2$, which is **bounded** by $O(n^2)$
3. $n^2 + n$ is obviously not bounded by $O(n^2)$
4. $1$ is obviously **bounded** by $O(n^2)$

However, it was alerted to me that one of my answers is incorrect. That seems strange, considering that after expanding all the expressions mathematically, I believe that I have chosen whether they are bounded by $n^2$ correctly.

# Answer
We have $n^2 + n = O(n^2)$. Indeed, if $n \geq 1$ then $n^2 \geq n$ and so $$ n^2 + n \leq 2n^2. $$
> 2 votes

# Answer
I know, that answer is done, is correct and is accepted, but let me add, that "function is bounded by $O(n^2)$" is not completely correct sentence and as such can lead to errors: $O(n^2)$ is set, so we can speak about boundedness by some member from it, but exact is to say, that **function is bounded by some** $\boldsymbol n^{ \boldsymbol 2}$ **factor**, starting from some number up to infinity.
> 2 votes

---
Tags: complexity-theory, time-complexity, algorithm-analysis, asymptotics
---


# Question
Title: For every non-trivial language $A$ and every finite strict subset $B \subsetneq A$, it's holds that $A \le_m A \setminus B$
It's claim 1 from *Bader Abu Radi*'s solution to this question.

My solution (have no idea how wrong it is):
$B$ finite $\Rightarrow$ $B\in R \Rightarrow$ exists TM $\langle M\_B\rangle$ that halts $B$.

**Wrong from here*
Let's define reduction $f$ from $A$ to $A \setminus B$, in the following way $f(\langle M\_B\rangle , x)=\langle M\_A\rangle$

When $M\_A$ implemented on input $w$ like this:

1. Run $M\_B$ on $w$ and answer on the same way

$x\in B \Rightarrow M\_B$ accept $x\Rightarrow M\_A$ accept $x\Rightarrow x\in M\_A$

$x\notin B \Rightarrow M\_B$ reject $x\Rightarrow M\_A$ reject $x\Rightarrow x\notin M\_A$
**till here**

So the reduction $A \le\_m A \setminus B$ true.

As I wrote early not sure how wrong is it, additionaly what're the changes that should be done to proof the second claim ($A \setminus B \le\_m A$) from the same answer.

**Edit**

$f(x)=x'=x\setminus x\_B$ (when $x\_B$ is all the $x$ that accepted by $M\_B$), because $M\_B$ halts on $B$ the reduction is applicable and work for any $x$.
It's implemented in the following way:

1. run $M\_B$ on $x$ (halts), if $M\_B$ accept, $x'$ reject
2. otherwise return $x$

If $x\notin A \Rightarrow x'\notin A \setminus B$
If $x\in A$:
$x\in B \Rightarrow M\_B$ accept $x \Rightarrow x'$ reject $\Rightarrow x'\notin A\setminus B$
$x\notin B \Rightarrow M\_B$ reject $x \Rightarrow x'=x\Rightarrow x'\in A\setminus B$

Is this one correct? Should something be added to it?

# Answer
As mentioned in the above comment, the format of your reduction is not correct, so you have to take care of that first, and think about it again. Also, the hint I gave in the question that you linked should be enough. Anyway, here is another hint.

**Hint:** consider the identity reduction that maps every word $x$ to itself, and try to understand why it does not work. Then, think what is the simplest thing you can do in order to fix the identity reduction.
> 2 votes

# Answer
The language $B$ is finite, and thus decidable. Let $M\_B$ be a TM that decides $B$. Also, as $B$ is strictly contained in $A$, we know that there is a word $y$ in $A\setminus B$.

The reduction operates as follows. Given input $x$, we check whether $x\in B$ (this can be done using $M\_B$), then:

* if $x\in B$: the reduction outputs $y$.
* if $x\notin B$: the reduction outputs $x$.

For correctness, one direction is clear: if $x\notin A$, then $f(x) = x\notin A\setminus B$. Conversely, if $x\in A$, then we split into cases: i) if $x\in B$, then $f(x) = y \in A\setminus B$. ii) if $x\in A\setminus B$, then $f(x) = x \in A\setminus B$. In both cases, $f(x)\in A\setminus B$, and we're done.

Note that $y$ is some fixed word - you can think of it as a constant hardcoded in the reduction.
> 0 votes

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


# Question
Title: Is there a real life example of algorithm that has running time $\Theta(1)$
I am a CS first year student, and as I was reviewing over the theta notation unit, I saw that $\Theta(1)$ exists. I was wondering if there was any real life example algorithm that has a running time of $\Theta(1)$.

# Answer
You talk about "real-life example", which is not really well defined. I take it to mean that you want an example of some "standard" algorithm that is studied in computer science and not something made up with the sole purpose of running in time $\Theta(1)$.

If you are fine looking at the complexity of algorithms that implement some data structure operation then there are several examples:

* A tree can be preprocessed in linear time so that, given any two vertices, their LCA can be found in $\Theta(1)$ time.
* A tree can be preprocessed in linear time so that, given a vertex $u$ and an integer $\ell$, the ancestor of $u$ at depth $\ell$ can be returned in $\Theta(1)$ time.
* Two Fibonacci heaps can be combined into a single Fibonacci heap in $\Theta(1)$ time.
* Inserting an element and decreasing the key of an element in a strict Fibonacci heap both take $\Theta(1)$ time.
* Any array $A\[1, \dots, n\]$ can be preprocessed in linear time so that, given two indices $i,j$, the quantity $\min\_{i \le k \le j} A\[k\]$ can be returned in $\Theta(1)$ time.
* Under reasonable assumptions, given a discrete probability distribution over a set $S$ of $n$ elements, it is possible to preprocess $S$ so that an element from $S$ can be sampled in $\Theta(1)$ time (according to the distribution).
* ...
> 2 votes

# Answer
Real-life algorithms with $\Theta(1)$ exist. Consider the problem of, given an array $A$ of $n$ integers of $O(\log{n})$ bits each and two integers $1\leq i,j\leq n$, computing $A\[i\]+A\[j\]$. This problem has a $\Theta(1)$ algorithm.

Of course, any problem with a $\Theta(1)$ algorithm is exceedingly simple.
> 2 votes

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


# Question
Title: Finding the Big-O and Big-Omega bounds of a program
I am asked to select the bounding Big-O and Big-Omega functions of the following program:

```
void recursiveFunction(int n) {
    if (n < 2) {
        return;
    }

    recursiveFunction(n - 1);
    recursiveFunction(n - 2);
}

```

From my understanding, this is a Fibonacci sequence, and according to this article here, https://www.geeksforgeeks.org/time-complexity-recursive-fibonacci-program/, the tight upper bound is $1.6180^n$. Thus, I chose all the Big-O bounds \>= exp(n) and all the Big-Omega bounds \<= exp(n). Below are the choices:

```
O(1)
O(log n)
O(n)
O(n^2)
O(exp(n))

Om(1)
Om(log n)
Om(n)
Om(n^2)
Om(exp(n))

```

The answer choices I selected:

```
O(n^2)
O(exp(n))

Om(1)
Om(log n)
Om(n)
Om(n^2)
Om(exp(n))

```

However, it was alerted that a few of my answers were incorrect (not sure which of them). This seems strange, considering that this recursive function mimics the calls of a fibonacci sequence which has a Big-Theta exponential time complexity.

# Answer
> 2 votes
$1.6180^n$ is not an upper bound to the running time of your program, not even up to multiplicative constants (in fact it is a lower bound). However $O(\phi^n)$ is a valid upper bound, where $\phi = \frac{1+\sqrt{5}}{2} \> 1.618$ is the golden ratio. It is also easy to see that your program takes $\Omega(\phi^n)$ time, so the above upper bound is asymptotically tight.

That said, $\phi^n \not\in O(n^2)$, so that answer is incorrect. Moreover, $\phi^n \not\in \Omega(e^n)$ since $\phi \< e$, so that answer is incorrect too.

Finally, notice that your answers contradict each other since you say that the running time of the program is both in $\Omega(e^n)$ and in $O(n^2)$ but $\Omega(e^n) \cap O(n^2) = \emptyset$.

---
Tags: complexity-theory, time-complexity, algorithm-analysis, asymptotics
---


# Question
Title: Can you reduce every decidable language to a regular language?
One of my previous questions on an exam was the following

> Can you reduce a decidable language to a given regular language? (decidable language $\leq \_m$ regular language). If so, does this mean that you can reduce every CFL to a regular language?

The reductions are all referring to *many-one* reductions. My intuition tells me that this is possible as all regular languages are also decidable.

# Answer
> 3 votes
In fact, every non-trivial language is $\text{R}$-hard. That is, every decidable language is reducible to every non-trivial language. Indeed, let $A$ be a decidable language, and let $B$ be a non-trivial language. A reduction from $A$ to $B$ operates as follows. On input $x$, check whether $x\in A$ (this can be done as $A$ is decidable), then:

* if $x \in A$, the reduction outputs $y\_{in}$
* if $x\notin A$, the reduction outputs $y\_{out}$

where $y\_{in}$ and $y\_{out}$ are constant words in $B$ and $\overline{B}$, respectively.

---
Tags: regular-languages, context-free, reductions
---


# Question
Title: Solving the recurrence $T(n)=T(n-2)+n^2$ with the iterative method
I'm trying to solve this recurrence. I applied the iterative method: $$T(n) = T(n-2)+n^2$$ $$=T(n-4)+(n-2)^2+n^2$$ $$=T(n-6)+(n-4)^2+(n-2)^2+n^2$$ $$\cdot$$$$\cdot$$$$\cdot$$ $$=T(n-2k) + \sum\_{i=0}^{k-1}(n-2i)^2$$ So $n-2k=1$ when $n=2k+1$ and we have: $$\sum\_{i=0}^{(n-3)/2}(n-2i)^2$$ Now how can I demonstrate that this series is $\Theta(n^3)$?

# Answer
> 1 votes
$$\sum\_\limits{i=0}^{(n-3)/2}(n-2i)^2 = \sum\_\limits{i=0}^{(n-3)/2}(n^2-4in+4i^2)=\\ =n^2\frac{n-3}{2}-4n\frac{\frac{n-3}{2}\left(\frac{n-3}{2}+1\right)}{2}+4\frac{\frac{n-3}{2}\left(\frac{n-3}{2}+1\right)\left(2\frac{n-3}{2}+1\right)}{6}=n^3\cdot A\_n$$ Where is easy to see, that $A\_n$ is bounded.

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


# Question
Title: How to calculate the basic steps in Fibonacci sequences to get nFn and n^2
I am reading ***Algorithms*** by *Sanjoy Dasgupta, Umesh Vazirani, Christos Papadimitriou* and I am trying to understand how the number of steps $nF\_n$ and $n^2$ were calculated. Here's the part of the book in Chapter 0 that mentions them. Functions `fib1` and `fib2` are written below the excerpt.

> `fib1`, which performs about $F\_n$ additions, actually uses a number of basic steps roughly proportional to $nF\_n$. Likewise, the number of steps taken by `fib2` is proportional to $n^2$, still polynomial in $n$ and therefore exponentially superior to fib1.

```
function fib1(n)
if n = 0: return 0
if n = 1: return 1
return fib1(n - 1) + fib1(n - 2)

```

```
function fib2(n)
if n = 0 return 0
create an array f[0 ... n]
f[0] = 0, f[1] = 1
for i = 2 ... n:
   f[i] = f[i - 1] + f[i - 2]
return f[n]

```

# Answer
> 1 votes
Let's start with the second function, fib2. If you count the number of operations, then you get only $O(n)$. So why is the running time given as $\Theta(n^2)$? The reason is that the Fibonacci numbers grow exponentially, and so addition can no longer be considered an $O(1)$ operation. The $n$-th Fibonacci number is $\Theta(n)$ bits in length, and this leads to a running time proportional to $\sum\_{i=2}^n i = \Theta(n^2)$.

As for fib1, we can easily write a recurrence for the running time $T(n)$: $$ T(n) = \begin{cases} O(1) & \text{if } n \leq 1, \\ T(n-1) + T(n-2) + \Theta(n) & \text{if } n \geq 2. \end{cases} $$ For the sake of asymptotic analysis, we can replace $\Theta(n)$ with $n$ and consider $S(n) = T(n)/n$, which follows the recurrence $$ S(n) = \begin{cases} O(1) & \text{if } n \leq 2, \\ S(n-1) + S(n-2) + 1 & \text{if } n \geq 3. \end{cases} $$ Thus $R(n) = S(n) + 1$ satisfies $R(n) = R(n-1) + R(n-2)$. Choosing appropriate initial values (which is fine, for the sake of asymptotic analysis), we find out that $R(n) = F\_n$, and so $T(n) = nS(n) = n(R(n) - 1) = \Theta(nF\_n)$.

---
Tags: algorithms, recursion
---


# Question
Title: (Un)computability of a restricted Halting Problem
Before I start with my question, I want to state some notation I am using. I fix some arbitrary but fixed enumeration of Turing Machines (TMs) and denote with $\Phi\_i : \mathbb{N}\to\mathbb{N}$ the function that is computed by the $i^\text{th}$ TM in this enumeration. Furthermore $\Phi\_i(x) \downarrow$ denotes that the computation of $\Phi\_i(x)$ terminates with some result $y$, i.e., $\Phi\_i(x) = y$. Furthermore, $\Phi\_i(x) \uparrow$ denotes that the computation of $\Phi\_i(x)$ never terminates.

I know that the following function is not computable: $$ f(x) = \begin{cases} 1 & \text{if } \Phi\_x(x)\downarrow \\ 0 & \text{otherwise} \end{cases} $$

Now, suppose we fix some $n \in \mathbb{N}$ and define: $$ h(x) = \begin{cases} 1 & \text{if } \Phi\_x(x)\downarrow \text{ and } x \le n\\ 0 & \text{otherwise} \end{cases} $$

I found some lecture notes which state that $h$ is computable because it is the characteristic function of a recursive set (because it is finite) and is therefore computable. Is this claim correct?

If $h$ is actually computable I can't think of an algorithm because one simply can't decide if $\Phi\_x(x)$ diverges to return $0$ in the case that $x \le n$.

# Answer
> 5 votes
Fix a value of $n$. For $b \in \\{0,1\\}^n$, consider the following algorithm $A\_b$:

> If $x \leq n$ then output $b\_x$, otherwise output $0$.

Clearly one of the $2^n$ algorithms of the form $A\_b$ computes your function $h$, hence $h$ is computable.

# Answer
> 3 votes
The subtle idea of computability of finite sets is that we don't necessarily need to know *which* TM machine actually decides that set or *how* it is internally. We just need to know that *some* TM decides that finite set.

Given $n$, there are (infinite) Turing Machines that decides every subset of $\\{0,1,\dots{},n\\}$.

You don't know which one is the set for which $h(\cdot)=1$, but you know that one of them is.

The definition of recursive/decidible set does not mention the fact that its characteristic function must have some "semantics" regarding some problem, but it concerns only on the fact that the 1 pre-image of that function is precisely that set.

---
Tags: computability
---


# Question
Title: If$A \leq_T B$ is given, can you reduce $\overline{A}$ to $B$ and vice-versa
If you are given two languages $A$, $B$ and $$A \leq\_T B.$$ Is it possible to $\overline{A} \leq\_T B$ or $A \leq\_T \overline{B}$?

Here is my shot.

Case 1: $\overline{A} \leq\_T B$

This is only possible if $A \leq\_m B$ exists and $B=\overline{B}$. As you can transform any many-one reduction to its complement, we can show that if $A \leq\_m B$, then $\overline{A} \leq\_m \overline{B}=B$. Thus $\overline{A} \leq\_m B$.

Case 2: $A \leq\_T \overline{B}$

This is the same as above but we need to change the role of $A$ and $B$.

# Answer
You say:

> This is only possible if $A \le\_m B$ exists and $B=\overline{B}$

But that condition simplifies to "false" since it can never the case that $B=\overline{B}$.

Anyway the answer to both cases is "yes". If $A \le\_T B$ then there is a Turing machine $T$ with oracle $B$ that decides $A$. By complementing $T$'s output we obtain a Turing machine with oracle $B$ that decides $\overline{A}$ showing that $\overline{A} \le\_T B$. Moreover, consider a Turing machine $T'$ with oracle $\overline{B}$ that simulates $T$ except for the following: whenever $T$ invokes its oracle for $B$ on some input $w$, $T'$ invokes its oracle for $\overline{B}$ on $w$ and then complements the result. Clearly $T'$ still decides $A$, thus showing that $A \le\_T \overline{B}$.
> 2 votes

---
Tags: formal-languages, reductions
---


# Question
Title: Number of hardware page tables and page directories kept in the MMU
How many hardware page tables (physical) and page directories are kept in the memory management unit?

If a cpu has a 32 bit virtual address, the upper 10 bits are used for the page directory, the middle 10 bits for the page table, and 12 bits for the 4K page frame. Does that mean 1 page directory containing 1042, 32 bit pointers, and 1042 page tables containing 1042, 32 bit pointers are needed?

What is the role of the page directory cr3 pointer control register in intel cpu?

# Answer
> 2 votes
The page tables are not kept in the MMU. In the MMU is a cache called the TLB which holds translated addresses. The TLB holds virtual addresses to physical addresses translations. For example, the TLB on intel core i5 has 64 entries for pages of 4KB.

Since the 10 upper bits are used as the offset in the page directory on 32 bits architecture, there are 2^10 = 1024 possible entries. The page directory has 1024 entries which hold the addresses of the page tables. Each page table has again 1024 entries holding the actual addresses of the page frames.

The CR3 register is used to locate the bottom of the page directory by the MMU. It holds a physical address (doesn't need to be translated).

---
Tags: memory-management, memory-hardware, virtual-memory, memory-allocation
---