Questions tagged [discrete-mathematics]

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

449 questions
Filter by
Sorted by
Tagged with
410 views

Divide sequence of numbers from 1 to n into 2 groups with minimum difference

Let's say for some $n$ we have the sequence $1, 2, 3, \dots , n$, what we want with this sequence is to divide it in two sets such that each element of the sequence will be in only one set, and the ...
155 views

How to solve a knapsack problem using a modified version of DP?

Im having difficulties understanding how to solve the knapsack problem using dynamic programming, where v is value and w is the weight, where I can fill up to a maximum weight j for some Capacity_J: <...
56 views

Relation between $\sqrt{x^2+y^2}$ and $|x|+|y|$

I have a problem in which I was given $n$ points and an integer $k$, and I need to find the $k$ points that are the closest to origin. My approach is to find the distances from origin of all points ...
28 views

Event-based rather than flow-based systems?

This is a very vague question, so I don't know if people will understand it (I'm not even sure I understand the question myself), but here goes. Also, I'm not sure if this is really the right forum to ...
99 views

Can Hall's theorem be applied to scheduling problems?

If I have a scheduling problem, is it possible that Hall's theorem can be applied? I was thinking that the graph representation of the scheduling problem can be the preferences of the people / workers ...
60 views

Best complexity to find solutions to $x^2+y^2=z^2$

What is the algorithm with the best complexity that finds solutions in a given range to the equation $x^2+y^2=z^2$ ? The best i could do is to iterate through all $x$ and all $y$ and store $x^2+y^2$ ...
324 views

399 views

Algorithm to split $n$ distinct items into $k$ nonempty unlabelled subsets

The number of ways to split $n$ items into $k$ nonempty unlabelled subsets ($k<n$) is a Stirling number of the second kind.(https://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind) Is ...
314 views

$A, B$ --- enumerable sets, is $A \times B$ enumerable?

$A, B$ – enumerable sets, is $A \times B$ enumerable? I have some thoughts, that maybe it can be done using something like the proof of countability of $\mathbb{N} \times \mathbb{N}$, but I don't know ...
319 views

Number of "hamiltonian tours" from upper left to lower left corner of a grid graph?

I got the following as an interview question: Count the number of tours from the upper left corner to the lower left corner in a grid world where you can move in any manhattan direction. This is the ...
216 views

Prove that the union of multisets is idempotent

I am struggling with a proof from my discrete mathematics class. We have to prove that multiset union is idempotent, i.e. $M \sqcup M = M$, where $\sqcup$ denotes the union of multisets. We have ...
376 views

Solving recurrence relations using substitution followed by tree method/masters theorem

$T(n) = 4T(\sqrt n) + n$ First I substitute n = $2^k$: $T(2^k) = 4T(2^{k/2}) + 2^k$ Now I rename the above as follows: $S(k)=4S(k/2) + 2^k$ Now if I try to use tree method on this in the ...
35 views

is mappings optimization problems onto neural networks still a thing?

Is mappings optimization problems onto neural networks still a thing? I only found papers are written prior to 1999. These old papers mostly deal with Hopfield network, which i read is obsolete and ...
194 views

Complexity of exponential algorithm, optimised with memoization?

I was solving a problem, where one part of it was the following: "Given a m-sided dice ([1,m] values) that will be rolled n times, calculate the possibility that the total sum of rolls will be higher ...
2k views

Why an ARM processor with 32 bits address bus can address 4 billion different bytes?

Why an ARM processor with 32 bits address bus can address 4 billion different bytes? I know that $2^{32}$ is equal to about 4 billions, but shouldn't it be 4 billion bits and not bytes? Hence if I ...
149 views

199 views

What are sequences?

What are sequences? How do we denote the numbers inside them? I know that in terms of computer science, a sequence of items is an array.
719 views

How to prove with induction [duplicate]

So far I have learned how to write proofs by induction and it went fine until I got this recursive problem, which I'm not quite sure how to begin and how to prove that with induction. ...
475 views

How to measure the complexity of the discrete logarithm problem?

The answers to this question on Crypto Stack Exchange basically says that, to measure the complexity of the logarithm problem, we have to take the length of the number representing the size of the ...
Searching for efficient method to compute $a^n \bmod p$ for large numbers [duplicate]
I need an efficient algorithm with clear steps to compute $a^n \bmod p$ when $n$ is large enough and $p$ also. I'm looking for something equivalent to the built-in ...