Searching, sorting and efficiency analysis – 20 course points
For this assignment, you will complete searching/sorting tasks and efficiency analysis. No code is to be written for this assignment.
- Binary Search. Search for the character S using the binary search algorithm on the following array of char- acters: A E G K M O R S 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).
| Iteration | Left | Right | Middle | Number of comparisons |
|---|---|---|---|---|
- Selection sort. 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 7 of the Selection Sort algorithm). Sort the following array of characters (sort into alphabetical order): C Q S A X B T
- Insertion sort. 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). Sort the following array of characters (sort into alphabetical order): C Q S A X B T
- Mergesort. List the resulting array after each iteration of the mergesort algorithm. Indicate the number of character-to-character comparisons made for each call to merge (line 22 of the Merge algorithm). Sort the following array of characters (sort into alphabetical order): C Q S A X B T
- Efficiency Analysis. For each problem given below, do the following:
- Create an algorithm in pseudocode to solve the problem.
- Identify the factors that would influence the running time of your algorithm. For example, if your algorithm is to search an array the factor that influences the running time is the array size. Assign names (such as n) to each factor.
- Count the operations performed by the algorithm. Express the count as a function of the factors you identified in Step 2. To do that, identify the basic operations of the algorithm. There is no need count every statement separately only the ones that will influence the running time.
- Describe the best case scenario for the algorithm and derive the big O.
- Describe the worst case scenario for the algorithm and derive the big O.
The problems are:
- Determine if two arrays have no elements in common.
- Counting the total number of characters that have a duplicate within a string, including spaces. (i.e. ”gigi the gato” would result in 9 (g*3 + i*2 + t*2+” “*2)
- Finding a row where every entry is ’x’ in a 2-D array.
Before submission
- Collaboration policy. Read our collaboration policy here.
- Writeup. Use your preferred text editor to type your answers, and then save the file in PDF format. We will only grade typed assignments and in PDF format. You will use Gradescope to submit your assignment. If you have not yet used Gradescope, go to your scarletmail inbox and look for an email from Gradescope with instructions on how to access your account.
- Submitting the assignment. Submit your assignment via the Web submission system called Gradescope. To do this, click the Assignments link from the course website; click the Submit link for that assignment.
- Read Help − > Student Workflow − > Submitting a PDF for instructions on how to submit your PDF file.
Getting help
If anything is unclear, don’t hesitate to drop by office hours or post a question on Piazza. Find instructors office hours by clicking the Staff link from the course website.