CS 311 - Design and Analysis of Algorithms- Dr. Huda Alrammah Prince Sulton University Feb 20, 2021 Assignment 2 Submission Deadline: Feb 27, 2021 @ 11:59pm Name: ID: Question 1: Solve the following recurrences using master's method. (pl.) T(n) = 3T(1/4) +n logn Question 2: Use the substitution method T(n) = 2 - 1-0(2) to solve the following recurrences: (2 p.) T(n)= 2T(n-1) + 1 TO) = 0 Question 3: A new implementation of Merge Sort uses a cutoff variable to use insertion sort for small number of items to be merged (Merging single elements is costly). 1. Give the pseudo code for the merge sort algorithm with a cutoff variable set to 4. (I pt.) 2. Show the trace for top-down merge sort using the following array of characters with a cutoff variable set to 4. (1 p.) EASYMERGESORTWITHINSERTION CS 311 - Design and Analysis of Algorithms- Dr. Hude Alrammah Prince Sulton University Feb 20, 2021 Algorithm countCommon(A, B, n) Input: Two arrays A and B with both size of n Output: Number of common elements in A and B counter +/umber of common elements for i 0 ton-1 do forje 1 to n - 1 do if Bil - A[i] then counter += 1; break; return counter CS 311 - Design and Analysis of Algorithms- Dr. Hudo Alrammah Prince Sulton University Feb 20, 2021 Question 4: Using Quick sort algorithm, sort the array: 65, 70, 75, 80, 85,60,55,50,45 Illustrate a trace of a Quick sort of the array below, following the style Draw the tree of the recursive calls used in lecture. (1 p.) made (pt) Left Array Pivot Right Array Question 5: Let A and B be the class lists of CS311 and CS320. Each of A and B consists of unique student IDs of the corresponding class. We want to know how many students are taking both CS311 and CS320 this term. 1. Write an algorithm in pseudocode to count the number of students who are taking both classes this term. To keep it simple, we assume that the two classes have the same number of students, denoted by n. A simple version of this algorithm could be using two for loops, and the time complexity is: T(n)-0(n). (the pseudocode is given down). Can you find a better algorithm for this problem with less running time? (1.5 p!) 2. Give the time complexity of your algorithm. (0,5 pr.)