# Questions tagged [discrete-mathematics]

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

442 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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$.)...
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 ...
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 ...
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,...
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$?
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 ...
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 ...
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\}}$$
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 ...
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 ...
164 views

1k views

### Online Learning Resources for Discrete Mathematics

Are there any good Discrete mathematics learning web resources with problem sets?
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 ...
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 ...