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

4
votes
2answers
272 views

What are BesselJ functions?

I solved an integration on mathematica which gives BesselJ functions and some other terms. I explored mathematica help and google but could not understand the difference between different types of ...
11
votes
2answers
8k views

Reed Solomon Polynomial Generator

I am developing a sample program to generate a 2D Barcode. And i am using reed solomon error correction code. By Going through this article i am developing the program. But i couldn't understand how ...
11
votes
3answers
7k views

Simplifying Catalan number recurrence relation

While solving a problem, I reduced it in the form of the following recurrence relation. $ C_{0} = 1, C_{n} = \displaystyle\sum_{i=0}^{n - 1} C_{i}C_{n - i - 1} $ However https://en.wikipedia.org/...
2
votes
1answer
1k views

CRC computation

I would like to understand the CRC computation using CCITT CRC-16 $x^{16} + x^{12} +x^{5} +1$. I was able to successfully implement it in a program but I would like to understand the computation ...
13
votes
1answer
6k views

Calculating Distance of a Point from an Ellipse Border

I'm thinking about using oriented ellipses to represent curves (dents/bumps etc.) in my physics engine, and have a few questions about working with them: What methods are there to finding the ...
3
votes
3answers
141 views

$2x_1 + 2x_2 + \cdots + 2x_6 + x_7 = N$

How do I find the number of integral solutions to the equation - $$2x_1 + 2x_2 + \cdots + 2x_6 + x_7 = N$$ $$x_1,x_2,\ldots,x_7 \ge 1$$ I just thought that I should reduce this a bit more, so I ...
1
vote
2answers
1k views

Convert Equilateral triangle to Isosceles triangle

Let an equilateral triangle have the length of each side an integer $N$. I need to find if it is possible to transform the triangle keeping two sides fixed and alter the third side such that it still ...
160
votes
14answers
37k views

Is computer science a branch of mathematics?

I have been wondering, is computer science a branch of mathematics? No one has ever adequately described it to me. It all seems very math-like to me. My second question is, are there any books about ...
46
votes
2answers
1k views

Computation with a memory wiped computer

Here is another result from Scott Aaronson's blog: If every second or so your computer’s memory were wiped completely clean, except for the input data; the clock; a static, unchanging ...
18
votes
4answers
5k 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 ...
15
votes
4answers
14k views

Representing IF … THEN … ELSE … in math notation

How do I correctly represent the following pseudocode in math notation? EDIT1: Formula expanded. EDIT2: Clarification. (a,b) represents a line segment on a 1D line. a <= b for each segment. The ...
10
votes
4answers
1k views

Is a “network topology'” a topological space?

Is there any connection between the computer science phrase "network topology" and the mathematical notion of a topological space (or, is there any other way to connect "network topologies" with ...
7
votes
4answers
2k views

Why isn't this a regular language?

I'm stuck as to figuring out why $L_1$={$n^p$ | $p$ = a prime number} is not a regular language but $L_2$={$n^p$ | $p$ = a prime number bounded by some fixed number f} is. I can see that $L_2$ is a ...
6
votes
1answer
372 views

Rank of an interesting matrix

Lets define: $U=\left \{ u_j\right \} , 1 \leq j\leq N= 2^{L},$ the set of all different binary sequences of length $L$. $V=\left \{ v_i\right \} , 1 \leq i\leq M=\binom{L}{k}2^{k},$ the set of ...
7
votes
2answers
1k views

Distance between a point and a m-dimensional space in n-dimensional space ($m<n$)

I am trying to find a method with a low computational cost to compute the distance of a point $P$ and a space $S$ that is defined by the origin $O$ and $m$ vectors $v_1, v_2, ..., v_m$ in an $n$-...
3
votes
0answers
209 views

Execution time of function

At the algorithm SELECT, there is the following step: ...
3
votes
2answers
7k views

Linear Homogeneous Recurrence Relations and Inhomogenous Recurrence Relations

I'm having some difficulty understanding 'Linear Homogeneous Recurrence Relations' and 'Inhomogeneous Recurrence Relations', the notes that we've been given in our discrete mathematics class seem to ...
1
vote
1answer
217 views

Rank of a graph matrix

$G$ is a bipartite graph with $2m$ nodes on the left $(u_0..u_{2m-1})$, and $2^{m}$ nodes on the right $(v_0..v_{2^{m}-1})$. There is an edge (connection) between $u_i$ and $v_j$ iff $(i+1)$'th ...
1
vote
1answer
1k views

Show $\{0^m1^n | m \neq n\}$ is not regular

I'm going through Michael Sipser's Introduction to the Theory of Computation, and in one of the exercises we are asked to show that $\{0^m1^n | m \neq n\}$ is not a regular language (i.e. is not ...
1
vote
1answer
242 views

Floating point arithmetic

How can I prove that : a real number has a finite representation in the binary system if and only if it is of the form $$\pm \frac{m}{2^n}$$ where n and m are positive integers.
15
votes
3answers
6k views

What are NP-complete problems and why are they so important?

I keep hearing questions about whether something is NP-complete, but they never really mention what it is. Why do people care so much about NP-complete problems?
17
votes
5answers
982 views

What interesting open mathematical problems could be solved if we could perform a “supertask” and what couldn't?

If we had a computer that could perform a countably infinite number of steps of a Turing machine, what currently open problems could we solve? I guess a lot of number theory problems could be solved ...
7
votes
3answers
9k views

Lower bound for finding second largest element

In a recent discussion, I came across the idea of proving a lower bound for the number of comparisons required to find the largest element in an array. The bound is $n - 1$. This is so because the set ...
8
votes
6answers
10k 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 ...
19
votes
2answers
24k views

Recognizable vs Decidable

What is difference between "recognizable" and "decidable" in context of Turing machines?
17
votes
6answers
907 views

What are the theorems of mathematics proved by a computer so far?

By theorems, I mean the ones you can find in an undergraduate course of mathematics, not the ones you can find in a textbook of automated proofs. I mean by "proved by a computer" that an existing ...
12
votes
2answers
447 views

State of the progess of the automated proof checking

I recently came across a concept of automated proof checking. I am very intrigued by the idea, that in the future all the proofs could be verified by a computer. Moreover, some proofs were already ...
10
votes
3answers
1k views

Proving the Riemann Hypothesis without revealing anything other than you proved it

Consider the following assertion from Scott Aaronson's blog: Supposing you do prove the Riemann Hypothesis, it’s possible to convince someone of that fact, without revealing anything other ...
11
votes
3answers
327 views

Why isn't NP = coNP?

Suppose a language L is in NP. I think that means a nondeterministic Turing machine M can decide it in polynomial time. But then shouldn't it be in co-NP, because can't we define a new Turing machine ...
9
votes
2answers
3k views

Fast Matlab Code for hypergeometric function $_2F_1$

I am looking for a good numerical algorithm to evaluate the hypergeometric function $_2F_1$ in Matlab (hypergeom in Matlab is very slow). I looked across the ...
6
votes
4answers
4k views

Example of a not recursively enumerable set $A \subseteq \mathbb{N}$

Can someone give me an example if a not recursively enumerable set $A \subseteq \mathbb{N}$ ? I came up with this question, when trying to show, that there exist partial functions $f: \mathbb{N} \...
5
votes
4answers
12k views

Intersection of two deterministic finite automata?

I'm trying to solve a problem where I have to create a DFA for the intersection of two languages. These are: $$\{s \in \{{\tt a}, {\tt b},{\tt c}\}^\ast : \mbox{every ${\tt a}$ in $s$ is ...
7
votes
2answers
696 views

What is the best way to factor arbitrary polynomials

I am currently working on a Computer Algebra System and was wondering for suggestions on methods of finding roots/factors of polynomials. I am currently using the Numerical Durand-Kerner method but ...
5
votes
2answers
4k views

How to prove the optimal Towers of Hanoi strategy?

In the towers of Hanoi game, how do we know that we have the optimal algorithm for solving it? I thought about this and it seemed like any deviation from the standard strategies would be putting you ...
6
votes
2answers
354 views

Relatively prime property verification

I am reading a computer science puzzles book. And I get the following question - "You have a five quart jug, a three quart jug and unlimited supply of water. How would you come up with exactly four ...
4
votes
1answer
421 views

Is there a polynomial-time algorithm to find a prime larger than $n$?

Is there a polynomial-time algorithm to find a prime larger than $n$? If Cramér's conjecture is true, we can use AKS to test $n+1$, $n+2$, etc. until the next prime is found, and this method will ...
3
votes
3answers
937 views

Is the language of all strings over the alphabet “a,b,c” with the same number of substrings “ab” & “ba” regular?

Is the language of all strings over the alphabet "a,b,c" with the same number of substrings "ab" & "ba" regular? I believe the answer is NO, but it is hard to make a formal demonstration of it, ...
2
votes
1answer
280 views

Restricted read twice BDDs and context free grammars

Several papers give poly-time algorithms for constrained paths on labelled graphs, e.g. [1] Quote: Given an alphabet Σ, a (directed) graph G whose edges are weighted and Σ-labeled, and a formal ...
2
votes
1answer
96 views

Are sets and symbols the building blocks of mathematics?

A formal language is defined as a set of strings of symbols. I want to know that if "symbol" is a primitive notion in mathematics i.e we don't define what a symbol is. If it is the case that in ...
2
votes
1answer
6k views

Rounding Percentages

Okay so I have been having a problem and would really appreciate any help. I have posted a table below with the aim of making this as simple/precise as possible. ...
2
votes
2answers
867 views

Context free languages closure property $\{a^n b^n : n\geq 0\} \cup \{a^n b^{2n}: n\geq 0\}$

I have been working on the following two problems: 1) Given any context free language L, form a new language by taking symbols at the odd positions, i.e. $w=a_1a_2\dots a_n \mapsto w'=a_1 a_3 a_5 \...
1
vote
3answers
219 views

Let X be a subset of {1,2,…,2014}…

Let X be a subset of {1,2,...,2014}. How would I show that if |X| ≥ 64, then there exist at least two different pairs {x,y} and {u,v} of distinct elements of X which |x-y|=|u-v|? I'm not too sure ...
0
votes
3answers
6k views

Prove that the set of palindromes are not regular languages using the pumping lemma.

Firstly I pick a language $xyz$ where $x = \epsilon$, $y = (abb)^{k}$, $z = (bba)^{k}$ where $|y| \ge$ the number of states in the automaton representing my language. Then $xyz = (abb)^k(bba)^k$ is a ...
6
votes
1answer
283 views

Numbers as sum of distinct squares

Yesterday Polish Olympiad of Information Science ended, one of the questions was purely mathematical, Squares (PL). In the task, we have defined square ...
3
votes
2answers
134 views

Computing the $n^{\textrm{th}}$ permutation of bits.

I've seen this post about the $n^{\textrm{th}}$ permutation of a set but that is not what I need. If you have a bit string (ones and zeros only) there are algorithms to quickly permute the NEXT ...
2
votes
2answers
681 views

How to determine which amounts of postage can be formed by using just 4 cent and 11 cent stamps?

Problem: a) Determine which amounts of postage can be formed using just 4 cent stamps and 11 cent stamps. b) Prove your answers to a using strong induction. My work: (I am only working on part a for ...
2
votes
2answers
171 views

How to find a function that is the upper bound of this sum?

The Problem Consider the recurrence $ T(n) = \begin{cases} c & \text{if $n$ is 1} \\ T(\lfloor(n/2)\rfloor) + T(\lfloor(n/4)\rfloor) + 4n, & \text{if $n$ is > 1} \end{cases}$ A. Express ...
2
votes
2answers
132 views

Minimum queens to reach $8 \times 8$ squares as a graph problem

A homework problem asks What is the minimum number of queens to reach all squares on a $8 \times 8$ chess board? We are expected to solve this by somehow casting the problem as a graph problem (...
1
vote
2answers
3k views

Prove that if a|b and b|c then a|c using a column proof that has steps in the first column and the reason for the step in the second column.

Let $a$, $b$, and $c$ be integers, where a $\ne$ 0. Then $$ $$ (i) if $a$ | $b$ and $a$ | $c$, then $a$ | ($b+c$) $$ $$ (ii) if $a$ | $b$ and $a$|$bc$ for all integers $c$; $$ $$ (iii) if $a$ |$b$ and ...
1
vote
2answers
265 views

Huffman Encoding Proof Probability and Length

If the frequency of symbol i is strictly larger than the frequency of symbol j, then the length of the codeword for symbol i is less than or equal to the length of the codeword for symbol j. I ...