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
3
votes
0 answers

Are there any math problems in artificial intelligence?

I'm interested in applying mathematics in artificial intelligence but only by solving purely mathematical problems. Is this possible? And what fields of mathematics are most applicable?
rrr123
  • 29
3
votes
1 answer

An interesting list ordering result based on skipping indexes by value entered

This is something interesting I've found while attempting to shuffle $n$ values in a list is a deterministic way intended to look "random-ish". The idea is that you sort a number of values $r$ from $0...n-1$ into a list by starting with an index…
Oliver
  • 33
3
votes
0 answers

Covering $n$ points with fewest disks with fixed radius $\epsilon$

The title says it all. I have a set of $n$ points in $\mathbb{R^{2}}$ and I am looking for an algorithm that tells me the fewest numbers of disks of radius $\epsilon$ that cover the set of $n$ points. Any ideas? Has this been done? I don't need…
acr423
  • 31
3
votes
1 answer

Prove that if $f(n) ∈ Θ(g(n))$ and $g(n) ∈ Θ(h(n))$ then $f(n) ∈ Θ(h(n))$.

I know that by the assumption that $f ∈ Θ(g)$ we know that there exist constants $c_0$ and $c_1$ in $\mathbb R^+$, and there exists $n_0 ∈ \mathbb N$ such that: $$c_0 \cdot g(n)\le f(n)\le c_1 \cdot g(n),$$ but this is then where I get stuck, can…
Hannah
  • 73
3
votes
1 answer

Does fixing the number of elements in PARTITION send it in P?

It's possible that this question is trivial and I've overlooked something. Let us impose the following constraint on the well-known PARTITION problem: in all inputs of a new problem the number of elements is fixed and equals $k$? Does such…
3
votes
1 answer

Pushdown Automata deriving context free language

I'm trying to understand how you derive a context free grammar (CFG) from a Pushdown Automata (PDA)? I have the following PDA. I believe the following context-free language can be derived.. {0^n1^n|n≥0} My problem is I don't understand how you can…
Ulkmun
  • 287
3
votes
3 answers

Proving that $\{ww^rx | w,x \in \{a,b\}^{+} \}$ is non regular using the pumping lemma.

I need to prove that $L=\{ww^rx | w,x \in \{a,b\}^{+} \}$ is non regular. First of all I assume that L is regular. Then L satisfies the pumping lemma, so let p be the pumping length. I've tried several strings, like $a^pbba^p$ that work with the…
3
votes
3 answers

which branch of computer science is most math intensive?

I am planning for a Master degree study, my major in college is computer science, but I also like math. I want to know which branch of computer science uses most math, not only discrete math, but also others like Calculus, Linear Algebra etc. I know…
3
votes
2 answers

A language that is not even context-sensitive?

Is there a language actually in use that can't be recognized by a linear bounded automaton? I only know of ones that don't have a practical use, like "the set of pairs of equivalent regular expressions with exponentiation" (Wikipedia). Or would…
Eric Yu
  • 284
2
votes
2 answers

Question about queues

A queue is implemented with a sequence $Q[1\ldots n]$ and two indices $\def\head{\operatorname{head}}\head[Q]$ and $\def\end{\operatorname{end}}\end[Q]$ such that the elements of the queue are the following: $$Q[\head[Q]], Q[\head[Q]+1], \ldots ,…
Mary Star
  • 13,956
2
votes
1 answer

in sending with name using λ (counting), how does the process happen?

Sometimes expressions has two states. the result of analyses might be two different things but at the end, there might be the same answer(result) for them.(the way we get to the answer is different,but the result is the same) for example: P->Q =…
sam
  • 21
2
votes
1 answer

Group of computable permutations

Why group of computable permutations of natural numbers is not finitely generated? It is obvious for all permutations but why it is also true for computable permutations?
2
votes
1 answer

transition function DFA, PDA

I am new to PDA, teacher is using different format, I see different notation for transition function I am not able understand teacher's format in this question for transition function of PDA! Problem $\mathbf {611}\quad$ Let $L$ be the language…
2
votes
2 answers

Number guessing game with expensive answers

I play the number guessing game with positive integers and a known constant upper bound. Every time I make a guess about the number I have to pay 1 dollar but if my partner answers 'Yes' I have to pay 9 more. What is the best strategy to minimize…
buherator
  • 153
  • 4
2
votes
1 answer

Large numbers calculation

I think this question has more mathematical background than computional, then I'm gonna ask it here. I was thinking about large numbers calculation. Let's say I have the number $16777735$ stored in memory like this: $256^0$ $256^1$ $256^2$ $256^3$ …
PPP
  • 2,041
1 2
3
16 17