Skip to main content

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).

Filter by
Sorted by
Tagged with
22 votes
1 answer
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 ...
user13's user avatar
  • 223
17 votes
2 answers
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 ...
Dungeon Hunter's user avatar
29 votes
3 answers
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/...
Shashwat's user avatar
  • 395
22 votes
2 answers
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 ...
nilo de roock's user avatar
15 votes
1 answer
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 ...
Griffin's user avatar
  • 468
8 votes
1 answer
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 ...
mtheorylord's user avatar
  • 4,284
36 votes
5 answers
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 ...
IamIC's user avatar
  • 671
25 votes
4 answers
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 ...
AlanFoster's user avatar
26 votes
5 answers
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 ...
Abaco's user avatar
  • 475
16 votes
2 answers
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$-...
simmmons's user avatar
  • 291
6 votes
1 answer
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 ...
www.sapnaedu.in's user avatar
5 votes
3 answers
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 ...
Donuts's user avatar
  • 51
67 votes
3 answers
125k views

Recognizable vs Decidable

What is difference between "recognizable" and "decidable" in context of Turing machines?
metdos's user avatar
  • 967
27 votes
4 answers
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: ...
puri's user avatar
  • 493
13 votes
4 answers
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 ...
templatetypedef's user avatar
8 votes
5 answers
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 ...
Terra's user avatar
  • 81
22 votes
5 answers
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 ...
Billie's user avatar
  • 3,469
19 votes
2 answers
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 ...
Tom Artiom Fiodorov's user avatar
16 votes
1 answer
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 ...
User1's user avatar
  • 163
11 votes
2 answers
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 ...
user avatar
9 votes
5 answers
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 ...
Shuzheng's user avatar
  • 5,633
9 votes
4 answers
32k 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 ...
AkshaiShah's user avatar
4 votes
2 answers
493 views

What is the algorithm hiding beneath the complexity in this paper?

So, I am a computer scientist (at least, I'm working to become one..) and I asked a question on here concerning some mathematics behind the Mandelbrot set. A reply I recieved pointed me to this paper. ...
Steven's user avatar
  • 1,580
3 votes
1 answer
565 views

Does sequent calculus have axiom?

Are axioms inference rules without assumptions, or not inference rules at all? I heard that sequent calculus doesn't have axioms, is that true? p69 in §6. Summary and Example in IV. A Sequent ...
Tim's user avatar
  • 47.7k
1 vote
1 answer
7k 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 ...
row's user avatar
  • 229
215 votes
13 answers
66k 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 ...
user107952's user avatar
  • 20.9k
64 votes
2 answers
4k 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 program;...
Casebash's user avatar
  • 9,307
48 votes
3 answers
131k views

What is the $3$-SAT problem? [closed]

In the hopes of improving my knowledge on the question, could someone outline the inputs and outputs for the 3-SAT problem? It would also be helpful if you could express how this problem differs in ...
nubela's user avatar
  • 849
30 votes
2 answers
33k views

Concrete FFT polynomial multiplication example

I have read a number of explanations of the steps involved in multiplying two polynomials using fast fourier transform and am not quite getting it in practice. I was wondering if I could get some help ...
alh's user avatar
  • 471
25 votes
3 answers
3k views

What is the current state of formalized mathematics?

Russell and Whitehead famously tried to actually create and use a formal system to explicitly develop formal mathematics in their work, "Principia Mathematica." Much more recently, with the aid of ...
JWP_HTX's user avatar
  • 1,664
25 votes
4 answers
5k 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 ...
bshanks's user avatar
  • 523
20 votes
4 answers
97k views

Number of edges in a graph with n vertices and k connected components

Let $m$ be the number of edges, $n$ the number of vertices and $k$ the number of connected components of a graph G. Prove that: $m$ $\leq$ $\frac{(n-k+1)*(n-k)}{2}$ Thanks!
Federico Martinez's user avatar
19 votes
5 answers
2k 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 ...
Seamus's user avatar
  • 4,035
16 votes
4 answers
43k 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. ...
user68486's user avatar
  • 161
15 votes
3 answers
13k views

Why do we divide or multiply by 2 when converting binary?

Trying to understand the fundamentals of binary rather than just following steps, I wanted to know why do we multiply by 2 to convert a decimal (0.5, 0.25) to a binary and why do we divide by 2 when ...
direprobs's user avatar
  • 510
10 votes
2 answers
11k 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 ...
WWright's user avatar
  • 5,530
7 votes
1 answer
451 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 ...
mghandi's user avatar
  • 1,792
7 votes
4 answers
9k 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 ...
pauliwago's user avatar
  • 635
3 votes
0 answers
411 views

Execution time of function

At the algorithm SELECT, there is the following step: ...
evinda's user avatar
  • 7,871
2 votes
1 answer
324 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 ...
mghandi's user avatar
  • 1,792
2 votes
4 answers
285 views

Evaluate $6^{433} \pmod {21}$ and a proving question

Question 1: Denote $a \mod b$ as $a \% b$, where $a$ and $b$ are some integers Evaluate 12^32475 % 21 The following is what I tried: ...
keanehui's user avatar
  • 145
1 vote
1 answer
664 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.
nour's user avatar
  • 153
1 vote
4 answers
46k 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$ then $a$|$bc$ for all integers $c$; $$ $$ (iii) if $a$ |$b$ ...
Yusha's user avatar
  • 1,641
1 vote
0 answers
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 ...
Han de Bruijn's user avatar
1 vote
1 answer
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 ...
GEU197's user avatar
  • 11
0 votes
1 answer
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 "...
Tim's user avatar
  • 47.7k
-1 votes
1 answer
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 ...
user avatar
42 votes
11 answers
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 ...
user avatar
25 votes
9 answers
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?
Razin's user avatar
  • 703
24 votes
2 answers
34k views

Computational complexity of computing the determinant

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 ...
Jonah Sinick's user avatar
  • 1,042

1
2 3 4 5
9