Skip to main content
Share Your Experience: Take the 2024 Developer Survey

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
1 answer
45 views

What exactly is a lattice?

In the class,my teacher give me the definition of lattice as below and show me some examples. But I was confused to the example(b): why do b and c have no least upper bound? I think d and e is the ...
san zhang's user avatar
-1 votes
0 answers
4 views

Trouble with Bayesian Linear Regression: Likelihood Calculation Issue

Perform Bayesian linear regression for various values of the uncertainty parameter (α) governing the Gaussian prior over weight parameters, along with corresponding values of σ². The uncertainty ...
User's user avatar
  • 9
1 vote
1 answer
31 views

Does a processing architecture exist that parallelises division operations?

I understand that while multiplication and division operations require similar compute power, multiplication can be parallelised per operation, meaning that using more transistors* in parallel to get ...
J Collins's user avatar
  • 143
2 votes
3 answers
910 views

Does Either...Or means Exclusive Or or Inclusive Or?

Let's take a compound propositions Either it is below freezing or it is snowing. Now if, $p$: it is below freezing $q$: it is snowing Question Link: https://gateoverflow.in/42720/kenneth-rosen-...
tbhaxor's user avatar
  • 208
8 votes
0 answers
99 views

Problem of constructing binary sequence with least possible 1s under given constraint

You are given a binary pattern p. Problem is to construct a binary sequence of length n such that by sliding p over our sequence there is always at least one position where two 1s align (one in the ...
Relja Šegvić's user avatar
3 votes
1 answer
227 views

How to optimize algorithm to solve the following time series problem?

I am working on a project and came across the following problem I have to solve. Imagine we have a time series data Ts which is an array of pair, say each element ...
askyfullofstars's user avatar
16 votes
4 answers
3k views

Why is Integer Linear Programming in NP?

The decision version of the problem Integar Linear Programming is the following: Input: two matrices $A\in \mathcal{M}_n(\mathbb{Z})$ and $B\in \mathcal{M}_{n,1}(\mathbb{Z})$. Question: is there a ...
Nathaniel's user avatar
  • 15.7k
1 vote
0 answers
38 views

Set cover variation: disjoint covers for all but one element

In the classical set cover problem, we are given the set $U$ of elements $\{1, \dots, n\}$ and a collection $C$ of some subsets such that their union is the whole set. Now, I will introduce the first ...
cgss's user avatar
  • 111
0 votes
0 answers
143 views

O(n) algorithm to find primes up to n

I don't know the name of this algorithm, but anyway it was interesting to share (btw Linear sieve, Sieve of Atkin and Sieve of Pritchard performs better) The main idea is to use the Fundamental ...
Lorenzo Tinfena's user avatar
1 vote
1 answer
134 views

Hoare Logic: Identifying Hoare Triple given a simple function

The program is designed to start with values for $x$ and $y$. The variables $u1$​ and $u2$​ are intended to represent $x$ and $y$ in ascending order. Provide suitable preconditions and postconditions ...
User's user avatar
  • 9
0 votes
0 answers
63 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,243
1 vote
1 answer
19 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
  • 341
1 vote
0 answers
30 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
  • 341
1 vote
1 answer
39 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
  • 341
1 vote
1 answer
125 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
72 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
181 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
25 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
  • 341
1 vote
1 answer
62 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
38 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
  • 341
0 votes
1 answer
71 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
42 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
  • 341
4 votes
2 answers
545 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
  • 341
3 votes
2 answers
128 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
  • 341
3 votes
2 answers
89 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
  • 341
0 votes
1 answer
144 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
128 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
1 vote
1 answer
55 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
34 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
35 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
12 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 Hamilton's user avatar
1 vote
0 answers
42 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
162 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
27 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
98 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
55 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
742 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
-2 votes
1 answer
189 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
25 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
1 vote
1 answer
40 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
79 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
39 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
117 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
33 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
55 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
94 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
1 vote
1 answer
185 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
44 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

1
2 3 4 5
11