Questions tagged [discrete-mathematics]
Questions about discrete mathematics, the study of mathematical structures that are fundamentally discrete rather than continuous.
485
questions
0
votes
0
answers
17
views
Is there any upper bound for the number of ways we can partition a multiset, where each part/segment in the partition has distinct elements?
A question is asked in the below link, which asks for the number of cases we can partition a multiset, where each part/segment in the partition has distinct elements.
https://math.stackexchange.com/...
- 1
-2
votes
0
answers
23
views
Prove there is a way to partition vertices of a simple graph into two groups so that degree of each vertex will be even in it's group induced subgraph
One of our groups can be empty Hint : we should use induction Question designer also suggested to choose one vertex first then supplement its neighbourhoods induced subgraph and then delete selected ...
0
votes
0
answers
32
views
How many ways we can partition a multiset, where each part/segment in the partition has distinct elements? [duplicate]
We define the set S as {(s1, f1), (s2, f2), ..., (si, fi)}, where each si is the frequency that it is repeated in the multiset T. How many ways can we partition the multiset T into different ...
- 1
1
vote
1
answer
30
views
Finding all zero sums of length m and checking for zero subsums on an abelian group (generalization of the sub sum problem?)
Let $G$ be an abelian group. We say that $G$ has property $V_n$ if for every $m > n$ and a list $L\subset G$ of $m$ elements s.t. $\sum_{g\in L}g=0$ there is a proper subset $\emptyset\neq L'\...
0
votes
0
answers
15
views
The RAM invalid object estimation problem
The following problem is originated from my research work in my startup.
Suppose we have a collection of $k$ memory objects, where object $i$ has size $d_i$ bytes. We consider a process where the ...
- 367
1
vote
1
answer
37
views
Number of ways to make change in o(k), where k is number of coins
Godd afternoon,
We have set C of k coins; For example C = (2, 3)
We have positive integer n.
In how many ways we can represent n using those coins?
Example:
If n = 12; C = (2, 3) we can represent 12 ...
- 111
2
votes
0
answers
37
views
Effecient algorithm to build a linear order on a set of states of automaton
Is there an algorithm that help to build a linear order on a set of states of automaton (without output signals), such that this order is compatible with a transtion function of automaton?
Let A = (X, ...
- 21
0
votes
2
answers
71
views
How to represent a point cloud in the pseudocode of an algorithm?
I am writing a scientific paper in which I describe some algorithms (using pseudocode) that have point clouds as inputs. In these algorithms, I need a mathematical structure to represent a point cloud....
1
vote
1
answer
28
views
Universal class $\mathcal{H}_{p, m}$ of hash functions has $p(p-1)$ members
In CLRS it is stated that the class $\mathcal{H}_{p, m} = \{ h_{ab}:\mathbf{Z}_p \to \mathbf{Z}_m \mid a \in \mathbf{Z}_p^*, b \in \mathbf{Z}_p\}$, $h_{ab}(x) = (ax+b) \mod p \mod m$, $m < p$ prime ...
- 13
1
vote
0
answers
50
views
Sum of coprime divisors
Define the following function to be the count of integers not greater than $L$ that are coprime to $n$:$$C(n,L)=\sum_{k=1 \atop {GCD(n,k)=1}}^L1$$
Then I am interested in the following sum:
$$S(x)=\...
- 143
3
votes
1
answer
76
views
Counting integers $n \leq x$ with a given prime signature
Given is a prime signature $S$ and an integer $x$. The task is to count how many integers $n$ exist such that $n \leq x$, and if $n = p_1^{k_1}p_2^{k_2}p_3^{k_3}p_4^{k_4}...$ then $S = (k_1,k_2,k_3,......
- 143
0
votes
0
answers
12
views
Schedule N captains, N copilots, N routes in N months
I have a problem as following:
Given N captains, N copilots, N routes and N months. How to schedule flights which satisfy:
Each captain fly new route every month in N months
Each copilot fly new ...
- 123
0
votes
1
answer
37
views
Algorithms for finding closest graph node within set of nodes
Given a set of nodes $N$ on an undirected, weighted graph $G$ and a query node $n$, what is the fastest algorithm for finding the node in $N$ that is closest to $n$?
Furthermore, say we are doing many ...
0
votes
0
answers
32
views
Baby step giant step algorithm complexity calculation
My question here is mainly a way for me to understand complexity a little better by a confusing example. From what I understand of calculating the complexity of an algorithm, we take the number of bit ...
-1
votes
1
answer
39
views
Need help proving the following for every integer n larger or equal to 1
i need help proving the following :
$$\sum_{k=1}^{n}\frac{1}{(3k-1)(3k+2)}=\frac{n}{6n+4}$$ for every integer n larger or equal to 1
Can you help? Thanks
1
vote
0
answers
45
views
Distinguishing two distributions with f-divergence
The statistical distance (SD) has been widely used as a 'measure' of the closeness of two distributions $D_1$ and $D_1$.
Suppose that the statistical distance (here, total variation with $\ell_1$ norm)...
- 11
1
vote
1
answer
22
views
Decomposing large bit mult or exp into smaller bit operations
Imagine a machine that can only hold N-bit values (N-bit uint).
The machine can also calculate the 2N-bit result of two operations: mult, exp.
The 2N-bit result is stored across 2 N-bit values (high/...
- 11
0
votes
2
answers
155
views
Sum of average of all subarrays
Suppose there is an integer array $a_1,a_2,...,a_n$. Calculate the sum of average of all subarrays. For example, the sum of average of all subarrays of array $[1,3,5]$ is $1+3+5+\frac{1+3}{2}+\frac{3+...
- 19
0
votes
0
answers
21
views
What Basic (pre-discrete maths course) areas to focus on - and what resources would be recommended?
To cut a long story short, I'm a mature CS student with fairly rusty maths skills, going into my second last year of my degree. I had studied maths to the sort of decent-ish high school level you'd ...
- 1
0
votes
1
answer
65
views
Walk from vertex u to vertex v on complete graph, formula for number of walks of length k
Complete graph with n vertices.
Walk from vertex u to vertex v of length k.
I don't understand how the number of walks between the two of length k is $n^{k-1}$
I've tried this formula on an example ...
- 13
0
votes
1
answer
52
views
equivalency of some facts in $O$ notation
I misunderstanding about some logarithm property in algorithm course:
is it correct that we say following three term is equivalent?
$O(\log a + \log b)$
$O(\log (ab))$
$O(\log (a+b))$
- 381
0
votes
0
answers
30
views
Finding Sum(F(i)) where F(i) = min(⌈ Ai / B1 ⌉ * C1, ⌈ Ai / B2 ⌉ * C2, ⌈ Ai / B3 ⌉ * C3, .... ,⌈ Ai / Bm ⌉ * Cm)
Given three arrays A, B, and C of size n, m, and m respectively (1-based indexed). A function F(i) is defined as -
F(i) = minimum_of(⌈ Ai / B1 ⌉ * C1 , ⌈ Ai / B2 ⌉ * C2 , ⌈ Ai / B3 ⌉ * C3 , .... , ⌈ ...
- 1
0
votes
0
answers
43
views
The relationship between types of registers / feedback functions and de Bruijn sequences, and how these feedback functions are created
I have been learning about de Bruijn sequences recently, and have a decent sense what they are. There seem to be 3 or 4 primary methods for generating de Bruijn sequences:
Feedback functions/...
- 1,943
1
vote
0
answers
23
views
How do you generate lots of binary de Bruijn sequences (somewhat small, such as less than 100 bits)?
I have been learning about de Bruijn sequences recently. I looked at this C library on Greedy algorithms, and took what I learned to make this JavaScript version, which tries to make as many de Bruijn ...
- 1,943
1
vote
1
answer
51
views
What is a de Bruijn sequence exactly?
I just discovered the term "de Bruijn sequence", but don't quite follow what it means exactly (or how de Bruijn is pronounced :), "brown" I guess).
There are two good resources I ...
- 1,943
0
votes
1
answer
73
views
Mathematical Induction vs Strong Induction
In Rosen's book Discrete Mathematics and Its Applications, 8th Edition it is mentioned that:
You may be surprised that mathematical induction and strong induction are equivalent. That is, each can ...
- 337
0
votes
0
answers
21
views
Can you recommend some materials on Turing Machine?
I need exercises with answers to practice building Turing machines. Books, online resources etc.
Can anyone recommend something?
- 1
1
vote
1
answer
81
views
3-colouring with a bounded amount of colors
The topic of 3-colouring is often talked about, but what happens if we limit the amount of times we can use one color? Take a graph $G=(V,E)$ with $k$ being the number of vertices, is it possible for ...
- 49
2
votes
1
answer
35
views
Satisfiability of bounded assignment of input variables to CNF formula
Consider a CNF formula $F$ such that all the literals in every clause must be negative ( here is an example : $F$ = ($\bar{x_{1}}$ $\wedge$ $\bar{x_{2}}$) $\vee$ ($\bar{x_{3}}$ $\wedge$ $\bar{x_{4}}$ $...
- 49
0
votes
0
answers
25
views
Graph with constant edge connectivity that remains connected after edge removals
I have an undirected graph $(V, E)$ with constast edge connectivity $\lambda$. Each edge is sampled independently with probability $min\{1,\frac{c \ln n}{\lambda}\}$ for some $c > 0$. I need to ...
- 149
2
votes
0
answers
35
views
Proving existence of sinkless orientation on graph with minimum degree 2
I am given a graph of minimum degree at least 2 (not necessairly regular). I want to prove that there is a way to orient the edges of G such that each node of G has at least one out-going edge.
As a ...
- 149
1
vote
1
answer
80
views
Trivial vertex cover in regular graph is 2-approximation Proof
I need to show that in any regular graph, taking all nodes gives a 2-approximation vertex cover.
My attempt: I am proving that every $k$-regular graph can be reduced to a 2-regular fully connected ...
- 149
1
vote
0
answers
29
views
How do I get the number of cycles in a grid. Is there a formula?
So does anyone know the formula in order to get the number of cycles, I'm not directly asking for the answer but at least someone guides me on how to get a cycle given a grid such as an image above.
- 11
0
votes
1
answer
46
views
Prove there is a matching of size n/2 on a graph with 2n vertices each of degree n
Given underirected $n$-regular graph with $2n$ nodes, I am asked to show it has a matching of size $n/2$.
My attempt:
At each step I will also remove the edge from the graph that I am adding to the ...
- 149
-3
votes
1
answer
71
views
Recursion problem T(n)=3T(n/3)+3n
I just need help solving this problem. I know I'm supposed to be using the Master's Theorem but I don't know where to start
1
vote
0
answers
50
views
Find sets which are subsets of the given search set?
The problem is the following:
You are given a collection( set, list, whatever ) C of sets, and you are given a search set S.
We want to find among all sets in C the ones which are subsets of S.
Hence, ...
- 121
0
votes
2
answers
72
views
Is there a quantifier more powerful than the other to determine FOL connector?
So basically we have 2 types of quantifier in first order logic, they are universal quantifier and existential quantifier. Usually we use implies connector(->) when we have universal quantifier in ...
1
vote
3
answers
104
views
Solve the recurrence $T\left(n\right)\:=\:3T\left(n-1\right)\:+\:3n^2$
I am trying to solve the recurrence
$T\left(n\right)\:=\:3T\left(n-1\right)\:+\:3n^2$
I tried method I saw but I do not fully understand which looks like:
$T\left(n-1\right)\:=\:3T\left(n-2\right)\:+\:...
- 29
3
votes
1
answer
115
views
Analytic combinatorics and less-precise running times
Analytic combinatorics and concrete mathematics are the mathematics of asymptotic counting, and they draw from combinatorics, analysis, and probability. These techniques have been applied to the ...
- 287
4
votes
1
answer
59
views
Copying a linked list with additional arrows from each node
Statement
Consider the following modified node structure for the linked list:
struct Node {
int value;
Node* next;
Node* random;
}
The ...
- 228
2
votes
1
answer
1k
views
Can we solve a "very" exponential recurrence?
Can we solve this recurrence relation : $T_n = \exp(T_{n-1})$ ?
Thanks!
- 29
1
vote
3
answers
146
views
Θ, O and Ω, and how they relate to each other as subsets
I am trying to understand how $\Theta(n)$, $O(n)$, and $\Omega(n)$ relate to each other as sets and want to make sure I'm on the right track.
I get that $Θ(n) \subseteq O(n)$ since $Θ(n)$ is stronger ...
- 11
1
vote
1
answer
124
views
bellman ford and one surprizing fact
I ran into a very surprising local contest problem.
after finishing bellman ford algorithm, if we continue to updating
distance and distance of one vertex v being updated, then v is
on negative cycle....
0
votes
0
answers
33
views
How to generate supersets from a finite number of subsets efficiently
Let $F$ be a set, for instance $\{a,b,c,d,e \}$. Suppose I have a set of subsets of cardinality two obtained from $F$:
$ ${ a,b },$\{b,c\},${a,d}
I want to create every possible set of cardinality ...
- 111
0
votes
1
answer
43
views
How to evaluate all the binary sequences, generated from $2^{100}$ for finding all the sequeces which contain minimum $10$ zeros?
Suppose I have a set of $2^{n}$ number of binary sequences. And I have to select only those sequences which contain a minimum ${P}$ number of $0$ in it. For example, please consider the below one
Eg.
...
- 168
5
votes
0
answers
129
views
Optimization on hypergraph "refinements"
Given a hypergraph $H = (V, E)$, call $H' = (V, E')$ a refinement of $H$ iff there exists a partition $p : E' \to I$ (where $I$ is an arbitrary index set) such that $E = \{\bigcup_{x \in p^{-1}(i)} x \...
- 364
2
votes
1
answer
163
views
Asymptotic height of d-ary heap
I know that the height of a $d$-ary heap on $n$ nodes is $\lceil (\log_d (n(d-1) + 1) - 1)\rceil$, but I was wondering how to justify that that's $\Theta(\log_d n)$?
I know the definition of $\Theta, ...
- 279
1
vote
1
answer
24
views
Is $\{\emptyset,a,\epsilon\}$ an algebraic structure with respect to $+$?
Let $R = \{\emptyset,a,\epsilon\}$ (the elements here are regular expressions) and let $+$ be the or operation, which can be applied over the regular expressions of $R$. Is $(R,+)$ some kind of an ...
- 13
1
vote
0
answers
25
views
Finding square root of a gram matrix over the integers [closed]
Suppose that matrix A is a symmetric positive definite matrix over the integers, i.e., $A \in Z^{n\times n}$, if B is a matrix over the real numbers, it is not difficult to find B such that $A = B \...
- 11
8
votes
11
answers
4k
views
Real life examples of *zero* weight edges in graphs
The meaning of edges with zero weight in a weighted graph questions me for a long time, and I even asked a related question previously.
Yet, when I recently read here a question on real life example ...
- 613