Questions tagged [discrete-mathematics]

Questions about discrete mathematics, the study of mathematical structures that are fundamentally discrete rather than continuous.

319 questions
Filter by
Sorted by
Tagged with
18 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 ...
12 views

Using a PDA, show that ( x * y ) + x is a valid string

Using a PDA, show that ( x * y ) + x is a valid string. im having trouble with part C
23 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 ...
13 views

Recursive definition character counter

This is my definition for part 1 (in latex form) \begin{alignat*}{2} \text{Base Case }& &&\text{ if } \mathtt{ones}(\varepsilon) = 0 \qquad \mbox{ ($\varepsilon$ is the empty ...
54 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 ...
38 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? (...
17 views

Array manipulation and number theory [closed]

How do I rearrange a given array such that the GCD of all the adjacent elements is always 1?
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" ...