Stack Exchange Network

Stack Exchange network consists of 174 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
vote
1answer
25 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
162 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
57 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
41 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) = ...
0
votes
0answers
19 views

How to compute last $k$ numbers of $n \choose m$ efficiently?

I know that the Lucas Theorem was able to solve ${n \choose m} \bmod p$ when $p$ is a prime and small enough (not up to $10^{18}$, etc). But the problem is that I want to calculate last $k$ numbers ...
2
votes
1answer
34 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
15 views

Determine all functions $f : \mathbb{N} \rightarrow \mathbb{N}$ such that for every positive integer $n$ we have: $2n+2001≤f(f(n))+f(n)≤2n+2002$ [migrated]

I don't know where to start as in is there a function that I can get to the solution by slightly modifying it? Any ideas
-1
votes
0answers
33 views

Proving Quadratic Kernel

We have the given quadratic kernel. $K(x, y) = (x^T y)^2$ $\phi([x1, x2]) = \{x1x1, x1x2, x2x1, x2x2\}$ Show that $K(x, y) = \phi(x)^T \phi(y)$ for arbitrary $n$-length vectors. I can show that ...
0
votes
0answers
14 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
20 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
52 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
40 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
48 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
56 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
0answers
36 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
40 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
0answers
25 views

Algorithm Fragment Analysis

I am not exactly sure what this question is asking: Provide an asymptotic notation for the sum obtained as the result of the following program fragment: ...
0
votes
1answer
44 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
55 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
125 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
55 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
39 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
24 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
85 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
42 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
54 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
42 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
23 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
63 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
249 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
45 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 ...
1
vote
2answers
184 views

Does graph G with all vertices of degree 3 have a cut vertex?

I'm asked to draw a simple connected graph, if possible, in which every vertex has degree 3 and has a cut vertex. I tried drawing a cycle graph, in which all the degrees are 2, and it seems there is ...
0
votes
0answers
24 views

prove that G has twice as many edges as vertices only if n >= 5 [duplicate]

Suppose $G$ is a simple graph with $n$ vertices, prove that $G$ has twice as many edges as vertices only if $n \geq 5$
0
votes
0answers
23 views

Lower Bound Space complexity one pass algorithm / Heavy-Hitters Problem

I am confronted with the following problem: Let S be the family of all m-subsets of $[n] = [2m]$ let $S_1, S_2 \in S$ be distinct sets and let the state of storage be $State_1$ after stream $S_1$ is ...
1
vote
0answers
30 views

System of congruences with non-pairwise coprime moduli

I have a set of congruences x ≡ a1 (mod n) ... x ≡ ak (mod nk) And I want to find x, this can be solved by the Chinese ...
2
votes
2answers
34 views

Can a perfect matching always be found by a picking sequence?

There are $n$ people and $n$ items. For each person, there is a set of items he likes. Our goal is to give to each person a single item that he likes, i.e, find a perfect matching in the preference ...
2
votes
2answers
108 views

Empty intersection of longest path in connected graph

Do all longest paths share a common point? (Gallai 1966) A few years later, Walther produced a counterexample on 25 vertices (a). The simplest counterexample was found by both Walther and Zamfirescu ...
0
votes
1answer
48 views

sub-optimal but fast partition generation

I have a set of N integers that I want to partition into m subsets. I want these subsets to be well-balanced wrt some criterion say that minimize the max difference between the size of all subsets. ...
2
votes
2answers
61 views

How to decompose a unit cube into tetrahedra?

I was presented with the problem of breaking the unit cube $[0,1] \times [0,1] \times [0,1] $ into tetrahedron shapes. The first two pieces are easy, but it's not so easy to visualize after that. I ...
5
votes
1answer
194 views

How to solve a recurrence relation with a sum?

How do I solve the following recurrence relation? $$ T(n) = 1 + \sum_{j=0}^{n-1} T(j). $$ I thought of solving it by generating its recursion tree. I found that the height of the tree would be ...
3
votes
2answers
191 views

How to check if a specific ILP problem can be solved in polynomial time or not?

How can we know that a specific ILP problem is solvable in polynomial time or not given the constraints?
1
vote
1answer
48 views

Placing small circles randomly inside a larger circle, where no two small circles intersect

Sorry if this is the wrong place to ask, was unsure...let me know if it belongs some where else. So i am trying to work out a way to write an algorithm to place a series of small circles of a set ...