All Questions
Tagged with discrete-mathematics computer-science
146
questions with no upvoted or accepted answers
8
votes
0
answers
314
views
Harmonic Numbers' Numerators Divisible by a Prime $p$
For a prime $p$, I am trying to determine the set of all $n$ for which the numerator of $H_n$ is divisible by $p$, with $H_n$ being the $n$'th harmonic number.
After going through a lot of literature, ...
- 1,022
4
votes
0
answers
61
views
How many dice rolls would it take, for an N-sided die, to guess with 99% probability that the number of sides is N?
Thought of this question today when I was looking at the dungeons and dragons dice.
- 61
3
votes
0
answers
49
views
Inequalities for sum of $k$ smallest degrees of a graph
As part of a homework assignment, I am doing a proof for a generalised variant of Karger's algorithm and am stuck at a particular step. I have proven that for a graph $G=(V,E)$ [writing $n=|V|$] with ...
- 55
3
votes
0
answers
124
views
Hyperplane Problem
Given $M$ points in $\mathbb{R}^{N}$, (where $M$ is larger than $N$) I was wondering if there is an approximation algorithm to find a hyperplane which goes through the origin and also intersects as ...
- 300
3
votes
0
answers
175
views
Why is this not a poset after adding zero?
The problem
Consider the following set for divisibility. {1, 2, 3, 4, 6, 8, 12, 16, 24, 32, 96}. If 0 is added, the divisibility relation set will no longer be a poset. Please ...
- 1,884
3
votes
0
answers
180
views
A Tricky Quetiones on Creative Algorithm in Graph
an agent is works between n producer and m consumers. i'th producer, generate $s_i$ candy and j'th consumer, consumes $b_j$ candy, in this year. for each candy that sales, agent get 1 dollar payoff. ...
- 127
2
votes
0
answers
76
views
the Ackermann function must be total and unique based on one specific list of rules
This is one following question based on one question I asked before.
In mcs.pdf, it has Problem 7.25 in p251(#259).
One version of the the Ackermann function $A:\mathbb{N}^2 \to \mathbb{N}$ is ...
- 416
2
votes
0
answers
52
views
Fastest way to get from one permutation to another (with distances between elements)
Imagine that I have some rows of shelves. Some shelves have items on them. Some may be empty. Imagine also that I have computed the shortest paths between each location (using Dijkstra's algorithm, ...
- 241
2
votes
1
answer
47
views
Are bits defined in a Boolean ring?
Premise: I'm not a mathematician, please be patient.
Anyway, if I consider the Galois field $GF(2)$ and two operations $+$ (inclusive or, also denoted with $\lor$) and $\neg$ (negation), where, given $...
- 21
2
votes
0
answers
59
views
How to solve these kind of Modular Arithmetics situations?
Helloo...
Im kinda dumb in Discrete Mathematics since I just started studying it currently and I'm trying to figure out studying material to get remainders from operations like $11^{14^{4578369}}\pmod ...
- 21
2
votes
1
answer
90
views
Minimum number of iterations required to introduce all n people to all $n$ in groups of size s?
I'm not sure if this is a well researched problem, I'm trying to think of a solution, it does not seem very obvious.
For eg: If $n = 6$ and $s = 3$, we can introduce everyone in $4$ iterations
...
- 121
2
votes
0
answers
89
views
Is there a context-free but non regular language, which still meets the requirements of the regular pumping lemma?
Is there a context-free but non regular language, which still meets the requirements of the regular pumping lemma?
Regular Pumping Lemma: $\exists n\in \mathbb{N}:\forall w \in L:{\mid
w \mid} \geq ...
- 1,197
2
votes
1
answer
855
views
How to figure out if a function is Big O, Big Ω, or Big θ of x?
I'm working on my last Discrete Mathematics online question set at the moment, and I've finished everything except this one problem on Big O. Essentially, it gives me 5 functions, and I have to figure ...
- 21
2
votes
0
answers
23
views
What is the term for "merging complementing data streams"
I'm merging 2 data streams together. One of them is precise, the other accurate. Excuse if this is obvious, but let me be sure I'm clear:
Accurate: Long term average is correct, but otherwise a ...
- 196
2
votes
1
answer
139
views
boolean algebra simplify using kmap
question: this is standar sop,try to simplify it using kmap
...
- 1,059