Transcript Introduction and Basic Counting PPT

Welcome to CSCA67/MATA67
Discrete Mathematics
Anna Bretscher and Richard Pancer
Richard Pancer
Weeks 1 -- 6
Anna Bretscher
Weeks 7 -- 12
Evaluation
Type
Percentage Each
Total
Assignments (2)
10
20
Exercises (8)
3
24
Quizzes (8)
1
6
Midterm
15
15
Final
35
35
Total
100
Evaluation
Exercises
– 8 each worth 3%
– Late exercises will not be accepted
– You are encouraged to discuss the problems with
other students however, the actual write up must be
an individual effort
– You must be able to reproduce any solution that you
submit. The penalty for cheating ranges from a zero
on the assignment to suspension from the university
Evaluation
Assignments
– 2 each worth 10%
– Late assignments will be accepted up to 24 hrs late
with a penalty of 25%
– You are encouraged to discuss the problems with
other students however, the actual write up must be
an individual effort
– You must be able to reproduce any solution that you
submit. The penalty for cheating ranges from a zero
on the assignment to suspension from the university
Evaluation
Quizzes
– 8 quizzes worth 6% (total)
– Drop the worst one in first 6 weeks and the worst
one in second 6 weeks
Term Test
– Week 7 or 8 worth 15%
Final Exam
– Worth 35%
Resources
Course Slides
Posted each week.
Print them and bring to class.
Website
http://www.utsc.utoronto.ca/bretscher/a67
Check the announcements daily.
Textbook
Stein, Drysdale and Bogart, Discrete Mathematics for
Computer Scientists
Office Hours
Tutorials
6
Course Expectations
Expectations of the lecturer
• Give clear, organized lectures
• Assign fair, challenging assignments that
ensure that you, the student, understand the
material
• Be available for help in office hours
• Help every student achieve their goals in the
course (this requires your help!)
Course Expectations
Expectations of the student
• Attend lectures and participate
• Bring course notes to class
• Review lecture notes after each class, not just
before the exam
• Complete homework fully, neatly and
independently
• Have respect for your classmates and lecturers
Discrete Mathematics
Who needs it?
Anyone in computer science or a mathematical
science
Why?
In CS we need to be able to
• speak precisely without ambiguity
• analyze problems and
• formulate solutions
• apply the concepts associated with probability,
graph theory and counting theory.
CS is Applied Mathematics!
Specifically, we will work on:
– Thinking abstractly
– Expressing ourselves precisely
– Arguing logically – i.e., inferring conclusions that
necessarily result from assumptions
– Writing rigorous solutions
– Learning how mathematics and computer science
work together
Where Does Mathematics Appear in
Computer Science?
Computer Graphics
Multivariable calculus, physicsbased modelling
Digital Signal
Processing
Multivariable calculus, (eg.,
speech understanding)
Numerical Analysis
Multivariable calculus, linear
algebra
Cryptography
Number theory
Networking Algorithms
Graph theory, statistics,
combinatorics, probability, set
theory
Where Does Mathematics Appear in
Computer Science?
Databases
Set theory, logic
Artificial Intelligence
Set theory, logic
Programming
Languages
Set theory, logic
Formal Methods
Set theory, logic for the
specification and verification of
hardware and software; (e.g.,
nuclear, aviation – NASA!)
Course Outline
Counting
3 weeks
Probability
3 weeks
Proofs
3 weeks
Graph Theory
3 weeks
How Do I Become Good At This
Stuff?
BY FAILING!
WHAT ???
Every time you fail at solving a
problem, you learn something. You
take a step closer to the solution.
Let’s Talk About Counting
Counting shows up everywhere…
Even when ordering pizza.
15
Counting Pizza Toppings
Q. Are there really 1,048,576 possibilities?
A. No! The commercial got it wrong.
Let’s count it ourselves.
16
Counting Pizza Toppings*
The commercial’s deal was:
• 2 pizzas
• up to 5 toppings on each
• 11 toppings to choose from
• all for $7.98 (back in 1997).
The commercial’s math kid claimed there are
1,048,576 possibilities.
*http://mindyourdecisions.com/blog/2011/04/27/math-problem-pizza-topping-combinations
17
Let’s Do The Calculation
Q. How many ways can we order a pizza with 0
toppings?
A. 1
Q. How many ways can we order a pizza with 1
topping?
A. 11
18
Let’s Do The Calculation
Q. How many ways can we order a pizza with 2
toppings?
A.
– 11 choices for the first topping (assume no
“double” toppings)
– 10 choices for the second would give
10 x 11 = 110.
– Order does not matter, so 110/2 = 55.
19
Let’s Do The Calculation
Q. How many ways can we order a pizza with 3
toppings?
A.
11 x 10 x 9 ways to select the toppings (assume no
“double” toppings)
Does the order the toppings are picked matter?
How many times have we over counted?
20
Let’s Do The Calculation
Q. How many times have we over counted?
Let our toppings be called x, y and z.
Equivalent pizzas: xyz xzy yxz yzx zxy zyx
Can think of this as 3 choices for the first topping, 2 for
the second, 1 choice for the last topping.
3x2x1=6
Total:
(11 x 10 x 9) / 6
21
Let’s Do The Calculation
Q. How many ways can we order a pizza with 4
toppings?
A. 11 x 10 x 9 x 8 ways to select the toppings (assume
no “double” toppings)
How many times have we over counted?
4 x 3 x 2 x 1 = 4! = 24
So
(11 x 10 x 9 x 8) / 4!
22
Let’s Do The Calculation
Q. How many ways can we order a pizza with 5
toppings?
A. 11 x 10 x 9 x 8 x 7 ways to select the toppings
(assume no “double” toppings)
How many times have we over counted?
5 x 4 x 3 x 2 x 1 = 5! = 120
So
(11 x 10 x 9 x 8 x 7) / 5!
23
Let’s Do The Calculation
So the total number of ways to order a pizza
with up to 5 toppings choosing from 11 toppings
is:
1 + 11 + (11 x 10)/2 + (11 x 10 x 9)/3! +
(11 x 10 x 9 x 8)/4! + (11 x 10 x 9 x 8 x 7)/5!
= 1 + 11 + 55 + 165 + 330 + 462 = 1024
Q. How did they get 1,048,576 in the
commercial?
24
Let’s Do The Calculation
Q. How did they get 1,048,576 in the
commercial?
A. Two pizzas. So for each of the 1024 choices
for the first pizza, there are 1024 choices for the
second pizza.
1024 x 1024 = 1, 048, 576
Q. Is 1,048,576 the correct answer?
A. No. Why not?
25
Let’s Do The Calculation
Q. Why isn’t 1,048,576 the correct answer?
A. We have over counted something.
The order of any two pizzas doesn’t matter
(Pizzas A, B are the same as B, A).
Q. How do we correct this?
A. Divide by 2:
1,048,576 ÷ 2 = 524, 288.
26
Let’s Do The Calculation
Q. Is 524,288 the correct answer?
A. No. We have under counted something.
There are not two orderings when we order
two identical pizzas (A, A). But we divided by 2
before.
Q. How do we correct this?
27
Let’s Do The Calculation
Q. How do we correct this?
A. Add back half of the number of identical
pizzas.
Q. How many pairs of identical pizzas are
there?
A. 1024.
Final answer: 524,288 + 1024÷2
= 524,288 + 512
= 524,800
28