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

learn more… | top users | synonyms

3
votes
0answers
22 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
25 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} ...
-3
votes
0answers
22 views

how do you write a summation in a single form [closed]

Rewrite Pnk Æ0 2k Å2nÅ1 as a single summation
1
vote
1answer
20 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 ...
5
votes
0answers
63 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 ...
4
votes
1answer
25 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
31 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
76 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
34 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
285 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
34 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
13 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 ...
1
vote
1answer
153 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
380 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 ...
2
votes
1answer
68 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
63 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
20 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 ...
4
votes
0answers
26 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
118 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
49 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
2
votes
1answer
40 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
171 views

Better Alternatives for Canny algorithm in Edge Detection?

Canny edge algorithm has 5 stages, from here ...
0
votes
2answers
91 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
42 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
247 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 ...
0
votes
1answer
53 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
117 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
304 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 ...
1
vote
1answer
102 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
75 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
244 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
122 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
38 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
59 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 ...
5
votes
1answer
108 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
394 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 ...
0
votes
1answer
85 views

What's wrong with this problem (Inclusion-Exclusion principle) [closed]

There are 120 students at University College taking the introductory Java programming class. The students have access to the following computers: ...
0
votes
1answer
173 views

Structural induction over list

I want to prove that unique(reverse(L)) = reverse(unique(L)) where L is a List. List has the following constructors: ...
-1
votes
1answer
166 views

Books to get prepared before self studying Artificial Intelligence [closed]

I want to study Artificial Intelligence from Artificial Intelligence: A Modern Approach by Russell and Norvig, in the mid-year vacation. I want to get prepared before diving into the book so I decided ...
0
votes
1answer
105 views

How can I learn about CS? [closed]

I am an Junior in college and I have come to the realization that my school didn't to that good of a job of actually teaching real CS to the students. On my own, I have become a fairly proficient ...
0
votes
3answers
77 views

How to find upper and lower bound without using formula

I'm studying discrete math for tomorrow's exam and got stuck in the below question. I tried to google it and couldn't find anything useful. Prove the following sum is $\Theta (n^2)$ (we have to find ...
2
votes
1answer
86 views

Encoding the pigeonhole principle in CBMC

CBMC is a Bounded Model Checker for ANSI-C and C++ programs. It also supports SystemC using Scoot. It allows verifying array bounds (buffer overflows), pointer safety, ex­cep­tions and ...