1
vote
3answers
28 views

Which discrete mathematics book to read for a software engineer?

I'm a computer science student, but I lack a good mathematics background. So I decided to start working on that. I was searching in the topic and I found that for computer science a good knowledge of ...
-2
votes
1answer
22 views

Which is a linear and homogeneous recurrence?

Which of the following choices is a linear and homogenous recurrence? $1)$ $A_n = A_{n-1} + 4A_{n-2} + 3n$ $2)$ $A_n = n + 1$ $3)$ $A_n = (A_{n-1})^2$ $4)$ $A_n = 5A_{n-1} + A_{n-2} + 3A_{n-3}$
0
votes
2answers
40 views

Recurrence Relationship Questions

Consider the recurrence defined by: $$G_0 = 0\\ G_n = G_{n-1} + 2n - 1$$ Determine what Gn is for several values of n to determine a formula for Gn. $2n$ $n$ $2n-1$ $n^2$ *I believe this one is ...
1
vote
1answer
37 views

Simple Recurrence Questions [closed]

$r$ is a real number, define a recurrence relationship for $A_n$ $$A_0 = 1\\ A_n = r\cdot A_{n-1}$$ Question: What is the value of $A_4$ $4(A{n-1})$ $r^4$ $1$ $4r$ I've pretty much eliminated ...
0
votes
0answers
13 views

(L1* ∩ L2*) = (L1 ∩ L2)* for all languages L1 and L2 over the alpabet Σ={A,B} Is it true or false and why?

plz answer me Determine whether each of the following statements is true or false. If a statement is false, give a counterexample..... 1- $(L_{1}^{*} \cap L_{2}^{*}) = (L_{1} \cap L_{2})^{*}$ for ...
0
votes
1answer
60 views

efficient algorithm to place people in a specific order

You are preparing a banquet where the guests are government officials from many different countries. In order to avoid unnecessary troubles, you are asked to check the list of international conflicts in ...
3
votes
2answers
61 views

Linear Homogeneous Recurrence Relations and Inhomogenous Recurrence Relations

I'm having some difficulty understanding 'Linear Homogeneous Recurrence Relations' and 'Inhomogeneous Recurrence Relations', the notes that we've been given in our discrete mathematics class seem to ...
1
vote
1answer
33 views

Finite state machine

I am doing discrete math, and we are studying Finite State Machines. But i am a little confuse on how to do this. Here is a question, Write a regular expression for the language, and define a finite ...
0
votes
2answers
25 views

Help with finding the generating function (with a constant )

How do you get the generating function from this formula: $8(1+x)^{7}$ I have the following formula for $(1+x)^{n}$ : $n\choose 0$ + $n \choose 1$$x^1$ + $n \choose 2$$x^2$+... +$n \choose ...
0
votes
1answer
45 views

Discrete Math: Functions and Set Questions

1) Consider the function: $f: \mathbb{R} \to \mathbb{R}$ (Real to Real Number), where $f(x)=2+x^2$, what would be all of the preimages of $3$? 1) $11$ 2) $11$, $-11$ 3) $1$, $-1$ 4) $1$ 2) Let $D ...
0
votes
0answers
42 views

Bitwise operations: using bitwise operations on bitstrings to find combinations

I'm not sure how one would go about solving this problem from my discrete math book. Here is the problem : Show how bitwise operations on bit strings can be used to find these combinations of ...
-1
votes
0answers
14 views

Discrete Math Inductive Definition for Strings

Find an inductive definition for the following set of strings: $S = \{a^pbc^r : p\text{ is a natural number, and r is a natural number greater than }0\}$
0
votes
1answer
24 views

Provide a Proof of Inequalities for the Given Problem

Let A be known as a graph. By definition an independent set S is a group of vertices (could be 0 vertices, or could be all vertices) of A where there are no two vertices from S that are adjacent in ...
0
votes
1answer
39 views

Planar and Euler's Formula Question

If a connected planar graph has four regions and six vertices, how many edges will the graph have? (I believe the answer is 8 but I'm not positive) 1) 9 2) 8 3) 6 4) 7 Graph A = ({a,b,c,d,e,f,g}, ...
0
votes
1answer
54 views

Bipartite Graphs and Trees Questions

Which of the claims below is not equivalent to the rest? 1) Every cycle in a graph "B" has an even length 2) Graph "B" is bipartite 3) Graph "B" has two components that are connected. 4) Graph "B" ...
0
votes
0answers
23 views

create a decision tree with depth at most 3?

I have a final tomorrow and I came across this on one of the samples, can anyone help out? thanks! We are given four elements a; b; c; d such that a < b and c < d . Give a decision tree that ...
0
votes
0answers
31 views

An independent set of vertices $\times$ the chromatic number $\ge$ the number of vertices

$A$ is a graph. By definition an independent set $S$ is a group of vertices (could be 0 vertices, or could be all vertices) of $A$ where there are no two vertices from $S$ that are adjacent in graph ...
0
votes
2answers
38 views

Discrete Math graph question?

How many edges would I need to add to $K_{n,m}$ to make it complete (instead of bipartite)? (n,m --> n+m) I know that $K_n$ has $\frac{n(n-1)}{2}$ edges and $K_{n,m}$ has $nm$ edges, but I can't ...
3
votes
1answer
86 views

“Opposite” of idempotent operation?

What is the adjective given to a mathematical operation/expression on a variable whose new value can only be described in terms of that variable's existing value? Sequential operation? Example: i = ...
0
votes
1answer
68 views

Graph Coloring Question

Given T(n) as a star graph with n edges. (Basically T(n) is a graph that has one vertex u in the center, and from u there is one edge to each vertex v1,...,vn.) It is easily know that star-graphs are ...
1
vote
1answer
31 views

Proof that such a Turing machine cannot be constructed…

Prove there can be no Turing machine $M^*$ that takes input $n$ and: i. halts printing 1 if $M_n$ halts on input 1 ii. halts printing 0 if $M_n$ doesn't halt on input 1 Intuitively I can see why ...
2
votes
0answers
34 views

Iteratively Replacing Substrings

This problem came up while I was helping someone. Informally, we have a string of characters and a "rule" which replaces a specific string with another one, and we repeat this rule until we can no ...
0
votes
1answer
68 views

Graph Theory - Introduction Questions [closed]

I have a couple of questions that are probably SUPER easy for anybody that has studied graph theory but are confusing the hell out of me. I know it may be inconvenient to help me but I have a test ...
3
votes
3answers
62 views

Is $L = \{(x,y,z) | x+y=z\}$ a regular language?

Suppose $x,y,z$ are coded as decimal or their binary representations in an appropriate DFA. Is $L$ regular? My intuition tells me that the answer is no, because there are infinitely many combinations ...
0
votes
2answers
72 views

Tough Turing machine multiple choice questions

I'm having a tough time deciding whether my answers for these questions are correct. Can anyone help me agree on something? They seem pretty easy, but I've found that they're actually difficult. ...
3
votes
1answer
58 views

Is Cartesian Product same as SQL Full Outer Join?

Is Cartesian Product same as Full Outer Join found in Relational Database SQL? I ask because I am taking a Discrete Mathematics course and I just want a better understanding of how what I am studying ...
1
vote
3answers
162 views

What is the difference between discrete and continuous mathematics?

I am studying computer science and this has me absolutely flummoxed. The definition I can find is that discrete data is countable and that continuous is uncountable. Examples are given stating that ...
3
votes
2answers
114 views

What will I be doing?

I'm a freshman studying discrete mathematics B.sc. It's easy to google ''typical mathematician jobs'' and get an idea of what mathematicians do for a living, but what sort of jobs can I expect to work ...
1
vote
2answers
33 views

binary representation shrinkage question

Suppose for a given number $n$, every operation is to add $+$ signs arbitrarily into its binary representation. Repeat this process $K$ times. Prove: It is always possible to reduce the number to ...
0
votes
1answer
49 views

How to prove such program is uncomputable

We say that two programs are equivalent if they give the same output on every input. Prove that it is impossible to write a computer program that takes as input two pieces of code, code1 and code2, ...
0
votes
1answer
30 views

Communication complexity example problem

Let $G = (V,E)$ and $H = (W,F)$ be two undirected graphs with $|V| = |W| = n$. G and H are isomorphic if there is a bijection f : V -> W such that: $\{u,v\} \in E$ <=> $\{f(u),f(v)\} \in F$ ...
1
vote
1answer
622 views

Colored ball probablity

A triangular box contains five differently colored balls: red (R), green (G), blue (B), white (W), and yellow (Y). Define an appropriate sample space to study the outcome of an experiment where a ...
1
vote
1answer
47 views

How can I encode this?

Let say I have 7 integers: 1, 2, 3, 4, 5, 6, 7. Among the 7 integers, I choose 3 integers. For example, my choice is (1,2,3). Note1: The order of the integers in the choice doesn't matter. This means ...
1
vote
0answers
54 views

Showing particular language is NP-complete

How is FLO NP-complete? Let G be a social network where vertices correspond to people and edges are relationships between people (undirected). Some pairs of people (who are friends) get married. We ...
2
votes
2answers
90 views

How to efficiently encode this?

I have 5 ring oscillators whose frequencies are f1, f2, ..., f5. Each ring oscillator (RO) has 5 inverters. For each RO, I just randomly pick 3 inverters out of 5 inverters. For example, in RO1, I ...
0
votes
1answer
51 views

Base conversion using geometric series

I'm working on converting numbers in various bases and one question asks to convert $.2525...$ from decimal to octal. I know that the answer is $1/3$ and that it is necessary to use the infinite ...
0
votes
1answer
50 views

Language equivalence - manipulation of languages with Star operator

Why is this always true $(A^{*} \cap B^{*})^{*} = (A \cap B)^{*}$ ? $A^{*} = \{ x_{1}x_{2}...x_{k}| k \ge 0$ and each $x_{i} \in A\}$, and similarly for B. Assuming A and B are any languages i.e. ...
2
votes
0answers
93 views

How to Enumerate of all simple connected labeled graphs with prescribed degree sequence?

For v=4 vertices, there must be 7 possible graphic sequence (3,3,3,3)(3,3,2,2)(3,2,2,1)(3,1,1,1)(2,2,2,2)(2,2,1,1)(1,1,1,1). From (3,3,3,3), one simple graph(complete) can be found. From(3,3,2,2), 6 ...
2
votes
2answers
81 views

Boolean Algebra-Simplification Assistance Needed

I have to show that (!(P.Q) + R)(!Q + P.!R) => !Q by simplifying it using De Morgan's Laws. Here is what I did but I'm not sure it's right. (!(P.Q) + R)(!Q + P.!R) => !Q (!P + !Q + R)(!Q + P.!R) ...
0
votes
2answers
43 views

Generating a random number of higher range

I had a discussion with my friend about writing a function (a computer program) which generates 9 values randomly using a random number generator which generates 4 values, i.e I have a PRNG rand(4) ...
8
votes
5answers
127 views

convert ceil to floor

Mathematically, why is this true? $$\left\lceil\frac{a}{b}\right\rceil= \left\lfloor\frac{a+b-1}{b}\right\rfloor$$ Assume $a$ and $b$ are positive integers. Is this also true if $a$ and $b$ are ...
1
vote
1answer
92 views

Question related to matrix in computer memory

I'm trying to solve the following problem from a book: A matrix $\mathbb M$ has 3 rows and 4 columns: $$\left[ \begin{array}{cccc} a_{11} & a_{12} & a_{13} & a_{14}\\ a_{21} ...
2
votes
1answer
82 views

How to model a client / server interaction with queuing theory

I'm interested in modeling a server application where the normal flow of data is as follows: Server A -> Server B -> Server C -> Server B -> Server A That is to say, a job originating from A makes a ...
0
votes
1answer
307 views

Ceiling to Floor Function Conversion Proof

I am working on a proof to convert a ceiling of a fraction to a floor of a fraction. I found this: \begin{aligned} q=\left\lceil \frac{n}{m} \right\rceil \;&\Leftrightarrow\; \frac{n}{m} \leq q ...
0
votes
1answer
87 views

Count the number of transitive functions over set of size n

What is the most efficient way to compute the number of transitive functions over a set of n variables. I cant think of anything but brute force.
1
vote
1answer
90 views

to find disconnected graphs

We know that if in a graph $G$, $e$ < $(n -1)$, then the graph is disconnected, where $e$ and $n$ are number of edges and number of vertices resp. Is there any other criteria to find out the ...
1
vote
0answers
36 views

is the $d$-dimensional arrangement of Trees still $NP$-hard?

The $d$ dimensional Arrangement Problem for general graphs is known to be $NP$-hard since the special case $d=1$ (OLA) already is (Garey et al, [1976]). For Trees however, the one dimensional case can ...
0
votes
1answer
29 views

How can i bound the largest edge length of an $n$-point metric in $O(n)$?

For a given metric $d$ on a finite (vertex) set $V$, how can I bound the largest edge length in $O(|V|)$? While (wlog) assuming that the smallest edge length is at least $1$.
7
votes
2answers
210 views

maximum number of edges to be removed to possess a property

I am working on a problem. We know that on squaring a cycle, degree of every vertex is 4. For squares of cycles, we know if we delete any arbitrary edge then still eccentricity is same for all ...
1
vote
2answers
74 views

Could graph theory aid in the understanding of comparison sorting algorithms?

I am interested in computing the exact number of comparisons that are needed to sort a list. See this wikipedia article. Up to $n=15$, we know how many comparisons between elements one must make to ...