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

Implementation of Heap (ADT) using Array Vs. LinkedList

In data-structure course , I need to implement a binary heap with the following time - complexity requirements: Find Max - O(1) Insert - O(log n) Delete Max - O(log n) Now I thought to implement this using array in the following way: The root of…
Noam
  • 853
  • 4
  • 16
0
votes
1 answer

How to Alphabetically Arrange Nodes in a Huffman Tree

Suppose there is a string of characters helloworld. The frequency of these characters are d1, e1, h1, l3, o2, r1, w1. So, when inserting them into the huffman tree, the root node should contain d1, but where should e1 and h1 go? In other words, how…
LaSpana101
  • 115
0
votes
1 answer

Why is the amortized time for path compressions approximately $\mathcal{O}(1)$?

For optimization of Find operations (an operation that returns the representative of the set a node belongs to) in a disjoint-set structure, path compression is used. Analysis of the operation approximately yields amortized complexity…
user26649
0
votes
1 answer

How instances of Automaton(NPDA) read and write the stack

I am reading a text book, Introduction of the theory of computation by Michael Siper. I do not understand the notion of NPDA well. One problem is that the definition of NPDA is not clear on how the stack is shared by possibly many instances of the…
kobu-kuro
  • 91
0
votes
1 answer

Extract each digit of a binary \ decimal number

How can one extract the digits of a binary \ decimal number. For example i have 100110111 to need to extract them only using +,-,*,/ and MOD. I can only use this LOOP Language. Most of the algorithms use floor function with decimal numbers, but i…
thetha
  • 472
0
votes
2 answers

Formal definition of Big-O Notation?

Big O Notation is formally defined as: Let $f(n)$ and $g(n)$ be function from positive integers to positive reals. We say $f = \theta(g)$ (which means that "$f$ grows no faster than $g$*) if there is a constant $c>0$ such that $f(n) ≤ c ⋅…
user26649
0
votes
1 answer

what is the data byte encoded in binary Hamming code?

the problem I am presented with is a binary hamming code shown below: 011101000100, what was the data byte encoded and sent from this hamming code? and the solution is 10101100, could someone explain to me how to approach this problem?
please rekt me
  • 13
0
votes
0 answers

How can a program calculate the distance along a road from point $A$ to point $B$?

Just as an example, when I go to Google Maps and get directions, it tells me how far along a road I need to travel to get to my next turn. For example, when I get directions from SeaWorld San Antonio to the Alamo, it says I need to travel $16.8$…
moonman239
  • 553
0
votes
2 answers

Halting problem confusion

Does the non-solvability of the halting problem mean that no program can tell if an arbitrary program halts, or only that if such a program exists then there is no computable proof that it works?
TROLLHUNTER
  • 8,728
0
votes
1 answer

Pumping lemma for $a^n b^m a^{n+m}$

I want to show that $L = \{a^n b^m a^{n+m} \mid n, m \geq 0\}$ is not regular. Is it suffice to say that $a^0b^pa^p$ is in the language, then y = $a^k$ with 0 < k <= p, choose i = 0 so I get $a^{−k}b^pa^p$ which is not in the language?
user270494
  • 687
0
votes
1 answer

Suppose that a and b are n-character Strings. what is the complexity of performing a=a+b?

Suppose that a and b are n-character Strings. what is the complexity of performing a=a+b? my answer is O(n) but i am not sure if this is correct.
bill
  • 1
0
votes
1 answer

Master's Theorem?

When the ratio is $1$, why does the efficiency of the algorithm evaluate to $\mathcal{O} \left( n^d \log n \right)$? The total work done would be: $$T(n) = \mathcal{O}(n^d) (1+1+\cdots+1^k)$$ $$= \mathcal{O}(n^d) (1)(\log_b n)$$ where $n$ is the…
user26649
0
votes
2 answers

Unique Aggregation of Numbers

Suppose I have 5 numbers: 1,7,13,5,6. I want to perform some kind of algorithm that allows me to derive a number such that if any of those numbers changed in value or switched in order that I would get a different aggregate. The aggregate must be…
Brian White
  • 1
0
votes
2 answers

Adding color components from (r,g,b,a) space

If we define a color with transparency as $(r,g,b,a)$ (red,green,blue,alpha), with $r,g,b,a\in[0,1]$, how do we define $(r_1,g_1,b_1,a_1)+(r_2,g_2,b_2,a_2)$? The definition must be closed, and must represent the computer science version of adding…
JMP
  • 21,771
0
votes
5 answers

explanation of notation in programming problem

I am trying to attempt to solve this problem but I am unsure what this equation means: $$\frac{n!}{ r!(n-r)!}$$ What do the exclamation marks mean in the above?
dagda1
  • 825
1 2 3
…
16 17