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

learn more… | top users | synonyms

1
vote
1answer
35 views

What is the context-free grammar for $0^{n}1^{2n+1}0^{n}$

context free grammar for $0^{n}1^{2n+1}0^{n}$ I've tried several different methods to find it but I can't figure out how to make both sides opposite to each other...please help I've been working on ...
0
votes
0answers
17 views

How is scope of research for a Computer Engineer different from that of Computer Scientist (Maths) [on hold]

How different are the research question answered by some who is a Computer Engineer and some who is mathematician who works in the field of computer. Examples would help?
1
vote
1answer
29 views

What is a transfer function?

If: $N$ is a set of nodes in a program dependence graph, which is a graph with two type of edge $L$ is a lattice of security levels What does the following mean: "For every $x\in N$, a so-called ...
0
votes
1answer
33 views

Fast multipole method: help on tutorial

I have some hard time with the FMM (Fast multipole method). I try to understand the basics with: "http://www.umiacs.umd.edu/labs/cvl/pirl/vikas/publications/FMM_tutorial.pdf". So here are my ...
-1
votes
0answers
46 views

Learning Math for Computer Science

Apologies if this has been already asked. I have gone through a lot of different questions but they don't adapt to my personal situation. I have a 2 years diploma in software development and I am ...
6
votes
1answer
104 views

FRACTRAN for natural numbers

Is there a simple analogue of FRACTRAN that maps a natural number to a natural number, instead of mapping a list of fractions to a natural number? One could use Gödel encoding to translate FRACTRAN ...
0
votes
2answers
26 views

Unique Aggregation of Numbers

Suppose I have 5 numbers: 1,7,13,5,6. I want to perform some kind of algorithm that allows me to derive a number such that if any of those numbers changed in value or switched in order that I would ...
1
vote
0answers
22 views

Calculus book for computer science students

I'm going to teach calculus I and II to undergraduate computer science students and I would like to know if someone here knows some book or site with easy calculus applications in computer science. ...
0
votes
1answer
22 views

Adding color components with transparency

If we define a color with transparency as $(r,g,b,a)$, with $r,g,b,a\in[0,1]$, how do we define $(r_1,g_1,b_1,a_1)+(r_2,g_2,b_2,a_2)$? The definition must be closed, and must represent the computer ...
1
vote
0answers
12 views

Each recursive approximating sequence for Kolmogorov complexity is not uniform

Denote the plain Kolmogorov complexity by $C(x)$. Let $\phi(t,x)$ be a recursive function and $\lim_{t\to\infty} \phi(t,x) = C(x)$ for all $x$. For each $t$ define $\psi_t(x) := \phi(t,x)$ for all ...
0
votes
0answers
19 views

Closest Triplets (Advanced form of Closest pair algorithm)?

So I was trying to solve for the closest triplets from the given number of points(closest in terms of sums of their Euclidean Distances i.e. D(P1,P2)+D(P2,P3)+D(P3,P1) ) ! I thought of proceeding in ...
-1
votes
0answers
9 views

Calculating the object height using camera output when object is small (in mm/inches) [closed]

Any formula to get object height, width of a object using camera output where we know focal, object distance and image distance and also angle of view.
2
votes
0answers
15 views

Kolmogorov complexity of substring if string is divided according to rule

Denote the plain Kolmogorov complexity of a string $u$ by $C(u)$. Now let $u$ be a string of length $n$ with $C(u) \ge n - O(1)$ and suppose $u = u_1 \cdots u_{\log n}$, a subdivision of the ...
0
votes
1answer
27 views

Length of substring if we just consider a subdivision in $\log n$ substrings

Let $u$ be a string of length $n$ and consider a subdivision in $\log n$ substrings $u = u_1 u_2 \cdots u_{\log n}$. Is it true that there exists a constant $C$ such that for each $1 \le i \le \log n$ ...
1
vote
5answers
189 views

explanation of notation in programming problem

I am trying to attempt to solve this problem but I am unsure what this equation means: $$\frac{n!}{ r!(n-r)!}$$ What do the exclamation marks mean in the above?
1
vote
0answers
29 views

On Kolmogorov complexity of first and last half of a string

Denote by $C(x)$ the plain Kolmogorov complexity of $x$ and let $x$ satisfy $C(x) \ge n - O(1)$ with $n = |x|$. If $x = yz$ with $|y| = |z|$ show that $C(y), C(z) \ge n/2 - O(1)$. Any ideas how to ...
2
votes
1answer
52 views

Implication in linear logic

Linear logic abandons the structural rules of weakening and contraction. I wanted to know whether we have $p ⊸ p$ in linear logic. Can anyone help?
1
vote
1answer
73 views

Ignoring the workspace in quantum computation

In his book Quantum Computer Science, Mermin says that, although we'll need lots of "workspace" qubits in addition to those in the input and output registers, we can essentially ignore these in our ...
1
vote
1answer
35 views

Chaikin's Algorithm: Proof of Convergence

Chaikin's algorithm is, in some sense, similar to de Casteljau algorithm in that (in the limit) it produces a curve from a set of control points. There are claims all over the internet that Chaikin's ...
1
vote
0answers
23 views

Kolmogorov complexity, no description mechanism can improve on additively optimal/universal one infinitely often

In An Introduction to Kolmogorov Complexity and Its Applications explaining the notion of additively optimal or universal it is written: The key point is not that the universal description method ...
1
vote
0answers
16 views

Epipolar geometry - Fundamental matrix derivation (Hartley, Zisserman)

I have a question to the following derivation of the fundamental matrix by Hartley and Zisserman in "Multiple View Geometry in computer vision" (Link, page 5): Why is it possible to do the very ...
1
vote
1answer
37 views

Reference for Dynamic Arrays

I'm looking for a reference for the fact that dynamic arrays have random access in constant time and inserting or deleting an element at the end can be done in constant amortized time. What would be a ...
0
votes
0answers
15 views

How do you compute the weighted sum of data points for learning the centers of a hyper basis function network (HBF)?

I was reading the following paper on hyper basis function (HBF) (similar to radial basis function RBF network) and was trying to figure out how one learns the movable centers of the hyper basis ...
0
votes
1answer
52 views

Prerequisite reading for Concrete Mathematics? [closed]

I'm a freshman computer science major who has just started reading Concrete Mathematics, mathematics for computer science. Is there any prerequisite reading or learning I should do before embarking on ...
0
votes
1answer
41 views

Why is 2's complement called this way?

So, I'm preparing for a test and one of the preparation questions is as follows: I can tell easily that 'a' and 'e' are just wrong and therefore these answers are irrelevant, but taking a look at ...
0
votes
1answer
18 views

Hashing: Quadratic Probing

I have the following to prove, unfortunately I am not able to do so. Let h, h' be hash functions: $h(k,i) = (h'(k) + c_{1}i + c_{2}i^2)$ mod $m$. Show the following: if m is prime and $c_{2} \neq 0$ ...
2
votes
2answers
25 views

Is the language $\{yxzx^Ry^R \mid x,y,z \text{ belongs to } \{0,1\}^+ \} $ regular?

This is a question from Iran's national grad school entrance exam. In the answers key, the answer was that the following language is regular but I doubt it is true, I proved using pumping lemma that ...
2
votes
0answers
66 views

Math behind No Man's Sky, or Math of Minecraft in Space [closed]

I recently received a question from one of my students which is a bit outside my life experience. However, I expect this may be of interest to many: I was reading up on a new video game that's ...
0
votes
0answers
19 views

The gradient of a 3D function

While learning computer-graphics I'm having trouble understanding what is the gradient of a 3D function - $f$, and can it be expressed algebrically? From my understanding the gradient is the ...
0
votes
0answers
16 views

Impose linear constraints

I am implementing Han and Kanade's [1] perspective factorization method. I reached the point where I need to impose some constraints on the Motion matrix so it becomes valid. The matrix I want to ...
3
votes
0answers
24 views

What does “the activation of a basis” mean?

In the paper Rajat Raina, Alexis Battle, Honglak Lee, Benjamin Packer, Andrew Y. Ng, Self-taught learning: transfer learning from unlabeled data, ICML '07 Proceedings of the 24th international ...
2
votes
0answers
27 views

Decidability - Complexity

Can someone tell me where I can get some information about the following? We have linear differential equations with polynomial coefficients depending on x. $a_n(x)y^{(n)}+ \dots ...
1
vote
1answer
44 views

Choosing best representation for hit detection in computer graphics

Suppose I have 3D spheres. What is the best representation for the spheres in order to detect whether the end of an arrow hit them? and why? I thought about an isoparametric representation since it's ...
-1
votes
0answers
163 views

need mathematical expression for the below [closed]

Want to convert below algorithm into a mathematical model:- General points 1. Let there be a Connected Directed Graph. G = (V, E) V vertices or nodes E edges. This graph can be seen as a network ...
2
votes
2answers
85 views

Verify input is the sum of other numbers

I have a relationship: 4000k + 2500j + 400g = n, k >= 0, 0 <= j <= k, 0 <= g <= j I have to, given n, verify ...
0
votes
1answer
57 views

Basic=pre algebra math books?

I have been searching and there is so many, I am in computer science and did not realize how heavy math was in this field. i do not really understand why it is unless you are going to work in the ...
0
votes
1answer
19 views

Proving a Partial Derivative Equivalence Using Taylor Series Expansion?

I'm studying computer vision, and one of the problems in my book is to prove that $\partial f/ \partial x = f(x+1) - f(x)$ It's been a while since I've touched Taylor Series, and so I'm not sure of ...
1
vote
0answers
20 views

FFT procedure for evaluationg a polynomial at $N$ Fourier points

The following is the recursive FFT procedure of Algorithm for evaluationg a polynomial of length $N$ at $N$ Fourier points. Algorithm (FFT - fast Fourier transform). Input arguments. $ \ ...
4
votes
1answer
75 views

Can the GM-AM inequality fail on a digital computer?

It is well-known that valid mathematical formulas can fail on digital computers, due to rounding error, catastrophic cancellation, or whatever. So, it seems that the celebrated Geometric Mean - ...
6
votes
0answers
74 views

How to attack universal hash function based on finite-field arithmetic?

As per the Recursive n-gram hashing is pairwise independent, at best paper, I want to use the algorithm described in chapter 6 and 7 (page 7 - 10). The hash works as follows: Define a random ...
3
votes
1answer
45 views

Usefulness of prime numbers as Threading Timeouts in programming [closed]

I am a .NET programmer, founded in math. I am having an argument with a fellow programmer. When I add a Threaded Timer to the program, the interval in milliseconds I use is always a prime number. ...
1
vote
0answers
34 views

Camera calibration: how does checkerboard size/numbers/placement affect accuracy

I am trying to calibrate a camera using a checkerboard by the well known Zhang's method followed by bundle adjustment, which is available in both Matlab and OpenCV. There are a lot of empirical ...
0
votes
0answers
35 views

Exponentiation of Pascal's Triangle(in matrix form)

I want to find a pattern in subsequent exponentiations of the pascal triangle shown in the form below Matrix P[K+1][K+1]: $$ \begin{matrix} \binom{0}{0} & 0 & 0 & 0\cdots ...
0
votes
1answer
12 views

Recursive formula for minimal editing distance - check my answer

Given a word $X=x_1x_2x_3...x_i$ and $Y=y_1y_2y_3...y_j$, the minimal editing distance is defined to be the minimal number of actions needed to transform $X$ to $Y$ where the legal actions are: 1) ...
0
votes
1answer
20 views

How do we prove a method is optimal?

This is a very simple question, infact it's so simple that I have no idea how to solve it. We have an ordered list of $n$ words. The length of the $i$'th word is $W_i$. Our goal is to write all the ...
0
votes
1answer
12 views

max degree polynomial for time complexity considerations

Is there some maximum degree for a polynomial for time complexity considerations and maybe P-NP considerations, maybe some high-degree polynomial formula identified by name, and associated with some ...
2
votes
1answer
33 views

Find recursive formula for special function

Kind of a strange question I know, but here goes: We are given a string of letters $T$ without any gaps or commas, just letters. Depending on what $T$ is, it could be broken down to form a valid ...
2
votes
1answer
37 views

Proving optimality of simple greedy algorithm

Professor Xavier (yeah, the one from X-Men) wants to drive from Reno to Newark. His gas tank, when full, holds enough gas to drive $n$ kilometers. The professor has a map showing the gas stations ...
2
votes
1answer
20 views

Problem with my simple algorithm to count repetitions

We have two arrays $A,B$ with sizes $n,m$ respectively. We know that $m \geq n$. We also know that no array contains the same number twice. Propose an algorithm that prints how many numbers appear in ...
1
vote
1answer
65 views

prove that $p(n) := n^2 + n + c$ is not prime

The question is in MIT Mathematics for CS assignments but unfortunately there is no solutions. -> I do understand that it is false if we use $n = c$ or $n = c-1$ but cannot formally write it as ...