Mathematics Stack Exchange
Mathematics Stack Exchange

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

Computer science is the study of the theory, experimentation, and engineering that form the basics for the design and use of computers. It is the scientific and practical approach to computation and its applications and the systematic study of the feasibility, structure, expression, and mechanization of the methodical procedures (or algorithms) that underlie the acquisition, representation, processing, storage, communication of, and access to information. An alternate, more succinct definition of computer science is the study of automating algorithmic processes that scale.

Some fields of computer science such as computational complexity theory (which explores the fundamental properties of computational and intractable problems) are highly abstract, while fields such as computer graphics emphasize real-world visual applications.

5523 questions
0
votes
0 answers

Euler’s theorem: any sequence of rotations = one rotation about some axis

While learning about transformations in Computer Graphics,I couldn't get why any sequence of rotations is actually equal to one rotation about some axis by Euler's theorem as stated in Computer Graphics.
justin
  • 367
-1
votes
1 answer

Universal way to convert from one base to another

Is there a universal way to convert from one base to another? I know how to convert numbers with any base to decimal form. i.e., with $\sum_{i=0}^{n-1} r^{i}d_i$. However I don't know any universal way to convert from a number of any base to another…
George Newton
  • 275
-1
votes
1 answer

Where does data structure enters in Turing Machine?

From what I have learnt so far the simplest Turing machine consists of an input tape, an output header which can move both ways, some internal states and a transition function. Since algorithms and Turing machines are one and the same, then where…
EarthIsNotFlat
  • 31
-1
votes
1 answer

Approximation bounds on the Nearest Neighbour Algorithm for the TSP.

I am currently studying about the Nearest Neighbour Algorithm applied to the TSP, and I want to check if there are any performance bounds on it. I have came across the following paper on the logarithmic bound for euclidean TSP. I came across this…
Dylan Galea
  • 15
-1
votes
1 answer

Is the regular expression: $(\lambda + a)^*$ equivalent to $a^*$?

I have a question about convert a regular expression to an automaton. In the middle of the regular expression, appears $(\lambda + a)^*$. What I am wondering is: it is not the same of $ a^* $? If is so, I could simplify the final…
Silva
  • 151
-1
votes
1 answer

Is there a way to prove that a binary operator is commutative?

Such binary operator returns an output in the same set as the two inputs and is a general computer program. Such general computer program is used in the reduce phase of some computations I run. Knowing ahead of time whether my general computer…
Giorgio
  • 3
-1
votes
1 answer

Static assumptions - computer science

Specify all conditions, assumptions and limitations for the following code that needs to compute an average value of different numbers in an interval $[1,10000]$. Conditions, assumptions and limitations must be written in mathematical…
user300045
  • 3,449
-1
votes
1 answer

For which block sizes are certain hash algorithms proven to not have collisions?

CRC32 has hash collisions for the inputs "plumless" and "buckeroo". What's the smallest data length for collisions in MD4, MD5, SHA-1, and the recently accepted SHA-3 (Keccak)? We know that lim_len n->infty p(collision) = 1.0, but I'm curious how…
mcandre
  • 461
-1
votes
2 answers

Find a grammar that generates strings over {a,b} that contain "ba"

My grammar is G = (Terminals, NonTerminals, Rules, StartingSymbol) Terminals = $a,b,\lambda$ NonTerminals = $A,B,S$ StartingSymbol = $S$ RULES = $$\begin{align*} &S\to A\mid B\\ &A\to a\mid aAB\mid\lambda\\ &BB\to B \end{align*}$$ Theses rules are…
csjr
  • 1
-1
votes
1 answer

For $L_1,L_2,L_3$ , $L_1 \cap L_2 = L_3$, if $L_1,L_2,L_3$ such that $L_1 \cap L_2 = L_3$, if $L_1$ and $L_3$ are CFLs, so $L_2$ is CFGLas well

I'm trying to answer this question: Is it true that for three languages $L_1,L_2,L_3$ such that $L_1 \cap L_2 = L_3$, if $L_1$ and $L_3$ are context free languages, so $L_2$ is context free languages as well. I know that context free languages are…
Jozef
  • 7,100
-1
votes
2 answers

Prove that, in the process of growing an array incrementally from size 0 to size $n$, approximately n^2 values must be copied.

Suppose that a precisely sized array is used to hold data, and that each time the array size is to be increased, it is increased by exactly one and the data are copied over. Prove that, in the process of growing an array incrementally from size $0$…
goat
  • 1
-1
votes
1 answer

Why is the smallest grammar problem hard?

There are several papers giving graph-theoretical proofs that the smallest grammar problem cannot be solved with a polynomial time algorithm. Could someone give a short intuitive proof? I haven't studied the complexity classes and that area of…
Daniel Donnelly
  • 21,342
-3
votes
1 answer

Digital Circuit Design

Design and implement a digital circuit which will detect a 4 bit number which is less than 3 or greater than 12 or divisible by 3 (if conditions are met, the output is 1, 0 otherwise). Implement the circuit with NAND only logic gate. I've derived a…
user215717
  • 25
1 2 3
…
16
17