Questions tagged [discrete-mathematics]
Questions about discrete mathematics, the study of mathematical structures that are fundamentally discrete rather than continuous.
337
questions
1
vote
0answers
18 views
Determining Range of Current Node in Segment Tree
I was attempting, though failing quite miserably, to find some method of of determining the range of some node $n$. By range I mean an interval $[l,r]$ over the base array that is reachable by the sub-...
-1
votes
0answers
27 views
Using Expand, Guess, Verify to solve the following recurrence relation
Hello and thanks to those who bothered reading! I am trying to solve the following recurrence relation, $S(n) = S(n-1) + (2n-1)$, with the following base case: $S(1) = 1$.
I already used the ...
2
votes
1answer
30 views
Recurrence Relations
I am starting to learn recurrence relations in class and I am having issue with this example:
T(N) = 2N - 1 + T(N-1)
I am bit confused as to get the base case.
I'm sorry if this seems elementary, ...
1
vote
1answer
37 views
Amount of k-partitions of a number
I'm stuck on writing an algorithm for getting the amount of distinct partitions for a number $n$ with the partition being size $k$. It's important that there isn't any repetition in the partitions.
...
1
vote
1answer
27 views
How many snakes there can be in the “snakes and ladders” game?
How to calculate the maximum allowed number of snakes in the game of "snakes and ladders" from mathematical/algorithmic point of view assuming that there is a nxn board?
UPD: My thoughts are simple, ...
1
vote
1answer
13 views
Why there is no polynomially large sequence of polynomial large weights that derandomize the isolation lemma?
I was studying the paper Derandomizing the Isolation Lemma and Lower Bounds for Circuit Size by Arvind and Mukhopadhyay and came across the following claim (Observation 1.2 on page 3):
"More ...
1
vote
0answers
35 views
Chomsky Normal Form for context free grammars ambiguous/unambiguous properties?
My textbook states:
Finally, it must be stressed that the Chomsky normal form says nothing about ambiguity in general—a CFG in Chomsky normal form may or may not be ambiguous, just like we have for ...
0
votes
1answer
34 views
Number of permutations of set {1, 2, …, n} for which insertion sort will perform exactly n permutations
I have had the following problem at my last exam:
For how many permutations of set {1, 2, ..., n} where n > 2 will insertion sort (without guard element) perform exactly n comparisons.
My thinking ...
2
votes
1answer
47 views
Set which is easy to sample, but difficult to sample from its complement
Given a set $S \subseteq \{0,1\}^*$, the algorithm $A$ is a generator for $S$ if given $n$ random bits $x \in \{0,1\}^n$, $A$ generates an element of $S$ of size $n$, and $A$ can generate at least $\...
4
votes
1answer
82 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
1answer
31 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
57 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
93 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
15 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
317 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
53 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
48 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
39 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
74 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
72 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
103 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
104 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
97 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
25 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
78 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
68 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
35 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
33 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
22 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
156 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
43 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
63 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
45 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
49 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
34 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
29 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
39 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
142 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
58 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
35 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
26 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.
...
