Questions tagged [discrete-mathematics]
Questions about discrete mathematics, the study of mathematical structures that are fundamentally discrete rather than continuous.
507
questions
0
votes
0
answers
18
views
How to estimate the number of nodes in a trie based on a dictionary of words?
Say I want to build a trie out of 800,000 Sanskrit "base" words (in Devanagari script), with 20 prefixes and 2,000 possible suffixes. Each word is anywhere from 1-20 characters, and prefixes/...
- 2,163
1
vote
1
answer
14
views
How to avoid global delaunay check in conforming triangulation?
I implemented a conforming (i.e. it creates Steiner points using Ruppert's algorithm) delaunay triangulator, which is working, but there is one step I am doing that I straight up don't understand and ...
- 331
1
vote
0
answers
26
views
How to actually implement ruppert's algorithm?
I have been scouting the internet for resource son how to properly implement Ruppert's algorithm and what I ahve found is always lacking in details. The best resources I have so far are these 2:
...
- 331
1
vote
1
answer
38
views
Fast measurement of distance from point to mid segment?
Say you have a segment defined by 2 points $a,b$ and a third point $p$. You want to know the distance from $p$ to the midpoint of the edge.
This is very straightforward:
$$d = \|\frac{a + b}{2} - p\|$$...
- 331
1
vote
1
answer
113
views
Finding the Largest Partition of Non-Connected Nodes in a Graph in polynomial time
I have a graph, and I want to determine the largest possible set (or partition) of nodes such that no two nodes within this set have an edge between them. I am looking for an efficient algorithm to ...
- 83
1
vote
1
answer
65
views
Number of maximal induced trees in a connected planar graph
An induced subgraph $G’$ of a graph $G$ is a subset of its vertices along with all the edges that are present in $G$ among those vertices. For $G’$ to be a tree, all vertices of a cycle in $G$ cannot ...
- 73
2
votes
1
answer
91
views
Are integer linear *feasibility* problems NP-hard?
I know that Integer Linear Programming problems are NP-hard. But it seems like this answer is only applicable to Integer Linear optimization problems.
It seems like integer linear feasibility problems ...
- 25
0
votes
1
answer
24
views
How to enforce convexity of triangulation output?
I implemented an incremental Delaunay triangulation algorithm. It basically works except it has this weird issue.
The algorithm starts by creating a bounding triangle that it then splits recursively ...
- 331
1
vote
1
answer
42
views
product of every difference
Given a sorted array where every element is distinct, we need to evaluate product of every difference, modulo $ 10^9 + 7 $
$$ \prod_{i < j} (arr[j] - arr[i]) \% (10^9 + 7) $$
Best approach I can ...
- 105
0
votes
0
answers
20
views
Getting a V-representation from an H-Representation of a polytope
I am trying to find an easy to follow resource on implementing any (reasonable) algorithm to find a V-represnetation of a polytope from its h-representation. I only need this to work for $\mathbb{R}^...
- 331
0
votes
1
answer
54
views
Consider A Busy Beaver like Turing Machine on a Mobius Strip. Is it equivalent to standard BB number?
I have modified Busy Beaver Turing Machine scenario. Is this new scenario equivalent to the standard one?
Consider a double sided tape twisted it into a mobius strip having P slots in total.
Initially ...
- 111
1
vote
0
answers
39
views
Algorithm for Steiner points?
I am trying to find resources that explain an easy to implement (not necessarily optimal but reasonable runtime) algorithm for inserting Steiner points in a triangulation.
There seems to be little ...
- 331
4
votes
2
answers
491
views
Detecting if an edge is "inside" a polygon?
I have computed a constrained triangulation of a set of points. The constraint happens to be a closed polygon.
The objective is to detect all edges which are inside the polygon, that is, an edge where ...
- 331
3
votes
2
answers
80
views
Constrained Delaunay triangulation algorithm?
I am trying to find a resource which explains how to compute the constrained Delaunay triangulation of a set of points and edge constraints, I found these slides by Jonathan Shewchuck, but without the ...
- 331
3
votes
2
answers
64
views
Efficiently finding point triangle inclusion when doing incremental delaunay triangulation?
I want to implement a delaunay triangulator by using incremental building, which is purported to be $O(n \log(n))$ I am a little puzzled about 2 things.
Ever resource I read on the matter says:
Make ...
- 331
0
votes
1
answer
91
views
Harder variation of light bulb problem (solvable in O(n log n)?)
Problem originally from: https://train.nzoi.org.nz/problems/1311
Every light-bulb is initially off, and O(N^2) solutions are too slow.
Emma is a massive nuisance at school by always meddling around ...
- 26
1
vote
1
answer
98
views
Reduction from MAX-3-CUT to MAX-CUT
Both MAX-CUT and MAX-3-CUT are known to be NP-complete. This post shows a reduction from MAX-CUT to MAX-3-CUT. I am curious if there is a way to reduce MAX-3-CUT to MAX-CUT?
MAX-CUT: Given an ...
- 113
0
votes
1
answer
39
views
On the equivalence between two definitions of universal hashing
Let $H=\{h|h:X\to Y\}$, $|X|=n$, $|Y|=m$. $H$ is a universal hash family if
Def 1. For any $x_1,\ x_2\in X$, $x_1\neq x_2$, $\left|\left\{h\in H\middle| h(x_1)=h(x_2)\right\}\right|\leq |H|/m$. (or ...
1
vote
0
answers
32
views
Maximum size of a graph with given girth
I am unable to get the bound on the maximum size of a graph of order $n$ with girth $g$. Is there any literature regarding this. I know that there is an asymptotic bound on the size of a graph $G$ ...
- 175
0
votes
0
answers
34
views
Algorithm to maximize generated maze score
I need to generate maze with 100x100 rooms. Each room connected only with 1 other room.
Here are example of correct 2x2 mazes:
+-+-+
|...|
+-+.+
|...|
+-+-+
And ...
- 1
0
votes
0
answers
7
views
Does T5 or another embedding embed every possible length tokenization?
I’m curious about an embedding technique where every possible “tokenization” of a text gets an embedding - not just individuals words, but every single 2-gram, 3-gram, and n-gram.
Does this exist?
Or ...
- 123
1
vote
0
answers
41
views
Show that the graph on 99 vertices cannot be divided into two classes
In a graph with 99 vertices, two vertices have a degree of 3, and the degree of the other vertices is 4. Show that the graph contains an odd cycle.
I figured I have to show that the graph cannot be ...
5
votes
1
answer
131
views
Let the vertices of the graph G be the numbers 1, 2, ..., 100, a. Determine χ(G), the chromatic number of the graph G
Let the vertices of the graph G be the numbers 1, 2, ..., 100, and two (different) vertices be adjacent if and only if at least one of 2, 3, or 5 is a common divisor of the respective numbers. ...
0
votes
0
answers
24
views
Can a CFG parse tree have a root other than S?
Can a CFG parse tree have a root other than starting non-terminal S? Except for the cases when tree has a height equal to zero and contains only one symbol from the main alphabet.
- 13
0
votes
1
answer
87
views
Markov algorithm for words of the form $ww$, $w\in \{a,b\}^*$
I need to construct a Markov algorithm as a set of an ordered rules which will recognize a language $L = \{ww |w \in \{a,b\}*\}$ and give
$$\begin{cases}
Y, \: \text{if given word is in L} \\
N, \: ...
- 13
1
vote
1
answer
48
views
How to generate all possible colour vectors generated by greedy colouring on a graph?
Given a graph $G$, how can we generate all possible color vectors that could be generated via greedy coloring?
N.B. Greedy coloring takes a graph and an order of vertices. It traverses vertices ...
- 298
1
vote
1
answer
467
views
Regular Expression of {w : w contains an even number of 0s and exactly two 1s}
I know the answer if it was OR would be (1*01*01*)* U 0*10*10*, but with the AND I have no clue how this can be achieved. There are lot's concatenations that I can'...
- 11
0
votes
0
answers
10
views
Regular Expression of {w : w contains exactly two 0s and at least two 1s} [duplicate]
I have this 1^*011^*011^* and haven't been able to think of it differently. Can you please help me see how I can get this input 0011 and 1100 correct?
- 11
-2
votes
1
answer
110
views
This is an exercise in CLRS 4th Edition. I am not sure how to solve this question, and I am not even sure how I would use equation 3.14
Use equation (3.14) or other means to show that $(n+o(n))^{k}=\Theta\left(n^{k}\right)$ for any real constant $k$. Conclude that $\lceil n\rceil^{k}=\Theta\left(n^{k}\right)$ and $\lfloor n\rfloor^{k}=...
- 101
0
votes
0
answers
24
views
Is there any upper bound for the number of ways we can partition a multiset, where each part/segment in the partition has distinct elements?
A question is asked in the below link, which asks for the number of cases we can partition a multiset, where each part/segment in the partition has distinct elements.
https://math.stackexchange.com/...
- 1
0
votes
0
answers
32
views
How many ways we can partition a multiset, where each part/segment in the partition has distinct elements? [duplicate]
We define the set S as {(s1, f1), (s2, f2), ..., (si, fi)}, where each si is the frequency that it is repeated in the multiset T. How many ways can we partition the multiset T into different ...
- 1
1
vote
1
answer
35
views
Finding all zero sums of length m and checking for zero subsums on an abelian group (generalization of the sub sum problem?)
Let $G$ be an abelian group. We say that $G$ has property $V_n$ if for every $m > n$ and a list $L\subset G$ of $m$ elements s.t. $\sum_{g\in L}g=0$ there is a proper subset $\emptyset\neq L'\...
1
vote
1
answer
59
views
Number of ways to make change in o(k), where k is number of coins
Godd afternoon,
We have set C of k coins; For example C = (2, 3)
We have positive integer n.
In how many ways we can represent n using those coins?
Example:
If n = 12; C = (2, 3) we can represent 12 ...
- 111
2
votes
0
answers
38
views
Effecient algorithm to build a linear order on a set of states of automaton
Is there an algorithm that help to build a linear order on a set of states of automaton (without output signals), such that this order is compatible with a transtion function of automaton?
Let A = (X, ...
- 21
0
votes
2
answers
108
views
How to represent a point cloud in the pseudocode of an algorithm?
I am writing a scientific paper in which I describe some algorithms (using pseudocode) that have point clouds as inputs. In these algorithms, I need a mathematical structure to represent a point cloud....
1
vote
1
answer
31
views
Universal class $\mathcal{H}_{p, m}$ of hash functions has $p(p-1)$ members
In CLRS it is stated that the class $\mathcal{H}_{p, m} = \{ h_{ab}:\mathbf{Z}_p \to \mathbf{Z}_m \mid a \in \mathbf{Z}_p^*, b \in \mathbf{Z}_p\}$, $h_{ab}(x) = (ax+b) \mod p \mod m$, $m < p$ prime ...
- 13
1
vote
0
answers
53
views
Sum of coprime divisors
Define the following function to be the count of integers not greater than $L$ that are coprime to $n$:$$C(n,L)=\sum_{k=1 \atop {GCD(n,k)=1}}^L1$$
Then I am interested in the following sum:
$$S(x)=\...
- 143
3
votes
1
answer
91
views
Counting integers $n \leq x$ with a given prime signature
Given is a prime signature $S$ and an integer $x$. The task is to count how many integers $n$ exist such that $n \leq x$, and if $n = p_1^{k_1}p_2^{k_2}p_3^{k_3}p_4^{k_4}...$ then $S = (k_1,k_2,k_3,......
- 143
0
votes
1
answer
126
views
Algorithms for finding closest graph node within set of nodes
Given a set of nodes $N$ on an undirected, weighted graph $G$ and a query node $n$, what is the fastest algorithm for finding the node in $N$ that is closest to $n$?
Furthermore, say we are doing many ...
-2
votes
1
answer
43
views
Need help proving the following for every integer n larger or equal to 1
i need help proving the following :
$$\sum_{k=1}^{n}\frac{1}{(3k-1)(3k+2)}=\frac{n}{6n+4}$$ for every integer n larger or equal to 1
Can you help? Thanks
1
vote
0
answers
46
views
Distinguishing two distributions with f-divergence
The statistical distance (SD) has been widely used as a 'measure' of the closeness of two distributions $D_1$ and $D_1$.
Suppose that the statistical distance (here, total variation with $\ell_1$ norm)...
- 11
1
vote
1
answer
24
views
Decomposing large bit mult or exp into smaller bit operations
Imagine a machine that can only hold N-bit values (N-bit uint).
The machine can also calculate the 2N-bit result of two operations: mult, exp.
The 2N-bit result is stored across 2 N-bit values (high/...
- 11
0
votes
2
answers
180
views
Sum of average of all subarrays
Suppose there is an integer array $a_1,a_2,...,a_n$. Calculate the sum of average of all subarrays. For example, the sum of average of all subarrays of array $[1,3,5]$ is $1+3+5+\frac{1+3}{2}+\frac{3+...
- 19
0
votes
1
answer
122
views
Walk from vertex u to vertex v on complete graph, formula for number of walks of length k
Complete graph with n vertices.
Walk from vertex u to vertex v of length k.
I don't understand how the number of walks between the two of length k is $n^{k-1}$
I've tried this formula on an example ...
- 13
0
votes
1
answer
54
views
equivalency of some facts in $O$ notation
I misunderstanding about some logarithm property in algorithm course:
is it correct that we say following three term is equivalent?
$O(\log a + \log b)$
$O(\log (ab))$
$O(\log (a+b))$
- 381
0
votes
1
answer
169
views
Finding Sum(F(i)) where F(i) = min(⌈ Ai / B1 ⌉ * C1, ⌈ Ai / B2 ⌉ * C2, ⌈ Ai / B3 ⌉ * C3, .... ,⌈ Ai / Bm ⌉ * Cm)
Given three arrays A, B, and C of size n, m, and m respectively (1-based indexed). A function F(i) is defined as -
F(i) = minimum_of(⌈ Ai / B1 ⌉ * C1 , ⌈ Ai / B2 ⌉ * C2 , ⌈ Ai / B3 ⌉ * C3 , .... , ⌈ ...
1
vote
0
answers
29
views
How do you generate lots of binary de Bruijn sequences (somewhat small, such as less than 100 bits)?
I have been learning about de Bruijn sequences recently. I looked at this C library on Greedy algorithms, and took what I learned to make this JavaScript version, which tries to make as many de Bruijn ...
- 2,163
1
vote
1
answer
81
views
What is a de Bruijn sequence exactly?
I just discovered the term "de Bruijn sequence", but don't quite follow what it means exactly (or how de Bruijn is pronounced :), "brown" I guess).
There are two good resources I ...
- 2,163
0
votes
1
answer
100
views
Mathematical Induction vs Strong Induction
In Rosen's book Discrete Mathematics and Its Applications, 8th Edition it is mentioned that:
You may be surprised that mathematical induction and strong induction are equivalent. That is, each can ...
- 337
1
vote
1
answer
103
views
3-colouring with a bounded amount of colors
The topic of 3-colouring is often talked about, but what happens if we limit the amount of times we can use one color? Take a graph $G=(V,E)$ with $k$ being the number of vertices, is it possible for ...
- 49