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

Is $ 5^{xf(x)} \in \mathcal O (5^{f(x)}) $?

Intuitively I know that $ 5^{xf(x)} \in \mathcal O (5^{f(x)}) $ but how would I go about proving this? I am at my wit's end on this. $ 5^{xf(x)} \in \mathcal O (5^{f(x)}) \Leftrightarrow \exists c, B \in \mathbb{R}^+, \forall n \in \mathbb{N}, n…
tuba09
  • 323
0
votes
1 answer

Comp Sci Math; Hamming Distance

I've been tasked with this question but I have no idea how to answer it. What is the maximum possible hamming distance between two points from level i in a n-cube?
David
  • 1
0
votes
1 answer

Determining if a problem is solvable by a Push-Down Automaton

I have the following language: {0^n 1^n 0^n 1^n | n >=0} And need to find a PDA that recognizes the language. I have devised PDAS which determine {0^n 1^n 0^m 1^m} And {0^n 1^m 0^m 1^n} But haven't found one to solve the original problem. Is the…
MrD
  • 416
0
votes
3 answers

Distance between pixel centres on a tv

I have a question i am stuck on in my maths class. I am going to change the numbers so i can figure it out this example myself. Need to get the distance between the two pixels calculated. Thanks for the help Thats 100" diagonal and 1920 pixels…
0
votes
1 answer

Regular expression-language

I want to draw the DFA of the language that is given of the following expression, but I got stuck... Let the expression be {$(xy)^{*},(zx)^{+}$}$xz$ . Could you help me understanding which language it is?
Mary Star
  • 13,956
0
votes
0 answers

Data structure with quick insert and search

I have a problem I'd like to code. I have a process which generates numbers 0 through n-1 and I want to stop it when it generates the first repeated element.* I'm looking for a data structure that makes this fast. In particular, adding a new element…
Charles
  • 32,122
0
votes
1 answer

How to approach this Secret Sharing scheme?

Suppose that I want to break up a secret into shares such that any set of k people can recover the secret, but I’m also worried that some people might be dishonest and may lie about the secrets they have (in order to prevent the other people from…
0
votes
1 answer

Is the empty string the empty set?

I've clicked through about a million questions on here and and on CS Stack Exchange and not yet come across an unequivocal "yes" or "no" to the following: Is the empty string the same thing as the empty set? Sipser ("Theory of Computation")…
EE18
  • 1,211
0
votes
0 answers

What is the nonstandard definition of "relation" in Sipser all about?

At the beginning of Sipser's Theory of Computation we get the following two definitions: A predicate or property is a function whose range is $\{TRUE, FALSE\}$. For example, let even be a property that is $TRUE$ if its input is an even number and…
EE18
  • 1,211
0
votes
0 answers

computer science math related questions

the number of s-stars of an input graph $G=(V,E)$ is $\sum\limits_{v\in V}\binom{d(v)}{S}$ when $d(v)$ is the degree of the node $v$. In this problem, we address the publication of the number of $s$-stars under $k$-edge differential privacy (defined…
0
votes
0 answers

How can we define the error of the CORDIC Algorithm for calculating sin(x) as a function of the number of iterations/rotations performed?

I intend on comparing the CORDIC algorithm and the Taylor Series expansion for computing sin(x). However, I need to compare them on the basis of accuracy and time complexity. How can we determine the error of the CORDIC Algorithm (similar to how the…
Ricardo
  • 41
0
votes
0 answers

Give context-free grammars that generate the following languages.

L1={a^n b^2n c^m |n,m>0} L2 = {a^3n b^2n | n ≥ 0}, the alphabet is ∑={a,b} L3 = {a^i b^j c^k | i, j, k ≥ 0 and i+j <= k}, the alphabet is ∑={a,b,c}
0
votes
0 answers

Are there any examples of functions that take inputs of different types (for example number, String) and produce output?

In programming it is rather the norm than the exception to have functions whose input are different data types. For example a function who produces a substring of a given string would have the following signature in Java: public static String…
0
votes
1 answer

Where does the $M$ come from? Which parameters are related with this question, $(x_0, y_0)$ or $(x_0, y_0, \gamma, \beta, \alpha, c, k)$?

My question is about Java programming. The question is . I struggle with where the $M$ comes from, and I do not understand this question very well. As in the final, it needs to find the array of $c$. The above are thoughts of mine. If they are…
0
votes
0 answers

If $f_1(n) ∈ O(g_1(n))$ and $f_2(n) ∈ O(g_2(n))$ show that $f_1(n)+f_2(n) ∈ O(max(g_1(n), g_2(n)))$

If $f_1(n) ∈ O(g_1(n))$ and $f_2(n) ∈ O(g_2(n))$ show that $f_1(n)+f_2(n) ∈ O(max(g_1(n), g_2(n)))$ I know that: $$f(n) ∈ O(g(n)) \iff \exists\ C >0, n_0\geq0\ | f(n) \leq C *g(n)\ \forall\ n\geq{n_0}$$ How to get proof with this information?
water
  • 101