false

Class Notes
(836,267)

Canada
(509,734)

University of Toronto Scarborough
(31,491)

Computer Science
(312)

CSCA67H3
(56)

Anna Bretscher
(30)

Lecture

Unlock Document

Computer Science

CSCA67H3

Anna Bretscher

Fall

Description

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 ﬂavours 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

Join OneClass

Access over 10 million pages of study

documents for 1.3 million courses.

Sign up

Join to view

Continue

Continue
OR

By registering, I agree to the
Terms
and
Privacy Policies

Already have an account?
Log in

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.