# Questions tagged [discrete-mathematics]

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

441 questions
Filter by
Sorted by
Tagged with
97 views

18 views

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 &... 1answer 82 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 ... 1answer 40 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 ... 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 ... 1answer 61 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 ... 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. ... 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: ... 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 ... 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} $$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 ... 3answers 106 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 (...
53 views

$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)$$?
28 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$, ...
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 ...
68 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 ...
47 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 ...
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.
55 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?
### 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: \$\...