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

learn more… | top users | synonyms

3
votes
0answers
6 views

Numerical Stability of Halley's Recurrence for Integer $n^{\mathrm{th}}$-Root

tl;dr? See last paragraph. If I use the initial value $2^{\left(\big\lfloor\lfloor\log_2 x \rfloor/n\big\rfloor + 1\right)}$ with Halley's recurrence in the compact form $ x_{k+1} = ...
2
votes
0answers
51 views

What are the simplest known algorithms to compute PI?

There are many algorithms that compute PI. Some are obviously complex, involving huge formulas and constants. Some formulas are not that complex, but involve operators such as ...
6
votes
1answer
44 views

Efficiently split a point cloud into two parts by a hyperplane to maximize the total sum of values associated with one part

I have the following problem in mind. Suppose we have an $n$-dimensional point cloud with $m$ points. Each point in the cloud is associated with a value $X_i,1\leq i\leq m$. I would like to use a ...
5
votes
2answers
67 views

Invertible function that randomizes order

I am looking for an invertible discrete function $f:\{0,1,2,\dots,n-1\} \to \{0,1,2,\dots,n-1\}$ for some given integer $n$. I want $f(0),f(1),\dots,f(n-1)$ to return all the integers in range ...
6
votes
1answer
74 views

Dividing bins into segments

This may be a question with a well known answer, but I've been thinking on it for two days, and can't quite come up with a satisfactory answer. Consider the problem of dividing $p n$ bins numbered ...
2
votes
1answer
17 views

Reference Request: Overlaps between complexity theory and dynamical systems?

Per Wikipedia: In mathematics, a dynamical system is a system in which a function describes the time dependence of a point in a geometrical space. Examples include the mathematical models that ...
1
vote
1answer
62 views

How many $(x, y)$-paths of length $20$ are there, where $x$, $y$ adjacent vertices in cycle $C_5$?

As the title of the question suggests, let $x$ and $y$ be two adjacent vertices in the cycle $C_5$. How many $(x, y)$-paths of length $20$ are there?
3
votes
0answers
28 views

Computing the index in a structured way

I want to map the various combinations to an unique index: For a given $n$ and $r$, we would have $\binom{n}{r}$ arrangement for values:$[0,\dots,n)$: Ex: For n = 6, r = 3 [012, 013, 014, 015, ..., ...
0
votes
1answer
28 views

CLRS: Asked to prove a result and then told to give a counter example [closed]

I am reading Introduction to Algorithms, and I am stuck at this execercise in the Appendix: Argue for any integers $n \ge 0$, $j \ge 0$, $k \ge 0$ and $j + k \le n$. $${n \choose j + k} ...
1
vote
1answer
23 views

Finding a closed form for a discrete sum using generating functions

Consider this sum: for context sake, the summand appears in the counting of the possible ways to have one cigarette box empty and the other having left N cigarettes when both boxes start with N ...
6
votes
0answers
76 views

Formulating shortest path as submodular minimization

I'm curious about the general question of whether any combinatorial optimization problem with polynomial time solution can necessarily be reformulated as minimizing a submodular function. The answer ...
5
votes
1answer
29 views

Inverting radial distortion

I'm trying to understand the math behind correcting a radial distortion (caused by a lens), but I'm failing to have it explained in simple terms. I found several examples that proceed this way: a ...
1
vote
2answers
41 views

Formulating a constraint to exclude a single point from the feasible region of an IP?

Consider a basic integer program such as: $$\begin{align} \min_x & \quad c^Tx \\ \text{s.t.} & \quad Ax \leq b \\ &\quad x_i \in \{-100,\ldots,100\} \end{align} $$ where $x \in ...
0
votes
4answers
82 views

Is it feasible to generate every possible RGB image?

This topic is normally brought up in computer science as a demonstration of how to calculate permutations but it stops there since we usually end up calculating that there are more images of a decent ...
0
votes
1answer
26 views

Help coming up with a solution to a combinatorial problem

So here is the problem: Say I want to find the only possible combinations to find the sum of a specific number using only the numbers 1, 2, & 3 with a specific number of additions. I know this ...
1
vote
0answers
39 views

What is the Necessary math to understand books?

I have many problems understanding algorithms described in the books. Well, I'm talking about the mathematical description of a problem. For example: I don't understand how the math of Unscented ...
7
votes
3answers
289 views

1-to-1 cryptographically secure bit shuffling

Given an input item (N bytes), I'm looking for a function that will map this to an output (still N bytes). The function should have the following qualities: It should be 1-to-1 so that all inputs ...
0
votes
1answer
38 views

Examples of maximal paths in undirected graphs

According to me, maximal paths in a graph are those paths which cannot be included in any other larger paths. Could anyone please explain me this with some examples? Also what would happen if the ...
-1
votes
1answer
14 views

L equivalence classes

Let L be the language consisting of all strings in (a+b)* that have an even number of letters and do not have aaba as a substring. Into how many L-equivalence classes is (a+b)* divided?
0
votes
0answers
21 views

Pedagogic reference on cut generating functions

Can you recommend an introduction to the topic of cut generating functions? I am looking for introductory or review-like material. I did find the following survey paper, but it seems to be addressed ...
2
votes
1answer
167 views

coding theory- perfect codes

I'm new to stackoverflow so please bear with me. A tutorial question I got given was as follows: You are given that $C \subseteq D \subseteq F^n_q$ where $|C| < |D|$ and $C$ is a perfect code. ...
-1
votes
2answers
415 views

number of subsets where GCD equals to X

The original statement for this problem can be found here This is a question from IEEExtream 2014. There is an array of integers given. Input is X, so output is the number of subsets where there GCD ...
0
votes
0answers
10 views

How to find the run time complexity of nested while loops? [duplicate]

So this problem is pretty nasty. I can easily find the number of iterations for each nested while loop. The first runs log_9(n) times and the second runs log_4(n) times. My problem that I do not ...
3
votes
1answer
86 views

Determining if (infinite) binary language DFAs contain at least 1 prime?

This problem has been given by Shallit as an open DFA/ complexity theory problem and is currently not even known to be decidable. It seems to be circulating on the internet in a few places (e.g. ...
0
votes
1answer
70 views

Negation of 8-bit hexadecimal

I am looking for a mathematical formula / algorithm to find the negation of a 8-bit hexadecimal without having to expand into a binary form. E.g; 0000BDDA -> 48602 FFFF4226 -> -48602 Need to get ...
0
votes
0answers
9 views

recursion trees and big theta bounds [duplicate]

Draw recursion trees and use them to find big theta bounds on the solutions to the following recurrences. For each, assume that T(1) = 1 and that n is a power of the appropriate integer. ex) T(n) = ...
1
vote
0answers
13 views

Big O help Discrete Math [duplicate]

Is 17x+11 a function of O(x^2)? My steps so far: 17x+11 < c.x^2 where x>k 17x+11/x^2 < C Im not too sure what to do next so I'd really appreciate if it someone could guide me. This question ...
1
vote
0answers
22 views

Voronoi game in discrete space

Here i want to discuss about Linear Voronoi game. The game consists of two players, and a finite set of users placed along a line. Each player has 2m facilities, where m>0 is a fixed integer. The ...
5
votes
0answers
29 views

Correctness of a zigzag algorithm to find the most similar vector in a bounded integer lattice

I am currently working on an integer lattice problem, called the "most similar vector problem," and wondering if can be solved correctly by a simple "zig-zagging" algorithm. Given a real vector $u ...
0
votes
0answers
151 views

Is the reverse postorder of a digraph's reverse the same as the postorder of the digraph?

I've been reading Sedgewick's intro to algorithms book, and he says that the reverse postorder of a digraph's reverse is not the same as the postorder of the digraph, however in both cases it seems ...
0
votes
1answer
53 views

Recurrence Relation(with Square root)

I came across a very peculiar recurrence relation : $\sqrt {T(n)} = \sqrt {T(n-1)} + 2 \sqrt {T(n-2)} $ with initial values $T(0) = T(1) = 1$ Any helps on how to find it
3
votes
1answer
44 views

Why are inversions useful in computer science?

In the second chapter of Cormen's textbook on Algorithms, he lists a discrete mathematics exercise on so-called "inversions", defined as follows: Let $A[1 \ldots n]$ be an array of $n$ distinct ...
0
votes
0answers
21 views

Landau bounds of a polynomial [duplicate]

I have this question in my homework. Its an a multiple choice question and goes as following: Let $f (x) = 3x^3 + 2x + 4$. One has that $O(x^3)$ ** the answers have been checked with the teachers ...
0
votes
1answer
27 views

How to exclude all points adjacent to a given point from the feasible region of IP

Consider a basic integer program such as: $$\begin{align} \min_x & \quad c^Tx \\ \text{s.t.} & \quad Ax \leq b \\ &\quad x_i \in \{-100,\ldots,100\} \end{align} $$ where $x \in ...
1
vote
0answers
235 views

Better Alternatives for Canny algorithm in Edge Detection?

Canny edge algorithm has 5 stages, from here ...
0
votes
2answers
96 views

How to expand 2D graphic and functions to 3D?

So I have a program that enables the user to draw 2D-objects. To rotate them, to move them, and so on, all in 2D. I want to expand the 2D objects and functions to 3D which I don't expect to be too ...
0
votes
1answer
59 views

Hamming Distance, Bit message [closed]

My professor told us to try and remember the equation used for an upcoming exam, however I'm struggling to fit the equation into the question: http://i.stack.imgur.com/RoPYG.png (need a high ...
3
votes
1answer
296 views

How to improve my these specific math skills? [closed]

I am student of CS. Problem is, I feel that I don't have enough math knowledge to solve mathematical problems. When some programming problems arises which needs some math skills to solve then despite ...
1
vote
1answer
60 views

What makes an MILP problem solvable?

Knapsack problems, Assignment problems can all be expressed as (MILP) mixed integer linear programs. MILP is NP-complete. But Knapsack problem is solvable in pseudo-polynomial time using dynamic ...
2
votes
1answer
126 views

Which optimization algorithm would you recommend for this small multidimensional problem?

Which algorithm would be suitable for finding or estimating the vector $$\mathbf{s}_{opt}=\begin{bmatrix} s_1 & \cdots & s_N \end{bmatrix}=\arg\max_{\mathbf{s}}\sum_{n=1}^{N}p_{s_n,n}$$ ...
-1
votes
1answer
335 views

How to prove a Double CNF SAT is in NP [duplicate]

So I've been stuck trying to figure this problem out for a while. I've looked on wikis and all over stack exchange but I'm really stumped. This isn't my best subject, so any sort of explanation would ...
2
votes
1answer
115 views

How to state a recurrence that expresses the worst case for good pivots?

The Problem Consider the randomized quicksort algorithm which has expected worst case running time of $\theta(nlogn)$ . With probability $\frac12$ the pivot selected will be between $\frac{n}{4}$ and ...
2
votes
1answer
81 views

How to choose between several constraints for a SAT task using quality metric?

I'm trying to solve a constraint programming problem using a SAT solver. I have set of constraints in the form of propositional logic statements, which are converted to CNF using Tseitin ...
5
votes
2answers
274 views

Application of set theory subjects as ordinals, forcing, generic filters in software engineering

I am going to teach a course in set theory for software engineering students. I am going to talk in this course about: ordinal numbers, partial orders, well ordering, generic filters and maybe some ...
4
votes
1answer
134 views

Tallest Person Average Memory Updating?

We ran into a problem that was mentioned in an interview 2 days ago. Can you help us with any idea or hint? A sequence of $n$ people, $\langle\,p_1,p_2,\dotsc p_n\,\rangle$ enter a room. We want to ...
2
votes
1answer
40 views

Efficient computation of traces of all primitive elements in field extensions of GF(2)

Let $n > 1$ and let $\mathbb{F}_{2^n}$ be the finite field with $2^n$ elements. The trace function $T(x) = x + x^2 + x^{2^2} + \cdots + x^{2^{n-1}}$ is an onto linear transformation from ...
0
votes
1answer
61 views

Lower bound the difference between distinct values of a function over a discrete domain?

I have a function $f: X \to \mathbb{R}$ where the domain $X$ is a (small) discrete set, such as $X = \mathbb{Z}^d \cap [-10,10]^d$ (i.e., the set of $d$-dimensional integer vectors all of whose ...
6
votes
1answer
121 views

How to find a subset of potentially maximal vectors (of numbers) in a set of vectors

I have a set S (so no duplicates) of d-dimensional vectors of non-negative real numbers (or if you would prefer, floats). I say a vector u "covers" a vector v if, in every dimension 1..d, u[i] >= ...
4
votes
1answer
450 views

Variants of the 3-SUM problem

The 3SUM problem has two variants. In one variant, there is a single array $S$ of integers, and we have to find three different elements $a,b,c \in S$ such that $a+b+c=0$. In another variant, there ...
1
vote
1answer
24 views

Can maximal number in poset be more than one?

In poset maximal number is defined as: An element 'a' belongs to 'A 'is called a maximal number if there is no element 'c' in 'A' such that a is less than c. but it again says that there can be more ...