Lab_09 CS171

pdf

School

Drexel University *

*We aren’t endorsed by this school

Course

171

Subject

Computer Science

Date

Jan 9, 2024

Type

pdf

Pages

Uploaded by DukeExplorationRhinoceros41

CS 171 - Lab 9 Professor Mark W. Boady and Professor Adelaida Medlock Content by Mark Boady, Drexel University Detailed instructions to the lab assignment are found in the following pages. • Complete all the exercises and type your answers in the space provided. What to submit: • Lab sheet in PDF format. • A screenshot with your code for question 8. Submission must be done via Gradescope • Please make sure you have tagged all questions and added your teammates if any • We only accept submissions via Gradescope. Student Name: Aryan Dixit User ID (abc123): 14479032 Possible Points: 103 Your score out of 103 : Lab Grade on 100% scale: Graded By (TA Signature):

CS 171 Lab 9 Week 9 2 Question 1: 9 points In this lab, we will look at two different methods of sorting. First, we will examine how the algorithms work. In the final question, you will code each of the algorithms. (a) (1 point) Sort the following list: [17, 12, 10, 15, 0, 14, 13, 5, 0, 6] [0, 0, 5, 6, 10, 12, 13, 14, 15, 17] (b) (1 point) Sort the following list: [11, 0, 10, 12, 3, 17, 11, 15, 7, 8] [0, 3, 7, 8, 10, 11, 11, 12, 15, 17] (c) (1 point) Sort the following list: [10, 19, 17, 0, 16, 3, 20, 14, 9, 1] [0, 1, 3, 9, 10, 14, 16, 17, 19, 20] (d) (1 point) Sort the following list: [7, 16, 20, 0, 20, 10, 11, 18, 0, 1] [0, 0, 1, 7, 10, 11, 16, 18, 20, 20] (e) (5 points) Think about how your group sorted the lists. Write out instructions for How to Sort a List . Start with the first item in the list. Compare it to each other item. If a smaller item is found, switch it with the first. Repeat for each item, moving through the list. Continue until the entire list is sorted in ascending order.

CS 171 Lab 9 Week 9 3 The first Algorithm we will look at is based on merging . If we have two lists that are already sorted, it should be easy to merge them into one new list. Let’s say we start with A = [1 , 3 , 5] B = [2 , 6 , 9] We can merge these arrays by looking at the first elements and picking the smallest. function Merge (A, B) C = [] while len(A) > 0 and len(B) > 0 do if A[0] < B[0] then Add A[0] to end of C Remove A[0] from A else Add B[0] to end of C Remove B[0] from B end if end while while len(A) > 0 do Move Remaining A values to C end while while len(B) > 0 do Move Remaining B values to C end while return C end function The steps taken to merge the two lists are shown in the table below. A B Comparison C [1 , ··· ] [2 , ··· ] 1 < 2 [1] [3 , ··· ] [2 , ··· ] 3 < 2 [1 , 2] [3 , ··· ] [6 , ··· ] 3 < 6 [1 , 2 , 3] [5 , ··· ] [6 , ··· ] 5 < 6 [1 , 2 , 3 , 5] [] [6 , ··· ] len ( B ) > 0 [1 , 2 , 3 , 5 , 6] [] [9 , ··· ] len ( B ) > 0 [1 , 2 , 3 , 5 , 6 , 9] [] [] Return [1 , 2 , 3 , 5 , 6 , 9]

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

CS 171 Lab 9 Week 9 4 Question 2: 19 points (a) (3 points) Is it possible for both the following while statements to run, or will at most one run during a specific call to the function? Explain your answer. while len(A) > 0 do Move Remaining A values to C end while while len(B) > 0 do Move Remaining B values to C end while while len(A) > 0 do Move Remaining A values to C end while while len(B) > 0 do Move Remaining B values to C end while (b) (14 points) Replicate the Table from the previous page to show how merge works with these new inputs. A = [5 , 7 , 9 , 11] B = [1 , 7 , 8] B = [1, 7, 8] | Step | A | B | C | |------|------------|-----------|----------------| | 1 | [5, 7, 9, 11] | [1, 7, 8] | [] | | 2 | [5, 7, 9, 11] | [7, 8] | [1] | | 3 | [7, 9, 11] | [7, 8] | [1, 5] | | 4 | [9, 11] | [7, 8] | [1, 5, 7] | | 5 | [9, 11] | [8] | [1, 5, 7, 7] | | 6 | [9, 11] | [] | [1, 5, 7, 7, 8]| | 7 | [] | [] | [1, 5, 7, 7, 8, 9, 11]|

CS 171 Lab 9 Week 9 5 (c) (2 points) When you encounter an element that is the same in both lists, which list is the element removed from first?

CS 171 Lab 9 Week 9 6 Question 3: 15 points The Merge function can be used to sort. We take a list and divide it into smaller lists. Then we merge them together. The MergeSort function takes a list. The list is divided in half repeatedly. When the list has been divided into single elements, it is merged back together. The below tree shows how we divide up the array [1,3,5,2,6,9] (a) (2 points) If the length of a list if odd does the extra element go on the left or right ? Left (b) (13 points) Draw a tree diagram, like the one above, that shows how [7,2,4,6,5,9,1] is divided. [7, 2, 4, 6, 5, 9, 1] / \ [7, 2, 4, 6] [5, 9, 1] / \ / \ [7, 2] [4, 6] [5, 9] [1] / \ / \ / \ [7] [2] [4] [6] [5] [9]

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

CS 171 Lab 9 Week 9 7 Question 4: 10 points We can put all the pieces together to make the Merge Sort Algorithm. function msort(X) if len(X) > 1 then middle = len(X) // 2 A = msort(X[ : middle]) B = msort(X[middle : ]) C= merge(A, B) return C else return X end if end function Below is a trace of how this function sorts a list [2, 4, 1, 3, 6] Calling msort ([2 ,4, 1, 3, 6]) Calling msort ([2, 4]) Calling msort ([2]) Calling msort ([4] ) Merge [2] and [4] Calling msort ([1, 3, 6]) Calling msort ([1]) Calling msort ([3, 6]) Calling msort ([3]) Calling msort ([6]) Merge [3] and [6] Merge [1] and [3, 6] Merge [2, 4] and [1 ,3, 6] (a) (10 points) Write out what the trace should look like out if we asked it to sort the list [9, 5, 7, 2] . This should look similar to the above example. Calling msort([9, 5, 7, 2]) Calling msort([9, 5]) Calling msort([9]) Calling msort([5]) Merge [9] and [5] Calling msort([7, 2]) Calling msort([7]) Calling msort([2]) Merge [7] and [2] Merge [5, 9] and [2, 7]

CS 171 Lab 9 Week 9 8 Question 5: 20 points A second method to sort uses Partitions . Instead of dividing the list in half at the middle, we divide it into smaller and larger piles. If a value is equal to the pivot, put in in the larger pile. (a) (4 points) Partition the list [68, 19, 86, 8, 64, 79, 77, 78, 18, 23] on the pivot value 23 Smaller Values: [19,8,18] Pivot: 23 Larger Values: [68,86,64,79,78] (b) (4 points) Partition the list [74, 62, 99, 63, 52, 74, 27, 78, 32, 6] on the pivot value 6 Smaller Values: Pivot: 6 Larger Values: [74,62,99,63,52,74,27,78,32] (c) (4 points) Partition the list [91, 8, 21, 86, 25, 73, 60, 49, 13, 46] on the pivot value 46 Smaller Values: [8,21,25,13] Pivot: 46 Larger Values: [91,86,73,60,49] (d) (4 points) Partition the list [53, 36, 60, 23, 51, 39, 68, 71, 92, 41] on the pivot value 41 Smaller Values: [36,23,39] Pivot: 41 Larger Values: [53,60,51,68,71,92] (e) (4 points) Partition the list [39, 9, 76, 30, 64, 26, 77, 13, 58, 38] on the pivot value 38 Smaller Values: [39, 9, 30, 26, 13] Pivot: 38 Larger Values: [76, 64, 77, 58]

CS 171 Lab 9 Week 9 9 Question 6: 6 points Quicksort Partitions a List repeatedly until it is sorted. The algorithm is described below. function qsort(A, start, stop) if start < stop then p = partition (A, start, stop) qsort(A, start, p - 1) qsort(A, p + 1, stop) end if end function Answer the following questions about this algorithm. (a) (2 points) Does this function have a return value? Why or Why not? No, because it sorts the array in-place and does not need to return a new array. (b) (2 points) Why don’t either of the recursive calls actually include the value at position p ? The value at position p is already in its final sorted position after the partition step. (c) (2 points) Why don’t we need to do anything when start >= stop ? When start >= stop, it means that the segment of the array being considered has one or zero elements, which is inherently sorted Question 7: 4 points The final piece we need to sort is an algorithm to partition. function partition (A, start, stop) Set pivot = A[stop] Set i = start for j in range(start, stop) do if A[j] ≤ pivot then Swap A[i] and A[j] i++ end if end for Swap A[i] and A[stop] return i end function (a) (2 points) What value is selected as the pivot element in this algorithm? The last element in the segment being considered, A[stop], is selected as the pivot element (b) (2 points) How would you implement the pseudocode Swap A[i] and A[j] ? temp = A[i]

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

CS 171 Lab 9 Week 9 10 A[i] = A[j] A[j] = temp

CS 171 Lab 9 Week 9 11 Question 8: 20 points (a) (5 points) Implement the Merge function in Python. (b) (5 points) Implement the MSort function in Python. (c) (5 points) Implement the Partition function in Python. (d) (5 points) Implement the Qsort function in Python. Test your functions with the below code. Submit screenshots and output for each question. You may submit multiple screenshots if needed to show all code or output. #Testing Sorts import random for x in range (0, 10): L = [random.randint (0, 100) for k in range (0, 10) ] print ("Merge Input:", L) L = msort(L) print ("Result after Merge Sort:", L) for x in range (0, 10) : L = [random.randint(0, 100) for k in range (0,10) ] print ("Quick Sort Input:", L) qsort (L, 0, len (L) − 1) print ("Result After Quick Sort:", L)

Lab_09 CS171

Related Documents