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

Paths with DFA?

My teacher made an example to explain DFA, it was about paths (URL paths), the rules were as follows: S ::= / S ::= /O O ::= [a-z] O ::= [a-z]R O ::= [a-z]S R ::= [a-z] R ::= [a-z]R R ::= [a-z]S Examples of paths could be: /foo, /foo/, foo/bar and…
whirlwin
  • 123
2
votes
1 answer

Contrast Enhancement For An Image Using A Gaussian Function

I am working on a program that involves detecting faces in photos, i am reading a paper that someone has wrote and they said that they had more success detecting faces once he they applied some enhancements to the image, one of these being a…
Dan
  • 21
2
votes
2 answers

A definition of mathematical expression that can distinguish between expressions that denote the same object

I asked a similar question on philosophy stack exchange, but was told to ask it here. In an elementary school math class, we sometimes are asked "What is 2+3?". It would be marked wrong if we simply wrote "2+3". What the teacher is after is a…
user107952
  • 20,508
2
votes
0 answers

Master Theorem(CLRS) Case 3

I copied my question from cs.stackexchange because I highly doubt it's going to get an answer there. In Introduction to Algorithms, Lemma 4.4 of the proof of the master theorem goes like this. $a\geq1,b>1,f$ is a nonnegative function defined on…
2
votes
1 answer

Finding a pair in an array that's difference i smaller then MAX-MIN / n-1

I've a problem I struggle to solve. The question is: Given an array A of size $n$, find a pair, $i,j$ so that $$ 0 \le A[i] - A[j] \le \frac{\max[A] - \min[A]}{n-1}$$ now the problem is that time complexity needs to be $O(n)$. Thx in advance
Stevie
  • 163
  • 5
2
votes
1 answer

What exactly is significand?

per wiki, The significand is part of a number in scientific notation or a floating-point number, consisting of its significant digits. in this example $$123.45 = 0.12345 × 10^3$$ which part is The significand? is it 0.12345? or just 12345
JJJohn
  • 1,436
2
votes
1 answer

How are clock cycles and clock rate inverses?

So I'm trying to understand this simple math formula, but I can't wrap my ahead about what it means to be an "inverse". So for example, a CPU execution time for a program is given by the formula: $$\text{CPU execution time} = \text{CPU Clock Cycles…
Stuy
  • 1,149
2
votes
3 answers

Regular Language Notation Language

What I would like to do is design a program (for academic purposes) which will take a representation of a DFA (as a directed graph) and display the regular language which it accepts, in a reasonable format. For example: For this graph: as input, an…
Steven Lu
  • 391
2
votes
1 answer

How to isolate $\alpha$ in $\frac{\alpha}{\log_2(4\alpha)}$

For my master thesis in computer science, I've got stuck at a point where I have to express $\alpha$ as a function of $\varepsilon$, when I know that $$\frac{\alpha}{\log_2(4\alpha)} > 96\varepsilon^{-1}$$ for $0 < \varepsilon < 1$. I have tried…
AstridNeu
  • 43
  • 2
2
votes
1 answer

Proving problems are unsolvable - reducibility proof

Suppose we have P, a string denoting a C program which takes in a natural number as input and outputs at most one natural number. Prove that it is impossible (unsolvable) to determine that P has infinite range. In other words, show that it is…
Friday
  • 535
2
votes
1 answer

Relationship between algebraic data types and the set of real numbers

I'm reading a book about the programming language Scala ("Functional Programming in Scala" by Paul Chiusano and Rúnar Bjarnason). They introduce the concept of an algebraic data type (ADT), which is a kind of data type used in functional programming…
ubadub
  • 169
2
votes
1 answer

Is language L context-free?

Is following language context-free? Alphabet: {a,b,c,d} L = {w | w is not in {aabbc,abc,add}} I think it is: {aabbc},{abc},{add} are all regular. Because of closure properties(Union) R = {w | w is in {aabbc,abc,add}} is also regular. Because of…
user7572
2
votes
1 answer

what is the best resource for foundation Computer Science related Maths

Could anyone please let me know what would be the best resource to get foundation for CS maths? Many Thanks
nish1013
  • 303
2
votes
3 answers

How large a number can a computer handle?

I remember reading that the largest prime found so far has about 13 million digits so I'm assuming there are computers that can handle such a number but how high a number can a computer hold in its memory and perform calculations with?
Samantha Clark
  • 359
  • 3
  • 6
2
votes
1 answer

O notation and growth order of function

This is for a homework problem, and I was wondering if someone could check my work and conclusions about growth of a function I am trying to determine if the following formula is Polynomial? Superpolynomial? Exponential? $$ f(n) =…