# Tagged Questions

All mathematical questions about computer science, including theoretical computer science, formal methods, verification, and artificial intelligence. For questions about Turing computability, please use the (computability) tag instead. For numerical analysis, use the (numerical-methods) tag. For ...

55 views

40 views

### Constructing every spanning tree from addition and deletion of edges

Let $G = (V,E)$ be given (note that this is not necessarily simple), and consider the set of every spanning tree of $G$, $S$. Choose any $G_a, G_b \in S$. Is it possible to construct $G_b$ from $G_a$ ...
44 views

### Time Complexity and big-O in CS

Suppose you have 2 algorithms, named A1 and A2 that are designed for solving a problem, with time complexity of $n^2\cdot 2^n$ and $n!$, respectively, where n is the size of the problem instance to ...
38 views

### Quintillion bytes to terabytes

I am trying to convert 2.5 quintillion bytes to terabytes (IBM's estimate on the amount of data produced daily), could someone check if my calculations are correct? ...
23 views

### Help with Legendre Plot Matlab

I've written a code to change a Chebyshev into a Legendre Polynomial, however it will not plot the graph after and I'm not sure why the graph will not plot? The code i have is: function ...
70 views

### Proving that a language is regular and context-free

Let Σ be a finite alphabet and L ⊆ Σ be a language. Let Σ0 ⊆ Σ. For each string w = w1 · · · wn ∈ Σ , define res(w, Σ 0 ) = y1 · · · yn where yi = wi if wi ∈ Σ 0 , and yi =  if wi ∈ Σ \ Σ 0 , for ...
12 views

### 3CNF is not satisfiable iff CNF is UNQ

I'm trying to come up with a reduction to show that $NOT3SAT \leq_p UNQ$, where NOT3SAT is the non-satisfiability problem for 3CNF and UNQ is unique satisfying assignment for CNF. So, what I'm ...
29 views

### Number of fragments into which a fixed triangle is cut in the 3d version of the binary space partitioning algorithm

You can scroll down the question, if you're familiar with the construction of a 3d binary space partition as presented in the book Computational Geometry: Algorithms and Applications by Mark de Berg ...
22 views

### Why is no analysis possible for the 3d version of the random binary space partioning algorithm?

Let $S$ be a set of $n$ non-overlapping line segments in the plane $\ell(s)$ be the line which contains $s\in S$ $\ell^+$ and $\ell^-$ be the half-plane above and below of a line $\ell$, ...