<div class="xblock xblock-public_view xblock-public_view-vertical" data-runtime-class="LmsRuntime" data-course-id="course-v1:MITx+6.005.1x+3T2016" data-has-score="False" data-usage-id="block-v1:MITx+6.005.1x+3T2016+type@vertical+block@vertical-ps3-beta" data-init="VerticalStudentView" data-graded="True" data-runtime-version="1" data-block-type="vertical" data-request-token="631484f433c111f0960512f8c5a42579"> <h2 class="hd hd-2 unit-title">Problem Set 3</h2> <div class="vert-mod"> <div class="vert vert-0" data-id="block-v1:MITx+6.005.1x+3T2016+type@html+block@html_24ca4386e5ee"> <div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-runtime-class="LmsRuntime" data-course-id="course-v1:MITx+6.005.1x+3T2016" data-has-score="False" data-usage-id="block-v1:MITx+6.005.1x+3T2016+type@html+block@html_24ca4386e5ee" data-init="XBlockToXModuleShim" data-graded="True" data-runtime-version="1" data-block-type="html" data-request-token="631484f433c111f0960512f8c5a42579"> <script type="json/xblock-args" class="xblock-json-init-args"> {"xmodule-type": "HTMLModule"} </script> <link href="/assets/courseware/v1/9fab367942e94f98d32835b3ef4df11d/asset-v1:MITx+6.005.1x+3T2016+type@asset+block/prism-edx-v1.css" rel="stylesheet" type="text/css" /> <h1 class="handout-title col-sm-8 col-sm-offset-2" id="problem_set_1_tweet_tweet">Problem Set 3 Starting Code</h1> <div> <p>Download the starting code for Problem Set 3 here:</p> <blockquote> <a href="/assets/courseware/v1/238e9f604d76243f6b3d5188c947ebe6/asset-v1:MITx+6.005.1x+3T2016+type@asset+block/ps3.zip">ps3.zip</a> </blockquote> <p>The process for doing this problem set is the same <a href="/courses/course-v1:MITx+6.005.1x+3T2016/jump_to_id/vertical-ps1-beta#import">as in Problem Set 1</a>, but here are quick reminders:</p> <ul> <li> <p>To import the starting code into Eclipse, use File → Import... → General → Existing Projects Into Workspace → Select Archive File, then Browse to find where you downloaded ps3.zip. Make sure <code>ps3-library</code> is checked and click Finish.</p> </li> <li> <p>To run JUnit tests, right-click on the <code>test</code> folder in Eclipse and choose Run As → JUnit Test.</p> </li> <li> <p>This problem set has no <code>main()</code> method to run, just tests.</p> </li> <li> <p>To run the autograder, right-click on <code>grader.xml</code> in Eclipse and choose Run As → Ant Build.</p> </li> <li> <p>To view the autograder results, make sure your project is Refreshed, then double-click on <code>my-grader-report.xml</code>.</p> </li> <li> <p>To submit your problem set, upload <code>my-submission.zip</code> to the submission page, which is the last section of this handout, at the end of the section bar.</p> </li> </ul> </div> </div> </div> <div class="vert vert-1" data-id="block-v1:MITx+6.005.1x+3T2016+type@html+block@html_fb42c4ee5ab5"> <div class="xblock xblock-public_view xblock-public_view-html xmodule_display xmodule_HtmlBlock" data-runtime-class="LmsRuntime" data-course-id="course-v1:MITx+6.005.1x+3T2016" data-has-score="False" data-usage-id="block-v1:MITx+6.005.1x+3T2016+type@html+block@html_fb42c4ee5ab5" data-init="XBlockToXModuleShim" data-graded="True" data-runtime-version="1" data-block-type="html" data-request-token="631484f433c111f0960512f8c5a42579"> <script type="json/xblock-args" class="xblock-json-init-args"> {"xmodule-type": "HTMLModule"} </script> <link href="/assets/courseware/v1/9fab367942e94f98d32835b3ef4df11d/asset-v1:MITx+6.005.1x+3T2016+type@asset+block/prism-edx-v1.css" rel="stylesheet" type="text/css" /> <h1 class="handout-title col-sm-8 col-sm-offset-2">Problem Set 3: The Librarians</h1> <h2 id="overview">Overview</h2> <div data-outline="overview"> <p>The purpose of this problem set is to practice designing, testing, and implementing abstract data types. This problem set includes both immutable and mutable types. For one type (<code>SmallLibrary</code>), the representation of the type is specified, and you should implement its methods to match that rep. For other types, the representation is up to you to choose. The problem set also includes an example of two different implementations of the same Java interface. Finally, you'll be expected to implement equality appropriately for all the types.</p> <p>Since we are doing test-first programming, your workflow for each type should be (<em>in this order</em>).</p> <ol> <li>Study the specifications of the type's operations carefully.</li> <li>Write JUnit tests for the operations according to the spec.</li> <li>Write the type's rep (its fields), document its rep invariant and abstraction function, and implement the rep invariant in a <code>checkRep()</code> method.</li> <li>Implement the type's methods according to the spec. </li> <li>Make an argument about why your rep is safe from rep exposure, and write it down in a comment. </li> <li>Revise your implementation and improve your test cases until your implementation passes all your tests.</li> </ol> <p>As in Problem Set 2, part of the point of this problem set is to learn how to write good tests for abstract data types, so the same expectations apply:</p> <ul> <li>Your test cases should be chosen using the input/output-space partitioning approach. </li> <li>Your test cases should be small and well-chosen. </li> <li>Your tests should find bugs. The Final grading test suite will include buggy implementations of the types, so your tests need to find those bugs.</li> <li>Your tests must be legal clients of the spec.</li> </ul> <p>Finally, in order for your overall program to meet the specification of this problem set, you are required to keep some things unchanged:</p> <ul> <li><strong>Don't change these class names:</strong> the classes <code>Book</code>, <code>BookCopy</code>, <code>Library</code>, <code>SmallLibrary</code>, <code>BigLibrary</code>, <code>BookTest</code>, <code>BookCopyTest</code>, <code>LibraryTest</code>, and <code>BigLibraryTest</code> must use those names and remain in the <code>library</code> package.</li> <li><strong>Don't change the method signatures and specifications:</strong> The public methods provided for you to implement in <code>Book</code>, <code>BookCopy</code>, and <code>Library</code> must use the method signatures and the specifications that we provided.</li> <li><strong>Don't include illegal test cases:</strong> The tests you implement in <code>BookTest</code>, <code>BookCopyTest</code>, and <code>LibraryTest</code> must respect the specifications that we provided for the methods you are testing.</li> <li><strong>Don't change the rep for <code>SmallLibrary</code>:</strong> One type, <code>SmallLibrary</code>, has a required rep that you should not change. For the other types (<code>Book</code>, <code>BookCopy</code>, and <code>BigLibrary</code>) the rep is up to you.</li> </ul> <p>Aside from these requirements, however, you are free to add new public and private methods and new public or private classes if you wish.</p> <hr> </div> <h2>Problem 1: Book and BookCopy</h2> <div> <p>The overall theme of this problem set is implementing a book catalog for a lending library. In this problem, you will test and implement the abstract data types <code>Book</code> and <code>BookCopy</code>. <code>Book</code> is an immutable type representing a published book (uniquely identified by its title, author list, and publication year). Since a library may have more than one copy of the same book, we also have a mutable type <code>BookCopy</code> that represents one copy of a book. The operations and specs for <code>Book</code> and <code>BookCopy</code> are given in their source files, and should not be changed.</p> <p>You'll find <code>Book.java</code> and <code>BookCopy.java</code> in the <code>src</code> folder, and their corresponding JUnit test classes <code>BookTest.java</code> and <code>BookCopyTest.java</code> in the <code>test</code> folder. as we did in previous problem sets.</p> <div class="list-style-lower-alpha"> <ol> <li> <p>Devise, document, and implement test cases for the operations of <code>Book</code>, and put them in <code>BookTest.java</code>.</p> </li> <li> <p>Choose a representation for <code>Book</code>, and write down the rep invariant and abstraction function in a comment. These types are basically warmups, so your rep invariant and abstraction function will be very simple. Implement the rep invariant by writing assertions in the <code>checkRep()</code> method.</p> </li> <li> <p>Implement the operations of <code>Book</code> using your rep. Make sure to call <code>checkRep()</code> at appropriate points, i.e. at the end of every creator, producer, and mutator operation. Also make sure to implement <code>equals()</code> and <code>hashCode()</code> as appropriate for an immutable type.</p> </li> <li> <p>Convince yourself that your type is safe from rep exposure, and write your argument down in a comment after the abstraction function.</p> </li> <li> <p>Finally, run your tests, and revise until your <code>Book</code> implementation passes your tests.</p> </li> </ol> </div> <p>Repeat these same steps for <code>BookCopy</code>, taking care to note that it is a mutable type where <code>Book</code> is immutable: <div class="list-style-lower-alpha"> <ol> <li> <p>Devise, document, and implement test cases for the operations of <code>BookCopy</code>, and put them in <code>BookCopyTest.java</code>.</p> </li> <li> <p>Choose a representation for <code>BookCopy</code>, and write down the rep invariant and abstraction function in a comment. Again, these will be very simple for this class. Implement the rep invariant by writing assertions in the <code>checkRep()</code> method.</p> </li> <li> <p>Implement the operations of <code>BookCopy</code>, including calls to <code>checkRep()</code> at appropriate points. Also make sure to implement <code>equals()</code> and <code>hashCode()</code> as appropriate for a mutable type.</p> </li> <li> <p>Convince yourself that your type is safe from rep exposure, and write your argument down in a comment after the abstraction function.</p> </li> <li> <p>Finally, run your tests, and revise until your <code>BookCopy</code> implementation passes your tests.</p> </li> </ol> </div> <hr> <h2>Problem 2: LibraryTest</h2> <div> <p>The library catalog itself is represented by the <code>Library</code> type, which is a Java interface. In later problems on this problem set, you will implement two different implementations of this type:</p> <ul> <li><code>SmallLibrary</code>, a simple brute-force representation that works well enough for small libraries, like a few hundred books owned by a single person.</li> <li><code>BigLibrary</code>, a representation that performs better on bigger libraries.</li> </ul> <p>In this problem, we'll just write tests for the <code>Library</code> interface itself, without caring which kind of library the tests are run on. The <code>LibraryTest</code> JUnit class has been designed so that it automatically runs twice, once using <code>SmallLibrary</code> and again using <code>BigLibrary</code>.</p> <p>Devise, document, and implement test cases for the operations of <code>Library</code>, and put them in <code>LibraryTest.java</code>.</p> <hr> </div> <h2>Problem 3: SmallLibrary</h2> <div> <p>Now that we have some test cases, we're ready to implement <code>SmallLibrary</code>. The representation for <code>SmallLibrary</code> is already given in <code>SmallLibrary.java</code>, including its rep invariant and abstraction function.</p> <div class="list-style-lower-alpha"> <ol> <li> <p>Implement the rep invariant of <code>SmallLibrary</code> by writing assertions in the <code>checkRep()</code> method.</p> </li> <li> <p>Implement the operations of <code>SmallLibrary</code>, including calls to <code>checkRep()</code> at appropriate points. Also make sure to implement <code>equals()</code> and <code>hashCode()</code> as appropriate for a mutable type.</p> </li> <li> <p>Write down an argument that your type is safe from rep exposure.</p> </li> <li> <p>Finally, run your <code>LibraryTest</code> tests, and revise until your <code>SmallLibrary</code> implementation passes your <code>LibraryTest</code> tests. Note that you won't get a full green light yet from JUnit, because it is also running <code>LibraryTest</code> against <code>BigLibrary</code>, which you haven't implemented yet.</p> </li> </ol> </div> <p>Notes:</p> <ul> <li><strong>Don't change the rep</strong>. You may find yourself tempted to add new fields to the <code>SmallLibrary</code> rep, but don't. The rep has been chosen to be as simple as possible, to make some Library operations very easy to implement (like <code>isAvailable()</code>) even though others are harder (like <code>find()</code>). Bear with that, and make it work. Starting with a simple brute-force rep allows you to debug your tests and your understanding of the spec. You'll invent a better rep in the next problem.</li> <li><strong>Ignore performance</strong>. SmallLibrary is designed for very small book collections, so its operations can be very slow or use extra space. It's brute force. Just don't worry about performance, and focus on simplicity and correctness. Save your performance-optimization ideas for the next problem.</li> <li><strong>Simplest possible functionality.</strong> In particular, the spec for <code>find()</code> is underdetermined. Just do the minimum required for <code>SmallLibrary</code>. Save your ideas for making it better for the last problem.</li> </ul> <hr> </div> <h2>Problem 4: BigLibrary</h2> <div> <p>Now that we've implemented a simple version of the library, let's make it better by implementing <code>BigLibrary</code>. You will choose your own representation for <code>BigLibrary</code>. You can borrow ideas and code from your <code>SmallLibrary</code>, but your goal should be to make the operations of <code>BigLibrary</code> work efficiently even when there are millions of books in the library.</p> <div class="list-style-lower-alpha"> <ol> <li> <p>Choose a rep for <code>BigLibrary</code> and write down its rep invariant and abstraction function. You may want to use <code>Map</code> or <code>SortedSet</code> or other data structures in your rep. You may want to store information redundantly to save time or space when you're implementing the operations.</p> </li> <li> <p>Implement the rep invariant of <code>BigLibrary</code> by writing assertions in the <code>checkRep()</code> method.</p> </li> <li> <p>Implement the operations of <code>BigLibrary</code>, including calls to <code>checkRep()</code> at appropriate points. As usual, make sure to implement <code>equals()</code> and <code>hashCode()</code> as appropriate for a mutable type.</p> </li> <li> <p>Write down an argument that your type is safe from rep exposure.</p> </li> <li> <p>Finally, run your <code>LibraryTest</code> tests, and revise until your <code>BigLibrary</code> implementation passes your <code>LibraryTest</code> tests.</p> </li> </ol> </div> <p>Notes:</p> <ul> <li><strong>Aim for constant-time or logarithmic-time performance</strong>. Since BigLibrary is designed for big book collections, try to make its operations run in O(1) or O(log N) time for a library with N books. Don't count the cost of <code>checkRep()</code>.</li> <li><strong>Simplest possible functionality.</strong> Again, start out by implementing only minimum required behavior for <code>find()</code>. Save your ideas for making it better for the final problem on this problem set.</li> </ul> <hr> <h2>Problem 5: Improving find()</h2> <div> <p>Now improve your <code>BigLibrary</code> so that <code>find()</code> behaves more like a user would expect a library catalog interface to behave. Examples of reasonable behavior that is allowed by the find() spec include:</p> <ul> <li>Matching words in the <code>keywords</code> argument to words in title or author names.</li> <li>Ranking the resulting list of books so that books that match more keywords appear earlier in the list.</li> <li>Ranking books that match multiple contiguous keywords higher in the list.</li> <li>Ranking older books or checked-out books lower in the list.</li> <li>Supporting quotation marks in the <code>keywords</code> argument, so that (for example) <code>"\"David Foster Wallace\" \"Infinite Jest\""</code> finds books whose title or author contains David Foster Wallace or Infinite Jest as contiguous words.</li> </ul> <p>When you add this new behavior to <code>BigLibrary.find()</code>, you should strengthen its spec accordingly, so that clients of <code>BigLibrary</code> can expect the behavior. Don't change Library's spec, however, and leave your <code>LibraryTest</code> tests and <code>SmallLibrary</code> implementation unchanged. Instead, to test your new stronger behavior, you should put the new tests in <code>BigLibraryTest.java</code>.</p> <div class="list-style-lower-alpha"> <ol> <li> <p>Write down the spec for your new behavior for <code>BigLibrary.find()</code> as a Javadoc comment above the method, including preconditions and postconditions as appropriate.</p> </li> <li> <p>Devise, document, and implement test cases for your stronger <code>find()</code> spec in <code>BigLibraryTest</code>.</p> </li> <li> <p>Change the rep of <code>BigLibrary</code> as needed to handle your new behavior, update the rep invariant and abstraction function comments, and update the <code>checkRep()</code> method.</p> </li> <li> <p>Implement your new <code>BigLibrary.find()</code>.</p> </li> <li> <p>Finally, run all your tests, including the original <code>LibraryTest</code> tests and your new <code>BigLibraryTest</code> tests, and revise until your <code>BigLibrary</code> implementation passes your tests.</p> </li> </ol> </div> <hr> </div> </div> </div> </div> </div> </div> </div>