Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [discrete-mathematics]

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

0
votes
0answers
21 views

Solving a modular equation programmatically

Consider that I've a mathematical equation of the form: $$ (6+4\times x)\text{ } mod\text{ } 22 = 0 $$ How can I solve this modular equation by using a program, efficiently? By trial and error, one ...
1
vote
1answer
19 views

How to calculate the number of invalid strings given a constraint system on alphabet, word blacklist, and string length

If I have the following system, I am wondering how to calculate the number of valid strings it contains. The system is something like this, which can have arbitrary variations. Only consists of an ...
1
vote
1answer
37 views

Randomized Algorithm in $O(d)$ for Solving Unknown Degree $d$ Polynomial Function Using an Erroneous Oracle

Consider the field $GF(p)$, where $p$ is a prime number. If there is a function $f: GF_p \times GF_p \rightarrow GF_p$ which has an unknown degree $d$ polynomial, with $1 < d < p / 4$. Although ...
4
votes
1answer
62 views

Prove the probability of which a hash function is collision-free

Suppose $H = \{h_1, ..., h_T\}$ be a family of pairwise independent hash functions mapping $\{0, 1\}^n$ to $\{0, 1\}^{n/2}$. Let $M = \frac{2^{n/4}}{10}$ and let $x_1, ..., x_M$ be any M distinct ...
1
vote
1answer
38 views

Solve the recurrence $a_n - 3a_{n-1} + 2a_{n-2} = 6 \cdot 2^n$

Consider the recurrence $$ a_n - 3a_{n-1} + 2a_{n-2} = 6 \cdot 2^n. $$ I tried to solve this as follows. First, I found the homogeneous solution: $$ a_n^{(h)} = r^2 - 3r + 2r \\ (r-2)(r-1) = 0 \\ ...
0
votes
1answer
26 views

Recursive definition for the length of a string?

I found a couple of answers online but I don't quite understand why the answer is right: The length of a string is: If a string has no characters, then its length is 0. Otherwise, the length of the ...
0
votes
0answers
15 views

Can we apply master theorem on this? [duplicate]

I'm very confused. It's my first time here . Idk how to ask question here . Sorry if I made some mistake or anything . T(n) = 2T(n/2)+ n/logn
1
vote
0answers
45 views

The maximum number of uniquely intersected elements from the all possible intersection scenarios among the sets in a two-column matrix

Let us define a $n \times 2$ matrix M consisting of integer sets, such that the first column consists of the so-called intersecting sets, and the second column ...
0
votes
0answers
12 views

How to understand DFA's and how to understand how to construct them based on a given regular language? [duplicate]

I have practiced DFA's for an upcoming test and I haven't been able to grasp how to construct more difficult DFA's. An example would be this question : Construct a deterministic finite state automata ...
4
votes
1answer
264 views

Irregularity of language of prefixes of decimal expansion of pi

Let $L_{\pi}$ be the language consisting of prefixes of the decimal expansion of $\pi$: $$L_\pi = \{3, 31, 314, 3141, 31415, 314159, \ldots\}.$$ Prove that Lπ is not DFA-recognizable. You may use the ...
1
vote
1answer
23 views

I don't understand what this regular language is asking for? Find a grammar for L(G) = {w || w | is odd,∑ = (0, 1) }

I don't understand what this regular language is asking for? Find a grammar for L(G) = {w || w | is odd,∑ = (0, 1) }. What does the " || " mean I know a single " | " means or.
-1
votes
1answer
38 views

Regular expression for all possible strings. Does the Kleene star distribute over each element. (0+1)* = 0* + 1*?

Regular expression for all possible strings. Does the Kleene star distribute over each element. Is this true? (0+1)* = (0* + 1*) ?
1
vote
0answers
55 views

Inductive proof on Quicksort with Explicit Stacking

Prove by induction that if Quicksort with Explicit Stacking is modified so that the end-points of the larger sublist are stacked, and the other sublist is sorted first, then the maximum stack size is $...
5
votes
2answers
82 views

Finding the cheapest buy order with fixed inflation for each product

Let's say we have a set of products $M$, a total of $|M|=n$ that we want to buy. However, we can only buy one product at a time, so that we need a total of $n$ time-units to buy all items. Each ...
5
votes
1answer
127 views

How does treewidth behave under graph minor operations?

It is a well-known fact that for any minor H of a graph G (commonly written as $H \leq_m G$), the treewidth of H is smaller than or equal to that of G. Minors of a graph are created through the ...
0
votes
1answer
210 views

Find the Pumping Length for Language L of (2+3k) a's or (10+12k) b's

The following question on the theory of computation is GATE 2019 CS question 24: For $Σ = \{a, b\}$, let us consider the regular language: $$L = \{x \mid x = a^{2+3k} \text{ or } x = b^{10+12k}, k ...
2
votes
2answers
190 views

Finding the maximum of a bitonic sequence

Given to us is an array $B[1],\ldots,B[n]$ as input, which satisfies the following property: there exists a special index $i^* ∈ \{1, \dots , n\}$ such that $$B[1] < B[2] < \dots < B[i^*− 1] &...
2
votes
1answer
25 views

Is it possible to denote “any single alphabet symbol” in an FSA state diagram?

This is a possible duplicate of the following (but not sure it answered my question): Is it possible to support .(any symbol) or \d, \w, \W in DFA My professor is asking for a finite automata state ...
-1
votes
1answer
34 views

Can someone point out why these directed graphs aren't equivalence relations?

As far as I can tell, these two directed graphs are reflexive, symmetric and transitive.
3
votes
0answers
78 views

Polynomial time algorithms for rank 1 elliptic curves over Q

As an outsider, it sounds like a lot of progress has been made on understanding rank 1 elliptic curves. Much of the BSD conjecture is known for rank 1, and Heegner points provide a way to calculate a ...
-4
votes
1answer
57 views

Is ∅ ∈ {{∅}} true? [closed]

I learned that the empty set is not an element of every set unless the empty set is explicitly included in the set like {∅}, so I believe it is false because it is not ∅ ∈ {∅}.
3
votes
1answer
59 views

Matrix Representation for logical gates?

I have been trying to find if there are other matrix type representations logical circuits, in the example below, $$\begin{bmatrix} 1 & 0\\ 1 & 1\\ \end{bmatrix} \equiv \, \, \Rightarrow$$ ...
0
votes
1answer
43 views

How to “logically” solve boolean logic

I came across of one excellent book Elements of Computing Systems and in chapter 1 we need to implement the "primitive" logic gates (for example: Not, And, Or, Xor, Mux, etc) based on a Nand gate. ...
0
votes
0answers
9 views

Most probable inputs assignment in Gaussian process

Given A Guassian process $w(\mu^*,\Sigma^*)$ $n$ observations of the output And $n$ potential inputs. But the assignment of the inputs to the observations is unknown. The goal is to find a inputs-...
0
votes
0answers
15 views

Possible Network Flow “Cuts”?

The possibilities are: always full and always crossing. (True, per chart) always full and sometimes crossing. (True, per chart) always full and never crossing. (False?) sometimes full and always ...
1
vote
0answers
18 views

Relation between deficiency and color class parity of graphs

Let $G$ be a graph with total vertices $|V(G)|$. Let the maximum degree of the graph be $\Delta$. Let us assume the graph is total colourable( no adjacent vertices, adjacent edges and an edge and its ...
0
votes
1answer
39 views

invite 12 person from 24 that we have 6 men and 6 womens [closed]

i had a question and its "A man has 5 female and 7 male friends and his wife has 7 female and 5 male friends. In how many ways can they invite 6 males and 6 females if husband and wife are to invite ...
2
votes
1answer
44 views

Compute the general time complexity of a merge sort algorithm with specified complexity of the merge process

The problem was from an exam, I spent much time wrapping my head up around this kind of problems, so I decided to ask for help ;( Problem: We implement a merge sort algorithm to sort $n$ items. The ...
1
vote
1answer
980 views

Define a DFA that accepts all even length binary strings that don't contain the substring “111”?

I think I have worked out a DFA that doesn't accept the substring "111," but I don't know how to account for accepting even length strings. Here is what I have so far. Any help would be greatly ...
1
vote
1answer
254 views

How to solve F(n)=F(n-1)+F(n-2)+f(n) recursive function?

Like in the title the following equation: F(n)=F(n-1)+F(n-2)+f(n) F(0)=0, F(1)=1 ...
2
votes
2answers
105 views

Prove that the number of edges is at least twice the number of vertices

I need to prove that In a simple graph $G$, if all the $n$ vertices have a degree of at least $4$, then the number of edges is at least twice the number of vertices. I already know that $\deg(n) = ...
2
votes
1answer
47 views

Alternate proof of the Caro-Wei theorem for lower bounding the independence number

Let $G$ be a graph on $n$ vertices whose degree sequence is $d_1,d_2,...,d_n$. Let $\alpha(G)$ denote the size of maximum independent set of $G$, i.e., the size of a maximum subset of vertices of $G$ ...
0
votes
0answers
22 views

Example of a language with linear NFA, but exponential DFA [duplicate]

So I read that regex engines use NFAs instead of DFA because f size blowup for dfas. I want to get an example of a language for which the minimum DFA has an exponential number of states but it,s NFA ...
1
vote
1answer
29 views

How to calculate $\sum_{i=1}^n \mu^2(i)$ in less than $O(n)$'s time

To go with $O(n)$, we can use the linear sieve according to that $\mu(n)$ is multiplicative. But it seems that we don't have to work each $\mu(n)$ out and accumulate them together, because I only want ...
2
votes
1answer
26 views

What's the connection between the two “Fast Walsh Transform”?

First Let's take a look at the convolution $\displaystyle C _ { i } = \sum _ { j \oplus k = i } A _ { j } * B _ { k }$, and the $\oplus$represents any boolean operation. And we are able to evaluate $C$...
2
votes
1answer
23 views

Design an algorithm for efficiently computing the k smallest numbers of the form a+b*sqrt(2)

Full question: Numbers of the form $a+b\sqrt{q}$, where $a$ and $b$ are nonnegative integers, and $q$ is an integer which is not he square of another integer, have special properties, e.g. they are ...
1
vote
2answers
99 views

How do you go from $\log P = \log N$ to the next step?

Let \begin{align*} &P=2^{\log_2 N}\\ &\Rightarrow \log_2 P = \log_2 N\\ &\Rightarrow P=N\\ &\Rightarrow 2^{\log_2 N}=N\,. \end{align*} I don't understand how can ...
1
vote
1answer
34 views

Number of ways to choose same number of elements from two different sets

Given two sets of elements S and R, with p elements and q elements respectively. 1 <= p,q <= n. Now, the number of ways to choose same number of elements from set S and R is $$\sum_{i=0}^{\min(p,...
2
votes
1answer
51 views

Coin flipping problem on an $n \times m$ grid

There are $n \times m$ coins lying on an $n \times m$ grid. Each coin is either facing up or down initially. We can do the following operation repeatedly: Flipping a row of coins; Flipping a colomn ...
1
vote
1answer
43 views

Is every graph with minimum degree $n/2$ connected?

Claim: Let $G$ be a graph on $n$ nodes, where $n$ is an even number. If every node of $G$ has degree at least $n/2$, then $G$ is connected. Decide whether the above claim is true or false, and ...
1
vote
1answer
60 views

What is the relation between Computer Graphics, Discrete Geometry, and Complexity Theory?

I am a master computer science student, and I am interested in both geometry and complexity theory. So I would like to know what is the relations between discrete geometry, computer graphics, and ...
1
vote
1answer
39 views

Maximizing entropy under constraint

How do I prove that entropy is maximal for $P(A_2) = \cdots = P(A_n) = (1-a) /(n-1)$ while $P(A_1) = a$ (a fixed number) and $A_1,…, A_n$ is a partition of the sample space?
1
vote
1answer
57 views

Discrete Mathematics Proofs for ∃ and ∀

Premises or Givens: $∃x(A(x) → B(x))$ $∀x (B(x) → K(x))$ To Prove: $∃x(A(x) → K(x))$ My Solution: $A(z) → B(z)$ From premise and Existential instantiation $x$ for $z$ $B(z) → K(z)$ From ...
1
vote
1answer
76 views

Possible ways to have cross and full edges in a mincut maxflow

I am trying to solve the following problem about maxflow mincut it seems like my conclusion is incorrect and I am wonder where. There is no graph just following question. An edge e can be (x) ...
4
votes
1answer
43 views

Probability of randomly designated subsets cover the universe

Let $U=\{1,2,\ldots,n\}$ and $S \subseteq \mathscr{P}(U)$. Let $T$ be a subset of $S$, randomly constructed selecting independently each element of $S$ with probability $p$. Is there a polynomial ...
0
votes
1answer
47 views

Efficient way to compute mod(w +1) or mod(w - 1) where w= 2^p

Knuth in his book provides a method of how to efficiently calculate mod(w +1) or mod(w-1) where w is a power of 2. I am not sure I could understand his assembly language completely. Could you explain ...
1
vote
0answers
58 views

Can somebody suggest what is wrong with these constraint? [closed]

I have written two constraints for Mixed integer linear problem. I am working on the scheduling problem i.e., Scheduling of hybrid appliances. For example, the washing machine is appliance indicated ...
2
votes
1answer
531 views

Average height of a BST with n Nodes

I have to find the maximum, minimum, and average height of a BST with n nodes. After doing some researching I found that the maximum height is $n-1$ and the minimum height is $\log_2(n+1)-1$. My ...
4
votes
2answers
66 views

Fast sampling from discrete space

Assume we are given a set $X = \{x_1,...,x_n \}$ of size $n$, and a probability distribution $P$ over $X$. I am interested in an algorithm $A$ which can sample from $X$ according to $P$, i.e. $\Pr(A=...
1
vote
0answers
42 views

For a minimum cut $(S, T)$, why do edges entering $S$ have a flow value of $0$?

I'm studying for an exam and I'm having trouble with a specific question: Let there be a flow network $G = (V, E)$ with a maximum flow $f$ and capacity $c$, a source $s \in V$ and a sink $t \in V$, ...