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 about discrete mathematics, the study of mathematical structures that are fundamentally discrete rather than continuous.

-1
votes
0answers
22 views

How to convert if else to map a array?

I have a variable Int a to set variable String b. ...
1
vote
1answer
37 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
37 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
21 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
47 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
29 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
37 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
59 views

Induction of recursive function

i'm trying to do these questions on an algorithms book, how might i use induction on these recursive functions like 1-7? Questions are in image
0
votes
1answer
43 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
52 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
57 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
54 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
38 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
22 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
83 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
32 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
46 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
39 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
186 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
43 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
68 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
18 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
81 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
47 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
52 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
177 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
176 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
36 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 ...
5
votes
1answer
119 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
76 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
55 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
30 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
46 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
291 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
42 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
50 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
36 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
100 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 ...