Questions tagged [discrete-mathematics]
Questions about discrete mathematics, the study of mathematical structures that are fundamentally discrete rather than continuous.
450
questions
1
vote
1answer
77 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
0answers
26 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 ...
0
votes
1answer
37 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.
...
3
votes
0answers
28 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 \...
1
vote
1answer
20 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
votes
0answers
24 views
Books for a first year college student in computer science [closed]
Books that involve maths, computer science, logic, programming or anything that would be helpful for a student like me
1
vote
1answer
20 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
0answers
19 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 \...
7
votes
11answers
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 ...
18
votes
6answers
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. ...
5
votes
0answers
111 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} ...
0
votes
1answer
56 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 ...
0
votes
0answers
30 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. ...
0
votes
0answers
44 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 ...
0
votes
1answer
17 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
0answers
28 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, ...
1
vote
0answers
34 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 ...
1
vote
1answer
81 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 ...
0
votes
0answers
6 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 ...
0
votes
0answers
57 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 ...
1
vote
1answer
34 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 ...
2
votes
0answers
46 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 ...
0
votes
0answers
31 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 ...
1
vote
1answer
54 views
Removing and adding edges from spanning tree
Let $T_1$ and $T_2$ be two spanning trees. If $a$ is an edge in $T_1$ that is not in $T_2$, and $b$ is an edge in $T_2$ that is no in $T_1$. I want to prove that $T_1 - \{ a\} + \{ b\}$ is a spanning ...
3
votes
1answer
47 views
Recurrence $T(n) = T(n-1) + (-1)^nn$, $T(0) = 1$
I am trying to solve the recurrence $$T(n) = T(n-1) + (-1)^nn, \quad T(0) = 1.$$
I'm stuck in the summation:
\begin{align}
T(n) &= T(n-1) + (-1)^n n \\ &=
T(n-2) + (-1)^{n-1}(n-1) + (-1)^nn \\ ...
0
votes
1answer
108 views
Shortest walk with alternating colors in a directed graph
Let $G$ be a directed graph such that every edge is colored (red, yellow or green). I want to compute the shortest walk (possibly with repeated vertices) with the restriction that the colors are ...
1
vote
1answer
38 views
Squaring the weights of an undirected graph and minimum spanning trees
This is from question 3(a) from http://www.cs.cmu.edu/afs/cs/academic/class/15210-s14/www/exams/exam2-practice-sol.pdf, which is: consider an undirected graph $G$ with unique positive weights. Suppose ...
3
votes
3answers
239 views
Solve $T (n) = T (\frac n2) + n(2 - \cos n)$
For the following recurrence relation:
$$T (n) = T (n/2) + n(2 - \cos n)$$
I see it based on values of $\cos$ function given that it output values in range, but this does not seem to have anything to ...
2
votes
1answer
288 views
What is the difference between Euler and Eulerian graph?
A Graph is Eulerian iff $\exists$ an Eulerian Cycle or all the vertices of Graph have even degree.
What is an Euler graph?
Wiki has a definition for the Eulerian graph but not for the Euler graph.
0
votes
1answer
97 views
What is the meaning of the pipe symbol here?
I am reading Distributed Algorithms by Nancy Lynch. In chapter 16, I came across the pipe symbol. Does this mean the same as "or" in some programming languages or could someone explain that ...
-1
votes
1answer
49 views
What does x sign mean in functions
I came across this cross sign when reading a book. Does anyone know what does this mean in the context of a function?
0
votes
1answer
51 views
What is the difference between problem solving and theorem proving?Is mathematics problem solving or theorem proving?
Some books of permutation and combinations ,theorems are to proved while in some book problem is to be solved using logic.
-1
votes
1answer
38 views
0
votes
1answer
21 views
A proof that if f is the heaviest edge in weight from all the other edges in the circle which it is a part of, then f will not participate in any MST
I cant proof that if f is the heaviest edge in weight from all the other edges in the circle which it is a part of, then f will not participate in any Minimum Spanning Tree. please help.
0
votes
1answer
25 views
Mapping reduction properties exercise
I am having trouble understanding how to conclude if the statements are true or false, I would really appreciate your help.
We know about three languages, A, B and C.
There exists a mapping reduction ...
0
votes
1answer
443 views
What is the meaning of this symbol that looks like an inverted uppercase A?
I found this symbol in a book I'm reading. Does anyone know what this symbol means? Does it mean for all js?
1
vote
1answer
120 views
Invariant vs Assertion vs lemma
I am reading Distributed Algorithms by Nancy Lynch. I have come across lemmas, assertions and invariants, but I do not understand the difference between them. I think lemma means an intermediate ...
3
votes
1answer
198 views
Disconnected bipartite graph
I was searching whether a bipartite graph can have a vertex with 0 degree. I found this, but the answer there says it is possible. Wouldn't that make a graph tripartite?
Also, if a vertex with zero ...
1
vote
0answers
23 views
Maximum number of edges with k components
Given $N$ vertices and $K$ components what is the maximum number of edges that may exists ? I just got gut instinct that it will be maximum if we take one set with $k-1$ vertices and this will have no ...
1
vote
0answers
26 views
Selecting sets that maximise the cardinality of the union minus the cardinality of the difference
I have a sparse $60000\times10000$ matrix where each element is either a $1$ or $0$ as follows.
$$M=\begin{bmatrix}1 & 0 & 1 & \cdots & 1 \\1 & 1 & 0 & \cdots & 1 \\0 &...
0
votes
0answers
18 views
Selecting five binary vectors that when multiplied elementwise are most similar to another vector
I have a sparse $60000\times10000$ matrix where each element is either a $1$ or $0$ as follows.
$$M=\begin{bmatrix}1 & 0 & 1 & \cdots & 1 \\1 & 1 & 0 & \cdots & 1 \\0 &...
1
vote
1answer
111 views
How do you prove that a solution to the 0-1 knapsack problem is optimal?
Given a boolean vector b representing a solution to the knapsack problem with n elements k capacity and where each element has integer weight and value.
Proving that the solution is a solution is ...
0
votes
1answer
41 views
What is the formal mathematical model of a register machine?
I have been searching the web for a mathematical model of a register machine and have fallen short. The closest I have found is found here:
But I am looking for more detail than what is provided ...
0
votes
0answers
24 views
How does the railway model of computation get translated to motion on the heptagrid tiling of the hyperbolic plane?
I have been reading these, along with slowly chipping away at the two books Margenstern has produced:
A universal cellular automaton in the hyperbolic plane
A Universal Cellular Automaton on the ...
2
votes
1answer
63 views
Iteration Vs Induction Method
I am working on different methods to solve Recurrence Relations. I am using Iteration method and substitution method, which involves Induction, but I feel that sometimes Induction method creates a bit ...
1
vote
1answer
40 views
Marks that are impossible to obtain?
There is an exam and the marking pattern is -
0 marks - Unattempted
4 marks - Correct Answer
-1 marks - Incorrect Answer
And total number of question is 30. ...
0
votes
2answers
91 views
Is this a general compression algorithm?
I'm aware that an algorithm that compresses every input doesn't exist (by the pigeonhole principle), however I tend to think about the problem sometimes and I came up with a (flawed, but why?) idea:
...
1
vote
1answer
50 views
a lower bound for the maximum fraction of matchings not containing an edge
I am trying to prove the following statement (from book, page 317):
Let $G(A,B,E)$ be a bipartite graph, where $A$ and $B$ are the two disjoint sets of vertices s.t. $|A|=|B|=n$. Let the number of ...
-1
votes
1answer
50 views
Solve the following recurrence
I'm trying to solve this the recurrence :
$$
T(n)=\begin{cases}
1, & \text{ if } n = 1 \\
T(n-1) +n(n-1), & \text{ if } n \geq 2
\end{cases}
$$
1
vote
0answers
18 views
In a DAG, what is the name of the process replacing no branch path with a single vertex
In my work, I meet a process for DAG, and need to explain it in my report. So, I would like to know the name of the process.
The process is very simple. The vertices of degree two except roots and ...
