COP 3530, Discrete Data Structures and Algorithms, Summer 1999, Homework 4 :: UFL Florida Computer Programming Homework

Class Notes: Data Structures and Algorithms Summer-C Semester 1999 - M WRF 2nd Period CSE/E119, Section 7344 Homework #4 -- Due Wed 16 June 1999 : 09.30am -- Answer Key Answers are in blue typeface. * 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. Answer: 1. Put the two sorted subsequences to be merged, denoted by S1 and S2 on stacks of the same name. Assume that the sorting is in ascending order; hence, each stack has its minimum values at the top of the stack. 2. The merge algorithm proceeds as follows: { repeat until S1 or S2 is empty { v1 = pop(S1) v2 = pop(S2) output(min(v1,v2)) if (max(v1,v2) = v1) then push v1 onto S1 else push v2 onto S2 endif }