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
0answers
11 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
22 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
11 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
18 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
7 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
29 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
35 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
18 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
60 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 ...
3
votes
1answer
300 views

Help with Recurrence relations forward substitution

Thanks in advance to anybody who can help, The question: solve by recurrence relation using forward substitution and verify by mathematical induction. $T(n) = 2T(n/7)$ for $n > 1, n$ is a power ...
1
vote
0answers
36 views

Why zero to the zero power is 1? [duplicate]

The google calculator say that $0^0=1$. I'm confused. It's well-known $0^0$ is undefined.
2
votes
1answer
40 views

Can we see natural deduction rules as functions or even as formal grammars?

Is there a way of seeing natural deduction rules as functions or even as formal grammars, maybe context-free grammars or Lambek grammars? It seems quite "easy" to see the rules as functions which take ...
2
votes
3answers
34 views

Prove correctness of simple greedy algorithm to find max

We have $2n$ values $x_1,x_2,x_3,\ldots,x_n$ and $y_1,y_2,y_3,\ldots,y_n$ such that the pair $(x_i,y_i)$ represents the location of a city $i$. Assume there is no straight line that goes through all ...
0
votes
1answer
5 views

Increasing order of fourier coefficients on the boolean cube

Given a function $f:\{0,1\}^n\rightarrow \{0,1\}$, is it true that for any $S,T\subseteq[n]$, such that $S\cap T =\phi$, then $\hat{f}(S\cup T)\leq \hat{f}(S)$? It seems so to me cause, if if you just ...
3
votes
0answers
40 views

Examples of calculus on “strange” spaces

I am interested in examples of calculus on "strange" spaces. For example, you can take the derivative of a regular expression[1][2]. Also the concept extends past regular languages, to more general ...
10
votes
2answers
2k views

An efficient way to determine if two context free grammars are equivalent?

I'm wondering if there's an efficient way of checking to see if two context free grammars are equivalent, besides working out "test cases" by hand (ie, just trying to see if both grammars can generate ...
2
votes
0answers
23 views

Proof of equality of least fixed point of two continuous function

The question is simple: given a set U, a continuous function (Scott continuity) $f \colon \mathcal{P}(U) \to \mathcal{P}(U)$ and function $g(X) := f(f(X))$, prove that $g$ is continuous and its least ...
0
votes
1answer
62 views

Construct grammar $\ a^i b^j c^{i+j} b^j a^i $

I've been going through old exams at my college and I found this problem that I haven't yet been able to solve. Construct grammar defined on the alphabet $\ \{{a, b, c}\} $ which generates strings of ...
0
votes
1answer
422 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
21 views

How to compute sine function within certain precision

I know that there exists CORDIC algorithm, but CORDIC algorithm contains component $\arctan 2^{-i}$, which needs to be looked up. I do not know how this leads to the precision that is advertised by ...
0
votes
0answers
30 views

Maxima CAS and programmatically defining a function with a variable number of arguments. -?

This is a very simplified question of what I had asked. In Maxima, how can I include a for-loop counter in the left-hand side of an assignment, e.g. ...
3
votes
0answers
18 views

NP-hardness of solving congruence equations in several variables

You are given the following equation modulo $N$ (where the $\beta_i$'s are given integers modulo $N$, and the $x_i$'s are unknown integers modulo $N$): $$\beta_1x_1 = \beta_2 x_2 = \ldots = \beta_l ...
0
votes
0answers
14 views

FFT differential equations

Given a generical differential equation what is the procedure to solve it using fft command. Can anyone explain me how to do it? For example: $$\frac{d^2y}{dt^2}+10\cdot \frac{d\:y}{dt}=-5\cdot ...
1
vote
1answer
58 views

Python Integer Game

Jacob and Vicky play the fun game of multiplication by multiplying an integer p by one of the numbers 2 to 9. Jacob always starts with p = 1, does his multiplication, then Vicky multiplies the number, ...
1
vote
1answer
32 views

error bound in function approximation algorithm

Suppose we have the set of floating point number with "m" bit mantissa and "e" bits for exponent. Suppose more over we want to approximate a function "f". From the theory we know that usually a ...
3
votes
3answers
8k views

Question regarding Context Free Grammar exercises

I'm working on the exercises in "An Introduction to Formal Languages and Automata" 4th Ed textbook by Peter Linz. Since there are too few answers given in the back of the book, I wasn't able to check ...
2
votes
1answer
39 views

Understanding difference between reduction methods

In Sipser's book "Introduction to the theory of computation" there are 2 methods for proving that $\rm HALT_{TM}$ is undecidable by a reduction from $\rm A_{TM}$ I am trying to figure out the ...
0
votes
1answer
383 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 ...
2
votes
2answers
70 views

which branch of computer science is most math intensive?

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 ...
15
votes
4answers
3k views

Ackermann Function primitive recursive

I am reading the wikipedia page on ackermann's function, http://en.wikipedia.org/wiki/Ackermann_function And I am having trouble understanding WHY ackermann's function is an example of a function ...
8
votes
5answers
7k views

Great Book on Probability and Statistics (for Computer Scientists)

I'm a Computer Science sophomore and we're studying Probability and Statistics (fundamentals and all). The teacher recommends a book which I don't like since it does not even try and explain ...
0
votes
0answers
18 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 ...
1
vote
1answer
65 views

How many non decreasing sequence of length k is possible?

If we have a set like this { 1A ,2A ,2B, 3A, 3B, 3C}, how many non decreasing sequence is possible, such that number in left is less than number in right of length k? i.e, Length = 2 then the ...
4
votes
2answers
277 views

What is the fastest computational graph theory package?

What is the fastest computational graph theory package with respect to executing algorithms and computing graph theoretic data? I am aware of this related question, which requests graph theory ...
1
vote
0answers
16 views

periodic boundary conditions and the FEM

I am trying to set up the mass matrix for a 1D system which I want to solve using finite elements. So the mass matrix is defined as $$ M = \int{NN^T}dL, $$ where $N$ is the finite element linear ...
0
votes
0answers
20 views

How to get samples of different paths?

Say I have a "semi" directed, weighted, graph (some edges are undirected, some are directed). Consider two nodes, A and B. Consider the set of all paths that take me from node A to node B. I ...
0
votes
0answers
17 views

Optimization approaches and algorithms for highly dimensional complex functions.

I am searching for an approach or algorithm that is best suited for finding a minimum or maximum in a n-dimensional function. All variables are complex, the function itself returns a real number. The ...
4
votes
3answers
6k views
2
votes
0answers
25 views

Stuck in a Context-Free Proof

I am trying to work through the pumping lemma for CFLs. $L_1 = \{0^n 1^{mn} : n,m \in \Bbb N\}$ I am trying to find a contradiction. I have currently chosen $z= 0^p1^{2p}$ to be my string. Then ...
0
votes
1answer
222 views

Basic idea of proof

I am trying to understand the proof that the expected running time of quicksort is $O(n \log n)$. Could you maybe explain me the basic idea? I am confused right now. EDIT: Suppose that we use the ...
1
vote
1answer
778 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 ...
5
votes
3answers
332 views

How to encode matrices uniquely

Given a square matrix $A=[a_{ij}]_{n \times n}$, an operation $swap(A, i, j)$ is defined to swap row $i$ and $j$ of $A$ and do the same thing with the corresponding columns. For example, in the ...
0
votes
0answers
18 views

Cost of an algorithm or an operation

In my notes there is the following: $G$: finite abelian group If $|G|=m$ elements we need $\lfloor \log_2 m \rfloor+1$ digits to represent all the elemets of the group. For example, ...
0
votes
0answers
16 views

How to compute the logarithm of a computable number

Let's say you have a computable number $x>0$. $\ln(x)$ is computable as well. Given the computability of $x$, what is a computation for $\ln(x)$. I am using the definition where $a$ is computable ...
0
votes
1answer
24 views

Calculating an Intensity Centroid

I am trying to understand the theory behind calculating an Intensity Centroid (image processing), in particular defining moments. As defined by Rosin 1: $m_{pq}=\underset{x,y}{\Sigma}x^py^qI(x,y)$ ...
0
votes
1answer
71 views

Computability problems — can't solve

I have a pair of exercises I can't solve (tomorrow I'll have a test). I need some kind of solution so I can apply it to other exercises...thanks to all! In the following $W_n$ means the domain of the ...
3
votes
1answer
113 views

A few questions about KSVD algorithm (dictionary learning) in a paper

To learn more about dictionary learning, I am currently trying to understand the concept in detail and to do so, I've found the following paper quite informative: KSVD: an algorithm for designing ...
1
vote
0answers
10 views

is the suggested PDA correct?

so i have this language $$ L = \{x^{i} v^{j} z^{j+2} w^{k} v^{i+k} | i,j,k \ge 0 \}$$ i made this PDA for it . states $ = \{q_0 ... q_5 , final\} $ alphabet $= \{ x,v,z,w \}$ stack ...
8
votes
3answers
583 views

Does the recursion theorem give quines?

Wikipedia claims that the recursion theorem guarantees that quines (i.e. programs that output their own source code) exist in any (Turing complete) programming language. This seems to imply that one ...
0
votes
1answer
38 views