CSCI 3333
Data Structures
Summer 2008
Homework #7

Due Date: July 30th (Wednesday)

Goals

Familiarize students with sorting

Specification

(1) Prove that Shell Sort is not stable.

(2) Show the evolution of applying Shell Sort with gap sequence (5,3,1) to the array: {44, 55, 21, 33, 10, 50, 22, 30, 10, 77, 27, 37, 17, 11, 36, 28, 38} by showing the array after 5-sorted, 3-sorted and 1-sorted. Show the conceptual view also.

(3) C-11.4: Describe and analyze an efficient method for removing all duplicates from a collection A for n elements.

(4) C-11-23 modified: Let A and B be two sequences of n integers each. Given an integer m, give an O(n lg n)-time algorithm for determining if there is an integers a in A and an integer b in B such that m=a+b.

Submission

• Name your solution word file as [LastName_FirstName]_h7.doc. (e.g. Doe_Jenny_h6.doc).
• Upload all files through your WebCT account at
  http://courses.uhcl.edu:8900/.
• Email the solution to both the instructor and the teaching assistant.
• Turn in a hardcopy. All should be included in an envelope. The cover of the envelope should include course name, student name, homework number, instructor name and TA name.
• Failure to follow this guideline may result in reduced grade.