# Questions tagged [discrete-mathematics]

Questions about discrete mathematics, the study of mathematical structures that are fundamentally discrete rather than continuous.

432 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
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 ...
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 ...
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 ...
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 \\ ...
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 ...
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 ...
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 ...
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.
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 ...
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?
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.
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?
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.
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 ...
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?
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 ...
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 ...
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 ...
26 views

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 ...
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 ...
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 ...
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 ...
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. ...
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: ...
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 ...
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}$$
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 ...
105 views

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