title: CVAL is in P (technical detail)

text:
# Question
Title: CVAL is in P (technical detail)
I would like to clarify to myself the way that an algorithm that proves the statement in the title works:

I think the idea should be like this:

1. We assign the input values to the bit nodes
2. We calculate the incoming edges values for each logical operator node
3. We finally get to the output node, and we have our result

What I would like to ask, is how technically we do step 2? I mean, it must be a sort of travel on the graph, where we visit each edge at most, let's say, 3 times, right?

Can the following implementation fit (even though it is not too formal)?

1. let VALUE(v) be the circuit value (for the input x) for the node v
2. if we know the values of the incoming edges of v we just compute the value of v
3. else: (assume the logical operator of v is \*, and that the incoming edge comes from nodes v1,..,vn)
4. we return \*(VALUE(v1),...VALUE(vn))

# Answer
> 2 votes
Yes, you are correct.

Essentially, since you are dealing with a circuit, the graph representing it is a DAG (directed acyclic graph). Hence, your implementation will indeed compute the value of each node, and will visit each node not a lot of times (usually it will be the "number of children$+ 1$", as in your recursive case), so it won't be hard to show this is indeed polynomial.

If you want to formally prove the fact that its polynomial, then here is a small hint: try to show why you need poly space first, then use that to your advantage when computing the time it takes to traverse on the graph.

---
Tags: time-complexity, complexity-classes
---


# Question
Title: Considerations for space complexity analysis
There is a lot of information on time complexity analysis. For example, we know that for calculating the time complexity we study the number of operations (e.g. traversal, swapping, comparisons etc.) an algorithm performs.

I have not been able to lay my hands on the considerations for space complexity analysis.

---

**Q) What are the main considerations in space complexity analysis?**

# Answer
> 1 votes
Usually, when talking about Turing Machines - the space complexity refers to the furthest position the TM's head will reach in its entire execution for the given input. For every step further - another memory block can be used. (there are a few other alternative definitions, all of them use this basic one)

For practical terms, its not "crystal clear" but there are still a few rules:

* Numbers, letters (not full strings however!) and all other "primitive" types are usually considered with $O(1)$ space (even though that's not *entirely* correct).
* Lists with $n$ elements, or strings with $n$ letters - take $O(n)$ space
* Any other data structure takes whatever memory needs for its components (for example, if we have a structure holding two lists, the first with $k\_1$ elements and the second with $k\_2$ elements - then the storage will take $O(k\_1+k\_2)$)
* The total "space complexity" of a particular method is determined by the total space it allocated

---
Tags: algorithms, data-structures, algorithm-analysis
---


title: Is it true that $P = coNP$?

text:
# Question
Title: Is it true that $P = coNP$?
I have recently read the definition of $coNP := \\{L \ \mid \ \overline{L} \in P\\}$, where $L$ denotes a language. However, I am wondering what the difference between $P$ and $coNP$ is, since an elementary result of the theory of Turing Machines is that if $L \in P$, then $\overline{L} \in P$.

So is $P = coNP$ or is there something that I am missing here?

# Answer
$P=coNP$ is an open question, equivalent to the famous: "is $P=NP$ true?" question.

The definition of $coNP$ you have is incorrect. The correct definition is the following:

$$coNP:=\\{L\mid \overline{L}\in NP\\}$$ As you can see, it reads $NP$ and **not** $P$. It was probably a typo wherever you saw that definition.
> 3 votes

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


# Question
Title: Find the directed subgraph with least edges that preserves connectivity
I have a directed graph $G$ with a set of nodes $N$ and a set of edges $E$ with the following property : if $(A\to B)\in E$ and $(B\to C)\in E$, then $(A\to C)\in E$, for all nodes $A,B,C$.

I would like to find the subgraph $G'$ with the same set of nodes $N$ and a set of edges $E'$ such that:

1. The "connectivity" (not sure if this term can be used here) stays the same: if $(A\to B)\in E$, then there exists a path such that $\left(A\to N\_1\right)\in E'$, $\left(N\_1\to N\_2\right)\in E'$, $\ldots$, $\left(N\_p\to B\right)\in E'$
2. $\left|E'\right|$ is minimal

Is it a known/studied problem? What is the best algorithm to perform such a task? Is there a polynomial solution?

# Answer
"In mathematics and computer science, connectivity is one of the basic concepts of graph theory: it asks for the minimum number of elements (nodes or edges) that need to be removed to separate the remaining nodes into two or more isolated subgraphs", says this Wikipedia article.

Reachability is the term that refers to the ability to get from one vertex to another within a graph.

A transitive reduction of a directed graph $G$ is another directed graph $G'$ with the same vertices as $G$ and with the fewest possible edges that has the same reachability relation as $G$.

---

Your problem is known as **finding the transitive reduction** of a given directed graph, with the condition that the given directed graph is its own transitive closure and with the catch that the transitive reduction $G'$ must be a subgraph, i.e., every edge in $G'$ is also an edge of $G$.

An characterization of $G'$ is also given in that Wikipedia article. Since your graph $G$ is its own transitive closure, each strongly connected component of it is, in fact, a complete directed graph. So it is trivial to find "a directed cycle for each strongly connected component of $G$, connecting together the vertices in this component", with all edges in $G$. So we can always construct the transitive reduction as a subgraph of $G$. So, your problem is, indeed, equivalent to finding the transitive reduction of a transitively-closed directed graph.

---

The characterization of $G'$ also indicates how to find it in **linear-time** as below.

1. Compute the condensation of $G$ using any one of the linear-time algorithms. (We can make this step much easier, since $G$ is transitively closed.)
2. Select the edges of the transitive reduction that correspond to condensation of $G$, an acyclic graph.
3. For each strongly connected component of $G$, which is a complete directed graph, select a listing of all nodes in it as a cycle.
4. Return all edges selected in step 2 and 3.
> 2 votes

---
Tags: graphs, directed-graphs, subgraphs
---


# Question
Title: Why can't we use BFS with modifications to find shortest paths in weighted graphs
I came across this post about how we can get to all shortest paths from source (u) to destination (v) . If the algorithm is working in O(E + V), why can't we use it (after slight modifications) for weighted graphs? Why do we use a priority Queue in Djikstra's Shortest path Algorithm?

# Answer
> 4 votes
In non-weighted graphs it is not possible that in the following graph the shortest path from A to C goes via B.

```
         A ----- B
          \     /
           \   /
            \ /
             C

```

That is why in non-weighted graphs it is enough to extend the current search paths with just one edge: In the first cycle we look at A-B and A-C and determine that we have hit C, and so A-C is the shortest path.

With weighted graphs, this way of working could lead to wrong results. Here are some weights:

```
         A --1-- B
          \     /
           3   1
            \ /
             C

```

Here the paths A-B and A-C are also candidates (like in the unweighted graph), but once A-B is visited, the priority queue will receive B-C (as extension of A-B), and *that* path will get precedence over A-C! This is a scenario that can never happen in an unweighted graph, and so the priority queue is only useful when dealing with weighted graphs.

---
Tags: time-complexity, breadth-first-search, shortest-path
---


# Question
Title: What is wrong with this "proof" of $coNP = NP$?
I am wondering why the following "proof" of $coNP = NP$ does not work:

$\subseteq:$Let $L$ be a language in $coNP$, that means there is a non-deterministic Turing Machine $M$ that decides the complement of $L$, denoted by $\overline{L}$, in polynomial time. Then the Turing Machine $N$ that decides $L$ in polynomial time by reversing the result of running $M$ on $\overline{L}$.

$\supseteq:$ Reverse the above arguments.

Remark: I know that this "proof" can not be correct in this way, since $coNP = NP$ is still an open problem and it is certainly not that easy. But I do not understand where the reasoning above goes wrong. Could you please explain this to me?

# Answer
> 2 votes
Nondeterministic Turing machines are asymmetric in their treatment of accept and reject states: they accept if any path accepts, and reject if all paths reject.

If you swap the accept and reject states of an ordinary Turing machine then it will accept the complement of the language it accepted before, but that isn't generally true of nondeterministic Turing machines.

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


# Question
Title: Las Vegas vs Deterministic in one-way communication complexity
I recently learned about the one-way 2-party model of communication complexity in some lecture notes. It seems that all algorithms studied in this model are either deterministic or randomized Monte Carlo, i.e., they fail with some nonzero error probability. This made me wonder if there is an obvious reason why we don't consider Las Vegas (i.e. 0-error) algorithms in the one-way setting:

1. Does a lower bound $\Omega(c)$ bits for deterministic algorithms imply that $\Omega(c)$ bits are necessary (in expectation) even for Las Vegas algorithms, in the public coin one-way 2-party model of communication complexity?

It looks like this statement should be true (I'm not sure if it is!), simply because compressing the message size inevitably introduces some amount of error and since we are in the one-way model there is no way for Alice to rectify a (rare) bad event, e.g., by Bob asking Alice to send more bits.

2. In case the answer to question 1 is "No": What would be an example of a Boolean function where the **one-way** deterministic communication complexity is asymptotically worse than the Las Vegas communication complexity?

# Answer
First, let's describe the one-way model of communication, for computing a function $f$ on Alice's input $x$ and Bob's input $y$:

* Alice sends Bob a string $s$ depending on $x$.
* Bob broadcasts the value of $f(x,y)$.

Alice could be a probabilistic algorithm, and in that case, Bob might sometimes output the wrong answer. To make the task nontrivial, for each $x$, Bob should output the correct answer with probability $2/3$. The cost of the protocol is the maximum length of $s$, over all possible $x$ and coin tosses.

There are actually two different variants of this model. The model just described has *private coins*: Bob only gets to see the string $s$. Another variant has *public coins*: the string that Alice sends is a function of both $s$ and some randomness $r$ not depending on $x$, and Bob gets to see both Alice's message $s$ and the randomness $r$ used to generate it.

(There's actually one more nicety: is the string $s$ self-delimiting or not? We can convert a protocol of cost $C$ to a self-delimiting protocol of cost $C + O(\log C)$, so the difference is not significant.)

---

How would a Las Vegas algorithm look like? Bob should now always output the correct answer, and the cost of the protocol is the maximum, over $x$, of the *average* length of $s$.

Consider first the private coin model. Suppose that cost of such a protocol is $C$. This means that for every input $x$, there is a string $s$ of length at most $C$ which causes Bob to output $f(x,y)$ correctly. Hence we can convert this protocol to a deterministic protocol with the same cost.

Newman's theorem shows that we can convert a protocol in the public coin model to one in the private coin model at an additive cost of $O(\log n)$, thereby converting a public coin protocol of cost $C$ to a deterministic protocol of cost $C + O(\log n)$.

---

In the presence of interaction, Las Vegas protocols become nontrivial, since Bob can single to Alice that she should "try again". Since no such feedback mechanism is available in the one-way model, Las Vegas algorithms don't really make sense in that model.
> 0 votes

---
Tags: randomized-algorithms, communication-complexity
---


# Question
Title: set theory with RegEx on fen strings (or another parser)
how can you find if a regex call is a subset of another regex call on an predictable set of data

I have a string (chess Forsyth–Edwards Notation (FEN) string`rnbqkbnr/pppp1ppp/8/4p3/3P4/8/PPP1PPPP/RNBQKBNR w KQkq e6 0 2`)

If I use `/(.)/g` it matches the super set of any possible chess position, i.e. `/(r/)/g` matches r/ , a sub set of `/(.)/g`

is it possible to apply set theory to regex (or another parser) on stings that follow a pattern like FEN? if so, how can I calculate if one regex is a subset, superset, or equal set of another for this data type?

my goal is to find if a parsing function will find a subset of the possible fen positions that another function will find. is it possible to do this without mapping every possible fen string? that's not an option. should I use regex? or a different parsing system because the characters follow a pattern already?

# Answer
> 1 votes
There is an algorithm that checks, for every two regular languages $L\_1,L\_2$ given as DFAs, whether $L\_1 \subseteq L\_2$. The idea is to construct a DFA for $L\_1 \setminus L\_2$ using the product construction, and then to check emptiness, by checking whether some accepting state is reachable from the initial state.

If your regular expressions are "TCS-regular" (they don't use backreferences), then you can convert them to DFAs and use the algorithm above. While the conversion to DFA incurs exponential blow-up in the worst case, in practice this probably won't happen.

---
Tags: regular-expressions, parsers, sets
---


# Question
Title: How can I combine 2 PDA's into 1 PDA deterministically?
I have two PDAs one with $\\{a^i b^j \mid i \> j\\}$ and the other $\\{a^i b^j \mid i \< j\\}$.

I know how to combine these two PDAs non-deterministically. My question is how do I combine these two PDAs into one *deterministic* PDA? What's the process and could I get a visual example of how to do it?

# Answer
> 2 votes
The family of deterministic context-free languages is not closed under union. For example, as vonbrand mentions in a comment to this answer, the languages $\\{a^nb^n : n \in \mathbb N\\}$ and $\\{a^nb^{2n} : n \in \mathbb N\\}$ are both deterministic context-free, but their union is not.

What this means is that there is no general way to take two deterministic PDAs and to combine them into a deterministic PDA which accepts the union of the languages accepted by the constituent PDAs.

---
Tags: pushdown-automata
---


# Question
Title: Why don't we recognize Python as a compiler-based language?
I just read this Why doesn't Python need a compiler?

I know that Python isn't absolutely compiler or interpreted but it is both of them it's maybe an interpretive, high-level, and all-purpose programming language. Python uses PVM(interpreter) and Bytecode(that is output of a compiler). after all, **why do we classify Python as a compiler language in comparison to C for example?** **what does make Python different from C which is quicker than Python?**

# Answer
The compilation process is a process of taking code from language "A" and translating it to code from language "B".

---

Lets start by saying that python doesn't compile at all - it stays python code all of the time.

On the other hand, $C$ compiles into assembly, which then turns into a standalone executable.

Since python stays python, this means that to run python code, you will need a special program - an interpreter. This interpreter reads the python code line-by-line, and executes it. But $C$ compiles into assembly, which is natural for the computer and can be executed without requiring help from other programs.

While creating an interpreter is usually simpler, a compiler is a much better option - here are a few advantages:

* Compiled code doesn't need to rely on external programs to run code
* The compiler can catch some errors even before the program is executed, while this is not possible when using an interpreter
* A compiler is capable of introducing optimizations into the compiled code, so that it will run faster (nowadays, its *significantly* faster!)

---

All of that being said, even though python is an interpreted language, it doesn't make it a bad one. The core concept of python is being simple, easy to learn and use, and still powerful - and python achieves those well.

---

## Important note

In this answer I was talking about the most basic versions and usages of python and $C$. Yes, you can create a compiler for any language, even python. And yes, python already isn't a "fully" interpreted language - there are some compilation steps that are done. But it is still considered an interpreted language since there really isn't a native compiler that translates it into machine code (assembly)
> 1 votes

---
Tags: python
---


# Question
Title: How to join two Scapegoat Trees in O(log n) time?
I am working on some binary-search-tree research and was surprised to find no mention of an algorithm to join two Scapegoat Trees. This is where two trees $L$ and $R$ are joined to create a single tree $T$, given that all values in $L$ are less than all values in $R$ and that all values are unique.

For this problem, the maximum height of a tree is $2\times\lfloor{\log\_2(n)\rfloor}+1$ where $n$ is the total number of nodes in the tree and height is the number of nodes along the longest path (maximum depth + 1).

I have tried some ideas but none have passed the height invariant checks so far. Does anyone know of a resource that explores this idea, or can provide a reasonable approach for this problem? You can assume that every node is annotated with its size to make things easier.

Can this be done in $O(log(n))$ without exceeding the height bound?

One approach might be to use a simple BST join (remove max of $L$ or min of $R$ to be the root) and have the balance restored over the next few insertions, but that means the height upper-bound is not always guaranteed, especially after multiple joins.

# Answer
> 1 votes
What I remember of more formal/theoretical discussion of (somewhat "basic") trees does not keep extra information about a whole tree beyond the regular information in the root node.
Seeing scapegoat trees keeping the size, anyway, and using a balance limit on trees rather than on nodes, I mused about keeping height, too. (Neither helping *split*…)

I figured the most simple idea you rejected was finding the rightmost node $rL \in L$ and the leftmost node $lR \in R$ (neither of which needs to be a leaf) and "rotating" the deeper to become the common root.
Guess: The height of the joint tree is one larger than the max. height of $L$, $R$ more likely than not.
And repeated joins keep increasing height.

If you knew the heights, the root of the higher (lighter to break ties) would be the joint root, with the "inner" child replaced by a join with the other tree by the previously sketched method.
Problems:
• analysis promises to be a PITA
• no(?) way to know the new height - you could keep upper (and lower) limits
much the same way scapegoat trees keep max\_size to provide for deletions

---

I'm afraid that at the end of the day, you are joining
\- one of the original trees (the shape of which you do know something about) with
\- a tree you know *nothing* about

One viable heuristic might be

* set *estimated size* to the size of the bigger tree,
*candidate* to its root
* while *estimated size* is bigger than the size of the smaller tree
and *candidate* has a child closer to the gap,
• set *candidate* to that child
• halve *estimated size*
* now, make *candidate* a child of the node closest to the gap in the smaller tree
and put the root thereof in the place *candidate* was in

---
Tags: algorithms, data-structures, binary-trees, balanced-search-trees, binary-search-trees
---


title: Give an O(n^2) algorithm to solve

text:
# Question
Title: Give an O(n^2) algorithm to solve
This is my homework question

Given an array A\[1..n\] of n integers, we want to decide if there exist i and j, where 1 ≤ i , j ≤ n, such that A\[i\] + A\[j\] = α for a given value α.

Give an O(n^2) algorithm to solve the problem.

Can anyone understand what the question like to ask?

# Answer
> 1 votes
This problem is called **two-sum** you should return indices of the two numbers such that they add up to the **target**.

let's say you have an array called `nums = [2,7,11,15]` and the `target = 9`, you should find two indices of two numbers in this example will be

```
num[0] + num[1] => 2+7 = 9 which is the target

```

There are two different approaches to solve it, first by **brute force** and the time complexity will be o(n ^ 2)

```
var twoSum = function(nums, target) {
    for (let i = 0; i < nums.length; i++) {
        for (let j = i + 1; j < nums.length; j++) {
            if (nums[i] + nums[j] == target) {
                return [i, j]
            }
        }
    }
};

```

and the second approach by using **Hash-table** and the time complexity will be o(n) and it's absolutely better

```
var twoSum = function(nums, target) {
    const indices = new Map();

    for (let index = 0; index < nums.length; index++) {
        const complement = target - nums[index];

        if (indices.has(complement)) {
            return [indices.get(complement), index]
        }

        indices.set(nums[index], index)
    }
};

```

**Note:** This solution by using JS language you can write it with any language, just you should understand the problem and the idea of solution and you'll be able to write it with any language you want.

---
Tags: data-structures, asymptotics, arrays
---


# Question
Title: Determines the smallest set of unit-length closed intervals that contains all of the given points
**Question**: Describe an efficient algorithm that, given a set $\\{x1, \cdots, x\_n\\}$ of points on the real line, determines the smallest set of unit-length closed intervals that contains all of the given points.

**Attempt**: If we sort the points in any order we would like to start with, we will get $S=\\{y\_1, \cdots, y\_n\\}$. Next, we pick the smallest each time from $S$ and build a **UNIT** internal around it, so we have $S-\\{smallest(S)\\}$ left and the unit interval would be $\[y\_i, y\_{i+1}\]$. Keep following this approach would guarantee we cover the whole real line.

**Complexity**: apply any sorting algorithm to sort points in non-decreasing order. Then take smallest point and build unit interval, so we have $O(n\log{n})$.

**Problem**: I am not really sure what is the goal behind the question? The mail goal is basically to build unit intervals all across the line? If yes for what purpose (application) please?

**Edit**: I made a mistake as it should be $\[y\_i, y\_{i}+1\]$.

# Answer
> 1 votes
To answer your question:

> *I am not really sure what is the goal behind the question?*

If I were to give this assignment to my students, I would expect

1. An algorithm in pseudo code
2. Running time analysis
3. Proof of correctness

You have given neither.

It is always risky to handwave an algorithm, because you always cherry-pick data structures and details when you analyse it, and the running time you end up with might not actually be realizable.

So: How do you traverse the points, what is the running time, and why is it correct?

---

On the second question, why do we want to cover points with unit intervals, the answer is two-fold:

1. It is a constructed formal problem designed to make you think about algorithms, as a means to practice algorithmic problem-solving more than solving real-world problems. When we do exercises in computer science, these are often "idealized/platonic" versions of problems that are much simpler than real-world problem, simply because real-world problems are messy and contain a lot of noise.
2. One example of a real-world problem could be: there are a bunch of houses along a road, and you want to place mailboxes so that the maximum distance from each house to a mailbox is $\delta$. How many mailboxes must you place and where? Feel free to replace "mailbox" with "fire station", "hospital", "school", etc.
3. A more general real-world instance could be that you have points in the plane, and want to cover all the points with as few radio antennas as possible. Each antenna covers a circle with radius $\delta$. This is a more difficult problem to solve, of course, but when learning a new field, one starts simple and builds on that.

---
Tags: algorithms, greedy-algorithms
---


# Question
Title: What is the minimum pumping lemma length of $01^*0^*1$?
I've taken the following steps to prove that the minimum pumping length (PL) of the above language, $L= 01^\*0^\*1$:

1. Set a PL. I chose $p=2$
2. Choose a string from $L$ where $|w|\geq p$, I chose $w=011$. $|w|=3 \geq p=2$
3. Split the word, $w$ into constituent parts, $x,y,z$ such that the following are true:

* $y\neq\varepsilon$
* $|xy|\leq p$
* For any $k \geq0$, $xy^kz\in L$

4. So I chose:

* $x=0$, $y=1$, $z=1$
* $y=1\neq\varepsilon$
* $|xy|=2\leq p=2$
* $xy^kz=01^k1 \in L$

My lecturer however has said that the minimum pumping length is $3$, and I don't understand why, and cannot ask him. Am I right, or have I misunderstood something?

# Answer
> 1 votes
Given a language $L$, its *pumping length* is the minimum $p$ for which the following holds:

> Every word $w \in L$ of length at least $p$ can be decomposed as $w = xyz$ such that $|xy| \leq p$, $y \neq \epsilon$, and $xy^iz \in L$ for all $i$.

Showing that a *particular* word can be pumped isn't enough — you have to show that *all* words in the language of length at least $p$ can be pumped, and moreover in such a way that $|xy| \leq p$.

The pumping length cannot be $2$ since the word $01 \in L$ cannot be pumped down, that is, there is no decomposition $w = xyz$ with $y \neq \epsilon$ and $xy^0z \in L$.

# Answer
> 1 votes
Another way to look at it: "Pumping length p" means that if you take a state machine, then any word w in the language with a length ≥ p must have re-entered the same state after at processing at most p characters of the input.

That's not true with p = 2; 01 is in the language but doesn't require re-entering the same state within the first two characters.

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


# Question
Title: Disambiguating Big-O and Theta for Expressing Time Complexity
Can someone please give me an example of two algorithms, one where "Big-O" is the most appropriate expression of how time complexity grows with input size, and one where this would be Θ?

Can you please be very clear about whether the statements refer to best, average or worst case, and about implicit assumptions about the input or anything else, beyond the fact that the general approach is to consider how the number of basic operations in a hypothetical machine grows with input size.

# Answer
> 1 votes
Lets start by explaining the difference between big-O and $\Theta$. Basically, if we think of big-O as "bounding from above", we can think of $\Theta$ as "bounding both from below and from above". Formally, $f=\Theta(g)\iff f=O(g)\land f=\Omega(g)$. This $f=\Omega(g)$ means that $g$ bounds $f$ *from below*, and is equivalent to saying that $g=O(f)$ ($g$ bounds $f$ from below if $f$ bounds $g$ from above).

So basically, $f=O(g)$ means that $f$ is asymptomatically at most like $g$, but $f=\Theta(g)$ means that $f$ is asymptomatically equivalent to $g$.

In the context of algorithms, the notions are a bit abused. For example, one may write "this algorithm works in $O(n)$", when he/she really meant "this algorithm runs in $\Theta(n)$".

Most of the times, this doesn't make a big difference. But sometimes, especially with algorithms that are hard to analyze - this distinction is important. Since those algorithms are hard to analyze, its perfectly possible that the proven run-time bounds are not tight, which means they are **not** $\Theta$ but are just $O$.

On the other hand, when someone explicitly writes $\Theta$, it probably means either one of two things (depending on the context, check it carefully!):

1. The algorithm's proven bound for the run-time is tight
2. This algorithm was proven to achieve a run-time equal to the known lower bound pf the problem. For example, with sorting - there is a nice proof that no comparison-based algorithm can sort in less than $n\log(n)$ time - this is a lower bound. Now, mergesort runs in $O(n\log(n))$, and hence it is optimal since it achieves the lower bound. So one may say that mergesort works in $\Theta(n\log(n))$.

# Answer
> 0 votes
Asymptotic notation arose in number theory, and is now commonly used in combinatorics. It has nothing to do with algorithms per se. We use asymptotic notation to describe the resource consumption of algorithms, mainly time and space. It comes in five main flavors:

* $f(n) = O(g(n))$ if $f(n) \leq Cg(n)$ for some constant $C\>0$. In words, $f(n)$ grows at most as fast as $g(n)$.
* $f(n) = \Omega(g(n))$ if $f(n) \geq cg(n)$ for some constant $c\>0$. In words, $f(n)$ grows at least as fast as $g(n)$.
* $f(n) = \Theta(g(n))$ if $cg(n) \leq f(n) \leq Cg(n)$ for some constants $C,c\>0$. In words, $f(n)$ and $g(n)$ grow at the same rate.
* $f(n) = o(g(n))$ if $\lim\_{n\to\infty} f(n)/g(n) = 0$. In words, $f(n)$ grows slower than $g(n)$.
* $f(n) = \omega(g(n))$ if $\lim\_{n\to\infty} f(n)/g(n) = \infty$. In words, $f(n)$ grows faster than $g(n)$.

---

When we say that an algorithm runs in time $O(f(n))$, we mean that its running time is bounded by $Cf(n)$, for some constant $C \> 0$. Often there is an unstated assumption that the bound is tight, that is, the function $f(n)$ cannot be replaced by any asymptotically smaller function. However, strictly speaking, this is not the meaning of $O(f(n))$. For example, quicksort runs in time $O(n!)$. This is a pretty bad bound, but the statement is mathematically valid nonetheless.

What do we mean when we say that an algorithm runs in time $\Theta(f(n))$? Strictly speaking, this means that the running time of the algorithm is always between $cf(n)$ and $Cf(n)$, for some constants $C,c\>0$. However, sometimes this kind of bound is too much to hope for, since the running time could depend on the particular input, or if the algorithm is randomized, on the random coin tosses. For example, quicksort always runs in $O(n^2)$, but sometimes it runs in $O(n\log n)$. We can say that its *worst-case* complexity is $\Theta(n^2)$, but it is not true that its runtime is $\Theta(n^2)$.

---

When should you use which notation? That's up to you. If you can bound the quantity in question tightly, then you might as well use big Theta. If all you have is an upper bound, you should use big O. If you know the worst-case complexity but want to describe the "every-case" complexity, the convention is to use big O, with the tacit understanding that the bound is probably tight for the worst case.

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


# Question
Title: Algorithm to find the saddle point in a Binary tree
How to find a saddle point in a binary tree. where saddle point is a node in a tree whose value = min(the node and all its ancestors) = max ( the node and all its descendants)

# Answer
Here is a sketch.

Given a node $u$, let $p\_u,\ell\_u,r\_u,v\_u$ denote its parent, it's left children, it's right children, and the value stored in $u$, respectively. Let $m(u)$ denote the minimum among all the values stored in the ancestors of $u$ ($u$ is an ancestor of itself). Let $M(u)$ denote the maximum among all the values stored in all the descendants of $u$ ($u$ is a descendant of itself).

Notice that $m(u) = \min\\{v\_u, m(p\_u)\\}$ and that $M(u)=\max\\{ v\_u, M(\ell\_u), M(r\_u) \\}$ and hence all values $m(\cdot)$ can be computed in linear time by a preorder visit, while all values $M(\cdot)$ can be computed in linear time by postorder visit.

Once you know $m(u)$ and $M(u)$ for a node $u$, you can check whether $u$ is a saddle. This should be more than enough to get you started. You can fill in the other details by yourself.
> 0 votes

---
Tags: algorithms, binary-trees
---


# Question
Title: prove that 2 collection have the same VC-dimensions
I'm new here on the site, I'm a final year student in computer science. In a machine learning course, there was a question on a test that I could not understand.

The question goes like this:

> Suppose that $ F\subseteq\\{0,1\\}^\Omega $ is some collection of Boolean functions over $\Omega $.
>
> Define $\Omega'=\Omega\times\\{0,1\\}$ and define $F'$ to be the collection of Boolean functions over $\Omega$ as follows:
>
> for every $f\in F$, there is some $f'\in F'$ that maps $(x,y)\in\Omega'$ to $1\[f(x)\neq y\]$.
> (Furthermore, $F'$ consists only of such $f'$; no other functions are allowed.)
>
> Prove that the VC-dimensions of $F$ and $F'$ are equal.

What I was able to understand is that there is a collection of some functions $F$, and that all these functions with the addition of $0$ and $1$ are also in $F '$

I think $F '$is like $F$ only if an addition of $0$ and $1$ to the functions.

Can't figure out how to prove it.

# Answer
> 1 votes
Every $f \in F$ is mapped to $f' \in F'$ defined as follows: $f'|\_{\Omega \times \\{0\\}} = f$ and $f'|\_{\Omega \times \\{1\\}} = 1 - f$.

Let us call a subset of $\Omega'$ *mixed* if it contains both $(\omega,0)$ and $(\omega,1)$ for some $\omega \in \Omega$.

For $S' \subseteq \Omega'$, let $S'|\_{\Omega} = \\{ \omega \in \Omega : (\omega,0) \in S' \text{ or } (\omega,1) \in S' \\}$.

For all $S \subseteq \Omega$, the set $S' = S \times \\{0\\}$ is not mixed and satisfies $S'|\_{\Omega} = S$.

The proof is a combination of two simple observations:

1. $F'$ doesn't shatter any mixed set.
2. If $S'$ is not mixed then $F'$ shatters $S'$ iff $F$ shatters $S'|\_{\Omega}$.

---
Tags: machine-learning, vc-dimension
---


title: Splitting a binary tree into two halves

text:
# Question
Title: Splitting a binary tree into two halves
I am looking to prove the following:

> Each binary tree with $n \ge 2$ nodes has an edge whose removal results in two trees, each having at most $\lceil (2n-1)/3 \rceil$ nodes.

I am not sure how to approach this, or find some way to detect such an edge. Would appreciate any hints.

# Answer
> 3 votes
Root the binary tree at an arbitrary node. Starting at the root, go down the tree, always choosing the node whose subtree is larger, until reaching a node $v$ whose subtree contains at most $\lceil (2n-1)/3 \rceil$ nodes. Remove the edge between the node and its parent.

By construction, the subtree rooted at the parent of $v$ contains $m \> \lceil (2n-1)/3 \rceil$ nodes. Since when going down we always choose the node whose subtree is larger, this means that the subtree rooted at $v$ contains at least $(m-1)/2$ nodes, and so the rest of the tree contains at most this many nodes: $$ n - \frac{m-1}{2} \leq n - 1 -\frac{\lceil (2n-1)/3 \rceil}{2}. $$ The right-hand side ought to be bounded by $\lceil (2n-1)/3 \rceil$.

---
Tags: algorithms, binary-trees
---


# Question
Title: Show that {xy : x,y ∈ {a,b}*, |x| = |y|, x ≠ y} is a not a regular language
Actually, I know that there are many examples showing how this is a contex-free language, but I can't find any that show it isn't regular. I would appreciate if I could have a solution step by step for this case Show that **{xy : x,y ∈ {a,b}\*, |x| = |y|, x ≠ y}** is not a regular language

# Answer
You need to use the concept of pumping lemma.

1. Define a pumping length, $p$
2. Choose a word, $w\in L $ such that $ |w|\geq p$
3. Split $w$ into three constituent parts, $x,y,z$ such that $y\neq\varepsilon$ (but $x$ and $z$ are allowed to $=\varepsilon$), $|xy|\leq p$, and $xy^kz$ is in your language $L$ for any $k \geq0$.
4. Let's leave $p$ undefined as $p$ for this, and take the word $a^p b^p$ which satisfies the rules of the language
5. $|w|=2p\geq p$ therefore the condition in step 2 is met
6. Now we split up $w$. With the rules defined, $y$, the important bit, must be in the first $p$ characters of $w$, meaning that it must be made up entirely of $a$'s, so let's take $x=a$, $y = a^{p-1}$, $z=b^p$ (but it doesn't matter whether $y$ is $a^1$, or $a^p$, and $x=\varepsilon$ or $x=a^{p-1}$, the outcome is the same).
7. Now for the important part - if we pump the string such that $xy^0z$, we get $a(a^{p-1})^0b^p=ab^p$ which you'll observe is $\notin L$.
8. In fact, whatever we use as $k$ to pump $y$, we'll always end up with a scenario where $|x|\neq|y|$, and this would be the same whatever string you used from your language.
> 0 votes

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


# Question
Title: Algorithm that finds a matrix with a specific number of 1s in its rows & columns
**Question:**

Given integer $n \geq 2$ and two lists of size $n$, $A$ and $B$, of non-negative integers, determine if there exists an $n \times n$ matrix whose $i$-th row has $A\[i\]$ $1$s and whose $j$-th column has $B\[j\]$ $1$s. If it does exist, then find it.

---

**My attempt:**

An extremely inefficient algorithm would be to find all possible matrices of size $n \times n$ and check each one. But I'm hoping to find a faster algorithm to do this task? My other thought was to set all the rows randomly such that the condition is satisfed along the rows. And then, starting from $j$ such that $B\[j\]$ is largest, start swapping elements around along a row to satisfy the column conditions (while keeping the row condition in-tact). However, I have no idea if this actually works, and how I would prove it works if it did.

Please do not give me any explicit solutions or code, but a hint in the right direction would be appreciated. Thank you!

# Answer
> 3 votes
This problem is not easy. The popular website GeeksforGeeks gives an answer that returns the wrong answer, "YES" when row sums are $ \[3, 3, 3, 1\]$ and column sums are $\[4, 4, 1, 1\]$.

---

How can we find a set of necessary and sufficient conditions that is easy to compute? How can we produce a wanted matrix if the conditions are satisfied?

One easy condition is that the sum of row sums must be equal to the sum of column sums, since both of them are equal to the total number of $1$s in the binary matrix.

However, that condition is not enough. For example, there is no binary matrix with row sums $\[2,0\]$ and column sums $\[2,0\]$. Why? Because a row sum of $2$ means every column of that row is $1$. So, every column sum must be at least $1$.

---

Let us check a much easier problem: given a lists of size $n$ non-negative integers $A$, determine if there exists a $n\times n$ matrix such that the $i$-th row has $A\[i\]$ $1$s. We can see immediately that if and only if each $A\[i\]$ is between $0$ and $n$ inclusive, there is such an matrix.

---

A useful property of row sums of a matrix is that if indices are ignored, all row sums as a collection do not change if we switch any two rows or any two columns. The same holds for the column sums. In other words, whether there exists an $n×n$ matrix with given row sums and column sums does not depend on the order of the row sums or the order of column sums. This observation suggests that we may sort the row sums as well as the column sums.

WLOG, let us fix a sequence of valid non-decreasing row sums. The problem now is to find the sequences of all valid non-decreasing column sums. There are a few venues to experiment and contemplate.

* How big or small can the biggest column sum be?
* How big or small can the smallest column sum be?
* Can we reduce the size $n$ by one if the biggest column sum is fixed?
* Can we combine two columns together?
* Compute all binary matrices with given row sums for some small $n$. List the columns sums. Are there any pattern?
* What happens to the first negative example in this answer?

Here is the last and most interesting hint. There is a nice $O(n\log n)$ characterization of the valid sums and a nice algorithm to produce a wanted matrix when the sums are valid.

---

Some hints above may not turn out to be very helpful. Hopefully, these hints can motivate you to continue searching for the right answer.

Be prepared that the right answer might be hard to find even though it could be considered simple. It is reasonable to imagine that I could not figure out an answer in a few minutes or in a few hours or even many months had I been given this problem as well as the hints above when I was a senior student.

Good luck!

---

# Answer
> 2 votes
This problem is equivalent to the bipartite b-matching problem on complete bipartite graphs, where you get a complete bipartite graph $G = (V, E)$ as input and an integral function $b : V \rightarrow \mathbb{N}$ that assigns an integer to each vertex. The goal is to find a subset of the edges $S \subseteq E$ such that $S \cap \delta(v) = b(v)$ for all $v\in V$, where $\delta(v)$ are the edges incident to $v$ in $G$.

The reduction is straight-forward (in both directions). The rows of the matrix correspond to one side of a complete bipartite graph and the columns to the other side.

This problem -similar to bipartite matching- can be easily reduced to the maximum-flow problem by adding a global source and connecting it to one side of the bipartite graph and a global sink and connecting it to the other side.

It is not hard to see the correctness of all previous reductions (the first one in both direction).

---
Tags: algorithms, greedy-algorithms, matrices
---


# Question
Title: Oblivious Universal Turing Machine in O(T log(T)) time
I'm currently reading Computational Complexity: A Modern Approach. In this book, they give a proof of a universal Turing machine $U$ such that if $M(x)$ runs in $T$ steps, then $U(\lfloor M \rfloor, x)$ runs in $CT \log T$ steps where $C$ depends **only** on $M$'s alphabet size, number of tapes, and number of states. I'll describe $U$ loosely here:

> It has an input tape, output tape, tape for $M$'s states and transition functions, tape for $M$'s current state, and one work tape. We say $M$ has $k$ work tapes and an alphabet of $\Gamma$.
>
> $U$ uses an alphabet of $\Gamma^k$ to put the letters of all $k$ tapes on one cell and has a clever way of imitating the left and right shifts of different heads.
>
> Since we only have $T$ steps, we only need to go from $-T$ to $T$. We'll say $L\_i$ goes from $2^i$ to $2^{i+1}-1$ and $R\_i$ goes from $-2^{i+1}+1$ to $-2^i$. This goes from $i=0$ to $i=\log T+1$. For any $i$, $L\_i$ and $R\_i$ is full of blank symbols, half-blank half-filled, or completely filled. Furthermore, the total number of blank symbols in both $L\_i$ and $R\_i$ at one time is $2^i$, meaning half of all of the cells are blank while the other half is information.
>
> To left shift, find the smallest $i$ so $R\_i$ is not empty and thus $L\_i$ is not full. Put the leftmost non-blank symbol in position $0$ (i.e. under the head in $M$) and move the other $2^{i-1}-1$ non-blank symbols into the empty $R\_0,R\_1,...R\_{i-1}$. This leaves all of those zones half-empty.
>
> Push the $2^{i-1}$ leftmost non-blank symbols in $L\_{i-1},...,L\_1$ into $L\_i$ and then reorganize the other non-blank symbols to make $L\_{i-1},...,L\_1$ all half-full.
>
> Right shifts look similarly, except switch the roles of the left and right zones.

I want to solve the following exercise:

> Define a TM $M$ to be oblivious if its head movement does not depend on the input but only on the input length. That is, M is oblivious if for every input $x \in \\{0, 1\\}^∗$ and $i \in N$, the location of each of $M$’s heads at step $i$ of execution on input $x$ is only a function of $\lvert x \rvert$ and $i$. Show that for any time-constructible $T : \Bbb{N} \rightarrow \Bbb{N}$, if $L \in \mathbf{DTIME}(T(n))$, then there is an oblivious TM that decides $L$ in $O(T(n)\log T(n))$ time.
>
> **Hint:** Show that $U$ can be tweaked to be oblivious.

Now, my question is, under such a machine, while maintaining $CT\log T$ time, how do we make $U$ oblivious? I see how putting the input down initially and the left/right shifts are simply functions of $\lvert x \rvert$, but when we decide to left/right shift each tape has to decide on $x$ since we're not given that $T$ is oblivious, so **how do we time the left and right shifts of $U$ so that they only depend on $\lvert x \rvert$ and not on the actual content of $x$**?

# Answer
A concrete construction of such a UTM, from which one can construct oblivious and efficient TMs, is given in this lecture note https://courses.cs.washington.edu/courses/cse531/16wi/lectures/lect01.pdf.

A crucial idea in the construction is rearranging $L\_{i+2}$ and $R\_{i+2}$ EVERY $2^i$ steps. The invariant ($L\_i$ and $R\_i$ are empty, half-full or full) does not hold every steps in this construction. However, we can see that it holds when the rearrangement occurs.
> 2 votes

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


title: Same instances for different problems

text:
# Question
Title: Same instances for different problems
According to the formal definition of an instance, it is a set of input data containing the values of the parameters of some problem (What is an instance of NP complete problem?).

So, two problems may formally have the same class of instances, as long as they share the same parameters, even though they might have, e.g., different objective functions?

# Answer
> 0 votes
Yes, two problems can be unrelated but have the same set of instances.

For example: given a graph $G$ you can consider the problems of computing a global minimum cut of $G$, computing a vertex cover of $G$, computing a dominating set of $G$, computing a maximum clique in $G$, computing a maximum independent set of $G$, computing the chromatic number of $G$, determining is $G$ is $2$-edge connected, determining whether $G$ is chordal, determining whether $G$ is triangle-free, etc...

---
Tags: optimization, theory, definitions
---


# Question
Title: Number of subsequence's with same values of bitwise and, or and xor
GeeksForGeeks

> We are given an array arr of $n$ element. We need to count number of non-empty subsequences such that these individual subsequences have same values of bitwise AND, OR and XOR. For example, we need to count a subsequence (x, y, z) if (x | y | z) is equal to (x & y & z) and (x ^ y ^ z). For a single element subsequence, we consider the element itself as result of XOR, AND and OR. Therefore all single element subsequences are always counted as part of result.

The editorial for the above problem states:

1. If there are $n$ occurrences of zeroes in the given array, then will be $2^{n} - 1$ subsequences contributed by these zeroes.
2. If there are $n$ occurrences of a non-zero element $x$, then there will be $2^{n-1}$ subsequences contributed by occurrences of this element. **Please note that, in case of non-zero elements, only odd number of occurrences can cause same results for bitwise operators.**

I am not able to understand the proof for the statement **Please note that, in case of non-zero elements, only odd number of occurrences can cause same results for bitwise operators.**

Can anyone help me understanding why this works?

# Answer
x & y & z == x | y | z if either all three of x, y and z are 1 or if all three are 0. The same obviously for 1, 2, 4, 5, 6 etc. numbers.

If all items are zero, then x ^ y ^ z is also zero, so you include all subsequences made of all zero.

If all items are one, then the xor of an even number of 1's is zero, and the xor of an odd number of 1's is 1. It matches the logical "and" or "or" if and only if the number of items is odd. So you include all subsequences made of an odd number of 1s.
> 0 votes

---
Tags: algorithms, subsequences, bit-manipulation
---


title: Size of minimal DFA

text:
# Question
Title: Size of minimal DFA
Assume a given NFA for a regular language with $n$ states. It is clear that determinizing it may result in an DFA with $\Omega(2^n)$ states. However, the minimization might decrease the number of states. Is there a counterexample which would show that the minimized version might aswell be of superpolynomial size? I.e. is the following true?

For every NFA with $n$ states, its (unique) minimal DFA has $O(\operatorname{poly}(n))$ states? If not, what is the counterexample? Here $\operatorname{poly}(n)$ is a polynomial in $n$.

# Answer
If you consider the language over $\Sigma = \\{a, b\\}$ defined by the set of words that contain a $a$ in the $n$-th position before the end, or formally: $$L\_n = \\{uav\mid u,v\in \Sigma^\*, |v| = n-1\\}$$

Then $L\_n$ is recognized by a NFA with $n+1$ states (quite simple to find), but the minimal DFA has $2^n$ states.

To prove that, suppose that there is a DFA $A = (Q, \delta, q\_0, F)$ such that $L(A) = L\_n$. Consider $u,v\in \Sigma^n, u\neq v$ two words of length $n$. Consider $w$ their longest common suffix. Without loss of generality, $u = u'aw$ and $v = v'bw$, with $u', v'\in \Sigma^\*$, and $w\in \Sigma^k$ (with $k\<n$).

Now, note that $ua^{n-1-k}\in L$ but $va^{n-1-k}\notin L$. That means that $\delta(q\_0, u)\neq \delta(q\_0, v)$ (otherwise $\delta(q\_0, va^{n-1-k}) = \delta(q\_0, ua^{n-1-k})\in F$)

What we proved is that two words in $\Sigma^n$ lead to two differents states when read from $q\_0$. That means that $|Q| \geq |\Sigma^n| = 2^n$.
> 4 votes

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


# Question
Title: Rearranging strings so that the Hamming distance between them is 1
This is a question from CodeFights.com:

> Given an array of equal-length strings, check if it is possible to rearrange the strings in such a way that after the rearrangement the strings at consecutive positions would differ by exactly one character.
>
> Example
>
> * For `inputArray = ["aba", "bbb", "bab"]`, the output should be `stringsRearrangement(inputArray) = false`; All rearrangements don't satisfy the description condition. *(sic)*
> * For `inputArray = ["ab", "bb", "aa"]`, the output should be `stringsRearrangement(inputArray) = true`. Strings can be rearranged in the following way: `"aa", "ab", "bb"`.

I found an exponential-time algorithm, but is there a polynomial-time algorithm? Is this problem NP-complete?

I know that a closely related problem, the Hamming Salesman Problem (HTSP), is NP-complete, and this problem is certainly reducible to HTSP, but I don't know if HTSP is reducible to this one.

# Answer
> 4 votes
Grid graphs are finite node-induced graphs of the infinite planar grid (whose vertices are integral points, and two vertices are linked when their Euclidean distance is 1). A. Itai, C. H. Papadimitriou, and J. L. Szwarcfiter proved that the Hamiltonian path problem on grid graphs is NP-complete.

To reduce that to your problem, suppose the grid graph has $m$ rows and $n$ columns. The $i$-th row is labeled with the string $a^ib^{m-i}$, and the $j$-th column is labeled with the string $a^jb^{n-j}$. Then a vertex corresponds to the concatenation of the two labels of its row and column. Now it is easy to show the unit disk graph under Hamming distance over all these concatenated strings is exactly the same as the original grid graph.

# Answer
> 0 votes
I am the someone who suggested the (apparently, now, failing algorithm). Here is a "reference implementation" in Python:

```
def consecutive(str1, str2): # are two strings consecutive?
    if str1 == str2:
        return False  # identical strings are not consecutive
    for i, L in enumerate(str1):
        if L == str2[i]:  #compare strings one char at a time
            continue
        else:  # if the chars aren't the same
            str2 = list(str2)
            str2[i] = L           # swap the letter of str2 with
            str2 = "".join(str2)  # one from str2, and compare
            return str1 == str2   # if now strs are the same
    return True                   # they are consecutive

def stringsRearrangement(inputArray):

    ordered = [inputArray[0]]
    left = inputArray[1:]

    previous_left = len(left) + 1 # sets the first iteration
                                  # of while loop to true

    while previous_left > len(left):  # less items than last iteration
        previous_left = len(left)
        for i,string in enumerate(left): # iter through left
            if consecutive(ordered[-1], string): # try to move item
                ordered.append(left.pop(i))      # from left to ordered
                break
            elif consecutive(ordered[0], string):
                ordered.insert(0, left.pop(i))
                break

    while left:                   # if still items in left
        previous_left = len(left) # to check if left is decreasing
        for i,string in enumerate(ordered): #iter thru ordered
            if consecutive(string, left[0]): #to find something in left
                try:                         # that can be inserted
                    if consecutive(left[0], ordered[i+1]):
                        ordered.insert(i+1, left.pop(0))
                        break
                except IndexError:  #if
                    ordered.append(left.pop(0))
        if previous_left == len(left): #if nothing found
            break
    return not (bool(left)) # true if left is empty

```

I'm not sure how one would *prove* that it always works -- but I also cannot find a failing input.

-- EDIT

> Could you explain your code with actual text or give the pseudocode?

added comments, let me know if that is enough

# Answer
> 0 votes
By giving each string an ID, For example: \['abc':0, 'bef':1, 'bcc':2, 'bec':3, 'bbc':4, 'bdc':5\]

Capture the hamming distance of 0/1 for all qualified string pairs. Now you have \[\[0, 4\], \[1, 3\], \[2, 3\], \[2, 4\], \[2, 5\], \[3, 4\], \[3, 5\], \[4, 5\]\]

where a map such as this can be produced from it: {0: \[4\], 1: \[3\], 2: \[3, 4, 5\], 3: \[1, 2, 4, 5\], 4: \[0, 2, 3, 5\], 5: \[2, 3, 4\]}

This is nothing but a representation of a graph, where as NP-complete part that you iterate through each starting point to exhaustically find one possible path that visit every node once and only once. In this case:

\[0, 4, 2, 5, 3, 1\] can be one solution

I assume there are some heuristic can be used to shorten search time. In this case, node 0 and 1 only have one connection each. They have to be the starting/ending points, for example. And for those who have 2 connections, ... etc. It doesn't have to be brute-forced.

---
Tags: np-complete, traveling-salesman, hamiltonian-path, hamming-code
---


# Question
Title: Is the running time of an algorithm that has O(n^2) where n = 10^5 equal to one that has O(1000000n) where n = 10^ 5?
Hello my question is that if i have two for loops inside each other like this:

```
for(int i = 0 ; i < 100000; i++){
   for(int j = 0; j < n ; j++){
     \\-------------}
 }

```

and another one like this:

```
for(int i = 0 ; i < n ; i++){
   for(int j = 0 ; j < n ; j++){
      \\-------------}
      }

```

where n can have any value from 1 to 100000.

Are these two equivalent regarding worst case running time?

# Answer
Check your definition of $O(\cdot)$. You'll see that $O(10^{20} n)$ is just $O(n)$, and that $2^n \ne O(n)$.

You are interested in comparing algorithms for *all* "sufficiently large" input sizes $n$, not one particular value of $n$. For sufficiently large values of $n$, $2^n \> c n$, however large the constant $c$ may be
> 1 votes

# Answer
The Big O notation is about the *limiting* behavior, thus it describes an upper bound of a function when the argument tends to a particular value or infinity.

In your case you have a fixed $n$, thus an upper bound of a number of operations for both loops is the same, namely $100000^2$, thus your algorithm is $O(1)$, consequently, both loops are equivalent in a worst case.

And here is the catch, you can measure the running time of various algorithms, think about $O(n)$, $O(n^2)$, $...$ $O(n^k)$, $...$, $O(nlog(n))$, bla-bla... but once you said *'Hey, my N is equal to K'* you immediately got an $O(1)$ running time for literally *any* algorithm. For sure, for that fixed $N$ the running time can take billions of years, but it's now *limited* by some value you know upfront.

In conclusion, in your question you were effectively talking about $O(1)$, thus you have equivalent running time for both cases.
> 1 votes

# Answer
1. Big-O is an upper bound. $\log n = O(n^2)$, for example, so the answer is “no idea”.
2. If you used $\Theta$ then you know that for large n f(n) is between some bounds. You don’t know how large n will have to be, so we know nothing at all for $n = 10^5$.
3. For large n, f(n) is between $c\_1 \cdot n^2$ and $c\_2 \cdot n^2$. We don’t know how large $c\_1$ and $c\_2$ are. So we still don’t know which one is smaller.

You would need an *estimate* for the execution time, say $5.3n^2$ microseconds vs $123,765n$ microseconds. That’s something you can compare. With $n=10^5$ it's 53,000 seconds vs. 12,376.5 seconds.
> 0 votes

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


# Question
Title: Finding the homomorphism between two homomorphic graphs: what is the name of this problem?
The "graph homomorphism problem" can be stated as: given two graphs $G$ and $H$, determine if there exists a homomorphism $f$ such that $f: G \rightarrow H$. This is a famous problem that is well-known to be NP-complete.

Now I'm thinking about a related problem: given two homomorphic graphs $G$ and $H$, find $f: G \rightarrow H$. Does this problem have a name? Is its complexity class known?

# Answer
There are a couple of cases that we can dispose of straight away.

A *self-edge* on some vertex $v$ is an edge $v \rightarrow v$. If $H$ has even one vertex with a self-edge, then it's trivial to construct a homomorphism which maps all vertices to that vertex and all edges to that edge.

Similarly, if $H$ doesn't have a single vertex with a self-edge but $G$ has, no homomorphism exists.

Finally, we can deal with the case where $G$ has no self-edges. Then $G$ must be a *chromatic* graph: for some $k$, the vertices of $G$ can be assigned $k$ colours such that the start and end of each edge do not share the same colour.

Denote the complete graph with $k$ vertices by $K\_k$.

Exercise: Show that a homomorphism $f : G \rightarrow K\_k$ describes a $k$-colouring of $G$. Conversely, show that every $k$-colouring of $G$ can be represented as a homomorphism $f : G \rightarrow K\_k$.

So any solution to your problem is also a solution to the $k$-colouring problem.

The decision problem of testing a mapping to see if it is a graph homomorphism is trivially in P. It follows that your problem is FNP-complete.
> 1 votes

---
Tags: complexity-theory, graphs
---


title: N points with maximum sum distance

text:
# Question
Title: N points with maximum sum distance
Given a distance matrix for 50,000 points, how do I select $N$ points so that the sum of all distances between the $N$ points is maximized? $N$ could be as high as 100.

To calculate the sum of distances for all sets of $N$ points would be exponential, which would not scale to 50,000 points.

What is the fastest algorithm that you would know? And also, does this problem have a name? If so, I could do more reading about it.

Thanks very much for your feedback.

# Answer
Your problem is known as the maximum diversity problem.
> 1 votes

---
Tags: algorithms, graphs, runtime-analysis, computational-geometry, matrices
---


title: What is an O(n)-approximation?

text:
# Question
Title: What is an O(n)-approximation?
I see the following notations used:

* $O(1)$-approximation
* $O(n)$-approximation
* $\Omega(n)$-approximation

Can someone please explain what they mean?

I know what an approximation is with a normal constant approximation (2-approx, 2/3-approx, etc). And I know what $O(n)$, $\Omega(n)$ mean, but I just don't understand what they mean exactly in this context.

**The way I understand it:** With $O(n)$, $\Omega(n)$ the approximation gets worse when the size of the input increases, $\Omega(n)$ is a lower bound (the approx is at least an $n$-approx) and $O(n)$ is a maximum bound, the approximation does not get worse than $n$-approx (so if n=100, and we have an algorithm that is a $\Omega(n)$-approximation then we have a 100-approx? the approximation algorithm will give an answer that is 100 times worse than OPT or worse?).

With $O(1)$ it is constant (a constant factor but we just don't care what the constant is, it's just bounded by some fixed $C$). But I am not sure my interpretation is correct.

# Answer
> 1 votes
A minimization problem has the following generic form.

For each instance $\mathcal{I}$ there is a set $F\_{\mathcal{I}}$ of feasible solutions and an objective function $\phi\_{\mathcal{I}}\colon F\_{\mathcal{I}} \to \mathbb{R}\_+$. The goal is to find a feasible solution which minimizes the value of the objective function.

Often instances also comes with a natural size function (sometimes several). We denote the size of an instance $\mathcal{I}$ by $|\mathcal{I}|$.

A (deterministic) approximation algorithm for a minimization problem gets as input an instance $\mathcal{I}$ and outputs a feasible solution $A(\mathcal{I}) \in F\_{\mathcal{I}}$ (sometimes we allow an approximation algorithm to relax the feasibility constraints — such an algorithm is known as a *bicriteria* approximation algorithm). The algorithm has approximation ratio $\rho(n)$, or that it is a $\rho(n)$-approximation (just different terminology), if for all $\mathcal{I}$, $$ \phi\_{\mathcal{I}}(A(\mathcal{I})) \leq \rho(|\mathcal{I}|) \min\_{x \in F\_{\mathcal{I}}} \phi\_{\mathcal{I}}(x). $$ In words, the approximation algorithm is guaranteed to returns a solution which is within a multiplicative factor of $\rho(n)$ of the optimal solution, where $n$ is the size of the instance. (Sometimes this definition is relaxed by also allowing a small additional additive error.)

For a randomized approximation algorithm, we require this guarantee to hold in expectation, with constant probability, or with high probability — different algorithms will have different guarantees.

Maximization problems are handled similarly, the guarantee becoming $$ \phi\_{\mathcal{I}}(A(\mathcal{I})) \geq \rho(|\mathcal{I}|)^{-1} \max\_{x \in F\_{\mathcal{I}}} \phi\_{\mathcal{I}}(x). $$

A specific feasible solution $y \in F\_{\mathcal{I}}$ is a $\rho$-approximation if $$\phi\_{\mathcal{I}}(y) \leq \rho \min\_{x \in F\_{\mathcal{I}}} \phi\_{\mathcal{I}}(x). $$

---

When we say that an algorithm has an approximation ratio of $O(n)$, we mean that it has an approximation ratio of $\rho(n)$ for some function $\rho(n) = O(n)$. Alternatively, for every instance of size $n$ it gives a solution which is within an $O(n)$ factor of the optimum.

As usual with big O notation, if an algorithm is an $O(n)$-approximation, this doesn't preclude it being an $O(1)$-approximation: the promised approximation ratio is just an *upper bound* on the actual performance of the algorithm.

When we say that an algorithm has an approximation ratio of $\Omega(n)$, we mean that any function $\rho(n)$ for which it the algorithm has an approximation ratio of $\rho(n)$ satisfies $\rho(n) = \Omega(n)$. This means that there is a sequence of instances $y\_n$ whose size tends to infinity on which the solutions produced by the algorithm have an objective value which is an $\Omega(n)$ factor more than the optimum.

---
Tags: algorithms, complexity-theory, algorithm-analysis, approximation
---


# Question
Title: Why is a regex search less efficient than a normal search?
On a lot of messaging applications, regex search isn't enabled due to a "linear scan". I'm not sure why this is the case. Can someone explain?

# Answer
"Linear scan" probably means the search can't backtrack. This guarantuees an O(n) complexity for the search. With backtracking it's possibly to get cases of exponential complexity. You might notice that that's not actually a problem for regular languages, since deciding regular languages doesn't need backtracking. Why then would regex search not be enabled due to wanting a "linear scan" of the chat history?

The issue is that many regular expression libraries actually don't just allow regular languages. For example, the standard regular expression library in Java uses backtracking to allow stuff like backreferences:

https://docs.oracle.com/javase/8/docs/api/index.html?java/util/regex/Pattern.html

> Capturing groups are so named because, during a match, each subsequence of the input sequence that matches such a group is saved. The captured subsequence may be used later in the expression, via a back reference, and may also be retrieved from the matcher once the match operation is complete.

The docs don't explicitely say this, but this is only possible because the matcher can backtrack.

So, I would take the informed assumption that regex search is disabled because a linear search is wanted, but the regex library used actually does more.

Note: There are regex libraries that do a linear scan. They don't allow backreference and lookaround but most other features still work. See

> Java's standard regular expression package, java.util.regex, and many other widely used regular expression packages such as PCRE, Perl and Python use a backtracking implementation strategy: when a pattern presents two alternatives such as a|b, the engine will try to match subpattern a first, and if that yields no match, it will reset the input stream and try to match b instead.
>
> If such choices are deeply nested, this strategy requires an exponential number of passes over the input data before it can detect whether the input matches. If the input is large, it is easy to construct a pattern whose running time would exceed the lifetime of the universe. This creates a security risk when accepting regular expression patterns from untrusted sources, such as users of a web application.
>
> In contrast, the RE2 algorithm explores all matches simultaneously in a single pass over the input data by using a nondeterministic finite automaton.
>
> There are certain features of PCRE or Perl regular expressions that cannot be implemented in linear time, for example, backreferences, but the vast majority of regular expressions patterns in practice avoid such features.

> RE2 was designed and implemented with an explicit goal of being able to handle regular expressions from untrusted users without risk. One of its primary guarantees is that the match time is linear in the length of the input string.\[...\]
>
> It is also not a goal to implement all of the features offered by Perl, PCRE and other engines. As a matter of principle, RE2 does not support constructs for which only backtracking solutions are known to exist. Thus, backreferences and look-around assertions are not supported.
> 1 votes

---
Tags: algorithms, search
---


# Question
Title: Heuristics for a variant of the traveling salesman problem
I am looking at a variant of TSP in which rather than visiting every node, there is a given collection of (possibly overlapping) subset, and the salesman must pass through one node from each subset.

Concretely, I have a graph with vertices $V$ and a family of subsets $S = \\{S\_1, S\_2, ..., S\_n \\}$. I'm looking for a simple path $\\{(v\_1, v\_2), (v\_2, v\_3), ..., (v\_{m}, v\_{1})\\}$ such that for all $S\_i$, there is a $k$ such that $v\_k \in S\_i$.

I'm interested in approximation algorithms, and heuristics for computing lower bounds for partial solutions for use in a branch and bound computation. Has this problem been studied elsewhere? If it helps, the problem is metric and the graph is complete.

# Answer
The problem is known as the Generalized TSP problem.
> 1 votes

---
Tags: reference-request, heuristics, traveling-salesman
---


# Question
Title: Intuitive proof that all planar graphs are disk contact graphs
Planar graphs are graphs which can be drawn on the plane without edges crossing.

Disk contact graphs are graphs obtained as follows. Place some disks in the plane without overlaps, allowing touching. Create a vertex per disk, and connect vertices by an edge if the corresponding disks touch.

As stated by graph classes, planar graphs and disk contact graphs are equivalent. What I understand from this equivalence is that the two sets contain the same graphs. It is easy to see that any disk contact graph is planar, however I am having trouble understanding how every planar graph is also a disk contact graph.

Is there an intuitive proof? I explicitly ask for an intuitive proof since the link cites a survey paper, which itself cites multiple sources for proofs, although these papers are either impossible to find due to ultimately not being published (or being too old for search engines?) or require some expertise in specific fields which I unfortunately do not have.

# Answer
> 1 votes
This is known as the circle packing theorem, and attributed to Koebe. Asaf Nachmias wrote a short note with a complete proof.

For more on circle packings, check out a survey by Rohde on Oded Schramm's related work.

---
Tags: correctness-proof, planar-graphs
---


# Question
Title: Find if it's possible to partition a set into 3 disjoint sets each with same sum
**Question**: I came a cross a problem where we have a set of numbers $W= \\{x\_1, \cdots, x\_n\\}$ where repetition of numbers is allowed. We would like to find out whether we can find out 3 **disoint** sets where the sum of numbers in each set is equal, e.g., $W=\\{1,5,2,4,3,3\\}$ can be split into 3 disjoint sets $(1,5), (2,4), (3,3)$ each with same sum that is $6$.

**Base condition**: So we can clearly see that the base condition for this problem to hold is $\frac W3$ is divisible otherwise it won't be solvable.

**Approach 1**: why we need dynamic programming? Because finding all permutations of a set would be $2^n$ and find their sums would take $2^n$, which is enough to tell this is a exponential time algorithm.

**Approach 2**: Let us formulate the problem with dynamic programming. First we start by building a table to fill up from subproblems (sets whose sum is to be found). The dimension of the table is $(\frac W3 + 1)(\frac W3 + 1)(n+1)$. For example, taking again $W=\\{1,5,2,4,3,3\\}$ can be split into 3 disjoint sets $(1,5), (2,4), (3,3)$, we can see that $W$ would be the sum we get from the disjoint groups, which is supposed to be the same for all 3. So the table $M$ would be of size $(3+1)\times(3+1)\times(7+1) = 4\times4\times8$. Then:

* Define $M\[x,y,k\] = 1$ iiff there are two disjoint subsets $I,J \subset \\{1, \cdots, k\\}$ such that their summation is equal, that is $\Sigma\_{i \in I} a\_i = x$ and $\Sigma\_{j \in J} a\_j = y$.
* **Base case** $k=0$, $M\[0,0,0\] = 1$ and $M\[x,y,0\] = 0$ for $x+y\>0$.
* **Recursive step**: $M\[x,y,k\] = M\[x-a\_k, y, k-1\] \lor M\[x, y-a\_k, k-1\] \lor M\[x, y, k-1\]$, for $k=1,\cdots, n$.
* So, the solution will be at index $\[\frac W3, \frac W3, n\]$. Each index $M$ will select one of 3 ways to place a number $a\_k$ in one of 3 disjoint sets $ M\[x-a\_k, y, k-1\], M\[x, y-a\_k, k-1\], M\[x, y, k-1\]$.

**Problem 1**: As I understand, we need to find 3 disjoint groups their sum is equal. So we build table whose rows and columns are simply from $0$ to last index $sum$ as $\frac W3$ will return one of the sums from the 3 groups as if all groups are equal, then their sum is $3 \times sum$, so dividing by 3 would give $sum$ which is the last index of the table $M$. So I am not sure why it's build in this way please given that we are looking for 3 groups disjoint having same sum. The recusrive step though is reasonable but still have problems undertsantind $x$ and $y$ which could be any number from $1$ to $sum$ in $M$.

**Problem 2**: as I understand from $M\[x-a\_k, y, k-1\], M\[x, y-a\_k, k-1\], M\[x, y, k-1\]$. Let us take 3rd group $M\[x, y, k-1\]$, it will loop over sum and then check upon removing an item from $x$, which we defined as sum from $x = Sum\_{\\{1, \cdots, k\\}}$, and we store at $M\[x, y, 0\]$, for $k=0$. So how do you interpret the recursive operation as you see it based on description please?

# Answer
I did not understand your question properly. But, I think you are asking for how the following identity holds: $M\[x,y,k\] = M\[x-a\_k, y, k-1\] \lor M\[x, y-a\_k, k-1\] \lor M\[x, y, k-1\]$

We want to check if there are two disjoint subsets $I,J \subset \\{1, \cdots, k\\}$ such that $\Sigma\_{i \in I} a\_i = x$ and $\Sigma\_{j \in J} a\_j = y$. There are three possibilities for $M\[x,y,k\]$ to be true:

1. The element $a\_{k}$ belongs to $I$.
2. The element $a\_{k}$ belongs to $J$.
3. The element $a\_{k}$ neither belongs to $I$ or $J$. It means it belongs to the third set.

For the first possibility, observe that $M\[x,y,k\] = 1$ only if $M\[x-a\_{k}\]\[y\]\[k-1\] = 1$.

For the second possibility, observe that $M\[x,y,k\] = 1$ only if $M\[x\]\[y-a\_{k}\]\[k-1\] = 1$.

For the third possibility, observe that $M\[x,y,k\] = 1$ only if $M\[x\]\[y\]\[k-1\] = 1$.

It implies that $M\[x,y,k\] = 1$ if and only if $M\[x-a\_k, y, k-1\] \lor M\[x, y-a\_k, k-1\] \lor M\[x, y, k-1\] = 1$.

Suppose you have computed all the entries of the form $M\[.\]\[.\]\[k-1\]$. Then, using the above identity you can compute all the entries of the form $M\[.\]\[.\]\[k\]$, and so on.

For this, you require to initially fill up the table for $k = 0$. All the entries of the form $M\[.\]\[.\]\[0\]$ are $0$ except $M\[0\]\[0\]\[0\]$ since without using any element from the array you can not create a non-zero sum $x$ or $y$.

Let me know, if it answers your question.
> 1 votes

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


# Question
Title: If L is regular so is the language of compressed doubles
Suppose L is a regular language over the alphabet $\Sigma$. I need to prove that

$$ L'=\\{x\_0\cdots x\_n:x\_0x\_0x\_1x\_1\cdots x\_nx\_n\in L, \ \ x\_i\in \Sigma\\}$$

I thought I could take a DFA which computes L, and take each accepting state, together with the state before it along an edge labeled 0, and the state before that along an edge labeled 0, and make an edge that skips over the middle state. Then do likewise with edges labeled 1.

If you either cut out the middle state or if you leave it and regard the result as an NFA, I can't seem to show that the resulting automaton to computes L'.

# Answer
When you want to prove your construction correct you have to be precise in your construction. The new automaton has the same states, and the same initial and final states as the original one. Then, as you suggest, for every pair of consecutive edges with the same label in the original automaton, the new automaton will have one edge with that label from the first state to the third one. We cannot delete the middle state, as what is a middle state in one pair of edges might be begin or end state in another.

The proof of correctness is now a simple observation on the construction. There is a path $(q\_0,a\_1,q\_1)(q\_1,a\_2,q\_2)\dots(q\_{n-1},a\_n,q\_n)$ in the new automaton if and only if there is a 'duplicated path' $(q\_0,a\_1,p\_1)(p\_1,a\_1,q\_1)(q\_1,a\_2,p\_2)(p\_2,a\_2,q\_2)\dots(q\_{n-1},a\_n,p\_n)(p\_n,a\_n,q\_n)$ in the original one. For the corresponding languages it is now sufficient to consider 'accepting' paths with initial state $q\_0$ and accepting state $q\_n$.
> 1 votes

# Answer
Let $h\colon \Sigma \to \Sigma^\*$ be the homomorphism given by $h(\sigma) = \sigma\sigma$. Then $L’ = h^{-1}(L)$. Now use the well-known fact that regular languages are closed under inverse homomorphism.

Equivalently, start with a DFA for $L$, and modify the transition function so that whenever the new DFA reads a symbol $\sigma$, it simulates the old DFA reading two $\sigma$’s in a row.
> 2 votes

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


# Question
Title: Do Adjacency Lists from Binary Trees go both ways?
From my reading and research it appears it's one way, however my lecturer states that it goes both ways in his examples.

Let me show you what i mean by this.

He claims that a binary tree built from a heap with numbers 1 - 7 appears as:

1-\>2-\>3

2-\>1-\>4-\>5

3-\>1-\>6-\>7

4-\>2

5-\>2

6-\>3

7-\>3

Whereas i would say it appears as:

1-\>2-\>3

2-\>4-\>5

3-\>6-\>7

4

5

6

7

Because the tree is moving in one direction, down from the root.

Are both ways valid? Is this the difference between a directed and undirected rendition maybe? Or is there one set way?

# Answer
> 0 votes
There are different 'families' of trees, and sometimes the borderline is slightly unclear.

In graph theory a tree usually is an undirected (simple) graph that is connected and has no cycles. There is no natural direction in the graph.

Additionally one might declare one of the nodes to be the root. Then, like you observe, this automatically induces a direction of the edges away from the root. Now it is a matter of taste. Is it still an undirected graph (a 'rooted tree') or is the structure directed (a 'directed tree').

Even in diagrams of trees this might be unclear. Usually one draws the root at the top and the leaves near the bottom. But even when the edges are undirected lines, the tree might be considered top-to-bottom directed.

I sympathise with your view, but of course I am not your lecturer.

---
Tags: graphs, binary-trees, adjacency-matrix
---


# Question
Title: PDA with multiple element access - $i$ - access PDA
We define an $i$ \- access PDA as a PDA that can manipulate the top $i$ characters in the stack, where $i\>0$.

Given a transition function of the form $\delta(p,x,c,d) \to (q,c')$, where $d \le i, d \> 0$, we read it as "When in state $p$, upon reading an input $x$, the stack has depth at least $d$, with $c$ at the $d$th position from the top. Transition to $q$, pop $c$, and add $c'$ at the same index as $c$.

In essence, a $1$ \- access PDA is essentially a normal PDA.

How do I show that for any language accepted by an $i$ \- access PDA, $\exists$ a normal PDA which accepts it as well?

I know that I have to show that in the end, any $i$ \- access PDAs can be reduced down to a $1$ \- access PDA. But I am not sure how to go about it.

# Answer
**Hint:** replace every $d$-depth transition with a set of states and transitions that will read out $d-1$ elements, then read the last element and do the transition, and afterwards return the last $d-1$ elements back to the stack.

**Another hint:** to "remember" the $d-1$ elements, construct a unique "path" for each unique combination of the $d-1$ elements. Then, you can reconstruct the stack by knowing exactly which path you took.

**Note:** this construction works in $3$ "phases":

* reading the first $d-1$ elements of the stack
* doing the actual transition
* returning the stack to its original way Make sure you understand how to do each of those and how they combine with each other!
> 3 votes

# Answer
One of the possibilities is to keep the topmost $i$ symbols of the stack in the finite memory rather than putting it on the stack.

Any simple symbol replacement of the topmost symbols can be performed in memory, rather than on the stack. If we push or pop symbols from/to the stack we also push or pop from the (shorthened) stack, shifting symbols from/to the finite memory.
> 1 votes

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


title: Proof of a logical theorem

text:
# Question
Title: Proof of a logical theorem
> Prove that if for every proposition $\psi\left(p\_{0}, \ldots, p\_{n}, p\right)$ there exists $\phi\left(p\_{0}, \ldots, p\_{n}\right)$ in which $\psi\left(p\_{0}, \ldots, p\_{n}, p\right) \rightarrow\left(\phi\left(p\_{0}, \ldots, p\_{n}\right) \leftrightarrow p\right)$ is a tautology then $\phi$ is a definition of $p$ in terms of $\psi$ then $\left(\psi\left(p\_{0}, \ldots, p\_{n} , p\right) \wedge \psi\left(p\_{0}, \ldots, p\_{n}, q\right)\right) \rightarrow(p \leftrightarrow q)$ is a tautology. $p\_{0}, \ldots, p\_{n}, p , q$ are atoms.

I looked it up in two logic books A Mathematical Introduction to Logic and Logic and Structure but couldn't find this theorem. I'm new to logical proofs and I don't know where to begin in proving this theorem. Is there anyone who can name some books that contain this theorem? If not please explain how this logical proof works.

# Answer
Let me explain what is going on here by way of an example: $$ \psi(p\_0,p\_1,p) = p \leftrightarrow (p\_0 \land p\_1). $$ That is, $\psi(p\_0,p\_1,p)$ is true iff $p = p\_0 \land p\_1$.

If you define $$ \phi(p\_0,p\_1) = p\_0 \land p\_1, $$ then we indeed have $$ \psi(p\_0,p\_1,p) \to (\phi(p\_0,p\_1) \leftrightarrow p), $$ which means that if $\psi(p\_0,p\_1,p)$ holds then $p = \phi(p\_0,p\_1)$.

Clearly, in this case, if both $\psi(p\_0,p\_1,p)$ and $\psi(p\_0,p\_1,q)$ hold then $p = q$, since both are equal to $\phi(p\_0,p\_1)$.

---

Now for the formal proof. We assume that $$ \tag{$\ast$} \psi(p\_0,\ldots,p\_n,p) \to (\phi(p\_0,\ldots,p\_n) \leftrightarrow p), $$ and want to conclude $$ (\psi(p\_0,\ldots,p\_n,p) \land \psi(p\_0,\ldots,p\_n,q)) \to (p \leftrightarrow q). $$

Assume, therefore, that $\psi(p\_0,\ldots,p\_n,p)$ and $\psi(p\_0,\ldots,p\_n,q)$ both hold. Assumption ($\ast$) implies that $$ p \leftrightarrow \phi(p\_0,\ldots,p\_n) \leftrightarrow q, $$ and so $p \leftrightarrow q$.
> 3 votes

# Answer
This problem sounds quite abstract and I'll sketch a proof below. To prove the final material conditional is a tautology, we only need to prove $\psi(p\_0, \ldots p\_n, p) \wedge \psi(p\_0, \ldots p\_n, q) \land \lnot (p \leftrightarrow q)$ is unsatisfiable, which means it can never be the case that $p,q$ can have opposite truth values while both $\psi(p\_0, \ldots p\_n, p)$ and $\psi(p\_0, \ldots p\_n, q)$ are true. In general cases this obviouly could be satisfied, for example in the case of a disjunctive normal form, $\psi(p\_0, \ldots p\_n, p)=p\_0 \lor \ldots \lor p\_n \lor p$.

However, we have the given assumption $\psi(p\_0, \ldots p\_n, p) \rightarrow (\phi(p\_0, \ldots p\_n) \leftrightarrow p)$ as a tautology, this obviously blocks the previous case as $\phi$ now must be truth-functionally dependent on $p$, for example, if $\psi=p\_0 \land \ldots \land p\_n \land \lnot p$, then we can have $\phi=\lnot (p\_0 \land \ldots \land p\_n)$. This given tautology (premise) thus ensures us that $\phi$ can be thought of as a logically equivalent definition of $p$ in terms of $\psi$ and therefore $p$ must be logically equivalent to $\phi(p\_0, \ldots p\_n)$ alone (nothing else), as a result it can never be the case that $p,q$ can have opposite truth values while both $\psi(p\_0, \ldots p\_n, p)$ and $\psi(p\_0, \ldots p\_n, q)$ are true.
> 0 votes

---
Tags: logic, propositional-logic
---


# Question
Title: Language and Decidability Problems for Turing Machines
Below are the two problems Im working on and my attempt at a solution (understanding the question). My first question is am I interpreting the question from the symbols right, second can you help explain what I need to do for these questions? Ive been reading through chapter 4 of Sipser 3rd ed. Intro to theory of computation and I haven't been able to make much sense the questions. Any help is appreciated.

1. Show that the following languages are partially decidable:

(a) ETx = {\<M, x\> | M(x) ↓ and at the end of computation the tape of M is empty}

ETx is a universal TM M with input x that terminates and at the end of computation the tape of M is empty. Not sure where to go from (restating the question...)

(b) ETE = {\< M \> | (∃x)(M(x) ↓ and at the end of computation the tape of M is empty)}

ETE is a universal TM M where there exists some input such that input X terminates M and at the end of the computation the tape of M is empty...

---

2. Show that the language ETx is not decidable. (Hint: Describe how a decision procedure for ETx could be used to decide the universal language Lu.)

Not sure where to begin with this one

---

# Answer
> 0 votes
Let's start with the first question. One can recursively enumerate triples $\langle M, x, t \rangle$ and print $\langle M,x\rangle $ or $M$ (depending on whether we consider the first or the second language) in case $M$ halts on input $x$ within $t$ steps and the tape is empty when $M$ halts.

For the second question we can reduce halting problem to the language a) by mapping a Turing machine $M$ to a pair $\langle M', M\rangle$, where $M'$ is defined as the Turing machine which runs the Turing machine $M$ (whose encoding it receves as its input) and which clears the computation tape if $M$ halts. Clearly $M$ halts on empty input iff $\langle M', M\rangle$ belongs to the language a).

---
Tags: turing-machines
---


# Question
Title: Prove the class of regular languages is closed or not closed under the operations below
Suppose $A$ and $B$ are both languages over $\Sigma=\\{0,1\\}$. We use $n\_0(x)$ and $n\_1(x)$ to represent the number of $0$s and $1$s in the string $x$ respectively. Consider the following two operations: $$ A\cong\_0 B=\\{x\in A\mid\exists y\in B,\ \text{s.t. }n\_0(x)=n\_0(y)\\}\\ A\cong\_{01} B=\\{x\in A\mid\exists y\in B,\ \text{s.t. }n\_0(x)=n\_0(y)\wedge n\_1(x)=n\_1(y)\\} $$ How to prove that the class of regular languages is closed under $\cong\_0$ operation and not closed under $\cong\_{01}$ operation?

# Answer
> 1 votes
For $A\cong\_0 B$, consider $\mathcal{A}\_A$ and $\mathcal{A}\_B$ two automata that recognize $A$ and $B$ respectively. Construct $\mathcal{A}'\_B$ where you replace $1$-transitions in $\mathcal{A}\_B$ with $\varepsilon$-transitions and add a $1$-transition loop on each state. Now, the product automaton between $\mathcal{A}\_A$ and $\mathcal{A}'\_B$ should recognize $A\cong\_0 B$.

For $A\cong\_{01}B$, consider $A = a^\*b^\*$ and $B = (ab)^\*$. Both are regular languages, however, $A\cong\_{01}B = \\{a^nb^n\mid n\in \mathbb{N}\\}$ which is a well known non-regular language.

---
Tags: regular-languages, automata, finite-automata, closure-properties
---


# Question
Title: Best algorithm to find "deepest" interval
Let's say I have a list of intervals on a number line. The "depth" of a point on this number line corresponds to the number of intervals in the list that contain it \[the point\].

So for instance if I have the intervals `[(1, 8), (3, 12), (4,6)]`, the deepest points comprise the interval `(4, 6)`.

What is the fastest algorithm to find a point of max depth (just one is fine)?

# Answer
> 8 votes
Here's an n log n algorithm:

1. Convert the intervals into a sorted collection of start and end events. O(n log n)
2. Initialize a depth value and deepest value to zero, and iterate the collection in sorted order. O(n)
3. When you encounter a start event, increment your depth value.

* If it's greater than the deepest you've seen, update your deepest and save the current value along the number line as your candidate point (or the start of a candidate interval)

When you encounter an end event, decrement your depth value.

* If you were tracking a candidate interval, and the current depth is less than the deepest depth when you're done processing all intervals that start/end here, then this is the end of your candidate interval.

Return the last (deepest) candidate point or interval you found.

(I've elided a little complexity for handling open versus closed intervals, but both can be accommodated with an appropriate tie-breaker rule for coincident start/end events.)

(You can improve the constants by having two collections, a collection of starts and a collection of ends, walking through them together. But that doesn't change the asymptotic analysis.)

---

I looked at a divide and conquer algorithm too, but it had the same O(n log n) and fussier case handling for merging the results for each half, so ordered traversal might be the neatest way if it's feasible for your data set.

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


# Question
Title: what is the time complexity of this for for for if
I need to know the analysis of time complexity of this case?

```
  for k=1:(N-1)
for i=1:N-1
    for j=1:N
        if (Groups22(i,j)==Groups2(k,I)& AA(i,j)==AA(k,I)& BB(i,j)==BB(k,I))
            Groups22(i,j)=nan;
        end

```

# Answer
First, let's try to analyze this together, how? Take every line/instruction of the code and check its complexity.

**Simple example:**

```
Let tableA=[0,1,...9]
For i=0 to i=n
 tableA[i]=0;

```

Depending on the computation model (Random access machine, Turing machine with tape, etc), but we usually consider that tableA\[i\]=0 is an operation that accesses a position of the array in constant time. Why constant? Simply because it does not depend on the size of the table. So we say it's $O(1)$

Generally, all if, ==, =\>, \<=, assignement, array access, etc are all considered constant time operations.

Now let's take the loop, what does the loop (valid for and while loops) do? it repeats the instruction within the loop body n times. We can see that depending on the size of the tableA, the loop may take longer to complete. So we say it's $O(n)$ multiplied by the complexity of the operations within the loop, so $O(n) \times O(1) = O(n \times 1) = O(n)$

**Now in your case:**

We have some comparison operations, all of these happen in constant time since it's direct access to the array and simple equality test, the operation does not depend on the size of the array, so this operation is $O(1)$. This $O(1)$ operation is performed in for loop, `for j=1:N` so it's performed n times. Just like the previous example I gave, We now multiply $O(1\times n) =O(n)$.

How many times to we repeat this inner for loop? we repeat it with for `i=1:N-1`so that's $O(n-1)$ in the complexity notation, the -1 (or a +1, or $\pm$ any constant) does not matter as they belong to the same complexity class. So we simply consider it $O(n)$. We repeat the following part that is $O(n)$: `for j=1:N if (....)...;` n times, so we have $O(n \times n) = O(n^2)$

Finally, repeat the same reasoning for the last outer loop `for k=1:(N-1)` and we arrive $O(n^3)$

**Please note that these are NOT formal definitions of asymptotic complexity notation** there are good answers here on CS SE on how to formally define them (you should look at these) or you can look for some lecture notes on the topic.
> 1 votes

---
Tags: time-complexity
---


# Question
Title: can similarity transformation be linear transformation?
Learning Computer Graphics -

Can similarity transformation be linear transformation?

Similarity T is a rigid transformation (translation and rotations) with uniform scaling. so I guess a similarity transformation can be linear. Am I missing someting?

Thank you

# Answer
> 2 votes
Linear transformations fulfill two criteria:

```
T(A) + T(B) = T(A + B)

```

and

```
k T(A) = T(k A)  (for any scalar k)

```

What happens if A is zero?

```
 T(0) + T(B) = T(0 + B)
 T(0) + T(B) = T(B)
 T(0) = 0

 k T(0) = T(k 0)
 k T(0) = T(0)
 (k - 1) T(0) = 0
 T(0) = 0   (since k can be any scalar, not limited to k = 1)

```

So, a linear transformation must transform zero to zero.

In two or more dimensions, that means transforming the origin (0, 0) or (0, 0, 0) etc. to itself.

This means that a linear transformation *cannot* include translation. A triangle joining points (0, 0), (1, 0), and (0, 1) can't be linearly transformed to the similar triangle spanning (1, 0), (2, 0), (1, 1), because that would require mapping the origin to a different point, which linear transformations can never do.

A transformation that can include a linear transformation *and* a shift in the origin is called an affine transformation.

So: some similarity transforms are *not* linear.

---

In game development, we work around this by bumping up a dimension. So if it's a 3D game, we work with 4D vectors and 4x4 matrices. We set the 4th, w, component to 1 for all positions, so the whole game world sits on the 3-dimensional w=1 hyperplane within the 4D space. We can then use a matrix as a linear transformation to shear this hyperplane around in the x, y, and z dimensions - including the origin of our 3D game world at (0, 0, 0, 1), even though the "real" origin of the containing 4D space at (0, 0, 0, 0) never moves.

---

To cover our bases, we should probably also attack this from the opposite direction: not all linear transformations are similarity transformations either.

To see this, take the linear transformation that scales the y axis by 2 but leaves the x axis as-is. This obeys the two criteria above, but changes angles and the ratios of lengths of non-parallel line segments, so it's not a similarity transformation.

---

So:

* *Some* similarity transformations are linear (those involving *only* rotation, uniform scale, and mirroring, but no translation)
* *Some* linear transformations are similar (those involving *only* rotation, uniform scale, and mirroring, but no non-uniform scale or shear)

But in general, similarity transformations are not the same as linear transformations.

---
Tags: linear-algebra, space-analysis, computer-graphics
---


# Question
Title: How do I know which direction I should rotate a node in an AVL Tree?
I'm studying AVL Trees in my programming class and we got this exercise dealing with right, left, left-right and right-left rotations as a way to check if we understand the theoretical concept of AVL Trees. We're given the numbers $100,50,25,10,37,32,200$. Creating an AVL Tree until $37$ wasn't that difficult but then I got stuck at balancing out the tree when I insert $32$. The following is my method:

Now I know that there is a conflict at $52$ but since it has 3 nodes (LRL), I don't understand how I should rotate. I think, I should get $37$ as the root node $25$ as it's left child and $52$ as it's right child but I dunno.

# Answer
> I think, I should get 37 as the root node 25 as it's left child and 52 as it's right child but I dunno.

You plan is correct.

What you need to do is a left-right rotation as shown in the third column of the table below. That is, a left rotation at node 25 followed by a right rotation at 52. It is symmetric to the right-left rotation as shown in the fourth column and as explained in Wikipedia.
> 1 votes

# Answer
Before you insert a node, you already know the insertion is forbidden. You can rotate 52 before you insert a new node, because the insertion direction is otherwise wrong (52 has the red light 1). You can check and rotate all the nodes before you insert a new node such that all roads are as clear as possible (all green lights).

This generally means that after two insertions, the global height may increase (amorphous flip-flopping); in other words, every 2 insertion may trigger the extra height compression subroutine; such subroutines are very costly and can be the real main cost (hidden cost).

The flip-flop sequence obeys a very simple horizonal nonlinear wave equation with probablistic short pebble-rain+ripples. The height growth is like a simple dirac delta.
> 0 votes

# Answer
1st step : Left-Left rotation. 2nd & 3rd step :Left-Right Rotation. 4th step: Right-Right Rotation. 5th is Final AVL tree.

https://www.tutorialspoint.com/data\_structures\_algorithms/avl\_tree\_algorithm.htm
> -1 votes

---
Tags: algorithms, data-structures, search-trees, balanced-search-trees, avl-trees
---


# Question
Title: Embedding from $L^\infty$ space to $L^2$ space
I have a set $X$ of $n$ points in a $poly(n)$-dimensional $L^\infty$ space. Does there exist a way to map the points into $poly(n)$-dimensional $L^2$ space so that the distances between points in $X$ are approximately preserved?

Formally, let $S\_1$ be the original $L^\infty$ space with $dim(S\_1) = O(n^k)$ ($k$ is known and fixed), let $X$ be a subset of $S\_1$ with $|X|=n$, and let $\epsilon \in (0,1)$ be some fixed number. Does there exist an $L^2$ space $S\_2$ with $dim(S\_2) = poly(n)$ and $\phi\colon S\_1 \to S\_2$ such that $\\|\phi(x) - \phi(y)\\|\_2 = (1 \pm \epsilon) \\|x-y\\|\_\infty$ for all $x,y \in X$?

# Answer
> 3 votes
The answer is unfortunately negative in general, by combining the following two well-known facts:

* Every metric space on $n$ points embeds isometrically into $(n-1)$-dimensional $L^\infty$.
* Embedding the metric of an $n$-vertex expander into $L\_2$ requires distortion $\Omega(\log n)$.

---
Tags: approximation, euclidean-distance
---