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
4
votes
2 answers

How to prove that this function is primitive recursive?

How can I solve the following problem: Let $f, \pi, g$ accept one, two and three arguments respectively. If you know that $f, \pi, g$ are primitive recursive functions prove that $h$ defined as: $$ \begin{align*} h(0, y) &\simeq f(y) \\ h(x…
Peter P
  • 71
4
votes
1 answer

Find the NFA for the language $\{ w | \text{ w contains an even number of 0s, or contains exactly two 1s } \}$

I'm working on the problem sets from "Introduction to the Theory of Computation" 2nd edition - Michael Sipser. This problem is in chapter 1 page 85, 1.7 part c) Give the state diagrams of NFA for the language $\{ w | \text{ w contains an even…
roxrook
  • 12,081
4
votes
2 answers

Closed form of this nested sum with variable lower bound

I would like to know why the closed form expression of $$\sum_{i=1}^{n}\sum_{j=i+1}^{n} (a_i + a_j)^2 + (b_i + b_j)^2$$ evalutes to $$ (n-2) \cdot \sum_{i=1}^{n} (a_i^2 + b_i^2) + (\sum_{i=1}^{n} a_i)^2 + (\sum_{i=1}^{n} b_i)^2$$. The problem poster…
Jia Geng
  • 43
4
votes
1 answer

Introduction to the Theory of Computation Solution Manual - Michael Sipser

I am hoping to test out a Theory of Computation class for next semester and have bought the course's textbook, Introduction to the Theory of Computation by Michael Sipser to prepare. I was trying to go over some of the exercises at the end of the…
Ranlou
  • 149
4
votes
1 answer

Decidable? Turing machine runs X steps for certain input?

Question is the following language decidable: {(M)|given input "aaaaa" Turing machine M will perform at least 1295 steps} I would say, yes it is. Just let the Universal Turing Machine count each step, and accept if it reaches step 1295. But is this…
user7572
4
votes
2 answers

L* regular -> L regular?

If language L* (Kleene Star) is regular, does it imply that L is also regular?
user7572
4
votes
4 answers

Is this BNF grammar ambiguous?

I have a BNF defined as follow: -> 0 -> 1 -> I think this grammar is not ambiguous, but the solution was 'yes'. Any idea? The book solution is odd to me, because I think it is the same as the one above. ->…
roxrook
  • 12,081
4
votes
1 answer

Prove that if $f(n) \in O(g(n))$ then $g(n) \in \Omega(f(n))$

Prove that if $f(n) \in O(g(n))$ then $g(n) \in \Omega(f(n))$. So I know that $$O(g(n)) \Rightarrow f(n) \leq c\cdot g(n)$$ and that $$\Omega(g(n)) \Rightarrow f(n) \geq c\cdot g(n)$$ but how do you use these to do the above proof?
Hannah
  • 73
3
votes
0 answers

Hardness of perimeter minimization?

Given $xy=C$ where $x, y$ are integer variables and $C$ is integer constant. What is the most efficient algorithm that finds $x,y$ such that $x+y$ is minimum? Providing references is highly appreciated. Edit: Input integers are reasonably…
Mohammad Al-Turkistany
  • 952
3
votes
1 answer

Given 2 colors, how to calculate the mix amount between them?

As an input I have two colors, let's say red (RGB = 1,0,0) and magenta (RGB = 1,0,1). Now I have an image which includes additive mixes between these two colors, for example purple (RGB = 0.5,0,1). I want to calculate the mix amount between these…
Ray
  • 151
3
votes
3 answers

algorithm question how prove that $(n+a)^b = \Theta(n^b)$

this question doctor in college give us as home work but I don't know how approve it
belo gadelo
  • 311
  • 1
  • 4
  • 10
3
votes
1 answer

Prove that the language $L = \{a^nb^kc^{n+k} : n \geq 0, k \geq 0\}$ is not regular

Problem Prove that the language $L = \{a^nb^kc^{n + k} : n \geq 0, k \geq 0\}$ is not regular by Pummping Lemma. Pumping Lemma Let $L$ be an infinite regular language. Then there exists some positive integer $m$ such that any $w \in L$ with …
roxrook
  • 12,081
3
votes
2 answers

Masters in Numerical Analysis?

My interests in CS are fairly narrow; I'm mainly interested in numerical analysis and numerical methods for solving differential equations. However, during my undergrad I mainly focused on other, more traditional aspects of CS. I don't have as…
Emir
  • 2,213
3
votes
2 answers

Is Halting Problem is decidable for any real world algorithms?

Halting Problem is (theoretically) decidable for such algorithms which termination may be proved in First Order Logic (FOL) because all true statements in FOL are recursively enumerable. It is correct? I'm talking about programs in Turing-complete…
Vag
  • 243
3
votes
1 answer

Help with Recurrence relations forward substitution

Thanks in advance to anybody who can help, The question: solve by recurrence relation using forward substitution and verify by mathematical induction. $T(n) = 2T(n/7)$ for $n > 1, n$ is a power of 7 $T(1) = 1$ Here is what I have so far and no…
Dereck
  • 131
1
2
3
…
16 17