Homework3 - Solutions

ECE360C: Algorithms Homework Assignment #3 University of Texas at Austin Due: September 15, 2023 (11:59pm) Homework Assignment #3 – Solutions Solutions are for individual use only by students registered for ECE 360C in Spring 2023 semester. They should not be otherwise shared or posted. Problem 1: Remember [20 points] Answer the following true/false questions about runtimes, as defined in class. True False ⊠ □ f ( n ) = O ( h ( n )) and g ( n ) = O ( h ( n )) ⇒ ( f ( n ) + g ( n )) = O ( h ( n )) □ ⊠ f ( n ) = O ( h ( n )) and g ( n ) = O ( h ( n )) ⇒ ( f ( n ) ∗ g ( n )) = O ( h ( n )) □ ⊠ log 2 ( n ) = ω (log 10 ( n )) □ ⊠ Quicksort, whose average case runtime is O ( n log n ) and worst case runtime is O ( n 2 ), is an optimal comparison sorting algorithm. ⊠ □ Mergesort, whose average case runtime and worst case runtime are both O ( n log n ) is asymptically better than Quicksort. □ ⊠ Mergesort will always run faster than Quicksort on the same input. □ ⊠ A heap, when implemented using a linked data structure rather than an array, still has O (log n ) runtime for inserting a new element. □ ⊠ The following process for building a heap takes Ω( n log n ) time: given an array of n arbitrarily-ordered elements, start with the element at position ⌊ n/ 2 ⌋ and call Heapify-Down . Continue with the element at position n/ 2 ⌋ − 1 and repeat until you reach the first element. ⊠ □ a n = ω ( n b ), for constants a > 1 and b > 0. □ ⊠ If f ( n ) is not O ( g ( n )), then if must be the case that f ( n ) = Ω( g ( n ))..

Homework Assignment #3: September 15, 2023 (11:59pm) 2 Problem 2: Understand [20 points] Prove or disprove each of the following: (a) 3 n = O (3 n − 1 ) Solution 3 n = 3(3 n − 1 ). So yes, 3 n = O (3 n − 1 ): c = 3 and n 0 = 1. (b) 3 3 n = O (3 n ) Solution 3 3 n = (3 n )(3 n )(3 n ). So, we need (3 n )(3 n )(3 n ) ≤ c 3 n or (3 n )(3 n ) ≤ c , which is clearly false. (c) 3 n = O (2 n ) Solution Using the limit theorem: lim n →∞ 3 n 2 n = lim n →∞ ( 3 2 ) n = ∞ because ( 3 2 ) > 1. Thus 3 n grows asympotoically faster than 2 n which disproves the statement 3 n = O (2 n ). (d) f ( n ) + g ( n ) = Θ(max( f ( n ) , g ( n ))), assuming both f and g are non-negative. Solution To show that f ( n ) + g ( n ) = O (max( f ( n ) , g ( n ))), see that f ( n ) + g ( n ) ≤ 2 max( f ( n ) , g ( n )) for all n . Thus we satisfy the definition of O with n 0 = 1 and c = 2. To show that f ( n ) + g ( n ) = Ω(max( f ( n ) , g ( n ))), see that max( f ( n ) , g ( n )) ≤ f ( n ) + g ( n ) if f, g are non-negative. Thus we statisfy the definition of Ω with n 0 = 1 and c = 1. f ( n ) + g ( n ) = O (max( f ( n ) , g ( n ))) and f ( n ) + g ( n ) = Ω(max( f ( n ) , g ( n ))) give us that f ( n ) + g ( n ) = Θ(max( f ( n ) , g ( n )))

Homework Assignment #3: September 15, 2023 (11:59pm) 4 In what way does a user of the system (i.e., an employer of a gig worker) influence the queue (i.e., what affordances does the user have)? Multiple possible correct answers here. But the most direct way the user has to influence the system is by rating gig workers. How might a user’s behavior change relative to α (that is, if the user knows that α is very small or very large, how might that impact what they do)? Again, multiple correct answers here. If I as a user know that α is small, then I am not likely to give ratings – they don’t have all that much impact, after all. If α is large, I know that my input is likely to have a significant impact on the system, so I might be more likely to rate workers.

Homework Assignment #3: September 15, 2023 (11:59pm) 5 Problem 4: Analyze [20 points] Consider a company that produces some number of widgets every day. The specific number fluc- tuates from day to day, but the company is interested in keeping track of the aggregate production of widgets over varying intervals of consecutive days. That is, they are interested in knowing, for pair of days, how many widgets were produced between those two days. Generically, the company has an array W that consists of n integers, where n is the number of days of production. The value W [ i ] is the number of widgets produced on the i th day. The company wants to compute a two dimensional ( n -by- n ) array A in which A [ i, j ] is the aggregate production from day W [ i ] to W [ j ] (including the widgets produced on days i and j ). (Note: A [ i, j ] is undefined if i ≥ j .) Below is a simple algorithm to solve this problem: i ← 1 n j ← i + 1 n Add entries W [ i ] through W [ j ] Store the result in A [ i, j ] 1. Give a function f ( n ) that is an asymptotically tight bound on the running time of this algorithm. Using the pseudocode above, argue that the algorithm is, in fact Θ( f ( n )). Θ( n 3 ). Why? The two for loops each run on the order of n times. Adding O ( n ) entries takes O ( n ) time. Therefore the total time is n 2 ∗ n or Θ( n 3 ). 2. Although the algorithm above is the most natural way to solve the problem, it contains some highly unnecessary sources of inefficiency. Give a different algorithm to solve this problem with an asymptotically better running time than the provided algorithm. i ← 1 n j ← i + 1 n A [ i, j ] = A [ i, j − 1] + W [ j ] 3. What is the running time of your new algorithm? Using your pseudocode, argue that your runtime is correct. Θ( n 2 ) 4. If the company wants to find all of the aggregates consisting of d days, where would they look in your two-dimensional array? Be as generic as possible (and state the answer relative to d ). These aggregates are all in the diagonal that starts at i = 1 and j = d .

Homework Assignment #3: September 15, 2023 (11:59pm) 7 Solution This is true because there are n 2 terms on both sides of the inequality, and each term on the left is smaller than each term on the right. Since half of log( n !) expanded is greater than ( n 2 ) log( n 2 ), ( n 2 ) log( n 2 ) ≤ log( n !) However, we need to prove the inequality for c 2 n log n ≤ log( n !), not for c 2 n log n 2 . Notice that: ( n 2 ) log( n 2 ) ≥ n 4 log( n ) This can be shown through algebra: ( n 2 ) log( n 2 ) ≥ n 4 log( n ) n 2 (log( n ) − log(2)) ≥ n 4 log( n ) We can use the log is base 2, so log(2) = 1 n 2 (log( n )) − n 2 ≥ n 4 log( n ) 2(log( n )) − 2 ≥ log( n ) log( n ) ≥ 2 This is true ∀ n ≥ 4. So, by transitivity, since ( n 2 ) log( n 2 ) ≤ log( n !) and ( n 4 ) log( n ) ≤ ( n 2 ) log( n 2 ) ∀ n ≥ 4 then it must be true that ( n 4 ) log( n ) ≤ log( n !) ∀ n ≥ 4 Therefore, we have proven log( n !) = Ω( n log( n )) and log( n !) = O ( n log( n )), so log( n !) = Θ( n log( n )) .

Homework Assignment #3: September 15, 2023 (11:59pm) 8 Problem 6: Create [20 points] Alan’s so impressed with your bolt sorting that you’ve been asked back to help with a stack of mismatched scrap wood. Specifically, Alan has a bunch of 2x4 pieces of wood left over from previous projects. They’re all different lengths. Alan would like to make best use of these leftovers for future projects. Construct an O ( n log n ) time algorithm to help Alan solve this problem: Given a project that requires a 2x4 of length t , does Alan have pieces of wood such that the need could be filled by exactly one or two left over pieces of wood (with no need to cut any wood)? Assume you have an array W that contains n distinct values that are the lengths of the leftover pieces of wood. Your algorithm should return simply “yes” or “no” to answer whether one or two of these pieces of wood will solve the project’s need. Sorting takes O ( n log n ) time. Then we have an O (log n ) operation (binary search among O ( n ) sorted elements) and a constant amount of O (1) operations, repeated O ( n ) times in the loop. Thus the complexity of the algorithm is O ( n log n ) + n ∗ O (log n ) + O (1) = O ( n log n ). Sort elements of W BinarySearch( t , W ) ‘yes’ i ← 1 n − 1 k = t − W [ i ] j = BinarySearch( k , W [ i + 1 : n ]) j = true ‘yes’‘no’