[PDF] [PDF] CS201A: Math for CS I/Discrete Mathematics - CSE - IIT Kanpur

[PDF] Discrete Mathematics Problems - University of North Florida

This booklet consists of problem sets for a typical undergraduate discrete mathematics own, without the temptation of a solutions manual These problems On a multiple choice test with 100 questions and 5 answers per ques - tion, how 

[PDF] Exam in Discrete Mathematics ANSWERS

11 jui 2014 · Is the compound proposition in question 1 a tautology? Answer: No a b c d e f g

[PDF] free pdf version - Discrete Mathematics - An Open Introduction

2 jan 2019 · Before we can begin answering more complicated (and fun) problems, we must lay down some foundation We start by reviewing mathematical 

[PDF] Discrete Mathematics Exam 1 Solutions

16 oct 2014 · (a) Count the number of possible ways to answer all the questions on that test Solution Each question has four possible answers so there are 

[PDF] CS201A: Math for CS I/Discrete Mathematics - CSE - IIT Kanpur

23 nov 2017 · Answer all 8 questions It has 4 pages + 1 page for the standard normal distribution table 2 Please start each answer to a question on a fresh 

[PDF] Discrete Mathematics Multiple Choice Questions With Answers

17 août 2017 · and answers pdf , discrete mathematics solved mcqs computer science solved, engineering mathematics multiple choice questions answers, 

[PDF] Sample Exam Paper - University of Kent

Candidates may not attempt more than ONE question from each of the TWO questions in sections B and C MA 304 Discrete Mathematics – p 1/6 Page 2 MA304 

[PDF] Discrete Structures Final exam sample questions - Cornell CS

Justify your answer Solution Alice transmits ak mod m to Bob, who then computes (ak)k−1 mod m Because Bob mis-

[PDF] Notes on Discrete Mathematics - Computer Science

31 déc 2020 · cs yale edu/homes/aspnes/classes/202/notes-2013 pdf xxi Introduction This is a course on discrete mathematics as used in Computer Science It's Answers to these questions are summarized by a probability, a number

[PDF] discrete mathematics springer pdf

[PDF] discrete time fourier series coefficients calculator

[PDF] discrete time fourier series matlab code

[PDF] discrete time fourier transform matlab code

[PDF] discriminant negatif racine complexe

[PDF] discriminant négatif solution complexe

[PDF] discuss physical evidence of service servicescape and ambiance

[PDF] discuss the characteristics of oral language

[PDF] disk cleanup windows 7 cmd

[PDF] disk cleanup windows 7 download

[PDF] disk cleanup windows 7 stuck

[PDF] disk cleanup windows 7 system files

[PDF] disk cleanup windows 7 takes forever

[PDF] disk cleanup windows 7 temporary files

[PDF] disk cleanup windows 7 windows update cleanup

CS201A: Math for CS I/Discrete Mathematics

Endsem exam

Max marks:150

Time:180 mins. 23-Nov-20171.A nsweral l8 questions. It has 4 p ages+ 1 p agefor the standar dnormal distribution table.

2.Please start each answer to a question on a fresh page. And keep answers of

parts of a question together. 3. Just writing a numb er/nalvalue/gur ewil lnot get you ful lcr edit.Y oumust give justi- cations/ derivations in each case. 4. Y ouc anc onsultonly your own handwritten notes. Nothing else is allowed. Keep any electronic gadgets in your bag and the bag on or near the stage. 5.

Wher ene ededuse the standar dnormal distribution table at the end of the question p aper.1.(a) Y ouare the instructor of CS201 some time in the future and one of the questions in the

exam is:

Prove that:

Every integern >1is a product of a unique non-decreasing sequence of prime numbers..

For example, 18 = 233, 20 = 225, 23 = 23 etc.

A student produces the following inductive proof:

Base case:n= 2. 2 is a prime and the unique sequence is trivially 2. Strong inductive hypothesis: Assume that for integersnthe claim holds. Inductive step forn+ 1: Ifn+ 1 is a prime then the claim holds trivially since the non- decreasing sequence contains onlyn+ 1. On the other hand ifn+ 1 is composite then there exist integersy;z < nsuch thatn+ 1 =yz. Sincey;z < nthe claim holds foryand forz. We can merge the non-decreasing sequences foryandzinto a single non-decreasing sequence whose product isn+ 1.

Hence proved.

i. Whe nthe answ erscripts are returned the studen tnds s/he has got a zero and s/he approaches you with a regrading request. How will you defend your decision? In other words what is wrong with the proof?

Solution:

The key problem with the proof is that in general forn+ 1 the integersy;zare not unique. For example,n= 18 = 36 = 29. So, it is necessary to show that for all possible such distinct factorizations the nal merged non-decreasing sequence of primes is the same. Induction cannot help with this part of the proof which is the key part.ii.Is there a simple w ayto repair the studen t'spro of?

Solution:

No, there isn't.

The claim is just the unique prime factorization theorem. The non-decreasing part is irrelevant. The central point of a proof of the claim is to prove uniqueness by showing that two dierent factorizations lead to the same prime factorization.

The induction does not help with that. The original proof was by Euclid.(b)i. Let Sbe an innite set andA=fa1;:::;angbe a nite set. Argue that there exists

a bijection fromS[AtoS.

Solution:

SinceSis an innite set we can nd a countably innite subset that is an innite sequence of distinct elementss1;s2;:::2Sand dene the following mapping fromS[AtoS: a

17!s1;:::;an7!sn.

s

17!sn+1;s27!sn+2;:::.

Fors2S fa1;:::;an;s1;s2;:::g,s7!s2S

The above is clearly a bijection.

This is just a variant of Hilbert's argument of how to accommodatennew guests

for a hotel with innitely many rooms that has no vacancy.ii.Fin da bijection from the semi-closed in terval(0 ;1]Rto the interval [0;1)R.

Solution:

The following function gives a bijection from (0;1] to [0;1): f(x) =(

0; x= 1

1x

0< x <1

The above is clearly a bijection.(c)Argue that a graph is a tree i there is a unique path b etweenev erypair of no desin the

graph.

Solution:

LetGbe a tree and let there be two verticesxandythat have two non-identical paths, sayp1andp2between them. Now eitherp1,p2do not have any vertices inPage 2 common exceptxandyor they do. In either case this implies thatGhas a cycle and therefore cannot be a tree. So, pathsp1andp2must be identical. For the converse let there be a unique path between every pair of vertices inG. This implies that for any pair of nodesxandyit is possible to reach fromxtoy(or the reverse) but to get back to eitherxoryone has to retrace the previous path between xandyso there can be no cycle inG. So,Gis a connected, acyclic graph or a tree.[(3,3),(5,3),6=20] 2.

Assume all graphs in this question are connected.

Dene the dual of a planar graphG= (V;E) as the graphG?= (V?;E?) where every vertex v ?2V?corresponds to a distinct face inG. So,jV?j=jFj(no. of faces inG). We connect verticesv?1;v?22G?by an edgee?2E?whenever an edgee2Eis a separating or boundary edge for facesF1;F2inGcorresponding to verticesv?1;v?2respectively. Note thatv?1;v?2may coincide for example whenGhas only one face soF1;F2are same. (a) T hroughan example sho wthat a simple graph Gcan have a dualG?that is not simple - that is it can have multi-edges and self loops.

Solution:

The simplest example of this is a tree - a graph with just one face. Consider, the

graph (tree) below which has only one face:Gis a tree the corresponding dualG?has a single node and both self-loops and

multi-edges. The edge label inG?shows the corresponding edge inG.(b)Ag ainthrough an example sho wthat t wodieren tplanar em beddingsof a planar graph

can have non-isomorphic duals.

Solution:

Consider two dierent planar embeddings of the same planar graph in the gure below.Page 3 The planar graph has 3 faces. But the embedding on the right has a node of degree 4 in the dual corresponding to the outside face. In contrast the graph on the left does not have any node in the dual with degree 4. So the two duals corresponding to the

two planar embeddings cannot be isomorphic.(c)Dene the length of a face F1ofGto be the total length of the closed walk inGthat

circumscribe or bound faceF1. IfFis the set of faces inGargue that:

2jEj=P

F i2Flength(Fi).

Solution:

Each edge inGleads to a corresponding edge inG?corresponding to the two faces separated (can be same face) by the edge inG. So,jEj=jE?j. InG?each face corresponds to a node and its degree corresponds to the number of boundary edges of the face. So, the sum in the formula is just the degree sum inG?which is twice

the number of edges inG?or 2jE?j= 2jEj.(d)Assume Gis a bi-partite planar graph. What kind of graph isG?? Justify your answer.

Solution:

A bi-partite graphGcan only have cycles of even length. So, every face inGis bounded by an even number of edges. This means that each node in the dualG?has even degree. So,G?is an Eulerian graph. This is true even whenGdoes not have any cycles and therefore has only one face. In this case each edge inGwill lead to a self edge inG?. So, the only node inG?will have even degree.[4,6,5,5=20] 3. (a) Let set S=fa;b;c;d;e;fg. Find the number of ways in which we can get two not necessarily distinct pair of setsA;BSsuch thatA[B=S. The order is not important - sofa;cg;fb;c;d;e;fgis the same asfb;c;d;e;fg;fa;cg.

Solution:

A[B=Sin each case so for each elements2Sexactly one of the following must hold i)s2A;s62B, ii)s62A;s2B, iii)s2A;s2B. This means there are 3 jSjways to chooseA;B. However, every pair is being counted twice except when A=B=S. So, the total pairs disregarding order is:3jSj12 + 1 =3612 + 1 = 365.(b)Le tn >1 be an odd integer. Argue that the sequencenC1;nC2;:::;nCn12 has an odd number of odd numbers.

Solution:Page 4

1 2 [nC1+nC2+:::+nCn1] =12 (2n2) = 2n11. This is an odd number. So, the

sequence must contain an odd number of odd numbers.(c)Consider the 3 3 numbered grid below. Each square in the grid will be painted either

BLACK or WHITE. The colour for each square is decided by tossing a fair coin. Find the probability that the grid does not have a 22 BLACK square (that is all 4 squares are painted BLACK).123 456
789
(Hint: Principle of inclusion-exclusion.)

Solution:

LetBi; i= 1;2;4;5 be the event that the 22 grid withias the upper left corner is painted BLACK, letP(Bi) be the probability of that event. The probability that there is at least one 22 BLACK square is by principle of inclusion-exclusion: B B

5) +P(B2\B4\B5)]P(B1\B2\B4\B5)

= 4(12 )4(4(12 )6+ 2(12 )7) + 4(12 )8(12 )9 95512
So, probability that the grid does not have even one 22 black square is:: 195512 =417512 [7,5,8=20] 4. (a) F oreac hrecurrence b elowapply the Master theorem, if applicable, and determine a solution bound for the recurrence. If not applicable say why it cannot be applied. i.T(n) = 2nT(n2 ) +n.

Solution:

For the Master theorem the recurrence must have the form:

T(n) =aT(nb

) +f(n) where constantsa1; b1 andf(n) is the time taken at the top level of the recurrence and often has the formnc. The Master theorem cannot be applied in this case sinceais not a constant.ii.T(n) = 16T(n4 ) +n!.

Solution:

Case 3 applies here. That isa < bcforn >3 since (n3 )n< n! (using Stirling's formula). So,T(n) = (n!)Page 5 (b)T herecurrence equation T(n) = 2T(n2 ) +nlogndoes not t the Master theorem we discussed in class (T(n) =aT(nb ) +f(n)) wheref(n) wasnc. Use iterative unfolding to get the (:) solution for the given recurrence equation.

Solution:

Using iterative unfolding:

T(n) = 2T(n2

) +nlogn = 4T(n4 ) +nlogn+nlogn2 = 4T(n4 ) +n(logn+ logn2 = 8T(n8 ) +n(logn+ logn2 + logn4 = 2 kT(nk ) +n(k1X i=0logn2 i) Usek= logn = (n) +n(log2nlognlog2(logn1)logn2 = (n) + (nlog2n) = (nlog2n)(c)Consider in tegern >0 and dene anordered partitionofnas a breakup ofninto one or more positive integers that add up tonbut where order is important. That is forn= 4,

2+1+1, 1+2+1, 1+1+2 are dierent partitions. Derive the expression for the number

of ordered partitions fornwithout using generating functions.

Solution:

Consider the unary representation ofnas a sequence ofn1s. A partition corresponds to dierent ways of clustering the 1s by putting separators in the gaps between the

1s. We need to do this for 0 ton1 separators. When we have 0 separators we have

a single cluster of size or valuen. When we haven1 clusters we havenclusters each of size or value 1. In both cases there is only one possible way to do this. When there is one separator we get n1C1ways to get two clusters and similarly when we have 2;3;:::;n2 separators. So, forkseparators we haven1Ckordered partitions.

The total number of partitions is:Pn1

i=0n1Ci= 2n1. So, there are 2n1ordered partitions forn.[(3,3),9,5=20] 5. (a) Let Fbe a-Field and letA;B2 F. AreAnB(AdierenceB) andA4B(symmetric dierence betweenAandB) inF? Justify.

Page 6

Solution:

SinceFis a sigma eld it is closed under complementation and countable union.quotesdbs_dbs17.pdfusesText_23