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.

515 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
• 9
1 vote
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 ...
• 143
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-...
• 208
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 ...
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 ...
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 ...
• 15.7k
1 vote
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 ...
• 111
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 ...
1 vote
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 ...
• 9
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/...
• 2,243
1 vote
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 ...
• 341
1 vote
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: ...
• 341
1 vote
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\|$$...
• 341
1 vote
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 ...
1 vote
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 ...
• 73
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 ...
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 ...
• 341
1 vote
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 ...
• 333
38 views

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