# 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 ...

44 views

### Relation between focus and camera intrinsic parameters

Does a focus tuning affect the camera intrinsic parameters? More precisely, if the focus of a camera is changed, does the camera intrinsic parameters matrix remain unchanged? Apparently, since this ...
20 views

15 views

### How instances of Automaton(NPDA) read and write the stack

I am reading a text book, Introduction of the theory of computation by Michael Siper. I do not understand the notion of NPDA well. One problem is that the definition of NPDA is not clear on how the ...
51 views

### $\prod _{k=2}^{n} {\log k}$ is big-$O$ of what?

$$\prod _{k=2}^{n} {\log k}$$ is a big-$O$ of what? I can see it $O(n!)$ but is there a tighter solution?
304 views

### Show that $\{a^ib^jc^{2j}\mid i\ge 0,j\ge 0\}$ is not regular

How can I show this?I don't know how to start. Show that the set given below is not regular. $$\{a^ib^jc^{2j}\mid i\ge 0,j\ge 0\}$$
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 ...
130 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? ...
24 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 LegendrePoly(n)...
76 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 ...
30 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 ...
23 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$, ...
25 views

### Why FFT algorithm (Cooley-Tukey) takes O(nlogn)?

I was wondering how this algorithm can be formally interpreted with an upper bound n*log(n). There's some formal proof for this? I would appreciate if somebody can help me. Thank you.
21 views

### Complement of automata

I know that in order for the complement of the automaton to work, it needs to be deterministic and complete, and if it is not deterministic we can always apply the power set construction, and if is ...
29 views

### How to prove that a depth-first algorithm labels every vertex of G?

I understand exactly how a depth-first search/algorithm works. You start at the root, and then go to the left most node, and go down as far as you can until you hit a leaf, and then start going back ...
20 views

### Progressive simple computation using a number to represent memory

Is it possible to represent computation using a base formula (function) and store it's progressive memory, bit arrays stored as a series of numbers along a $y=c(x)$ style? Where $c(x)$ is a "...
36 views

### Prove that for every function $s:\mathbb N\to \mathbb N$ with the following constraints holds that:

Hello guys I'm studying Computational Complexity and I have stumbled upon the following question which I has no idea how to even start proving. I would appreciate any help. Prove that for every ...
56 views

100 views

### Encyclopedia of Integer Sequences - Formula

I am trying to reproduce the following sequence (https://oeis.org/A062734): ...
89 views

### Reverse Automorphic Numbers

I recently stumbled across Automorphic Numbers (definition and examples). In simple words, a number $n$ is said to be automorphic if last $d(n)$ digits of $n^2$ are $n$ itself (where $d(n)$ is ...
35 views

### Correctness of the sweep line algorithm for line segment intersection in the plane

Suppose we are given a finite set $S$ of line segments in the plane and the intersection between two segments is empty or a single point in the interior of both segments at most two segments ...
59 views

### Problem with 4-body Matlab code

I'm trying to model the 4 body problem to see how Jupiter, Earth and Mercury orbit the Sun. I found a two body script and adapted it as accordingly to modify my problem, but for some reason the ...
44 views

### Create a formula for order of parenthesis

I am stumped at creating a formula (for a coded math problem evaluator) that finds what is within the parenthesis. It gets tricky when you have () within ...
16 views

### Proof quadratic congruent equation has no solutions in $\mathbb{N}$

In computer science, quadratic probing is used in hash tables. We choose a $c_1$ and $c_2$ in the hash formula $h(k,i) = (h'(k) + c_1 i + c_2 i^2) \mod{m}$ where $h'(k) = k \mod{m}$ and $m$ is the ...
34 views

### Extract each digit of a binary \ decimal number

How can one extract the digits of a binary \ decimal number. For example i have 100110111 to need to extract them only using +,-,*,/ and MOD. I can only use this LOOP Language. Most of the algorithms ...
28 views

### What's the difference between “worst/best case big-O()” and omega()/theta()?

In formal discrete math and computer science we talk about "big-θ," "big-O," and "big-Ω" notation, being tight, upper, and lower bounds (respectively) on the growth of properties of an algorithm as ...
Someone else had asked this question but not to enough detail. I understand that you can sum all of the elements from $1$ to $n^2$ that are in the matrix to get $n^2(n^2+1)/2$. Then from there you ...