All Questions
Tagged with discrete-mathematics computer-science
716
questions
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
28
votes
7
answers
5k
views
How do you correctly reason that this directed graph is acyclic?
How can you correctly reason that this directed graph is acyclic?
I can only visually say that this graph is acyclic because there is not a single path in the graph where the starting vertex is equal ...
- 953
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
15
votes
2
answers
533
views
Is there an infinite set of finite strings such that no element is a subsequence of another?
Of course, this is meant to be over a finite alphabet. My intuition is that this doesn't exist over any such alphabet, so that's what I'd want to know how to prove.
I'm also interested in questions ...
- 558
14
votes
3
answers
9k
views
"Opposite" of idempotent operation?
What is the adjective given to a mathematical operation/expression on a variable whose new value can only be described in terms of that variable's existing value? Sequential operation?
Example: i = i ...
- 253
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
14
votes
5
answers
23k
views
What is the difference between discrete and continuous mathematics?
I am studying computer science and this has me absolutely flummoxed. The definition I can find is that discrete data is countable and that continuous is uncountable.
Examples are given stating that ...
- 241
12
votes
4
answers
21k
views
How many bit strings of length 8 start with "1" or end with "01"?
A bit string is a finite sequence of the numbers $0$ and $1$. Suppose we have a bit string of length $8$ that starts with a $1$ or ends with an $01$, how many total possible bit strings do we have?
I ...
- 263
11
votes
3
answers
393
views
Counting sets by their connectedness
Let $U = \{u_1, u_2, \ldots , u_m \}$ where each $u_i$ is an $r$-subset of $[n]$ and
$\,\bigcup u_i \!=\! [n]$. Construct the intersection graph of $U$. That is, let node $i$ correspond to $u_i$ and ...
- 1,499
10
votes
3
answers
5k
views
Mathematical Explanation of the Difference between SQL Joins: Inner, Outer, Left, Right
Question
This question calls for a mathematically sound & intuitive explanation of SQL joins that clearly shows the difference between the following:
Inner Join
Left Join
Right Join
Full Outer ...
- 4,729
10
votes
5
answers
2k
views
convert ceil to floor
Mathematically, why is this true?
$$\left\lceil\frac{a}{b}\right\rceil= \left\lfloor\frac{a+b-1}{b}\right\rfloor$$
Assume $a$ and $b$ are positive integers.
Is this also true if $a$ and $b$ are ...
- 203
9
votes
2
answers
1k
views
In how many different from a set of numbers can a fixed sum be achieved?
I have a set of number, and I want to know in how many ways from that set with each number being used zero, once or more times can a certain sum if at all, be achieved. The order doesn't matter. For ...
- 193
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
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
8
votes
5
answers
9k
views
Big-O notation Basics, is it related to derivatives?
I am having the hardest time with Big-O notation (I am using this Rosen book for the class I am in).
On the surface, Big-O reminds me of derivatives, rate of change and what not; is this proper ...
- 325