Starting from:
$30
CS20B Homework 3 Recursion, Queues and Collections Solved
1 Questions
.
1. (8 points) Given the following method:
int
exer(int num)
{
}
if (num == 0) return 0;
else
return num + exer(num + 1);
1
2
3
4
5
6
7
(a) Is there a constraint on the value that can be passed as an argument for this method to pass the smaller-caller test?
(b) Is exer(7) a valid call? If so, what is returned from the method? (c) Is exer(0) a valid call? If so, what is returned from the method?
(d) Is exer(-5) a valid call? If so, what is returned from the method?
2. You must assign the grades for a programming class. Right now the class is studying recursion, and students have been given this assignment: Write a recursive method sumValues that is passed an index into an array values of int (this array is accessible from within the sumValues method) and returns the sum of the values in the array between the location indicated by index and the end of the array. The argument will be between 0 and values.length inclusive. For example, given this configuration:
then sumValues(4) returns 12 and sumValues(0) returns 34 (the sum of all the values in the array). You have received quite a variety of solutions. Grade the methods below. If the solution is incorrect, explain what the code actually does in lieu of returning the correct result. You can assume the array is “full.” You can assume a “friendly” user-the method is invoked with an argument between 0 and values.length.
Figure 1: Example
(a)
int
sumValues(int index)
{
}
if (index == values.length) return 0;
else return index + sumValues(index + 1);
1
2
3
4
5
6
7
8 (b)
int
sumValues(int index)
{
}
int sum = 0; for (int i = index; i < values.length; i++) sum = sum + values[i];
return sum;
1
2
3
4
5
6
7 (c)
int
sumValues(int index)
{
}
if (index == values.length) return 0;
else return (1 + sumValues(index + 1);
1
2
3
4
5
6
7 (d)
int
sumValues(int index)
{
}
return values[index] + sumValues(index + 1);
1
2
3
4 (e)
int sumValues(int index)
{
if (index values.length) return 0;
else return values[index] + sumValues(index + 1);
}
1
2
3
4
5
6
7
Figure 2: Comparison of Collection Implementations.
(f)
int
sumValues(int index)
{
}
if (index = values.length) return 0;
else return values[index]+sumValues(index + 1);
1
2
3
4
5
6
7 (g)
int
sumValues(int index)
{
}
if (index < 0) return 0;
else return values[index] + sumValues(index - 1);
1
2
3
4
5
6
7
8
3. Read Chapter 5, view all the code examples there: even those we didn’t see in the class (the complete code for classes from this Chapter is provided for you, you can also find partial code in the book). Look at the table provided in Chapter 5 (see Figure 2 in this file). Explain the following:
(a) Why does SortedArrayCollection exhibit logarithmic time for contains and get methods?
(b) Why do ArrayCollection and LinkedCollection exhibit O(1) time for add (adding an element method), while SortedArrayCollection exhibits a worse O(N) time for the same method?
(c) How is O(1) accomplished for size method for all of these collections in the table?
4. a) Which method do we need to implement to check if the contents of our objects are the same? b) Write its signature. c) Is it inherited from some class? d) If yes, which one?
5. Based on the equals method for Circle objects defined in Section 5.4, “Comparing Objects Revisited,” what is the output of the following code sequence and why! (you need to provide 8 answers for each printout, and a very short explanation of why it is so)?
1 Circle c1 = new Circle(5);
2
3 Circle c2 = new Circle(5);
4
5 Circle c3 = new Circle(15);
6
7 Circle c4 = null;
8
9 System.out.println(c1 == c1);
10
11 System.out.println(c1 == c2);
12
13 System.out.println(c1 == c3);
14
15 System.out.println(c1 == c4);
16
17 System.out.println(c1.equals(c1));
18
19 System.out.println(c1.equals(c2));
20
21 System.out.println(c1.equals(c3));
22
23 System.out.println(c1.equals(c4));
6. (6 points) Consider the following interfaces:
1 public interface Event{
2 public void RSVP();
3 }
4
5 public interface PublicEvent extends Event{
6 public void doSecurityCheck();
7 }
8
9 public interface PrivateEvent extends Event{
10 public void checkIdentification();
11 }
12
13 public interface PartneredEvent extends Event{ 14 public void findPartner(); 15 }
Which method(s) should implement a class
(a) called Hockey that implements PublicEvent?
(b) called Prom that implements PrivateEvent and PartneredEvent.
2 Programming exercises
For the programming exercises, please follow the provided instructions in the instructions.pdf. Each of the exercises below should be a separate zip of a Java project.
1. Project 1: Attached to this homework is a .java file called LinkedListReverse.java. Part of it is implemented for you and there is a main method already written that will test your code. A recursive printing of a linked list is also provided for you in method called recRevPrintList. You need to implement iterRevPrintList (method signature is given to you) which iteratively, not recursively, does the same - prints a linked list in reverse. Make sure you include and import all necessary support classes for this code to work.
2. Add the following methods to the LinkedQueue class (from ch04.zip), and create a test driver for each to show that they work correctly. In order to practice your linked list coding skills, code each of these methods by accessing the internal variables of the LinkedQueue, not by calling the previously defined public methods of the class.
(a) String toString() creates and returns a string that correctly represents the current queue. Such a method could prove useful for testing and debugging the class and for testing and debugging applications that use the class. Assume each queued element already provides its own reasonable toString method.
(b) void remove(int N) removes the front N elements from the queue; throws QueueUnderflowException if less than N elements are in the queue.
3. Add the following methods to the ArrayCollection class, and create a test driver for each to show that they work correctly. Note that you can find the implementation of the classes mentioned here in ch05.zip or check the book for the implementation details. Some classes require imports from other packages. All the packages you need and classes can be found in the code I shared with you. In order to practice your array coding skills, code each of these methods by accessing the internal variables of the ArrayCollection, not by calling the previously defined public methods of the class. Make sure you have a driver class that will put your methods to use (and also serve to check whether your methods are correct).
(a) String toString() creates and returns a string that correctly represents the current collection. Such a method could prove useful for testing and debugging the class and for testing and debugging applications that use the class. Assume each stored element already provides its own reasonable toString() method.
(b) int count(T target) returns a count of the number of elements e in the collection such that e.equals(target) is true.
(c) void removeAll(T target) removes all elements e from the collection such that e.equals(target) is true.
(d) ArrayCollection<T combine(ArrayCollection<T other) creates and returns a new ArrayCollection object that is a combination of this object and the argument object. Choose any way to combine these collections and make sure you include comments to explain what the combination is. (Note: add the signature of this method to CollectionInterface
4. Create a FacebookUser class that includes numFriends and username attributes of type int and String, respectively, both set by a constructor. The attribute numFriends represents the number of friends a user with username has. Implement an equals method that such that two FacebookUsers are equal if they have the same username.
In the homework package I gave you a FacebookUser.java code. Use this code to test whether your equals works well.
.
1. (8 points) Given the following method:
int
exer(int num)
{
}
if (num == 0) return 0;
else
return num + exer(num + 1);
1
2
3
4
5
6
7
(a) Is there a constraint on the value that can be passed as an argument for this method to pass the smaller-caller test?
(b) Is exer(7) a valid call? If so, what is returned from the method? (c) Is exer(0) a valid call? If so, what is returned from the method?
(d) Is exer(-5) a valid call? If so, what is returned from the method?
2. You must assign the grades for a programming class. Right now the class is studying recursion, and students have been given this assignment: Write a recursive method sumValues that is passed an index into an array values of int (this array is accessible from within the sumValues method) and returns the sum of the values in the array between the location indicated by index and the end of the array. The argument will be between 0 and values.length inclusive. For example, given this configuration:
then sumValues(4) returns 12 and sumValues(0) returns 34 (the sum of all the values in the array). You have received quite a variety of solutions. Grade the methods below. If the solution is incorrect, explain what the code actually does in lieu of returning the correct result. You can assume the array is “full.” You can assume a “friendly” user-the method is invoked with an argument between 0 and values.length.
Figure 1: Example
(a)
int
sumValues(int index)
{
}
if (index == values.length) return 0;
else return index + sumValues(index + 1);
1
2
3
4
5
6
7
8 (b)
int
sumValues(int index)
{
}
int sum = 0; for (int i = index; i < values.length; i++) sum = sum + values[i];
return sum;
1
2
3
4
5
6
7 (c)
int
sumValues(int index)
{
}
if (index == values.length) return 0;
else return (1 + sumValues(index + 1);
1
2
3
4
5
6
7 (d)
int
sumValues(int index)
{
}
return values[index] + sumValues(index + 1);
1
2
3
4 (e)
int sumValues(int index)
{
if (index values.length) return 0;
else return values[index] + sumValues(index + 1);
}
1
2
3
4
5
6
7
Figure 2: Comparison of Collection Implementations.
(f)
int
sumValues(int index)
{
}
if (index = values.length) return 0;
else return values[index]+sumValues(index + 1);
1
2
3
4
5
6
7 (g)
int
sumValues(int index)
{
}
if (index < 0) return 0;
else return values[index] + sumValues(index - 1);
1
2
3
4
5
6
7
8
3. Read Chapter 5, view all the code examples there: even those we didn’t see in the class (the complete code for classes from this Chapter is provided for you, you can also find partial code in the book). Look at the table provided in Chapter 5 (see Figure 2 in this file). Explain the following:
(a) Why does SortedArrayCollection exhibit logarithmic time for contains and get methods?
(b) Why do ArrayCollection and LinkedCollection exhibit O(1) time for add (adding an element method), while SortedArrayCollection exhibits a worse O(N) time for the same method?
(c) How is O(1) accomplished for size method for all of these collections in the table?
4. a) Which method do we need to implement to check if the contents of our objects are the same? b) Write its signature. c) Is it inherited from some class? d) If yes, which one?
5. Based on the equals method for Circle objects defined in Section 5.4, “Comparing Objects Revisited,” what is the output of the following code sequence and why! (you need to provide 8 answers for each printout, and a very short explanation of why it is so)?
1 Circle c1 = new Circle(5);
2
3 Circle c2 = new Circle(5);
4
5 Circle c3 = new Circle(15);
6
7 Circle c4 = null;
8
9 System.out.println(c1 == c1);
10
11 System.out.println(c1 == c2);
12
13 System.out.println(c1 == c3);
14
15 System.out.println(c1 == c4);
16
17 System.out.println(c1.equals(c1));
18
19 System.out.println(c1.equals(c2));
20
21 System.out.println(c1.equals(c3));
22
23 System.out.println(c1.equals(c4));
6. (6 points) Consider the following interfaces:
1 public interface Event{
2 public void RSVP();
3 }
4
5 public interface PublicEvent extends Event{
6 public void doSecurityCheck();
7 }
8
9 public interface PrivateEvent extends Event{
10 public void checkIdentification();
11 }
12
13 public interface PartneredEvent extends Event{ 14 public void findPartner(); 15 }
Which method(s) should implement a class
(a) called Hockey that implements PublicEvent?
(b) called Prom that implements PrivateEvent and PartneredEvent.
2 Programming exercises
For the programming exercises, please follow the provided instructions in the instructions.pdf. Each of the exercises below should be a separate zip of a Java project.
1. Project 1: Attached to this homework is a .java file called LinkedListReverse.java. Part of it is implemented for you and there is a main method already written that will test your code. A recursive printing of a linked list is also provided for you in method called recRevPrintList. You need to implement iterRevPrintList (method signature is given to you) which iteratively, not recursively, does the same - prints a linked list in reverse. Make sure you include and import all necessary support classes for this code to work.
2. Add the following methods to the LinkedQueue class (from ch04.zip), and create a test driver for each to show that they work correctly. In order to practice your linked list coding skills, code each of these methods by accessing the internal variables of the LinkedQueue, not by calling the previously defined public methods of the class.
(a) String toString() creates and returns a string that correctly represents the current queue. Such a method could prove useful for testing and debugging the class and for testing and debugging applications that use the class. Assume each queued element already provides its own reasonable toString method.
(b) void remove(int N) removes the front N elements from the queue; throws QueueUnderflowException if less than N elements are in the queue.
3. Add the following methods to the ArrayCollection class, and create a test driver for each to show that they work correctly. Note that you can find the implementation of the classes mentioned here in ch05.zip or check the book for the implementation details. Some classes require imports from other packages. All the packages you need and classes can be found in the code I shared with you. In order to practice your array coding skills, code each of these methods by accessing the internal variables of the ArrayCollection, not by calling the previously defined public methods of the class. Make sure you have a driver class that will put your methods to use (and also serve to check whether your methods are correct).
(a) String toString() creates and returns a string that correctly represents the current collection. Such a method could prove useful for testing and debugging the class and for testing and debugging applications that use the class. Assume each stored element already provides its own reasonable toString() method.
(b) int count(T target) returns a count of the number of elements e in the collection such that e.equals(target) is true.
(c) void removeAll(T target) removes all elements e from the collection such that e.equals(target) is true.
(d) ArrayCollection<T combine(ArrayCollection<T other) creates and returns a new ArrayCollection object that is a combination of this object and the argument object. Choose any way to combine these collections and make sure you include comments to explain what the combination is. (Note: add the signature of this method to CollectionInterface
4. Create a FacebookUser class that includes numFriends and username attributes of type int and String, respectively, both set by a constructor. The attribute numFriends represents the number of friends a user with username has. Implement an equals method that such that two FacebookUsers are equal if they have the same username.
In the homework package I gave you a FacebookUser.java code. Use this code to test whether your equals works well.
1 file (0.0bytes)
