All Questions
Tagged with discrete-mathematics computer-science
716
questions
3
votes
1
answer
6k
views
How to find the number of normalised floating point numbers in a system?
I'm trying to make floating point number systems a bit more intuitive for myself. There are a few things I am confused about, and I think the best way to clear up my confusions would be for someone to ...
- 131
4
votes
1
answer
2k
views
Over an alphabet of $n$ symbols, how many are the strings of length $k$ without consecutive symbols repeated?
From combinatorics, it's known that over an alphabet of $n$ symbols there are $n^k$ different strings of length $k$, of which $\frac{n!}{(n-k)!}$ (assuming $k \le n$) are those without any repeated ...
- 145
2
votes
1
answer
391
views
Pumping lemma usage
I need to know if my solution for a problem related with regular languages and pumping lemma is correct.
So, let $L = \{a^ib^jc^k \mid i, j,k \ge 0 \mbox{ and if } i = 1 \mbox{ then } j=k \}$
Now i ...
user19410
25
votes
1
answer
763
views
Always oddly-many ones in the binary expression for $10^{10^{n}}$?
Update: Pending independent verification, the answer to the title question is "no", according to a computation of $q(10) = 11609679812$ (which is even).
Let $q(n)$ be the number of ones in the ...
- 15.1k
9
votes
2
answers
1k
views
Given $N$, count $\{(m,n) \mid 0\leq m<N, 0\leq n<N, m\text{ and } n \text{ relatively prime}\}$
I'm confused at exercise 4.49 on page 149 from the book "Concrete Mathematics: A Foundation for Computer Science":
Let $R(N)$ be the number of pairs of integers $(m,n)$ such that $0\leq m < N$, $...
- 221
4
votes
4
answers
2k
views
First order logic and higher order logics?
I hear that Prolog is based in first-order logic. This makes me wonder, C/C++ are based on which higher order logics?
If this question is incorrect, please point out that.
and how are these logics ...
- 311
45
votes
4
answers
43k
views
What books do you recommend before 'Concrete Mathematics'?
What book(s) do you recommend before Concrete Mathematics?
Is something like "Introduction to discrete Mathematics" enough?
- 553
4
votes
2
answers
3k
views
Addition on big omega notation
It seems to my uneducated mind that if I have $\frac{n}{k}$ subproblems, each of size $\Omega (k \log k)$, that my overall problem must be at least of size $\Omega (n \log k)$, by the reasoning that ...
- 544
9
votes
2
answers
1k
views
Looking for a bijective, discrete function that behaves as chaotically as possible
I need to write a coupon code system but I do not want to save each coupon code in the database. (For performance and design reasons.) Rather I would like to generate codes subsequent that are ...
- 255
3
votes
3
answers
6k
views
What are the prerequisites for combinatorics?
I'm looking to strengthen my understanding of the math that is directly useful to practical computer science, as opposed to unsolved computer science problems. In other words, the kind of math that ...
- 55
14
votes
2
answers
2k
views
Twenty questions against a liar
Here's one that popped into my mind when I was thinking about binary search.
I'm thinking of an integer between 1 and n. You have to guess my number. You win as soon as you guess the correct number. ...
- 1,445