Class Notes: Data Structures and Algorithms

Summer-C Semester 1999 - M WRF 2nd Period CSE/E119, Section 7344

Instructor: M.S. Schmalz -- TAs: TA Mailing List

Homework #3 -- Due Thu 10 June 1999 : 09.30am

• Question 1. Given an 8-element sequence S = (3, -10, 4, -3, 8, 6, 5, 1), diagram the merge-sort tree (architecture) for the divide, sort, and conquer phases of the merge-sort algorithm, as we did in class. Label each level (e.g., L1, L2, etc.), as you will need this information in Question 2. Do not write code for merge-sort.

• Question 2. Produce a budget of computational work for the sorting architecture you developed in Question 1. For example, the number of operations (e.g., external I/O, additions, memory I/O, comparisons, incrementations, etc.) (b) Given this budget, produce a Big-Oh estimate of complexity, and show the assumptions you used to arrive at that estimate.

• Question 3. Given a 7-element sequence S = (-60, -3, 4, 1, 0, -1, 2) diagram the sorting architecture (divide-and-conquer) for quick-sort using as a pivot the (a) mean, (b) median, and (c) average of lowest and highest values for S and each of the lower-level subsequences employed in the quick-sort algorithm. Do not write code for quick-sort.

• Question 4. Analyze the complexity of the algorithm for each of the three cases you developed in Question 3, in the same way as required in Question 2. Based on in-class discussion, what would be the optimal choice of pivot for S, and why?

• Question 5. Given a 7-element sequence S = (9, 4, -3, 6, 8, 12, -14), diagram the insertion-sort tree (architecture), as we did in class. Label each level of the tree. Do not write code for insertion-sort.

• Question 6. Repeat Question 4 for the sorting architecture diagrammed in Question 5.

Copyright © 1999 by Mark S. Schmalz.