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

1
2 3 4 5
9