CS 284: Mid-Term (Take Home) – Spring 2021 March 24 - March 26, 2021 Student Name: Honor Pledge: Grade sheet: Problem XXXXXXXXXXpoints) Problem 2 (4 points) Problem XXXXXXXXXXpoints) Problem 4 (2...

assignment in a file below




CS 284: Mid-Term (Take Home) – Spring 2021 March 24 - March 26, 2021 Student Name: Honor Pledge: Grade sheet: Problem 1 (3.5 points) Problem 2 (4 points) Problem 3 (3.5 points) Problem 4 (2 points) Problem 5 (2 points) Extra Credit 1 Instructions Deadlines The midterm exam is released at 11:00 AM EST on Wednesday March 24th. It is due at 11:59 PM Friday March 26th. Policy The midterm is open notes and book. You are welcome to use lecture slides, lecture recordings, the course textbook, and code from lecture/recitation. You cannot google the exact (or very similar) question, copy and paste code you find online, or use someone else’s work. Submission Instructions Submissions are due at 11:59PM on Friday, March 26th. Please submit your answers in one file called midterm.zip. This file midterm.zip should include: • A folder named q1. q1 should include Animal.java, Metamorphose.java and three .java files containing the implementations of animals of your choice. These files must be named appropriately. • A folder named q2. q2 should contain one .txt file named q2.txt. This file should contain your answers to both a) and b) of Problem 2, clearly marked. • A folder named q3. q3 should contain one .java file MySLL.java and one optional .txt file called q3.txt if and only if you choose to answer the bonus question. • A folder named q4. q4 should contain one .txt file named q4.txt containing your answers to q4. • A folder named q5. q5 should contain one .java file LinkedQueue.java. • An optional folder named bonus. bonus should contain one .txt file called bonus.txt containing your answer to the bonus question. 2 Problems Problem 1 (3.5 pts). You’ve met an aspiring zoologist interested in classifying animals. Help them out by implemented the following: • Create an abstract java class Animal.java. The zoologist would like each animal to provide implementations for a public String getName() method, a public int numLegs() method and a public boolean canFly() method. Create abstract methods for each in Animal.java. You may create any data fields you like. • Create two concrete Java classes for animals of your choice that extend the class Animal and implement all abstract methods. • The zoologist notes that some animals undergo a process called metamorphosis, where they transform from an immature form to an adult form. Create a Java interface Metamorphose.java specifying a public void metamorphose() method and a public boolean metamorphosisComplete() method. • Create one more concrete Java class for an animal of your choice that extends the class Animal and also implements the interface Metamorphose. The first call to the method metamorphose() must change the result of the public String getName() method (and can optionally change the results of canFly() and numLegs() depending on your chosen animal). In other words, two different Strings should be printed in the following code where MetamorphicAnimal stands in for your chosen animal. MetamorphicAnimal a = new MetamorphicAnimal (); 2 System.out.println(a.getName ()); // prints babyAnimalName a.metamorphose (); 4 System.out.println(a.getName ()); // prints adultAnimalName These strings are basically the name of your animal before and after metamorphosis. Consider adding data fields (if you have not already done so) to Animal.java to help with this. If the metamorphose() function has been called, metamorphosisComplete() should return true. Else it should return false. Again, consider adding a data field to enable this function- ality. 3 Problem 2 (4 pts). Indicate for each of the following code fragments their approximate worst- case running time via both a polynomial T and the big-O class of functions to which the polynomial belongs. You may assume that n > 2. // a (2 points) 2 for(int i=0; ii; j--) { 4 for(int k=0; k<3; k++)="" {="" system.out.println("hello");="" 6="" }="" }="" 8="" }="" 10="" b="" (2="" points)="" for(int="" i="1;"> l = new MySLL (); 2 l.addFirst (0); l.add (1 ,1); 4 l.add (2 ,4); l.remove (1); In the code example above, l is a linked list [0;4]. The Node 0 has age 2, while the Node 4 has age 0. • Define a public int findOldest() function that returns the age of the oldest node in the singly linked list. Include this function in MySLL and write a javadoc-style documentation comment for the function. • Add a private int ageOfList data field to MySLL. We will use this data field to store the ”age” of a MySLL. The age of a MySLL is the number of nodes that have ever been added to the list. The age is unchanged when a node is removed. • Modify the public void add(int index, E item) to update ageOfList each time a new node is successfully added. • Using ageOfList and findOldest, write a function public boolean oldestRemains() to deter- mine if the first node ever added to the linked list still remains in the linked list. Include this function in MySLL and write a javadoc-style documentation comment for the function. Bonus question (.5 pts) Come up with alternative approach to determine if the first node ever added to the linked list remains in the linked list. You do not have to implement your proposed idea. Instead to receive credit, answer the following: • Provide a short write-up of the high level concept in your approach. • Specify any data fields you will be adding to either Node or MySLL. • Specify any currently existing function in MySLL that your approach would change. For each function, update the javadoc-style documentation comment to include your new functionality. Specify how your changes would impact the runtime of the function. • Specify any new function you propose adding to MySLL. For each function, write a javadoc- style documentation comment. One function must be public boolean oldestRemains() which returns true if the oldest node remains and false otherwise. Specify the runtime of each function. • Evaluate the pros and cons of your approach compared to the one you implemented according to the above instructions. Your approach does not have to be ”better” in order to receive full credit. Criteria for comparison include – Does one approach add fewer instance variables to Node or MySLL that must be stored and kept track of. – Does one approach preserve a more efficient runtime for existing MySLL methods? – Is the runtime to determine public boolean oldestRemains() different across the ap- proaches. 5 Problem 4 (2 pts) Suppose that you are given a class that implements a Stack and you execute the following lines of code: public static void main(String [] args){ 2 Stack myStack = new Stack (); myStack.push (3); 4 myStack.push (9); myStack.push (7); 6 x = myStack.peek (); y = myStack.pop(); 8 myStack.push(x+y); z = myStack.pop(); 10 w = myStack.pop(); } What are the values of: • x = • y = • z = • w = Problem 5 (2 pts) Write a new queue method called public void moveToRear that moves the el- ement currently at the front of the queue to the rear of the queue. The element that was second in line will be the new front element. Add this method to the class LinkedQueue. To receive full credit, you may not use the offer(), poll(), or peek() methods (or reimplement them under different names), nor the constructor for a Node. You will need to manipulate the internal data fields of LinkedQueue directly. Correct implementations that use these functions will receive 1 out of a possible 2 points. 6 Bonus Question (.5 pts) Come up with a real-world application for a data structure we covered in class. To receive credit, your answer must go beyond ”We need to store data and this data structure stores data”. Make a case that the data structure you advocate for is well-suited to the scenario you describe. 7