Discrete mathematics is the study of mathematical structures that are fundamentally discrete rather than continuous.
-3
votes
1answer
60 views
Proving that the largest number of leaves in an $n$-ary tree of height $k$ is $k^n$
How to prove that the largest number of leaves in an $n$-tree of height $k$ is $k^n$?
8
votes
1answer
79 views
How to practically construct regular expander graphs?
I need to construct d-regular expander graph for some small fixed d (like 3 or 4) of n vertices.
What is the easiest method to do this in practice?
Constructing a random d-regular graph, which is ...
1
vote
2answers
51 views
How to distinguish empty cells from cells outside of the input cells?
Setup
I need to develop a Turing Machine that accepts a string m that has the same number of a's and b's.
My alphabet is {a,b}, and we use a diamond in class to represent an empty space.
Problem
...
1
vote
1answer
42 views
Faster Algorithm for Computing Norm
Can anyone suggest an algorithm faster than $\Theta(n^{2})$ for computing the following function:
$$||n||:=\frac{1}{\max\{k \in \mathbb{N}: 1|n, 2|n,\ldots,k|n\}}$$
-4
votes
2answers
57 views
Binary Substraction Operation Closed Over The Set Of Natural Numbers [closed]
HISTORY AND REASONING (skip to BINARY OPERATION for actual question)
British mathematician Francis Maseres claimed that negative numbers:
"... darken the very whole doctrines of the equations and ...
4
votes
1answer
66 views
What is the maximum number of shortest paths between any pair of vertices in a chordal graph?
A graph $G$ is chordal if it doesn't have induced cycles of length 4 or more. Chordal graphs are precisely the class of graphs that admit a clique tree representation. A clique tree $T$ of $G$ is a ...
4
votes
1answer
30 views
How to construct this generalized xor without needing an extra vector?
Operator - Generalized Symmetric Difference
If you take binary xor and generalize it to other radices
you can do so by the absolute value of the difference of each
element in a radix vector.
However ...
2
votes
2answers
113 views
Finding the number of iterations to a recurrence
I have an algorithm where the number of items in my set decrease by $\sigma/(1+\sigma)$ on each iteration until all items are exhausted.
$$
\begin{align*}
S_0 &= S \\
S_{k+1} &= S_k - S_k ...
4
votes
1answer
48 views
Complexity of GF(2) and applications to cryptography
If I have a system of N polynomial equations with N unknowns in GF(2):
What are some good methods to solve them?
What are some software packages or libraries that implement this?
What's the highest ...
16
votes
6answers
397 views
What use are groups, monoids, and rings in database computations?
Why would a company like Twitter be interest in algebraic concepts like groups, monoids and rings. https://github.com/twitter/algebird
All I could find is:
Implementations of Monoids for ...
1
vote
1answer
123 views
Calculating Binet's formula for Fibonacci numbers with arbitrary precision
Binet's formula for the nth Fibonacci numbers is remarkable because the equation "converts" via a few arithmetic operations an irrational number $\phi$ into an integer sequence. However, using finite ...
3
votes
1answer
76 views
Find vectors with elements of finite fields that sum up to given value
Given a universe $U$ consisting of k sets of vectors with each vector $\vec{v} \in {\mathbb{F}_{p^m}}^n $. Given also another vector $\vec{c} \in {\mathbb{F}_{p^m}}^n$.
Now decide if there is a set ...
0
votes
1answer
111 views
Why is $\sum_{j=0}^{\lfloor\log (n-1)\rfloor}2^j$ in $\Theta (n)$?
I am trying to understand summation for amortization analysis of a hash-table from a MIT lecture video (at time 16:09).
Although you guys don't have to go and look at the video, I feel that the ...
3
votes
2answers
98 views
What are some applications of binary finite fields in CS?
I was looking at details on finite fields. Finite binary fields, e.g. $\mathbb{F_2}$, are used in CS in some places such as circuit theory [1].
What are some key applications of finite fields in ...
2
votes
0answers
107 views
What is the time complexity of computing $\frac{1}{2^n} {{n}\choose{(n+2)/2}}$
What is the time complexity of computing $\frac{1}{2^n} {{n}\choose{(n+2)/2}}$?
$$\frac{1}{2^n} {{n}\choose{(n+2)/2}} = \frac{1}{2^n} \frac{n(n-1)\cdots ((n-2)/2)}{((n+2)/2) (n/2) \cdots 1}$$
The ...
3
votes
2answers
481 views
Why is the minimum height of a binary tree $\log_2(n+1) - 1$?
In my Java class, we are learning about complexity of different types of collections.
Soon we will be discussing binary trees, which I have been reading up on. The book states that the minimum height ...
6
votes
1answer
159 views
What's a fast algorithm to decide whether there is an $A_G$ corresponding to a given $\chi_G(\lambda)$?
Given an adjacency matrix $A_G$ of an undirected graph $G$, it is easy and straightforward to compute the characteristic polynomial $\chi_G(\lambda)$. What about the other way around? The problem can ...
1
vote
1answer
42 views
What is a good resource to learn about oriented matroids in the context of digraphs and optimization?
I am interested in oriented matroids in the context of directed graphs and optimization. Unfortunately, I know very little of the topic. Is there a book, article or a resource that serves as a good ...
4
votes
1answer
267 views
Fastest square root method with exact integer result?
I am dealing with the problem of computing $ s = \lfloor sqrt(x)\rfloor$ with $x \in [0,30000^2]$. The common sqrtf(x) on C language is too slow for this case, ...
8
votes
0answers
153 views
On “The Average Height of Planted Plane Trees” by Knuth, de Bruijn and Rice (1972)
I am trying to derive the classic paper in the title only by elementary means (no generating functions, no complex analysis, no Fourier analysis) although with much less precision. In short, I "only" ...
0
votes
2answers
131 views
Predicate Logic Paradox [duplicate]
Possible Duplicate:
Negation of nested quantifiers
The problem is:
∃x∀y(x ≥ y)
With a domain of all real positive integers.
The negation is:
∀x∃y(x < y)
so, if y = x + 1
the ...
2
votes
1answer
48 views
Solving $\text{key}=(\sum_{K=0}^n\frac{1}{a^K})\bmod m$ with High limits
I was solving this equation:
$$\text{key}=\left(\sum_{K=0}^n\frac{1}{a^K}\right)\bmod{m}.$$
Given
$$ 1,000,000,000 < a, n, m \; < 5,000,000,000, $$
$$ a, m \text{ are coprime}. $$
I solved it ...
15
votes
1answer
412 views
Pizza commercial claim of 34 million combinations
A pizza commercial claims that you can combine their ingredients to 34 million different combinations. I didn't believe it, so I dusted off my rusty combinatorics skills and tried to figure it out. ...
6
votes
0answers
83 views
Fast algorithm for max-convolution with concave functions?
I'm interested in a discrete max-convolution problem, which is to compute
$$r(c) = \max_{x | x \ge 0, \sum_k x_k = c} \left[ \sum_{k=1} f_k(x_k) \right] $$
for all values $c=0, \ldots, C$, where ...
3
votes
4answers
539 views
How much math does one need to know to understand discrete math/structures for computer science?
Normally universities teach discrete math / discrete structure. My question is, how much math does one need to know to understand this area? Is calculus required or will precalculus do just fine? Does ...
7
votes
2answers
234 views
How hard is finding the discrete logarithm?
The discrete logarithm is the same as finding $b$ in $a^b=c \bmod N$, given $a$, $c$, and $N$.
I wonder what complexity groups (e.g. for classical and quantum computers) this is in, and what ...
4
votes
2answers
200 views
Online Learning Resources for Discrete Mathematics
Are there any good Discrete mathematics learning web resources with problem sets?
10
votes
1answer
91 views
Polytime and polyspace algorithm for determining the leading intersection of n discrete monotonic functions
Some frontmatter: I'm a recreational computer scientist and employed software engineer. So, pardon if this prompt seems somewhat out of left field -- I routinely play with mathematical simulcra and ...
6
votes
2answers
173 views
Are two elements always in a relation within a partially ordered set?
In a partially ordered set, am I always able to order two arbitrary elements out of the set? Or is it possible that two elements within the set have no order relation to each other?
For example if ...
16
votes
2answers
1k views
Counting binary trees
(I'm a student with some mathematical background and I'd like to know how to count the number of a specific kind of binary trees.)
Looking at Wikipedia page for Binary Trees, I've noticed this ...
9
votes
2answers
343 views
What is an intuitive way to explain and understand De Morgan's Law?
De Morgan's Law is often introduced in an introductory mathematics for computer science course, and I often see it as a way to turn statements from AND to OR by negating terms.
Is there a more ...
