| 
CSE 142 Winter 2003 -- Homework 5 |
|
 UW Home |
CSE Home |
Message
Board |
Contact Info |
|
|
CSE 142 Homework #5Due: Sunday, March 9 at 9:00 PM. No late assignments will be accepted.Directions: Please answer the following questions. Use full sentences when answering questions that require explanations. Remember to acknowledge any help you receive from individuals outside the course staff. These questions are based on material from lecture and from Chapters 12 thru 14 in the textbook.You answers should be formatted using Microsoft Word or WordPad (.doc file), Notepad or any plain text editor (.txt), or any other file format that can be read by recent versions of Microsoft Word. When you are done, use this turnin form to submit this assignment along with part A of programming project 3 over the web. If you make a mistake, you can resubmit your assignment as often as needed. We will grade the last one that you hand in. Your graded assignment will be returned to you via email. Please include the questions along with your answers in your homework file. Remember to get started right away. Don't wait until Sunday after dinner to begin, or you are likely not to finish on time. Just as a reminder, homework in this course is to help you understand the conceptual material that we cover. If you need assistance, please get help from the course staff. Grading Guidelines: Unless indicated otherwise, each question or part of a question is worth 2 points. To gain the full 2 points, your answer must have no significant flaws, must be clear to the reader, and must be complete (but remember that complete does not mean verbose - be concise and to the point). One point will be awarded to answers that are partially correct, are somewhat unclear, or are incomplete. You must show credible effort to gain at least one point per question. Use the variations of the StringList class below to complete this homework assignment. This assignment does not require a lot of implementation; rather, you will analyze the tradeoffs between implementations. The first implementation, SortedStringBag.java, keeps a bag of Strings in an array, and only sorts the strings when a search for a particular string is performed using binary search (see the contains method). The alternative implementation, OrderedStringBag.java, keeps the strings in sorted order every time a new string is added; therefore, binary search can be performed without first sorting the collection of strings. 1. [2 points] Make a copy of the SortedStringBag class and rename it to InsSortedStringBag.java. Rewrite the sortStrings method using the insertion sort algorithm. Here's the algorithm in English: For indices k from 0 to numStrings-1 Take element at position k and insert it where it belongs in the array between positions 0 to k-1, shifting each element up by one index that is larger than the element at position k The invariant is that the strings in positions 0 to k are in sorted order. Paste your code for the sortStrings method (implementing Insertion Sort) into your homework file. 2. [2 points] Be sure to test your insertion sort algorithm by creating a new InsSortedStringBag object, adding strings to the InsSortedStringBag, and then searching for a string using the contains method. [If you don't want to generate the strings yourself, you can use the method generateRandomString (which returns a randomly generated string) OR setRandomSequence (which takes a parameter num and adds num randomly generated strings to the strings array in positions 0 to (num-1)).] Paste your code from the interactions window, showing how you tested your sortStrings method. You may use the toString method in the class to print out the strings in the array. 3. [6 points (1 per scenario, 1 for adding the instance variable, and 2 for the questions)] It's time to analyze the three implementations of the StringList classes. The operation that we care about is the number of comparisons between Strings in the code. Add an instance variable called numComparisons to each class, set this variable to 0 in the constructors, and increment this variable anytime two Strings are compared in any method in the class. Only increment numComparisons for comparison operations between Strings. Once you have modified the code, find out how many String comparisons are done in total for the three implementations in the following three scenarios: [At the end of each scenario, get the value of the instance variable numComparisons to find out how many comparison operations were performed.] Be sure that when you create new instances of the classes that you set the initial capacity to be greater than or equal to the total number of strings you want to add in each scenario. Scenario 1: Add 20 strings, search for 1 string, add 40 strings, search for 1 string, add 80 strings, search for 1 string Scenario 2: Add 20 strings, search for 10 strings, add 20 strings, search for 5 strings, add 20 strings, search for 1 string Scenario 3: Add 20 strings, search for 10 strings, add 1 string, search for 10 strings, add 1 string, search for 10 strings, add 1 string, search for 10 strings In your homework file, write down the numbers for each implementation for all three scenarios. Answer the following questions: With the goal of minimizing comparison operations, in which scenarios would you use the SortedStringBag implementation? In which scenarios would you use the OrderedStringBag implementation? How did the SortedStringBag and InsSortedStringBag implementations compare in terms of string comparison operations? 4. (2 points) No Java programming necessary. Assume you are designing the online retail store system and you now know about subclasses, superclasses, and inheritance. The store would like to sell shirts, pants, and jackets. The classes and their properties are described below. Determine an appropriate superclass that represents retail items. Describe (by drawing a figure or in English) the relationship between the superclass and the existing classes and describe how you rearranged/added/modified class properties. Shirt: Properties include price, color, manufacturer, size (S, M, L, XL), fabric type Pants: Properties include price, color, manufacturer, size (integers), fabric type Jackets: Properties include price, outer shell color, inner lining color, manufacturer, size (S, M, L, XL), outer shell fabric type, inner shell fabric type 5. (2 points) Please complete part A of Project 3 with your partner. Use this turnin form to submit the files for part A of the project along with this assignment. (Submit the files separately; don't paste the code for the project into the file containing your solutions to this homework.) Both you and your partner should turn in the code for this homework assignment, but the code should be the same since you are working on the project together.
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
