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
1
vote
0 answers

How to prove a property of the Lawvere theory for global state

In the field of algebraic computational effects, there is a Lawvere theory for global binary state (taking value either $0$ or $1$) which is generated by three operations $get: 2 \to 1$ $put_0: 1 \to 1$ $put_1: 1 \to 1$ subject to three natural…
Tom Ellis
  • 223
1
vote
1 answer

Grammar to Chomskys Normal Form eliminating epsilon productions

I've got the following grammar I'm attempting to convert to CNF. S -> T01 | USV | epsilon U -> X V -> S1S | X | 1 X -> 0XS | 0 T -> TV | XT | UTU I know that when I eliminate epsilon-productions I get... S -> T01 | USV | UV U -> X V -> S1S | S1 |…
Ulkmun
  • 287
1
vote
1 answer

Big $\theta$ of $x^2ln(x) + xln(x^2+1)$

I am working on finding the big $\theta$ of $x^2ln(x) + xln(x^2+1)$ but have never done it before with logarithms. How would I handle this problem? I also know that n is big $\Omega$ of nln(n) which I feel has something to do with this question...…
Paradox
  • 285
1
vote
1 answer

Complexity of fast multipole method

I am trying to implement the Fast multipole Method on Matlab. But i have a question: if we call N the number of source point we need (in the FMM algorithm) to sort the data points. Such a procedure require O(NlogN) complexity in the best case (the…
curious
  • 295
1
vote
1 answer

how MIX subtractions works with "packed" words

Im reading the Knuth's book TAOCP. And im just learning a simple math operations with registers. And there is an example of subtraction operation: rA before: - | 1234 | 0| 0| 9 Cell 1000: - | 2000 | 150| 0 SUB 1000 rA after: + | 766 | 149 |…
RusAlex
  • 135
1
vote
1 answer

What is the total speedup?

This is a repost of a StackOverflow thread. I was told that people on this forum will be able to answer this question faster. So here it is: This is not homework. I'm taking a computer architecture MOOC on my own time. There is a problem I can't…
flashburn
  • 465
  • 1
  • 6
  • 16
1
vote
1 answer

Where can I find the basic definitions used by researchers in string processing / matching / searching.

Fast String Correction with Levenshtein-Automata This paper uses the terms descendent and stroke, and I can't find definitions for them by googling. Could you recommend a book, or page. Grazie.
1
vote
0 answers

A doubly infinite tape Turing machine can simulate a ordinary Turing machine, a rigorous proof.

Let $M$ be a ordinary Turing machine. Intuitively, we can say that $M$ can be transformed to a machine $M_D$ with doubly infinite tape, by placing to the left on every input $w = w_1, \dots , w_n$ some symbol $\#$ that tells the machine to 'get…
1
vote
2 answers

How do you embed $Z_5 \times Z_7$ into $Z_{2^8}$?

Basically, the real question which I thought was better asked that way is what are the ways to represent all ordered pairs of elements $(x,y)$ where $x\in Z_5$ and $y\in Z_7$ in a byte of memory? I.e. There needs to be atleast 5*7 = 35 code words. …
1
vote
1 answer

validity of isbns in catching jump transposition errors

Does the isbn detect jump transpositions? $$a_1+2a_2+3a_3+\cdots+10a_{10}=0\pmod{11}$$ I think it does because the specific formula multiplying 1 times 1st digit, 2 times 2nd digit... will give you a remainder of zero if the isbn is correct. if it's…
1
vote
1 answer

Why is the maximum number of integer values per fixed-length variable sightly more than the amount of values for the previous one squared?

For example; an 8-bit variable can have 255 total values. 255 squared is 65,025, but the amount of total values for a 16-bit variable is 65,536. Where do these extra 511 values come from?
1
vote
2 answers

Propability of same characters next to each other in words

At the start , I have word of length N(N characters in a word) And each character can only be A,B or C Now the words that i want is words that have 3 or more same character that is next to each other. Example N=4 Want: AAAB,BBBB,ACCC........ Don't…
1
vote
2 answers

Using K-Map to simplify functions

I hope this is the right place to ask this. I have the following problems: 1. Using a K-Map technique perform the following: Simplify the following function: f = (A,B,C,D) = ∑ m (0,1,2,3,6,7,8,9,13,15) Show all the "prime implicants" and…
1
vote
1 answer

Clock Frequency and Duty Cycle

A clock has a 1ns clock period with rise and fall time as 0.05ns. The clock signal stays at exact Boolean state 1 for 0.35ns and at state 0 for 0.55ns. The memory used in the design takes 2 clock cycle time to compute a write and 1 clock cycle to…
1
vote
3 answers

Period of a simple pendulum

I'm writing a short program to simulate a simple pendulum. The equations of motion are $$\frac{d\theta}{dt}=\omega$$ $$\frac{d\omega}{dt}=-\frac{g}{r}\sin\theta$$ For some small time step $dt$ the time evolution of $\theta$ and $\omega$ are governed…
user213973