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
Join us in building a kind, collaborative learning community via our updated Code of Conduct.

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