Questions tagged [discrete-mathematics]

Questions about discrete mathematics, the study of mathematical structures that are fundamentally discrete rather than continuous.

Filter by
Sorted by
Tagged with
8
votes
2answers
319 views

Courcelle's Theorem: Looking for papers

I am looking for an easy and introductory paper on the proof of Courcelle's Theorem. I am also interested in its connection to parameterized complexity regarding the treewidth. I am only a beginner ...
2
votes
1answer
123 views

What will be minimum no of operation to make whole matrix zero if one is allowed to multiply a row or column by zero?

Suppose we are given an M×N matrix, with some elements are zero, some non-zero. We know the co-ordinates of non-zero elements. Now, if I am allowed to multiply a whole row or a whole column by zero ...
0
votes
1answer
155 views

trouble with bijection definition [closed]

I have a bijection problem that I cannot get my head around. It goes like this: let f: A -> B and g: B -> C be functions such that g o f is a bijection. Prove that f must be one-to-one and that g ...
0
votes
1answer
67 views

Math term for Associative arrays/Maps/Dictionaries

What would be the equivalent math concept for associative arrays/maps/dictionaries? EDIT: Disregard mutability. FYI,off topic, the reason why I ask this question, is that I want to calculate the ...
3
votes
3answers
13k views

Why is discrete mathematics required for data structures?

Data Structures is the second CS course taught at Columbia University and it lists Discrete Mathematics as a Co-Req. I have a BSEE and have not taken any discrete mathematics and am having a hard ...
14
votes
4answers
1k views

Bridge theorems for group theory and formal languages

Is there some natural or notable way to relate or link math groups and CS formal languages or some other core CS concept e.g. Turing machines? I am looking for references/applications. However note ...
7
votes
1answer
2k views

Proof of Ramsey's theorem: the number of cliques or anti cliques in a graph

Ramsey's theorem states that every graph with $n$ nodes contains either a clique or an independent set with at least $\frac{1}{2}\log_2 n$ nodes. I tried to look it up at a few places (including ...
2
votes
1answer
117 views

No of ways in which n indistinguishable items can be placed in m indistinguishable boxes [closed]

This problem is the same as number of ways to partition n into exactly m parts. The recurrence given in Wikipedia has p(n,k) = the number of partitions of n using only natural numbers ≥ k How ...
8
votes
3answers
447 views

Algorithm to shrink a DFA by introducing nondeterminism?

This is somewhat related to another question I asked, but I feel it's different enough to warrant its own question. I'm doing research where I'm trying to find the structure of complements of a ...
5
votes
1answer
81 views

Subgraph isomorphisms: does large out-expansion imply large in-expansion?

Let $G$ be a directed graph, and $H$ a subgraph of $G$ that contains all the vertices of $G$. (In other words, $H$ is obtained by deleting some of the edges of $G$, but not any of the vertices of $G$.)...
10
votes
2answers
922 views

What mathematics can be interesting for these CS areas?

For my CS degree I have had most of the "standard" mathematical background: Calculus: differential, integral, complex numbers Algebra: pretty much the concepts up until fields. Number Theory: XGCD ...
6
votes
1answer
1k views

circle packing algorithm used by Percolator

I was admiring this rendition of the Mona Lisa from quasimondo's Flickr account. He says: Combining circle packing with data visualization. The pie charts show the distribution of the dominant ...
0
votes
1answer
127 views

How this expression leads to the given sequence

Here given is a sequence from OEIS. The sequence is triangle of coefficients from fractional iteration of e^x - 1. Few terms are: 1, 1, 3, 1, 13, 18, 1, 50, 205, 180, 1, 201, 1865, 4245, 2700, 1, 875,...
-3
votes
1answer
3k 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$?
14
votes
2answers
2k 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
240 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 ...
2
votes
1answer
69 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\}}$$
6
votes
1answer
3k 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 ...
9
votes
1answer
1k 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
164 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 \...
38
votes
6answers
7k views

What use are groups, monoids, and rings in database computations?

Why would a company like Twitter be interested in algebraic concepts like groups, monoids and rings? See their repository at github:twitter/algebird. All I could find is: Implementations of ...
2
votes
1answer
1k 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 ...
4
votes
2answers
361 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 $X$...
0
votes
1answer
500 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 ...
5
votes
2answers
426 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
152 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 ...
10
votes
3answers
51k 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
207 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 ...
2
votes
1answer
95 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 ...
6
votes
1answer
1k 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, ...
15
votes
1answer
428 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
386 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 negation is ...
2
votes
1answer
52 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 by ...
21
votes
1answer
14k 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. ...
12
votes
0answers
779 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 $x=(...
10
votes
5answers
29k 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 ...
20
votes
3answers
10k 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 ...
9
votes
3answers
1k views

Online Learning Resources for Discrete Mathematics

Are there any good Discrete mathematics learning web resources with problem sets?
16
votes
1answer
225 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 ...
7
votes
2answers
444 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 ...
29
votes
2answers
12k 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 ...
20
votes
4answers
9k 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 ...

1
5 6 7 8
9