# Question
Title: How to do a reverse topological sort using depth first search?
I'm doing a replacement for the venerable `make` utility that will support, among other things, automatic cleaning. The utility figures out automatically what files and directories are targets, and then deletes those, if the user wishes to do a clean operation. However, a file may reside in an automatically created directory, meaning I should do a topological sort for the targets, where every file has an arc towards the parent directory, and every directory has an arc towards its parent. So, for example:

* `objhierarchy/obj/foo.o` has an arc towards `objhierarchy/obj`
* `objhierarchy/obj` has an arc towards `objhierarchy`

What complicates the things is that the files need to be deleted in the reverse order. So, in the example given, you need this order: (1) `objhierarchy/obj/foo.o`, (2) `objhierarchy/obj`, (3) `objhierarchy`.

Topological sort seems like a good solution, but it gives the opposite order. So, a topological sort of the directory parent graph would yield (1) `objhierarchy`, (2) `objhierarchy/obj`, (3) `objhierarchy/obj/foo.o`.

A solution could be a buffer of pointers that is reversed in-place (or just iterated in the reverse order), but I would like to avoid allocating extra memory.

What is the best way to get the files deleted in the reverse order? Can the topological sort algorithm based on depth first search be modified to call some callback function in a reverse order?

# Answer
> 1 votes
In order to get the files in the desired order, simply follow the following rule: A node can be deleted iff all of its children have been deleted. This is the same as a postorder traversal of a tree.

Let's say you use a container $S$ for your search structure (stack for DFS or queue for BFS). Now, we create a stack $T$ which will in the end will be the files to be deleted in order (starting from the top of the stack). Due to the nature of DFS/BFS on trees, every node will be pushed to and popped from $S$ before its children. Therefore, every time we pop a node from $S$, we add it to the stack $T$. At the end of the search $T$ will maintain the property that all nodes appear deeper in the stack than their children. Keep in mind this only works if the file node structure is a tree not a DAG.

# Answer
> 0 votes
I'm not sure about the algorithm modification to directly call the callback function in a reverse order, but I found a way to do this without extra memory allocation.

My solution is to embed a doubly linked list node within the data structure storing rules. (It actually turns out there was already a linked list node in the data structure I used for other purposes, and I have the ability to reuse this existing linked list node because the two linked lists are disjoint!)

In some cases, linked lists require extra memory allocation, namely if you want to have the ability to store an object into more than 1 linked list at the same time. However, if you only need to ability to store the object into 1 linked list, you can embed the linked list node within the object itself.

Then, the embedded linked list nodes are used to construct a linked list of all files/directories that need removal using the standard topological sort based on depth first search. When a depth first search finds a file/directory to be removed, it is added to the linked list.

It is trivial to iterate a doubly linked list in whatever order: either the insertion order or the reverse of it.

Arguably, a singly linked list would work too, but I already had a doubly linked list node embedded within the data structure, so the "optimization" to use a singly linked list would not be an optimization in my case at all.

# Answer
> -1 votes
Why not *topological* sorting on the **reversed** graph?

---
Tags: sorting, trees, search-algorithms, topology
---


# Question
Title: Is there a "recommended" way to choose the neighbours in a local search algorithm?
For my programming project I need to implement a local search algorithm. The generic local search algorithm is easy to understand but the thing I am most struggling with is how to deal with the neighbourhood.

It seems that when you implement such an algorithm, you don't explicitly state the neighbourhood but you declare a neighbourhood relation which tells you what you are allowed to modify in your present solution to get a "neighbour" or how two neighbours differ.

So lets say I have such a neighbourhood relation and a starting solution. What I first thought about was to make this purely random. Take the starting solution S. I would then call something like neighbour(S) which randomly chooses a neighbour and then you would start comparing...

How common is it to choose the neighbour systematically? I thought about the option to choose my neighbour systematically but so I had somehow to keep track about the neighbours I already visited which seemed more complicated than to just choose them randomly. What is your opinion on that?

# Answer
I expect choosing a single neighbor systematically will work poorly. Typical local search algorithms either look at multiple neighbors and choose the best (in which case you need more than one...) or repeatedly choose a random neighbor and decide whether to move there or stay where you are (in which case if you always choose the same neighbor, then you will quickly get stuck at a local optimum). But you can do anything that works.
> 1 votes

---
Tags: algorithms
---


# Question
Title: If NP is not a proper subset of coNP, why does NP not equal coNP?
I am studying some lecture notes on the complexity of algorithms.
The notes give a proof that NP is not a proper subset of coNP.
However, they still assert that NP is a subset of coNP (which I agree with).
So, in this case, why does it not follow that NP is equal to coNP?

# Answer
> 7 votes
$\\{2,3\\}$ is not a proper subset of $\\{3,4\\}$, yet the two clearly are not equal.

Comparing sets is not like comparing numbers: two sets might not be comparable.

Additionally, NP is not a subset of coNP, or at least, it is not known that this is the case. You are either misreading the textbook, or your textbook is wrong, since proving that $NP \subseteq coNP$ would be a massive result.

$P\subseteq coNP$, perhaps that is what you actually read?

# Answer
> 0 votes
NP is not the subset of co-NP unless we assume A be an NP-Complete problem and A∈ co-NP (which is not possible) then we can say all NP problems are a subset of co-NP problems since we can reduce all NP problems to problem A which is NP-complete it follows that for every problem in NP, we can construct a non-deterministic Turing machine that decides its complement in polynomial time; i.e., NP ⊆ co-NP. From this, it follows that the set of complements of the problems in NP is a subset of the set of complements of the problems in co-NP.

More information can be found Here

---
Tags: complexity-theory, np, complexity-classes
---


# Question
Title: Current state of polynomial-space exact graph coloring
The fastest algorithm I could find that finds the chromatic number of an undirected simple graph exactly in only polynomial-space is "Faster Graph Coloring in Polynomial Space" by Gaspers and Lee (DOI: 10.1007/978-3-319-62389-4\_31). It's running time is $O(2.2356^n)$.

However that's from 2016/2017, so I'm wondering whether there are any new relevant developments.

The mentioned algorithm is based on a procedure for counting the number of independent sets of a graph, meaning that new developments in that area are possibly relevant, too.

# Answer
The way to tell whether there are any new developments is to look up that paper on Google Scholar, find all newer papers that cite it, and check each to see whether it reports a better result. Anyone who has an improvement will surely cite that paper.
> 1 votes

---
Tags: graphs, colorings
---


# Question
Title: What is the maximal length of a CNF formula?
The question is quite short. Let $k$ be a given number. What is the maximal length of $k$-CNF formulae can we compute, over the set of binary variables $\left\\{ x\_1 ,\ldots, x\_n \right\\}$?

The way I see it, if we ignore the $k$ for a minute, we have $2^n$ different binary sequences, each sequence is a $1-1$ representation of a clause over $n$ variables.

This means that we already have $2^n$ different clauses, so the maximal length of a clause is $2^n$.

In here, we assumed each variable must either appear as $x\_i$ or as its negation. And we didn't count the instances in which a variable does not appear and the length of a clause is less than $n$. So it might actually be $3^n$...

This is a huge number...

But what happens when we consider the size of each clause has (ver1: at most, ver2: exactly) $k$ literals?

I tried going at it in the following way:

Lets look at $2n$ possible literals...

We need to choose $k$ of them. So its $\left( \frac{2n}{k}\right)$ different possibilities (I meant $2n$ over $k$, not division...).

This is $\frac{(2n-k+1) \cdot \ldots \cdot 2n}{k!}$

And I'm at loss how to continue from here.

Also, looks like the answers I get are not the same (if, for example, $k=n$).

**Clarification:** I provide 2 definitions for $k$-CNF formula, and I am interested in both possibilities (versions). For both, a literal cannot appear more than once in the same clause and if a literal appears, its negation cannot appear (or we might as well remove this clause all together). Additionally, if a clause appeared, it won't appear again (orelse, there is no actual limit on the length of a formula). In the first version, a clause has exactly $k$ literals. In the second, at most $k$ literals.

# Answer
For the version where every clause must have exactly $k$ literals:

There are ${n \choose k} 2^n$ possible clauses. (Why? Because you must choose exactly $k$ of the variables to appear in the clause, and then for each variable, you choose whether it appears negated or not.) A formula is obtained by choosing some subset of those possible clauses. So, the total number of possible formulas is

$$2^{{n \choose k} 2^n}.$$

---

For the version where every clause must have exactly $k$ literals:

By similar reasoning, the number of possible clauses is given by

$$c = \sum\_{i=0}^k {n \choose i} 2^i.$$

It follows that there are exactly $2^c$ possible formulas.
> 1 votes

---
Tags: combinatorics, satisfiability, 3-sat, constraint-satisfaction, word-combinatorics
---


# Question
Title: Algorithm for finding subsets subject to union condition
I'm a mathematician and the following came up in my research:

> Fix some positive integers $a\_0,...,a\_n$ and $N$.
>
> Consider subsets $A\_i \subset \\{0,...,N\\}$ where $|A\_i|=a\_i$, subject to some fixed conditions of the form: $A\_{i\_0}=A\_{j\_0}\sqcup A\_{j\_1}\sqcup ... \sqcup A\_{j\_t}$. (See an example below).
>
> I want to code an algorithm that takes the values $a\_1,...,a\_n$, $N$ and the conditions $(i\_0, \\{j\_0,...,j\_t\\})$, and returns all possible values for the subsets $A\_1,...,A\_n$.

To be clear, the condition means that $A\_{i\_0}$ is the union of $A\_{j\_0},...,A\_{j\_t}$ and $A\_{j\_k}\cap A\_{j\_{k'}}=\emptyset$ for all sets in the RHS.

What's a good way to go about this?

---

**Example**: Take $N=1$ and $a\_0=a\_1=a\_3=a\_4=1$ and $a\_2=2$, subject to: $A\_2=A\_0\sqcup A\_1$, $A\_2=A\_3\sqcup A\_4$. There are exactly 4 such families of subsets:

* $A\_0=A\_3=\\{0\\}$, $A\_1=A\_4=\\{1\\}$, $A\_2=\\{0,1\\}$
* $A\_0=A\_4=\\{0\\}$, $A\_1=A\_3=\\{1\\}$, $A\_2=\\{0,1\\}$
* $A\_1=A\_3=\\{0\\}$, $A\_0=A\_4=\\{1\\}$, $A\_2=\\{0,1\\}$
* $A\_1 =A\_4=\\{0\\}$, $A\_0=A\_3=\\{1\\}$, $A\_2=\\{0,1\\}$

Notes: I suspect the answer is some sort of recursive function, but I haven't been able to do this by myself. I also suspect this can be translated into a graph coloring problem. Incidentally, here is the (as of yet unanswered) math version of this question

# Answer
> 2 votes
Given your comments that the numbers involved here are all fairly small, I recommend you use a SAT solver. There is a straightforward encoding: introduce boolean variables $x\_{i,\ell}$, with the intended meaning that $x\_{i,\ell}$ is true iff $\ell \in A\_i$. Then all of your constraints can be translated into CNF clauses, and you can search for a satisfying assignment to the resulting CNF formula using a SAT solver.

The trickiest part will be the cardinality constraints (that $|A\_i|=a\_i$). That can be encoded using standard methods (see, e.g., Reduce the following problem to SAT, Encoding 1-out-of-n constraint for SAT solvers). In practice, your life will be easier if you use Z3, which provides a convenient front-end to SAT solvers. Z3 supports cardinality constraints natively (see, e.g., https://stackoverflow.com/q/43081929/781723).

Any time you find yourself doing something like recursive search with backtracking etc., consider a SAT solver. At its core, that is more or less what a SAT solver is doing, but folks have worked out powerful and sophisticated methods for doing that intelligently.

---

Another approach would be to use an integer linear programming (ILP) solver. In particular, introduce zero-or-one variables $x\_{i,\ell}$, with the intended meaning that $x\_{i,\ell}=1$ iff $\ell \in A\_i$ (the same encoding as above). Now, each constraint can be encoded into a linear inequality. Then, try to solve the resulting problem with an off-the-shelf ILP solver, such as Cplex or Gurobi.

The encoding into ILP is in some sense "simpler" than the encoding into SAT (in particular, the cardinality constraints can be encoded directly in a natural way), so it's possible this might work better.

---
Tags: algorithms, graphs, enumeration
---


# Question
Title: single algorithm to work on both directed and undirected graph to detect cycles?
I have been trying to implement an algorithm to detect cycles (probably how many of them) in a `directed and undirected graph`. That is the code should apply for both directed and undirected graphs.

Using `DFS or topological sort` is mostly recommended in various posts. But largely, everything is addressed for undirected graph.

This link describes one approach for cycle detection. To my understanding this works for directed graphs.

This link has the code for cycle detection in undirected graphs. but I fail to understand how it ignores the back edge. That is it must ignore any cycles with two nodes, say D to C and C to D. which means it must remember it parent as the DFS recurses. But the code does not seem take care of that.

Any suggestions welcome..

# Answer
> 2 votes
For a Directed Graph - we keep track of the recursion stack. For an edge (u,v), if we currently are processing u, and we see that v is in the recursion stack, then we have a Cycle.

For Undirected Graph - we look construct a parent array while we are traversing with DFS. Similar situation, for an edge (u,v) while processing u, if we see that v is Visited && not the parent of u, then we have a cycle.

I hope this helps!

# Answer
> 1 votes
Take a look at the answers for finding all cycles in graph.

You can transform undirected graph into a directed graph quite easily: for every edge (u,v) in your original graph G, put two edges (u --\> v) and (v --\> u) into your new directed graph T. Apply any of the algorithms that find cycles in a directed graph on T. However, notice that any undirected edge transforms into a directed cycle (u - v - u), so if your original graph was initially undirected, you can ignore cycles of length 2 at the end.

---
Tags: algorithms, graphs, recursion
---


# Question
Title: Describing the language of this Automaton
I am trying to describe the above automaton in English. The pattern that I can see is that it accepts any input that starts with $1$ or $0$ with an exact one occurrence of $00$ and ends with 1 or 10. How can I also phrase that it also may end with 00?

# Answer
> 2 votes
The automaton accepts exactly the strings that contain exactly one occurrence of $00$ as a substring.

---

The above is the simplest description of the automaton in English. Note that $00$ substring can be at the very beginning of a string or at the very end of a string.

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


# Question
Title: Best-known complexity for $l \times m$ by $m \times n$ matrix multiplication?
I know that the fastest known algorithm for multiplying two $m \times m$ matrices runs in time $m^{\omega}$, where currently we have $\omega = 2.3728596$ due to Virginia Williams's latest result (see here and here). But I'm not sure how this translates to matrices with other dimensions.

In terms of $\omega$, $l$, $m$, and $n$, what is the fastest known algorithm for multiplying an $l \times m$ and $m \times n$ matrix?

---

**Notes:**

* If $l \> m$ and $n \> m$ I think it would just be $O(lnm^{\omega - 2})$. But I'm not sure about when $l \< m$ or other such cases.
* Yuval Filmus's answer points to *Improved Rectangular Matrix Multiplication using Powers of the Coppersmith-Winograd Tensor,* Le Gall and Urrutia 2017. But it is difficult for me to extract a precise idea of how these results translate to $l \times m$ by $m \times n$. I think there is some implicit knowledge involved in the easy cases and hard cases of multiplying an $n \times n^\alpha$ and $n^\alpha \times n$ matrix.
* Coppersmith 1982, *Rapid Multiplication of Rectangular Matrices,* appears to be the seminal reference, where the quantity I am interested in is called `Rank<K,M,N>`, but does not provide a derivation of it.
* The important basic fact that these references show is that multiplying an $n \times n^\alpha$ and $n^\alpha \times n$ matrix takes approximately $\tilde{O}(n^2)$ time (less than $n^{2 + \epsilon}$ for any $\epsilon$) for sufficiently small $\alpha$, approximately $0.313$ or less, currently. I expect that going from this to $l \times m$ and $m \times n$ is more or less direct or well-known, but this is not my area and the complexity for $l \times m$ and $m \times n$ is not stated directly.

# Answer
More "down to earth" fast matrix multiplication algorithms are described at this url. If you know better ones for these matrix sizes (all up to 32x23), their definitions is welcome.
> 3 votes

# Answer
Le Gall improved over Williams' result, and Alman and Williams improved over his result. The latter is currently the state of the art for multiplying two square matrices.

The best known algorithms for multiplying an $n \times n^\alpha$ by an $n^\alpha \times n$ matrix ("rectangular matrix multiplication") can be found in Le Gall and Urrutia.

If your dimensions are any different, try to reduce your problem to one of the above. For example, let $t = \min(l,m,n)$. You can think of your problem as that of multiplying an $l/t \times m/t$ matrix with an $m/t \times n/t$ matrix, both of them having $t \times t$ entries. The corresponding complexity is $lmn t^{\omega-3+o(1)}$ (recall that $\omega$ is an infimum!), which is roughly $lmn/t$ if $\omega = 2$. If you only want to assume currently known bounds on $\omega$, you could get better bounds in some cases using rectangular matrix multiplication.
> 2 votes

---
Tags: algorithms, matrices, matrix-multiplication
---


# Question
Title: Can anyone solve this? Is the answer 4 or 7. I'm confused
I'm trying to solve this but I'm confused with different answers. I'm getting 4 but the answer written is 7. Please guide me.

# Answer
> 1 votes
It's 4 because you're allowed to "wrap around" from the top edge to the bottom edge or from the right edge to the left edge (those moves still represent 1-bit changes because the Gray code is cyclic).

So there is one PI of *3* minterms in the first column, one in the fourth column, one in the third row, and one of 2 minterms in the second row.

---
Tags: boolean-algebra, karnaugh-map
---


# Question
Title: Fastest way to find optimal graph coloring in polynomial space given chromatic number
Suppose I have a graph's chromatic number. Give a faster-than-brute-force polynomial-space algorithm for finding an optimal coloring.

If such an algorithm isn't known, please tell me so.

This question is not a duplicate, contrary to what the title may suggest: Using the chromatic number to compute an optimal coloring

This is not a homework question, I just want to write a program finding optimal colorings.

# Answer
Probably no theoretical algorithm "faster than brute-force" will be as good as using a SAT solver in practice. If you know the chromatic number already, it suffices to solve a single instance of SAT to find the coloring. Moreover, since you know the instance is always satisfiable, you can also try local search solvers such as Sparrow.

The SAT encoding of k-colorability of straightforward. In my experience the obvious encoding works fine for many instances. Of course, there are multiple ways of encoding the problem some of which can work better for certain instances, but it's hard to know without trying them out. A good symmetry breaking technique which will also speed up things nicely is to find a clique (as large as possible - for sparse graphs there are extremely good practical solvers like pmc), forcing it to have distinct colors, and then feeding that instance to the SAT solver.

I helped implement this very approach to the IGraphM Mathematica library and it works quite nicely.
> 2 votes

---
Tags: graphs, np-hard, colorings
---


title: decomposition to BCNF

text:
# Question
Title: decomposition to BCNF
Given $R$=($A,B,C,D,E,G$), And $F\_c$={$A$$\rightarrow$$E$ ,$E$$\rightarrow$$ACD$ ,$BD$$\rightarrow$$E$, $CD$$\rightarrow$$B$}

> Candidate keys are: $GA, GE, GDB, GCD$

Lets say I pick the FD $A$$\rightarrow$$E$ that violates **BCNF**
(1) should the decomposition looks like that:

> $R\_2$=$(A,G)$, $R\_1$=$(A,E,C,D,B)$ // \[$R\_1$ is created by $A$ and due to $E$$\rightarrow$$ACD$ and $CD$$\rightarrow$$B$ \]

(2) or perhaps like that:

> $R\_1$=$(A,E)$, $R\_2$=$(A,B,C,D,G)$

I am struglling to realize which decomposition is correct cause according to the algorithm you should take the FD $X$$\rightarrow$$Y$ that violates the BCNF and decomposite it to relations such that $R\_1$=$XY$ and $R\_2$=$R-Y$

# Answer
> 1 votes
The first is the correct decomposition since from X -\> Y one should decompose R in X+, the closure of X (that is AECDB) and T - (X+ - X) (that is AG), where T is the set of all the attributes.

---
Tags: database-theory, normal-forms, decomposition
---


# Question
Title: About a possible optimized version of Johnson's algorithm on a DAG with "elementary circuits"
Recently I came upon the Johnson's algorithm to find "elementary circuits" on a directed graph, which is really cool to me. I'm just implementing it from scratch in C++ following the original Johnson's paper

I have a couple of doubts before going on.

In the paper it's clear to me what $A\_k$ about adjacency, but in the pseudocode I see at a certain point $V\_k$, which seems to me a TYPO, since probably the $A\_k$ should be used instead.

Also, it's clear to me the mechanism to find the "s" vertex and remove it from the $A\_k$ to reloop on it with the s+1 vertex.

However it's not clear to me why he needs to find the minimum s from each SCC.

In my code a SCC is represented as a unordered\_setm since not in need to have them sorted.

So let's imagine to have a DAG with 50 nodes, and running the Tarjan on it to find SCCs with more than one vertex in them.

In my case this could give a couple of SCCs, let's say:

$${50, 12, 8, 40}$$ and $${4, 3, 20}$$

First of all, I'm wondering why the algo is taking into account also SCCs with 1 node only, since they cannot contain any "elementary circuits", but the self-loops, eventually.

So I was wondering if I could modifiy the algo like this: instead of using an incremental s from 1 to N, why not taking each SCC and pick the entries as they come, i.e. running:

CIRCUIT(50)

then removing 50 from the $A\_k$, rebuilding a SCC subgraph from it and re-running:

CIRCUIT(12)

then removing 12 and running

CIRCUIT(8)

and so on and so forth.

Actually I'm probably understimating the problem, but it seems to me we could keep only the "meaningful" SCCs with nNodes \> 1 and go linearly on the SCCs, without getting the min Vertex index from them.

Actually I'm applying this possible optimization on a DAG, but it could work for any generic directed graph indeed, I mean:

running Tarjan and keeping ONLY the SCCs with more than 1 node in it

for each SCC, pick the s linearly from the SCC as they come, without worrying about to get the Min s from each of them. Of course, the algo would still remove the s from the SCC subgraph incrementally, to exhaust each SCC as doing in the original paper.

Am I right in claiming that?

Thanks in advance

# Answer
While implementing Johnson's algo, I think to have figure out by myself why he's exctracting the min node Id from the SCCs, during the pipeline. Basically, Johnson's algo is:

1. initing a StartIndex "s" to 1, since assuming all nodes range from 1 to N
2. extracting a subgraph from the main graph induced by node Ids (s, s+1, ..., N) this means the extracted subgraoh will have nodes Ids \>=s, discarding the previous ones.
3. running Tarjan on this subgraph and finding all SCCs from this subgraph
4. finding the min Node Id between all these SCCs and assigning it to s.
5. cleaning internal data (blocked etc)
6. running the CIRCUIT on the s node
7. increasing s by 1, where s is meant to be a node Id, here

Basically, what I have understood is getting the min Id from the SCCs simply let the found circuits to come in their first node Id increasing order. There's no other reason for that, I mean in order to have a "good" enumeration in increasing order.

A possible other solution could be:

1. instead of using s as a node Id to extract the subgraph, simply loop on the internal graph nodes, one by one. So the second graph will start from the second node discarding the first one, etc.
2. build the SCCs on this subgraph as above
3. instead of finding the min Node Id among the SCCs, simply take the first node of the first SCC, assigning it to s.
4. cleaning stuff and running CIRCUIT(s)
5. loop back without the need to increase s, since point 1) is working incrementally on internal nodes, one by one.

Of course this solution will give scrambled circuits, not in increasing order. The only benefit I could see here is to avoid to find the min node Id, saving a bit of time in the algo.

However, finding the minimum between a list of Ids is not taking too much for sure, and complete in a negligible time.

So, all in all, I've decided to keep the original Johnson's approach which gives back the circuits in a elegant and visually appealing increasing order.

The only thing I've changed a bit is the usage of the blocked and blocked set, which I turned to:

1. unordered\_set for the blocked nodes, instead of plain bool arrays, saving a bit of memory
2. unordered\_map\<nodeIdx, vector\> representing the blocked chain to be used in the UNBLOCK f(), instead of plain list of vector, saving a bit of memory as well.

I will run build complete graphs up to N=10 and see if my results will match Johnson's paper in the number of found circuits, now, focusing on the performances as well.

A particular care has to be taken between internal node Idx Vs node Ids management. Node Ids are fundamental to be able to re-find the same node within the CIRCUIT to navigate the neighbors of a node in the subgraph. So you basically have to find the node Id of the node fed to the CIRCUIT and match the corresponding one in the subgraph, by the same Id. This is because the subgraph will have LESS nodes than the original graph, and so the Node idx will not make sense in the second subgraph list. However, when found a neighbor, you will have to find back the original graph node idx matching the same Id as well, of course. This is a solution where you refer the internal objects to the original graph node idx domain, no matter the subgraph you are using, and it could sound a bit trickier. However, since the original paper uses $V\_k$ as vertex index set inside $A\_k$, it's probably better to work directly in the subgraph subidx domain everywhere. I will probably change my current implementation and use this second approach, to avoid to do too many "Id finding" in the CIRCUIT f(). Notice, doing like that, the algo is more robust since does not assume the original graph has uniformly distributed node Ids, but could contain holes in them, like in my case (I mean the node Ids can be {1, 5, 8, 10}, without being uniform and admitting holes).

To sum up: if the circuits order is not important for you, you can use the second solution, saving a bit of time, even if it will not impact the final performances.
> 0 votes

---
Tags: graphs
---


# Question
Title: Best starter resources for learning about Reverse Engineering?
I would want to start learning reverse engineering (Software and Hardware Projects), but I don't know from where to start. Will be grateful for online resources and/or books. Thanks.

# Answer
One advice is that you don't "learn reverse engineering". You learn about engineering and reverse engineering knowledge comes by itself.

For example, if you take binary instructions encoding. You can read either the AMD or Intel developer's manuals and learn how instructions are encoded in binary for x86. Then it is easier to try and reverse engineer a binary executable because you know how instructions are encoded.

As to hardware, it is the same. If you want to, let's say, reverse engineer a PCI network card. First learn how a PCI device is designed then you can even start thinking of reverse engineering one.

Reverse engineering is learnt by just learning how things work in the proper direction. It just comes by itself once you know how things work. Maybe just writing an assembler would be a good starting point. Then, maybe you can start thinking of reverse engineering a binary. Even then, there are a lot of things to learn about high level language compilation and the layout of the binary in itself. Just learning about reverse engineering is quite impossible I would say.
> 1 votes

# Answer
Just want to share my research with community. I'm finding this list for useful. https://github.com/wtsxDev/reverse-engineering
> 0 votes

---
Tags: software-engineering
---


title: Is NL closed under complemenrt?

text:
# Question
Title: Is NL closed under complemenrt?
I am trying to understand if NL is closed under complement or not. By NL i mean the non-deterministic-logspace complexity. I suppose that the answer is linked to the fact that we don't even know if L = NL so scientifically speaking we cannot determinate if NL is closed or not on complement, for now. I've searched on the internet and wikipedia says that NL is closed on this operation but there is no demostration on that.

# Answer
> 3 votes
This is known as the Immerman–Szelepcsényi theorem, and the technique used to proving it is called *inductive counting*.

---
Tags: space-complexity, closure-properties
---


# Question
Title: How to find lightest path in directed weighted graph where each edge has a color
We're Given a directed graph $G = (V, E)$ and a weight function $\omega : E \rightarrow \mathbb{Z}$. Each edge is colored with one of these colors: Red, Green, Blue. Given two vertices $s,t \in V$, Find an efficient algorithm that gives the weight of the lightest path from $s$ to $t$ that satisfies these conditions:

1. If there is a green edge, then there must be a red edge that appeared before **the first** green edge in the path.
2. If there is a blue edge, then there must be a green and a red edge that appeared before **the first** blue edge in the path.

Note: it's possible that A path that satisfies these conditions doesn't have all colors in it. For example the lightest path from $s$ to $t$ with 7 red edges in it.

So I think that we must use the Bellman-Ford algorithm after editing $G$ or creating a new graph and using it on it.

# Answer
> 0 votes
Given $G=(V,E,w)$, the new graph you want to build is $H=(V', E', w')$ where:

* $V' = \\{\text{target}\\} \cup(V \times \\{r, g, b\\})$
* + $((v, r),(u, r))\in E'$ iff $(v,u)\in E$ is red.
    + $((v, r),(u, g))\in E'$ iff $(v,u)\in E$ is red.
    + $((v, g),(u, g))\in E'$ iff $(v,u)\in E$ is red or green.
    + $((v, g),(u, b))\in E'$ iff $(v,u)\in E$ is green.
    + $((v, b),(u, b))\in E'$ iff $(v,u)\in E$
    + $((t, .), \text{target}) \in E'$
* + For any $e' =( (u,\cdot), (v,\cdot) ) \in E'$, $w'(e') = w(u,v)$.
    + $w'(((t, .), \text{target})) = 0$

In plain words,

* $H$'s vertices are a special vertex, $\text{target}$ and three copies of original vertices, a copy in **r**ed, a copy in **g**reen and a copy in **b**lue.
* + An edge connects two red vertices iff the (corresponding) edge between the original (uncolored) vertices (exists and it) is red.
    + An edge goes from a red vertex to a green vertex iff the edge between the original vertices is red.
    + An edge connects two green vertices iff the edge between the original vertices is red or green.
    + An edge goes from a green vertex to a blue vertex iff the edge between the original vertices is green.
    + An edge connects two blue vertices iff the edge between the original vertices exists (and its color can be any color).
    + An edge that goes from each colored copy of $t$ to $\text{target}$.
* The weight of a new edge is the same as that of the edge between the original vertices, except the weight of each edge that connects to $\text{target}$ is $0$.

The construction of edges in $H$ ensures that

* from a red vertex, a red edge must be visited before we can reach a green vertex, and
* from a green vertex, a green edge must be visited before we can reach a blue vertex.

A path from $s$ to $t$ in $G$ that satisfies the conditions in the question corresponds to, edge by edge, some path from $(s, r)$ to $\text{target}$ in $H$ and vice versa. Since the weights on each pair of corresponding edges are the same except the edge to $\text{target}$, the weight of which is $0$, the weights of the two paths are the same as well. A valid cycle of negative weight in $H$ (here valid means that cycle can appear in a path satisfying the two conditions) corresponds to a negative cycle in $G$ and vice versa. A shortest path from $s$ to $t$ in $G$ corresponds to some shortest path from $(s,r)$ to $\text{target}$ in $H$ and vice versa.

Now we can apply the Bellman-Ford algorithm on $H$ with source $(s,r)$. The application will be able to detect whether there is a cycle of negative weight. If there is a negative cycle, there is also a valid negative cycle in $G$, and hence there will not be a shortest path. Otherwise, the application will tell the weight of the lightest path from $(s,r)$ to $\text{target}$ in $H$, which is what we wanted, the weight of the lightest path from $s$ to $t$ satisfying the two conditions.

---

If you know the basic theory on finite state machines, read How hard is finding the shortest path in a graph matching a given regular language? and its answer, where you can learn the general strategy.

---
Tags: algorithms, weighted-graphs, directed-graphs, path
---


# Question
Title: Find all integer points that lay in a 3-ball with a given radius
How can I efficiently find all lattice points in the cubic lattice $Z^3$ (that is to say, all integer points in a 3-space) that lay in a closed ball of radius $R$ centred at the origin?

Essentially,

Let $dist(p)$ be a function denoting the euclidean distance between a point in n-space and the origin point of that space, so $dist(p)=\sqrt{p\_1²+p\_2²+p\_3²\ldots p\_n²}$.
How might I efficiently iterate over $\\{p \in \mathrm{Z}^3\ | \ dist(p) \le R\\}$?

I'm aware that this is trivial to do in $\mathbb{O}(R^3)$ time by iterating over all lattice points that lay inside the minimum bounding box of the ball and filtering out every point $p$ where $dist(p) \> R$, and I'm also aware that this can be optimised by squaring both sides of the distance function, but this algorithm is still too slow for my needs.

# Answer
> 0 votes
One straightforward approach is to iterate over $x,y$ in the bounding box, then find $z\_\max$ so $(x,y,z)$ is in the sphere iff $|z| \le z\_\max$. You can find $z\_\max$ via the formula

$$z\_\max = \sqrt{R - x^2 - y^2}.$$

If you can compute squares and square roots in constant time, then the running time is proportional to the number of pixels in the ball, i.e., you iterate over $\frac43 \pi R^3$ points.

A similar but slightly better algorithm is to iterate over $x,y$ in the bounding box, then iterate over increasing values of $z$ (i.e., $z=0,1,2,\dots$) until $z^2 \> R - x^2 - y^2$. This is a little more efficient, because it doesn't require computing square roots, and because you can use the identity

$$(z+1)^2 = z^2 + 2z + 1$$

to avoid the need to compute squares in the inner loop either, instead updating the value of $z^2$ in each iteration. (Make sure to add in the negative values of $z$ too.)

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


title: Proving that a class equals NP ∩ coNP

text:
# Question
Title: Proving that a class equals NP ∩ coNP
We say that a non-deterministic Turing machine is nice if for every input x the following holds:
• Every computation path returns either ’accept’, ’reject’ or ’quit’.
• There is at least one non-quit path.
• All non-quit paths have the same value.
Let NICE be the class of all languages L that are accepted by some nice non-deterministic, polynomial time, Truing machine.
Prove that NICE = NP ∩ coNP.

Could you please explain the process of proving that a class is equal to NP ∩ coNP?

# Answer
> 1 votes
Regarding your answer, here are some corrections. For part (1), your argument is partially correct but incorrectly stated. For part (2), your argument is not correct.

Your biggest mistake is in the way you describe nondeterministic Turing machines. Remember that a nondeterministic Turing machine does not magically have access to all possible paths at once -- instead, it nondeterministically picks a path, but at the end it can only follow the particular path it has chosen! So, for example, the language you used in 1.2 "the machine checks if any non-quit path exists" does not make sense.

Similarly, you cannot say this in 1.1: "The machine guesses all the possible paths for the given input." A nondeterministic machine cannot guess all possible paths. It can guess one particular path and then inspect that path.

Instead, you can say this: "the machine guesses one particular path. If that path accepts, accept, otherwise reject."

This correction will also expose an error you made in step (2).

Finally, I suggest that in making this argument, you start by giving the "nice" machine a name, call it **N.** This will make the logic of the argument much clearer.

You do not need to check 1.3 because you know N is nice; you don't need to verify whether it's nice or not.

Instead, you need to prove that your construction accepts a string iff it is in the language L.

---

Here is a corrected form of your argument (1), incorporating the above. The corrections are in bold:

1. Let us construct an NP machine **M** for L that gets the input x. **Since we know L is accepted by a nice machine, let N be the nice machine for L.**

1.1 The machine **M** guesses **one particular path of N** for the given input.

1.2 **The machine M checks the result of N on this path: if it is accept, accept. If it is reject or quit, reject.**

1.3 **Let us argue why this construction is correct: first suppose $x \in L$. Then $N$ accepts $x$ on all non-quit paths, therefore $x$ is accepted by at least one path in M, so M accepts. Second, suppose $x \notin L$. Then all paths in M either quit or reject, therefore, all paths in M reject.**

---

For part (2), I recommend you start out by naming your variables N, M as in part (1). Then your goal is to define machine M given machine N.

# Answer
> 0 votes
Can I prove the first direction in the following way?

1. Let us construct an NP machine for L that gets the input x.
1.1 The machine guesses all the possible paths for the given input.
1.2 The machine checks if any non-quit path exists.
1.3 The machine checks whether the value of all the 'Accepts' and 'Rejects' paths are equal.
If both 1.2 and 1.3 are true, then the machine would accept. Otherwise, it would reject.
The machine is polytime because there are N paths =\> L∈.
2. Let us construct an NP machine for $\overline{L}$ that gets the input x.
2.1 The machine guesses the value of 'Accept'/'Reject' path T, so that its value will differ from the rest of the 'Accept'/'Reject' paths.
The machine found a T path successfully, then the machine would accept. Otherwise, the machine would reject.
=\> The machine accepts the language $\overline{L}$. The machine is polytime because there are N paths =\> $\overline{L}$∈.
We proved that L∈ and $\overline{L}$∈ hence L∈co.

# Answer
> 0 votes
Based on the review that I received, I fixed the second part of the proof. I would like to know if it's correct now, I would appreciate your input on this.

2. Let us construct an NP machine M for $\overline{L}$ that gets the input x. Since we know L is accepted by a nice machine, let N be the nice machine for L.

2.1. The machine M guesses one particular path of N for the given input.

2.2. The machine M checks the result of N on this path: if it is rejected or quit, accept. If it is accepted, reject.

2.3. Let us argue why this construction is correct: first suppose ∈$\overline{L}$. Then all paths in N either quit or reject. Therefore, all paths in M accept. Second, suppose ∉$\overline{L}$. Then accepts on all non-quit paths, therefore is rejected in M.

2.4. The machine M accepts the language $\overline{L}$.

2.5. The machine M is polytime because there are n paths =\> $\overline{L}$∈.

2.6. We proved that L∈ and $\overline{L}$∈ hence L∈co.

---
Tags: turing-machines, computability, np-complete, np
---


# Question
Title: $\{uuv\mid u\in\Sigma^+, v\in \Sigma^*\}$ and pumping lemma
As I am currently teaching regular languages and pumping lemma, I was searching for nice examples of languages, regular or not, for exercises.

* $L\_1 = \\{vv\mid v\in \Sigma^\*\\}$ is a classic example, as it can be proven to be non regular for $|\Sigma|\geqslant 2$ using the pumping lemma;
* $L\_2 = \\{ uvv\mid u,v\in\Sigma^\*\\}$ looks like $L\_1$, however it is a bit of a trap: since $L\_2 = \Sigma^\*$, it is regular;
* $L\_3 = \\{uvv\mid u\in\Sigma^\*, v\in\Sigma^+\\}$ looks like $L\_2$, however it is not regular if $|\Sigma| \geqslant 2$. This can be proven using the pumping lemma: suppose it is regular, and let $n$ be the pumping length. Let $u=a^nba^nb\in L\_3$ and $u = xyz$ a decomposition such that $|xy|\leqslant n$ and $|y| \> 0$. Then $xz = a^kba^nb$ with $k\< n$ and does not end with a (non empty) square, therefore is not in $L\_3$ which is not regular;

Things became a bit complicated with $L\_4 = \\{uuv\mid u\in \Sigma^+, v\in \Sigma^\*\\}$: after struggling a bit to find a counter-example word to the pumping lemma, I proved $L\_4$ to be non regular if $|\Sigma|\geqslant 2$, using the fact that $L\_3 = L\_4^R$ and that regular languages are closed under mirror image.

However, if $|\Sigma| = 2$, I found out that $L\_4$ verifies the conclusion of the pumping lemma, with a pumping length of $5$! Indeed, since any word of length $\geqslant 4$ contains a square, any word $u\in L\_4$ with $|u| \geqslant 5$ can be written $u = vwwu'$ with $|vww|\leqslant 5$ and $|v|,|w| \> 0$. Therefore $u = xyz$, with $x = \varepsilon$, $y = v$ and $z = wwu'$ verifying:

* $|xy| = |v| \< |vww| \leqslant 5$;
* $|y| = |v| \> 0$;
* for all $k \geqslant 0$, $xy^kz\in L\_4$. Indeed, $xz = z = wwu' \in L\_4$ (because $|w| \> 0$), $xyz = u \in L\_4$ (hypothesis) and if $k\>1$, $xy^kz = yyy^{k-2}z \in L\_4$ (because $|y| \> 0$).

I then tried to find a counter-example to the pumping lemma for $L\_4$ when $|\Sigma|\>2$, but without success. I found out that in order to not be able to apply the previous reasoning, in any counter-example, the first $n$ (pumping length) letters need to not contain a square, which is possible, but couldn't go further.

My questions are all related to this problem:

* I don't think I did, but maybe, did I make any mistake?
* Is there a counter-example word to the pumping lemma for $L\_4$ when $|\Sigma| \geqslant 3$?
* Do you know of any simpler language that is a counter-example to the converse of the pumping lemma (not regular but verifying the conclusion of the pumping lemma)? vonbrand proposed this one which is a tad bit complicated. I also know of $\\{ab^iab^jab^j\mid i,j\geqslant 0\\}\cup \\{uaav\mid u,v\in\Sigma^\*\\}$ which is not better.

# Answer
> 4 votes
When the alphabet is of size $4$ or more, it is easy to prove that $L\_4$ is not regular using the pumping lemma. Given a pumping length $n$, let $s$ be a square-free word over $\\{0,1,2\\}$ of length $n$; such a word exists since there is an *infinite* square-free word over $\\{0,1,2\\}$. We choose $w = 3s33s3 \in L\_4$. Suppose that we could write $v = xyz$ so that $|xy| \leq n$, $y \neq \epsilon$, and $xy^iz \in L\_4$ for all $i \geq 0$. In particular, $xz \in L\_4$. We consider two cases:

1. $x \neq \epsilon$. In this case, $xz = 3t 33s3$, where $t$ is a word over $\\{0,1,2\\}$ satisfying $0 \< |t| \< s$. If $xz$ started with a square $u^2$, then $u$ starts with a $3$, and so the second occurrence of $u$ must also start with a $3$. The second letter cannot be a $3$ (since $t$ doesn't start with $3$), hence $u = 3t3$, but since $|t| \< |s|$, the word $u^2$ is not a prefix of $xz$. Hence this case is impossible.
2. $x = \epsilon$. In this case, $xz = t33s3$, where $t$ is a non-empty suffix of $s$. Since $xz$ contains only three $3$s, if $xz$ starts with a square $u^2$, then either $u$ contains no $3$ or it contains a single $3$. It $u$ contains no $3$ then $u^2$ is a prefix of $t$, which is impossible since $s$ is square-free. If $u$ contains a single $3$ then $u = t3$, which is impossible since $t$ doesn't start with a $3$ whereas the second occurrence of $u$ does. Hence this case is also impossible.

---

In the ternary case, it suffices to find a collection or arbitrarily long square-free ternary words $w$ such that for any decomposition $w = xyz$ with $y \neq \epsilon$, we have $xy^i z \notin L\_4$ for some $i$. I conjecture that prefixes of the Leech word satisfy this condition (even if we restrict $i$ to be either $0$ or $2$).

Suppose that arbitrarily long words exist satisfying the above constraints. Given a pumping constant $n$, choose such a word $w\_k$ of length at least $n+2$ which starts and ends with the same letter $\sigma$, and let $w = w\_k \sigma w\_k \sigma \in L\_4$. (Note that since each word satisfying the constraints is square-free, every subword of length 5 contains all different letters; hence we can always truncate a long enough word to one which ends with the same letter with which it starts.)

Suppose that $w = xyz'$, where $y \neq \epsilon$ and $|xy| \leq n \leq |w\_k| - 2$. Then we can write $z' = z\sigma w\_k \sigma$, where $w\_k = xyz$; note that $|z| \geq 2$ and $z$ ends with $\sigma$.

According to the conjecture above, we can find $i \neq 1$ such that $xy^i z$ does not have a square prefix. If $xy^i z'$ does have a square prefix $u^2$, then $u^2$ must reach the first $\sigma$; in particular, $|u| \geq 2$.

If the first copy of $u$ doesn't reach the first $\sigma$ then then $u$ doesn't contain $\sigma^2$, but then its second copy contains both $\sigma$ and either the last letter of $z$ or the first letter of $w\_k$, and so does contain $\sigma^2$. Thus the first copy of $u$ does reach the first $\sigma$.

If the first copy of $u$ doesn't end at the first $\sigma$ then it contains $\sigma^3$. Since this is the unique copy of $\sigma^3$ in $w$, this is impossible. Hence $u = xy^iz\sigma$, and so $u$ is a prefix of $w\_k \sigma$. In particular, $i = 0$, since otherwise $|u| \> |w\_k \sigma|$. But then $u$ is a proper prefix of $w\_k \sigma$, implying that $w\_k$ contains a copy of $\sigma^2$, which is false.

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


# Question
Title: Calculating the number of ways to generate each number in $\left\{ n,\ldots,6n\right\} $ by throwing $n$ dice
**Question**

The convolution $a\*b=\left(c\_{0},c\_{1},\ldots,c\_{n+m-2}\right)$ of two vectors $\left(a\_{0},\ldots,a\_{n-1}\right)$ and $\left(b\_{0},\ldots,b\_{m-1}\right)$ is defined as follows: $$ \left(a\*b\right)\_{i}=c\_{i}=\sum\_{j=0}^{i}a\_{j}b\_{i-j} $$

Given that by using the $FFT$ algorithm the convolution can be calculated in $O\left(n\log n\right)$, suggest an algorithm that calculates the number of ways to generate each number in $\left\\{ n,\ldots,6n\right\\} $ by throwing $n$ dice in $O\left(n\log n\right)$.

---

**My Take**

I tought on defining the following vectors: $$ V\_{A}\left\[i\right\]=V\_{B}\left\[i\right\]=\begin{cases} 1 & \text{i is a possible result for n dice throws}\\ 0 & \text{else} \end{cases} $$ For example, if n = 2 then: $$ V\_{A}=V\_{B}=\left\[\underbrace{0}\_{1},\underbrace{1}\_{2},\underbrace{1}\_{3},\underbrace{1}\_{4},\underbrace{1}\_{5},\underbrace{1}\_{6},\underbrace{1}\_{7},\underbrace{1}\_{8},\underbrace{1}\_{9},\underbrace{1}\_{10},\underbrace{1}\_{11},\underbrace{1}\_{12}\right\] $$ So the convolution would be: $$ c\_{i}=\sum\_{j=0}^{i}V\_{A}\left\[j\right\]V\_{B}\left\[i-j\right\] $$ when $c\_{i}$ contains the possible ways to get $i$ as the sum of $n$ throws.

For example: $$ c\_{2}=\underbrace{V\_{A}\left\[0\right\]V\_{B}\left\[2\right\]}\_{0}+\underbrace{V\_{A}\left\[1\right\]V\_{B}\left\[1\right\]}\_{1}+\underbrace{V\_{A}\left\[1\right\]V\_{B}\left\[0\right\]}\_{0}=1 $$ So there is only one way to get 2 as the sum of two dice throws.

Well, I think it works for $n=2$ but it gets complicated for $n\>2$, and I don't think it works in $O\left(n\log n\right)$ anymore.

When $n=3$ I will define: $$ V\_{A}=V\_{B}=\left\[\underbrace{0}\_{1},\underbrace{0}\_{2},\underbrace{1}\_{3},\underbrace{1}\_{4},\underbrace{1}\_{5},\underbrace{1}\_{6},\underbrace{1}\_{7},\ldots,\underbrace{1}\_{23},\underbrace{1}\_{24}\right\] $$

So for example: $$ c\_{8}=\underbrace{V\_{A}\left\[0\right\]V\_{B}\left\[8\right\]}\_{0}+\ldots+\underbrace{V\_{A}\left\[3\right\]V\_{B}\left\[5\right\]}\_{1}+\underbrace{V\_{A}\left\[4\right\]V\_{B}\left\[4\right\]}\_{1}+\underbrace{V\_{A}\left\[5\right\]V\_{B}\left\[3\right\]}\_{1}+\ldots+\underbrace{V\_{A}\left\[8\right\]V\_{B}\left\[0\right\]}\_{0}=3 $$

That is incorrect, because in this case I need to find the number of possible ways to get 3,4 and 5.

This is where I got stuck. I don't know if my idea is good and if it's possible to use it and stay at $O\left(n\log n\right)$. I think it gets recursive and complicated.

# Answer
> 1 votes
FFT allows you to multiply two degree $d$ polynomials in $O(d\log d)$.

In your case, you want to compute $(x+x^2+x^3+x^4+x^5+x^6)^n$. Using repeated squaring and FFT, you can compute this in $O(n\log n)$. The coefficient of $x^k$ gives you the number of ways to obtain $k$ by throwing $n$ dice.

---
Tags: algorithms
---


# Question
Title: Finding a point on the unit segment satisfying certain distance relations from $n$ points
Let $x\_1,x\_2,x\_3,\dots,x\_n$ be n points on the unit segment $\[0,1\]$.Mathematically it can be shown that there always exists a point $\in\[0,1\]$ such that $$ \frac1n \sum\_1^n|x-x\_i|=\frac12$$. Given $x\_1,x\_2,x\_3,\dots,x\_n$, how do we find(numerically) $x$ satisfying the above relation to given level of accuracy?In other words ,given $x\_1,x\_2,x\_3,\dots,x\_n$ and $\epsilon\>0$ ,the task is to find $x$ such that $$ \Bigg|{\frac1n \sum\_1^n|x-x\_i|-\frac12}\Bigg| \< \epsilon$$.Thank you for any hints/suggestions in advance.

# Answer
The function $f(x)= \sum\_{i=1}^n |x -x\_i|$ is a piecewise linear continuous function with angles at the points $x\_i$. Assuming the points are ordered, one can compute successively $f(0), f(x\_1),\cdots ,f(x\_n), f(1)$. It remains to see on which interval the function crosses the value $\frac{n}{2}$ and find the intersection point by interpolation on this interval.

The values of the function can be computed efficiently because one has \begin{equation} |x\_{k+1} - x\_i| - |x\_k - x\_i| = (x\_{k+1}- x\_k)(\[i\le k\]-\[i \> k\]) \end{equation} where $\[\]$ is Iverson's bracket. Hence \begin{equation} f(x\_{k+1}) - f({x\_k}) = (x\_{k+1}-x\_k)(k - (n-k)) = (x\_{k+1}-x\_k)(2k-n) \end{equation}

The above arguments also shows that $f(x\_k)$ decreases and reaches its minimum when $k = \lfloor\frac{n+1}{2}\rfloor$ then increases. The maximum of $f$ is reached at $x=0$ or $x=1$. In fact one has $f(0)+f(1) = n$, so the algorithm could start from $x=0$ or from $x=1$, depending of which value of $f$ is larger than $n/2$.
> 2 votes

---
Tags: algorithms
---


# Question
Title: Given a set $S =\{1,2,...,k\}$, how to generate variations of length $n, (k<n)$, such that each element of $S$ appears at least once?
Take, for example: $$S=\\{1,2,3\\}\to k=3$$ $$n=4$$ The desired output for this would be:

```
[1 1 2 3]
[1 1 3 2]
[1 2 1 3]
[1 2 2 3]
[1 2 3 1]
[1 2 3 2]
[1 2 3 3]
[1 3 1 2]
[1 3 2 1]
[1 3 2 2]
[1 3 2 3]
[1 3 3 2]
[2 1 1 3]
[2 1 2 3]
[2 1 3 1]
[2 1 3 2]
[2 1 3 3]
[2 2 1 3]
[2 2 3 1]
[2 3 1 1]
[2 3 1 2]
[2 3 1 3]
[2 3 2 1]
[2 3 3 1]
[3 1 1 2]
[3 1 2 1]
[3 1 2 2]
[3 1 2 3]
[3 1 3 2]
[3 2 1 1]
[3 2 1 2]
[3 2 1 3]
[3 2 2 1]
[3 2 3 1]
[3 3 1 2]
[3 3 2 1]

```

I managed to generate this by iterating through every variation and eliminating those which are missing an element from $S$. However, I need a much more efficient algorithm, without recursive calls if possible. Any ideas are appreciated.

# Answer
Run a recursive procedure which keeps track of which elements appeared so far. If there are $k$ elements which haven't appeared so far and only $k$ positions left, choose one of them.

With some care, you can convert the recursion to an iteration, if you so wish.
> 3 votes

---
Tags: algorithms, combinatorics
---


title: Addition in One's Complement

text:
# Question
Title: Addition in One's Complement
It is my belief that addition in one's complement is done the same way as unsigned addition except that if there is a carry out in the most significant bit then that carry is added to the last significant bit of the answer. If I am wrong about this, please tell me.

I am going to work in 4 bits. My claim is that $-1$ is $1110$ in one's compliment. Now, I want to add $-1$ to $-1$ in one's compliment. I should get $-2$ or $1101$. Here is my work:

```
 1110
+1110
-----
 1000
    1
 ----
 1001

```

In this case, we added the one because we had a carry out of the most significant bit. However, my answer is not $-2$. Where did I go wrong?

# Answer
> 0 votes
Something went wrong in the addition. 1110 + 1110 is not 1000 (with carry), but 1100 (with carry). This is hopefully obvious in retrospect, after all two times 1110 had better shift that number one place to the left, by definition.

1100 plus the end-around carry is 1101 which corresponds to -2.

---
Tags: computer-architecture, arithmetic
---


# Question
Title: Who said first "In practice, log log N is at most (single digit number)?"
In one of my undergrad theory or algorithms classes, I remember a professor sharing a quip that went something like

> In practice, $\log(\log(N))$ is at most 9.

...the idea being that even though the function $f(N) = \log(\log(N))$ technically grows without bound, it's tiny for any value of $N$ that's remotely plausible for nearly any real-world problem, so an $O(\log(\log(N))$ algorithm is effectively constant-time. For example, $\log\_2(\log\_2($number of particles in the universe$)) \approx 8$. (It's even smaller if you use base $e$ or base 10.)

Does anyone know who first (or most famously) said this?

Googling this with various parts in quotes turns up plenty of lecture notes and tutorials about big-O notation and how slowly $\log(N)$ and $\log(\log(N))$ grow, but so far the earliest example I've found is this lecture by Richard Borcherds in 2021, which is several years later than my memory of hearing it (and doesn't cite anyone else as the source of the remark).

# Answer
> 1 votes
I don't think this is some historical quote that was famously said by someone, or that needs to be attributed to someone who said it. It is just a mathematical fact. I imagine many people have made a similar observation.

Your question is a little like asking "Who said first that 2+2=4?" You'd probably give me a funny look if I asked that question.

See also Is there a meaningful difference between O(1) and O(log n)?, "For small values of n, O(n) can be treated as if it's O(1)", https://en.wikipedia.org/wiki/Ackermann\_function#Inverse (for a similar property of Ackerman's function), https://en.wikipedia.org/wiki/Iterated\_logarithm#Analysis\_of\_algorithms (for a similar fact about the iterated logarithm).

# Answer
> 0 votes
I said it, and many people said it. It’s obvious when n is the size of a problem: if you wanted to sort all bits on all of Google’s hard drives, that’s less than $2^{80}$ bits, log n \< 80, log log n \< 6.34.

It’s not quite correct when n is a number. For example in a search for Fermat primes, we look at numbers around $2^{70,000,000}$, log n ≈ 70,000,000, log log n \< 26.2.

Adding integers less than n takes O(log n), but in practice the time is constant for $n \< 2^{64}$.

---
Tags: time-complexity, big-o-notation, history
---


# Question
Title: What if solving P vs NP revealed a contradiction?
Let's just say that some person discovered that $P = NP$ implies $P \neq NP$ and $P \neq NP$ implies $P = NP$, and we don't know what is causing this contradiction, And this was a valid proof that was accepted. What would the consequences of this be? This would probably be the least likely outcome of the P vs NP question. But one I don't see talked about.

# Answer
> 1 votes
If P=NP implies P≠NP, then P≠NP (unconditionally).

Similarly, if P≠NP implies P=NP, then P=NP.

If both are true, then both P≠NP and P=NP, and so the axioms of mathematics are inconsistent. Most (but not all) mathematicians consider this quite unlikely.

# Answer
> 0 votes
If you have a proof that $(P=NP)\Leftrightarrow (P\not= NP) $ then $P=NP$ is proveable is equivalent to $P\not= NP$ is provable. This would mean that neither $P=NP$ nor $P\not= NP$ is provable.

But if there would be a proof, that $P=NP$ is not provable then it would be proven that one cannot find an efficient algorithm for SAT or any other $NP$-complete problem. This would mean that $P \not= NP$. So, if $P$ versus $NP$ is independent from math then this would not be provable, too.

---
Tags: complexity-theory, logic, p-vs-np
---


# Question
Title: What are some problems in EXPTIME not known to be EXPTIME-complete?
Not problems like chess. I'm thinking problems that would be very useful to be able to solve in sub-exponential time. These would be problems not known to be EXPTIME complete.

Edit I mean problems that are not known to be in NP and assuming $NP \neq EXP$, Problems that are thought in EXP but there could hypothetically be a deterministic polynomial time algorithm for

# Answer
> 2 votes
If the Polynomial Hierachy does not collapse then there are incomplete sets between $PH$ and $PSPACE$, see https://cstheory.stackexchange.com/questions/7639/is-there-a-pspace-intermediate-language/7640. These sets would be also incomplete in $EXP$, because $PSPACE \subseteq EXP$

# Answer
> 3 votes
Any $\mathsf{NP}$-complete problem is in $\mathsf{EXPTIME}$ and not known to be $\mathsf{EXPTIME}$-complete, since it is still unknown whether $\mathsf{NP} = \mathsf{EXPTIME}$ or not.

---
Tags: complexity-theory
---


# Question
Title: How can I calculate the maximum sum/product of sequence?
I am looking for an algorithm in $O(N^2)$ that finds the maximum value that be obtained from a sequence of real numbers greater than 0 (e.g. $\\{ 1, 2, 3 , 4\\}$) by inserting a plus ($+$) or multiplication ($\times$) between the elements.

Really not having much luck and wondering if anyone has any insight on this?

It must follow normal order of precedence.

For example with $\\{1,2,3,4\\}$, the maximum is $1+2\times3\times4 = 25$ not $1\times2\times3\times4 = 24$ and not $1\times2+3+4 = 9$.

# Answer
Let's say all numbers are positive (i.e. $\geq0$). Before and after $0$s you should always use $+$. This could also solved in $O(n^2)$ by first finding all zeros and then find maximum value for each group separated by zeros. Inside each group, for positive numbers, you should always use $\times$ except in $1$ cases, if ones are in the middle of a group, still you should choose $\times$. But when ones are at the very beginning or at the very end of the group, you should choose $+$.
> -1 votes

# Answer
By using dynamic programming, we can solve this! Negative values also work.

Let's start off with the subproblems. We would like to know $OPT(i,j)$, the maximum value of a consecutive subsequence from index $i$ to index $j$.

Then the recurrence equation looks like this:

$$ \begin{equation} OPT(i,j)=\begin{cases} v\_i & \text{if $i=j$,}\\ \max \\{ OPT(i,k) * OPT(k + 1,j), OPT(i,k) + OPT(k + 1,j) \mid i \le k \lt j \\} & \text{else}. \end{cases} \end{equation} $$ The base case takes care of returning the value at index $i$ itself. If $i \neq j$, we split the substring into two parts at index $k$. We either take the product of the maximum values of those two parts, or we take the sum of them.

Now for the original problem, we have $OPT(0, n-1)$.

The order is guaranteed, since the problem is split up into smaller subproblems from left to right, until no subproblem can be found.

The time complexity of this algorithm with memorization can at most be the time it takes per subproblem = $O(n)$, and the amount of times we call this, $O(n)$. So $T(n) = O(n^2)$.
> 1 votes

---
Tags: algorithms, optimization, arithmetic
---


# Question
Title: What's the complexity class of determing the halting problem of a finite memory Turing machine?
What's the complexity class of determining the halting problem of a finite memory Turing machine? What is the computational complexity class of determining whether a machine halts on any input if it is allowed to access no more than $n$ bits of memory.

I know this problem is decidable because due to the limited memory, if it runs for longer then $2^n$ it must be caught in a loop.

# Answer
Please see Reiner Czerwinski's answer; that is a better answer than mine.

---

I will assume the problem is as follows: given inputs $x,n,T$, where $x$ is an input word, $T$ is a Turing machine, and $n$ is a positive integer, determine whether $T$ accepts $x$ using at most $n$ bits of memory.

If so, the problem is PSPACE-hard. In other words, any PSPACE problem can be reduced to this problem. Consider any PSPACE problem. Since it is in PSPACE, there must be a Turing machine $T$ that solves the problem in polynomial space. Let $p$ be the polynomial, so that $T$ takes space at most $p(|x|)$ on input $x$, where $|x|$ is the length of $x$. Modify $T$ so that if $T$ accepts, it halts, and if $T$ rejects, it enters an infinite loop. This gives us a new Turing machine $T'$; notice that the space usage of $T'$ is the same as $T$ (and $T'$ has at most one more state than $T$). Now, if you have an algorithm for your problem, then you can use it to test whether $x$ is a yes-instance for the problem by running your algorithm on the input $x,T',p(|x|)$. So, if you could solve the halting problem for polynomial-space Turing machines, you could solve every PSPACE problem.

The problem is in PSPACE if $n$ is represented in unary. You can test whether such a machine halts in space polynomial in $n$ and the length of $x,T$, by running the Turing machine for $2^n |Q| n + 1$ steps, where $|Q|$ is the size of the finite control, and checking whether it halts. Why? Each configuration of the Turing machine is determined by the values on the tape, the state of the finite control, and the position of the head, so there are at most $2^n |Q| n$ such configurations; the rest follows by a pigeonhole argument.

If $n$ is represented in binary, then the problem is in EXPSPACE, by a similar argument.
> 3 votes

# Answer
The answer depends on the coding of $n$. The set $\\{(M,x,1^n) | \text{ TM } M \text{ accepts }x \text{ within } n \text{ tape space } \\}$ is $PSPACE$-complete. But the set $\\{(M,x,n) | \text{ TM } M \text{ accepts }x \text{ within } n \text{ tape space } \\}$ where $n$ is binary coded is $EXPSPACE$-complete.
> 1 votes

---
Tags: complexity-theory, turing-machines, time-complexity, complexity-classes, halting-problem
---


# Question
Title: What are some problems in EXP not known to be EXPTIME-Complete, but also do not have any known algorithm in NP?
These would be problems known to be in exp where there could hypothetically be a P or NP algorithm, but none have been discovered yet if one is possible.

# Answer
Assuming that $NP\not= PSPACE$ and $PSPACE \not= EXPTIME$, all $PSPACE$-complete problems are incomplete in $EXPTIME$
> 2 votes

# Answer
Any BQP-complete problem should suffice, since BQP is contained in EXPTIME but not believed to be contained in NP and not believed to be equal to EXPTIME.
> 3 votes

---
Tags: complexity-theory
---


# Question
Title: Whether and how to distinguish two kinds of $O(1)$ speedup
Here is a very bad algorithm that computes $4n$ for an integer input.

```
# Original algorithm
function fourtimes(n)
    two = 1 + 1
    res = 0

    for i in 1:n
        res += two
        res += two
    end

    return res
end

```

Here is one way of improving the algorithm (**speedup A**).

```
# Speedup A
function fourtimes(n)
    two = 2
    res = 0

    for i in 1:n
        res += two
        res += two
    end

    return res
end

```

Here is another way of improving the algorithm (**speedup B**).

```
# Speedup B
function fourtimes(n)
    four = 2 + 2
    res = 0

    for i in 1:n
        res += four
    end

    return res
end

```

The original algorithm is $O(n)$, and both **speedup A** and **speedup B** leave this overall complexity the same. Thus, I am inclined to call both of these $O(1)$-speedups.

On the other hand, for large $n$, **speedup A** is barely noticeable, whereas **speedup B** cuts the computation time in half. If the original algorithm takes $1n$ units of time to compute, then **speedup A** takes $1n - \epsilon$ units, whereas **speedup B** takes $\frac{1}{2}n$ units.

I am wondering if there is a way to express mathematically that **speedup B** is a more significant improvement than **speedup A** over the original algorithm—or is it?

If so, can the difference be expressed in big-O notation?

Would it be appropriate to abuse notation and call A an $O(0)$-speedup instead?

# Answer
> 2 votes
We can analyze the number of arithmetic operations as a function of $n$. Let us call the algorithms O (for "original"), A (for "speedup A") and B (for "speedup B").

Let us denote by $f\_X(n)$ the number of additions performed by algorithm X. We have that

* $f\_O(n) = 1 + 3n$,
* $f\_A(n) = 0 + 3n$, and
* $f\_B(n) = 1 + 2n$.

So the only improvement of A over O is that it avoids computing 1 + 1 by initializing `two` to 2 directly. On the other hand, B is even better as it does one operation less for each round of the loop.

This is a mathematically sound way of expressing that B gives us a more significant saving than A, which is what you wanted. So in particular, there is no need to express any of the $f\_X$ in terms of Big Oh. It's good to be as precise as possible whenever you can and it makes sense.

---
Tags: complexity-theory, big-o-notation
---


# Question
Title: Is subtype polymorphism a kind of ad hoc polymorphism?
> "Ad-hoc polymorphism is obtained when a function works, or appears to work, on several different types (which may not exhibit a common structure) and may behave in unrelated ways for each type." – Strachey 1967

Subtype polymorphism seems to fit this description, albeit usually with late binding on the type that dictates the function's behavior. In Java, for example, the `toString` function works on any object at all, but has many wholly distinct implementations which are distinguished from one another based on the runtime type of the object; i.e., any class can override it and create a new ad hoc definition.

But when I poke around online, I usually find people making a sharp distinction between subtype polymorphism and ad hoc polymorphism; they are treated as wholly different beasts. Would it be correct to say that subtype polymorphism is a kind of ad hoc polymorphism? If not, why not?

# Answer
Strachey's paper defines only two main classes of polymorphism. Subtyping is certainly not parametric polymorphism, so either subtyping *is* a form of the remaining class or Strachey's terms are not as comprehensive as he thought.

Strachey distinguished between **parametric** polymorphism, where there is no information about the actual type and *any* type can be passed as an argument, and **ad hoc** where an arbitrary set of types has been nominated as acceptable. Subtyping is not parametric polymorphism because a specific type (the superclass) *is* known. So the question is, is it ad-hoc?

The choice of the term **ad hoc** emphasises that there need be no relationship between the different types in a given abstraction; the only unifying factor is the existence of concrete implementations that make them part of the set. Operator overloading and Haskell's type classes fit that criteria.

In contrast, subtyping requires a relationship between the subtypes and the supertype, one that allows subtypes to be used in place of the supertype. The currently-existing set of subtypes is only arbitrary in the sense that all code is arbitrary - being the set of code developers have chosen to write. While the implementation of each subtype can be entirely distinct and unique, the substitutability requirement means that inclusion in the set of acceptable types is principled and not ad hoc.

There is a significant difference between providing the implementation that makes type **A** a subtype of type **B** and providing the implementation that enables it to be used as an instance of type class **C** or an argument for operator **+**. That seems to justify considering subtyping to be a distinct class of polymorphism.
> 5 votes

# Answer
Keep in mind that, in PL lingo, the term "polymorphism" is used for different notions.

In OOP, polymorphism usually means subtype polymorphism. If we have a function `foo(x: A)` we can call `foo` with any object having a subtype of `A`. In this way, the function is defined only once but can operate on "many types" -- which justifies the usage of the word "polymorphism".

In functional programming, we often do not have subtypes. Still functions can have a universally quantified type such as `bar : forall a b, a -> b -> a`. This function can take two arguments of any types `a` and `b` (chosen by the caller), and return a value of type `a`. Hence, this is called a polymorphic function. In some OOP languages, a similar feature can be found with the name of "generic function", e.g. `<A,B> A bar(A a, B b)` in Java. We can call also this feature "parametric polymorphism".

There is a terminology mismatch here since OOP decided to use the "polymorphism" term to refer to the subtyping one, hence it needed a new term for "parametric polymorphism".

Anyway, in parametric polymorphism, values of the "unknown" quantified types `a,b` can not be concretely used (since we do not know what they are), but can be merely passed around. This is why `bar` above *must* be the projection of its first argument: the function has no other way to produce a return value of type `a` except to reuse its first argument. Similarly, `baz : forall a, a->a` must be the identity function.

In real-world languages, sometimes parametric polymorphism is broken by some specific constructs in the language. Minor offenders are

* non termination: infinite loops / recursion allows to write a `baz : forall a, a->a` which never terminates, hence it differs from the identity function.
* exceptions / runtime errors: similar to non termination.
* `null` values: if `null` is a value of any type `a`, that can be returned by `baz` as well, making it differ from the identity.

When these are present, one still obtains a weaker form of parametric polymorphism. Worse offenders are

* checked type casts / `instanceof`
* reflection

Indeed, consider this pseudo-Java code

```
<A> baz(A x) {
  if (x instanceof Integer)
     return (x+1);    // Some casting omitted to make this work
  else
     return x;
}

```

This is the identity function on all types, except `Integer` where it does something arbitrarily different. The function above is ugly: it does not handle the `x` argument as an argument of an unknown type. It actually checks the type of `x` at *runtime* and makes decisions on that. We no longer have parametric polymorphism here, since type `A` is not handled in a "uniform" way: the `A=Integer` is now "special".

What we get, instead, is just a function which can act on each type `A` (so it is still polymorphic) but which on each `A` can have a completely unrelated behavior. In a sense, it is just an unconstrained family of functions, indexed over a type $A$. This is what we call "ad hoc polymorphism".
> 5 votes

# Answer
They're definitely different things, which is easier to see with a clearer definition of ad-hoc polymorphism. Quoting from Wikipedia:

> ...ad hoc polymorphism is a kind of polymorphism in which polymorphic functions can be applied to arguments of different types...

So in the definition you've quoted, they're using "on" to mean "passed as arguments", rather than "called from". Ad-hoc polymorphism is available in Java in the form of method overloading. For example `BigDecimal` has 5 `divide(...)` methods, all taking different sets of parameters. Other languages have more obvious examples of ad-hoc polymorphism, where there's only one function/procedure, with a list of parameters, and the programmer has to decide what to do with them inside the function/procedure.

Subtype polymorphism, however, is when you can treat an instance of one type as an instance of another type, so anything available on the second type is also avaialable on the first. This is the `toString()` example you give. `toString()` doesn't operate on different arguments, but it can be called from different types (because it's defined on `Object` which everything in Java is a subtype of).
> 4 votes

# Answer
> The difficulties of dealing with polymorphic operators are not removed by treating types dynamically (i.e., making them latent). The problems of choosing the correct version of the operator and inserting transfer functions if required remain more or less the same. The chief difference in treating types as manifest is that this information has to be made available to the compiler. The desire to do this leads to an examination of the various forms of polymorphism. There seem to be two main classes, which can be called ad hoc polymorphism and parametric polymorphism.
>
> In ad hoc polymorphism there is no single systematic way of determining the type of the result from the type of the arguments. There may be several rules of limited extent which reduce the number of cases, but these are themselves ad hoc both in scope and content

This an excerpt from 'Fundamentals Concepts in Programming Languages' by Christopher Strachey, 1967. Clearly his focus at that time was on forms of Polymorphism where dispatching happens at compile time.

Dynamic Dispatch and Subtyping showed up next year with Simula 67. But to extend his classification, we could say that we've two kinds of Polymorphism : - Ad hoc and Universal. Subtyping and Parametric would be more on the universal side than being ad hoc.
> 0 votes

---
Tags: programming-languages, polymorphisms
---


# Question
Title: Scale a vector until it reaches a certain bound
I got a two points A and B with their respective x and y coordinates. Point B determines the direction of the vector AB, and I know that `-10^9 <= x,y <= 10^9`. My goal is to scale that vector until the x or y coordinate of B hit either bound. Basically I need the vector AB, where B is moved to the edge without changing the direction. In practice this should represent a linear flight path of an object.

How can this easily be implemented?

# Answer
Find the intersection of the line that contains AB with the line $x=10^9$. This is easy.

Do the same for the line AB and the line $x=-10^9$, and for AB and $y=10^9$, and for $AB$ and $y=-10^9$. Now you should be able to take it from there.
> 0 votes

---
Tags: python
---


# Question
Title: How to define formula to determine which group does the element belong to?
I am trying to build a min-max heap tree, here's an example of the tree structure:

* The tree is a complete binary tree
* The index in the array of the tree root is 0 and it contains no element.
* The left subtree is a min-heap and the right subtree is a max-heap.

When I am trying to implement the insertion, I meet a problem that I don't know whether the new element belongs to the min-heap or the max-heap by its index.

index\_of\_min\_heap = {1, 3, 4, 7, 8, 9, 10, ...} index\_of\_max\_heap = {2, 5, 6, 11, 12, 13, 14, ...}

How can I make a formula to determine the index is a min-heap index or a max-heap index? example :

```
is_min_or_max_heap(112) // return min or max

```

# Answer
> 0 votes
Please initially note that w.r.t. your definition, your min-max heap tree is also a complete binary tree (WikiPedia: In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible).

In a complete binary tree implemented via an array -like yours- the $k$th layer has an index from $2^{k-1}-1$ to $2^{k}-2$, considering the root to be $0$th element of the array existing in $k=1$ (where your root is the null element).

So for a given index, $x$, you need to initially iterate through $k$ (starting k=$1$ where the root exists) and if for $k=k^\*$ the condition $2^{k-1}-1 \le x\le 2^{k}-2$ satisfies you should stop and do as follows to know whether the index belongs to the min heap or the max heap.

Please note that you have a binary tree so in each level you can divide it into two halves. The right half belongs to the min heap and the left one belongs to the max heap. Since in each layer exists $2^{k}-2 - (2^{k-1}-1) + 1 = 2^{k-1}$ nodes, nodes with index from $2^{k^\*-1}-1$ to $2^{k^\*-1}-1 + \frac{2^{k^\*-1}}{2} - 1= 3\times2^{k^\*-2} -2$ belong to the min heap and the rest (i.e. $3\times2^{k^\*-2} -1$ to $2^{k^\*}-2$) belong to the max heap.

# Answer
> 0 votes
Personally, I like to start my indexing with 1 when representing complete binary trees. The main reason is that the computation of left and right children is very simple: the children of node $n$ are $2n$ and $2n+1$. This is just adding a 0/1 bit after the binary representation of the parent.

Also for your question this representation gives a clear answer. The second bit (after the leading 1) determines whether the child is in the left or right subtree of the root. (Combinatorically simple, but I do not know whether that is computationally feasible.)

---
Tags: algorithms, heaps
---


# Question
Title: Implementing a correct `let rec in` interpreter in Haskell with `eval` and `sub` semantics
I'm implementing the toy fb-lang from the principles of programming language book. It's a small interpreted language that uses `eval`(uate) expression function and `sub`(stitute) variable with value function to process expressions.

The most challenging construct is the `let rec in` construct which makes it possible to define and interpret recursive functions. And this is where my implementation is failing.

The operation semantics for the recursive function (from the book) are as follows -

$$ \frac{\left.e\_{2} \text { \[Function } x \rightarrow e\_{1}\left\[\left(\text { Function } x-\>\text { Let } \operatorname{Rec} f x=e\_{1} \operatorname{In} f x\right) / f\right\] / f\right\] \Rightarrow v}{\text { Let } \operatorname{Rec} f x=e\_{1} \operatorname{In} e\_{2} \Rightarrow v} $$

The logic as far as I've understood is to unroll one layer of the recursion, wrap it in a function and substitute where the recursive call was being made. You might want to take a look at pg 17 - Substitution and pg 21 - Operational Semantics from the linked book to get more context.

I have a recursive summation function as defined below. For some reason, that I've failed to debug, the subtract operation is not being performed, because of which the termination condition is never being hit.

```
f(x) = if x == 0 then 1 else x + f(x - 1)

```

The code is at Main.hs, the relevant function are `eval`, `sub` and the recursive expression is sumToNExample. Relevant snippets given below.

```
sub :: Ident -> Expr -> Expr -> Expr
sub var@(Ident x) new e = case e of
      EApp ex ex' -> case ex of
        (EVal (VFunc x ex)) ->
          if x == var
            then -- if the function parameter is substituted
            -- the function body is now a closed expression
            -- and the function call can replaced by it's body
              sub var new ex
            else -- substitute variables in the function body and the
            -- expression being applied to the function
              EApp (EVal $ VFunc x (sub var new ex)) (sub var new ex')
        -- substitute variables in both expressions
        _ -> EApp (sub var new ex) (sub var new ex')
      ELetRecIn f x ex ex' ->
        if x == var
          then -- if variable is same as variable of let rec in
          -- then do not substitute it in expression body
          -- because they are bound to the parameter and
          -- are not free variables
            ELetRecIn f x ex (sub var new ex')
          else ELetRecIn f x (sub var new ex) (sub var new ex')

eval :: Expr -> Value
eval ex = case ex of
  ELetRecIn f x ex ex' ->
    let unroll = sub f (EVal $ VFunc x (ELetRecIn f x ex (EApp (EVal $ VVar f) (EVal $ VVar x)))) ex
    newFunc = EVal $ VFunc x unroll
        nextCall = sub f newFunc ex'
     in eval nextCall

```

This is not an assignment, I'm just self-learning. I've spent hours of head-scratching. So **any help with where I might have gone wrong, or any tooling suggestions that make it easy to walk through each step of `eval` function will be helpful**.

# Answer
> 2 votes
Your definition of substitution is doing too much work for `EApp`.

```
(a b)[e/x] = a[e/x] b[e/x]

```

```
sub x e (EApp a b) = EApp (sub x e a) (sub x e b)

```

For substitution the only interesting cases should be variables and binders. `EApp` is neither, so apply `sub` to its fields and reconstruct the term, without any additional matching, let recursion handle that.

---
Tags: recursion, haskell, interpreters
---


# Question
Title: Attempt to reduce to problem of inner product
The problem of Orthogonality: gives $n$ vectors of dimension $k$ and another set of same, can a pair be found with inner product = $0$?

The problem of max product: likewise two sets each $n$ vectors (I forgot to mention in both cases values are binary). We want to find maximal inner product (one vector from set $A$ and one from $B$).

I want to find a reduction between OV to max. Inner product.

My idea: Use negative values, claim its equivalent with negative value and possitive values.

What I mean, OV reduced to max. Inner prod with negative values by multiplying all by $-1$.

Then if maximum is zero... Orthogonality. Else, no orthogonality.

But i need to argue negative max inner product equivalent to max. Inner product.

Maybe there is another way?

If it does not work, also interested in reduction from sat.

# Answer
One possibility is to take the tensor squares of the vector: replace each vector $x$ with a new vector $\hat{x}$ given by $\hat{x}\_{ij} = x\_i x\_j$ (the vectors have length $k^2)$. We have $$ \langle \hat{x}, \hat{y} \rangle = \sum\_{ij} x\_i x\_j y\_i y\_j = \langle x,y \rangle^2. $$ Therefore if you know the *minimum* inner product, you can solve OV. It remains to negate all vectors in one of the sets.
> 5 votes

---
Tags: algorithms, complexity-theory, reductions, combinatorics, satisfiability
---


# Question
Title: Algorithm to convert a large number (output of a hashing algorithm) into something easily compared visually by humans?
I'm looking for a way to help my users more easily compare the output of a fingerprinting algorithm (which is a very large number/byte array).

So instead of showing something like "8c0db1f40b6e4c1e268a5f3e2405278f" as the fingerprint, I'd rather show something like 'AT-BAD-HONEY-CAR-MOUSE' (obviously the underlying number of represented bits still needs to be the same as I cannot allow ambiguity, it's a fingerprint after all).

I'm not restricted to a textual representation, a (very small) image would also be fine (note: just using the bits as pixels in a b&w image does not count as "easily visually comparable" in my book). The only constraint on the algorithm would be that the final output does not need crazy amounts of screen real-estate.

# Answer
> 1 votes
For textual representations, check out the PGP word list, Diceware (as improved by EFF), S/KEY's word list, and BIP39.

For visual representations, check out randomart; see also here.

# Answer
> 0 votes
This is a problem that identicons intend to solve. You may not have noticed, but SE uses identicons for their avatars. You may not have noticed, which says enough.

---
Tags: hashing
---


# Question
Title: Why does this algorithm not have an exponential complexity?
In this article :
Kinodynamic Motion Planning
B. Donald, P. Xavier, J. Canny, J. Reif
https://www.cs.duke.edu/brd/papers/src-papers/jacm-final.pdf

The authors present a PTAS algorithm that can compute a safe, close to optimal trajectory from a point A (having a certain speed vector) to a point B (having a certain speed vector). They do this by transforming the problem to finding the shortest path in a directed graph. All vertices in the resulting directed graph have an outgoing degree of 3.

I don't understand how we can find the shortest path in this directed path from one point to another (by using BFS) without the complexity being exponential, since doing a BFS from the starting point until we encounter the end point would take $O(3^x)$ with $x$ being the layer of the BFS.
Instead the complexity that is noted on page 5 of the article is this :

> $O( n( \frac{lv\gamma³}{\epsilon⁶})^d)$

$n$ being the number of bounding halfplanes on obstacles, $l$ being the length of the side of a cube in which all points are placed, $v$ is maximum velocity and $\gamma$ is maximum acceleration divided by maximum velocity. $\epsilon$ as always is the approximation value and $d$ the number of dimensions in which our problem is placed. For simplicity let $d$ be $1$.

Clearly we can see this complexity is not exponential, my question is why? Even in one dimension, we still obtain a graph in 2 dimensions (1 for position and one for velocity) and the BFS will still take exponential running time. Am I missing something?

Thanks

# Answer
The graph in question is a grid discretization of the phase space ($TC$ in the paper). Consider a 4-connected grid in the plane with 10x10 vertices. The branching factor of this graph is 4 (ignoring the boundary), but there are only 100 vertices in this graph total. BFS on this graph will not take exponential time because BFS throws away exponentially many paths by keeping track of nodes that have already been "explored" and not adding them back to the queue.
> 1 votes

---
Tags: algorithms, algorithm-analysis, runtime-analysis, approximation
---


# Question
Title: Find all nodes in directed graph from starting node that complete a loop
Suppose I have a directed graph, where one of the nodes is selected to be the "initial" node. **What algorithms should I consider using** to to find all the nodes that

* have a path from the initial node to itself
* have a path from itself to the initial node

For example, in the below graph with node A as the initial node, I would like the algorithm to only return the green nodes, as they are the only nodes that have a complete path to and from node A.

# Answer
> 1 votes
You should use the BFS algorithm to find the path from the source node to any other node (and it even produces the shortest path).

For the converse, run the BFS on the transposed graph (swap the direction of each edge).

In your example, what you found is the strongly connected component that the initial source node resids in. There are plenty of fast algorithms to compute the set of all strongly connected components in the graph, if you are interested.

---
Tags: directed-graphs
---


title: Maximum planar subgraph problem

text:
# Question
Title: Maximum planar subgraph problem
Given a graph G I want to find the maximum planar subgraph which is a grid graph. (Because the nodes of this subgraph represent points on a grid).

Is there any library in python for finding the maximum planar subgraph?

Is there some way how to implement these constraints for the grid graph?

Edit: As I understood I am looking for the maximum planar subgraph which is at most 4-connected and at least 2-connected

# Answer
I doubt there are any implementations for the algorithms you are looking for.

The problem, also known as *Planar Edge Deletion*, *Edge Planarization*, *Graph Planarization*, or sometimes *Minimum Planarization*, is NP-complete and was shown in 2007 to be fixed-parameter tractable (for every *fixed* number of edges you want to delete, there is a "linear time algorithm" for the problem). However, the algorithm is extremely non-trivial and rely on deep mathematical results.

* K. Kawarabayashi and B.A. Reed. Computing crossing number in linear time. In: Proc. STOC 2007, 382—390.
> 1 votes

# Answer
This doesn't answer your question about your particular problem, but you can find theory for a related problem involving grids by searching for "bidimensionality".

It's the idea that every graph is either low treewidth or contains a large grid minor which makes it possible to get solution in polynomial time.

See Section 3 in Beyond Planar Graphs presentation by DeMaine. Also this is mentioned in Section 1 of Width parameters beyond tree-width and their applications, which is a good tutorial for the basics needed to understand bidimensionality results.
> 0 votes

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


title: Calculate the effective access time

text:
# Question
Title: Calculate the effective access time
This question seems to be causing a lot of debate and I'm wondering whether my working is correct.

> A computer with a single cache (access time 20ns) and main memory (access time 500ns) also uses the hard disk (average access time 0.01ms) for virtual memory using paging. If it is found that the cache hit rate is 95% and the page fault rate is 1%
> Calculate the effective (average) access time (EAT) of this system for a sequential access system.
> (a) 73.5ns. (b) 55ns. (c) 50ns. (d) 74.75ns.

My working was as follows: (0.95x20) + 0.05 (0.01(10000+500+20) + 0.99(500+20))

Leading me to an answer of 50 being C), however others have seem to have chosen D) as their answer

Any help would be appreciated.

# Answer
Seems correct , cache hit gives you **0.95\*20** ns if it misses then 0.05 or 5% of the time you consult memory that is 0.05\*( no page fault hence 0.99\*( 500 from mem to cache + 20 from cache to cpu) else if page fault occurs then 1% or 0.01 \*( 10000 ns from disk to mem + 500 ns from mem to cache + 20 ns from cache to cpu)) Should be 45.5 ns which I would give as C
> 0 votes

# Answer
The problem is a bit unclear, but I would assume that the page fault rate is 1% for *all* accesses, not just for the 5% that didn’t hit the cache. So the total is 0.95 x 20 + 0.04 x X + 0.01 x Y.

Then there is the question how long X or Y are: Many processors will fill a cache line from memory, then access the cache. Total x = 500 + 20. Others might deliver data directly from main memory, X = 500. Similar for Y.
> 0 votes

# Answer
just came across the same question

you need to add an extra 500 to your calculation for accessing the main memory because it actually has to be accessed twice: once for making the page table and another for the actual data, when using virtual memory

(0.95x20) + 0.05 (0.01(10000+500+500+20) + 0.99(500+500+20)) =75 which i would have guessed is closeset to D
> 0 votes

---
Tags: cpu-cache, memory-access
---


# Question
Title: Understanding halving algorithm in online learning
I am working through *"Understanding Machine Learning Theory"* by Shai Shalev-Schwartz. In the chapter "Online learning" I came across the halving algorithm, the author uses the following algorithmic pseudo-code for the algorithm  I am having difficulty understanding authors intention from the highlighted portion. Here $\mathcal{H}$ is the hypothesis class, $V\_{t}$ is the version space at iteration t, $(x\_t,y\_t)\in S$ are samples from the set provided by the oracle. We also assume that $h^{\*}\in\mathcal{H}$ (realizability).

**Attempt**: My guess is the prediction is based on majority vote from hypotheses in version space, but I don't see where he is pruning the version space using the majority vote? What am I missing? Any help would be appreciated!

# Answer
The prediction is the value of $r$ which maximizes the quantity $$ | \\{ h \in V\_t : h (\mathbf{x}\_t) = r \\} |. $$ This is the number of surviving hypotheses (belonging to $V\_t$) which predict $r$ on the current point ($\mathbf{x}\_t$). Equivalently, we ask all hypotheses in $V\_t$ for their opinion on $\mathbf{x}\_t$. If more answer $0$, we predict $0$. If more answer $1$, we predict $1$. In case of a tie, we (arbitrarily) predict $1$. In other words, we take majority vote on the opinions of the hypotheses in $V\_t$ on $\mathbf{x}\_t$.

After seeing the true label, we throw out all hypothesis which were wrong; this is the meaning of the update line, which sets $V\_{t+1}$ to contain all hypotheses $h$ in $V\_t$ such that $h(\mathbf{x}\_t) = y\_t$, where $y\_t$ is the true label of $\mathbf{x}\_t$.

Each time the algorithm is wrong, at least half of the hypotheses in $V\_t$ were wrong, so $V\_{t+1}$ is at least twice as small as $V\_t$. So after $\log\_2 |\mathcal{H}|$ wrong answers, we are left with a single hypothesis, which must be the true one. This is why this algorithm makes at most $\log\_2 |\mathcal{H}|$ mistakes.
> 2 votes

---
Tags: machine-learning, learning-theory
---


# Question
Title: Is the Berkeley tutorial on Fibonacci trees using wrong figures?
I'm confused about the figures in a Berkeley tutorial on Fibonacci trees, which depicts **fibtree(2)** as

and **fibtree(3)** as

I thought **fibtree(3)** looks like the following

(the figure is adapted from another StackOverflow post).

Do I misunderstand something? Or is the Berkeley tutorial misusing the figures?

# Answer
> 21 votes
I would like to say both you and that Berkeley tutorial are correct.

As commented by chepner, the trees in Berkeley tutorial and the trees you thought are the same semantically; only the labels of the nodes are different.

Every node in all figures represents a call to compute the corresponding Fibonacci number.

The difference is that you prefer to use strings "F(0)", "F(1)", "F(2)", etc. to represent the calls that compute the 0-th Fibonacci number, the 1-st Fibonacci number, the 2-nd Fibonacci number, etc. respectively while the Berkeley tutorial uses those Fibonacci numbers themselves, $0, 1, 1$, i.e., the results of those calls to represent the same calls respectively.

Your preference is more illustrative since the string "F(0)", "F(1)", "F(2)", "F(3)", etc. are obviously descriptive while the Fibonacci numbers $0, 1, 1, 2$, etc. do not indicate the calls immediately without additional explanation. Furthermore, both the node representing the call "F(1)" and the node representing a different call "F(2)" are labelled $1$ in Berkeley tutorial, which may lead to confusion.

# Answer
> 7 votes
Your trees are showing the same thing; you are just labeling each node by the call, and the Berkeley tutorial is labeling each node by the result of that call. Compare the two pictures of fibtree(3), noting that:

$F(0) = 0$

$F(1) = 1$

$F(2) = 1$

$F(3) = 2$

You'll see there's no disagreement at all.

Perhaps it would be informative to see the tree "grow" over time as the calls are made and resolved. If we define $F(0) = 0$, $F(1) = 1$, and $F(x) = F(x-1) + F(x-2)$ for $x\>1$, we can visualize how we compute $F(3)$ with a tree, where each node is a function call. I will label nodes as $F(x)$ when we don't know the answer yet, and label them with a purple number when we do.

We want to know $F(3)$:

Since $3\>1$, we call $F(3-1)$ and $F(3-2)$ and wait for the result.

Since $2\>1$, we call $F(2-1)$ and $F(2-2)$ from that node, and wait for the result. **This is your picture**.

We can immediately replace $F(0)$ with $0$ based on our function definition, and then return, making no further calls.

We can also replace all $F(1)$ calls with $1$ by our definition.

We can now evaluate $F(2)$ by adding the results of its child calls, $1+0$

And finally we can find $F(3)$ by adding the results of its child calls, $1+1$. This is **Berkeley's picture**.

Hopefully that clarifies the relationship between the two pictures.

---
Tags: terminology, recursion
---