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

learn more… | top users | synonyms

2
votes
1answer
110 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
26 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
85 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}$$ ...
3
votes
0answers
249 views

Is the logarithm of $\aleph_0$ infinite? [migrated]

In classical mathematics $2^{\aleph_0}=\aleph_1$, right? So if $2^x=\aleph_0$, what does $x$ equal? In other words, can we define a logarithm for $\aleph_0$, and what should it be. Is it infinite? ...
-1
votes
1answer
112 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
38 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
59 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
83 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
113 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
71 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
32 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
38 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
67 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
140 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
23 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
69 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
79 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
64 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
91 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 ...
-1
votes
3answers
55 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
69 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
118 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
49 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
21 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
45 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
40 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
106 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
45 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
89 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
81 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
41 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
187 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
80 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
46 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
67 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
37 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
64 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
460 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
354 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
88 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 ...
0
votes
1answer
94 views

the height of a tree given n nodes and a condition [closed]

I came across a question on which I got totally stuck :( a sort of homework question) A weight-balanced tree is a binary tree in which for each node. The number of nodes in the left sub tree is at ...
1
vote
1answer
572 views

Determining the optimal threshold value for a one-dimensional decision stump classifier

I'm currently trying to find an efficient algorithm to solve a discrete optimization problem that arises when constructing decision trees. The problem is as follows: Say we are given $N$ ordered data ...
1
vote
2answers
107 views

Why can any polynomial and exponential be represented as a recurrence?

I posted this question on math.SE but I haven't got any reply so I'm posting here also. I am reading The Algorithm Design Manual by Steven S Skiena. In Section 4.10.1 Recurrence Relations, I ...
1
vote
1answer
123 views

Why don't people use Fermat's little theorem to check if number is prime?

There're a lot of examples of code for checking if a number is prime. Why don't people use Fermat's little theorem, i.e. this simple formula $\qquad a^{p-1} \equiv 1 \pmod p$, to check if a number ...
4
votes
0answers
36 views

Elementary proof of compact space = exhaustible space?

The work of Martín Escardó has demonstrated close parallels between classical topology o one hand and computability on the other hand. (See for example "Infinite sets that admit fast exhaustive ...