Questions tagged [discrete-mathematics]
Questions about discrete mathematics, the study of mathematical structures that are fundamentally discrete rather than continuous.
473
questions
-1
votes
0
answers
18
views
Modal logic S4 system
How to prove in S4 system modal logic that ◇□◇x->◇x? Probably i only need to show that ◇□x->x
Any help will be great?
- 1
1
vote
0
answers
43
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
19
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
91
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
16
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
40
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
50
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
28
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
41
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,871
1
vote
0
answers
22
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,871
1
vote
1
answer
38
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,871
0
votes
1
answer
33
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 ...
- 319
0
votes
0
answers
19
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
50
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
29
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
24
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
27
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
31
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
40
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
40
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
28
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
64
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
95
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
103
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 ...
- 315
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 ...
- 206
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
126
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
103
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
31
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
41
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
127
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
94
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, ...
- 225
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
23
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 ...
- 603
18
votes
6
answers
3k
views
Real life examples of negative weight edges in graphs
I am unable to relate to any real life examples of negative weight edges in graphs. Distances between cities cannot be negative. Time taken to travel from one point to another cannot be negative. ...
- 319
5
votes
0
answers
118
views
discrete optimization problem with a matrix inverse
I'm trying to solve this discrete optimization problem:$\newcommand{\I}{\mathcal{I}}\newcommand{\R}{\mathbb{R}}$
$$\max_{|\I| \le k} f(\I) \qquad\text{where}\; f(\I) :=x_{\I}^{\top} (\Sigma_{\I})^{-1} ...
- 51
0
votes
1
answer
59
views
How can it be proved that two different kinds of dfs unequivocally define a unique tree?
How can it be proved that two different kinds of dfs ( for example let call them inorder and postorder) unequivocally define a ...
- 17
0
votes
0
answers
35
views
Why is “For all the simple things you have done to me, there exists one thing that makes me happy” FALSE? Use nested quantifiers to prove your point
I've done my due dilligence and tried to answer this question using every resource I could get. KhanAcademy, NesoAcademy, and Rosen's Discrete Mathematics book. I still can't wrap my head around it. ...
- 1
0
votes
0
answers
48
views
Finding the shortest path with this algorithm
This is a homework question. We want to find the shortest $s$-$t$ path in an undirected weighted graph $G = (V, E)$ with capacities $c_e$ for each edge and positive weights. Let $S'$ be the set of all ...
- 115
0
votes
1
answer
20
views
Polytime Mapping Reduction from Language A to Language A (identity)
How would I create a polytime mapping reduction to prove A ≤p A for any language A.
I was thinking to assume A is in P to start.
For every 𝑥: 𝑥∈𝐴 iff 𝑓(𝑥)∈𝐴.
But I am not sure what to do from ...
1
vote
0
answers
32
views
Linear programming and network flow
I would like some hint in this homework question. I have to write the max-flow problem (with souce $s$ and sink $t$) as a linear program. I have to do this by defining variables on each $s - t$ path, ...
- 81
1
vote
0
answers
38
views
Finding a path that passes through a given vertex
This is a homework question. Let $G = (V, E)$ be an undirected graph. Let $u, v, w \in V$, find a path from $u$ to $w$ that passes through $v$. I know that I can solve this by running BFS on $u$ and ...
- 31
1
vote
1
answer
112
views
How to get the highest score in this game?
I would like some advice in this homework question. There is a three players game, in which each player ($A, B$, and $C$) is given a $n$-length array of integer values. There are $n$ rounds in this ...
- 115
0
votes
0
answers
10
views
Discrete Event Simulation: modeling entity arrivals
I have seen the stochastic introduction of simulated "entities" (typically queuing for service) via stochastic inter-arrival times. Specifically, the times between arrivals are simulated ...
- 101
0
votes
0
answers
77
views
Longest sequence of 1s in a binary matrix
I would like a hint for this homework question. The problem is to come up with a divide and conquer solution for finding the maximum sequence of 1s in a given a binary matrix of order $n$. The ...
- 31
1
vote
1
answer
42
views
Assigning balls to bins with constraints
Let $S= \{ b_{11}, b_{12}, b_{21}, b_{22}, b_{31}, b_{32},\dots, b_{n1}, b_{n2} \}$ be a set of $2n$ balls grouped in $n$ pairs, and $T = \{ B_1, B_2, \dots, B_m\}$ be a set of $m$ bins with ...
- 115
2
votes
0
answers
63
views
Variation of the gas station problem
Consider an acylicic directed weighted graph in which the nodes represent cities and the weights represent the amount of fuel a car spends when going through that edge. At each city $u$ the car ...
- 31
0
votes
0
answers
39
views
Finding sequences in a binary matrix with recursion
Given a binary square matrix of order $n$. Can the problem of finding the longest sequence of 1's (horizontal or vertical) be solved with recursion?
I know how to solve the problem without recursion ...
- 115