13 Pages
Unlock Document

Computer Science
Anna Bretscher

Midterm Test: Chapter 4 1.2 Sum and product principles 3.1 Truth tables, implication 3.3 Direct proofs, contrapositive, Proof by contradiction 4.1 Proof by induction 6.1 Properties of graph 6.2 BFS and Trees 6.5 Colouring Counting With Repetitions The genetic code of an organism stored in DNA molecules con- sist of 4 nucleotides: Adenine, Cytosine, Guanine and Thymine. • It is possible to sequence short strings of molecules. • One way to sequence the nucleotides of a longer string of DNA is to split the string into shorter sequences. • A C-enzyme will split a DNA-sequence at each “C”. This means that each fragment will end at a C except possibly the last fragment. • Similarly for A-enzymes, G-enzymes and T-enzymes. • If the original nucleotide is split on each of C, A, G and T then it can be sequenced as it is most likely a unique sequence that can be constructed by each of the four sets of fragments. 1 Example. Given a 20-nucleotide string split at the Cs, one might have the fragments: AC, AC, AAATC, C, C, C, TATA, TGGC Q. How many different 20-nucleotide strings could have given rise to the above set of fragments? In other words, how many different arrangements are there of these fragments? A. Since TATA doesn't belong have a C, it must go last. C x3 AC x2 AAATC TGGC (7 choose 3) for the C (4 choose 2) for the AC multiply them all ( 2 choose 1) for AAATC (1 choose 1) for TGGC 7!/3!2!1! 2 Theorem. Given n objects, with 1 of type 1,2r of type 2,..., rm of type m where r + r + ... + r = n 1 2 m then the number of arrangements of the n objects, denoted by P(n;r 1r 2...,rm ) is: ▯ ▯▯ ▯▯ ▯ ▯ ▯ n n − r1 n − r1− r2 n − r1− r2−···− rm = ··· r1 r2 r3 rm Q. What does this formula simplify to? A. 3 Proof. n! P(n;r ,1 ,2..,r m)= r1!r2!...r m! • Convert the problem into something we can already solve. • Suppose all objects are distinct. How many permutations are there? • Consider the ith type. It is repeated r times. i • Add the subscripts 1,2,...,r to make them unique. i Example. Let our set of objects be the letters {b,a,a,a,n,n}. We can make the as and ns unique as follows: a ,a 1a 2 3 n ,n . 1 2 Q. Number of permutations of {b,a ,1 ,2 ,n3,n1}? 2 A. We can think of this as the number of ways to arrange {b,a,a,a,n,n} × . Q. How do we say this mathematically? A. 6! = P(6,3,2,1) # of ways to arrange {b,a,a,a,n,n} 4 Q. Suppose we have b,a,a,n,n,a. What are the different ways to arrange the as? A. b,a1,a2,n,n,a3 b,a1,a3,n,n,a2 b,a1,a2,n,n,a3 ..... can be arranged 3! (a1,a2,a3) Q. How many ways to arrange the ns for each arrangement of as? A. 2! Resulting in: 6! = P(6! 3,2,1,) x 3! x2! x1! • Generally, for the itype, we have ways to arrange the objects. Therefore: n ! = number of ways to arrange objects with repetition x number of ways to arrange with repeated type P(n!,r1,r2,....rn) x r1! x r2! x r3!......rm! n ! = • Rearranging gives: P(n;r ,1 ,2..,r m )= n! / r1! r2! r3!...rm! 5 # of ways to arrange n unique objects = (# of ways to arrange repeated objects times # of ways to arrange each repeated objects 8! / 5!3! computer = 8! lets only care about consonant and vowels 5 consonant and 3 vowels Selections With Repetitions Example. While shopping at the St. Lawrence market, you decide to buy half a dozen bagels. There are three flavours to choose from. Q. How many different ways can you select your 6 bagels? permutation of 8 things, 6 A. Rephrase as an arrangement problem. bagels and 2 bars Sesame Poppy Seed Plain xx xxx x Q. How is this an arrangement problem? A. Same as arranging 6xa7 2 | in 8 spots : Q. How can we also think of this as a selection problem? A. Pick 2 spots for 1 and 6 for x(bagels) Let n be the number of choices, r the number of items selected. Then 8= r +( n − 1) and we are choosing r =6 . This results in: r=6, n=3 (sesame, poppy seed, plain) 8 = r+(n-1) = 6+2 6 Theorem. Given r objects and n types of objects to choose from, the number of selections with repetitions is: ▯ ▯
More Less

Related notes for CSCA67H3

Log In


Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.