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

12
votes
3answers
763 views

Twenty questions against a liar

Here's one that popped into my mind when I was thinking about binary search. I'm thinking of an integer between 1 and n. You have to guess my number. You win as soon as you guess the correct number. ...
15
votes
6answers
3k views

The Practical Implication of P vs NP Problem

Although whether $$ P = NP $$ is important from theoretical computer science point of view, but I fail to see any practical implication of it. Suppose that we can prove all questions that can be ...
11
votes
5answers
994 views

Why is convexity more important than quasi-convexity in optimization?

In the mathematical optimization literature it is common to distinguish problems according to whether or not they are convex. The reason seems to be that convex problems are guaranteed to have ...
10
votes
2answers
264 views

Applications of Geometry to Computer Science

How is differential geometry (or any type of theoretical math) being used in computer science? Any research I have done on this topic leads me to some sort of applied math concept. I know that there ...
6
votes
3answers
756 views

Is learning haskell a bad thing for a beginner mathematician?

Haskell is a programming language which uses some concepts from category theory like functor, monad, etc. My question is: Learning intuitive concepts about category from Haskell will ruin my intuition ...
11
votes
3answers
274 views

What is necessary to exchange messages between aliens? [closed]

Lets assume that two extreme intelligent species in the universe can exchange morse code messages for the first time. A can send messages to B and B to A, both have unlimited time, but they can not ...
10
votes
3answers
591 views

Solving P vs NP with computer

Is it possible to build a computer program that would (eventually) bring a solution to the P vs. NP question?
10
votes
1answer
10k views

Recognizable vs Decidable

What is difference between "recognizable" and "decidable" in context of Turing machines?
8
votes
4answers
7k 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 ...
6
votes
1answer
384 views

Importance of Constructible functions

A function $f$ is called fully time-constructible if there exists a Turing machine $M$ which, given a string $1^n$ consisting of $n$ ones, stops after exactly $f(n)$ steps. Analogously, we can call a ...
5
votes
3answers
597 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?
4
votes
2answers
918 views

Learning Proofs (for Computer Science)

Harvard's math curriculum, for freshmen, is divided into 4 classes beyond the BC Calculus level, Math 21, 23, 25 and 55. Math 21 is your classic plug-and-chug multivariable calculus and linear algebra ...
26
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 ...
7
votes
2answers
11k 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!
5
votes
1answer
6k 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 ...
5
votes
5answers
692 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
3answers
264 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
4answers
6k 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 ...
2
votes
1answer
82 views

Combinatorics/Task Dependency

Here is a competitive programming question: You have a number of chores to do. You can only do one chore at a time and some of them depend on others. Suppose you have four tasks to complete. For ...
1
vote
3answers
93 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 ...
12
votes
3answers
325 views

Etymology of “topological sorting”

This may be a dumb question, but what's "topological" about topological sorting in graph theory? I thought topology was related to geometry and deformations.
8
votes
1answer
422 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
416 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
532 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
161 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
786 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
1k 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 ...
4
votes
2answers
498 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
251 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
5answers
12k views

Merge Sort time complexity analysis

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

Prove that Y is not context free.

2.42 Let $$Y = \{w\mid \text{$w=t_1\#t_2\#\cdots\#t_k$ for $k \ge 0$, each $t_i \in 1^*$, and $t_i \ne t_j$ whenever $i \ne j$}\}.$$ Here $\Sigma = \{1,\#\}$. Prove that $Y$ is not context free. ...
3
votes
2answers
2k views

Finite automaton that recognizes the empty language $\emptyset$

Since the language $L = \emptyset$ is regular, there must be a finite automaton that recognizes it. However, I'm not exactly sure how one would be constructed. I feel like the answer is trivial. ...
3
votes
2answers
218 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
2answers
63 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 ...
2
votes
1answer
368 views

Polynomial complexity algorithm of partition problem with sets of equal size

Partition problem is well known ( http://en.wikipedia.org/wiki/Partition_problem ). Let's add an additional condition: sizes of both sets should be equal. Is there a pseudo-polynomial solution to ...
1
vote
1answer
352 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
245 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
2answers
55 views

How to design a Context-Free Grammar and Pushdown Automaton for the following language:

How would you design a context-free grammar for the following language? $\{p^n \ r^m \ p \ \ b^{m+n} \ \ r^2 ∣ m,n\geq 0\}$ Derive a Pushdown Automaton that accepts the same language as the CFG. ...
0
votes
2answers
42 views

Increase by one, Shortest path, changes the edges or not?

as i read the following text : "Let P be a shortest path from some vertex s to some other vertex t in a graph. If the weight of each edge in the graph is increased by one, P will still be a shortest ...
6
votes
2answers
519 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
240 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
850 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
519 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
434 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 ...
4
votes
2answers
4k views

What makes a context free grammar ambiguous?

What makes a context free grammar ambiguous?
4
votes
3answers
7k 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
57 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
99 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
3answers
6k 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 ...
3
votes
1answer
671 views

Visualizing Lattice Products

Partial orders can be thought of as a set $S$, and a partial relation on that set, $\le$. If a greatest lower bound and least upper bound exist for any subset of $S$, the poset defines a lattice. The ...