Questions tagged [discrete-mathematics]

Questions about discrete mathematics, the study of mathematical structures that are fundamentally discrete rather than continuous.

Filter by
Sorted by
Tagged with
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/...
Lance's user avatar
  • 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 ...
Makogan's user avatar
  • 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: ...
Makogan's user avatar
  • 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\|$$...
Makogan's user avatar
  • 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 ...
LargeHorse's user avatar
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 ...
YoloV4's user avatar
  • 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 ...
user161190's user avatar
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 ...
Makogan's user avatar
  • 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 ...
bihariforces's user avatar
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}^...
Makogan's user avatar
  • 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 ...
user238607's user avatar
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 ...
Makogan's user avatar
  • 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 ...
Makogan's user avatar
  • 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 ...
Makogan's user avatar
  • 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 ...
Makogan's user avatar
  • 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 ...
Minko_Minkov's user avatar
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 ...
Phasivio's user avatar
  • 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 ...
Kagura Hitoha's user avatar
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$ ...
vidyarthi's user avatar
  • 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 ...
Redwill's user avatar
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 ...
Julius H.'s user avatar
  • 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 ...
Ibrakhim Tolobekov's user avatar
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. ...
Ibrakhim Tolobekov's user avatar
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.
aassegai's user avatar
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, \: ...
aassegai's user avatar
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 ...
Subhankar Ghosal's user avatar
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'...
Raxhacks's user avatar
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?
Raxhacks's user avatar
-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}=...
Arham Mehta's user avatar
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/...
Amir's user avatar
  • 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 ...
Amir's user avatar
  • 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'\...
levav ferber tas's user avatar
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 ...
yomol777's user avatar
  • 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, ...
raf120196's user avatar
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....
claydergc's user avatar
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 ...
Maciej Mehl's user avatar
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)=\...
MC From Scratch's user avatar
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,......
MC From Scratch's user avatar
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 ...
user12878817821's user avatar
-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
pierrovoltela's user avatar
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)...
Newbie's user avatar
  • 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/...
1m1's user avatar
  • 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+...
Blabla W's user avatar
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 ...
Ben Harris's user avatar
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))$
Maryam Panahi's user avatar
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 , .... , ⌈ ...
Nachiket Kanore's user avatar
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 ...
Lance's user avatar
  • 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 ...
Lance's user avatar
  • 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 ...
Sandeep's user avatar
  • 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 ...
Guts's user avatar
  • 49

1
2 3 4 5
11