Description
Questions related to:
(NOTE: DO NOT use any AI tools)
1. Recurrence Relations
2. Advanced Counting
3. Counting in Computer Science
4. Algorithms
5. Algorithm Complexity
6. Applications of Discrete Mathematics
Unformatted Attachment Preview
Week 7: Recurrence Relations
7.1.
It is possible to draw n circles so that each circle intersects each other circle
exactly twice (but impossible for any two circles to intersect three times.) For example,
here are sets of two, three, and four circles where each circle intersects each other circle
exactly twice:
Write a recurrence relation describing the maximum number of intersection points on n
circles.
(Hint: if you have 7 circles, you can add an eighth and it will add two points of
intersection with each of the 7 existing circles.)
7.2.
Write a closed-form formula for the number of intersection points on n circles,
and write a proof that it is correct. (Hint: the closed-form formula will be quadratic.)
Week 11: Advanced Counting
11.1.
Consider lists of 10 different letters with no repeats, chosen from among the 26
letters in the standard English alphabet.
a. How many such lists of 10 letters are there? (Writing an expression is fine—you
don’t need to evaluate it.)
b. If we consider sets of 10 letters, there’s a function from lists of 10 letters to sets
of 10 letters. What is that function? (To describe this function, you’d say “f[input])
= [output]”).
c. The function you described in part b is n-to-one for some n. What is n? Explain.
d. If we consider circular necklaces of 10 letter beads, which may be rotated or
flipped, there’s again a natural function from lists to circular strings:
ABCDEFG
HIJ
BCDEFGH
IJA
C
JIHGFED
CBA
H
The three lists shown above actually produce the same necklace arranged
differently. List all the lists of letters that produce this same circular necklace.
e. How many circular necklaces of 10 letter beads are there? Explain.
11.2.
If I pick a random list of 10 different letters with no repeats:
a. What is the probability that it has an A as its first letter? Explain.
b. What is the probability that it has an A as its second letter? Explain.
c. What is the probability that it includes an A somewhere? Explain.
d. What is the average number of A’s that will appear? Explain.
Week 12: Counting in Computer Science
12.1.
Let 1 , . . . , and 1 , . . . , be two sequences of digits. Consider the following
algorithm:
←0
for ∈ {1, . . . , } do:
for ∈ {1, . . . , } do:
← +
a. How many multiplications will this algorithm conduct?
b. How many times will this algorithm do the ← operation?
12.2.
Explain the difference between ( 2 ( )), ( 2 ( )), and ( 2 ( )) as
clearly as you can. Draw a Venn diagram and give some examples of functions that are
in each area of the Venn diagram. (BONUS: see if you can include some functions that
are not in any of these classes.)
12.3.
Which of these functions is unlike the others in terms of its asymptotic behavior,
and why?
i.
the number of cubes used to make an × × cube as in these
diagrams:
ii.
the number of balls used to make the nth square pyramid as in this
diagram:
iii.
the number of squares used to make the surface area of the × ×
cube in these diagrams:
Week 13: Algorithms
13.1.
Consider the C(n, r) function from section 4.2.
a. Write an algorithm that computes C(n,r).
b. Is your algorithm iterative, recursive, both, or neither?
c. What preconditions are appropriate for your algorithm?
13.2.
In the “pounds, shillings, and pence” (£sd) system historically used in Great
Britain, there were the following coins (leaving some out for simplicity):
penny
sixpence (6 pennies)
shilling (12 pennies)
florin (24 pennies)
half-crown (30 pennies)
a. Write a greedy algorithm for making change in this system (like algorithm 5.8).
b. Prove that your greedy algorithm does not always make change with the fewest
possible coins.
Week 14: Algorithm Complexity
14.1.
What are the best-, worst-, and average-case complexity classes of the change-
making algorithm 5.8 in the text? (Imagine using this change-making algorithm without
the precondition 1≤N≤100—in other words, you could use this algorithm to find coins
totaling 739 cents.) Explain.
14.2.
The table at right shows the number of known species in different
major groups of organisms. Suppose you were designing a classifier using
a series of yes/no questions to identify a given species. (The classifier is
going to identify the species, not identify what group it’s in—e.g., if I have
a raven the classifier is going to ask enough questions to identify that it’s
Corvus corax, not that it’s a bird. So there are 1,730,725 possible outputs
for the algorithm.)
a. If you wanted your classifier to be optimal, what would be its worstcase number of questions?
b. The following decision tree is one way to get started asking yes/no questions to
identify a species.
Is it an animal?
Y
Is it a
vertebrate?
Y
(continue to
classify
vertebrates)
N
(continue to
classify
invertebrates
)
N
Is it a
plant?
Y
(continue to
classify
plants)
N
(continue to
classify fungi
and protists)
Explain why this decision tree is not the starting point of an optimal algorithm for
identifying a species.
Week 15: Applications of Discrete Mathematics
15.1.
Describe your favorite concept, fact, or idea you learned about in week 15.
Describe it in some detail, so I know you understand it; and describe how it relates to
one or two other ideas from either elsewhere in week 15, or earlier in the semester.
Purchase answer to see full
attachment
