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
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 ...
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, ...
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 ...
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)=\...
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,......
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+...
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 ...
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))$
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 , .... , ⌈ ...
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 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)\:+\:...
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 ...
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 ...
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, ...
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 ...
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 \...
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 ...

1
2 3 4 5
10