Discrete mathematics is the study of mathematical structures that are fundamentally discrete rather than continuous.

learn more… | top users | synonyms

1
vote
1answer
27 views

Tower Of Hanoi Time Calculation

I have been trying this Towers of Hanoi question since last week but never able to come with the right approach towards the solution. The setup is the standard Towers of Hanoi, except that moving the ...
-2
votes
0answers
15 views

Why the given relation fails to be transitive [migrated]

The need is to check if relation is equivalence or not, It can be seen it is reflexive and symmetric but I'm not able to find out if it is transitive.. The relation is defined on the set of all ...
0
votes
2answers
72 views

How to simplify the sum over 1/i?

With the recurrence relation: $$ T(n) = 2T\left(\frac{n}{2}\right) + \frac{n}{\log(n)}$$ The "sum for all levels" in the recurrence tree is: $$ \sum_{i=0}^{\log n -1} \frac{n}{\log n - i} = ...
3
votes
0answers
55 views

What is this discrete/combinatorial optimization problem?

There exist very rich literature on discrete optimization problems such as variants of knapsack problem, traveling salesman problem, orienteering problem, tourist trip design problem and etc. ...
1
vote
0answers
26 views

Describe in English the pattern in the following regular expressions [duplicate]

Describe (in English phrases) the languages associated with the following regular expression. it says to be as simple as possible ...
1
vote
2answers
34 views

Finding number of numbers <= N, containing atleast one of the digits 2,4,6,8

Given an integer $N$, I want to find the number of numbers $\le N$, that contain at least one of the digits from the set $\{2, 4, 6, 8\}$. How do I go about solving this problem? I was thinking of ...
3
votes
1answer
172 views

What do queues and stacks correspond to in math?

Many (and I suspect all) abstract data types in CS correspond to some math concepts, and even share the same names, for example, set, map, record/tuple, .... As abstract data types, what do queues ...
1
vote
1answer
30 views

Applications in Computer Sciences of Partition Functions

A partition function computes the number of ways an integer $n$ can be represented as the sum of $m$ other integers. For some value $n$, we have a partition function $p(n)$. These were studied ...
0
votes
1answer
31 views

Bytes--Measured or Counted [closed]

I hope the Computer Science section is the appropriate place to ask this question. I’m working on profiling some data sets and I am a bit tripped up on something, I was hoping I could get some ...
1
vote
0answers
44 views

the union of all the circuits and the intersection of all the bases [closed]

Is it correct that in a matroid, the union of all the circuits and the intersection of all the bases do not overlap? I susepect that is true from the equivalence in the definition for a coloop ...
1
vote
0answers
43 views

Discrete Mathematics books for Computer Science Self-study [closed]

I am an experienced software developer, want to refresh discrete math back in uni. I am looking for a book that is easy to read, contains more examples, and exercises and solutions for self study ...
5
votes
1answer
46 views

Not able to simplify a sum over reciprocals of $\log i$

Every time I solve these questions, I get stuck at the end where I need to find a closed form for the summation. Here in this case, I have reached until this point: $$ \begin{align} T(n) &= ...
2
votes
1answer
33 views

How to check if two sequences of setoid members are mutual rotations? [closed]

Task and terminology Assume we have a set $X$ and two sequences $S_1 = (a_1, a_2, \ldots,a_n)$ and $S_2 = (b_1, b_2, \ldots,b_n)$, where $a_i \in X, b_i \in X, \forall i \in [1..n]$. We define, that ...
0
votes
3answers
55 views

How do I mathematically express a set generated using two loop variables within a single for loop?

I don't know the proper mathematical expression for for-loops, especially those that carry two distinctly behaving variables with each iteration. For example, assuming ...
1
vote
2answers
313 views

Undirected graph with 12 edges and 6 vertices [closed]

For school we have to make an assignment, and part of the assignment is this question: Describe an unidrected graph that has 12 edges and at least 6 vertices. 6 of the vertices have to have ...
1
vote
0answers
26 views

Is the moment generating function for a sequence $\{a_n\}$ unique? [closed]

Suppose $\{a_n\}$ is a sequence with moment generating function $A(z)=\sum_{k \ge 0} a_kz^k$. Can a sequence $\{b_n\}$ with $b_n \neq a_n$ for at least one $n\in \mathbb N$ have the same moment ...
0
votes
1answer
137 views

Find largest chromatic number of a full binary tree [closed]

This is a Discrete Math/Combinatorics Question from my hw…but I don't really understand the question. Find largest chromatic number of a full binary tree given the following depths: (Check all ...
1
vote
0answers
21 views

Need help with Proof by Strong Induction question [closed]

So, here is the question: For any position integer n, let T(n) be the number 1 if n<4 and the number T(n-1) + T(n-2) + T(n-3) if n >= 4. We have T(1)=1, T(2)=2, T(3)=3, T(4)=T(3)+T(2)+T(1) = ...
6
votes
2answers
68 views

Finite representations and programming languages Countably inifite

I'm going over some of the pre-requisite math regarding Automata theory, and finite representations. I read the following: If ∑ is a finite alphabet the set of all strings over the alphabet (∑*) is ...
0
votes
1answer
57 views

the height of a tree given n nodes and a condition [closed]

I came across a question on which I got totally stuck :( a sort of homework question) A weight-balanced tree is a binary tree in which for each node. The number of nodes in the left sub tree is at ...
1
vote
1answer
216 views

Determining the optimal threshold value for a one-dimensional decision stump classifier

I'm currently trying to find an efficient algorithm to solve a discrete optimization problem that arises when constructing decision trees. The problem is as follows: Say we are given $N$ ordered data ...
1
vote
2answers
83 views

Why can any polynomial and exponential be represented as a recurrence?

I posted this question on math.SE but I haven't got any reply so I'm posting here also. I am reading The Algorithm Design Manual by Steven S Skiena. In Section 4.10.1 Recurrence Relations, I ...
1
vote
1answer
99 views

Why don't people use Fermat's little theorem to check if number is prime?

There're a lot of examples of code for checking if a number is prime. Why don't people use Fermat's little theorem, i.e. this simple formula $\qquad a^{p-1} \equiv 1 \pmod p$, to check if a number ...
3
votes
0answers
26 views

Elementary proof of compact space = exhaustible space?

The work of Martín Escardó has demonstrated close parallels between classical topology o one hand and computability on the other hand. (See for example "Infinite sets that admit fast exhaustive ...
2
votes
1answer
110 views

Counting elements that are greater than the median of medians

Short version: I want to know where the $-2$ comes from in the formula on p. 221 of CLRS 3rd edition. Long version: CLRS (3rd ed.) give an algorithm for $O(n)$ worst case arbitrary order statistic of ...
1
vote
1answer
128 views

how to solve this lambda expression with free variable/s

Iam a beginner in Lambda Calculus, I have a expression saying (λx.xy) Here y is a free variable and x is a bound variable. My question is what would be the value of the expression (which has free ...
0
votes
2answers
74 views

help regarding combinatorics [closed]

I want to know if there is any good book or material that fully explains and fully covers all combinatorics.I even did not find even Kenneth H.Rousan for this.So can anyone tell me any Discrete ...
2
votes
1answer
189 views

Counting the number of N-dimensional coprime integer vectors

I am looking for an efficient way to count the number of coprime vectors in a finite and bounded set of integer vectors. The vectors in my set are $N$-dimensional integer vectors whose components are ...
3
votes
1answer
82 views

Is the image of a function the codomain of a function?

Here is a definition from the functions section in my discrete math textbook (Discrete Mathematics and its Applications 7e, Rosen 2012): Let $f$ be a function from $A$ to $B$, and let $S$ be a ...
2
votes
2answers
45 views

Prove that two different concatenations of relations are equivalent

I've had this question on my exam today and I couldn't figure it out, I would like to know the answer. The question: Given relations $R$, $S$ on a set $U$. $R$ is transitive, $S$ is ...
2
votes
0answers
15 views

Computing with the Monster [duplicate]

The Monster M is the largest of the finite sporadic groups that arises in the classification of finite, simple groups in mathematics. M can be realized as a (very large!) set of ...
3
votes
2answers
173 views

Algorithm to determine if recursion was breadth first or depth first

Given a tree $T$ and a sequence of nodes $S$, with the only constraint on $S$ being that it's done through some type of recursion - that is, a node can only appear in $S$ if all of its ancestors have ...
6
votes
2answers
104 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
69 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
74 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
35 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
886 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 ...
5
votes
3answers
220 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 ...
6
votes
1answer
303 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
97 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 ...
6
votes
3answers
225 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
36 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 ...
6
votes
2answers
221 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 ...
5
votes
1answer
421 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
116 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, ...
2
votes
0answers
44 views

Is there a formal CS definition of VCS and file versions?

I don't know whether it was a joke, but once I read what was referred to as a formal definition of a file in a versioning system such as git, hg or svn and that was something like a mathmetaical ...
-4
votes
1answer
304 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$?
11
votes
2answers
276 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
61 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
49 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\}}$$