Questions tagged [discrete-mathematics]
Questions about discrete mathematics, the study of mathematical structures that are fundamentally discrete rather than continuous.
329
questions
1
vote
0answers
13 views
Separating the snakes
In a two-dimensional grid, there are $n$ "snakes" (sets of contiguous grid-blocks). The snakes do not touch each other. The goal is to cut the grid into $n$ rectangles using $n-1$ "fences" (horizontal ...
-2
votes
0answers
50 views
Prove big-Oh by induction
How can I prove by induction that
C * O(1) = O(1)
For every C > 0 while C is a const and for every f, g function
2
votes
1answer
27 views
Prove that there is a sequence of k minimum spaning trees between two distinct minimum spanning trees that each one is different in only 1 edge [duplicate]
I'm pracitcing exams towards finals,
Given an undirected graph $G(V,E)$ , we denote 2 MST $T,T'$ neighbours if by deleting one edge from $T$ and add another one we get $T'$.
Prove :
for every 2 ...
2
votes
1answer
45 views
Encoding set of At-Most-One constraints as a MAX-SAT problem
Assume a set of variable $V$ = $\{v_1,...,v_m\}$.
Given total $n$ at-most-one (AMO) constraints (at most one element in a given set is true) set [of the below form], over the variable set $V$,
$$ ...
0
votes
2answers
76 views
How is the set of functions from ${\{a,b\}}$ to $N$ countable?
Assume a set of functions from ${\{a,b\}}$ to $N$
Where $N$ is the set of Natural numbers.
Let us assume that the size of $N$ is $n$.
i.e $|N|=n$
The first element $a$ have $n$ choices for mapping....
0
votes
0answers
12 views
How to model most optimized encoding of string data
Sorry if this question isn't super well defined, I am just struggling currently with figuring out what an "ideal solution" looks like to the following problem, and haven't pinned down an equation.
I ...
3
votes
2answers
139 views
Proof of the inclusion-exclusion principle
The inclusion-exclusion principle for $n$ sets is proved by Kenneth Rosen in his textbook on discrete mathematics as follows:
THEOREM 1 — THE PRINCIPLE OF INCLUSION-EXCLUSION Let $A_1,...
0
votes
1answer
45 views
Language to regex
Let A={a,b}.
So the question is to write regular expression such that L(r) which consists of all words.
My answer is this:
L(r)= (a+b)* a* b* (a+b)*
Is this ...
3
votes
1answer
50 views
Triangulation of disjoint line segments
Given a set of disjoint line segments in the plane, prove (or disprove) that you can always join the line segments to make a near-triangulation where the vertices are the endpoints of the segments, ...
3
votes
2answers
44 views
Joining line segments to make tree
Given a set of disjoint line segments in the plane, prove (or disprove) that we can always join the line segments to make a tree where the vertices of the tree are the endpoints of the segments and ...
3
votes
1answer
38 views
Prove vertices of polygon are endpoints of disjoint line segments
If we are given a set of disjoint line segments in the plane, can we prove (or disprove) that we can always join the line segments to make a simple polygon where the vertices of the polygon are the ...
5
votes
1answer
66 views
Near Triangulation Planar Graph
This is the problem I am dealing with:
Given a set P of n points in general position, let a graph G be defined as follows:
The vertex set is P. Two vertices, a and b, are joined by an edge provided ...
6
votes
2answers
69 views
Voronoi Diagram Drawing Variations and Charateristics
I am learning about Voronoi diagrams and I have seen that the Voronoi diagram of a set of points is drawn with straight line segments and rays.
Similarly how can we draw the Voronoi diagram for the ...
5
votes
1answer
95 views
Voronoi Cell and Voronoi Diagram
Consider a set R of n red points and B of n blue points in the plane. Let x∈R and y∈B be the shortest edge xy. Let P = R ∪ B. Let Vor(P) be the Voronoi diagram of P. Let V(x) be the Voronoi cell of x ...
6
votes
0answers
102 views
Placing a tripod in a plane such that it partition a given set of points (with pic)
I would appreciate if anyone could help me with the following problem:
Given a set of 3n points in the plane with n > 0, is it possible to find a placement of a tripod such that each region contains ...
1
vote
1answer
39 views
Proving set of finite languages vs all languages over finite alphabet to be countable / uncountable
I came across following facts:
Set of finite languages over a finite alphabet is countable.
Set of languages over finite alphabet is uncountable.
I believe proof of this will be similar to ...
0
votes
1answer
24 views
$O(k)$ Algorithm to find the first $k$ pairs of Magic numbers $a$ and $b$ such that $\sum_{i=1}^{a-1} i = \sum_{k=a+1}^b k $, with restrictions
Provide an $O(k)$ algorithm to find $k$- magic pairs of positive integers a and b of type signed int where a magic pair is defined as $\sum_{i=1}^{a-1} i = \sum_{k=a+1}^b k $. You can't use the ...
5
votes
2answers
107 views
Fermat's last theorem: How to (partially) solve by programs
No three distinct positive integers $a, b, c$ can satisfy the equation
: $a^n + b^n=c^n$, if $n$ is an integer greater than two.
The above statement, known as the Fermat's last theorem is proven ...
1
vote
1answer
51 views
O(n) external intersection points?
I have a doubt. For a given n (axis-parallel) squares in a plane, where there are Ω(n²) intersection points between the edges of the square, is it possible to have O(n) external intersection points? (...
4
votes
2answers
66 views
Equal partition up to one integer
In the partition problem, the task is to partition $n$ given integers into two subsets $A$ and $B$ with equal sum. This problem is known to be NP-hard, but it becomes easy if the "equal sum" ...
0
votes
1answer
28 views
Do all the numbers belong to same slot in the Hashtable?
I was reading the CLRS. In the Hashing Chapter on page 262 a statement says: "For example, if we know that the
keys are random real numbers $k$ independently and uniformly distributed in the range $0 \...
0
votes
1answer
66 views
Doubt regarding Cantor's diagonalization argument [closed]
So, we use Cantor's diagonalization argument to prove that the Universal Turing Machine is not a decider.
I understand the overall argument but have a problem regarding one caveat mentioned in my ...
2
votes
2answers
31 views
How to show all false outputs in a circuit?
I have 3 input variables and the output for all 8 possible combinations is 0 (false). When making a circuit, how would I show this using gates or no gates at all? Thanks!
0
votes
0answers
22 views
Total number of integer solutions with constraints
Find the number of ways 5 dices can be rolled to get a sum of 25.
While solving this question, the way we solve it is $x_1+x_2+x_3+x_4+x_5$ $=25$ where $1<=x_i<=6$
So we replace $x_i$ ...
2
votes
1answer
29 views
How does one simulate continuous gravity using a discrete timestep?
While gravity in real life is continuous, computers are limited to discrete calculations.
Therefore, a seemingly correct projectile simulation inevitably drifts off.
For example:
...
0
votes
0answers
21 views
Prove that x and y in extended Euclid's algorithm won't overflow an Integer (If a,b <= 1e8, ax+by=gcd(a,b))
We are given a and b <= 1e8.
The extended Euclid's algorithm always finds a solution for ax+by=gcd(a,b) (assuming it exists) which can always be stored in an Int.
How to prove the x and y won't ...
1
vote
2answers
151 views
How can I make my algorithm more efficient or Is there a better way to solve the problem
Problem Statement: You are given an array/sequence of positive numbers $a_1,a_2,a_3,\cdots,a_n$ and you need to execute q queries on the array and in each query you ...
0
votes
1answer
38 views
Prove, a^2+b^2=c^2,there exists only 1 case such that a,b,c are consecutive non negative integers(3,4,5) [closed]
I want to prove, $a^2+b^2=c^2$,there exists only 1 case such that a,b,c are consecutive non-negative integers(3,4,5).
I have no clue to prove this lemma. Please help me to prove this lemma.
0
votes
1answer
52 views
Guess the number from its different base representations
Given a set of numbers in different representations (we don't know the value of the base in which we are representing) of bases, find the original number (in decimal representation) if it exists or ...
2
votes
1answer
43 views
Can most programs (except the IO part) be re-written as a sequence of matrix operations?
I got this idea recently. If we do not consider the data IO part of software, imagine the data is in the memory and we need to come out with some decision (which product to recommend to a user, how to ...
4
votes
0answers
44 views
Convex hull in a discrete space
I know some algorithms which compute the convex hull in a continuous space. Are there efficient algorithms to compute it in a discrete domain?
For example in 3D discrete space, given the blue points, ...
0
votes
2answers
42 views
prove that {$↔,⊕$} is incomplete set?
How do i prove that Is {$↔,⊕$} not a complete set ? I have no clue how to prove it .
0
votes
0answers
33 views
Minimise the maximum degree of a vertex in a connected graph
Given $N$ vertices and $M$ edges, how to create a connected graph so that I can minimize the maximum degree of every vertex. A vertex can have at most degree $N$ (self loop and other $N-1$ edges). ...
3
votes
1answer
107 views
Are these 2 equivalent?
Is ∀x∀y∀z[φ(x,y)∧p(y,z)->p(x,z)] equivalent to ∀x∀y∀z[φ(x,y)∧p(x,z)->p(y,z)] ?
The only thing I can think of is that this question can be answered if we show that ...
0
votes
0answers
26 views
Uncommon case in Arden's lemma $q_{2} = 1q_{2} \cup 0q_{2}$
I'm trying to get the regular expression of an automata but an state has a form that I don't know how to solve, the form on its simplest example is:
$$q_{2} = 1q_{2} \cup 0q_{2}$$
What's the ...
1
vote
1answer
27 views
Number of induced paths in an interval graph
Let $G$ be an interval graph. For any two vertices $u,v$ in $G$, how many induced paths are between them in $G$? Is it polynomial in terms of the number of vertices in $G$?
0
votes
0answers
29 views
Greedy algorithm for feedback vertex set / greedy algorithms vs local ratio in general
A greedy algorithm for finding a minimum feedback vertex set
is to pick and remove a vertex with minimum $w(v)/\delta_H(v)$, where $H$ is the current graph, until there are no more cycles left. (...
2
votes
4answers
138 views
how to calculate $2^{5000}$ mod 10 without calculator in fast way?
How is it possible to calculate $2^{5000}$ mod 10 without using a calculator in a fast way?
The result with calculator was 6.
0
votes
1answer
57 views
How to count all integers less than a given integer and having two contigous digits as $y$?
Suppose i have been given a number 54432 .How to count all numbers less than 54432 and having last two digits as 1 ? i.e all the numbers of form xxx11 and xxx11 < 54432 .Here x can be any digits ...
1
vote
0answers
33 views
Given a system in $\mathbb{F}_2$ in RREF, how do I find a solution of minimal norm?
I have a $12 \times 12$ (so not really large) system of linear equations in $\mathbb{F}_2$ which I got to RREF through the usual row reduction. Suppose the system has multiple solutions, and call the ...
2
votes
1answer
51 views
How do I minimize the cost of some algorithm that performs some operation on a list?
I stumbled upon this problem whilst studying the complexity of a simple algorithm. I used set-theoretic notation, but all the $S_i$'s are lists (I couldn't think of a better way to write the problem ...
1
vote
1answer
25 views
What easy algorithms are there for calculating products of cycle decompositions?
Here is the easy algorithm we are taught for adding two numbers in base-10 notation. We are taught this algorithm in first or second grade.
...
0
votes
0answers
48 views
What are necessity and sufficiency?
I was reading deadlock topic from Operating Systems book by Stallings. It states four pre requisites for deadlock:
Mutual exclusion
No preemption
Hold and wait
Circular wait
It then have following ...
2
votes
1answer
69 views
Steiner tree problem in graphs of diameter 3
I have an unweighted undirected graph $G(V, E)$ of diameter 3 and a subset $T\subseteq V$ of these vertices. I want to find the minimum tree $(V', E')$ that contains all vertices in $T$, minimizing ...
0
votes
1answer
44 views
find derivation trees for CFG
I need to draw the derivation tree for $1-2-(3-4)*5*6$ from the grammar below.
I want to know how many possible derivation trees are there from this grammar.
$$\begin{align}V_n&=\{expr,term,...
3
votes
1answer
101 views
Is is possible to determine if a given number is xor combination of some numbers?
I have been given a number Y which is ($a$ xor $b$ xor $c$ xor $d$ xor $e$ ) of some numbers ($a$,$b$,$c$,$d$,$e$) and another no X. Now i have to determine if X is a xor combination of ($a$,$b$,$c$,$...
1
vote
0answers
16 views
Do all Cellular Automata have some kind of information boundary? Can all Cellular Automata be modelled with the Bekenstein Bound?
Since they are discrete models, do they have some kind of information boundary? Can all Cellular Automata models be related to the Bekenstein Bound?
https://en.wikipedia.org/wiki/Bekenstein_bound
0
votes
1answer
68 views
why is discrete maths needed to understand algorithms?
I am new to algorithms. I need to know is it necessary to study discrete maths to understand algorithms. If so, why? In particular, is it necessary for understanding algorithms or is it only necessary ...
1
vote
0answers
37 views
How to solve 2 variable recursion?
T(m,n) = T(m-1,n) + T(floor(m/2), n-1)
Base conditions
T(m,n) = 1 when n = 0
T(m,n) = 0 when m < n
Edited: Below is the code for which I want to know the time complexity in terms of m and n.
<...
0
votes
0answers
28 views
Solving a modular equation programmatically
Consider that I've a mathematical equation of the form:
$$ (6+4\times x)\text{ } mod\text{ } 22 = 0 $$
How can I solve this modular equation by using a program, efficiently? By trial and error, one ...
