# Tagged Questions

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 ...

265 views

### Huffman Encoding Proof Probability and Length

If the frequency of symbol i is strictly larger than the frequency of symbol j, then the length of the codeword for symbol i is less than or equal to the length of the codeword for symbol j. I ...
291 views

### Algorithms for solving the discrete logarithm $a^x \equiv b\pmod{n}$ when $\gcd(a,n) \neq 1$

The general discrete logarithm problem is to find $x$ given $a, b$ and $n$ such that $$a^x \equiv b\pmod{n}.$$ Normally one can use the "baby-steps giant-steps" algorithm to solve it fairly quickly. ...
56 views

100 views

### Computability and continuous real functions

I have found somewhere the following statement: "Every computable real function has to be continuous," but I'm not able to prove it and the "proofs" that I found in some blog posts don't seem ...
39 views

### Is $L_1$ context free language?

Let $L = L_1 \cap L_2$, where $L_1$ and $L_2$ are languages as defined below: $L_1= \left \{ a^m b^mca^nb^m \mid m,n \geq 0 \right \}$ $L_2=\left \{ a^i b^j c^k \mid i,j,k \geq 0 \right \}$ Then L ...
12k views

### What makes a context free grammar ambiguous?

What makes a context free grammar ambiguous?
6k views

### fast algorithm for solving system of linear equations

I have a system of linear equations, $Ax=b$, with $N$ equations and $N$ unknowns ($N$ large) If I am interested in the solution for only one of the unknowns, what are the best approaches? for ...
1k views

### Does DTIME(O(n)) = REGULAR?

(I don't think that this is a good fit on cstheory, since I figure that this question already has a known answer. However, if you think that this would be a better fit there, please feel free to ...
12k views

### Reduction from Hamiltonian cycle to Hamiltonian path

I'm looking for an explanation on how reducing the Hamiltonian cycle problem to the Hamiltonian path's one (to proof that also the latter is NP-complete). I couldn't find any on the web, can someone ...
362 views

### Matrix Chain Multiplication?

The following are questions about using dynamic programming for matrix chain multiplication. Pseudocode can be found in the Wikipedia article on matrix chain multiplication. 1) Why is the time ...
717 views

### Can a polynomial size CFG over large alphabet describe a language, where each terminal appears even number of times?

Can a CFG over large alphabet describe a language, where each terminal appears even number of times? If yes, would the Chomsky Normal Form be polynomial in |Î£| ? EDIT: What about a language where ...
587 views

### Why do we divide or multiply by 2 when converting binary?

Trying to understand the fundamentals of binary rather than just following steps, I wanted to know why do we multiply by 2 to convert a decimal (0.5, 0.25) to a binary and why do we divide by 2 when ...
151 views

### What is the algorithm hiding beneath the complexity in this paper?

So, I am a computer scientist (at least, I'm working to become one..) and I asked a question on here concerning some mathematics behind the Mandelbrot set. A reply I recieved pointed me to this paper. ...
371 views

### Reasoning the calculation of the Hilbert's distance

I'm not a mathematician, I'm a computer science student, and I'm attending to a course called Advanced Functional Programming. There's this homework where I need to implement the Hilbert R-tree data ...
411 views

### Proving formula for sum of squares with binomial coefficient

$$\sum_{k=0}^{n-1}(k^2)= \binom{n}{3} + \binom{n+1}{3}$$ How should I prove that it is the correct formula for sum of squares? Should I use induction to prove the basis? Any help is appreciated.
232 views

496 views

### Etymology of “topological sorting”

This may be a dumb question, but what's "topological" about topological sorting in graph theory? I thought topology was related to geometry and deformations.
579 views

### Throwing balls into $b$ buckets: when does some bucket overflow size $s$?

Suppose you throw balls one-by-one into $b$ buckets, uniformly at random. At what time does the size of some (any) bucket exceed size $s$? That is, consider the following random process. At each of ...
1k views

### Finding the 2,147,483,647th prime number

In computer science an array is indexed by an integer (int). Unlike in mathematics, the computer science integer (int) has a ...
192 views

### How to maximize the number of operations in process

In my research project I have encountered the following problem, concerning a tuple of words in the formal language $L=\{0,1\}^*$, with $\epsilon$ denoting the empty word. If we are given an ordered ...
### Finite automaton that recognizes the empty language $\emptyset$
Since the language $L = \emptyset$ is regular, there must be a finite automaton that recognizes it. However, I'm not exactly sure how one would be constructed. I feel like the answer is trivial. ...
How can I prove that $T(n) = 2T(n/2) + n$ is $O(n \log n)$ ?