Questions tagged [discrete-mathematics]
Questions about discrete mathematics, the study of mathematical structures that are fundamentally discrete rather than continuous.
407
questions
1
vote
1answer
47 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 ...
-2
votes
1answer
45 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
16 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 ...
0
votes
3answers
102 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
48 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
25 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
58 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
29 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
41 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
16 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 ...
1
vote
2answers
103 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
33 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
70 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
100 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
39 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
41 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
39 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
45 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
63 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
vote
1answer
34 views
Find The “Best” Permutation of Inputs to Maximize Sum of Functions (or approximate “best”)
The Problem (in words)
I want to sort $N$ items where the value of item $i$ at position $p$ is given by the function $f_i(p)$. The "best" order for these items is the one that maximizes the ...
2
votes
1answer
107 views
Number of nodes at given depth in binary tree
Show that there is no comparison sort whose running time is linear for at least half of the $n!$ inputs of length $n$. What about a fraction of $1/n$ of the inputs of length $n$? What about a fraction ...
1
vote
1answer
71 views
Proving that the recurrence $T(n) = 2T\left(\frac{n}{2}\right) + 1$ with $T(2) = 1$ is asymptotically $O(n)$
I've already solved the recurrence exactly and found that $T(n) = n - 1$. Therefore, I know that $T(n) = O(n)$.
However, I'm having trouble showing that $T(n) = O(n)$ without solving the recurrence ...
0
votes
1answer
38 views
What is the exponent of 0.00000072
And how do I solve this?
I know this is a decimal and we have to convert it to an exponent. I want to know how I would solve this and the steps as well so I will be able to solve questions similar to ...
0
votes
0answers
41 views
Show that this language is undecidable
Given the language $K$ $=\{<M> $ where $M$ is a turing machine ( that is on the alphabet {0,1}) and $L(M)$ contains at least one word of form $0^k1^l$ with $k,l\geq 0\}$
I would like to know if ...
1
vote
1answer
70 views
How to show ambiguous context-free grammars in Chomsky normal form is Turing recognizable?
So this question has two questions and i have to use the answer from 1 to answer question 2. Assuming that my answer for 1 is good. I need help with 2. ( Correct me if wrong please.)
Question 1 :
Show ...
0
votes
1answer
47 views
any one can prove following inequality?
are for every $\alpha \in N $ , $ \frac{1}{\alpha-2} \geq \frac{1}{\alpha}+\frac{1}{\alpha-1}$?
1
vote
1answer
43 views
Height of AVL tree with balance condition of 2
The maximum height of an AVL tree with a balance condition of 1 is 1.44log(n). So the worst case height is O(logn). However, if the balance condition was hypothetically 2 (meaning that the allowed ...
0
votes
0answers
25 views
Question about graphs and Eulerian path
An almost complete graph of n vertices is obtained from the removal of two edges of the complete graph
of n vertices. For which values of n are there almost complete graphs that admit Eulerian paths?
...
0
votes
1answer
75 views
How can I prove the correctness of this exponentiation algorithm using induction?
I have the following algorithm. How could I prove it using induction that for every $n\ge 0$, Exp(n)${}= 2 ^ n$?
...
4
votes
2answers
140 views
Min path cover for a three-layer graph with all paths traversing all layers
Best to start with an example. I want to design fictional fruits. The fruits have three attributes: color, taste and smell. There are $c$ possible colors, $t$ possible tastes and $s$ possible smells. ...
2
votes
0answers
36 views
Line graphs of Powers of Cycles are powers of cycles
Are line graphs of powers of cycles again a power of cycle? I think yes, this is because the line graphs of cycles are cycles of the same order, and moreover, since powers of cycles consist of edge ...
-1
votes
3answers
44 views
Which topics of mathematics should I need to learn to be a good app developer?
I'm 29 years old. I couldn't continue my studies after grade 10 due to some financial issues and I didn't have time to practice mathematics. It's been more than 11 years since I left studies. Now I ...
0
votes
0answers
28 views
Algorithm for specific load balancing/arbitration problem
I'm trying to design an algorithm for some specific arbitration requirements and I have a feeling I'm on well-trodden ground, but lack the maths background to properly analyse it. If someone could ...
3
votes
1answer
880 views
Arrange in increasing order of asymptotic complexity
I have the following functions that I need to rank in increasing order of Big-O complexity:
$$(\log n)^3, 10\sqrt n, n\log n, n\sqrt n, n^4 + n^3, (2.1)^n \cdot n^2, 3^n, 2^n \cdot n^3, n! + n, n^n. $$...
2
votes
3answers
58 views
How to use DFA/NFA to prove the language {$0^n 𝑥1^𝑛$ | x ∈ Σ*, n ≥ 1} is regular?
I'm trying to prove the language L = {$0^n 𝑥1^𝑛$ | x ∈ Σ*, n ≥ 1} is regular, but don't know how to present it in a DFA/NFA.
I'm thinking to have n+1 states in a NFA, with the start state as the ...
0
votes
0answers
15 views
How do you prove that this tree path calculation function works, from first principles mathematically?
I recently got an amazing answer to an SO question about how to calculate the path in a tree to an item, where you give it the corresponding array index, and the ...
0
votes
1answer
37 views
Mathematical expression for the quantity that we are maximising in the stock buying and selling problem
Problem Statement:
Say you have an array prices for which the $i^{th}$ element is the price of a given stock on day $i$.
Design an algorithm to find the maximum profit. You may complete as many ...
-1
votes
1answer
56 views
2
votes
1answer
472 views
Asymptotic analysis of $T(n) = T(n/5) + T(4n/5) + \Theta(n)$
If I have a recurrence relationship like this:
$$T(n) = T(n/5) + T(4n/5) + \Theta(n),$$
how would I analyze its rate of growth?
I believe I can't use the master theorem. I tried to draw a tree but ...
1
vote
1answer
14 views
Populating a vector of numbers to expose an error in a function implementation
So lets say I'm writing an algorithm that takes a vector as input. I want to know that I'm writing this algorithm correctly however so I of course write tests to see if the output equals what I expect ...
0
votes
0answers
43 views
Proof using tableau algorithm
I have spent an hour finding the answer to this problem but can't do it, this is the problem:
Determining whether the following semantic entailment holds or not by using the tableau algorithm
...
0
votes
1answer
26 views
Represent a DNF formula as a multivariate linear formula?
Lets say I have the following DNF: (x or y) and (z or i) / $(x\lor y)\land(z\lor i)$
How do I convert that into a polynomial form?
3
votes
0answers
57 views
Data structure to determine vertex membership after edge removal from a tree in sub-linear time?
Consider a tree $T = (V,E)$ and its induced disjoint trees $T_1 = (V_1, E_1), T_2=(V_2, E_2)$ by the removal of an edge $e \in E$.
Is there a data structure that enables the immediate determination of ...
2
votes
0answers
23 views
How to linearly combine loss functions to preserve optimal substructure property?
I've been working on a binary tree optimization problem with two choices of loss function (let's call them A and B). I'm fairly certain that the problem of minimizing either A or B individually has ...
3
votes
1answer
61 views
An efficient way of calculating 𝜙(𝜙(p*q)) where p and q are prime
Let $p$ and $q$ be prime numbers and $\phi$ Euler's totient function. Is there an efficient way of computing $\phi(\phi(p\cdot q)) = \phi((p-1)(q-1))$, that is not simply based on factoring $p-1$ and $...
0
votes
1answer
45 views
For an NFA, can we always find a RAM?
For an NFA, can we always find a RAM, which recognises the same language?
2
votes
1answer
16 views
Maximum Chromatic number of Cayley Graphs with large degree
It is known that there does not exist a regular graph of order $n$ with clique size greater than $\lceil\frac{n}{2}\rceil$. My question pertains to Cayley graphs with large degree, say $\ge \frac{n}{2}...
