Data Structures and Algorithms Homework help

CS241 - Fall 2017 - Assignment #1

Assigned: September 27th, 2017 Due: October 4th, 2017 No late submissions. You will be able to complete your submission later if appropriate, but if you do not submit a significant part of the assignment by the due date you will not be able to submit afterwards. Extra credits do not have a deadline.

Collaboration policy: The goal of homework is to give you practice in mastering the course material. Consequently, you are encouraged to collab- orate with others (groups of at most three). In fact, students who form study groups generally do better on exams than do students who work alone. If you do work in a study group, however, you owe it to yourself and your group to be prepared for your study group meeting. Specifically, you should spend at least 30–45 minutes trying to solve each problem beforehand. If your group is unable to solve a problem, it is your responsibility to get help from the instructor before the assignment is due. You must write up each problem solution and/or code any programming assignment by yourself without assistance, even if you collaborate with others to solve the problem. You are asked to identify your collaborators. If you did not work with anyone, you must write “Collaborators: none.” If you obtain a solution through research (e.g., on the web), acknowledge your source, but write up the solution in your own words. It is a violation of this pol- icy to submit a problem solution that you cannot orally explain to the instructor. No other student may use your solutions; this includes your writing, code, tests, documentation, etc. It is a violation of this policy to permit anyone other than the instructor and yourself read-access to the location where you keep your solutions.

1

Submission Guidelines: Your group has to submit your work on Black- board by the due date. Only one submission per group is necessary. Just make sure that you identify your group in the header. For each of the programming assignments you must use the header template pro- vided in Blackboard. The header must contain, your name, course number, semester, homework number, problem number, and list of collaborators (if any, otherwise put “none”). Your answers to questions that do not require coding must be included in this header as well. Your code must follow the Java formatting standards posted in Blackboard. Format will also be part of your grade.

To complete your submission, you have to upload two files to Blackboard: your source file and your class file. The submission will not be accepted otherwise.

Style and Correctness: Keep in mind that your goal is to communi- cate. Full credit will be given only to the correct solution which is described clearly. Convoluted and obtuse descriptions might receive low marks, even when they are correct. Also, aim for concise solutions, as it will save you time spent on write-ups, and also help you conceptualize the key idea of the problem.

2

Assignment #2

Programming Assignment Grading Rubric: The following rubric applies only to programming assignments.

Program characteristic

Program feature Credit possible

Design 30%

Algorithm 30%

Functionality 30%

Program runs without errors

20%

Correct result given 10%

Input 15%

User friendly, typos, spacing

10%

Values read in correctly

5%

Output 15%

Output provided 10%

Proper spelling, spacing, user friendly

5%

Format 10%

Comments, name 5%

Indentation 5%

TOTAL 100%

1(40) 2(40) 3(20) TOTAL(100) EC

3

Assignment:

1. (40 points) Implement a generic class Set〈T〉 that maintains a set of items of generic type T using the class LinkedList〈T〉 in the Java API. Your Set class must provide the following instance methods:

add: that adds a new item. (Ignore if already in the set.)

remove: that removes an item. (Ignore if not in the set.)

membership: that returns true if a given item is in the set and false otherwise.

toString: that returns a string with the list of the items in the set.

(REMINDER: do not violate encapsulation, you can only use List methods.)

2. (40 points) Write a testSet class with a main() method that tests all the operations of the Set class above. That is, create an empty set A of integers, obtain from the user some integers and store some in A, some in B, and some in both, display the set using toString(), obtain from the user some integers and remove them from A using remove(), display the set using toString(), obtain an integer from the user and check whether it is in A or not using membership() and display the result. (REMINDER: you can only store objects.)

3. (20 points) Based on the big-O running time of each method, argue whether implementing with ArrayList would have been better or not. (A complete answer must include the big-O running time of all methods for each of the implementations. If you do not base your answer on the big-O running time, you get no points.)

4. (Extra credit) Expand your class Set〈T〉 with the following static methods, and expand your testSet class to test them.

union: that returns the union of two given sets.

intersection: that returns the intersection of two given sets.

difference: that returns the difference between two given sets.

4