# Question
Title: Is this a correct description of Dijkstra's algorithm
I am on a journey understanding Dijkstra's algorithm.

My familiarity with mathematical terms is not great, so I have put the algorithm into my own English. I understand this is not ideal, but this is part of my learning process.

What are the major areas of misunderstanding in the description below?

---

We maintain a list `D` of all the tentatively known shortest distances to nodes.

Each item in `D` comprises a node name, a shortest (yet known) distance and a "via" node, indicating the node the path arrives via.

ie. `[{ node, tentativeDistance, via }, ...]`

We start with a list `G` of all the nodes in the graph.

ie. `[{ name, edges }, ...]`

We use `G` to keep track of the nodes we have visited. Each time we visit a node we remove it from `G`. In this way we never visit a node more than once.

We pull a node `N` from `G`. At the start we pull the start node with cumulative distance of zero.

If this is the start node we add it to `D`.

We calculate the cumulative distance to it, given the node we have arrived via. At the start we arrive via itself.

eg. if we arrived at node `C` via node `B`, we know that the shortest path to `B` is, say, `2` because we *must* have previously explored other options to arrive at `B`; if the cost of the edge from `B` to `C` is `1` the cumulative distance is `2 + 1 = 3`.

We then review the unfollowed edges from every node that we have visited already (in `D`). This is akin to choosing which part of the advancing "wavefront" to advance from.

For each of the unfollowed edges if the cumulative distance to the destination node is shorter than any previously recorded distance for that node in `D` (or we do not yet have a distance for it) then we replace (or add) the entry for the node in `D`, together with the "via" value (the current node). In this way we build up a list of best-known distances to nodes.

We pick the new destination node with the shortest cumulative distance.

Again: in this way, we can be confident that when we arrive at a node, we have found the shortest path to it.

When we arrive at the destination node, or when we have visited all the nodes we stop, otherwise we repeat the edge-reviewing process described above.

# Answer
> 2 votes
Not bad. May I suggest a few improvements?

* Distinguish between the algorithm (what you do) and the argument (the proof of why it works).
* Your `D`, which you say is a list, is better thought of as a map/associative-array from `Node` to `[distance, Node]`, where the former `Node` is the predecessor of the latter.
* Start the computation with `{start-node -> [0, nil]}` in `D`.
* Define the graph `G` as a mapping `Node -> Set of [distance, Node]`, where the `distance` is the edge length from the former to the latter node. This makes the iterative step easier to describe precisely.

---

The point of Dijkstra's algorithm is that the tentative distances turn out to be final. The way to prove this is to show that - given that it is true of `D` so far - it is true at the next step too. This is called the *inductive hypothesis*. Given that it is true of the initial `D`, which it is, it is true of all the `D`s thereafter, including the final one.

---
Tags: shortest-path
---


title: Solving 2-CNF TQBF with #SAT solver?

text:
# Question
Title: Solving 2-CNF TQBF with #SAT solver?
We clearly know that 2-QCNF is in $\mathsf{P}$. Since that, if I understand it right, it is possible to solve it with #SAT solver (because $\mathsf{P} \subseteq \mathsf{\\#P}$). But how can we only knowing amount of positive assignments for some non-quantified formulae solve 2-QCNF? And why this doesn't hold (at least, assumed so) for general case of TQBF?

# Answer
First of all, it is a bit misleading to say that $\mathsf{P} \subseteq \mathsf{\\#P}$, since $\mathsf{P}$ is a class of decision problems, while $\mathsf{\\#P}$ is a class of counting problems. However, we can think of a decision problem as a counting problem in which the answer is 0 (no) or 1 (yes), and in that sense it is certainly true that $\mathsf{P} \subseteq \mathsf{\\#P}$.

The problem $\mathsf{\\#SAT}$ is $\mathsf{\\#P}$-complete. This means that for any problem $A \in \mathsf{\\#P}$ there exists a polynomial time reduction $f$ such that for any instance $x$ of $A$, we have $$ A(x) = \mathsf{\\#SAT}(f(x)), $$ where $A(x)$ is the value of the counting problem $A$ on instance $x$.

Since $\mathsf{2QCNF} \in \mathsf{P}$, there is a trivial reduction from $\mathsf{2QCNF}$ to $\mathsf{\\#SAT}$: if the $\mathsf{2QSAT}$ is satisfiable, we output the formula $x$, and otherwise we output the formula $x \land \lnot x$. This reduction runs in polynomial time since $\mathsf{2QCNF} \in \mathsf{P}$.
> 2 votes

---
Tags: algorithms, reductions
---


# Question
Title: How the LZ77 compression algorithm handles the case when the entire look-ahead buffer is matched in the search buffer
The LZ77 compression algorithm uses a sliding window technique, where the window consists of a look-ahead puffer and a search-buffer. What I am wondering is how the algorithm handles the case if the match of the word in the search-buffer is the entire word in the look-ahead buffer? According to the desriptions I find, the algorithm matches as long as it can, and then outputs the offset, the length of the match and the next token after the matched portion in the look-ahead buffer, but in case the entire look-ahead buffer is matched we do not have a next token to output?

I nowhere find this case described, for example the pseudocode just states "X first char after p in view", but I am asking about the case where we have no char after p in the view, as p is entire view?

For example, consider a search buffer of size 5 and a look-ahead buffer of size 4 and we read in

|abrar|rarr|ad

then we find a match at offset 3, and the match (which extends behind the boundary between both puffers, but this is no problem) goes up to all of rarr, even the next a could be matched, but what we should do now, should we output (3,4, C(a)) where C(a) denotes the code of a which is not in the look-ahead buffer, or should we just match the first 3 tokens?

# Answer
> 1 votes
A simple solution: your look ahead buffer is no smaller than your longest match length. As long as the start position is in the Search Buffer(a min of 1 byte), then the look-ahead buffer will have that one extra byte available to use as the follow byte

---
Tags: algorithms, data-compression, coding-theory
---


# Question
Title: GCD binary representation time complexity
```
1.  Consider the following algorithm for deciding GCD:

```

“On input :

```
1. If z doesn’t divide x or y, reject.               O(n)

2. For i from z + 1 to min(x,y) do:                  O(2^n)

    2.1. If i divides both x and y, reject.         O(n)

3. Accept.”                                           O(1)

```

Analyze the algorithm’s time complexity (in big-O notation).

n is the length of the max(x,y) So I was given an algorithm, the time complexity to the right is My addition and not part of this question. I want to make sure this is correct. I was thinking diving binary numbers is O(n) using long devision and step 2 just adds 0 or 1 to each previous number thus making the time exponential. Am I right ? Also, is there an algorithm that solves this in polynomial time ? Thanks

# Answer
> 1 votes
Assuming x \<= y and no particularly clever division, it's O (x log x log x), if you don't divide y by I if x is already not divisible by I.

If z divides x and y then you just need to check if gcd (x/z, y/z) = 1. And only test 2 \<= I \<= sqrt (x) and x itself.

---
Tags: turing-machines, computer-architecture, polynomial-time, arithmetic
---


# Question
Title: How do contemporary processors differ from a pure von Neumann architecture?
So I never really understood the von Neumann architecture, and have started to revise it as I wasn't in school during the lessons of the CPU. Can't really get help through my teacher as they wont respond to their email.

I have learnt about the von Neumann architecture, and now I need to know how the architecture differs from a contemporary processor.

I know that contemporary processors sometime use a mixture of Harvard and von Neumann architecture by using Harvard for the communication between the control unit and caches though for cost effective reasons von Neumann is used between the main memory and cpu.

The specification point wants to know how it differs though, and I will be very thankful for any responses that might answer the question.

Thanks!

# Answer
Well I think I may have answered my own question, the specification just wanted to know how it differs from the **pure** von Neumann architecture. It differs as contemporary processors use a mixture of architectures from Harvard and von Neumann for many reasons (mainly cost) and where speed advantages outweigh the complexity costs.

Contemporary processors use a mixture of both von Neumann and Harvard architecture, which differs from a pure von Neumann architecture by using von Neumann architecture for the main memory to the CPU and Harvard for the control unit and caches.
> -1 votes

---
Tags: computer-architecture, cpu
---


# Question
Title: Differences between SISD, SIMD and MIMD architecture (Flynn classification)
I have a problem with classifying certain CPUs to the proper classes of Flynn's Taxonomy.

# 1. Zilog Z80

According to this article on Sega Retro, Z80 has limited abilities to be classified as SIMD:

> a limited ability for SIMD (Single Instruction, Multiple Data) with instructions to perform copy, compare, input, and output over contiguous blocks of memory;

For what I understand, Z80 is usually behaving as a SISD but when it comes to performing thing like copying or comparing Z80 is able to process multiple data using a single instruction.

How should we classify Z80 then? Is the ability to become SIMD processor a voice for or against saying that Z80 implements SIMD architecture?

# 2. Intel i5 (Dual core)

Form what I understand, we classify multicore CPUs as MIMD.

Is it as simple as that?

# 3. ARM Cortex-A15 (single core)

I'd classify the architecture of this processor as a SIMD model. Wikipedia says that it has superscalar pipeline, but as we know from Why is a superscalar processor SIMD? that multiple pipelines does not imply MIMD model.

Are "modern" single cores usually implementing SIMD model or not?

---

# Answer
> 6 votes
Michael J. Flynn is one of the all-time great computer architects. He was the design manager of the IBM 360/91, and made numerous foundational contributions in the areas of pipelining, and in computer arithmetic.

But the Flynn Taxonomy has not stood the test of time, and is no longer useful.

The SI/MI part of the taxonomy is easy to differentiate on the surface: how many hardware *instruction pointers* (sometimes called *program counters*) does the machine have? If there is one hardware instruction pointer the machine is "SI" (either SISD or SIMD). If there is more than one hardware instruction pointer the machine is "MI" (either MISD or MIMD).

If you go a bit deeper, it becomes less clear though. Does a vector machine with one instruction pointer but vector predicate registers count as SI or MI? Why is a machine with only one fetch unit that can quickly (just a few cycles) switch back and forth between two different instruction pointers MI, but a machine with only one fetch unit that can context switch once ever few-hundred or thousand cycles considered SI? Is a machine with two hardware instruction pointers, but that only context switches at long-latency cache misses SI or MI?

The SD vs. MD distinction is just a complete mess. When Flynn made up the classification I believe he was referring to whether the machine had instructions that could operate on multiple independent pieces of data or not. That does *not* mean that the operations happen simultaneously. It could mean that the machine has instructions that operate on vectors of numbers, one at a time (or maybe pipelined), like the CDC STAR-100. The vector instructions in the CDC STAR-100 were pretty complex, giving two vectors start addresses to load, a start address for storing the result vector back to memory, and an arithmetic operation. The vector lengths were controllable on the CDC STAR-100. The CDC STAR-100 designers *could* have leveraged the implicit independence of the operations in the vector instructions to make some of those operations happen truly simultaneously, but they did not.

It may be more appropriate to talk about whether certain instructions in an instruction set architecture are "SIMD" or not. The ARM NEON instructions are SIMD instructions, but most of the other ARM instructions are not SIMD.

I don't know whether the Z-80's copy instruction was SIMD or not. I guess I'd call it SIMD because I can't think of any reason not to call it SIMD.

# Answer
> 7 votes
Flynn's taxonomy was defined by the great computer architect Flynn in 1960s. Though since that time there is an entire paradigm shift, so today it's better to understand these concepts with a different context. In modern world, parallel computing works by dividing large problems into smaller problems which are then solved at the same time.

Now let's understand Flynn's taxonomy, which says that computers have single (S) or multiple (M) streams of instructions (I) and data (D), leading to four types of computers: SISD, SIMD, MISD, and MIMD.

### SISD

In computing, SISD is a computer architecture in which a single uni-core processor, executes a single instruction stream, to operate on data stored in a single memory.

### SIMD

The SIMD architecture performs a single, identical action simultaneously on multiple data pieces. Here we have a single control unit (CU) and more than one processing unit (PU). For e.g. a single instruction to fetch multiple files.

### MISD

Multiple Instruction, Single Data (MISD) computers have multiple processors. Each processor uses a different algorithm but uses the same shared input data. MISD computers can analyze the same set of data using several different operations at the same time. The number of operations depends upon the number of processors. There aren't many actual examples of MISD computers, for e.g. fault-tolerant computers executing the same instructions redundantly in order to detect and mask errors.

### MIMD

It means that parallel units have separate instructions, so each of them can do something different at any given time. While technically it's true that most modern desktop/laptops are MIMD. Using the MIMD, each processor in a multiprocessor system can execute asynchronously different set of the instructions independently on the different set of data units.

---
Tags: computer-architecture, classification
---


# Question
Title: Operation on two CFLs which results in a non-CFL
Suppose we have two context-free Languages $L\_{1}$ and $L\_{2}$, and we form a new language $L\_{3}=L\_{1} \circ L\_{2} = \\{\alpha\beta | \alpha \in L\_{1},\beta \in L\_{2},|\alpha|=|\beta|\\}$. Is it possible that $L\_{3}$ is not context-free?

# Answer
Let's denote your operation by $\diamond$, so the question is, if $L\_1$ and $L\_2$ are CFLs, is $L\_1\diamond L\_2$ always a CFL? The answer is no.

Let $L\_1=L\_2=\\{0^n1^n\mid n\ge 0\\}$. This is, of course, a CFL. However, $$ L\_1\diamond L\_2=\\{0^n1^n0^n1^n\mid n\ge 0\\} $$ and it's not too hard to show that this language is not context-free.
> 3 votes

---
Tags: context-free
---


title: Is the language in class P

text:
# Question
Title: Is the language in class P
So class P is the class of languages that are decidable in polynomial time on a deterministic single-tape TM.

I can show that the decider for a language L\* runs in polynomial time.

So is it true that this language in class P? STARCLOSED DFA = { | A is a DFA, and L(A) = L(A)\*}

# Answer
A language L is equal to its Kleene closure if and only if L contains ε and L = L^2. So in a sense, this problem boils down to testing whether those two conditions are true. The test for whether L contains ε is pretty easy to accomplish - just see if A's start state is accepting. The trickier part is seeing whether L = L^2.

If you already know that ε ∈ L, then L ⊆ L^2, so the only way that L isn't equal to L^2 is if there's a string in L^2 that isn't in L. This is something we can test in polynomial time, as follows:

1. Construct an NFA for L^2 by applying the concatenation construction to A and itself. Call the resulting automaton B.
2. Take the cross product of B and the automaton formed by flipping the accept and reject states of A. Running this automaton corresponds to simultaneously running A and B, with the accepting states corresponding to executions that lead to an accepting state in B and a rejecting state in A.
3. Run a DFS over this net automaton to find an accepting state. If one exists and is reachable, there's a string in L^2 that isn't in L, and otherwise every string in L^2 is in L.

Step (1) takes polynomial time and builds an automaton with 2n states, where n is the number of states in the original automaton A, since we're just duplicating the states in A and adding in some new transitions. Step (2) builds an automaton with 2n^2 states, and the DFS in step (3) runs in time polynomial in n.

Overall, this construction runs in polynomial time.
> 3 votes

---
Tags: turing-machines
---


# Question
Title: How do the unit intervals compose when generating higher order homotopies?
I'm trying to apply homotopy type theory as a theoretical foundation for describing how database query plans solve relational algebra queries. I'm modeling the problem as, given a set of input function types and constraints on composing them, and a goal function type, find a composition of the input functions which has an equivalent type to the goal function type. Because interactions between datasets of subqueries can be nonlocal and also circularly dependent, we cannot assume that the codomain type of any function is defintionally equal to the domain type of any other function. (That is, the domains and codomains are dependent types dependent on *each other*.) Instead, what can be done is that the function types can be projected into other spaces which can be made equal by the univalence axiom, as long as we also properly keep track of what structure was projected away and "put it back" when computing the full solution.

In order to do this, I need to understand the rules of when a homotopy is applicable between two functions, and what is happening in the derivation rules when higher order homotopies are composed.

I've watched videos of talks about homotopy type theory which mention that since a path between paths is also a path, we can extend homotopies into higher order homotopies. However I'm confused about how the details of this process work out algebraically. I'm also interested in understanding the minimum requirements two paths must have in common in order to participate in a higher-order path.

The HoTT book defines a homotopy *introduces a classical homotopy* (see Andrej Bauer's answer) as a continuous map H between a pair of continuous maps $f:X \to Y$ and $g:X \to Y$ as $H:X \times \[0,1\] \to Y$. Let $I$ refer to the unit interval $\[0,1\]$ component of $H$ in the above definition.

My first difficulty is that $f$ and $g$ have a different "interface" (in programming terms) than $H$. In the definition, $f$ and $g$ were "functions of one argument" and $H$ was a "function of two arguments". If I then compose two paths $H$ and $H'$, what happens to their unit interval "argument" $I$ when I substitute $H$ and $H'$ for $f$ and $g$ in the original definition?

I do understand that a product of two types $X \times I$ can in turn be viewed as the single "opaque" type $X'$ from the level of the higher order path. However I am also concerned with how terms of the types are constructed and how the $I$ hidden in the lower-order homotopy relates to the $I'$ of the higher-order homotopy.

I can think of two scenarios:

1. The entire space $\[0,1\]$ of the inner $I$ collapses down to a single point.
2. The higher-order homotopy $H''$ should be treated of as having *two* interval arguments, $I\_1$ and $I\_2$, where $\\H''(x,0,0)=f\_1(x),\\H''(x,1,0)=g\_1(x), \\H''(x,0,1)=f\_2(x),\\H''(x,1,1)=g\_2(x)$

Here's what I think based on intuition:

Given functions $f\_{1}:A \to B$ and $g\_{1}:C \to D$, if $A \cap C = \emptyset$ and $B \cap D = \emptyset$, then both may be represented as loops attached to a single point, $f\_{B^A \rightsquigarrow \circlearrowright}:\* \to \*$ and $g\_{D^C \rightsquigarrow \circlearrowright}:\* \to \*$, where the subscripts by the function names represent encoding (somehow, somewhere) what was done to the function in collapsing it. Then, the homotopy is the trivial mapping of that point to itself. The "program" formed by the composition of all this might be summarized as $f\_1 \curvearrowright * \curvearrowleft g\_1$ which represents shrinking all of $f\_1$ down to a singularity and then inflating it back up to all of $g1$ or vice versa. (Sounds like a description of The Big Bang.) The resulting program would compute a Cartesian product. The idea there is that if $f\_1$ and $g\_1$ are really unrelated to each other, but by fiat you declared that a homotopy exists between them, that's the same as doing a CROSS JOIN between database tables with no common columns.

On the other hand if it is not the case that $A \cap C = \emptyset$ and $B \cap D = \emptyset$, then we cannot collapse them down to a singularity because the nonempty intersections of the input (co)domains represent an *interaction* between between $f\_1$ and $g\_1$ which potentially could represent *holes* in the space of the homotopy. That is, any pre-existing holes in the two input spaces could interact to produce a more complex hole in the homotopy. In the previous case we were able to ignore preexisting holes in the input spaces because the funny subscripting operation "preserved structure". But each subscript only related a particular space "up to" the singularity; if it could relate two different spaces "within" the singularity (or across it) then it would amount to begging the question (it would amount to assuming the solution to the problem we are purporting to solve). Therefore, we can only collapse dimensions which are *not* part of the intersection of the input spaces. The dimensions which *are* in the intersection form the space where the homotopy is "interesting" and the dimensions which are not form the part which was projected-away-but-recorded. This corresponds to an INNER EQUIJOIN.

How that relates to the unit interval argument $I$ is that if the (co)domains of $f$ and $g$ have no natural intersection, then we can take scenario (1) when constructing higher-order homotopies; $I$ collapses to a single point and we can simplify $X \times I \Rightarrow X \times 1 \Rightarrow X$. However if $f$ and $g$ have a nonempty intersection of the spaces they operate in, we have to go with scenario (2) and instead of unit intervals go to unit squares, unit cubes, etc.

Do I have that right?

# Answer
I recommend that in addition to watching videos you also read some material which actually explains homotopy type theory. Some good sources are:

1. The HoTT book, which is "the bible".
2. If you are philosophically minded you might like this primer by James Ladyman & Stuart Presnell.
3. It might not hurt to read on some basic notions in topology, where it is explained how paths are composed (but that's not what happens in HoTT).

I see you refer to the HoTT book in your question, but you falsely claim that the HoTT book *defined* a homotopy as a map $H : X \times \[0,1\] \to Y$. This is *not* what the HoTT book does, it's the *classical* definition of homotopy in topology. The HoTT definition is that a homotopy between $f, g : X \to Y$ is an element of $\prod\_{x : X} f(x) = g(x)$. Paths in homotopy type theory are *not* continuous maps from the interval, that again is classical topology.

I do not understand your setup for doing database queries, but let me just point out that there is HoTTSQL which is based on ideas from homotopy type theory.
> 2 votes

---
Tags: homotopy-type-theory
---


# Question
Title: An algorithm to find the area of intersection between a convex polygon and a 3D polyhedron?
Suppose I have a set of points in 3D which are all co-planar, and which describe the vertices of a convex polygon. I know the coordinates of all of these vertices, I know the unit normal to the plane of the polygon, and I know the order (in a right-hand sense with respect to the normal) in which the vertices go around the polygon.

I also have a polyhedron, which is in general non-convex, and the surface of which is made of triangles. It is a triangle mesh like the one shown here. It describes a completely enclosed volume (no holes in the surface). I know the coordinates of all the vertices of all the triangles that make up the polyhedron. For a given vertex, I know the list of which triangles it is a vertex of.

One other thing I know, which may or may not be useful, is that the polygon lies "in the vicinity of" a particular pair of vertices of the polyhedron, say the ones with indices $i$ and $j$. So if there were to be some kind of a search of the surface of the polyhedron, that would be the place to start.

My task is to find the area of the intersection between the polygon and the polyhedron. I believe this is a well-defined quantity. I need an algorithm to calculate this, hopefully efficiently but at this point I'll take anything.

My thoughts:

I can classify each polygon vertex as either inside or outside the polyhedron. I've written a ray-casting algorithm that computes this fairly accurately and efficiently. That means that each edge of the polygon can be classified as either "both vertices inside", "both vertices outside", or "one in, one out." I can calculate the point of intersection between a given polygon edge and the polyhedron by checking a bunch of nearby triangles.

But that's not enough. For instance, just because both vertices of an edge are inside doesn't mean the whole edge is inside. A "finger" of the polyhedron might intersect an edge without touching either of its endpoints. Furthermore, the polyhedron might intersect the polygon in such a way that it doesn't touch any of the edges at all. Clearly, one must also calculate the intersections between the triangles' edges and the polygon as well.

It gets a bit too complicated for me at that point, and I'm wondering if there is some established algorithm for this?

Perhaps something like: Project the polyhedron onto the plane containing the polygon and then... I don't know.

# Answer
You have a 2D convex polygon $G$, and a 3D polyhedron $H$. Let $P\_G$ denote the plane that the polygon is contained in. The following should work:

Their intersection is a 2D polygon. You can find the edges of the intersection as follows:

* For each triangle of $H$:

+ If the triangle intersects $G$, output this intersection.

This procedure outputs the edges of a 2D polygon, and now you want to compute its area. To do this, compute a triangulation of it (which apparently can be done in linear time), then sum up the area of the resulting triangles.

You can test whether a triangle intersects $G$ as follows: compute the intersection of the triangle with $P\_G$; call the result $R$. Typically, $R$ will be a point or line. $R$ can be computed efficiently. Then, compute the intersection of $R$ with $G$. This is purely a 2D problem. There are standard algorithms for solving this; see, e.g., https://en.wikipedia.org/wiki/Line\_clipping or http://geomalgorithms.com/a13-\_intersect-4.html.
> 3 votes

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


# Question
Title: How to convert two conflicting objective functions into a single objective function
I have two objective functions say f1 where I have to minimize (X+Y) and another function f2 where I have to maximize (A-B). The two functions are conflicting.

I need to convert them into a minimization problem involving one single objective function using the weighed sum approach where the final form would become f3 = Min {u*f1 (+ or-) v*f2} where u+v=1.

I am not sure what would be the sign before v*f2 ? I wonder if it should be f3 = Min {u*f1 + v*f2} or f3 = Min {u*f1 - v\*f2}.

Thanks in advance.

# Answer
To turn a maximisation problem into a minimisation one (or vice versa), simply multiply the value by -1.

Hence you want w1 * f1 - w2 * f2, for some appropriate choice of weights w1, w2 (which could indeed both be 1).

Unless there's some other requirement you haven't mentioned, there's no specific need for w1 and w2 to add up to 1: it depends on the relative importance of f1 and f2, which is problem-specific.
> 1 votes

---
Tags: optimization, modelling, convex-hull
---


title: Intuition behind straight-line programs

text:
# Question
Title: Intuition behind straight-line programs
Wikipedia defines straight-line programs in the following manner:

> In mathematics, more specifically in computational algebra\[disambiguation needed\], a straight-line program (SLP) for a finite group G = 〈S〉 is a finite sequence L of elements of G such that every element of L that belongs to S, is the inverse of a preceding element, or the product of two preceding elements. An SLP L is said to compute a group element g ∈ G if g ∈ L, where g is encoded by a word in S and its inverses.

This is a fairly confusing definition to unpack. However, in some meaningful sense, I believe the main idea here is that there are no comparisons allowed. Since there are no comparisons, the "computation tree" ends up being a straight line - hence the name "straight-line program."

In modern terms, is this the correct idea? Or are there even more subtle restrictions than this on what sorts of programs are allowed to be straight-line programs?

# Answer
> 2 votes
A straight-line program is one with no branches, no loops, no conditional statements, no comparisons -- just a sequence of basic operations.

A straight-line program for a finite group $G$ is a straight-line program in a very simple language with an unlimited number of registers $r\_1,r\_2,r\_3,\dots$ and with only two legal operations:

* $r\_i := \text{inverse}(r\_j)$
* $r\_i := \text{multiply}(r\_j,r\_k)$

You specify $i,j,k$ for each line of the program; those are constants. Each register holds a group element.

---

For instance, the following is a straight-line program that computes the cube of the element in $r\_1$ and stores the result in $r\_3$:

* $r\_2 := \text{multiply}(r\_1, r\_1)$
* $r\_3 := \text{multiply}(r\_1, r\_2)$

Here is another program that computes the same thing, but in a different way:

* $r\_2 := \text{multiply}(r\_1, r\_1)$
* $r\_4 := \text{multiply}(r\_2, r\_2)$
* $r\_5 := \text{inverse}(r\_1)$
* $r\_3 := \text{multiply}(r\_4, r\_5)$

---
Tags: complexity-theory, intuition, computation-tree-logic
---


# Question
Title: Applying a 1-qubit gate to entangled qubits
Given two entangled qubits in the state ${|00⟩+|11⟩\over \root \of 2}$, I have trouble getting the way of applying a **1**-qubit gate (let's say a Hadamard) to **1** of the entangled qubits (let's say the first one). Actually I have several questions:

* Following this link, Ran G. says that *"You **can** apply a quantum gate on any subset of the qubits."*
On the other, hand Agent Gotse says here that *"You **can not** compute the Hadamard gate on only one qubit, as the state is entangled and cannot be factored into two independent qubits."*
Do the answers contradict themself?
* I understand part of the principle of the entangled pair, it a superposition of bipartite system. But given for example an entangled pair $|00⟩+|11⟩ = |0⟩ \otimes |0⟩ + |1⟩ \otimes |1⟩$, and two unitary operators $A\ B$ to appy to the system.
Why can't we juste do $A|0⟩ \otimes B|0⟩ + A|1⟩ \otimes B|1⟩$?
I mean what is the **mathematical** meaning of that?
* Finally, the superdense coding use an entangled pair, and in the procedure given in the link, Alice apply some operator to her qubit without changing Bob's one (because it's probably far far away...). Quantum Computing textbooks say that in the case of an entangled pair, Alice has to apply $U \otimes I$, with $U$ the chosing operator.
But Alice has only **1** qubit, and clearly $U \otimes\ I$ acts on 2 qubits (it's a $4\*4$ matrix), how it's works **physically**?

# Answer
> 1 votes
I think you're confusing people talking about what must be done theoretically (to compute operations on qubits on paper) with people talking about what must be done experimentally (to operate on qubits in the real world).

> Do the answers contradict themself?

No. The person who appeared to be saying "you can't apply the operation" just meant that the algebra you do to apply the operation won't start by factoring the state. *When doing algebra* you can't apply the operation in the simple way that you'd use when the qubits factor.

> Why can't we just do $A|0\rangle \otimes B |0\rangle + A|1\rangle \otimes B |1\rangle$?

You can! $A|0\rangle \otimes B |0\rangle + A|1\rangle \otimes B |1\rangle$ is equivalent to $(A \otimes B) (|00\rangle + |11\rangle)$. To apply a Hadamard operation to one qubit while leaving the other alone, set $A=H$ and $B=I$.

> Alice has only 1 qubit, but U⊗I acts on 2 qubits. How does it work physically?

Alice just does whatever she would do to apply $U$ to her single qubit. That applies the operation $U \otimes I$ to the system of two qubits.

---
Tags: quantum-computing
---


title: Appropriate graph clustering algorithm

text:
# Question
Title: Appropriate graph clustering algorithm
I'm looking for an appropriate technique to search for clusters. My underlying data is 70,000 respondents to about 2500 multiple choice questions. Most respondents have not answered most questions. I have no expectations as to how many clusters I might expect or how clustered this data might be but am interested to explore if there are personality types wrt. to the kinds of questions asked, and if so, how well defined they are.

My thinking is that the best approach might be to transform the data into a graph and run a cluster analysis on that. Each node is a respondent and each edge is a distance between '0' or '1' derived from how similarly the respondents answered whatever questions they both responded to (or no connection at all, if they answered very few common questions) but I'm struggling to identify an appropriate algorithm for this situation.

Note: it seems likely that this graph setup will violate the principle of triangularity ie. there is no reason to suppose that $ dist(i, \ j) \leq dist(j, \ k) + dist(k, \ i) $ will always hold.

# Answer
> 0 votes
I would treat each multiple choice answer as a "feature" of a given user. If we assume your 2500 multiple choice questions each had 4 possible answers, you would then have a sparse matrix that is `70,000`x`10,000`. You could have a varying number of answers per question and still use this approach.

You could then cluster this via k-means or similar data clustering.

If you really want to do graph clustering, you could treat the sparse matrix as a bipartite graph, with `70,000+10,000` nodes, and edge exists where a user has given a certain answer. You could then apply graph clustering techniques like modularity maximization or graph partitioning.

Detecting these groups/clusters/communities falls under the category of unsupervised learning.

---
Tags: algorithms, graphs, clustering
---


# Question
Title: Calculate execution time from linear speedup
Given an execution time $t(c\_1)$ and linear speedup $s$, how do you calculate the execution time for $c\_2$ processor cores?

(Assuming Gustafson's law, or in other words, $t(\infty)=0$)

**My ideas:**

I haven't found any references that give formulas for calculating execution time, surprisingly. However, I think you can derive a formula from the speedup equation: $$speedup = t(1)/t(c)$$ The problem is, I'm pretty sure this is not what people are referring to when they give you a "linear speedup" factor $s$. I haven't been able to find any exact definitions on what "linear speedup" is. I can be sure that linear speedup means that $speedup$ is linearly dependent on cores. But what is the equation?

I looked at the superlinear speedup values from the introduction of this paper. The data points $(c, speedup)$ are $(2, 2.46)$, $(4, 4.68)$, and $(8, 9.59)$. From these, it would seem the formula is: $$s = speedup/c$$ This gives $1.23$, $1.17$, and $1.20$ for $s$; since $s$ should be constant, this seems like it could be correct. Assuming this is correct, you get: $$ t(1) = s\*c\_1\*t(c\_1)\\ t(c\_2) = c\_1\*t(c\_1)/c\_2 $$ But that can't be right, can it? It's not even dependent on $s$ anymore.

Perhaps one potential problem is that $s$ is only linear for $c\>1$; so maybe you cannot estimate $t(1)$ using that formula. I've thought of a way to correct for this, by devising this formula: $$s\*(c-1)+1 = speedup$$ This makes sure speedup is one for $c=1$, as you'd expect. With the modified formula, you get $1.46$, $1.23$, and $1.23$ for $s$. There is a greater variance in $s$, but not by much. So it seems like it *could* be a correct model. Both models work for linear speedup of one. I tried to find more datasets of non-one linear speedup, but couldn't find any. So I can't confirm whether this model works universally. Assuming this model, we get: $$ t(c\_2) = \frac{t(1)}{s\*(c\_2-1)+1}\\ \text{given: } t(1) = t(c\_1)\*(s\*(c\_1-1)+1) $$ This formula is at least dependent on $s$, as I would expect. But I feel like my corrected formula for $s$, from which this was derived, was rather arbitrary. For one thing, $s$ is undefined at $c=1$, even if it does make sure $speedup=1$. Secondly, the final equation for $t(c\_2)$ is not very intuitive; given $s=.7$ you'd think $t(2)$ would get a $1.4x$ speedup, not a $1.7$ speedup.

What are your thoughts? What am I doing wrong here? What is the correct derivation?

# Answer
> 2 votes
The term you're looking for is called parallel efficiency, which is a measure of how efficiently an algorithm uses its parallel resources. And you are correct that it is:

```
E = parallel speedup / p

```

Where p is the number of processors (or cores).

Your equation for `t(c_2)` is still valid, when the parallel efficiency is the same for `c_1` and `c_2`, as it's equivalent to:

```
t(c_1) / c_1 = t(c_2) / c_2

```

A parallel efficiency greater than one is truly possible. While it is observed sometimes, this is because of NUMA effects which accompany the access to more processors / cores (i.e., more of the problem fits in caches).

Also see: https://computing.llnl.gov/tutorials/parallel\_comp

---
Tags: runtime-analysis, distributed-systems, parallel-computing
---


# Question
Title: Do there exist algorithms for which the Big-O cannot be found out?
Just out of curiosity:

Do there exist algorithms for which the Big-O cannot be found out?

I have done a quick search in the google search bar: "Big o, impossible to evaluate" "algorithms without big o"

And these gave results which were unsatisfactory. Mostly, teaching me how to find the big o. Nothing I haven't learned earlier.

On a side note, it is my understanding that finding the big o requires us to assume the worst possible case. But, is that always a correct metric for efficiency? What is the likelihood a function is called with the worst possible argument?

# Answer
There are some algorithms for which, as of today, we are not able to prove termination, much less to bound complexity.

A simple case is given by the Collatz function: in pseudocode

```
function Collatz(n):
  if n <= 1  then return 1
  if even n then return 1 + Collatz(n/2)
  return 1 + Collatz(3*n + 1)

```

It is believed that, for any natural $n$, `Collatz(n)` will eventually stop recursing. However, we do not know whether this is is the case. Consequently, we also do not know an upper bound for the time complexity of this algorithm.
> 4 votes

# Answer
Normally, the order of complexity can be described as typical, best case and worst case. That complexity is normally expressed in terms of compute time, but could also be expressed in terms of memory utilization.

Big omega is commonly used to denote lower bound.

Big theta is commonly used to denote two sided bounds.

With respect to the aspect of your question around whether there are algorithms which cannot be characterized .. I would suggest that there are algorithms which are suitably complex, and who's performance has a very wide range of performance observations so as to not readily be characterizable. However, I am not aware of a proof that there are a class of algorithms which are uncharacterizable.
> 0 votes

---
Tags: time-complexity
---


# Question
Title: Prove that $L = \{ a^ib^jc^k | i < j \ and \ i+2j +3 < k \}$ is not CFG
Can someone help me prove that $L = \\{ a^ib^jc^k | i \< j \ and \ i+2j+3 \< k \\}$ is not a context free language?

I've tried applying the pumping lemma for CFGs and proving case by case (taking x=uvw, at first v is int $a^+$, then v is in $a^+b^+$ etc.but I'm failing to find a contradiction). Any help is welcomed.\

PS: The suggestion does not solve my problem. I know the technique of applying the pumping lemma for CFG to prome a language is not context free, but I don't know how to use it on this particular language.

# Answer
Firstly I want to point out that what you want to prove that $L$ is a context free *language* or CFL not grammar. A CFL can be defined by a CFG, but they are very different things. Anyway, back to your question.

I'm going to give you somewhat informal reasoning, but I think you will be able to formalize it if necessary.

Let us assume that $L$ is in fact a CFL. Then the pumping lemma for CFL's holds for $L$. Let **n** be the number of the pumping lemma for L.

Consider the word $w = a^nb^{n+1}c^{3n+4} \in L$

From the pumping lemma we have that $w = uxyzv, |xyz| \leq n, |xz| \geq 1, (\forall i \geq 0)\[ux^iyz^iv \in L$\]

We have two inequalities we can try to break:

1. $i \< j$
2. $i + 2j + 3 \< k$

Assume $xz$ does not contain $c$. This means that $xz$ contains only $a$'s or $b$'s (or both). Since $xz \geq 1$ This means we can pump up the word as much as necessary to break inequality $(2)$ -The right side of the inequality will remain the same when we pump up, but the left side will increase by at least $1$ on each step.

So we have deduced that $xz$ must contain a $c$.

Assume that $xz$ contains only $c$'s. Since $xz \geq 1$ we can pump down to remove at least one $c$. This will again break inequality $(2)$ since the right side will become less than or equal to the left.

So we have deduced that $xz$ must contain both a $b$ and a $c$. But since $xz$ contains a $b$, this means that we can pump down and remove at least one $b$, thus breaking inequality $(1)$.

Thus we have shown that no matter how we break up $w$ we can always pump it out of the language. This is contradiction with out assumption that $L$ is a $CFL$ so it must mean that $L$ is not a $CFL$.
> 2 votes

---
Tags: context-free, formal-grammars, pumping-lemma
---


title: Which graph algorithm should I use?

text:
# Question
Title: Which graph algorithm should I use?
I need to find the shortest path in a Directed Unweighted Cyclic graph. And it has to be optimal (find a path if exists one) and also optimal in terms of space and time complexity, being time complexity the most important. I think BFS is the solution. But am not sure.

What I am doing is mapping database tables into a graph data structure. And I need the shortest path for querying the tables with joins. Am storing information in the edges related to the nature of the relationship between the tables, like foreign key field and type of relation (one2many, one2one, etc).

# Answer
You can use bidirectional BFS. It will find a shortest path in an unweighted graph **much** faster than the traditional BFS.

The only additional requirement in using a bidirectional search is that you can efficiently compute the **parent nodes** of any given node.

If you ask why, the argument is simple: BFS runs in $\mathcal{O}(\sum\_{ = 0}^N b^i)$, whereas the bidirectional BFS runs in $\mathcal{O}(2 \sum\_{i = 0}^{\lceil N / 2 \rceil}b^i)$, where $b$ is the average node degree and $N$ is the length of a shortest path. So by carefully choosing the graph statistics, you can make bidirectional BFS arbitrarily faster than traditional BFS. Actually, twice I have seen a speed up of 1000.
> 2 votes

# Answer
Do you have any sort of distance-heuristic? If not, then yes, BFS is likely your best choice.
> 4 votes

---
Tags: graphs, time-complexity, shortest-path, space-complexity
---


# Question
Title: Are recursively enumerable languages closed under shuffle?
For languages $L\_1, L\_2$ over some alphabet $\Sigma$, we define

$$ \textit{Shuffle}(L\_1, L\_2) = \\{a\_1b\_1a\_2b\_2 \cdots a\_nb\_n : n \geq 1 \wedge a\_1, \ldots , a\_n \in L\_1 \setminus \\{ \varepsilon \\} \wedge b\_1, \ldots , b\_n \in L2 \setminus \\{ \varepsilon\\}\\}$$

I think that RE are closed under shuffle, I tried to use the multitape TM model with 3 tapes, one for the input, one for the $a\_1, \ldots , a\_n \in L\_1 \setminus \\{ \varepsilon \\}$, and the last one for $b\_1, \ldots , b\_n \in L\_2 \setminus \\{ \varepsilon \\}$, but the problem is that $a\_1, \ldots , a\_n, b\_1, . . . , b\_n$ are words from the languages,not symbols, so we do not know when $a\_1$ ends and $b\_1$ begins, any suggestions for proving closure under shuffle ?

# Answer
> 2 votes
*Hint:* A language is recursively enumerable if and only if it can be recognised by a *nondeterministic* Turing machine. Use this fact to build a nondeterministic recogniser for $\textsf{shuffle}(L\_1,L\_2)$ from the deterministic recognisers for $L\_1$ and $L\_2$. What is it, that one most use nondeterminism to guess?

---
Tags: formal-languages, computability, closure-properties, semi-decidability
---


# Question
Title: Correctness of Algorithm for Computing Diameter of a Graph
I am a TA for an introductory CS course, and one question given to students was how to use BFS to determine the diameter of a graph. The students were told they wouldn't be graded for efficiency, so the expected answer was a brute force algorithm where they ran BFS from every node to every other node and returned the maximum distance from these BFS runs. The students were provided with a BFS method they could reference in their pseudocode which took as an input a node and returned two mappings: one from each node in the graph to its distance from the start node (called distmap), and one from each node to its 'parent node' along the shortest path from the input node (called parentmap).

One student wrote the following algorithm:

```
1. Choice an arbitrary node from the graph and run BFS from it.
2. Create a set Temp of all the nodes that are not values in parentmap (ie nodes which don't lie upon any shortest paths)
3. Initialize max_dist to 0
4. For each node n in Temp:
    5. Run BFS from n
    6. For each value d in distmap:
        7. IF d > max_dist THEN set max_dist equal to d
8. RETURN max_dist

```

I believe this answer is correct, but I am unable to prove it. Can someone prove why it works or provide a counterexample?

# Answer
> 3 votes
It works for trees (although it can be simplified). However, on general graphs it does not work.

If your arbitrary vertex $v$ is the one on the top (labeled 1), then the `Temp={8,9}`. However, the unique diameter path is from 7 to 6.

---
Tags: graphs, graph-traversal
---


# Question
Title: Writing a Turing Machine that convers a number from binary to decimal
I'm trying to write a Turing machine that can convert a number in *binary* representation to a number in *decimal* representation. For example if the input on the tape is **1101** the output should be be **13**. Where should I start from?

# Answer
> 1 votes
Since you don't have any questions in your post, it's hard to give any concrete tips.

Try to do the simpler binary to unary converter instead. And should also assume that you have as many working tapes as you need (say, one input tape, one counting tape and one work tape) and a separate output tape.

You should also pick that of LSB/MSB that suits you best (e.g. LSB).

The biggest task is probably computing $2^i$, so you should start making one machine that takes as input a number $n$ in unary, and outputs (on a separate tape) $2^n$.

---
Tags: turing-machines, base-conversion
---


title: Data structure for A*'s "open" set

text:
# Question
Title: Data structure for A*'s "open" set
I'm looking at Wikipedia's pseudocode implementation of A\* and found myself wondering about what they call `openSet`. That is, the neighbours we've seen, but not yet analyzed.

The first part of the outer loop reads:

```
 current := the node in openSet having the lowest fScore[] value

```

And this makes sense to me, as I intuitively think of openSet as a heap. So we just pop() and get whatever's most interesting to look at next.

But when looping through the neighbours in the inner loop, this happens:

```
 if neighbor not in openSet // Discover a new node
                openSet.Add(neighbor)

```

And obviously, that's not going to go well with a heap. So what I'm wondering is this:

How is this contains() check meant to be carried out? Am I supposed to use something like an AVL tree to get logarithmic performance on both lookup and pop?

Would it make sense to keep a separate hashset to keep track?

Or can I altogether ignore this step?

What would be most effecient?

# Answer
I think I never heard the term "Open Set" as we usually call it "OPEN list" (and by convention we use upper-case letters). I mention this to highlight the fact that this structure is closer to a list than a set indeed ---thought sets might be used as well, see below.

Anyway, your understanding of the purpose of the OPEN list is perfect. It should contain all nodes generated that are awaiting for expansion, in contraposition to the so-called CLOSED list that contains all nodes that have been already expanded.

There are many different implementations of the OPEN list. For a good review of different ways to implement it, see Chapter 3 of Stefan Edelkamp, Stefan Schroedl Heuristic Search: Theory and Applications, Morgan Kaufmann 2011. In the following I'm just describing three typical alternatives:

**Plain open list**

The first alternative consists simply of using a list which sorts nodes in ascending order of their $f$-value. Extracting nodes from the list is done in $O(1)$ as it just suffices to take the first item from the list. Inserting is a little bit more difficult. The best would consist of creating a small OPEN list with the descendants of a node that has just been expanded and to sort it in ascending order of their $f$-values. Next, *merge* this sort list with the global OPEN list. The operation has a cost which is logarithmic in the size of the global OPEN list, but be aware that its size grows exponentially.

**Bucketed open list**

If the $f$-values of all nodes are known to be discrete and also to be bounded by a constant $B$, then create an array with $(B+1)$ locations, each one pointing to one different *list*. This ensures that inserting nodes in the OPEN list takes only $O(1)$: given a node with an $f$-value equal to $x$, just add it to the tail of the list pointed to by location OPEN\[x\]. Extracting is a little bit more difficult, but still very easy. You have to keep track of the lower non-empty index $x$, min x. When popping a node return the first node in the list pointed to by OPEN\[min x\]. Clearly, this requires some maintanenance: first, when removing all nodes with an $f$-value equal to min x, it is necessary to update this lower bound; secondly, if a node with an $f$-value strictly less than the current min x is inserted, min x has to be updated as well.

**Using sets**

A$^\*$ might additionally require to perform searches in the OPEN list. Strictly speaking, this is not required and the only purpose for doing it is to save some memory ---which anyway will grow exponentially. Note please that this will not avoid redundant expansions, as the CLOSED list already serves specifically to that purpose (in a nutshell: before the expansion of any node verify it is not in the CLOSED list; if so, skip the current expansion; otherwise, expand it and insert it into CLOSED) so I do not think it is really common practice to avoid the insertion of nodes in OPEN that are already in OPEN.

Anyway, if you are interested in saving some additional memory at the expense of investing some additional CPU running time, create a set with the current contents of the OPEN list (implemented in either way) and use it only for performing searches. Yeap, you might be thinking that you are then using twice the memory required by A$^\*$ but be aware that the memory consumption of this algorithm is exponential in the depth of the paths generated, so that multiplying the memory usage by a low constant (such as two) will not prevent your algorithm from finding solutions that otherwise could have been found.

Hope this helps,
> 5 votes

# Answer
First of all, it makes sense to implement the `gScore` in the Wikipedia's pseudocode as a hash table.

Next, considering an arbitrary node $v \in V$, it may have three "states":

1. It is in the open list,
2. It is in the closed list,
3. It is in neither open nor closed lists.

Also, note that the key set of `gScore` is exactly all the nodes in open and closed lists.

Now, you can implement

```
neighbor not in openSet

```

as

```
neighbor not mapped in gScore

```

Why this works?

Well, if we reached that very test, it means that it is not in the closed list, which implies that `neighbor` is in the open list or none of the lists. Since `gScore` contains all open nodes, `neighbor` is in the open list only if it is in the `gScore`.

Hope that helps.
> 1 votes

---
Tags: algorithms, graphs, shortest-path, efficiency
---


# Question
Title: using orientation sensor data to predict image points
I want to use Android's gyro/accelerometer/magnetometer to predict (over a very short time interval) how image points corresponding to a fixed object will change (without trying to scan for them in the image). In particular, suppose we have an object of known size with model points $v\_1, \dots, v\_N$. In this question, all vectors are assumed to be in homogenous form.

Here is what I am trying:

1. Detect the object. Let the pixel coordinates of the model points be denoted by $u\_1, \dots, u\_N$. Given the calibration matrix $K$ and negligible lens distortion, solve the PnP problem to get rotation $R\_0$ and translation $t\_0$ from the coordinates in which the vectors $v\_1, \dots, v\_N$ are defined into camera-centric coordinates, shown in black in the image above. In particular, the solution to the PnP problem solves the following equation. $$ u\_i = K \begin{bmatrix} R\_0 & t\_0 \\ 0^\top & 1\end{bmatrix} v\_i. $$
2. Simultaneously query the Android rotation sensor for a rotation matrix.
This is the relative orientation from Earth coordinates to the device coordinates (colored frame in the picture above). The direction of the this transformation is discussed informally in the Android developer site:

> The rotation vector represents the orientation of the device as a combination of an angle and an axis, in which the device has rotated through an angle $\theta$ around an axis ($x$,$ y$, or $z)$.

Let $R\_1$ denote this rotation matrix.

3. Rotate the phone a small amount and query the rotation sensor again for $R\_2$.
4. Render the predicted location to the pixel coordinates. For this, lets assume the sensors and the camera are collocated, so that the transformation from camera coordinates to device coordinates is a pure rotation: $$ D= \begin{bmatrix} 0 & -1 & 0 & 0\\ -1 & 0 & 0 & 0 \\ 0 & 0 & -1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix} $$ This matrix maps the black frame to the colorful frame in the picture. Note that the $+z$ axis of the camera frame (black in the picture) is meant to point out of the back of the phone, so that it constitutes a right-handed coordinate frame.

The transformation from the body coordinates of the object $v\_1, \dots, v\_N$ to the image coordinates in the perturbed camera frame $u\_1', \dots, u\_N'$ are given by $$ u\_i' =KD\begin{bmatrix}R\_2 R\_1^\top & 0 \\ 0^\top & 1 \end{bmatrix} D \begin{bmatrix} R\_0 & t\_0 \\ 0^\top & 1 \end{bmatrix} v\_i, $$ where we used the fact that $D=D^{-1}.$

Right now, I am stuck tying to verify that this equation actually works. Here is a simple experiment (that I have tried in Python). Let $v = (0, 0, 1)^\top,$ and suppose it is already defined in the camera coordinate frame, i.e., $R\_0=I$ and $t\_0=0.$ Moreover assume that $R\_1= I,$ Then, I rotate the device by a small angle about the $x$ or $y$ axis (which are the same for the device and for the Earth because $R\_1=I.$) This rotation constitutes $R\_2$ from the equations above. When I try this in Python, this is what I observe for various counter-clockwise rotations:

test rotation of device :: expected result :: observed result

rotate device about $+x$ :: $x$ pixel coordinate increases :: opposite behavior

rotate device about $-x$ :: $x$ pixel coordinate decreases :: opposite behavior

rotate device about $+y$ :: $y$ pixel coordinate decreases :: as expected

rotate device about $-y$ :: $y$ pixel coordinate increases :: as expected

# Answer
It turns out that I had two bugs that broke my experimental results:

* Even though the rotation matrix reports the rotation from Earth to Device, I should have been applying the opposite rotation to the point. It took me a day to convince myself of this. Basically, if you rotate the whole frame about, e.g., $+x$, then coordinates that remained fixed w.r.t. the device will rotate w.r.t. the Device frame about $-x$.
* I had a wrong minus sign in the rotation about the y-axis in the experimental results that I reported at the end. Note that y-axis rotations have a different +/- pattern than x- and z- axis rotations. See wikipedia for basic rotations.

The method described herein works fine (at least in theory). I'll post an update after I port my python dummy code into Android and see how it works.
> 3 votes

---
Tags: computer-vision
---


title: Reduce Turing Machine

text:
# Question
Title: Reduce Turing Machine
If $T\_n = \\{ \langle M \rangle \mid M \mbox{ is a Turing machine and } |L(M)| = n\\}$ where $n$ is $0,1,2....$

I need to show that if $n \geq 1$, $T\_{n+1}$ reduces to $T\_n$. I know I need to create a machine where that machine accepts $|L(M)|-1$ strings, which I could then use to verify with $T\_n$. I'm just confused as how to properly do it. Can I use some kind of search algorithm to find a string in it and exclude it?

# Answer
I don't want to spoil the exercise, but I'd try to play with the fact that the property

$$ p\_M(n,k):\ \mbox{$M$ accepts $n$ in exactly $k$ steps} $$

is decidable. Then, we have that $\langle M \rangle \in T\_{n+1}$ iff there are exactly $n+1$ pairs $(n,k)$ satisfying $p\_M$.

Try to exploit this in your reduction.

---

> Can I use some kind of search algorithm to find a string in it and exclude it?

This approach is unlikely to work: to search, the new TM $N$ would need to run $M$ on some given inputs, but this is risky since $M$ can diverge and "block" the whole execution of $N$. It's safer to work with decidable predicates like $p\_M$.
> 1 votes

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


# Question
Title: Why using finite automata in implementing lexical analyzers
I studied the subject of building a lexical analyzer using finite automata, through the classical way: Regular Expression -\> NDA -\> DFA. And I found it elegant, and a more solid approach for building a lexer.
Now my question is, what are other benifits from building a lexer this way, rather than the "*ad hoc*" way?

# Answer
> 3 votes
Speed and simplicity. A regular expression is a compact and declarative specification of lexemes. For most realistic regular expressions, simply writing code to mimic that specific regular expression would likely be something like an order of magnitude longer and less clear. This is especially true if you want high-performance.

A regular expression, on the other hand, can be compiled to very efficient code and is relatively simple to understand. You also get guarantees that are difficult or impossible to verify of code. For example, a regular expression is guaranteed to be implementable using only a fixed, finite amount of memory and matching is, of course, guaranteed to terminate. This is very similar to the reasons we use primarily SQL to query relational databases rather arbitrary code.

So far this has been an answer to the question of modeling/implementing lexical analysis with regular expressions, and not to why we would implement regular expressions with DFAs. Again, the main reasons are speed and simplicity. There are however, many other options including: directly interpreting the regular expression operators, compiling regular expressions to machine code, differentiating regular expressions, NDAs clearly, converting a regular expression to a CFG and applying CFG techniques. Many of these approaches are arguably "inherently" slower than DFAs, e.g. using CFG techniques suggests that there will be overhead to support a degree of flexibility that is not used.

There are two obvious ways of implementing a DFA at least when the alphabet is reasonably small. One is to have a two dimensional table indexed by state and character. This approach is modular in that you can write the matcher once and just change the language by providing a different table (perhaps dynamically). Matching involves incrementing a pointer, one 2D table lookup, and a highly predictable jump. A second approach is to "store the state in the instruction pointer/program counter" by having each state be its own block of code. Matching in this case involves incrementing a pointer and a(n unpredictable) indirect jump. Ignoring instruction/data caching and branch prediction effects, it's hard to conceive of a more efficient approach than these. You are looking at two or three machine instructions per character of input. In the latter case, we can improve on the instruction caching and branch prediction performance by combining blocks of code together. Again, all this can be handled by a tool that takes a regular expression as input. There's no real way to beat this latter approach to implementing DFAs in performance except by improving instruction caching or branch prediction.

---
Tags: finite-automata, compilers, lexical-analysis
---


# Question
Title: Shortest paths among two subsets of nodes
Given a directed graph $G = (V, E)$ with all edge weights being non-negative and two disjoint subsets of nodes $S, T \subseteq V$, design an algorithm to find the shortest paths among $S$ and $T$, (formally, $\min\\{d(s,t): s \in S, t \in T\\}$) in $O(m \log n)$ time, where $|V| = n$ and $|E| = m$.

# Answer
> 2 votes
*Note:* The first version of my problem is to find all $d(s,t)$ for each $s \in S$ and $t \in T$. As @D.W. argues, it is not likely to do this in $O(m \log n)$ time because taking $S, T = V$ requires all pairs shortest paths. For $\min\\{d(s,t): s \in S, t \in T\\}$, however, the following method of "adding extra nodes" works:

* Add an extra node $s\_0$ and add edges of weights 0 from $s\_0$ to each node in $S$
* Add an extra node $t\_0$ and add edges of weights 0 from each node in $T$ to $t\_0$
* Find the shortest path from $s\_0$ to $t\_0$.

---
Tags: graphs, shortest-path
---


title: information about matching algorithms?

text:
# Question
Title: information about matching algorithms?
I have been searching for matching algorithms similar to the Gale Shapley, or stable marriage algorithm, but with no luck. The question is if there are other algorithms that are similar to the GS and used for the assignation of persons or items based on preferences?

# Answer
A very similar well studied problem is the assignment problem. In essence, it seeks to find a matching in a weighted bipartite graph that has maximum weight. Such matching is not necessarily stable, but maximum weighted matching might be preferable than a stable one, depending on the application.

On the plus side, the well known Hungarian algorithm solves the assignment problem in an optimal manner. There are also other methods to solve it such as the Auction algorithms. As I said, the field includes well established methods.

Maybe you can think about representing your problem as an assignment one rather than stable marriage.
> 1 votes

---
Tags: matching
---


# Question
Title: Does there exist a Turing-machine that runs in time $o(n\log n)$, but not $O(n)$?
It is known that any (deterministic, single-taped) Turing-machine that runs in time $o(n\log n)$, decides a regular language (e.g., see this link). Thus, there exists an equivalent Turing-machine that runs in time $O(n)$. In other words, if $t(n)=o(n\log n)$ then $$\mathsf{DTIME}\left(t\left(n\right)\right)\backslash\mathsf{DTIME}\left(n\right)=\emptyset.$$

I was wondering whether there exists an example in which the original Turing-machine was not already running in time $O(n)$.

To sum up: Does there exist a Turing-machine that runs in time $o(n\log n)$, but not $O(n)$?

# Answer
> 7 votes
The answer seems to be negative, according to Corollary 4.12 of *Verifying Time Complexity of Deterministic Turing Machines* by David Gajser (ArXiv).

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


title: Subset partition problem variant

text:
# Question
Title: Subset partition problem variant
Given a set S of integers, the task is to partition the set into subsets such that:

* Total number of partitions is maximized
* Each partition has sum at least K

This looks like a variant of bin-packing problem, in which the bin has to filled upto a minimum capacity and the objective is to maximize the number of bins. I looked up the solutions of bin-packing problem, turned out ffd was the best approximation solution to it.

Could someone please tell me how to approach the partition problem?

# Answer
> 2 votes
For its complexity, note $N$ the sum of all your integers. Then, the number partitioning problem injects itself into your problem with $K=\frac{N}{2}$

I found this paper which deals with almost your problem. It aims to maximise the number of bins used, but instead of working with each partition must have a sum of at least $K$, you have each partition cannot be completed with another item.

Edit: Another user already asked almost the same question: https://scicomp.stackexchange.com/questions/8216/bin-packing-maximise-number-of-bins-fukubukuro-problem

---
Tags: algorithms, combinatorics, sets, partitions
---


title: Big-O notation based on runtime

text:
# Question
Title: Big-O notation based on runtime
I am having a hard time determining the Big-O notation based on the runtime of the algorithm. I would really appreciate it if any one of you could give me some hint/ or tips in answering the question.

# Answer
Taking into account both of the comments above, you can improve a pretty good answer for your problem by taking different orders of magnitude and then using log-logplot in order to get a polinomal for which your data converges (for instance you can use Lagrange's interpolation theorem result) so you can determine a good approach for the function you're looking for. You can check this site to get more info about, not only the process I've just described for you, but also about big O notation and theta notation (also known as tilde notation).
> 1 votes

# Answer
Measuring the runtime of an algorithm may give you an educated guess about the time complexity of an algorithm, if used intelligently. That educated guess may be wrong. On the other hand, it may be right, and having a correct guess may make it easier to prove the time complexity.

In your case my educated guess would be a large constant, plus maybe some growing factor, with no good guess possible with your small numbers. Try n = 100, 1000, 10000 and see what happens.

Another effect of measuring the runtime is that it takes account the presence of bugs in your implementation. You might try to implement bubblesort and get linear time in your runtime - that's quite possible if there's a bug in your code. Your array will probably not be sorted :-(
> 1 votes

---
Tags: algorithms, data-structures, computer-architecture
---


# Question
Title: How to count the bits with a 1 bit error correction Hamming code?
I've seen both ways of counting the bits when determining where to place the parity bits in a 1 bit error correction Hamming code. Some people count the bits starting from the left, others do it by starting from the right.

When to use one or the other? Does this depends on the Endian ordering?

# Answer
> 0 votes
Yes, it is about what bit-endianness you choose. Just make sure you are using the same interpretation on both ends.

(However if on 'Endian ordering' you meant byte order, that does not really apply here. As most Hamming codes do not transfer a whole number of data bytes, it is far simpler to think about the input as a stream of bits)

---
Tags: hamming-code
---


# Question
Title: Turing machine that increments a binary number by 1
I was asked to construct a Turning Machine that computes the increment of a binary string by 1- The Turing Machine receives a binary string and accept a string which is an increment by 1 of the input, written to the left of the head . I was given the fact that the head first reads the **MSB**.

I thought of an Idea but I do not see how to put it into action: My idea was to:

1.First put a $ sign at the beginning of the string

2.Place the entire string right side to it

3.Starting to increment from the end, switching $1$ with $0$

4.Once I stumble upon $0$ I replace it with $1$ and then accept it or Once I stumble upon $ I replace it with 1 and accept

I can't seem to find a way to put a $ at the beginning of the string without losing any information..any help with will be very helpful!

# Answer
*Hint:* First write an informal description of the machine, then give a precise description as a transition diagram. Use the state of the Turing machine to hold the carry bit.
> 2 votes

# Answer
This is my solution:

Note: B is for Blank.

I drew the Machine in this website: http://madebyevan.com/fsm

Algorithm:

1. Add a `0` at the beginning of the string (To be able to handle overflow).
2. Traverse through the string to get to the LSB.
3. Traversing backwards (LSB to MSB); use `NOT` operator on every `1` until you reach a `0` (Since we added a `0` at the beginning, we are certain that we will eventually reach a `0`)
4. use `NOT` operator on said `0`.
5. Traverse backwards until you reach the beginning of string.
6. If the first bit is equal to `0`, you have to remove it with blank.
7. If the first bit is equal to `1`, it means that overflow has occurred. (Nothing needs to be done in if you reach this step)

Any improvements will be appreciated.
> 1 votes

---
Tags: computability, turing-machines
---


# Question
Title: Number of grid points in d-dimensional sphere of radius r
Given integers $d$ and $l$, compute the number of grid points $x \in N^d$ that satisfy $\sum\_i x\_i^2 \leq l$ (i.e. $||x||\_2^2 \leq l$). (Think of $l$ as $r^2$).

The problem is obviously in #P. Is it in P or a smaller class? What if in place of $l\_2$ we use $l\_p$?

# Answer
I'll assume $l,d$ are given in unary, otherwise the problem has a trivial exponential lower bound as the number of solutions can be $\Omega(2^d)$, e.g. in the case of $l=d$, each entry could be zero or one.

If we are given $1^l,1^d$, then this can be solved in polynomial time. Suppose $d=2^k$ (this will simplify things), and let $A(d,l)$ be the recursive algorithm for counting the number of solutions which is defined as follows:

$A(d,l)=\sum\limits\_{l'=0}^l A\left(\frac{d}{2},l'\right)A\left(\frac{d}{2},l-l'\right)$

I'm pretty sure $A$ can be made to run in polynomial time using memoization, by keeping a $d\times l$ size table of the values we computed so far.
> 1 votes

---
Tags: algorithms, complexity-theory, computational-geometry
---


# Question
Title: Language of balanced parentheses; Biconditional proof about parentheses
Let L be language of balanced parentheses.

(a) Prove If there are equal number of ('s and )'s and every prefix of w contains at least as many ('s as )'s, then w is in L.

(b) Prove If w is in L, then there are equal number of ('s and )'s and every prefix of w contains at least as many ('s as )'s.

After much thought, I don't seek what I'm supposed to be doing. All I know is that I'm supposed to be using induction.

Here is the grammar that generates L: $S\to SS|(S)|\epsilon$

# Answer
You are given two different definitions of the language of balanced parentheses:

1. $w \in L$ iff $w$ contains an equal number of "(" and ")", and every prefix of $w$ contains at least as many "("s as ")"s.
2. $L$ is generated by the grammar $S \to SS | (S) | \epsilon$.

You need to show that both definitions are the same. The easy direction is showing that each word generated by the grammar satisfies property (1). You do this by induction - either induction on the length or "structural" induction, which in this case is induction on the number of derivation step (base case: $S \to \epsilon$, steps: $S \to SS$, $S \to (S)$). The other direction is more complicated. You need to use complete induction; given a word $w$ satisfying (1), figure out which production needs to be applied first, and which parts of the word it generates, and then appeal to the induction hypothesis.
> 3 votes

# Answer
In fact you are given two languages

1. $L\_1$ defined as a set of strings of balanced parentheses.
2. $L\_2$ defined as a set of strings with equal number of ('s and )'s and every prefix of w contains at least as many ('s as )'

You have to prove that these two languages/sets are equal. One way to prove it is to demonstrate that the grammar you indicated in your post does generate both languages.

Another way is to prove $L\_1 \subset L\_2$ and $L\_2 \subset L\_1$.

I would go about this as following:

**First I show that if a string $s$ consists of balanced parentheses then it is generated by the grammar.**

*Proof*: (by induction on the length of the string)

*Base case*: the string $()$. It is generated by $S\Rightarrow (S) \Rightarrow ()$.

*Induction*:

Case 1: $s = \alpha\beta = (...)(...)$. Then by induction on the length of strings we know that $S\Rightarrow^\* \alpha = (...)$ and $S\Rightarrow^\* \beta = (...)$, so we can generate $s$ by $S \Rightarrow SS \Rightarrow^\*(...)(...)$.

Case 2: $s = ((...)) = (\alpha)$. Then by induction we know $S \Rightarrow^\* \alpha$, and so we can derive the whole string by $S \Rightarrow (S) \Rightarrow^\* ((...))$.

**Then I would show that any string generated by the grammar consists of balanced strings.**

*Proof*: by induction on the length of a derivation.

*Base case*: $n=1$, $S \Rightarrow ()$ is clear. Ignore $S \Rightarrow \epsilon$ since the grammar may be rewritten without $\epsilon$.

*Induction*: Fix $n$ - length of a derivation leading to terminal strings.

Case 1: Start with $S \Rightarrow SS$. Both S's turn into terminal strings $\alpha$ and $\beta$ respectively in fewer than $n$ steps and so both are strings of balanced parentheses. Hence $\alpha \beta$ is a string of balanced parentheses

Case 2: Start with $S \Rightarrow (S)$. $S$ turns into a terminal string $\alpha$ in fewer than $n$ steps and so is a string of balanced parentheses. Thus $(\alpha)$ is a string of balanced parentheses.

Therefore, the grammar generates only and only ALL strings with balanced parentheses.

Analogously for the language $L\_2$.
> 2 votes

# Answer
**Hint.** Since you don't have a formal definition for $L$, I suggest to use the following one: $L$ is the context-free language generated by the grammar $$ S \to SS + (S) + 1 $$ where $1$ is the empty word. Now you can try to prove (1) and (2). In my opinion, (2) might be easier.
> 1 votes

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


# Question
Title: What's the fastest way to find the longest (partial) repeat in a sequence that continues to the end?
Here are some sequences:

```
'0.66666'
[3,0,1,2,2,2,0,1]
'banana'
'bandana'
'11221122'

```

I would like to find the index and length of the substring in each which is repeated (even if partially) for the most terms and which repeats until the end.

I wrote a function in JavaScript that successfully returns the **expected output:**

```
'0.66666'           After occurring at index 2, '6' repeats for 4 terms.
[3,0,1,2,2,2,0,1]   After occurring at index 1, [0,1,2,2,2] repeats for 2 terms.
'banana'            After occurring at index 1, 'an' repeats for 3 terms.
'bandana'           After occurring at index 4, 'an' repeats for 1 terms.
'11221122'          After occurring at index 0, '1122' repeats for 4 terms.

```

**Explanation:**

* `[3,0,1,2,2,2,0,1]` is a sequence with 8 terms. `[0,1,2,2,2]` is the longest substring which repeats at least partially to the end of the sequence, because after its first occurrence it repeats directly after for another 2 terms. Then the sequence terminates.
* If we were to input `[3,0,2,2,2,0]`, you might think the substring `[2]` wins because it repeats for 2 terms following its first occurrence, but it doesn't repeat to the end so the substring `[0,2,2,2]` wins as the term that follows the only occurrence of this substring (`0`) is also the first term in the substring meaning that it repeats for 1 term following the first occurance.

Repetition must continue to the end so for the second example `[2,2,2]` is not valid though it also repeats for two terms

Here's the function (JS Bin):

```
function longestRepeatedSuffix(sequence) {
    var repeatStart;
    var blockLength;
    var maxRepeatLength = 0;

    // Go through each suffix from length 1 to the length of the sequence - 1.
    suffixLoop: for (var suffixI = sequence.length - 1; suffixI > 0; suffixI--) {
        var len = sequence.length - suffixI;
        var repeatLength = 0;

        // Go right to left through adjacent substrings the length of suffix.
        // substringI may be negative on the last iteration.
        for (var substringI = suffixI - len; substringI >= 1 - len; substringI -= len) {

            // Go right to left through characters in the suffix and current substring.
            for (var charI = len - 1; charI >= 0 && substringI + charI >= 0; charI--) {

                // See how many characters match.
                if (sequence[substringI + charI] === sequence[suffixI + charI]) {
                    repeatLength++;
                    if (repeatLength > maxRepeatLength) {
                        maxRepeatLength = repeatLength;
                        repeatStart = substringI + charI;
                        blockLength = len;
                    }
                } else {
                    continue suffixLoop;
                }
            }
        }
    }
    return 'After occurring at index ' + repeatStart + ', "' +
        sequence.slice(repeatStart, repeatStart + blockLength) +
        '" repeats for ' + maxRepeatLength + ' terms.';
}

```

I believe this is an O(n^2) implementation even though I used 3 nested `for`-loops. So my question is: how can I use something like a suffix-tree to get even better time complexity?

**Similar algorithm:**

* **Longest repeated substring:** This is different, as it includes repetitions which overlap and those which are not adjacent (not just consecutive repetitions) and it doesn't require repetition to continue to the end.

# Answer
This can be solved with a prefix function in linear time.

Prefix function of a string $S$ is an array $p$ of length $s$, where $p\_i$ is the length of the longest border of a string $s\_1 \dots s\_i$. The $border$ of a string is its longest proper prefix which is also a suffix. E.g. the border of $abacaba$ is $aba$, the border of $ababa$ is $aba$, the border of $banana$ is empty. The prefix function can be computed in linear time (see this Coursera lecture, for example).

For simplicity I reverse the string and now look for a recurring prefix, not suffix. Let $p\_i$ be the prefix function of the string. Then the length of the shortest recurring substring of the $i$-th prefix of the string is $i - p\_i$:

```
s: a b a c a b a c a b a
p: 0 0 1 0 1 2 3 4 5 6 7
   -------------
           -------------
   + + + +

```

With hyphens I denote the matching prefix-suffix pair found by prefix function, and with pluses the generating prefix itself. It is easy to see that it ends exactly where the matching suffix begins, that is, at the position $i - p\_i$.

Having the length, the answer is trivially computed as $i - (i - p\_i) = p\_i$. Isn't it the nice observation? ;) So what you actually want to do is to take the maximum value of the prefix function of the reversed string.
> 2 votes

# Answer
Let $x\[1\],\ldots,x\[n\]$ be your string and let the alphabet be $A=\\{1,2,\ldots,m\\}$. Do a single pass in $O(n)$ and determine the highest frequency character $a \in A$ and its support, so $S\_a=\\{i: 1\leq i\leq n, x\[i\]=a\\}$ and $f\_a=\\# S\_a.$

If I understood the question as being the "most common substring with partial repeats", you are looking for is the longest substring which starts at the first occurence of $a$, i.e., $k=\min(S\_a)$ and its length is $$n-\min(S\_a)+1.$

So the candidate string $C\_a$ is $x\[k\],x\[k+1\],\ldots,x\[n\].$

You can find it in $O(n)$ time as above.

**Edit:** In response to OPs comment, let $k'=\max(S\_a).$ One can now see if string $x\[k'\],\ldots,x\[n\]$ is a prefix of the candidate string $C\_a$. Call this Condition 1. If yes, we are done. If no, repeat above algorithm for the next most frequent letter $a',$ etc. until we find that Condition 1 holds. This would seem to give $O(n^2)$ complexity.
> 0 votes

# Answer
This can be solved in $O(n)$ time, i.e., linear time, using a suffix tree or suffix array. Let $S\[1..n\]$ denote the input string. You want to find the largest length $\ell$ such that the suffix $S\[n-\ell+1..n\]$ appears somewhere in $S\[1..n-\ell\]$.

This can be solved with a suffix tree. Let $S^r$ be the reversal of $S$ (i.e., the string $S\[n\]S\[n-1\] \cdots S\[1\]$). Build a suffix tree/array for $S^r$. Given any string $t$, this lets you find the last place where $t$ appears as a substring of $S^r$, i.e., the first place where $t^r$ appears as a substring of $S$. Now there's a nice algorithm for your problem:

* Build a suffix tree for $S^r$.
* For $\ell := 1,2,\dots,n$:

+ Look up the string $S\[n\] S\[n-1\] \cdots S\[n-\ell+1\]$ in the suffix tree for $S^r$.
    + Use this to find the first (smallest) index $i$ in $S$ where the string $S\[n-\ell+1..n\]$ appears in $S$.
    + If $i \le n-2 \ell$, you've found a valid candidate substring that repeats for $\ell$ terms.
* Output the last candidate you found, i.e., for the largest value of $\ell$ where you found a valid candidate.

Note that if you keep track of where you are in the suffix tree for $S^r$, then each iteration of the loop can be done in $O(1)$ time. You can build a suffix tree for $S^r$ in linear time, too. Therefore, the total running time is $O(n)$.
> 0 votes

---
Tags: algorithms, time-complexity, strings, substrings
---


# Question
Title: Heavy hitters problem linear scan and auxiliary space
I'm looking at Lecture #2 from this Stanford course http://web.stanford.edu/class/cs168/index.html, let me introduce the HH problem:

We have an array of $n$ elements and we want to know which elements appear at least $\frac{n}{k}$ times, for a given $k$. You can think of $n$ as being pretty large and $k$ small.

**Proposition** There's no algorithm that solves the Heavy Hitters problem in one pass while using a sublinear amount of space.

An intuition for why this holds is given in the notes:

* for $k=\frac{n}{2}$ we're looking at elements that appear at least twice in the array.
* suppose the array is of the form $x\_1, x\_2, \ldots , x\_{n-1}, y$ , say $S=\\{x\_i \mid 1\leq i\leq n\\}$, then basically the HH problem reduces to a membership problem, is $y\in S$?
* we can solve this problem by saving $S$ as a hash table, and the idea is that we can't solve all the memebership problems (for say $n/2$ elements) using sublinear space.

They suggest using the PHP but I don't see how that applies in this context, any idea?

I can see why the statement is true but I'm looking for a formal proof of it.

# Answer
> 3 votes
Here is the idea, taking as an example the case $k = n/2$ which you mention. Also, let's assume that a *word* is $\log n$ bits, and that each element consists of $C$ words. In total there are $n^C$ possible elements, forming the universe $U$.

Suppose that an algorithm uses $m$ words of space. For each subset $S$ of $U$ of size $n-1$, let $T(S)$ denote the contents of memory after the algorithm has read the first the elements of $S$ in order. We claim that $T(S\_1) \neq T(S\_2)$ if $S\_1 \neq S\_2$. Indeed, suppose without loss of generality that $S\_1$ isn't a subset of $S\_2$, and let $x \in S\_1 \setminus S\_2$. If the last element that the algorithm reads is $x$ then it should output $x$ if it had read the elements in $S\_1$, and it should output nothing if it has read the elements in $S\_2$.

Since there are $\binom{|U|}{n-1} = \binom{n^C}{n-1}$ different sets $S$ and $n^m$ different memory settings, we conclude that $\binom{n^C}{n-1} \leq n^m$. Since $\binom{a}{b} \geq (a/b)^b$, we conclude that $(n^{C-1})^n \lesssim n^m$, and so $(C-1)n \leq m$ or $m = \Omega(n)$ (for $C \> 1$).

# Answer
> 2 votes
The reference for the proof the lecture refers to is:

N. Alon, T. Matias, and M. Szegedy. *The space complexity of approximating the frequency moments*. In Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, 1999.

http://www.tau.ac.il/~nogaa/PDFS/amsz4.pdf

You'll find the reult you're looking for in §3.7.

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


# Question
Title: Given a Noisy Curve, Write a Function to Output Likely Slopes
I am training a Variational Autoencoder (type of convolutional neural network), and have been plotting cost over time. The result is a noisy curve, shown here:

I would like to write a function that gives the probability that the cost function has bottomed out, i.e. that its slope going into the future is zero. Due to the noise, I can't just take the derivative of the cost function, as it oscillates stochastically. I could take the derivative of the *moving average* of the cost function, but it would be unclear what window size to use, and regardless a single window size would be useful for only part of the line (the noise tends to increase over time).

**Is there some mathematical function/theorem I can use to take the local noise of the curve into account, and output a range/distribution of probable slopes?** I would imagine the output being something like a histogram with the most likely slope at the middle and increasingly less-likely slopes off on the sides.

# Answer
> 1 votes
A moving window (with some reasonable window size) is probably hard to beat. I don't know of any parameter-less solution.

Another possible approach could be to estimate the slope of the last 10% of the data, and compare this to some threshold. (So, the 1000th data point uses the average of points 900-1000. The 2000th data point uses the average of points 1800-2000. And so on.) This way, if it does flatten out, then if you continue for another 10% longer, you'll reach a point where the last 10% is all flat and the procedure will likely terminate. This may do 10% more iterations than "necessary", but that might be acceptable given that in return you get a procedure that doesn't require a fixed window size.

However, choosing a threshold might be a bit tricky. I'm not sure how to do that in a reasonable way.

Given a bunch of data points, you can compute a least-squares fit for the regression line through those points, and find an estimate of the slope of that line. You can also compute a confidence interval for that slope. This will give you a range of plausible slopes.

---
Tags: optimization, neural-networks, approximation, randomness
---


# Question
Title: Problem of finding a very independent set of size at least $k$ is NP-Complete
Given a simple graph $G$, A subset of vertices $V\_G$ is called "very independent" if there is no edge between each pair of the vertices in $V\_G$ and for each pair $v,v'$, there is no vertex which is connected to both $v$ and $v'$.

In other words, a very independent subset is an independent subset of vertices like $V\_G$ such that there is no path of length $2$ or less than it, between each pair of vertices in $V\_G$.

How can we prove that the problem of finding a "very independent set" of size at least $k$ in a given simple graph is NP-Complete?

Note: I was thinking of reducing it to the problem of finding an independent set of size $k$... But, Is that even NP-Complete?

# Answer
> 1 votes
Your notion is what is called distance-2 independent sets, also a particular case of rulling sets (see here Independent set where two vertices need to have distance \>= c).

Your problem is NP-complete by an easy reduction to Independent Set (which is NP-complete, https://en.wikipedia.org/wiki/Independent\_set\_(graph\_theory)#Maximum\_independent\_sets\_and\_maximum\_cliques): for every vertex $u,v$ of $G$ such that there exists $w$ with $(u,w) \in E$ and $(v,w) \in E$, add the edge $(u,v)$.

This gives you a new graph $G'$ whose independent sets are the distance-2 independent sets of $G$.

---
Tags: graphs, np-complete
---


title: Have I invented a new data structure?

text:
# Question
Title: Have I invented a new data structure?
EDIT: Seems like what this structure is nothing more than a 26-bit bitwise trie, as KWillets suggested in the comments! You can think of the words we insert the trie as 26-bit Bitsets where the i-th bit indicates whether the word contains the i-the letter in the alphabet.

As I was tackling an interview problem I came up with this tree-like data structure. Actually it IS a binary tree that is maximum 26(English alphabet size) nodes deep. Basically the problem is:

> There are a set of dictionary words and a set of license plate numbers. Write a code/algorithm to find the shortest dictionary word which contains all the letters in the license plate, irrespective of the order of characters

This data structure is specifically designed for the problem of finding words from a given list containing all letters from a set of letters.
I call this operation getSupersetWords().

It can also be used for finding words containing ONLY a set of letters.(In fact my empirical tests show that this is the use case giving the best performance gain over linear search (**over 16 times faster** on average for a list of 73k English words)).
I call this operation getSubsetWords().

To give you an example:

Lets say we have list of words = \[ “cat” ,”dog” “cow”, “case”\].

On query getSupersetWords(\[‘a’, ‘c’\]) we get \[“cat”, “case”\].

On query getSubsetWords(\['c', 'o', 'w', 'a', 't'\]) we get \["cat", "cow"\].

**How to add a string to this data structure ?**
As I said earlier the data structure is a binary tree. At every level of the tree we make a decision. If the word contains the next letter of the alphabet(we start from 'a' at level 1) we go right, else we go left.
If we have made all the 'right' possible decisions for the given word we place it in the current node.(A node contains a reference list of strings).

**How to answer a query from this data structure ?**
Now to answer a getSubsetWords() query we traverse the tree recursively in DFS making both decisions if the query contains the character at the current letter, or 'left' if it doesn't and adding the words at the given Node to a list
(this is VERY confusing to type out...but not so much in code :/).

It sounds confusing, that's why I made a simple diagram illustrating the idea.

Assume we have a list of strings = {"a","aaa","baa","ab","bb"}.

Now If we had 'z' in the list the tree would be 26 nodes deep, but because the 'biggest' letter is 'b' We only need 3 levels.

The circle shapes are lists of strings, the rectangles are the nodes. I was wondering if this structure is something I have 'invented' or it is already well known, (Which probably is the case :).

# Answer
After a short research on the subject I found out that this data structure is first examined in paper by Rivest from 1976 http://epubs.siam.org/doi/abs/10.1137/0205003
> 3 votes

# Answer
I've never seen this data structure before. However, it doesn't seem like a good choice for storing a set of words, for most purposes. I see three significant disadvantages:

* **Performance.** Looking up a word in this data structure can potentially be quite slow. In particular, when looking up a word of length $n$, checking whether it contains a particular letter involves looking at all $n$ characters of the word. Therefore, traversing the entire tree (all 26 levels) might require reading the entire word 26 times. In contrast, a trie reads each character of the word only once, so might be about 26x times faster. Same for a hashtable.
* **Space usage.** This might take a lot of space. I am assuming you won't construct a node unless it is needed (i.e., if it has only one child, you'll omit the node). With that optimization, the depth of the tree is at most 26 if you're using words with letters a-z. If you are storing strings in Unicode, the depth of the tree might be enormous, and in the worst case this might devolve to a data structure where the depth of the tree is proportional to the number of words in the set, and then the space usage is bad and the time for a lookup is very bad (linear in the size of the set). Without that optimization, the number of the nodes in the tree can be as large as $2^{26}$ for letters a-z, or enormous for Unicode strings.
* **Incomplete.** This isn't a complete data structure. It cannot distinguish between two words with the same set of letters, e.g., between words that are permutations of each other (anagrams). Therefore, you'll need another data structure for storing the second-level sets (your circle shapes). If we had a good data structure for that purpose, why wouldn't we use it for all the words, and skip your data structure? Conversely, if you use a poor data structure for that, then your data structure inherits the limitations of that data structure: for instance, if you store all the words in the circle in a linked list, then lookups will be slow as they might need to traverse the entire list.
> 7 votes

---
Tags: algorithms, data-structures, trees, binary-trees, strings
---


# Question
Title: Randomized algorithm for 2kCNF satisfiability problem
> The problem: Let a formula in $\varphi\in 2kCNF$ where there's an assignment $\alpha$ such that for every clause, $l$ in $\varphi$, $\alpha$ satisfies at least $k$ literals of $l$. Suggest a randomized algorithm for finding a satisfying assignment for such $\varphi$.

So basically I've read about the $WALKSAT$ algoritm which starts with some random assignment, $\alpha\_1$ and for every iteration chooses randomly an unsatisfied clause, $l$ of $\varphi(\alpha)$ and a literal of $l$. Then, it flips this literal in $\alpha\_1$, getting a new assignment, $\alpha\_2$.

We repeat this process within a time bound $t$ or until a satisfying assignment has been found.

I've understood that this algorithm could be suitable here. I need to show that there's a probability of $\frac{1}{2}$ finding a satisfying assignment (probably after amplification)

I think we should look at the hamming distance of $\alpha, \alpha^t$ where $\alpha$ is the assignment as described in the question and $\alpha^t$ is unsatisfying assignment after $t$ iterations.

I'd be glad if you could guide from this point.

Thanks!

# Answer
> 2 votes
The analysis of Schöning's algorithm (see for example these CMU lecture notes) relies on the fact that if $\alpha$ is a satisfying assignment, $\beta$ is any assignment, and $C$ is an unsatisfied $k$-clause, then flipping a random variable decreases the distance between $\beta$ and $\alpha$ with probability at least $1/k$. In your case, you can get a better guarantee since $\alpha$ satisfies half the literals in every clause.

---
Tags: algorithms, satisfiability, randomized-algorithms, random-walks
---


title: Why isn't coNP = NP?

text:
# Question
Title: Why isn't coNP = NP?
I am having trouble understanding the class $coNP$. We defined

$$coNP = \left\\{ \overline{A} : A \in NP \right\\}$$

As far as I know, a language $A$ is in $NP$ if, and only if, a non-deterministic turing machine $M$ exists, which outputs $1$ if $w \in A$ and $0$ if $w \notin A$. But if this is true, then a turing machine $M'$ must exist which simulates $M$ and inverts the output:

$$M' = \begin{cases}0 \text{ if } M = 1\\1 \text{ if } M = 0\end{cases}$$

Therefore, $w \in A \implies w \notin L(M')$ and $w \notin A \implies w \in L(M')$, meaning that $L(M') = \overline{L(M)}$.

As $M'$ works in non-deterministic polynomial time, $L(M') \in NP$, and as $L(M') = \overline{L(M)}$, $\overline{L(M)} \in NP$, but $\overline{L(M)} \in coNP$ as well. As this holds true for all languages in $NP$, why isn't $coNP = NP$?

# Answer
> 2 votes
A problem in NP can be solved quickly if the answer is YES. Your inverted Turing machine finds the answer quickly if the answer to the original question is YES and the answer to the inverted question is NO. You need an answer quickly if the answer to the inverted question is YES and to the original is NO, and you don't have that.

Edit: Take for example the "Travelling Salesman" problem. I give you a list of cities to visit and ask you "is there a tour to visit them all that is at most 957 miles"? If the answer is YES then there is such a tour, so all your nondeterministic TM has to do is take such a tour and verify in polynomial time that it is indeed 957 miles or shorter. You only need to check one tour (the right one) to prove the answer is YES. If the answer is NO then you have to check all possible tours and see that none is short enough. Proving the answer is NO is a lot, lot harder.

---
Tags: complexity-theory, time-complexity, np, co-np
---