CSE 2050 Exam with Questions Solved 100% Correct |A Graded Quadratic Sorting: Best at random distribution - ANSWER selection Quadratic Sorting: Worst at random distribution - ANSW ER bubble Quadratic Sorting: Best at one big item at front - ANSWER bubble Quadratic Sorting: Worst at one big item at front - ANSWER selection Quadratic Sorting: Best at one little item in the back - ANSWER Insertion Quadratic Sorting: Worst at one li ttle item at back - ANSWER Bubble Quadratic Sorting: Best at reverse sorted distribution - ANSWER Selection Quadratic Sorting: Worst at reverse sorted distribution - ANSWER Bubble and Insertion (tied) What are the steps of divide -and-conquer algorithms? - ANSWER 1. Break the original problem into subproblems 2. Solve subproblems 3. Combine subproblems solution s into a solution to the original problems 4. Define a base case for subproblems that should not be further divided What divide -and-conquer algorithm is characterized by: >Guaranteed nlogn running time >Substantial memory overhead for large n > A simple "divide" step, but a complicated "conquer" step - ANSWER Mergesort What divide -and-conquer algorithm is characterized by: >Worst case n^2 running time >Low memory overhead >A complicated "divide" step, but a simple "conquer" step - ANSWER quicksort What divide -and-conquer algorithm is characterized by: >Average case O(n) running time >Low memory overhead >A "prune -and-search" framework - ANSWER Quickselect What process corresponds to the "divide" portion of merge sort's "divide -and-
conquer"? - ANSWER Re cursively splitting lists in half What is the appropriate base case for a recursive function for mergesort(L)? - ANSWER if len(L)<=1: return L What code adds remainder of my left and right sublists to L after zipping the while loop? - ANSWER L[median:]= left[i:]+right[i:] Why is quickselect asymptotically faster than quicksort? - ANSWER The recursive tree formed by quickselect requires fewer operations per level.
conquer"? - ANSWER Re cursively splitting lists in half What is the appropriate base case for a recursive function for mergesort(L)? - ANSWER if len(L)<=1: return L What code adds remainder of my left and right sublists to L after zipping the while loop? - ANSWER L[median:]= left[i:]+right[i:] Why is quickselect asymptotically faster than quicksort? - ANSWER The recursive tree formed by quickselect requires fewer operations per level.
