Questions tagged [discrete-mathematics]
Questions about discrete mathematics, the study of mathematical structures that are fundamentally discrete rather than continuous.
432
questions
0
votes
0answers
43 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
21 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
31 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
27 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 ...
0
votes
0answers
26 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
46 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
54 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
18 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
106 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
261 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
93 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
47 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
35 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
19 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
439 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
105 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
184 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
22 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
17 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
43 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
37 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
22 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
51 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
38 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
89 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 ...
1
vote
3answers
105 views
Primes not dividing sequence $a_{n+1} = 1 + a_0 a_1 \cdots a_n$
Prove that there are infinitely many primes that divide none of the elements of the integer sequence
$a_{n+1} =1+a_0 a_1 \cdots a_n$, with a starting point of $a_0 \geq 0$.
I thought about $$\log (...
1
vote
1answer
52 views
Question about generating functions
$A(x)$ is generating function of $\{a_n\}_{n=0}^{\infty}$ and $B(x)$ is generating function of $\{b_n\}_{n=0}^{\infty}$, what is
$$A(x^2)+xB(x^2)$$?
0
votes
1answer
27 views
Search for specific element in sorted array
Given sorted array $A[1..n]$. We want to find an element such that
$A[i]=3i+2$ in $O(\log n)$(binary search).
I trying to relate to problem finding element in sorted array $A$ such that $A[i]=i$, ...
0
votes
0answers
38 views
A problem in proving with induction
According to
asked question in this post.
Suppose $T(n,k)=T(n-1,k-1)+T(n-1,k)+1$, now let $C(n,k)=T(n,k)+1$.
As a result $C(n,k)=C(n-1,k-1)+C(n-1,k)$.
I want to prove
$C(n,k)=2\binom{n}{k}$, now on ...
1
vote
1answer
67 views
Greedy algorithm for maintaining drugs
Given $n$ drugs such that each drug $d_i$ should maintain in interval
$[c_i,h_i]$.We want to minimize number of containers to maintain
medicines in compatible interval.
My answer is as follows:
I use ...
0
votes
1answer
44 views
If possible, use binary search to find an element in sorted array
Given sorted array $A[1..n]$, we want to find an element such that,
$A[i]=i^2$,Can we use binary search to find such a element?
My Attempt:
initially, I read this link, but I can't understand the ...
0
votes
0answers
19 views
Computer Science [duplicate]
I am trying to solve the following problem to find big-theta. I am having a lot of trouble, if anyone can help!
T(n)=8T(√n)+log^2(e^n)?
The logarithm is base 2 and is squared.
-2
votes
2answers
52 views
Solve T(1) = 1 T(n) = T(n-1) + n^2 for n ≥ 2
I am not able to solve the following recurrence relation:
$$
T(n) = \begin{cases}
T(n-1) + n^2 & \text{if } n \ge 2,
\\
1 & \text{otherwise.}\\
\end{cases}
$$
How do I start?
0
votes
1answer
30 views
Lower bound on $c_n = 4c_{\lfloor n/2 \rfloor} + n$
Define a sequence $c_1,c_2,\dots$ by the equations
$$ c_1=0, \quad c_n = 4c_{\lfloor n/2 \rfloor} + n \text{ for all } n > 1. $$
Prove that $\frac{(n+1)^2}{8} < c_n$ for all $n \geq 2$.
Hint: $\...
0
votes
0answers
18 views
Why can't I evaluate this L-Attributed SDD with a pre-order traversal?
My powerpoints for a compiler class says "an L-Attributed SDD can be evaluated with a pre-order (root, left, right) traversal", and to be L-Attributed the nodes need to have either ...
2
votes
2answers
160 views
Is discrete math enough for computer science ? Or there other Math topics that I should also learn With it?
I want to learn computer science, SO is discrete math enough for computer science ? Or there other Math topics that I should also learn With it ?
I don’t have specific topic that I care more about ...
2
votes
1answer
35 views
Expressing a constraint of the form $\max(x_1,x_2) \ge q$ in a linear program
I am trying to solve an LP in which one of the constraints is mentioned below,
$$\max(x_1,x_2) \ge q,$$
where $x_1 \ge 0$ and $x_2 \ge 0$.
Is it possible to do in linear programming?
1
vote
2answers
79 views
What mathematical guarantees gives alpha-beta pruning?
In the alpha-beta pruning version of the minimax algorithm, when one evaluates a state p with $\alpha$ and $\beta$ cutoff and gets a ...
0
votes
3answers
217 views
Computing square vs computing square-root? Time complexity
I am working on something that requires checking a very large natural number $x$ to determine if it is the square root of an even larger natural number $y$. So I am wondering what are the fastest ...
1
vote
2answers
41 views
How can I show mathematically the time complexity of this function is O(N)?
int foo(N){
if(N <= 1){
return 0
}else{
return 1 + foo(N-1)
}
}
I can tell that the time complexity of this program is O(N) but I am ...
0
votes
0answers
49 views
A necessary condition for a relation to be in 2NF but not in 3NF is that some non-prime attribute must be determined by a non-prime attribute
I will state the complete question now, since it did not fit in the title.
Is the statement given below correct?
A necessary condition for a relation to be in 2NF but not in 3NF is that some non-...
1
vote
2answers
43 views
Compute average case with best case
is it correct to compute the average case time complexity of an algorithm by taking the mean of the best and worst cases ? My findings : for binary search, $\frac{\log (n) +1}{2}\in \Theta \left(\log (...
1
vote
1answer
52 views
Given an undirected graph, find an orientation such that every vertex has out-degree at least 3
Given an undirected graph $G=(V,E)$, describe an algorithm that computes an orientation of $E$ such that each vertex has out-degree at least 3.
I know how to check if a vertex $v$ has at least $k$ ...
1
vote
1answer
71 views
facts on tree and MST
We are given an Undirected, Weighted and Connected Graph $G$, (non-negative weights, all distinct) with one property that shortest path between any two vertexes on this graph is on MST.
The following ...
