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

How do you prove that this tree path calculation function works, from first principles mathematically?

I recently got an amazing answer to an SO question about how to calculate the path in a tree to an item, where you give it the corresponding array index, and the ...
0
votes
0answers
20 views

Mathematical expression for the quantity that we are maximising in the stock buying and selling problem

Problem Statement: Say you have an array prices for which the $i^{th}$ element is the price of a given stock on day $i$. Design an algorithm to find the maximum profit. You may complete as many ...
2
votes
1answer
35 views

Asymptotic analysis of $T(n) = T(n/5) + T(4n/5) + \Theta(n)$

If I have a recurrence relationship like this: $$T(n) = T(n/5) + T(4n/5) + \Theta(n),$$ how would I analyze its rate of growth? I believe I can't use the master theorem. I tried to draw a tree but ...
1
vote
1answer
11 views

Populating a vector of numbers to expose an error in a function implementation

So lets say I'm writing an algorithm that takes a vector as input. I want to know that I'm writing this algorithm correctly however so I of course write tests to see if the output equals what I expect ...
0
votes
0answers
41 views

Proof using tableau algorithm

I have spent an hour finding the answer to this problem but can't do it, this is the problem: Determining whether the following semantic entailment holds or not by using the tableau algorithm ...
0
votes
1answer
22 views

Represent a DNF formula as a multivariate linear formula?

Lets say I have the following DNF: (x or y) and (z or i) / $(x\lor y)\land(z\lor i)$ How do I convert that into a polynomial form?
3
votes
0answers
55 views

Data structure to determine vertex membership after edge removal from a tree in sub-linear time?

Consider a tree $T = (V,E)$ and its induced disjoint trees $T_1 = (V_1, E_1), T_2=(V_2, E_2)$ by the removal of an edge $e \in E$. Is there a data structure that enables the immediate determination of ...
2
votes
0answers
22 views

How to linearly combine loss functions to preserve optimal substructure property?

I've been working on a binary tree optimization problem with two choices of loss function (let's call them A and B). I'm fairly certain that the problem of minimizing either A or B individually has ...
3
votes
1answer
47 views

An efficient way of calculating 𝜙(𝜙(p*q)) where p and q are prime

Let $p$ and $q$ be prime numbers and $\phi$ Euler's totient function. Is there an efficient way of computing $\phi(\phi(p\cdot q)) = \phi((p-1)(q-1))$, that is not simply based on factoring $p-1$ and $...
0
votes
1answer
40 views

For an NFA, can we always find a RAM?

For an NFA, can we always find a RAM, which recognises the same language?
2
votes
1answer
15 views

Maximum Chromatic number of Cayley Graphs with large degree

It is known that there does not exist a regular graph of order $n$ with clique size greater than $\lceil\frac{n}{2}\rceil$. My question pertains to Cayley graphs with large degree, say $\ge \frac{n}{2}...
1
vote
0answers
31 views

If factor isn't found in P-1 algorithm, should upper bound be increased linearly (i.e. +1)

I have seen some implementations of Pollard's P-1 algorithm where the upper bound is only increased by 1 if no factor is found. Such an implementation is described here. Is it sort of missing the ...
1
vote
2answers
46 views

Implementing piecewise linear functions

I need to implement piecewise linear functions (this is not homework, it is for my own personal project). However, I have been having difficulties to get it right. Below, I describe the ...
2
votes
1answer
41 views

Pumping Lemma,regular languages

Lets say that we have the language L = { $a^n$$b^m$$c^{m+n}$ $|$ $m$,$n$ $>=0$ } What is the way that i should follow to prove that the language is not regular? Assume that the language is ...
3
votes
2answers
127 views

Check for common element in two arrays using FFT

My task asks me to check whether there is a common element in two sets $\{x_1,x_2,...,x_n\}$, $\{y_1,y_2,...,y_n\}$ with $x_i,y_i\in\mathbb{N}$ using the Fast Fourier Transform (FFT). (I'm aware that ...
2
votes
1answer
30 views

Confusion about the Hiring Problem

I'm confused about where the probability from the hiring problem comes from. For background: We interview one person everyday who has a quality characteristic, x, from 0 to 1(distributed uniformly). ...
1
vote
1answer
70 views

Lexicographic permutation

Consider that you have a permutation of $n$ elements from $1$ to $n$ and you need to sort the elements lexicographical . for example sorted permutation for $n=11$ is $1,10,11,2,3,4,5,6,7,8,9$ .Now ...
1
vote
1answer
22 views

How is expected value in entropy derived?

I was self learning about entropy and came across this equation. $$ H = - \sum p(x) \log p(x) $$ The equation for entropy in expected value, $$ H(x) = \operatorname*{\mathbb{E}}_{X \sim P}[I(x)] = -\...
1
vote
0answers
13 views

Trivial clarification with the analysis of the Dijkstra Algorithm as dealt with in Keneth Rosen's “Discrete Mathematics and its Application”

I was going through the text, "Discrete Mathematics and its Application" by Kenneth Rosen where I came across the analysis of the Dijkstra Algorithm and felt that the values at some places ...
-2
votes
2answers
81 views

Is a 'discrete language' well-defined?

Are the following well-defined formal languages (in these cases: subsets of {0,1}*) ? An argument w is a member of L under the following rules... Example1: If more than half of w's digits are 1's --...
0
votes
0answers
15 views

Total weight of Huffman Code

We are given the following letters with the respective frequencies: \begin{equation*}\begin{matrix}a/2 & b/4 & c/7 & d/6 & e/4 & f/5 & g/8 & h/10 & i/3 & j/11\end{...
1
vote
1answer
35 views

computationally efficient linear index to index pair mapping

Consider two index sets $S = \{0, 1, 2, 3, 4, ..., N - 1\}$ and $Q = \{0, 1, 2, ..., \frac{N(N + 1)}{2} - 1\}$. Let $R = \{(a, b)\space |\space a, b \in S, a \ge b\} = \{(0, 0), (1, 0), (1, 1), (2, 0),...
2
votes
1answer
18 views

Enumerating every “partnering” without repeating partners

I'm taking a class. In this class every week we have a partner. There are an even number of people in the class. We'd like avoid having repeat partners if possible so that everyone gets to work with ...
1
vote
2answers
42 views

Master Theorem applicable here?

Let $T(n):=\begin{cases} \frac{2+\log n}{1+\text{log}n}t(\lfloor\frac{n}{2}\rfloor) + \log ((n!)^{\log n}) & \text{if }n>1 \\ 1 & \text{if }n=1 \end{cases}$ I need to prove that $t(n) \in ...
0
votes
1answer
49 views

Same notation/terminology for union of sets and concatenation (Kleene star)?

For the union of sets we use the union operator $\cup$ (or $\bigcup$). And for a concatenation (Kleene star) we also use the union operator. The operations are different, but why the same terminology ...
0
votes
0answers
44 views

Counting a walk $i \rightarrow k \rightarrow l \rightarrow i \rightarrow k \rightarrow j \rightarrow l \rightarrow j$ in a graph

This paper gives a procedure for counting redundant paths (which I will refer to as walks) in a graph using its adjacency matrix. As an exercise, I want to count only the walks of the form $i \...
1
vote
1answer
65 views

Turing reducibility of 2 versions of the satisfiability problem

I need help with this problem. There are 2 versions of the satisfiability problem: [1] decision version: determine whether an arbitrary formula f is satisfiable or not [2] search ...
1
vote
1answer
62 views

Reducibility of 2 boolean satisfiability problems

I beg some help with this problem. There are 2 boolean satisfiability problems. Problem $A$: Determining whether an arbitrary formula of size $n$ is $satisfiable$. Problem $B$: Determining ...
0
votes
1answer
36 views

About computable sets

Let TOT be the set of all Turing Machines that halt on all inputs. Find a computable set B of ordered triples such that: TOT = {e : ($\forall$x)($\exists$y)[(e, x, y) $\in$ B] This definition means ...
1
vote
1answer
26 views

Is there a way to hash a turing machine?

If we have a Turing machine with various $\delta(q_i, a_i) = (q_j, a_j, Direction)$ where Direction can be L or R(denoting the movement of head), can we encode it uniquely to some natural number(which ...
1
vote
0answers
117 views

Recursive Algorithm to compute Square numbers

I figured out an algorithm to compute the square of a number (power of 2) in a recursive way backwards or forward. I don't think I have ever seen this anywhere else before, so I am curious if this ...
0
votes
0answers
23 views

Stable matching with dynamic preference lists

I have a set $F$ of $n_1$ families, a set $C$ of $n_2$ children ($n_1<n_2$) and a set $M$ of feasible one-to-one matchings of the families with the children. All the children have the same ...
0
votes
1answer
92 views

Prove or Disprove, 3SAT ≤p 2SAT, then P = NP

I know that 3SAT is in NP and 2SAT is in P. And 2SAT can reduce to 3SAT just says 3SAT is strictly harder than 2SAT, so I don't think this proves P = NP, but it doesn't seem to disprove it either.
0
votes
0answers
40 views

If a problem A ≤p B, then that B ≤p A, prove or disprove

I think the intuition is to disprove this by counter example, but what are 2 specific well known problems I can use as counter example?
1
vote
1answer
25 views

How interpret the notation $f:\{0,\dots, N-1\} \rightarrow \{0,\dots, N-1\}$, $N$ is a number of the form $2^n$? [closed]

I need help how to interpret the following notation for $f$: Zeroes and ones form a binary number which can be converted to decimal notation. Thus, we may think of the computer as calculating a ...
1
vote
1answer
214 views

Turing reducible in natural numbers?

I'm confused about Turing reducible things. I understanded Turing reducible like this ...
1
vote
1answer
26 views

Hoare Logic for Factorial

I came across this hoare logic for factorials but I don't quite understand it. We multiply F and X but we're not adding up all values of F so how do we get the sum/factorial at the end? Precondition: ...
1
vote
0answers
21 views

Determining Range of Current Node in Segment Tree

I was attempting, though failing quite miserably, to find some method of of determining the range of some node $n$. By range I mean an interval $[l,r]$ over the base array that is reachable by the sub-...
2
votes
1answer
33 views

Recurrence Relations

I am starting to learn recurrence relations in class and I am having issue with this example: T(N) = 2N - 1 + T(N-1) I am bit confused as to get the base case. I'm sorry if this seems elementary, ...
1
vote
1answer
38 views

Amount of k-partitions of a number

I'm stuck on writing an algorithm for getting the amount of distinct partitions for a number $n$ with the partition being size $k$. It's important that there isn't any repetition in the partitions. ...
1
vote
1answer
30 views

How many snakes there can be in the “snakes and ladders” game?

How to calculate the maximum allowed number of snakes in the game of "snakes and ladders" from mathematical/algorithmic point of view assuming that there is a nxn board? UPD: My thoughts are simple, ...
2
votes
1answer
22 views

Why there is no polynomially large sequence of polynomial large weights that derandomize the isolation lemma?

I was studying the paper Derandomizing the Isolation Lemma and Lower Bounds for Circuit Size by Arvind and Mukhopadhyay and came across the following claim (Observation 1.2 on page 3): "More ...
1
vote
0answers
78 views

Chomsky Normal Form for context free grammars ambiguous/unambiguous properties?

My textbook states: Finally, it must be stressed that the Chomsky normal form says nothing about ambiguity in general—a CFG in Chomsky normal form may or may not be ambiguous, just like we have for ...
0
votes
1answer
37 views

Number of permutations of set {1, 2, …, n} for which insertion sort will perform exactly n permutations

I have had the following problem at my last exam: For how many permutations of set {1, 2, ..., n} where n > 2 will insertion sort (without guard element) perform exactly n comparisons. My thinking ...
2
votes
1answer
48 views

Set which is easy to sample, but difficult to sample from its complement

Given a set $S \subseteq \{0,1\}^*$, the algorithm $A$ is a generator for $S$ if given $n$ random bits $x \in \{0,1\}^n$, $A$ generates an element of $S$ of size $n$, and $A$ can generate at least $\...
4
votes
1answer
89 views

Separating the snakes

In a two-dimensional grid, there are $n$ "snakes" (sets of contiguous grid-blocks). The snakes do not touch each other. The goal is to cut the grid into $n$ rectangles using $n-1$ "fences" (horizontal ...
2
votes
1answer
35 views

Prove that there is a sequence of k minimum spaning trees between two distinct minimum spanning trees that each one is different in only 1 edge [duplicate]

I'm pracitcing exams towards finals, Given an undirected graph $G(V,E)$ , we denote 2 MST $T,T'$ neighbours if by deleting one edge from $T$ and add another one we get $T'$. Prove : for every 2 ...
2
votes
1answer
64 views

Encoding set of At-Most-One constraints as a MAX-SAT problem

Assume a set of variable $V$ = $\{v_1,...,v_m\}$. Given total $n$ at-most-one (AMO) constraints (at most one element in a given set is true) set [of the below form], over the variable set $V$, $$ ...
0
votes
2answers
99 views

How is the set of functions from ${\{a,b\}}$ to $N$ countable?

Assume a set of functions from ${\{a,b\}}$ to $N$ Where $N$ is the set of Natural numbers. Let us assume that the size of $N$ is $n$. i.e $|N|=n$ The first element $a$ have $n$ choices for mapping....

1
2 3 4 5
8