Questions about discrete mathematics, the study of mathematical structures that are fundamentally discrete rather than continuous.
4
votes
2answers
45 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=...
0
votes
0answers
27 views
Min-Cut-Max-Flow Theorem Question
I'm studying for an exam and having trouble with a specific questions for which I don't have a solution.
Question : Why do edges from a minimum $S$-$T$-cut which go into $S$ have a flow value of $0$?
...
2
votes
1answer
18 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
78 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
25 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
31 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
41 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
37 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
22 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
60 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
18 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
101 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
41 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
34 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
22 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
17 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
32 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 ...
1
vote
1answer
73 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
46 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
50 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
168 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
166 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
28 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 ...
4
votes
1answer
103 views
Moving an edge in a weighted tree to maximize longest path length
Let $G$ be a undirected edge-weighted tree, where all edge weights are positive. A move of an edge $\{u,v\} \in E(G)$ is the operation of deletion of $\{u,v\}$ and the addition of a new edge $\{x,y\}$,...
1
vote
1answer
74 views
Filling a string with wildcards with minimum cost
You are given a string with wildcards, e.g. X***Y*Z. Your goal is to print an input string filling all the wildcards in the given string.
You are allowed to write data to the string in blocks of ...
2
votes
0answers
22 views
Filling a board with maximum number of fixed size tiles
You are given a rectangular board of known size, e.g. 20x20 cm. Some 1x1 cm pieces are missing. Your task is to cover this board with a maximum number of 2x2 cm tiles (an example is attached below), ...
0
votes
0answers
39 views
An energy consumption problem
We want to show one schedule of jobs consumes less energy than another one. For example, there are two schedules A and B. Both the schedules A and B schedule two jobs $j_1$ and $j_2$ with execution ...
0
votes
0answers
53 views
Median of list of difference of elements
I have a list. I have to find median of absolute difference of all pairs of array.
Eg - A={1,2,10}
Difference for all distinct pairs :
1-10=9
1-2=8
2-10=8
...
2
votes
0answers
20 views
Find Vector in set A furthest from any Vector in set B
Given 2 sets of Vectors in 3 dimensional space: A and B, what are the fastest algorithms to find the vector in set A furthest from any in set B?
0
votes
0answers
42 views
$(Q\to R)\wedge (R\to Q)$ converting to sentence
Well, I am following this video lecture (MOOC) and I came across this quiz where I have to convert $(Q\to R)\wedge (R\to Q)$ to sentence.
$Q$: "I will go to town"
$R$: "I have time"
My answer to $(...
0
votes
0answers
44 views
Need resources to learn about Graph Spanners
I'm trying to learn about Graph Spanners. I have searched for it but unfortunately, I couldn't find any solid helpful resource related to this very topic.
I would highly appreciate if anyone can ...
1
vote
1answer
175 views
How to transform Nondeterministic finite automaton (NFA) to regular expression equivalent
Im struggling to understand how to transform Nondeterministic finite automaton (NFA) of the following form:
To a regular expression equivalent. What I have tried was using arden's rule. However I ...
1
vote
1answer
41 views
Simplifying sum of falling factorials
I wrote the worst algorithm in the world.
Doesn't matter what it does. I have just a question about folding formula for it's time complexity into some shorter form which would be easier to compute.
So ...
1
vote
0answers
46 views
Should I go for computer science or maths? [closed]
I am in 11th grade. The only subject which I love the most is solving alegebraic equations and questions related to it. I enjoy doing trigonometry but hate the part of proving theorems. I opted ...
1
vote
1answer
33 views
Inequality over the entropy of an integer-valued random variable
I stumbled upon this inequality over a course on Information Theory :
If $Z\in\mathbb{N}$ with finite mean, then $H(Z) \leq E(Z)\times h(\frac 1 {E(Z)})$ where $h$ is the binary entropy function
...
2
votes
0answers
87 views
How many similar binary search trees are made from different permutations?
If I have numbers ranging from 1 to n, and I generate all the permutations of these numbers. Now, I create Binary search tree from these permutations. For a value n i want to know how many BSTs would ...
1
vote
1answer
22 views
Divide sequence of numbers from 1 to n into 2 groups with minimum difference
Let's say for some $n$ we have the sequence $1, 2, 3, \dots , n$, what we want with this sequence is to divide it in two sets such that each element of the sequence will be in only one set, and the ...
2
votes
0answers
57 views
How to solve a knapsack problem using a modified version of DP?
Im having difficulties understanding how to solve the knapsack problem using dynamic programming, where v is value and w is the weight, where I can fill up to a maximum weight j for some Capacity_J:
<...
1
vote
1answer
46 views
Relation between $\sqrt{x^2+y^2}$ and $|x|+|y|$
I have a problem in which I was given $n$ points and an integer $k$, and I need to find the $k$ points that are the closest to origin. My approach is to find the distances from origin of all points ...
0
votes
0answers
25 views
Event-based rather than flow-based systems?
This is a very vague question, so I don't know if people will understand it (I'm not even sure I understand the question myself), but here goes. Also, I'm not sure if this is really the right forum to ...
1
vote
1answer
43 views
Can Hall's theorem be applied to scheduling problems?
If I have a scheduling problem, is it possible that Hall's theorem can be applied? I was thinking that the graph representation of the scheduling problem can be the preferences of the people / workers ...
1
vote
1answer
52 views
Best complexity to find solutions to $x^2+y^2=z^2$
What is the algorithm with the best complexity that finds solutions in a given range to the equation $x^2+y^2=z^2$ ?
The best i could do is to iterate through all $x$ and all $y$ and store $x^2+y^2$ ...
0
votes
0answers
19 views
group date ranges into buckets
I have a problem where I have a date range and I want to split the date range into chunks(provided by user) such that each chunk has a whole date range(start of month to end of the end month). I want ...
1
vote
1answer
105 views
Polynomial bound on sum of strings
I am struggling with the following problem:
Given a set of finite binary strings $S=\{s_1,\ldots,s_k\}$, we say that a string $u$ is a concatenation over $S$ if it is equal to $s_{i_{1}} s_{i_{2}} \...
1
vote
0answers
49 views
A road-map for mathematics needed in CS? [closed]
Before asking my question, I have to give some background about myself. I live in Iraq and this made my education a total disaster. My middle/high school math skills are not that great and I never ...
2
votes
4answers
154 views
Is it necessary to learn how to prove Mathematical theorems as a CS Student? [closed]
I've just started my undergraduate course and have tried my hands on MIT's OpenCourseWare on Discrete Math on Logic and Proofs. There was a particular question asking to prove Cantor's Theorem:
...
2
votes
1answer
37 views
Simple discrete math problem: A and B in 3CNF
I need to write (A and B) in 3CNF, and for whatever reason, I can only come up with (A or B) in 3CNF (A OR B OR X) AND (NOT(X) OR A OR B). Any help is greatly appreciated!
1
vote
1answer
72 views
Question on Predicates and Quantifiers
I am reading from "Discrete Mathematics and Its applications" by Kenneth H. Rosen, 7th edition. Consider the highlighted part in the following example taken from the same book:
Question Use ...
