Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

CS 3000: Algorithms & Data — Spring 2024

Recitation 5: Midterm 1 Review

1 Asymptotic notation

Review: Review all definitions of asymptotic notation, practice how to compare functions, go over the problems in the problem sets, recitation exercises, and quizzes.

Exercise 1. Asymptotic comparison of functions

For each of the following pairs of functions, indicate which relationships apply:

f (n) = O(g(n)), f (n) = Θ(g(n)), and/or f (n) = Ω(g(n)).

Give brief justification, using limits, or rules that we have established in class, or first principles.

1. f (n) = n4 and g(n) = 100n3 + 200n2

2. f (n) = log3 n and g(n) = log9n

3. f (n) = 2n and g(n) = 4n

4. f (n) = n and g(n) = 

5. f (n) = n3 and g(n) = ⌈n3/10000⌉

Exercise 2. Asymptotic notation

Let f (n) and g(n) be asymptotically positive and monotonically increasing functions. Prove or disprove each of the following statements.

(a) f (n) + g(n) = Θ(max{f (n),g(n)}).

(b) If log(f (n)) = O(log(g(n))), then f (n) = O(g(n)).

2 Basic analysis of running times

Review: Practice the analysis of running times of basic iterative algorithms. Work through the problems in the problem sets, recitation exercises, and quizzes.

Exercise 3. Analysis of running time of an algorithm

What is the big-Θ running time of this pseudocode?

3 Divide and conquer

Review: Practice the analysis of running times of recursive algorithms using recurrences. Review the Master Theorem and recursion tree method. Review the divide and conquer paradigm, binary search, and the divide-and-conquer problems we have studied in class. Work through the problems in problem sets, recitation exercises, and quizzes.

Exercise 4. Recursive Algorithm - Part I

Consider the following recursive algorithm:

(a) State a recurrence which captures the number of times “Hello” is printed. Your recurrence should be of the form “T (n) = ...”. Don’t forget your base case(s)!

(b) Solve your recurrence from part (a) with the Master Theorem. That is, give a simplest function g(n) such that T (n) = Θ(g(n)).

Exercise 5. Recursive Algorithm - Part II

Consider the following augmentations to the RECALG above.

• There will now be three recursive calls, two on n/4 and one on n/3

• We will now print ”Hello” two times in the base case of n = 1 and print ”Hello” n times for all other values of n

(a) Based on the pseudocode from Part I, provide new pseudocode which captures the above changes.

(b) The following recurrence represents the number of times “Hello” is printed:

T (n) = 2T (n/4) + T (n/3) + n, T (1) = 2

Solve this recurrence to find a function g(n) such that T (n) = Θ(g(n)).

(c) Does the original recursive algorithm in Part 1 or the augmented version in Part 2 carry out more prints, as n goes to infinity?

Exercise 6. Processing an up-down list

You are working for an investment firm that prides itself on its analysis of the past. (You have heard this before!) You have been regularly asked to analyze historical data, which are being updated every minute and hence result in huge lists (of the order of several millions). One of the problems you repeatedly face is to find the minimum or maximum in such a list.

Of course, you know that the maximum, the minimum, or, in fact, element of any given rank, in any list can be computed in linear time. But since the lists are huge, even linear time is prohibitively large. Fortunately, most of the lists you analyze are up-down: that is, the list is composed of two contiguous (possibly empty) segments, the first is an increasing segment and the second is a decreasing segment.

Formally, an array A[1...n] is up-down if there exists an integer k, 1 ≤ k ≤ n such that A [1...k] is increasing and A[k ...n] is decreasing; that is, for 1 ≤ i < k, A[i] < A[i + 1], and for ≤ i < n, A[i + 1] < A[i].

Examples

• A = [2,4,6,7,8,3,2] is up-down since it consists of an increasing segment A[1...5] = [2,4,6,7,8] followed by a decreasing segment A[5...7] = [8,3,2].

• A = [2,13,9,7,6,3] is up-down since it consists of an increasing segment A[1...2] = [2,13] followed by a decreasing segment A[2...6] = [13,9,7,6,3].

• A = [9,7,5,3] is up-down since it consists of a trivial increasing segment A[1...1] = [9] followed by decreasing segment A[1...4] = [9,7,5,3] = [9,7,5,3].

• A = [1,2,5,6,8] is up-down since it consists of an increasing segment A[1...5] = [1,2,5,6,8] followed by a trivial decreasing segment A[5...5] = [8].

• A = [9,10,12,10,7,8] is not up-down since there is no k such that A[1...k] is increasing and A[k ...6] is decreasing.

For each of the following parts, give an algorithm for the desired task. State the worst-case running time of your algorithm (as a function of the input size n) using Θ notation.

(a) Finding the minimum element of an n-element up-down list.

(b) Finding the maximum element of an n-element up-down list.

(c) Sorting an n-element up-down list.

(You may assume that all elements of the list are distinct.)

For each part, make your algorithm as efficient as you can, in terms of its worst-case running time. Pseudocode is not required, but your algorithm description must be clear. Your grade would be based on the clarity of your algorithm description, the correctness of your algorithm, and its worst-case running time.

Note that the running-time is measured by the number of basic arithmetic and logical operations and the number of list entries that your algorithm accesses in the worst case.

(You need not prove the correctness of your algorithm or justify your stated running time.)

4 Dynamic programming

Review: Recall the different pieces of the DP paradigm: understanding the structure of the optimal solution, defining subproblems, writing the recurrence, converting recurrence to pseu-docode, recovering solution, and analyzing running time. Work through the problems in the problem sets, recitation exercises, and quizzes.

Exercise 7. Treasure hunt

You are in one of the famed vaults in Gringotts with a bag that can carry W grams of weight, where W is a positive integer. You see in front of you n different types of treasure, labeled 0 through n − 1. The weight of one piece of treasure i is w[i] grams. Each w[i] is a positive integer, and w[0] = 1. You know that a simple touch of a treasure makes multiple copies, so you have in front of you an infinite supply of each type of treasure.

You want to fill your bag fully with treasure; that is, the total weight of the treasure you select is W . Your objective is to select the smallest number of pieces that make this weight. For example, consider the following instance.

n = 3;w[0] = 1,w[1] = 4,w[2] = 5;W = 18.

One solution is to take 18 pieces, each of weight 1. Another solution is to take three pieces of weight 5 and three pieces of weight 1. The optimal solution is to take two pieces of weight 5 and two pieces of weight 4.

In this problem, you will design a dynamic programming algorithm, that takes as input the array w and the integer W , and returns the smallest collection of pieces, whose weight adds up to W .

(a) Let OPT(i) denote the smallest number of treasure pieces whose weight adds up to i. Give a recurrence to compute OPT(i), and write the base case(s) for this recurrence. Write a few sentences explaining why your recurrence is correct.

(b) Using your recurrence, design a dynamic programming algorithm to output the smallest collection of pieces whose weight adds up to W . You may use either a top-down or bottom-up approach. Remember that your algorithm needs to output the optimal collection of pieces, not only their count. Your algorithm may output the collection as an array A[0...n − 1] where A[j] is the number of pieces collected.

(c) Analyze the running time and space usage of your algorithm.