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

3
votes
0answers
21 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
22 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
20 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
votes
0answers
161 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 ...
3
votes
0answers
23 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
2answers
3k views

What is the best strategy for a guess-my-number game?

In the "guess-my-number" game, one player (player A) makes guesses at another player's (player B) secret number. All games would follow the following procedure: Player B decides on a number between ...
0
votes
0answers
18 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
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 ...
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
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$ ...
2
votes
1answer
50 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
72 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
0answers
28 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 ...
0
votes
0answers
61 views

When to use $\Delta$ or $\delta$ in formulas? [closed]

I use this symbol to denote the interval of created packets (variable, not constant) in the field of computer science. In formulas, which symbols should I use, $\Delta$ or $\delta$? Or other symbols? ...
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 ...
-4
votes
0answers
34 views

Getting Started [closed]

I am new to code and need a good program for a basic knowledge. I have started looking at programs but am in need of advice of something that does not need a masters or doctorate in the subject and i ...
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 ...
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 ...
1
vote
1answer
36 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
1answer
19 views

About Newman and Girvan definition of Modularity of Network-Community

Can some body explain me the following statement about Community Structure in a Graph : Newman and Girvan write: „In a network in which edges fall between vertices without regard for the communities ...
0
votes
1answer
459 views

Y-Axis units on FFT graph

A 50Hz sinusoid wave with a voltage range of +/-20V is sampled at 512Hz for 1 second. No bias or phase shift are present. The signal is run through an FFT. The result is one spike at 50Hz on the ...
0
votes
1answer
49 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
40 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 ...
2
votes
1answer
626 views

Finite state machine

I am doing discrete math, and we are studying Finite State Machines. But i am a little confuse on how to do this. Here is a question, Write a regular expression for the language, and define a finite ...
0
votes
1answer
405 views

Calculating normals for a polygon mesh (3D computer graphics)

I want to write a program to generate arches, a common architectural form, and export them to a wavefront object format for sharing with various three dimensional graphics editors. To do this, I need ...
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$ ...
1
vote
1answer
814 views

Using BFS or DFS to determine the connectivity in a non connected graph?

How can i design an algorithm using BFS or DFS algorithms in order to determine the connected components of a non connected graph, the algorithm must be able to denote the set of vertices of each ...
2
votes
2answers
24 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
63 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 ...
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 ...
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
15 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 ...
2
votes
0answers
26 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
2answers
76 views

Can anyone explain the average case in insertion sort?

I am not sure if this question is off topic or not but a question like this has been asked on this site before - Insertion sort proof Here is an example of insertion sort running a on a set of data ...
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
54 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
18 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 ...
2
votes
3answers
133 views

which branch of computer science is most math intensive? [closed]

I am planning for a Master degree study, my major in college is computer science, but I also like math. I want to know which branch of computer science uses most math, not only discrete math, but also ...
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 ...
0
votes
2answers
1k views

problem simplifying boolean algebra expression using consensus theorem

Please simplify this logic expression for me with helping boolean algebra : A'C'D + A'BD + BCD + ABC + ACD' I know that must use consensus theorem . my solve : STEP 1 : Terms 1 & 3 ...
6
votes
2answers
364 views

Image Reconstruction:Phase vs. Magnitude

Figure 1.(c) shows the Test image reconstructed from MAGNITUDE spectrum only. We can say that the intensity values of LOW frequency pixels are comparatively more than HIGH frequency pixels. $$ ...
3
votes
1answer
44 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 ...