Questions tagged [discrete-mathematics]
Questions about discrete mathematics, the study of mathematical structures that are fundamentally discrete rather than continuous.
297
questions
0
votes
0answers
19 views
Efficient method of representing bijections
Let's say I have to map the elements $\{1,2,3,4,5\}$ to $\{a,b,c,d,e\}$ as follows.
$\{ \space \{\space(1,a) , (2,b) , (3,c)\space\} \space , \space \{\space(1,a) , (2,c) , (3,b)\space \} \space \} \...
-2
votes
0answers
18 views
computation of a hypergeometric sum [closed]
Let $q,\ell, M \in \mathbb{N}$
I am not familiar with mathematica, maple or mathlab to, at least see what this sum suppose to be. I am wondering if someone can compute this sum
$$
\sum_{m=0}^q\binom{q-...
2
votes
4answers
111 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.
1
vote
1answer
41 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
31 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
44 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
24 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
39 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
61 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
40 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
88 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
14 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
63 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
24 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 ...
1
vote
1answer
19 views
How to calculate the number of invalid strings given a constraint system on alphabet, word blacklist, and string length
If I have the following system, I am wondering how to calculate the number of valid strings it contains.
The system is something like this, which can have arbitrary variations.
Only consists of an ...
1
vote
1answer
37 views
Randomized Algorithm in $O(d)$ for Solving Unknown Degree $d$ Polynomial Function Using an Erroneous Oracle
Consider the field $GF(p)$, where $p$ is a prime number. If there is a function $f: GF_p \times GF_p \rightarrow GF_p$ which has an unknown degree $d$ polynomial, with $1 < d < p / 4$.
Although ...
4
votes
1answer
62 views
Prove the probability of which a hash function is collision-free
Suppose $H = \{h_1, ..., h_T\}$ be a family of pairwise independent hash functions mapping $\{0, 1\}^n$ to $\{0, 1\}^{n/2}$. Let $M = \frac{2^{n/4}}{10}$ and let $x_1, ..., x_M$ be any M distinct ...
1
vote
1answer
39 views
Solve the recurrence $a_n - 3a_{n-1} + 2a_{n-2} = 6 \cdot 2^n$
Consider the recurrence
$$ a_n - 3a_{n-1} + 2a_{n-2} = 6 \cdot 2^n. $$
I tried to solve this as follows. First, I found the homogeneous solution:
$$
a_n^{(h)} = r^2 - 3r + 2r \\
(r-2)(r-1) = 0 \\
...
0
votes
1answer
26 views
Recursive definition for the length of a string?
I found a couple of answers online but I don't quite understand why the answer is right:
The length of a string is:
If a string has no characters, then its length is 0.
Otherwise, the length of the ...
0
votes
0answers
15 views
Can we apply master theorem on this? [duplicate]
I'm very confused. It's my first time here . Idk how to ask question here . Sorry if I made some mistake or anything .
T(n) = 2T(n/2)+ n/logn
1
vote
0answers
45 views
The maximum number of uniquely intersected elements from the all possible intersection scenarios among the sets in a two-column matrix
Let us define a $n \times 2$ matrix M consisting of integer sets, such
that the first column consists of the so-called intersecting sets,
and the second column ...
0
votes
0answers
12 views
How to understand DFA's and how to understand how to construct them based on a given regular language? [duplicate]
I have practiced DFA's for an upcoming test and I haven't been able to grasp how to construct more difficult DFA's. An example would be this question : Construct a deterministic finite state automata ...
4
votes
1answer
267 views
Irregularity of language of prefixes of decimal expansion of pi
Let $L_{\pi}$ be the language consisting of prefixes of the decimal expansion of $\pi$:
$$L_\pi = \{3, 31, 314, 3141, 31415, 314159, \ldots\}.$$
Prove that Lπ is not DFA-recognizable. You may use the ...
1
vote
1answer
23 views
I don't understand what this regular language is asking for? Find a grammar for L(G) = {w || w | is odd,∑ = (0, 1) }
I don't understand what this regular language is asking for? Find a grammar for L(G) = {w || w | is odd,∑ = (0, 1) }. What does the " || " mean I know a single " | " means or.
-1
votes
1answer
39 views
Regular expression for all possible strings. Does the Kleene star distribute over each element. (0+1)* = 0* + 1*?
Regular expression for all possible strings. Does the Kleene star distribute over each element. Is this true? (0+1)* = (0* + 1*) ?
1
vote
0answers
56 views
Inductive proof on Quicksort with Explicit Stacking
Prove by induction that if Quicksort with Explicit Stacking is modified so that the end-points of the larger sublist are stacked, and the other sublist is sorted first, then the maximum stack size is $...
5
votes
2answers
84 views
Finding the cheapest buy order with fixed inflation for each product
Let's say we have a set of products $M$, a total of $|M|=n$ that we want to buy. However, we can only buy one product at a time, so that we need a total of $n$ time-units to buy all items.
Each ...
5
votes
1answer
127 views
How does treewidth behave under graph minor operations?
It is a well-known fact that for any minor H of a graph G (commonly written as $H \leq_m G$), the treewidth of H is smaller than or equal to that of G.
Minors of a graph are created through the ...
0
votes
1answer
294 views
Find the Pumping Length for Language L of (2+3k) a's or (10+12k) b's
The following question on the theory of computation is GATE 2019 CS question 24:
For $Σ = \{a, b\}$, let us consider the regular language: $$L = \{x \mid
x = a^{2+3k} \text{ or } x = b^{10+12k}, k ...
2
votes
2answers
205 views
Finding the maximum of a bitonic sequence
Given to us is an array $B[1],\ldots,B[n]$ as input, which satisfies the following property: there exists a special index $i^* ∈ \{1, \dots , n\}$ such that $$B[1] < B[2] < \dots < B[i^*− 1] &...
2
votes
1answer
28 views
Is it possible to denote “any single alphabet symbol” in an FSA state diagram?
This is a possible duplicate of the following (but not sure it answered my question):
Is it possible to support .(any symbol) or \d, \w, \W in DFA
My professor is asking for a finite automata state ...
-1
votes
1answer
36 views
Can someone point out why these directed graphs aren't equivalence relations?
As far as I can tell, these two directed graphs are reflexive, symmetric and transitive.
3
votes
0answers
79 views
Polynomial time algorithms for rank 1 elliptic curves over Q
As an outsider, it sounds like a lot of progress has been made on understanding rank 1 elliptic curves. Much of the BSD conjecture is known for rank 1, and Heegner points provide a way to calculate a ...
-4
votes
1answer
58 views
Is ∅ ∈ {{∅}} true? [closed]
I learned that the empty set is not an element of every set unless the empty set is explicitly included in the set like {∅}, so I believe it is false because it is not ∅ ∈ {∅}.
3
votes
1answer
66 views
Matrix Representation for logical gates?
I have been trying to find if there are other matrix type representations logical circuits, in the example below, $$\begin{bmatrix} 1 & 0\\ 1 & 1\\ \end{bmatrix} \equiv \, \, \Rightarrow$$ ...
0
votes
1answer
44 views
How to “logically” solve boolean logic
I came across of one excellent book Elements of Computing Systems and in chapter 1 we need to implement the "primitive" logic gates (for example: Not, And, Or, Xor, Mux, etc) based on a Nand gate.
...
0
votes
0answers
9 views
Most probable inputs assignment in Gaussian process
Given
A Guassian process $w(\mu^*,\Sigma^*)$
$n$ observations of the output
And $n$ potential inputs.
But the assignment of the inputs to the observations is unknown. The goal is to find a inputs-...
0
votes
0answers
16 views
Possible Network Flow “Cuts”?
The possibilities are:
always full and always crossing. (True, per chart)
always full and sometimes crossing. (True, per chart)
always full and never crossing. (False?)
sometimes full and always ...
1
vote
0answers
18 views
Relation between deficiency and color class parity of graphs
Let $G$ be a graph with total vertices $|V(G)|$. Let the maximum degree of the graph be $\Delta$. Let us assume the graph is total colourable( no adjacent vertices, adjacent edges and an edge and its ...
0
votes
1answer
39 views
invite 12 person from 24 that we have 6 men and 6 womens [closed]
i had a question and its
"A man has 5 female and 7 male friends and his wife has 7 female and 5 male friends. In how many ways can they invite 6 males and 6 females if husband and wife are to invite ...
2
votes
1answer
45 views
Compute the general time complexity of a merge sort algorithm with specified complexity of the merge process
The problem was from an exam, I spent much time wrapping my head up around this kind of problems, so I decided to ask for help ;(
Problem:
We implement a merge sort algorithm to sort $n$ items. The ...
1
vote
1answer
1k views
Define a DFA that accepts all even length binary strings that don't contain the substring “111”?
I think I have worked out a DFA that doesn't accept the substring "111," but I don't know how to account for accepting even length strings. Here is what I have so far. Any help would be greatly ...
1
vote
1answer
396 views
How to solve F(n)=F(n-1)+F(n-2)+f(n) recursive function?
Like in the title the following equation:
F(n)=F(n-1)+F(n-2)+f(n) F(0)=0, F(1)=1
...
2
votes
2answers
126 views
Prove that the number of edges is at least twice the number of vertices
I need to prove that
In a simple graph $G$, if all the $n$ vertices have a degree of at least $4$, then the number of edges is at least twice the number of vertices.
I already know that $\deg(n) = ...
2
votes
1answer
52 views
Alternate proof of the Caro-Wei theorem for lower bounding the independence number
Let $G$ be a graph on $n$ vertices whose degree sequence is $d_1,d_2,...,d_n$. Let $\alpha(G)$ denote the size of maximum independent set of $G$, i.e., the size of a maximum subset of vertices of $G$ ...
0
votes
0answers
24 views
Example of a language with linear NFA, but exponential DFA [duplicate]
So I read that regex engines use NFAs instead of DFA because f size blowup for dfas. I want to get an example of a language for which the minimum DFA has an exponential number of states but it,s NFA ...
1
vote
1answer
30 views
How to calculate $\sum_{i=1}^n \mu^2(i)$ in less than $O(n)$'s time
To go with $O(n)$, we can use the linear sieve according to that $\mu(n)$ is multiplicative. But it seems that we don't have to work each $\mu(n)$ out and accumulate them together, because I only want ...
2
votes
1answer
26 views
What's the connection between the two “Fast Walsh Transform”?
First Let's take a look at the convolution $\displaystyle C _ { i } = \sum _ { j \oplus k = i } A _ { j } * B _ { k }$, and the $\oplus$represents any boolean operation. And we are able to evaluate $C$...
2
votes
1answer
24 views
Design an algorithm for efficiently computing the k smallest numbers of the form a+b*sqrt(2)
Full question: Numbers of the form $a+b\sqrt{q}$, where $a$ and $b$ are nonnegative integers, and $q$ is an integer which is not he square of another integer, have special properties, e.g. they are ...
