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.

learn more… | top users | synonyms

5
votes
3answers
525 views

Are computers going to be able to discover and prove important mathematics theorems? [closed]

Are computers going to be able to discover and prove important mathematics theorems within, say, 20 years?
25
votes
6answers
3k views

Is the set of all valid C++ programs countably infinite?

I have heard that the set of valid programs in a certain programming language is countably infinite. For instance, the set of all valid C++ programs is countably infinite. I don't understand why ...
5
votes
5answers
686 views

Can a polynomial size CFG over large alphabet describe a language, where each terminal appears even number of times?

Can a CFG over large alphabet describe a language, where each terminal appears even number of times? If yes, would the Chomsky Normal Form be polynomial in |Σ| ? EDIT: What about a language where ...
4
votes
2answers
54 views

Question about queues

A queue is implemented with a sequence $Q[1\ldots n]$ and two indices $\def\head{\operatorname{head}}\head[Q]$ and $\def\end{\operatorname{end}}\end[Q]$ such that the elements of the queue are the ...
4
votes
3answers
218 views

Deciding equivalence of regular languages

Given two regular expressions $R$ and $S$ on an alphabet $\Sigma$ it is possible to decide their equivalence as follows: build two finite automata $M_R$ and $M_S$ such that $L(R) = L(M_R)$ and $L(S) ...
4
votes
2answers
8k views

What is the 3SAT problem?

I don't get the 3SAT problem. Can someone explain the 3SAT problem as if I were 5 years old, ideally with examples? Thanks!
8
votes
1answer
380 views

Throwing balls into $b$ buckets: when does some bucket overflow size $s$?

Suppose you throw balls one-by-one into $b$ buckets, uniformly at random. At what time does the size of some (any) bucket exceed size $s$? That is, consider the following random process. At each of ...
8
votes
5answers
396 views

Is there any mathematical operation on Integers that yields the same result as doing bitwise “AND”?

I'll provide a little bit of a background so you guys can better understand my question: Let's say I have two positive, non-zero Binary Numbers.(Which can, obviously, be mapped to integers) I will ...
7
votes
1answer
492 views

What is the best way to self-study GAP?

Background: This year I'll do another Group Theory course ( Open University M336 ). In the past I have used Mathematica's AbstractAlgebra package but (although visually appealing ) this is no longer ...
6
votes
2answers
123 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 ...
6
votes
2answers
716 views

Finding the 2,147,483,647th prime number

In computer science an array is indexed by an integer (int). Unlike in mathematics, the computer science integer (int) has a ...
5
votes
2answers
862 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 ...
5
votes
2answers
381 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 ...
4
votes
2answers
474 views

How to calculate π [duplicate]

Possible Duplicate: Simple numerical methods for calculating the digits of Pi How do people/computers calculate π? Im sure long ago, someone just took a measurement of the circumference of ...
4
votes
1answer
5k views

Degeneracy in Linear Programming

Consider the standard form polyhedron, and assume that the rows of the matrix A are linearly independent. $$ \left \{ x | Ax = b, x \geq 0 \right \} $$ (a) Suppose that two different bases lead to ...
3
votes
4answers
5k 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 ...
3
votes
2answers
208 views

Alternate expression for the following function

So if the following function is evaluated with the floating-point arithmetic, we get poor results for certain range of values of $x$. Therefore, I need to provide an alternate function that can be ...
2
votes
3answers
88 views

Combination Problem Understanding

How many ways can a Doctor go to the Hospital on $5$ days of January (which has $31$ days) such that no two visits are on consecutive days? I think the solution is: $\displaystyle\binom{27}{5}$ But ...
2
votes
5answers
10k views

Merge Sort time complexity analysis

How can I prove that $T(n) = 2T(n/2) + n$ is $O(n \log n)$ ?
1
vote
1answer
320 views

A regular expression for the words that don't contain the sequence $ab$ over $\{a,b,c\}$

The following is an exercise in a book I am reading: Let $\Sigma=\{a,b,c\}$, define $L$ to be the language of all words over $\Sigma$ that do not contain $ab$ as a sub-word. Find a regular ...
1
vote
1answer
240 views

Complexity of verifying proofs

My question can be read on many levels and so I welcome answers to any reading. The general question is: What is the computational complexity of verifying a proof? One way of looking at a ...
0
votes
0answers
28 views

Adversarial Secret Sharing [duplicate]

Suppose that I want to break up a secret into shares such that any set of k people can recover the secret, but I’m also worried that some people might be dishonest and may lie about the secrets they ...
6
votes
2answers
458 views

What requirements should a CRC polynomial satisfy?

What requirements should a CRC polynomial of a given degree satisfy to make the CRC catch a maximum of errors? edit I'm talking about GF(2) polynomials. As an example of the kind of requirements ...
5
votes
2answers
207 views

NP-complete: One proof to rule them all

To prove a decision problem $C$ is in NP-complete, 2 things need to be shown: There is a polynomial verification for $C$ solution. Every problem in NP is reducible to $C$ - You can solve all the ...
4
votes
3answers
734 views

Formally prove that $\Theta(\max(f,g)) = \Theta(f+g)$

I am having a hard time proving that $\Theta(\max(f,g)) = \Theta(f+g) $ where $(f+g)(n) = f(n) + g(n) $ and $(\max{f,g})(n) = \max(f(n), g(n))$ I know that $\Theta$ is the combination of the ...
4
votes
1answer
194 views

Reasoning the calculation of the Hilbert's distance

I'm not a mathematician, I'm a computer science student, and I'm attending to a course called Advanced Functional Programming. There's this homework where I need to implement the Hilbert R-tree data ...
4
votes
1answer
482 views

Max-turn hamiltonian path in square grids

Given an $n \times n$ square grid graph, what is the maximum number of turns a Hamiltonian path can take?
4
votes
2answers
3k views

What makes a context free grammar ambiguous?

What makes a context free grammar ambiguous?
4
votes
3answers
6k views

Reduction from Hamiltonian cycle to Hamiltonian path

I'm looking for an explanation on how reducing the Hamiltonian cycle problem to the Hamiltonian path's one (to proof that also the latter is NP-complete). I couldn't find any on the web, can someone ...
3
votes
0answers
31 views

What is the desirable function identification when setting up arrows in the category of types?

My question is which functions can not be allowed in a statically typed programming language, so that the "canonical" category is less coarse than what you get if you define it's arrows to be ...
3
votes
1answer
93 views

Is this language decidable?

Is this language decidable? $$\{x\mid \text{$x$ is the code of a Turing machine that always halts on $y$ in less than $y^3$ steps}\}$$ I think it is, because it halts in a finite number of ...
3
votes
1answer
244 views

What is the complexity of computing the minimum distance between two convex polyhedra that both have $n$ faces?

EDIT: (in response to what deinst said) sometimes using a sledgehammer for some menial task is rather convenient - especially if it also has the complexity $O(n)$ (which is what my question is about) ...
3
votes
2answers
382 views

Asymptotically optimal algorithms

Suppose one has an algorithm to solve a problem using at most f(n) computations with size of input n. How to prove, if such is the case, that this algorithm is the fastest possible for solving this ...
3
votes
2answers
194 views

Prove or refute that $\frac{t^a-1}{t^b-1}$ has more than 100 digits if $a \mod b \neq 0$

I'm a computer science student from Mexico and I have been training for the ICPC-ACM. So one of this problems called division sounds simple at first. The problem is straight for you have and 3 ...
3
votes
1answer
379 views

An “uncountable” Turing Machine?

A proof of the insolubility of the halting problem is a diagonalization, which I'm sure most of you have seen. I am not very familiar with set theory, but it strikes me as similar to Cantor's proof of ...
3
votes
2answers
323 views

How to solve recurrence relations with emphasis on algorithmic complexity

I am having trouble solving recurrence relations, probably because I am missing the basics. Is there any web reference/book I can read to help me cover the basics? I watched some lectures and read ...
3
votes
1answer
278 views

Big-oh for function of two variables

Is it true that $O(M^3 + NM^2) \, = \, O(M^3 + N)$, where $M$ and $N$ are variables of the function?
2
votes
3answers
1k views

Time complexity of binary multiplication?

Using the grade school method of multiplying two binary numbers takes $O(n^2)$ time, where $n$ is the length of the number in bits. Why is this true?
2
votes
2answers
234 views

Shortest paths from $s$ by weight which contain even number of edges

Given a directed graph $G=(V,E)$, and a vertex $s\in V$, for every edge there's an integer weight $w(e)$ (positive or negative), I need to find an algorithm such that for every vertex $v \in V$ it ...
2
votes
4answers
429 views

Halting problem on finite set of programs

As I understand the halting problem, it imply the fact that there doesn't exist one program which can answer the halting problem for every computable program and it rely on Cantor diagonalization to ...
2
votes
1answer
103 views

maximizing number of 4s times number of 7s in decimal representation

$F_4(X)$ be the number of digits 4 in the decimal representation of $X$, and $F_7(X)$ be the number of digits 7 in the decimal representation of $X$. We have to find largest product $F_4(X)\cdot ...
2
votes
3answers
5k views

Inverse of transformation matrix

I am preparing for a computer 3D graphics test and have a sample question which I am unable to solve. The question is as follows: For the following 3D transfromation matrix M, find its inverse. Note ...
2
votes
1answer
392 views

Form or asymptotic behaviour of $T(n) =2T(n-1)+n$

$T(n) =$ if $n=1$, then time execution is $1$, if $n \geq 2$ then $2T(n-1)+n$ The options are: $T(n) = 2^{n+1} - n - 2$ $T(n) = O(n2^n)$ $T(n) = \Omega(n)$ $T(n) = \theta(2^n)$ Thanks.
2
votes
1answer
289 views

To officially be recursion, must there be a base case?

In this Python code, the function f is defined, which then immediately calls itself: def f(): f() It's not very complicated, the first line defines the ...
2
votes
3answers
645 views

calculating unique value from given numbers

let's say I have some (n) random numbers 12, 13, and 18. I want to calculate some unique value from these three such that if I change their order 13, 12, 18 or 18, 12, 13..whatever order they are in, ...
2
votes
4answers
134 views

Regular expression $baa \in a^*b^*a^*b^*$: is that true or false?

Could someone please guide me how to go about solving this problem? $$ baa \in a^*b^*a^*b^* .$$ The question asks whether string $baa$ is an element of $a^*b^*a^*b^*$ (in other words a set of any ...
2
votes
2answers
326 views

Step function for greaterthan

I need to avoid using an if statement that does a $\geq$ comparison, (I'm writing HLSL code for the xbox). I need a function such that $f(x, y) = 0$ when $x < y$ and $f(x,y)=1$ when $x \geq y$. ...
1
vote
1answer
59 views

Merge two or more cubic Bézier curves for optimization

I am looking for an algorithm which can merge several cubic Bezier curves. For instance, I have a lot of cubic Bezier that are joined to form a poly-Bezier curve. The idea is to merge dynamically some ...
1
vote
1answer
73 views

Solving recurrence relation: f(n) = 3f(n/2) - 2f(n/4) | f(2) = 5, f(1) = 3

f(n) = 3f(n/2) - 2f(n/4) | f(2) = 5, f(1) = 3 I have attempted to solve it by letting n = 2k f(2k) = 3f(2k-1) - 2f(2k-2) Then set S(k) = f(2k) S(k) = 3*S(k-1) - 2*S(k-2) ...
1
vote
1answer
67 views

Let $L_{UIUC}$ = $\{ \langle M \rangle$ : $L(M)$ contains the string $UIUC\}$. Prove that $L_{UIUC}$ is undecidable.

Been stumped as to why the following proof works. Note: I have taken this proof directly from here. Proof by reduction from $A_{TM}$. Suppose that $L_{UIUC}$ were decidable and let $R$ be a Turing ...