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