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
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

Upper bound of $nc^n$

Is it true that $nc^n \leq (c+1)^n$, where $c$ is a constant? If so, how?
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 ...

1
2 3 4 5
9