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.

-1
votes
0answers
19 views

Formula for maximum matching in bipartite graph

Let $G = (U, W, E)$ be a bipartite graph. Show that $\alpha'(G) = \min(|U| - |S| + |N(S)|)$, where $S$ ranges over all subsets of $U$, $\alpha'(G$) is the size of maximum matching of $G$, and $N(S)$ ...
5
votes
2answers
70 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
119 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
92 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 ...
3
votes
2answers
105 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
23 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
29 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
65 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
54 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
44 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
36 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
7 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
13 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
14 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
36 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
37 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
440 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
74 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
52 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
36 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
19 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
27 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
17 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
22 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
61 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
49 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
41 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
51 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
59 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
42 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
45 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
56 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
267 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
58 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
41 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$, ...
2
votes
1answer
31 views

Minimum number of strings to cover entire space within Hamming distance

Given $(n, k)$: What is the minimum number $x$ of (binary) strings such that all $n$-bit (binary) strings are within $k$ Hamming distance of some string? Is there an asymptotic expansion or lower ...
8
votes
2answers
1k views

Double exponentials vs single exponentials

Here are four tenets I cannot reconcile: Double exponential time algorithms run in $O(2^{2^{n^k}})$ time with $k \in \mathbb{N}$ constant Exponential time algorithms run in $O(2^{n^k})$ with $k \in \...
5
votes
2answers
94 views

Definition of “properly partial” versus “total” value types

In the Foundations chapter of Elements of Programming (Stepanov and McJones, 2009), this paragraph appears: A value type is properly partial if its values represent a proper subset of the abstract ...
3
votes
1answer
26 views

Detecting isthmuses on digital curves

Consider a digital curve, i.e. a sequence of points at integer coordinates, with unit taxicab distance between them. I want to find the isthmuses, i.e. sections of the curve that are close to each ...
2
votes
1answer
58 views

Centre, diameter, and radius of graph

I have been thinking a lot on some questions related to centres, diameter ($D$), and radius ($R$) of an undirected connected graph, but couldn't find anywhere the answers, so am posting here. Ques1. ...
3
votes
1answer
56 views

Is k -rainbow coloring of a hypergraph NP-complete or not?

**A hypergraph is k-rainbow colorable if there exists a vertex coloring using k colors such that each hyperedge has all the k colors. Is k-rainbow coloring of a hypergraph is NP-complete or not? The ...
-2
votes
1answer
61 views

Symmetric difference of a set with an empty set [closed]

The definition of symmetric difference of two sets $\alpha $ and $\beta$, $\alpha \oplus \beta$ is defined as the set of all $x$ such that, $x \in (\alpha \cup \beta) - (\alpha \cap \beta)$. If, $\...
0
votes
0answers
25 views

Classify manifolds with neural networks

Can a neural network be used to find the genus of a 2-manifold given for instance as a CW complex?
1
vote
0answers
64 views

Best way to make the jump from programming to computer science

I have decent enough experience with programming to be able to tackle most things but I want to know how you recommend making the jump from just programming to computer science. I still have a couple ...
-1
votes
1answer
20 views

Independence groups and fully connected groups

Let G be a connected graph, knowing that it has more than 9 vertex, Show that either its independence number is bigger-equal than 4 or its click number (the size of the biggest fully connected group) ...
0
votes
1answer
312 views

Prove that, if deg(v) ≥ (n−2)/3 for every vertex v in G, then G contains at most two connected components

Let G be a graph with $n$ vertices such that $n\geq2$. Prove that, if $\mathrm{deg}(v)\geq \frac{n-2}{3}$ for every vertex $v$ in G, then G contains at most two connected components.
0
votes
1answer
48 views

Can anyone find a mapping from the set of all possible string to the natural numbers?

Can anyone find a map(injection) $h$ from the set of all possible strings $S^*$ to the natural numbers $\mathbb{N}$? $$h : S^* \rightarrow \mathbb{N} $$ Assume $S$ is finite. I would prefer an ...