CSCE 411 Sample Midterm Exam 1. (10 points for each part)

```CSCE 411 Sample Midterm Exam
1. (10 points for each part)
(a) Do the following descriptions correspond to matroids? If not, why not?
(1) S is a given ﬁnite set and A is a given non-empty subset. The independent sets are all the subsets
of A.
(2) S is a given ﬁnite set with positive integer weights on the elements of S. The independent sets are
all sets with sum of weights greater than T , for some positive integer T .
(b) Brieﬂy explain the diﬀerence between the expected time for a sequence of operations and the
amortized time. Your explanation should make it clear that you understand what these terms mean.
(c) For the following pairs of functions f and g, is f = Ω(g)? is f = Θ(g)? is f = ω(g)? is f = O(g)?
f (n) = 2n , g(n) = n!
f (n) = n ∗ lg(n), g(n) = n1.5
(d) Give tight asymptotic bounds on the solutions to the following recurrences, justifying your answer
brieﬂy:
T (n) = 9T (n/4) + n2
T (n) = 3T (n/3) + log(n)
(e) Derive the Huﬀman tree using Huﬀman’s algorithm for the alphabet A = {a, b, c, d} when the
frequencies are given by f (a) = 3000, f (b) = 6000, f (c) = 5000, f (d) = 4000.
2. (25 points total) Suppose you were trying to maintain dynamic tables as the text described, but
when the table was full, you moved to a table that was 3 times as big instead of twice as big, and moved
to a table 1/3 the size when the table was 1/9 full.
(a) (10 points) What potential function would you use to show that the amortized time for an insert
operation is O(1) when the table is full?
(b) (15 points) Assuming (without proof) that all of the operations have amortized constant time, show
that the actual time for n operations is O(n).
3. (25 points total) Consider the following coin changing problem: Given a set of positive integer
denominations d0 , d1 , . . . , dN with unlimited coins of each denomination and a target amount T , ﬁnd the
minimum number of coins that can be used to achieve exactly the amount T . (Assume d0 = 1 so that
every T can be achieved exactly.)
(a) (10 points) Show the optimal substructure for this problem, by writing down the equation showing
how to recursively ﬁnd the solution in terms of the solultion of smaller problems.
(b) (10 points) Describe a greedy approach to ﬁnding the solution.
(c) (5 points) Show by example that your approach does not always get the optimal solution for all
possible sets of denominations.
```