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
1answer
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 ...
2
votes
0answers
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: <...
1
vote
1answer
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 ...
0
votes
0answers
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 ...
2
votes
1answer
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 ...
1
vote
1answer
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$ ...
2
votes
2answers
324 views

Polynomial bound on sum of strings

I am struggling with the following problem: Given a set of finite binary strings $S=\{s_1,\ldots,s_k\}$, we say that a string $u$ is a concatenation over $S$ if it is equal to $s_{i_{1}} s_{i_{2}} \...
2
votes
0answers
302 views

A road-map for mathematics needed in CS? [closed]

Before asking my question, I have to give some background about myself. I live in Iraq and this made my education a total disaster. My middle/high school math skills are not that great and I never ...
2
votes
4answers
1k views

Is it necessary to learn how to prove Mathematical theorems as a CS Student? [closed]

I've just started my undergraduate course and have tried my hands on MIT's OpenCourseWare on Discrete Math on Logic and Proofs. There was a particular question asking to prove Cantor's Theorem: ...
2
votes
1answer
49 views

Simple discrete math problem: A and B in 3CNF

I need to write (A and B) in 3CNF, and for whatever reason, I can only come up with (A or B) in 3CNF (A OR B OR X) AND (NOT(X) OR A OR B). Any help is greatly appreciated!
1
vote
1answer
1k views

Question on Predicates and Quantifiers

I am reading from "Discrete Mathematics and Its applications" by Kenneth H. Rosen, 7th edition. Consider the highlighted part in the following example taken from the same book: Question Use ...
1
vote
1answer
53 views

Determine whether a variable has positive influence in Boolean function

Given a Boolean function $f$ over the set of variables $X =\{ x_1,...,x_n \}$, the influence of $x_i$ is defined as the probability that changing only $x_i$ on random input changes $f$. Given a ...
0
votes
0answers
88 views

Existence of perfect hash function

In their original paper, Storing a sparse table with O(1) worst case access time (Fredman, Kolmos and Szemeredi, Proc. FOCS '82, IEEE, 1982), the authors show that a perfect hash function must exist, ...
3
votes
1answer
231 views

How would one use "BUT" logic in a ternary logic computer in a practical way?

Using three valued logic one can define a multitude of ternary operations. When dealing with 5:3:1[1] operations, its very easy to see how ...
2
votes
1answer
748 views

Solving T(n) = 2T(n/3) + 2 T(2n/3) + n

The goal is to get big $\Theta$ for $$T(n) = 2T\left(\frac{n}{3}\right) + 2T\left(\frac{2n}{3}\right)+n$$ I tried two approaches, but both failed: Recursion tree. We see that $$\begin{align} \sum_{...
0
votes
1answer
65 views

How can I calculate the new quotient if I came to know divisor is increased by one?

If I have two number consider a and b and let their division quotient is c. I know the value of c but I don't know either value of divided(a) or divisor(b). If I came to know the value of divisor is ...
1
vote
1answer
106 views

What should be the way to design code for such a situation?

I have a graph as given below: Let us assume one node as transmitter and another as receiver. We need to transfer particles in every time slot constrained by maximum particles N and minimum 0. The ...
0
votes
1answer
1k views

The meaning of symbols [closed]

What does the following symbols or expression mean?
0
votes
0answers
26 views

Arranging cubes in bins to minimize expected variation ratio

I am working on an optimization problem. Let's say we have a grid of bins where solid metal cubes could be placed. We have a number of colored metal cubes to be arranged in the bins. Each of these ...
1
vote
2answers
144 views

minimize sum of primes with a lower bound on product

I can't quite figure out an algorithm for this: Given some integer n, what subset of the primes (so no repeats) would yield the lowest possible sum if their product is at least n? Example: 6 -> 2*3, ...
1
vote
1answer
655 views

ignoring overflow in two's complement addition of numbers with different signs[specific case]

I understand the rule says that overflow cannot happen for two's complement addition of numbers with different signs, but do not understand why this specific case does not cause overflow: ...
1
vote
1answer
88 views

Broadcasting on a dynamic grid

We are given a $n \times n$ grid, where each node can maintain a single "active" edge with one of its 4 neighbors at each time step. The active edge of each node changes periodically clockwise or ...
2
votes
1answer
704 views

DPLL algorithm: OLR vs. PLR

Can someone please show me examples of what is the difference between OLR (one literal rule) and PLR (pure literal rule) using the DPLL algorithm?
-2
votes
1answer
32 views

What's the complexity of running an algorithm that searches over all cuts on a network and returns the minimum?

It's a question of a problem set. If I search for all possible cuts on a network graph and return the minimum, (so it will be equal to max flow), what will be the complexity of running this?
0
votes
1answer
47 views

A simple Query regarding Modulus Notation?

Aren't these two Modulus equations exactly the same (seems obvious): $ X = 0 \ (mod\ B) $ $ X = B \ (mod\ B) $ The reason for the query is the following NP Complete Problem from Garey and Jhonson: ...
2
votes
1answer
108 views

Sum of 2^Pi mod 1000000007 for all i where Pi is sum of numbers in ith subset of a set X [closed]

I am stuck on a problem in which I have to print sum of 2Pi mod 1000000007 for all i where Pi is sum of numbers in ith subset of a set X. Length of set can be upto 100000. Value of element in the ...
2
votes
1answer
291 views

The Height of subtree in Heap

In order to find the recurrence function of The Height in Heap, the following figure is drawn. Question 1: How can we compute the height if Right subtree in form of Log in base 3, and why do we have ...
2
votes
1answer
355 views

How to find the number of discrete states possible by current computers?

In his famous article, "Computing Machinery and Intelligence", Allan Turing talks about discrete-state machines and the largeness of the number of states provided by that time "state-of-the-art" ...
1
vote
1answer
92 views

Numbering of computable functions

Is there a numbering (not Gödel numbering) of all computable functions $U(p, x)$, such that the set of numbers of functions defined in zero is exactly the set of even numbers. More formally: $I = \{p,\...
1
vote
1answer
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 ...
3
votes
2answers
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 ...
3
votes
1answer
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 ...
2
votes
0answers
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 ...
1
vote
1answer
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 ...
2
votes
0answers
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 ...
0
votes
0answers
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 ...
1
vote
3answers
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 ...
4
votes
1answer
149 views

how to prove the following is a bijection?

I have a translation function which translates $\lambda$-terms to another representation let me call it $G_\lambda$, as follows. $\chi(x)$ $=$ $ X^2$ if $ x \notin \Gamma$ $\...
0
votes
1answer
64 views

Optimal way for the remainder [closed]

I want to know if for any base the most significant digit is 1 or not. Here is the code: ...
3
votes
0answers
200 views

$\lambda$-terms equal modulo $\alpha$-renaming, is this an equivalence relation?

Want to clarify few things. It is said that two $\lambda$-terms are equal up to renaming of bound variables, such as $\lambda x.x$ equals $\lambda y.y$, so I think it is a relation actually, about ...
1
vote
1answer
154 views

Is the Backus-Naur Form a type 2 grammar? If So why?

I understand that the Backus-Naur Form is utilized to assess and specify type 2 grammar, but is it in itself a form of type 2 grammar?
2
votes
1answer
91 views

Prove that every undirected connected graph with $|V | > 2$ results in a connected graph if two vertices removed.. [duplicate]

How do I go about proving this? Prove that every undirected connected graph with $|V | > 2$ has at least two vertices such that if one or both are removed (along with their incident edges) the ...
2
votes
0answers
71 views

TCS/Math/Quantum Information Advice [closed]

I am currently a high school 12th grader and am very interested in computer theory and pure mathematics. I also have a strong interest in astronomy and a desire to study quantum information. However,...
-1
votes
1answer
106 views

Discrete Math/Logic Problem used in Computer Science Class: Who Robbed the National Bank?

The following question is supposed to give you insight on how to maintain logic when making programs. Please be open minded as this may not look like a Computer Science Problem, but it definitely ...
2
votes
2answers
46 views

Growing a set given constraints

I am trying to solve the following: Given a set $S_0$, find min $|S|$ where $S_0 \subseteq S$ subject to: $\forall s \in S$ $\exists$ $s_a, s_b \in S $ $|$ $ ( s_a \neq s, s_b\neq s ) \land ( s = ...
0
votes
1answer
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.
2
votes
2answers
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. ...
9
votes
1answer
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 ...
3
votes
1answer
647 views

Relation between Lattice and Boolean Algebra

In discrete math, I have read that lattice is a generalized form of boolean lattice. But those places where boolean algebra is mentioned, they don't tell about lattices (digital logic, binary,...). ...
1
vote
2answers
104 views

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

1
5
6
7 8 9