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 #4 -- Due Wed 16 June 1999 : 09.30am

• Question 1. Write pseudocode and a diagram that shows how to implement the merge part of the merge-sort algorithm using two stacks (one for each subsequence), and be sure to use the correct ADT operations for stacks. Do not write Java code, or pseudocode for merge-sort.

• Question 2. Write pseudocode and a diagram that shows how to implement the insertion-sort algorithm using (a) one stack, and (b) two stacks, with appropriate ADT operations for stacks.

• Question 3. Develop a complexity budget for each of the implementations in Question 2 (a and b), above. Compare the complexity of the one-stack and two-stack implementations, and explain why a difference in the count of a given type of operation occurs (one or two sentences per operation type).

• Question 4. In class, we discussed how to implement a heap using an array. (a) Implement a heap using two stacks, being sure to preserve both the heap-order and heap-structure property.
  Hint: When you bubble-up a value, you need to pop data D off the stack (S₁) that holds the heap, then push D onto the other stack (S₂). After swapping nodes to re-establish the heap property, you would pop data off S₂ and push it back onto S₁. If absolutely necessary, you may use a scalar variable to hold one data item.

  (b) Implement the heap ADT operations we discussed in class using the stack-based heap you implemented in Part a).

• Question 5. Analyze the complexity of the INSERT and DELETE operations on the stack-based heap you developed in Question 4. Use (a) a complexity budget for each operation, (b) Big-Oh estimates of complexity for each type of operation (e.g., memory I/O, comparison, etc.), and (c) tell why any differences between the counts for each operation type occurred between the INSERT and DELETE operations.

• Question 6. Using the procedure for building a heap that we discussed in class, answer the following questions: (a) what are the general characteristics of the best-case input, (b) what are the general characteristics of the worst-case input, and (c) give an example of a) and b) for building a min-heap.

Copyright © 1999 by Mark S. Schmalz.