# Questions tagged [computer-science]

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 questions from scientific computing, use (computational-mathematics).

440 questions
Filter by
Sorted by
Tagged with
4k 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 ...
• 223
22k views

### Reed Solomon Polynomial Generator

I am developing a sample program to generate a 2D Barcode, using Reed-Solomon error correction codes. By going through this article, I am developing the program. But I couldn't understand how he ...
32k 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/...
• 395
4k views

### Which resources are available 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 ...
• 2,789
12k 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 minimum ...
• 468
1k views

### Testing Zeros Of The Riemann Hypothesis [closed]

I was on Mathworld some time ago when I read this from http://mathworld.wolfram.com/RiemannHypothesis.html: The Riemann hypothesis was computationally tested and found to be true for the first ...
• 4,284
59k 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 ...
• 671
13k 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 ...
• 353
65k 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 ...
• 475
5k 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$-...
• 291
3k 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 ...
60k 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 ...
• 51
125k views

### Recognizable vs Decidable

What is difference between "recognizable" and "decidable" in context of Turing machines?
• 967
11k views

### Number of ways to partition a rectangle into n sub-rectangles

How many ways can a rectangle be partitioned by either vertical or horizontal lines into n sub-rectangles? At first I thought it would be: ...
• 493
5k views

### Does DTIME(O(n)) = REGULAR?

(I don't think that this is a good fit on cstheory, since I figure that this question already has a known answer. However, if you think that this would be a better fit there, please feel free to ...
• 10.5k
8k views

### Calculating a SQRT digit-by-digit?

I need to calculate the SQRT of $x$ to $y$ decimal places. I'm dealing with $128$-bit precision, giving a limit of $28$ decimal places. Obviously, if $\,y > 28$, the Babylonian method, which I'm ...
• 81
94k views

### How does linear algebra help with computer science?

I'm a Computer Science student. I've just completed a linear algebra course. I got 75 points out of 100 points on the final exam. I know linear algebra well. As a programmer, I'm having a difficult ...
• 3,469
3k 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 ...
• 1,431
466 views

### How to prove there are no more positive integers that are products of 2 and 3 consecutive numbers?

$6$ and $210$ share the property that both are the products of both two and three consecutive numbers. $6$ is $2\times3$ and $1\times2\times3$ and $210$ is $14\times15$ and $5\times6\times7$. It was ...
• 163
6k 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 ...
8k views

### What is a fast algorithm for finding the integer square root?

What is a fast algorithm for computing integer square roots on machines that doesn't support floating-point arithmetic? I'm looking for a fast algorithm for computing the integer square root of an ...
• 5,633
32k views

• 1,641
1 vote
530 views

### Computability, Continuity and Constructivism

Triggered by an IMO extremely interesting question & Mathematics Stack Exchange, asked by Dal: Computability and continuous real functions And a link in one of the comments that could have ...
• 17.2k
1 vote
782 views

### Give Lambda Calculus Term for Haskell Function

I am working on a larger project translating Haskell to Lambda calculus. I would like to give a lambda term to specific Haskell functions. I am not quite sure how to approach two of them. I went ahead ...
• 11
174 views

### Does "the alphabet of the language of propositional logic" have no function symbols, relation symbols, and constants?

In Ebbinghaus' Mathematical Logic, II.2.1 on p14 says that the alphabet of a first order language contains function symbols, relation symbols, and constants, whereas I don't see these symbols in "...
• 47.7k
1k views

### Lambda Calculus Beta reductions

I have two questions about $\beta$-reduction in the $\lambda$-calculus. Please find them below. I have also included some background information about how lists (i.e. finite sequences) can be encoded ...
24k views

### what are the different applications of group theory in CS? [closed]

What are some applications of abstract algebra in computer science an undergraduate could begin exploring after a first course? Gallian's text goes into Hamming distance, coding theory, etc., I ...
25k views

### Is it possible to generate truly random numbers using a computer? [closed]

I know that there are many algorithms to generate pseudorandom numbers but is it possible to generate truly random numbers using a computer program?
• 703
The formula for the determinant of an $n$ by $n$ matrix given by expansion of minors involves $n!$ terms. As such, computing the determinant of a given matrix of with integer entries via expansion by ...