CS111 - Introduction to Computer Science<Fall 2020>Assignment 7 - Searching, Sorting, and Efficiency Analysis,(100% score)download to score A

Document Content and Description Below

Assignment 7 - Searching, Sorting, and Efficiency Analysis [65 points] For this assignment, you will complete searching/sorting tasks and efficiency analysis. No code is to be written for this assi... gnment. Problem 1 - Binary Search (8 points) Search for the character Z using the binary search algorithm on the following array of characters: A D H J L N P R Z For each iteration of binary search use a table similar to the table below to list: (a) the left index and (b) the right index of the array that denote the region of the array that is still being searched, (c) the middle point of the array, and (d) the character-to-character number of comparisons made during the search (line 09 and line 11 of the Binary Search algorithm at the end of the assignment). Grading (8 points): 0.5 point for each correct left, right, and middle index, and for each compare. Iteration Left Right Middle Number of Comparisons 1 0 8 4 2 2 5 8 6 2 3 7 8 7 2 4 8 8 8 1 Problem 2 - Selection Sort (7 points) List the resulting array after each iteration of the outer loop of the selection sort algorithm. Indicate the number of character-to-character comparisons made for each iteration (line 07 of the Selection Sort algorithm at the end of the assignment). Sort the following array of characters (sort into alphabetical order): C Q R B P D X Grading (7 points): 0.5 point for each correct iteration; 0.5 points for the number of comparisons B Q R C P D X - 6 comparisons B C R Q P D X - 5 comparisons B C D Q P R X - 4 comparisons B C D P Q R X - 3 comparisons B C D P Q R X - 2 comparisons B C D P Q R X - 1 comparisons B C D P Q R X - 0 comparisons 1Rutgers University CS111 - Introduction to Computer Science Fall 2020 Problem 3 - Insertion Sort (12 points) List the resulting array after each iteration of the outer loop of the insertion sort algorithm. Indicate the number of character-to-character comparisons made for each iteration (line 06 of the Insertion Sort algorithm at the end of the assignment). Sort the following array of characters (sort into alphabetical order): C Q R B P D X Grading (12 points): 0.5 point for each correct iteration; 0.5 points for each number of comparisons C Q R B P D X - 1 comparisons C Q R B P D X - 1 comparisons B C Q R P D X - 3 comparisons B C P Q R D X - 3 comparisons B C D P Q R X - 4 comparisons B C D P Q R X - 1 comparisons Problem 4 - Mergesort (12 points) List the resulting array after each call of the merge method. Indicate the number of characterto-character comparisons made for each call to merge (line 20 of the merge method at the end of the assignment). Sort the following array of characters (sort into alphabetical order): C Q S A X B T Grading (12 points): 0.5 point for [Show More]

Last updated: 1 year ago

Preview 1 out of 8 pages