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
1 answer

What's wrong with this "proof" of time complexity? Traversing a $n \times n$ matrix in $O(n)$

Claim: I can traverse an $n \times n$ matrix in $O(n)$. "Proof": Clearly, this is true for $n=1$. Now suppose this is true for $n-1$. Then given an $n \times n$ matrix, traverse the upper left $(n-1)\times(n-1)$ matrix in $O(n-1)$ time, and then the…
user48372
  • 35
  • 3
1
vote
2 answers

Translate Programming code to Math

Almost all mathematical formulas functions etc can be translated to programming codes, can it be done in reverse i.e. code to math? Is it possible to convert simple programming codes (programs that are not hardware or software specific) to…
LifeH2O
  • 379
1
vote
3 answers

Representing circular bitwise shift mathematically

If you wanted to represent, A -> B. B -> A, you could easily represent it by matrix multiplication. But for nonlinear operations like circular bitwise shifts, is there any nice mathematical representation that can be manipulated easily?
countunique
  • 2,449
1
vote
1 answer

Myhill-Nerode theorem for the language: $L = \left\{ a^n b^n\mid n\ \geq\ 1 \right\}$

I have to use the Myhill-Nerode theorem for the following language: $$L = \left\{ a^n b^n\mid n\ \geq\ 1 \right\}$$ An equivalence relation is the following: $$x \sim y\ \Leftrightarrow \forall\ \ z\ \in \Sigma ^*\ : xz\ \in\ L\ \Leftrightarrow\ yz\…
Mary Star
  • 13,956
1
vote
2 answers

Does a System to Automatically (Mathematically) Generate Arbitrary Computer Programs Really Exist?

Has anyone actually developed a Program Synthesis system for creating computer programs automatically from a non-procedural specification that is taken from a fairly robust system of specifications? For example, I might say "Check if X is a factor…
1
vote
2 answers

How to make a Truth Table and turn Truth table into A Circuit.

Background I'm a novice student learning some mathematics (Programming background) and I'm currently learning how to construct Truth Tables from Logical Statements and then use that Truth Table to make a circuit. In the last few months I've had exam…
1
vote
2 answers

How can I tell if these are undecidable?

For each of the following set, show that they are undecidable. Do not use Rice theorem. a. $L_{1} = \{M |M$ accepts w if w contains the substring 10 $\}$ b. $L_{2} = \{M| M$ accepts an odd number of strings $\}$ I have tried proving using aTM…
bccurry
  • 135
1
vote
2 answers

Pumping Lemma Help

Can somebody explain or possible solve the following question regarding the pumping lemma? I have a book from Sipser that I took this from and I honestly can't really get a good grasp of the pumping lemma technique, much less solve anything using…
1
vote
1 answer

which class does this function belong to in the fast growing hierarchy?

the class $\mathfrak{F}_k$ of the fast growing hierarchy is the closure under substitution and limited recursion of the constant, sum,projections and $F_n$ functions for $n\leq k,$where $F_n$ is defined recursively by $$ \begin{eqnarray*} …
ougao
  • 11
1
vote
1 answer

Related Integer Combination

The title and tags are a little goofy since I'm not quite sure what to call this. This may be more of a computer science question, but I thought I'd ask here too. I have two integers $n$ and $m$ that are arbitrarily (logically) related with…
Nalandial
  • 113
1
vote
1 answer

Picking an appropriate "guess" for Heron's Method and The Fast Reciprocal Method

I've been thinking for a while about writing some code that would use Heron's Method and the Fast Reciprocal Method. Heron's Method This finds the approximation of $ \sqrt{S} $. The initial guess is $ G_0 $ The update formula is: $$ G_{n+1} =…
1
vote
0 answers

Set-theoretic description of stack frames

I am trying to understand some of the mathematical underpinnings of computing, and I've gotten stuck on functions and stackframes. For example, consider the following bit of code that is executed during a program: { // Stackframe S a = 1 …
1
vote
1 answer

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 accepted by a finite automaton). The author gives two…
row
  • 229
1
vote
2 answers

How do I find the infinite sum of $\arctan(2^{-n})$?

I am looking at the CORDIC Algorithm and I want to show that iterative rotations by the nth angle given by arctan $2^{-n}$ is greater than $\frac{\pi}{2}$. $$ \sum_{n=0}^{\infty} \arctan 2^{-n} $$
Ricardo
  • 41
1
vote
1 answer

Create a formula from a set of number ranges

I'm not sure what what to call what I would like help creating so please bear with me. Basically I have a program which assigns you a number of points(a competition point not a point on a graph or anything) depending on how quickly you answer a…
krz
  • 113