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.

© Copyright 2018