H2 Solution

1 CS 6212 Fall 2023 Youssef Homework 2 Problem 1 : (10 points) a. Show step by step how the heapsort algorithm sorts the array 27, 13, 56, 35, 48, 8, 18, 67, 5, 62, 7 starting from the min-heap you built in homework 1 (Problem 4a) for the same array. Let us denote B[1..n] as the sorted array. Step 0: A[i] 5 7 13 27 8 56 18 67 35 62 48 B[i] Step 1: A[i] 7 8 13 27 48 56 18 67 35 62 B[i] 5 Step 2: A[i] 8 27 13 35 48 56 18 67 62 B[i] 5 7 Step 3: A[i] 13 27 18 35 48 56 62 67 B[i] 5 7 8 Step 4: A[i] 18 27 56 35 48 67 62 B[i] 5 7 8 13 Step 5: A[i] 27 35 56 62 48 67 B[i] 5 7 8 13 18

2 Step 6: A[i] 35 48 56 62 67 B[i] 5 7 8 13 18 27 Step 7: A[i] 48 62 56 67 B[i] 5 7 8 13 18 27 35 Step 8: A[i] 56 62 67 B[i] 5 7 8 13 18 27 35 48 Step 9: A[i] 62 67 B[i] 5 7 8 13 18 27 35 48 56 Step 10: A[i] 67 B[i] 5 7 8 13 18 27 35 48 56 62 Step 11: A[i] B[i] 5 7 8 13 18 27 35 48 56 62 67 b. Show step by step how the quicksort algorithm sorts the same array 27, 13, 56, 35, 48, 8, 18, 67, 5, 62, 7. Indicate at each step what the partitioning element is. We always take the 1st element as a pivot and omit the steps for sorting A[p:q] when p=q. Color: red signified that location where the pivot ends up. Yellow highlight means that the corresponding number has taken its final position in the sorted array.

4 We highlight the intervals where Mergesort is applied using red and bold font. To simplify the presentation, (1) we simply assume that sorting is in plac e, i.e., the input and output arrays are assumed to be A, and (2) we skip calls to Mergesort when the input size is 1. A[i] 27 13 56 35 48 8 18 67 5 62 7 Mergesort(A[1:11]) → Mergesort(A[1:6]) → Mergesort(A[1:3]) → Mergesort(A[1:2]): A[i] 13 27 56 35 48 8 18 67 5 62 7 Mergesort(A[1:11]) → Mergesort(A[1:6]) → Mergesort(A[3:3]) : A[i] 13 27 56 35 48 8 18 67 5 62 7 Mergesort(A[1:11]) → Mergesort(A[1:6]) → Mergesort(A[6:6]) : A[i] 13 27 56 8 35 48 18 67 5 62 7 Mergesort(A[1:11]) → Mergesort(A[1:6]) → Merge(A[1:3],A[4:6]): A[i] 8 13 27 35 48 56 18 67 5 62 7 Mergesort(A[1:11]) → Mergesort(A[7:11]) → Mergesort(A[7:9]) → Mergesort(A[7:8]): A[i] 8 13 27 35 48 56 18 67 5 62 7 Mergesort(A[1:11]) → Mergesort(A[7:11]) → Mergesort(A[7:9]) → Merge(A[7:8],A[9]): A[i] 8 13 27 35 48 56 5 18 67 62 7 Mergesort(A[1:11]) → Mergesort(A[7:11]) → Mergesort(A[10:11]): A[i] 8 13 27 35 48 56 5 18 67 7 62 Mergesort(A[1:11]) → Mergesort(A[7:11]) → Merge(A[7:9], A[10:11]): A[i] 8 13 27 35 48 56 5 7 18 62 67 Mergesort(A[1:11]) → Merge(A[1:6], A[7:11]): A[i] 5 7 8 13 18 27 35 48 56 62 67 d. Show step by step how the insertion sort algorithm sorts the same array. (This algorithm sorts by repeated insertion into a (initially empty) sorted array.) We highlight the sorted output subarray using red and bold font.

5 A[i] 27 13 56 35 48 8 18 67 5 62 7 A[i] 13 27 56 35 48 8 18 67 5 62 7 A[i] 13 27 56 35 48 8 18 67 5 62 7 A[i] 13 27 35 56 48 8 18 67 5 62 7 A[i] 13 27 35 48 56 8 18 67 5 62 7 A[i] 8 13 27 35 48 56 18 67 5 62 7 A[i] 8 13 18 27 35 48 56 67 5 62 7 A[i] 8 13 18 27 35 48 56 67 5 62 7 A[i] 5 8 13 18 27 35 48 56 67 62 7 A[i] 5 8 13 18 27 35 48 56 62 67 7 A[i] 5 7 8 13 18 27 35 48 56 62 67 e. Show step by step how selection sort sorts the same array. (This finds the minimum first, then the 2nd min, then the 3rd min, and so on. It has nothing to do with quick-select.) At each step, we highlight the selected minimum element in red and bold, and the swapped element with an underline. The output subarray is shown with yellow highlight. A[i] 27 13 56 35 48 8 18 67 5 62 7 A[i] 5 13 56 35 48 8 18 67 27 62 7 A[i] 5 7 56 35 48 8 18 67 27 62 13

7 a. procedure ClosestNeighborsAndMinMax(input: A[1:n], low, high; outputs: m, M, i, j) //The input is A[low:high]; the output is: m is min(A[low:high]); M is max(A[low:high]) , i is // the index of the left element of the closest neighbors, and j= i+1 is the // index of the right element of the pair. begin // Base case: single element if low == high then m= A[low]; M=A[high]; i=none; j=none; return ; endif // Base case: two elements if high - low == 1 then m= A[low]; M=A[high]; i=low; j=high; return ; endif mid = (low + high) // 2 ClosestNeighborsAndMinMax(A, low, mid; minL, maxL, iL, jL); ClosestNeighborsAndMinMax(A, mid+1, high; minR, maxR, iR, jR); // Min and Max of A[low:high] next m= min(minL, minR) M = max(maxL, maxR) // Closest neighbors crossDist = abs(A[mid] - A[mid + 1]) distL=abs(A[iL]-A[jL]); distR=abs(A[iR]-A[jR]); minDist = min(distL, distR, crossDist) // Determine closest neighbors if minDist == crossDist then i=iL; j=jL; elseif minDist == distL then i=iR; j=jR; else i=mid; j=mid+1; endif end ClosestNeighborsAndMinMax Of course, the caller of this procedure would typically call ClosestNeighborsAndMinMax(A[1:n,1,n]; outputs: m, M, i,j), i.e., low=1 and high=n.

8 b. Time Complexity: The base step and the merge take constant time c. Each recursive call is made on half the input. Therefore, 𝑇𝑇 ( 𝑛𝑛 ) = 2 𝑇𝑇 � 𝑛𝑛 2 � + 𝑐𝑐 . We have seen this recurrence relation before, and its solution is 𝑇𝑇 ( 𝑛𝑛 ) = 𝑂𝑂 ( 𝑛𝑛 ). Problem 3 : (20 points) Let 𝐴𝐴 [1: 𝑛𝑛 ] be an array of real numbers. A subarray of 𝐴𝐴 is any sequence 𝐴𝐴 [ 𝑖𝑖 : 𝑗𝑗 ] made up of 𝐴𝐴 [ 𝑖𝑖 ], 𝐴𝐴 [ 𝑖𝑖 + 1], … , 𝐴𝐴 [ 𝑗𝑗 ] where 𝑖𝑖 ≤ 𝑗𝑗 . The sum of the subarray 𝐴𝐴 [ 𝑖𝑖 : 𝑗𝑗 ] is the value 𝐴𝐴 [ 𝑖𝑖 ] + 𝐴𝐴 [ 𝑖𝑖 + 1] + ⋯ + 𝐴𝐴 [ 𝑗𝑗 ] . We are interested to find the maximum-sum subarray, i.e., the subarray that has the largest sum in A. a. Write a divide-and-conquer algorithm that takes 𝐴𝐴 [1: 𝑛𝑛 ] and returns maximum-sum subarray and its sum, that is, it returns the following output: (1) the starting index 𝑖𝑖 , (2) the ending index 𝑗𝑗 , and (3) the sum, of the maximum-sum subarray. In case of ties, break the tie arbitrarily. b. Analyze the time complexity of your algorithm. Note: For many divide-and-conquer algorithms, you may need to have the algorithm compute more outputs than initially stated, in order for the merge step to be doable efficiently. Note: Again for full credit, your algorithm has to be as efficient as possible. Solution : a. In this problem, it is not enough to find the max-sum subarray in the left half and the max-sum subarray in the right half of the input array A. That is because the max-sum subarray of A[1:n] may be a cross-over subarray that crosses the boundaries 𝐴𝐴 [ 𝑛𝑛 2 ] and A[ 𝑛𝑛 2 + 1] . Therefore, the merge procedure in this problem must have three max-sum subarrays available, namely, the max-sum cross-over subarray, and the two max-sum subarrays of the left and right halves of A, and then it selects the largest sum of the three. Now, observe that every cross-over subarray consists of two contiguous portions: a 1 st portion is a trailing portion of the left half of A (that portion is referred to as a suffix of A[1: 𝑛𝑛 2 ]), and a 2 nd portion is a leading portion of the right half of A (that portion is referred to as a prefix of A[ 𝑛𝑛 2 + 1 : 𝑛𝑛 ]). Observe also that in the max-sum cross-over subarray, the left portion must be a max-sum suffix of A[1: 𝑛𝑛 2 ], and the right portion i=must be a max-sum prefix of A[ 𝑛𝑛 2 + 1 : 𝑛𝑛 ]. This can be proved easily by contradiction. One more observation. In the Merge process, to find the max-sum prefix of A[1: 𝑛𝑛 ], we need to look at both the max-sum prefix of the left half A[1: 𝑛𝑛 2 ], and the max-sum cross-over prefix, which is A[1: 𝒏𝒏 𝟐𝟐 ]+the max-sum prefix of the right half A[ 𝒏𝒏 𝟐𝟐 + 𝟏𝟏 : 𝒏𝒏 ] . To make such computation doable in the Merge process, the algorithm has to compute the sum of the left half A[1: 𝑛𝑛 2 ].

10 if (SubSum == SubSumL) then Start=StartL; End=EndL; elseif (SubSum == SubSumR) then Start=StartR; End=EndR; else // SubSum is the cross-over sum Start= SuffixStartL; End= PrefixEndR; endif // compute the sum of the whole input array A[low:high] WholeSum= WholeSumL+ WholeSumR; // Compute the max-sum prefix of the whole input array A[low:high] PrefixSum=max(PrefixSumL, WholeSumL+ PrefixSumR); if (PrefixSum== PrefixSumL) then PrefixEnd = PrefixEndL; else PrefixEnd = PrefixEndR; // cross-over prefix endif // Compute the max-sum suffix of the whole input array A[low:high] SuffixSum=max(SuffixSumR, WholeSumR+ SuffixSumL); if (SuffixSum == SuffixSumR) then SuffixStart = SuffixStartR; else SuffixStart = SuffixStartL; // cross-over suffix endif end findMaxSubArray b. Time Complexity. Observe that the Merge process takes a constant time c! Therefore, the time of the algorithm satisfies 𝑇𝑇 ( 𝑛𝑛 ) = 2 𝑇𝑇 � 𝑛𝑛 2 � + 𝑐𝑐 . Again, we have seen this recurrence relation before, and its solution is 𝑇𝑇 ( 𝑛𝑛 ) = 𝑂𝑂 ( 𝑛𝑛 ). Problem 4 : (10 points) Consider this instance of the knapsack problem: The weights are: 12, 8, 16, 4, 20, 28 The prices are: 48, 24, 80, 24, 40, 28 The capacity is: M=28. Find the greedy the solution for this problem, showing the process step by step. Solution : We use a greedy approach by prioritizing items according to "price-per-weight" ratio. The ratios are: [4, 3, 5, 6, 2, 1]

11 Then, we pick the items with the following steps: 1. Pick 4 th item with weight 4 and price 24, M = 28-4=24, obtained profit = 24 2. Pick 3 rd item with weight 16 and price 80, M = 24-16=8, obtained profit = 24+80=104 3. Pick 1 st item with weight 8 out of 12 (so 𝑥𝑥 1 = 8 12 = 2 3 ) M = 8-8=0, total obtained profit = 104 + 2 3 ∗ 48 = 104 + 32 = 136 . Therefore, the solution is: 𝑥𝑥 1 = 2 3 , 𝑥𝑥 2 = 0, 𝑥𝑥 3 = 1, 𝑥𝑥 4 = 1, 𝑥𝑥 5 = 0, 𝑥𝑥 6 = 0. Total profit: 136. Problem 5 : (20 points) Let G=(V,E) be the following weighted graph: V={1,2,3,4,5,6,7,8,9,10,11,12} E={[(1,7) 2], [(1,8) 6], [(1,12) 5], [(7,12) 1], [(8,12) 2], [(12,6) 3], [(2,6) 7], [(2,7) 4], [(7,8) 7], [(12,5) 2], [(6,10) 5], [(5,10) 2], [(9,10) 1], [(9,4) 2], [(10,11) 2.5], [(11,4) 2.5], [(3,6) 2], [(3,9) 2.3]}, where [(i,j) a] means that (i,j) is an edge of weight a. a. Use the greedy method (Kruskal’s algorithm) to find a minimum spanning tree of G. Show the tree after every step of the algorithm. b. Using the greedy Dijkstra’s single-source shortest-path algorithm, find the distances between node 1 and all the other nodes. Show the values of the DIST array at every step. c. Show the actual shortest paths of part (b). Note that these paths together form a spanning tree of G. Is this tree a minimum spanning tree? Solution : a. We show the original graph in blue color and the MST in red and yellow colors. We indicate which edge is being considered in every step by red color, and if the edge is to be discarded, change it to a dashed black line.

13

14

16

17 b. We denote the unvisited node with minimal distance to node 1 at each step by red color. Node ID 1 2 3 4 5 6 7 8 9 10 11 12 DIST[i] 0 inf inf inf inf inf 2 6 inf inf inf 5 Node ID 1 2 3 4 5 6 7 8 9 10 11 12 DIST[i] 0 6 inf inf inf inf 2 6 inf inf inf 3 Node ID 1 2 3 4 5 6 7 8 9 10 11 12 DIST[i] 0 6 inf inf 5 6 2 5 inf inf inf 3 Node ID 1 2 3 4 5 6 7 8 9 10 11 12 DIST[i] 0 6 inf inf 5 6 2 5 inf 7 inf 3

19 Problem 6 : (20 points) You are given a list 𝐴𝐴 of activities. Each activity 𝑎𝑎 is represented by a pair ( 𝑎𝑎 1 , 𝑎𝑎 2 ) where 𝑎𝑎 1 is the start time of 𝑎𝑎 , and 𝑎𝑎 2 is the end time of 𝑎𝑎 . Your goal is to select the maximum number of non-overlapping activities that you can participate in, given that you can only participate in one activity at a time. We will use the greedy method for solving this problem. a. Consider the following greedy selection policy: select the activity with the earliest starting time; in case of ties, select the one with the shortest duration among the tying activities. Prove by a counter-example that this method doesn’t guarantee optimality. b. Give a greedy policy that is guaranteed to yield an optimal solution, and prove optimality. c. Illustrate your policy on 𝐴𝐴 = {(1,5), (6,10), (3,8), (14,17), (9,13), (12,15), (7,11)}. Solution : a. Let’s consider A = [(1,10), (2,3),(4,5)]. The greedy selection will select [(1,10)] while a better selection is [(2,3),(4,5)] because it has more activities. This proves that this greedy method does not guarantee optimality. b. Select the activity with the earliest ending time next that doesn’t overlap with any previously chosen activities ; in case of ties, select the one with the shortest duration among the tying activities. Proof of optimality: Denote the greedy solution as = ( 𝑠𝑠 1 , 𝑠𝑠 2 , 𝑠𝑠 3 , … ) , and the optimal solution as 𝑂𝑂 = ( 𝑜𝑜 1 , 𝑜𝑜 2 , 𝑜𝑜 3 , … ). If 𝑆𝑆 = 𝑂𝑂 , there is nothing to prove. Assume that 𝑆𝑆 ≠ 𝑂𝑂 .

20 Then there exists some index such that 𝑠𝑠 𝑖𝑖 ≠ 𝑜𝑜 𝑖𝑖 , and assume 𝑖𝑖 is the first such index. That is, 𝑜𝑜 1 = 𝑠𝑠 1 , 𝑜𝑜 2 = 𝑠𝑠 2 , … , 𝑜𝑜 𝑖𝑖−1 = 𝑠𝑠 𝑖𝑖−1 and 𝑠𝑠 𝑖𝑖 ≠ 𝑜𝑜 𝑖𝑖 . Replace 𝑜𝑜 𝑖𝑖 by 𝑠𝑠 𝑖𝑖 in the optimal solution and get a new solution 𝑂𝑂 = ( 𝑜𝑜 1 , 𝑜𝑜 2 , 𝑜𝑜 3 , … , 𝑜𝑜 𝑖𝑖−1 , 𝑠𝑠 𝑖𝑖 , 𝑜𝑜 𝑖𝑖+1 , … ) = ( 𝑠𝑠 1 , 𝑠𝑠 2 , 𝑠𝑠 3 , … , 𝑠𝑠 𝑖𝑖 , 𝑜𝑜 𝑖𝑖+1 , … ) . Since 𝑠𝑠 𝑖𝑖 has a smaller ending ending time for every activity except the first activities in and , 𝑠𝑠 𝑖𝑖 does not overlap with any other activities in , and is still a valid optimal solution (valid because all the activities in are still non-overlapping, and optimal because both 𝑂𝑂 and 𝑂𝑂′ have the same number of activities and 𝑂𝑂 has a maximum number of activities). By repeating the above step until there exists no index such that , we convert the optimal solution to the greedy solution without changing the number of selected activities. Therefore, the greedy solution is optimal. Q.E.D. c. After sorting the activities we have: . The greedy selection yields selections: . Bonus Problem : (5 points) Let 𝐴𝐴 [1: 𝑛𝑛 ] be an array of real numbers. An inversion in 𝐴𝐴 is a pair ( 𝑖𝑖 , 𝑗𝑗 ) where 𝑖𝑖 < 𝑗𝑗 and 𝐴𝐴 [ 𝑖𝑖 ] > 𝐴𝐴 [ 𝑗𝑗 ] . A split inversion of 𝐴𝐴 is an inversion ( 𝑖𝑖 , 𝑗𝑗 ) such that 𝑖𝑖 is in the left half of 𝐴𝐴 and 𝑗𝑗 is in the right half of 𝐴𝐴 . a. Assume for now that A is made of two sorted halves. Write an algorithm that computes and returns the number of split inversions in A, and also merges the two halves into a sorted array. Analyze the time complexity of your algorithm. b. Now, 𝐴𝐴 is a totally arbitrary array of real numbers. Write a divide-and-conquer algorithm that sorts 𝐴𝐴 and returns the total number of inversions. Analyze the time complexity of your algorithm. Solution : a. Assume the first half 𝐴𝐴 � 1: 𝑛𝑛 2 � of the array is sorted in increasing order, and so is the second half 𝐴𝐴 [ 𝑛𝑛 2 + 1 . . 𝑛𝑛 ] . We can observe that every inversion is a split inversion. In addition, we note that if is an inversion, every is a split inversion for all 𝑘𝑘 where 𝑖𝑖 ≤ 𝑘𝑘 ≤ 𝑛𝑛 2 . Thus, we conclude the following algorithm, which is a slight modification of the Merge procedure of MergeSort: Procedure MergeAndCountSplitInversions( input : C[1:n]; output : B, inversions) // merges sorted C[1: 𝑛𝑛 2 ] and sorted C[ 𝑛𝑛 2 +1:n] into B[1:n], and count split inversions. // It is identical to Merge(…) in MergeSort except for the yellow-highlighted line begin int i=1, j= 𝑛𝑛 2 +1, k=1;