Discrete mathematics is the study of mathematical structures that are fundamentally discrete rather than continuous.

learn more… | top users | synonyms

2
votes
1answer
31 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
21 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
61 views

Better Alternatives for Canny algorithm in Edge Detection?

Canny edge algorithm has 5 stages, from here ...
0
votes
2answers
77 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
23 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
154 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
33 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
110 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
164 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
45 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
66 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
133 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
117 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
83 views

What is the algorithm to add 2 binary numbers with boolean operations?

What is the algorithm to add up 2 binary numbers when the basis is {negation, conjunction, disjunction} in linear time? Also the program needs to be linear as well, meaning there can only be ...
2
votes
1answer
36 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
46 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 ...
4
votes
1answer
85 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] >= ...
3
votes
1answer
250 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
76 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
91 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
98 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
94 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
72 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
78 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 ...
2
votes
1answer
196 views

Relations and Zero One Matrices

I was studying but realized that I am having trouble grasping the representations of relations using Zero One Matrices. For example if I have a set A = {1,2,3} and a relation R = {(1,1), (1,2), ...
0
votes
0answers
73 views

The Inverse of a function with logic operators

How would one be able to tell whether or not a function has an Inverse? I've got a question in my discrete mathematics/ combinatorics class that asks whether or not the following function has an ...
-1
votes
1answer
23 views

How do you show that repeatedly dividing $n$ by $2$ takes $\log_2n$ steps to reach $1$?

I don't see why $n, n/2, n/4, n/8, \dots, 1$ takes $\log_2 n$ steps. Is there a more general statement on this repeated division?
1
vote
1answer
59 views

Converting Base 16 to Base 8? [closed]

I understand the basic but what I dont understand is this: so base 16 to base 10 357/16 = 22.3125 but on this example im looking at says remainder 5?
-2
votes
2answers
41 views

Lower bound of this harmonic series sum [closed]

I'm stuck on an excercise in my maths class. How can I find an explicit lower bound for the harmonic series sum: $$\sum_{x=1}^{2^m}\frac{1}{x}\,?$$
1
vote
2answers
107 views

Proving that $2^n$ does not divide $n!$ [closed]

How can prove that $2^n \nmid n!$ using binary representation for $n!$ and $2^n$.
1
vote
1answer
48 views

Tower Of Hanoi Time Calculation

I have been trying this Towers of Hanoi question since last week but never able to come with the right approach towards the solution. The setup is the standard Towers of Hanoi, except that moving the ...
0
votes
2answers
95 views

How to simplify the sum over 1/i?

With the recurrence relation: $$ T(n) = 2T\left(\frac{n}{2}\right) + \frac{n}{\log(n)}$$ The "sum for all levels" in the recurrence tree is: $$ \sum_{i=0}^{\log n -1} \frac{n}{\log n - i} = ...
4
votes
0answers
86 views

What is this prize-collecting optimization problem with travel times?

There exist very rich literature on discrete optimization problems such as variants of knapsack problem, traveling salesman problem, orienteering problem, tourist trip design problem and etc. ...
1
vote
0answers
25 views

Is lower bound for log (n!) also nlogn [closed]

I saw the same question here.They have proved the lower bound like this ...
1
vote
0answers
27 views

Describe in English the pattern in the following regular expressions [duplicate]

Describe (in English phrases) the languages associated with the following regular expression. it says to be as simple as possible ...
1
vote
2answers
43 views

Finding number of numbers <= N, containing atleast one of the digits 2,4,6,8

Given an integer $N$, I want to find the number of numbers $\le N$, that contain at least one of the digits from the set $\{2, 4, 6, 8\}$. How do I go about solving this problem? I was thinking of ...
3
votes
1answer
193 views

What do queues and stacks correspond to in math?

Many (and I suspect all) abstract data types in CS correspond to some math concepts, and even share the same names, for example, set, map, record/tuple, .... As abstract data types, what do queues ...
1
vote
1answer
110 views

Applications in Computer Sciences of Partition Functions

A partition function computes the number of ways an integer $n$ can be represented as the sum of $m$ other integers. For some value $n$, we have a partition function $p(n)$. These were studied ...
0
votes
1answer
49 views

Bytes--Measured or Counted [closed]

I hope the Computer Science section is the appropriate place to ask this question. I’m working on profiling some data sets and I am a bit tripped up on something, I was hoping I could get some ...
1
vote
0answers
47 views

the union of all the circuits and the intersection of all the bases [closed]

Is it correct that in a matroid, the union of all the circuits and the intersection of all the bases do not overlap? I susepect that is true from the equivalence in the definition for a coloop ...
1
vote
0answers
76 views

Discrete Mathematics books for Computer Science Self-study [closed]

I am an experienced software developer, want to refresh discrete math back in uni. I am looking for a book that is easy to read, contains more examples, and exercises and solutions for self study ...
5
votes
1answer
52 views

Not able to simplify a sum over reciprocals of $\log i$

Every time I solve these questions, I get stuck at the end where I need to find a closed form for the summation. Here in this case, I have reached until this point: $$ \begin{align} T(n) &= ...
2
votes
1answer
39 views

How to check if two sequences of setoid members are mutual rotations? [closed]

Task and terminology Assume we have a set $X$ and two sequences $S_1 = (a_1, a_2, \ldots,a_n)$ and $S_2 = (b_1, b_2, \ldots,b_n)$, where $a_i \in X, b_i \in X, \forall i \in [1..n]$. We define, that ...
0
votes
3answers
67 views

How do I mathematically express a set generated using two loop variables within a single for loop?

I don't know the proper mathematical expression for for-loops, especially those that carry two distinctly behaving variables with each iteration. For example, assuming ...
1
vote
2answers
492 views

Undirected graph with 12 edges and 6 vertices [closed]

For school we have to make an assignment, and part of the assignment is this question: Describe an unidrected graph that has 12 edges and at least 6 vertices. 6 of the vertices have to have ...
1
vote
0answers
28 views

Is the moment generating function for a sequence $\{a_n\}$ unique? [closed]

Suppose $\{a_n\}$ is a sequence with moment generating function $A(z)=\sum_{k \ge 0} a_kz^k$. Can a sequence $\{b_n\}$ with $b_n \neq a_n$ for at least one $n\in \mathbb N$ have the same moment ...
0
votes
1answer
373 views

Find largest chromatic number of a full binary tree [closed]

This is a Discrete Math/Combinatorics Question from my hw…but I don't really understand the question. Find largest chromatic number of a full binary tree given the following depths: (Check all ...
6
votes
2answers
95 views

Finite representations and programming languages Countably inifite

I'm going over some of the pre-requisite math regarding Automata theory, and finite representations. I read the following: If ∑ is a finite alphabet the set of all strings over the alphabet (∑*) is ...