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

Show that Turing-decidable languages are closed under set difference

Can we use the proof of turing-decidable languages being closed under complement to show that turing-decidable languages are closed under set difference?
0
votes
1 answer

How many bits of memory per character?

If I create an array with 10 random numbers in the range [0, 2^30]. How can calculate the number of bits that it will consume of memory? Let's assume that each of the numbers has 10 digits. That totals 100 digits. Would it be 800 bits (8 bits per…
whynot
  • 183
0
votes
1 answer

Language complexity from instances of graph

Let $G$ represent an undirected graph, let $a$ and $b$ represent vertices and let $k$ represent a non-negative integer. I have two languages: $L_1 = \left \{ \left \langle G, a, b, k \right \rangle \mid G \text{ contains a path of at most } k…
braedy.
  • 15
0
votes
1 answer

Prove that if $f(n) \in \mathcal{O}(h(n))$ and $g(n) \in \mathcal{O}(h(n))$ then $f(n) + g(n) \in \mathcal{O}(h(n))$

Prove that if $f(n) \in \mathcal{O}(h(n))$ and $g(n) \in \mathcal{O}(h(n))$ then $f(n) + g(n) \in \mathcal{O}(h(n))$. I know that $\mathcal{O}(g(n))=\{f\space | \space\exists c\in\mathbb{R}^{+},\exists n_{0} \in \mathbb{N},\forall n\geq n_{0} :…
Hannah
  • 73
0
votes
2 answers

Inverse of a bit conversion equation

I'm reading a computer science book that gives several functions, in the mathematical sense. There are two that are the basis of this question. These are equations used to convert a number represented in base ten to a bit representation using two's…
senordev
  • 103
0
votes
1 answer

Understanding Finite Automata Notation

I am having having troubles understanding the following finite automata example: I don't quiet understand what they mean by $B_i$ is in $q_j$. $B_i$ is a finite automation and $q_j$ is a state. I neither understand what the functions mean.
TheMathNoob
  • 2,011
0
votes
1 answer

Specify the Grammar for the Non-regular Language

I am trying to find the Grammar for the Non-regular (I've proven it by Pumping Lemma) Language: $$ L=\left\{0^{k+1}1^k0^k~~|~~ k\ge1 \right\}$$ It should generate the following: $0010, 0001100,0000111000,0000011110000,\ldots$ I have tried several…
0
votes
0 answers

Comp Science Question Divide and conquer

Design a O(n log(n)) time algorithm that computes two indices i and j (where i ≤ j) for which the sum A[i] + A[i + 1] + · · · + A[j − 1] + A[j] is maximum. Describe your algorithm in plain English. Moreover, you must use the Divide…
0
votes
0 answers

Computer Science Question

Let x, y and z be three integers. Suppose that the binary representation of x uses n bits, the binary representation of y uses n bits and the binary representation of z uses n bits. How many bits does the binary representation of the product xyz…
0
votes
2 answers

drawing markings on a ruler

Let us consider the simple ask of drawing the markings on a ruler. Each inch on the ruler has a mark at the $1/2$ inch point, slightly shorter marks at $1/4$ inch intervals, still shorter marks at $1/8$ inch intervals, and so forth. Our task is to…
0
votes
1 answer

spacing between float numbers in a range?

So i'm trying to find the spacing of float numbers in decimal in the range let's say for example [1,12) Is it as simple as something like 12-1 = 11 if not, then how?
0
votes
0 answers

Given an array $A$ of length $N<10^6,$ how many subarrays have $\text{max}(A[x:y]) - \text{min}(A[x:y]) {\le} K$?

Given any K and an array of length $N$ what is the most efficient way to find the number of unique subarrays that satisfy this constraint? I believe there is an $O(N)$ solution using monotonic queues but am unsure of the specifics. Unique refers to…
Jack Pan
  • 1,704
0
votes
1 answer

$HAM-NO-HAM$ problem: How do I show reduction from $HAMcircuit$ problem to the following problem?

consider the following language: $HAM-NO-HAM=\{(G_1,G_2)|G_1, G_2\}$ are undirected graphs, $G_1$ has a Hamilton and $G_2$ doesn't have one$\}$. i need to decide wheter it's in $P, NP, CONP$ or none of the above. If I'll show reductions from …
Jozef
  • 7,100
0
votes
1 answer

Context-free grammar and regular expression

I have got these Context-free grammar/regular expression: (1) $abba^{*}$ (2) $abb(a+b)^{*}$ (3) $a^{*}ba^{*}ba^{*}$ (4) $S \implies abA \\ A \implies Aa|b$ (5) $S \implies aS|bA \\ A \implies aA|bB \\ B \implies aB|\varepsilon$ (6) $S \implies…
0
votes
1 answer

Does a disjoint set forest have multiple distinct "upwards closed" partitions?

The following is an excerpt from a powerpoint on the role of the inverse Ackermann function in determining the complexity of path compression. Dissection of a disjoint set forest $F$ with node set $X$ Partition of $X$ into “top part” $X_t$ and…
user26649