CSCI 2110 Data Structures and Algorithms Assignment 3 Release Date: Oct 16th Due Date Nov 1st 23h55 (5 minutes to midnight) Introduction This assignment will help you develop an understanding of ordered lists and basic recursion. Marking Scheme Exercise 1 /25 • Working code, Outputs included, Efficient, Good basic comments included: 25/25 • No comments or poor commenting: subtract up to 3 points • Unnecessarily inefficient: subtract up to 4 points • No outputs and/or not all test cases covered: subtract up to 2 points • Code not working: subtract up to 14 points depending upon how many classes and methods are incorrect. • Assignment submission and test case text files are not well labeled and organized: subtract up to 2 points. Exercise 2 /12 • Working code, Outputs included, Efficient, Good basic comments included 12/12 • No comments or poor commenting: subtract up to 2 points • Unnecessarily inefficient: subtract up to 1 point • No outputs and/or not all test cases covered: subtract up to 2 points • Code not working: subtract up to 5 points depending upon how many classes and methods are incorrect. • Assignment submission and test case text files are not well labeled and organized: subtract up to 2 points. Error checking: Unless otherwise specified, you may assume that the user enters the correct data types and the correct number of input entries, that is, you need not check for errors on input. Submission: All submissions are through Brightspace. Log on dal.ca/brightspace using your Dal NetId. Java Versions: Please ensure your code runs with Java 11. What to submit: Submit one ZIP file containing all source code (files with .java suffixes) and a text documents containing sample outputs. For each exercise you will minimally have to submit a demo Class with a main method to be tested and your test code, sample outputs. Your final submission should include the following files:OrderedList.java, list1.txt ,list2.txt, OrderedListDemo.java, merged.txt, RecursionExercises.java, Exercise2out.txt You MUST SUBMIT .java files that are readable by your TAs. If you submit files that are unreadable such as .class, you will lose points. Please additionally comment out package specifiers. Your code must compile. Failure to compile may result in a mark of 0. You may add extra helper methods as needed as long as you adhere to the functionality and specifications of this document. Exercise 0 (no marks): Ordered Lists Examine the java file OrderedList.java and its methods. Create a test file with a main method, and practice the following: • inserting items to a new OrderedList object • use the enumerate method to print the list • using the binarySearch method for items in the list and items not in the list • using the first() method, the next() method, and how they relate to the cursor variable You do not need to submit anything for this exercise. Exercise 1: Two-finger Walking Algorithm This exercise focuses on the two-finger walking algorithm for ordered lists. You will write a program called OrderedListDemo.java that can read a list of names from a file and construct an ordered list. You will be provided with the following starter files: OrderedList.java, list1.txt ,list2.txt. Examine these files and study the methods before proceeding. Create a demo class called OrderedListDemo.java • In the main method, read in the values from list1.txt and list2.txt o Your program should accept input from a user (specifying the names of two input files) and read files formatted like the one described (see also: list1.txt and list2.txt). Your program should read two text files, each containing a list of names, and construct two ordered lists. o Store the lists in two separate OrderedList objects called names1 and names2 Input/Output If the input text file is: Shai Tom Jim Aaron Barbara Beth Fred Jack Jarred Jill Amar Ralph Jill Hillary It should create the following ordered list and display the contents of the list: [Aaron, Amar, Barbara, Beth, Fred, Hillary, Jack, Jarred, Jill, Jim, Ralph, Shai, Tom] Note: Although Jill is repeated in the input list, the ordered list does not have repeated items. . Finally, your program should demonstrate a method that returns a third list that is a merger of the two ordered lists. Use the two-finger walking algorithm discussed in class. Use the following method header: • public static
> OrderedList merge(OrderedList list1, OrderedList list2) If list1 is: Amar Boris Charlie Dan Fujian Inder Travis And list2 is: Alex Ben Betty Charlie Dan Pei Travis Zola Zulu Your method should create and return the new merged ordered list: Alex Amar Ben Betty Boris Charlie Dan Fujian Inder Pei Travis Zola Zulu Student Generated Test Cases: Test your program and print outputs from a sample run in the following format to a file called merged.txt: Enter the first filename to read from: list1.txt Enter the second filename to read from: list2.txt The Ordered Lists contain the following entries: List 1: [Amar, Boris, Charlie, Dan, Fujian, Inder, Travis] List 2: [Alex, Ben, Betty, Charlie, Dan, Pei, Travis, Zola, Zulu] A merged version of the two lists looks like this: [Alex, Amar, Ben, Betty, Boris, Charlie, Dan, Fujian, Inder, Pei, Travis, Zola, Zulu] Exercise 2: Recursion This exercise focuses on recursion. You will implement two static methods to solve two separate problems. All solutions must be recursive. Create a class called RecursionExercises.java. This class will contain the static methods and the main method to run your code. Create the following static methods: • Write a recursive method call squares which accepts a single positive integer and calculates the sum of the squares of all the digits up to and including the integer. Use the following signature: o public static int squares(int n) o For example, squares(5) would return 55 • Write a recursive method called reverseString which accepts a string and an integer. The method returns the passed in string in reverse order starting from a specified index. Use the following header: o public static String reverseString(String n, int i) o For example, reverseString(“Hello”,0) would return “olleH” o reverseString(“Hello”,1) would return “lleH” since we start from index 1. Input/Output Input: No user input for this exercise. Output: • For the squares method call the method and print the following: o The sum of the squares up to [n] is: [answer] o Example: The sum of the squares up to 5 is: 55 • For the reverseString method call the method and print the following: o Starting word is [word], reversed from index [i] is [answer] o Example: Starting word is Hello, reversed from index 2 is leH. Student Generated Test Cases: Demonstrate that your recursive methods work by calling them in the main method of the RecursionExercises.java class. • Use print statements for the demo, no scanner is needed. • Show 2 different examples for squares and 2 examples for reverseString with different index values. Test your program and print outputs from a sample run in the following format to a file called Exercise2out.txt. 欢迎咨询51作业君