homework_2_solutions

CSE101: Design and Analysis of Algorithms (CSE, UCSD, Winter-2022) Homework-2 Solutions • Homework solutions should be neatly written or typed and turned in through Gradescope by 11:59pm on the due date. No late homeworks will be accepted for any reason. You will be able to look at your scanned work before submitting it. Please ensure that your submission is legible (neatly written and not too faint) or your homework may not be graded. • Students should consult their textbook, class notes, lecture slides, instructors, TAs, and tutors when they need help with homework. Students should not look for answers to homework problems in other texts or sources, including the internet. Only post about graded homework questions on Piazza if you suspect a typo in the assignment, or if you don’t understand what the question is asking you to do. Other questions are best addressed in office hours. • Your assignments in this class will be evaluated not only on the correctness of your answers, but on your ability to present your ideas clearly and logically. You should always explain how you arrived at your conclusions, using mathematically sound reasoning. Whether you use formal proof techniques or write a more informal argument for why something is true, your answers should always be well-supported. Your goal should be to convince the reader that your results and methods are sound. • For questions that require pseudocode, you can follow the same format as the textbook, or you can write pseudocode in your own style, as long as you specify what your notation means. For example, are you using “=” to mean assignment or to check equality? You are welcome to use any algorithm from class as a subroutine in your pseudocode. There are 4, questions for a total of 100, points. 1. (20 points) Give the fastest dynamic programming possible, an explanation of correctness and its time analysis. Given an array of integers, A [1 ..n ], find the subset S of positions so that no two consecutive numbers i and i + 1 are both in S , which maximizes ∑ i ∈ S A [ i ]. Solution: 1. Subproblems: Let P [ i ] be the pair ( sum, in ), where sum is the max sum of non-contiguous elements in A [1 ..i ], and in is if A [ i ] is in the set of non-contiguous elements in A [1 ..i ] that makes up the max sum. 2. Base cases: • P [ - 1] = P [0] = (0 , False) since there are no elements. 3. Recurrence relation: • Case 1: If A [ i ] is part of the sum, then we can’t use A [ i - 1]. So P [ i ] = ( A [ i ] + P [ i - 2] .sum, True). • Case 2: If A [ i ] is not part of the sum, then the sum consists of elements in A [1 ..i - 1]. So P [ i ] = ( P [ i - 1] .sum, False). We take the max P [ i ] .sum from the 2 cases, so P [ i ] = ( A [ i ] + P [ i - 2] .sum, True) if A [ i ] + P [ i - 2] .sum > P [ i - 1] .sum , and P [ i ] = ( P [ i - 1] .sum, False) else. 1 of 9

CSE101: Design and Analysis of Algorithms (CSE, UCSD, Winter-2022) Homework-2 Solutions 4. Ordering of subproblems: Each subproblem depends on the two subproblems before it, so we solve the subproblems from left to right, in increasing values of i . 5. Final output: Let S = ∅ be the output, and let j = n . While j > 0, if P [ j ] .in is True, add j to S and set j = j - 2, else just set j = j - 1. Return S . 6. Pseudocode: MaxNonContiguousSum( A [1 ..n ]: array of integers): (1) Declare P [ - 1 ..n ] (2) P [ - 1] ← (0 , False), P [0] ← (0 , False) (3) For i = 1 to n : (4) If A [ i ] + P [ i - 2] .sum > P [ i - 1] .sum then P [ i ] ← ( A [ i ] + P [ i - 2] .sum, True) (5) Else P [ i ] ← ( P [ i - 1] .sum, False) (6) j ← n , S ← ∅ (7) While j > 0: (8) If P [ j ] .in = True then S ← S ∪ { j } and j ← j - 2 (9) Else j ← j - 1 (10) Return S 7. Runtime: There are O ( n ) subproblems, solving each takes O (1) to make the comparison and saving the new pair. Declaring P [ - 1 ..n ] takes O ( n ). Constructing and returning S takes O ( n ). Overall the algorithm takes O ( n ) time. 2. (20 points) Consider the following problem. You wish to purchase (at least) n identical gizmos. Gizmos come in packages of different sizes and different prices. You can buy any number of packages of each size, as long as the total number is at least n . You wish to find the minimum total price of such a set of packages. The input is given as n and an array Packages [1 ..m ], where each Package [ i ] has a positive integer field Package [ i ] .size and a positive real field Package [ i ] .price giving the number of gizmos in the package and the price of the package. A recursive algorithm to solve this problem is: BestPrice[ n : positiveinteger, Packages [1 ..m ] : array of pairs ( size : integer, price : real).] 1. MinPrice ← inf; 2. For d = 1 to m do: 3. begin; 4. IF Packages [ d ] .size ≥ n THEN TempPrice ← Packages [ d ] .price 5. ELSE TempPrice ← Packages [ d ] .price + BestPrice ( n - Packages [ d ] .size, Packages ); 6. IF TempPrice < MinPrice THEN MinPrice ← TempPrice ; 7. end; 2 of 9

CSE101: Design and Analysis of Algorithms (CSE, UCSD, Winter-2022) Homework-2 Solutions We want the minimum of all the above cases, so M [ i ] = min 1 ≤ j ≤ m ( Package [ j ] .price + δ i,j ), where δ i,j = 0 if Package [ j ] .size ≥ i , and δ i,j = M [ i - Package [ j ] .size ] else. 4. Ordering the subproblems: M [ i ] depends on all M [0] to M [ i - 1], so we solve the array from left to right, in increasing values of i . 5. Final output: We output M [ n ], which is the minimum cost to buy at least n identical gizmos from any of the m packages. 6. Pseudocode (this is the only required part): BestPriceDP( n : minimum gizmos, Packages [1 ..m ]: array of pairs ( size, price )): (1) Declare M [0 ..n ] (2) M [0] ← 0 (3) For i = 1 to n : (4) M [ i ] ← ∞ (5) For j = 1 to m : (6) AdditionalCost ← 0 (7) If Package [ j ] .size < i then AdditionalCost ← M [ i - Package [ j ] .size ] (8) M [ i ] ← min( M [ i ] , Package [ j ] .price + AdditionalCost ) (9) Return M [ n ] Part 4: Runtime We have O ( n ) subproblems, each taking O ( m ) to take the minimum of m cases. It takes O ( n ) to declare the array M , and O (1) to return the final output. Overall the algorithm’s runtime is O ( mn ). Part 5: Array M produced using part 1’s input: i 0 1 2 3 4 5 6 M [ i ] 0 6 6 8 12 12 16 3. (20 points) Often, even when greedy algorithms do not find optimal solutions, they are used as heuristics. An independent set in an undirected graph G is a set of nodes I so that no edge has both endpoints in I . In other words, if { u, v } ∈ E , then either u 6∈ I or v 6∈ I . The maximum independent set problem is , given G , find an independent set of the largest possible size. Implement a greedy algorithm for maximum independent set based on including nodes of smallest degree. Test it on random graphs where each possible edge is in the graph with probability 1 / 2. What is the average size of the independent set it finds for graphs of different sizes? (Try n as many powers of 2 as you can.) How do you conjecture the size will grow as a function of n ? Solution: The greedy independent set algorithm should be as follows: GreedyIndependentSet( G ( V, E )): (1) S ← {} (2) While | V | > 0: (3) v ← vertex with lowest degree 4 of 9

CSE101: Design and Analysis of Algorithms (CSE, UCSD, Winter-2022) Homework-2 Solutions (4) S ← S ∪ { v } (5) Remove v and all its neighbors from V : V ← V - ( { v } ∪ { u | ( u, v ) ∈ E } ) (6) Return S For this problem, you can generate a graph (represented by an adjacency list or adjacency matrix) with n = 2 m vertices (for increasing values of m , e.g. from 2 to 10), and each edge has a 1 / 2 probability of being in the graph. Then you can run the above algorithm to get the independent set of that random graph. Run this on multiple random graphs (for example, 100) for each value of m , then record the average size of the independent set for each m . The result of our implementation is as follows: Number of vertices 4 8 16 32 64 128 256 512 1024 Average independent set size 2.41 3.57 4.77 6.09 7.35 8.73 9.97 11.11 12.34 We observe that for graphs with n = 2 m vertices, on average the independent set size obtained by the greedy heuristic is approximately O ( m ). This implies that for a graph with n vertices, the size of the independent set obtained by the greedy heuristic is O (log( n )) on average. Our implementation is as follows: import random import matplotlib.pyplot as plt # function for creating random graphs def create_random_graph (num_vertices): adj_list = dict () # adjacency list for u in range (num_vertices): adj_list[u] = [] for u in range (num_vertices): for v in range (u +1 , num_vertices): if random . uniform( 0 , 1 ) > 0.5 : # 1/2 probability adj_list[u] . append(v) adj_list[v] . append(u) return adj_list 5 of 9

CSE101: Design and Analysis of Algorithms (CSE, UCSD, Winter-2022) Homework-2 Solutions # plot output plt . style . use( 'classic' ) plt . plot(num_vertex, avg_is_size) plt . xlabel( "Number of vertices" ) plt . ylabel( "Average independent set size" ) plt . show() 4. (40 points) Consider the following problem: You are baby-sitting n children and have m > n cookies to divide between them. You must give each child exactly one cookie (of course, you cannot give the same cookie to two different children). Each child has a greed factor g i , 1 ≤ i ≤ n which is the minimum size of a cookie that the child will be content with; and each cookie has a size s j , 1 ≤ j ≤ m . Your goal is to maximize the number of content children, i.e.., children i assigned a cookie j with g i ≤ s j . Give a correct greedy algorithm for this problem (10 points), prove that it finds the optimal solution (20 points), and give an efficient implementation (10 points). Solution: Greedy strategy: For the greediest child, if the largest cookie makes that child content, give them the largest cookie, else give them the smallest cookie. Repeat for the remaining children and remaining cookies. Proof of correctness: Without loss of generality, assume that the children’s greed factor g 1 ..g n are sorted in decreasing order. We proceed with an exchange argument. Let G be the greedy choice, that is, the size of the cookie assigned to child with greed factor g 1 as determined by the greedy strategy. Let OS = { ( g 1 , s σ (1) ) , ( g 2 , s σ (2) ) , ..., ( g n , s σ ( n ) ) } be a cookie assignment that doesn’t make the greedy decision, that is, G 6 = s σ (1) . Create a new solution OS 0 from OS that does make the greedy choice as follows: • Case 1: If G ∈ OS , but is assigned to child i > 1 instead of child 1, swap the positions of G and s σ (1) in OS to create OS 0 = { ( g 1 , G ) , ..., ( g i , s σ (1) ) , ... } . • Case 2: If G 6∈ OS , replace s σ (1) with G to create OS 0 = { ( g 1 , G ) , ( g 2 , s σ (2) ) , ..., ( g n , s σ ( n ) ) } . We want to show that OS 0 is a valid solution, that is, every child is assigned a different cookie: • Case 1: By the validity of OS , { s σ (1) , s σ (2) , ..., s σ ( n ) } are n different cookies. OS 0 uses the same cookies as OS , but assigned differently, so it still uses n different cookies. • Case 2: By the validity of OS , { s σ (1) , s σ (2) , ..., s σ ( n ) } are n different cookies. G 6∈ OS in this case, so swapping s σ (1) for G still results in n different cookies. In all cases, OS 0 also uses n different cookies. So OS 0 is a valid solution. We next want to show that OS 0 is at least as good as OS , that is, the number of content children in OS 0 is at least as many as in OS . First, if the largest cookie can satisfy the first child, then G is the largest cookie. We have the following: • Case 1: Let G = s σ ( i ) . By assumption, g 1 ≥ g i , and by the nature of the greedy choice, G ≥ g 1 . So G satisfies the i th child, and by swapping G and s σ (1) , G still satisfies the first child. If s σ (1) satisfies the first child, then it must also satisfy the i th child, and if it doesn’t then it might still satisfy the i th child. The remaining cookie assignments are left unchanged, so the number of satisfied children there remain the same. 7 of 9

CSE101: Design and Analysis of Algorithms (CSE, UCSD, Winter-2022) Homework-2 Solutions • Case 2: By the nature of the greedy choice, G ≥ g 1 , so by replacing s σ (1) with G , if s σ (1) ≥ g 1 , then the first child remains satisfied, and if not, then the first child is now satisfied. The remaining cookie assignments are left unchanged, so the number of satisfied children there remain the same. Else, if the largest cookie cannot satisfy the first (greediest) child, then G is the smallest cookie. We have the following: • Case 1: Let G = s σ ( i ) . By the nature of the greedy choice, G ≤ s σ (1) . If the largest cookie cannot satisfy the first child, then no cookie can satisfy them, so s σ (1) < g 1 . So replacing s σ (1) with G still results in the first child not being satisfied. If the i th was satisfied with G , then they will also be satisfied by s σ ( i ) since G ≤ s σ (1) . If they weren’t satisfied with G , then they might still be satisfied by s σ (1) . The remaining cookie assignments are left unchanged, so the number of satisfied children there remain the same. • Case 2: By the nature of the greedy choice, G ≤ s σ (1) . If the largest cookie cannot satisfy the first child, then no cookie can satisfy them, so s σ (1) < g 1 . So replacing s σ (1) with G still results in the first child not being satisfied. The remaining cookie assignments are left unchanged, so the number of satisfied children there remain the same. In all cases, OS 0 has at least as many satisfied children as OS . So OS 0 is at least as good as OS . Next, we prove the optimality of the greedy strategy with a proof by induction. Base case : If there is only one child, then for any number of cookies m > 1, the greedy strategy is optimal, since if the largest cookie satisfies that child, then all children are satisfied, but if not, then the child can never be satisfied. Inductive hypothesis : Assume for k ≥ 1 children and m > k cookies that the greedy solution GSol is optimal, that is, it satisfies the most number of children. We want to show that for k + 1 children and m 0 > k + 1 cookies that GSol is also optimal. Inductive step : Let S = { s 1 , ..., s m 0 } be the set of cookie sizes, and C = { g 1 , ..., g k +1 } be the set of children’s greed factors. Without loss of generality, assume C is sorted in decreasing order. For some cookie assignment AS , we use the notation | AS | to denote the number of satisfied children in AS . Let OS be any valid cookie assignment. By the exchange argument, we know that there exists a solution OS 0 that makes the greedy choice, at is at least as good as OS . Let S 0 = S - { G } , C 0 = C - { g 1 } , and Sol ( S 0 , C 0 ) be any valid solution for S 0 and C 0 . Since C has k children and S has m > k cookies, by the inductive hypothesis, we know that the greedy solution GSol ( S 0 , C 0 ) is optimal for cookie sizes S 0 and children’s greed factors C 0 . Because of this, we have | Sol ( S 0 , C 0 ) | ≤ | GSol ( S 0 , C 0 ) | . Then: | OS | ≤ | OS 0 | = |{ ( g 1 , G ) } ∪ Sol ( S 0 , C 0 ) | ≤ |{ ( g 1 , G ) } ∪ GSol ( S 0 , C 0 ) | = | GSol ( S, C ) | Therefore, GSol is also optimal for k + 1 children and m 0 > k + 1 cookies. By induction, the greedy strategy is optimal for n children and m > n cookies. Therefore the greedy strategy is always optimal. Efficient implementation: Cookie( s [1 ..m ]: array of cookie sizes, g [1 ..n ]: array of greed factors): (1) Sort s [1 ..m ] and g [1 ..n ] in decreasing order 8 of 9