Notes for midterm
• Computational thinking—fundamental skill for everyone; Most fundamentally addresses the question:
What is computable?; way that humans think, conceptualizing, fundamental, ideas
• Two trends not to be missed:
The growing scale of available data; The shrinking time to make decisions
• A matching is stable if there is no pair, who are not matched, but would prefer each other
to their current matched partners. (deferred choice algorithm
Counting:
Product rule--If there are m ways to do one thing, and n ways to do another thing, then there are m
x n ways of doing both things. –both to be done at the same time (and)
Sum rule--If there are m ways to do one thing, and n ways to do another thing, and both things
cannot be done at the same time, then there are m + n ways of doing only one of the things. –OR
Inclusion-exclusion principle--If two things can be done at the same time, the sum rule will lead to
double counting. In this case, we add the number ways to do each task, and then subtract the
number of ways to do both tasks. (e.g. multiples)
Permutations--A permutation of a set of objects is an ordered arrangement of these objects.
P(n, n) = n! The number of permutations of a set of length n is n!
An r-permutation of a set of n objects is an ordered arrangement of r of the n objects
Permutation: order/sequence is important
n
Pr = n! / (n - r)!
N: number of items; R: number of items taken at a time
Combinations--A combination of a set of objects is an unordered selection of these objects.
C (n, n) = 1 The number of combinations of a set of length n is 1.
Combinations: order is not important; only the grouping combo
The number of combinations of a set of length n is 1.
An r-combination of a set of n objects is an unordered selection of r objects out of the n objects.
n
Cr =n! / r!(n - r )!
e.g. out of 45 students, you want to select 5 students (combination); however, if you want to assign
the students to different positions, then it’s a permutation problem
Special cases:
, How many ways are there for n men and n women stand in a line so that no two women stand next
to each other? Total = n! x n+1Cn x n!
Table problem: How many ways are there to seat six people around a circular table where two
seatings are considered the same when everyone has the same two neighbors without regard to
whether they are right or left neighbors? 6!/6*2 --> because when left and right are the same, 6! is
the number of possible combination, divided by 6 cos is the same going down the table by shifting so
eliminate and *2 cos must consider the reverse
Line problem: A group contains n men and n women. How many ways are there to arrange these
people in a row if the men and women alternate? n!*n!*2
How many positive integers between 100 and 999 inclusive: find the integer divisible by 7 that is
closest to 100 and 999→(994-105)/7 + 1
Algorithm—inputs, outputs, operations; must be precise (understandable), effective (solves the
problem), practical
Brute force algorithm—For two numbers a and b, its gcd is between 1 and the minimum of a and b;
try all possibilities
• Computational thinking—fundamental skill for everyone; Most fundamentally addresses the question:
What is computable?; way that humans think, conceptualizing, fundamental, ideas
• Two trends not to be missed:
The growing scale of available data; The shrinking time to make decisions
• A matching is stable if there is no pair, who are not matched, but would prefer each other
to their current matched partners. (deferred choice algorithm
Counting:
Product rule--If there are m ways to do one thing, and n ways to do another thing, then there are m
x n ways of doing both things. –both to be done at the same time (and)
Sum rule--If there are m ways to do one thing, and n ways to do another thing, and both things
cannot be done at the same time, then there are m + n ways of doing only one of the things. –OR
Inclusion-exclusion principle--If two things can be done at the same time, the sum rule will lead to
double counting. In this case, we add the number ways to do each task, and then subtract the
number of ways to do both tasks. (e.g. multiples)
Permutations--A permutation of a set of objects is an ordered arrangement of these objects.
P(n, n) = n! The number of permutations of a set of length n is n!
An r-permutation of a set of n objects is an ordered arrangement of r of the n objects
Permutation: order/sequence is important
n
Pr = n! / (n - r)!
N: number of items; R: number of items taken at a time
Combinations--A combination of a set of objects is an unordered selection of these objects.
C (n, n) = 1 The number of combinations of a set of length n is 1.
Combinations: order is not important; only the grouping combo
The number of combinations of a set of length n is 1.
An r-combination of a set of n objects is an unordered selection of r objects out of the n objects.
n
Cr =n! / r!(n - r )!
e.g. out of 45 students, you want to select 5 students (combination); however, if you want to assign
the students to different positions, then it’s a permutation problem
Special cases:
, How many ways are there for n men and n women stand in a line so that no two women stand next
to each other? Total = n! x n+1Cn x n!
Table problem: How many ways are there to seat six people around a circular table where two
seatings are considered the same when everyone has the same two neighbors without regard to
whether they are right or left neighbors? 6!/6*2 --> because when left and right are the same, 6! is
the number of possible combination, divided by 6 cos is the same going down the table by shifting so
eliminate and *2 cos must consider the reverse
Line problem: A group contains n men and n women. How many ways are there to arrange these
people in a row if the men and women alternate? n!*n!*2
How many positive integers between 100 and 999 inclusive: find the integer divisible by 7 that is
closest to 100 and 999→(994-105)/7 + 1
Algorithm—inputs, outputs, operations; must be precise (understandable), effective (solves the
problem), practical
Brute force algorithm—For two numbers a and b, its gcd is between 1 and the minimum of a and b;
try all possibilities
