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 votes
0 answers
18 views

Modal logic S4 system

How to prove in S4 system modal logic that ◇□◇x->◇x? Probably i only need to show that ◇□x->x Any help will be great?
user avatar
1 vote
0 answers
43 views

Distinguishing two distributions with f-divergence

The statistical distance (SD) has been widely used as a 'measure' of the closeness of two distributions $D_1$ and $D_1$. Suppose that the statistical distance (here, total variation with $\ell_1$ norm)...
user avatar
  • 11
1 vote
1 answer
19 views

Decomposing large bit mult or exp into smaller bit operations

Imagine a machine that can only hold N-bit values (N-bit uint). The machine can also calculate the 2N-bit result of two operations: mult, exp. The 2N-bit result is stored across 2 N-bit values (high/...
user avatar
  • 11
0 votes
2 answers
91 views

Sum of average of all subarrays

Suppose there is an integer array $a_1,a_2,...,a_n$. Calculate the sum of average of all subarrays. For example, the sum of average of all subarrays of array $[1,3,5]$ is $1+3+5+\frac{1+3}{2}+\frac{3+...
user avatar
0 votes
0 answers
16 views

What Basic (pre-discrete maths course) areas to focus on - and what resources would be recommended?

To cut a long story short, I'm a mature CS student with fairly rusty maths skills, going into my second last year of my degree. I had studied maths to the sort of decent-ish high school level you'd ...
user avatar
  • 1
0 votes
1 answer
40 views

Walk from vertex u to vertex v on complete graph, formula for number of walks of length k

Complete graph with n vertices. Walk from vertex u to vertex v of length k. I don't understand how the number of walks between the two of length k is $n^{k-1}$ I've tried this formula on an example ...
user avatar
0 votes
1 answer
50 views

equivalency of some facts in $O$ notation

I misunderstanding about some logarithm property in algorithm course: is it correct that we say following three term is equivalent? $O(\log a + \log b)$ $O(\log (ab))$ $O(\log (a+b))$
user avatar
0 votes
0 answers
28 views

Finding Sum(F(i)) where F(i) = min(⌈ Ai / B1 ⌉ * C1, ⌈ Ai / B2 ⌉ * C2, ⌈ Ai / B3 ⌉ * C3, .... ,⌈ Ai / Bm ⌉ * Cm)

Given three arrays A, B, and C of size n, m, and m respectively (1-based indexed). A function F(i) is defined as - F(i) = minimum_of(⌈ Ai / B1 ⌉ * C1 , ⌈ Ai / B2 ⌉ * C2 , ⌈ Ai / B3 ⌉ * C3 , .... , ⌈ ...
user avatar
0 votes
0 answers
41 views

The relationship between types of registers / feedback functions and de Bruijn sequences, and how these feedback functions are created

I have been learning about de Bruijn sequences recently, and have a decent sense what they are. There seem to be 3 or 4 primary methods for generating de Bruijn sequences: Feedback functions/...
user avatar
  • 1,871
1 vote
0 answers
22 views

How do you generate lots of binary de Bruijn sequences (somewhat small, such as less than 100 bits)?

I have been learning about de Bruijn sequences recently. I looked at this C library on Greedy algorithms, and took what I learned to make this JavaScript version, which tries to make as many de Bruijn ...
user avatar
  • 1,871
1 vote
1 answer
38 views

What is a de Bruijn sequence exactly?

I just discovered the term "de Bruijn sequence", but don't quite follow what it means exactly (or how de Bruijn is pronounced :), "brown" I guess). There are two good resources I ...
user avatar
  • 1,871
0 votes
1 answer
33 views

Mathematical Induction vs Strong Induction

In Rosen's book Discrete Mathematics and Its Applications, 8th Edition it is mentioned that: You may be surprised that mathematical induction and strong induction are equivalent. That is, each can ...
user avatar
  • 319
0 votes
0 answers
19 views

Can you recommend some materials on Turing Machine?

I need exercises with answers to practice building Turing machines. Books, online resources etc. Can anyone recommend something?
user avatar
1 vote
1 answer
50 views

3-colouring with a bounded amount of colors

The topic of 3-colouring is often talked about, but what happens if we limit the amount of times we can use one color? Take a graph $G=(V,E)$ with $k$ being the number of vertices, is it possible for ...
user avatar
  • 49
2 votes
1 answer
29 views

Satisfiability of bounded assignment of input variables to CNF formula

Consider a CNF formula $F$ such that all the literals in every clause must be negative ( here is an example : $F$ = ($\bar{x_{1}}$ $\wedge$ $\bar{x_{2}}$) $\vee$ ($\bar{x_{3}}$ $\wedge$ $\bar{x_{4}}$ $...
user avatar
  • 49
0 votes
0 answers
24 views

Graph with constant edge connectivity that remains connected after edge removals

I have an undirected graph $(V, E)$ with constast edge connectivity $\lambda$. Each edge is sampled independently with probability $min\{1,\frac{c \ln n}{\lambda}\}$ for some $c > 0$. I need to ...
user avatar
  • 149
2 votes
0 answers
27 views

Proving existence of sinkless orientation on graph with minimum degree 2

I am given a graph of minimum degree at least 2 (not necessairly regular). I want to prove that there is a way to orient the edges of G such that each node of G has at least one out-going edge. As a ...
user avatar
  • 149
1 vote
1 answer
31 views

Trivial vertex cover in regular graph is 2-approximation Proof

I need to show that in any regular graph, taking all nodes gives a 2-approximation vertex cover. My attempt: I am proving that every $k$-regular graph can be reduced to a 2-regular fully connected ...
user avatar
  • 149
1 vote
0 answers
29 views

How do I get the number of cycles in a grid. Is there a formula?

So does anyone know the formula in order to get the number of cycles, I'm not directly asking for the answer but at least someone guides me on how to get a cycle given a grid such as an image above.
user avatar
  • 11
0 votes
1 answer
40 views

Prove there is a matching of size n/2 on a graph with 2n vertices each of degree n

Given underirected $n$-regular graph with $2n$ nodes, I am asked to show it has a matching of size $n/2$. My attempt: At each step I will also remove the edge from the graph that I am adding to the ...
user avatar
  • 149
-3 votes
1 answer
40 views

Recursion problem T(n)=3T(n/3)+3n

I just need help solving this problem. I know I'm supposed to be using the Master's Theorem but I don't know where to start
user avatar
1 vote
0 answers
28 views

Find sets which are subsets of the given search set?

The problem is the following: You are given a collection( set, list, whatever ) C of sets, and you are given a search set S. We want to find among all sets in C the ones which are subsets of S. Hence, ...
user avatar
  • 121
0 votes
2 answers
64 views

Is there a quantifier more powerful than the other to determine FOL connector?

So basically we have 2 types of quantifier in first order logic, they are universal quantifier and existential quantifier. Usually we use implies connector(->) when we have universal quantifier in ...
user avatar
1 vote
3 answers
95 views

Solve the recurrence $T\left(n\right)\:=\:3T\left(n-1\right)\:+\:3n^2$

I am trying to solve the recurrence $T\left(n\right)\:=\:3T\left(n-1\right)\:+\:3n^2$ I tried method I saw but I do not fully understand which looks like: $T\left(n-1\right)\:=\:3T\left(n-2\right)\:+\:...
user avatar
3 votes
1 answer
103 views

Analytic combinatorics and less-precise running times

Analytic combinatorics and concrete mathematics are the mathematics of asymptotic counting, and they draw from combinatorics, analysis, and probability. These techniques have been applied to the ...
user avatar
  • 315
4 votes
1 answer
59 views

Copying a linked list with additional arrows from each node

Statement Consider the following modified node structure for the linked list: struct Node { int value; Node* next; Node* random; } The ...
user avatar
2 votes
1 answer
1k views

Can we solve a "very" exponential recurrence?

Can we solve this recurrence relation : $T_n = \exp(T_{n-1})$ ? Thanks!
user avatar
  • 29
1 vote
3 answers
126 views

Θ, O and Ω, and how they relate to each other as subsets

I am trying to understand how $\Theta(n)$, $O(n)$, and $\Omega(n)$ relate to each other as sets and want to make sure I'm on the right track. I get that $Θ(n) \subseteq O(n)$ since $Θ(n)$ is stronger ...
user avatar
1 vote
1 answer
103 views

bellman ford and one surprizing fact

I ran into a very surprising local contest problem. after finishing bellman ford algorithm, if we continue to updating distance and distance of one vertex v being updated, then v is on negative cycle....
user avatar
0 votes
0 answers
31 views

How to generate supersets from a finite number of subsets efficiently

Let $F$ be a set, for instance $\{a,b,c,d,e \}$. Suppose I have a set of subsets of cardinality two obtained from $F$: $ ${ a,b },$\{b,c\},${a,d} I want to create every possible set of cardinality ...
user avatar
  • 111
0 votes
1 answer
41 views

How to evaluate all the binary sequences, generated from $2^{100}$ for finding all the sequeces which contain minimum $10$ zeros?

Suppose I have a set of $2^{n}$ number of binary sequences. And I have to select only those sequences which contain a minimum ${P}$ number of $0$ in it. For example, please consider the below one Eg. ...
user avatar
  • 168
5 votes
0 answers
127 views

Optimization on hypergraph "refinements"

Given a hypergraph $H = (V, E)$, call $H' = (V, E')$ a refinement of $H$ iff there exists a partition $p : E' \to I$ (where $I$ is an arbitrary index set) such that $E = \{\bigcup_{x \in p^{-1}(i)} x \...
user avatar
  • 364
2 votes
1 answer
94 views

Asymptotic height of d-ary heap

I know that the height of a $d$-ary heap on $n$ nodes is $\lceil (\log_d (n(d-1) + 1) - 1)\rceil$, but I was wondering how to justify that that's $\Theta(\log_d n)$? I know the definition of $\Theta, ...
user avatar
1 vote
1 answer
24 views

Is $\{\emptyset,a,\epsilon\}$ an algebraic structure with respect to $+$?

Let $R = \{\emptyset,a,\epsilon\}$ (the elements here are regular expressions) and let $+$ be the or operation, which can be applied over the regular expressions of $R$. Is $(R,+)$ some kind of an ...
user avatar
1 vote
0 answers
23 views

Finding square root of a gram matrix over the integers [closed]

Suppose that matrix A is a symmetric positive definite matrix over the integers, i.e., $A \in Z^{n\times n}$, if B is a matrix over the real numbers, it is not difficult to find B such that $A = B \...
user avatar
8 votes
11 answers
4k views

Real life examples of *zero* weight edges in graphs

The meaning of edges with zero weight in a weighted graph questions me for a long time, and I even asked a related question previously. Yet, when I recently read here a question on real life example ...
user avatar
18 votes
6 answers
3k views

Real life examples of negative weight edges in graphs

I am unable to relate to any real life examples of negative weight edges in graphs. Distances between cities cannot be negative. Time taken to travel from one point to another cannot be negative. ...
user avatar
  • 319
5 votes
0 answers
118 views

discrete optimization problem with a matrix inverse

I'm trying to solve this discrete optimization problem:$\newcommand{\I}{\mathcal{I}}\newcommand{\R}{\mathbb{R}}$ $$\max_{|\I| \le k} f(\I) \qquad\text{where}\; f(\I) :=x_{\I}^{\top} (\Sigma_{\I})^{-1} ...
user avatar
0 votes
1 answer
59 views

How can it be proved that two different kinds of dfs unequivocally define a unique tree?

How can it be proved that two different kinds of dfs ( for example let call them inorder and postorder) unequivocally define a ...
user avatar
0 votes
0 answers
35 views

Why is “For all the simple things you have done to me, there exists one thing that makes me happy” FALSE? Use nested quantifiers to prove your point

I've done my due dilligence and tried to answer this question using every resource I could get. KhanAcademy, NesoAcademy, and Rosen's Discrete Mathematics book. I still can't wrap my head around it. ...
user avatar
  • 1
0 votes
0 answers
48 views

Finding the shortest path with this algorithm

This is a homework question. We want to find the shortest $s$-$t$ path in an undirected weighted graph $G = (V, E)$ with capacities $c_e$ for each edge and positive weights. Let $S'$ be the set of all ...
user avatar
  • 115
0 votes
1 answer
20 views

Polytime Mapping Reduction from Language A to Language A (identity)

How would I create a polytime mapping reduction to prove A ≤p A for any language A. I was thinking to assume A is in P to start. For every 𝑥: 𝑥∈𝐴 iff 𝑓(𝑥)∈𝐴. But I am not sure what to do from ...
user avatar
1 vote
0 answers
32 views

Linear programming and network flow

I would like some hint in this homework question. I have to write the max-flow problem (with souce $s$ and sink $t$) as a linear program. I have to do this by defining variables on each $s - t$ path, ...
user avatar
1 vote
0 answers
38 views

Finding a path that passes through a given vertex

This is a homework question. Let $G = (V, E)$ be an undirected graph. Let $u, v, w \in V$, find a path from $u$ to $w$ that passes through $v$. I know that I can solve this by running BFS on $u$ and ...
user avatar
1 vote
1 answer
112 views

How to get the highest score in this game?

I would like some advice in this homework question. There is a three players game, in which each player ($A, B$, and $C$) is given a $n$-length array of integer values. There are $n$ rounds in this ...
user avatar
  • 115
0 votes
0 answers
10 views

Discrete Event Simulation: modeling entity arrivals

I have seen the stochastic introduction of simulated "entities" (typically queuing for service) via stochastic inter-arrival times. Specifically, the times between arrivals are simulated ...
user avatar
  • 101
0 votes
0 answers
77 views

Longest sequence of 1s in a binary matrix

I would like a hint for this homework question. The problem is to come up with a divide and conquer solution for finding the maximum sequence of 1s in a given a binary matrix of order $n$. The ...
user avatar
1 vote
1 answer
42 views

Assigning balls to bins with constraints

Let $S= \{ b_{11}, b_{12}, b_{21}, b_{22}, b_{31}, b_{32},\dots, b_{n1}, b_{n2} \}$ be a set of $2n$ balls grouped in $n$ pairs, and $T = \{ B_1, B_2, \dots, B_m\}$ be a set of $m$ bins with ...
user avatar
  • 115
2 votes
0 answers
63 views

Variation of the gas station problem

Consider an acylicic directed weighted graph in which the nodes represent cities and the weights represent the amount of fuel a car spends when going through that edge. At each city $u$ the car ...
user avatar
0 votes
0 answers
39 views

Finding sequences in a binary matrix with recursion

Given a binary square matrix of order $n$. Can the problem of finding the longest sequence of 1's (horizontal or vertical) be solved with recursion? I know how to solve the problem without recursion ...
user avatar
  • 115

1
2 3 4 5
10