(60 points)

1. (8 pts) Exercise 1 Chapter 3.

2. (5 pts) Exercise 7 Chapter 3.

3. (5 pts) Write a method to count the number of positive integers in a linked list of integers recursively.

4. (22 pts) Exercise 18 Chapter 3.  You are required to write and execute program code to answer this question.   You are required to submit your programs as part of homework 3. Use the program and determine the counts to compute 3³² and 3¹⁹.   For part c make sure that you perform the recursive call only once at each level and then square the result.  Also make sure that you declare all numbers as "long" instead of "int" so that overflow will not occur.  Finally you will need to instrument your code in order to determine the number of multiplications and recursive calls.  The most straightforward way to accomplish this is to declare counter variables (type long) as member data, and increment them as appropriate. Another option is to design a Counter class to keep track of the count.

5. (12 pts) Exercise 3 Chapter 7.  You are required to show the pseudocode using the ADT stack operations independent of the implementation.

6. (8 pts) Suppose you have a queue aQueue and you want to compute the sum of elements in aQueue, leaving aQueue unchanged.
a. Perform the task using aQueue and an empty auxiliary queue auxQueue.
b. Perform the task using aQueue and an empty auxiliary stack auxStack.
You are required to show the pseudocode using the ADT stack and ADT queue operations independent of the implementation.