Question details

CSE205 Object Oriented Programming and Data Structures Homework 2 + SUBMISSION
$ 20.00

CSE205 Object Oriented Programming and Data Structures Homework 4 : 25 pts (13 bonus pts) 1 Submission Instructions
Create a document using your favorite word processor and type your exercise solutions. At the top of the document be
sure to include your name and the homework assignment number, e.g. HW4. Convert this document into Adobe PDF
format and name the PDF file <asuriteid>.pdf where <asuriteid> is your ASURITE user id (for example, my ASURITE
user id is kburger2 so my file would be named kburger2.pdf). To convert your document into PDF format, Microsoft Office
versions 2008 and newer will export the document into PDF format by selecting the proper menu item from the File
menu. The same is true of Open Office and Libre Office. Otherwise, you may use a freeware PDF converter program, e.g.,
CutePDF is one such program.
Next, create a folder named <asuriteid> and copy <asuriteid>.pdf to that folder. Copy any requested Java source code
files to this folder (note: Java source code files are the files with a .java file name extension; do not copy the .class files as
we do not need those).
Next, compress the <asuriteid> folder creating a zip archive file named <asuriteid>.zip. Upload <asuriteid>.zip to the
Homework Assignment 4 dropbox by the assignment deadline. The deadline is 11:59pm Wed 30 Apr. Consult the online
syllabus for the late and academic integrity policies.
Note: not all of these exercises will be graded, i.e., random ones will be selected for grading.
Exercises 4.7–4.9, 5.4, and 5.8–5.9 are optional and are worth bonus credit. Any points earned on these exercises will be
added to your homework assignment point total before computing your homework assignment percentage. Your homework
assignment percentage is limited to a maximum of 100%, e.g., if you ended up earning 95 homework points your
homework percentage would be calculated as min(95 / 87.5, 1.0). 2 Learning Objectives
1.
2.
3.
4.
5.
6. To
To
To
To
To
To use the merge sort and quick sort sorting algorithms to sort a list of elements.
analyze the time complexity of the merge sort and quick sort sorting algorithms.
implement linked list, stack, queue, and tree data structures.
analyze the time complexity of linked list, stack, queue, and tree operations.
implement a binary search tree (BST) data structure.
analyze the time compexity of BST operations. 3 Sorting
3.1 In the video lecture for Sorting Algorithms : Section 7 : Merge Sort Example we traced how merge sort would
recursively sort list = { 4, 2, 7, 3, 5, 13, 11, 8, 6, 2 }. For this exercise, I would like you to draw a similar diagram
showing how merge sort would sort list = { 5, 3, 1, 6, 2, 4 }. Scan this diagram and insert it into your final PDF.
The objective of this exercise is to essentially see if you understand how the merge sort procedure works. 3.2 In Sorting Algorithms : Section 9 : Merge Sort Pseudocode we discussed the high-level pseudocode for the merge
sort algorithm. I wrote three methods: recursiveMergeSort(), merge(), and copyRest(). Continuing the previous
exercise, how many times will recursiveMergeSort() be called when sorting the list of Exercise 3.1. Include the
original nonrecursive call to recursiveMergeSort() and all of the recursive calls in the sum. 3.3 Continuing, how many times will merge() be called? 3.4 Continuing, during the final call to merge()—when we are merging listL and listR to form the final sorted list—
copyRest() will be called. (a) When copyRest() executes, which list will be srcList (listL or listR)? (b) What will be
the value of srcIndex? (c) Which list will be dstList? (d) What will be the value of dstIndex? 3.5 Consider list = { 5, 4, 2, 9, 1, 7, 3, 8, 6 } and the quick sort algorithm. Assume we always choose the first list item
in the list being partitioned as the pivot. Trace the partition method showing how list is partitioned into listL and
listR. To get you started, here is the format of what I am looking for in your solution (next page): Arizona State University Page 1 CSE205 Object Oriented Programming and Data Structures Homework 4 : 25 pts (13 bonus pts) list = { 5, 4, 2, 9, 1, 7, 3, 8, 6 }, pivot = 5, leftIndex = -1, rightIndex = 9
While loop pass 1:
leftIndex ends up at 0, rightIndex ends up at 6
leftIndex < rightIndex so swap list[0] and list[6]: list = { 3, 4, 2, 9, 1, 7, 5, 8, 6 }
While loop pass 2:
...
While loop pass 3:
...
While loop terminates because leftIndex = ??? >= rightIndex = ???

Available solutions