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
13 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
39 views

Usefulness of prime numbers as Threading Timeouts in programming [on hold]

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
18 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
29 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 ...
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
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 ...
3
votes
0answers
41 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 ...
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 ...
2
votes
1answer
41 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 ...
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
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 ...
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
15 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, ...
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. ...
1
vote
1answer
33 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 ...
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 ...
2
votes
2answers
74 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 ...
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
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 ...
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 ...
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 ...
2
votes
0answers
26 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
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 ...
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 ...
0
votes
1answer
42 views

Fractional Knapsack- explanation

The following algorithm is given: ...
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 ...
4
votes
2answers
111 views

Help with deriving an absolute strategy (very fun if anything)

My friend and I are trying to figure out a solution or even a best path to figuring out a certain win strategy to this game. This game that my friend made, calling it the number game for short, is ...
0
votes
0answers
11 views

Prove that $ALL_{CFG}$ is undecidable by reducing from PCP

I'm studying for a Computability exam that I have in a few weeks, and have come across this question which I'm having a hard time solving: Prove that $ALL_{CFG}=\left\{ \left\langle ...
0
votes
1answer
19 views

Time complexity function

I'm not sure I should post this on the Mathematics website or the Computer science website of Stack Exchange. If I'm wrong I will replace my question. So I'm trying to calculate the time complexity ...
0
votes
0answers
25 views

Bitwise Operations and the Naming Convention of their Operators

So I just recently came across a bitwise operation on StackOverflow which shifts the bits in a binary number to the right while zero-filling from the left. The left side zero-filling overwrites the ...
1
vote
2answers
38 views

Alternate plain English algorithm for Towers of Hanoi

There are four plain English algorithms for the Towers of Hanoi Puzzle available on Wikipedia, but when I was first solving the puzzle, I came up with an algorithm that is different from any of the ...
2
votes
0answers
39 views

Neighbor-full partition of $\{0,1\}^n$

What is the partition of $\{0,1\}^n$ with each set connected and neighboring each other that has the maximum number of elements? (which we call $k(n)$) We say $A$ and $B$ are neighbors if their ...
0
votes
0answers
24 views

Clique Percolation Method calculation

According to Clique Percolation Method as shown in Wikipedia I could not understand why the result of Graph1 is Graph2 if we assign k to be=2, According to the definition of CPM, then the cluster ...
4
votes
3answers
62 views

WolframAlpha has a different answer for a definite integral, why?

So I ran into this contradiction and I'd appreciate if someone could help explain what is happening: So when i perform the following integral on paper: $$\int_{-1}^1(\sqrt[3]{x} -2)\;dx \; = [\frac ...
2
votes
1answer
43 views

How to understand or derive the formula $Mantissa$ $bits$ $/$ ${log_2}$ $10$ = $Decimal$ $digits$ $of$ $precision$?

I asked a question a couple days ago about floating point precision on stackoverflow called, "Is floating point precision mutable or invariant?" and I received the following response. The formula ...
2
votes
1answer
29 views

pumping lemma for CFL vs pumping lemma for regular languages

Is the pumping lemma for context free languages a generalization of the pumping lemma for regular languages (for instance if we set $u=\epsilon, v=\epsilon$ we can then relate $wx$ in the pumping ...
0
votes
1answer
30 views

Quick question on DFA

I'm asked to list all DFA over the alphabet sigma = {0} such that the set of states is {s0, s1}, for which the initial state is s0 and the set of accept states is either {s0} or {s1}. And also asked ...
1
vote
0answers
33 views

Formal (Mathematical) Definition of N-Clan?

I tried many times to find a formal definition for the following important concepts in Graph Theory and Network Analysis: 1) N-Clique. 2) N-Clan. 3) K-Plex. 4) K-Core. Reference , but ...
1
vote
0answers
9 views

What is the maximal possible 'non-empty' K-Core of a Graph G

Since any graph can be extracted to find K-Core easily, since finding K-Core is Pronominal problem, what is the maximal possible 'non-empty' K-Core of a Graph G. Is it k+1 ? or what exactly ?