The program should be first readable and understand to human

Instructions: [100 points] The final exam is made up of short answer, code analysis and programming. Please provide your responses under the question using this MS Word document and submit to me via the course Blackboard site. Submission is due on Monday, August 10^th at 11:59pm (eastern). Under NO circumstances will late submissions be accepted! Good luck!

Student Full Name: __________________________________ Student ID:______________________

1. [2 points] What makes a program easy to modify?

< The program should be first readable and understand to human. It should be well designed which makes it easy to determine where a changes must take places. And lastly, it should be able to withstand small changes easily, which makes different pieces of the program work relatively independent. >

2. [3 points] Describe the order of magnitude of the following code section using Big(O) notation.

j = 1;

While (j < N)

{

j = j * 2);

}

< O(log2N) >

3. [3 points] What are the benefits we accrue by using a Java interface construct to formally specify the logical level of ADTs?

< It helps us to check the syntax of our specification by compiling interface. It allows to verify the interface to see if it is satisfied by a class that implements the interface. Also we can provide a consistent interface to applications from among alternative implementations of the ADT >

4. [5 points] Suppose we have a linked list of Strings, as defined in the textbook, named presidents. Suppose it contains three nodes, with the first node holding “Adams”, the second node “Washington”, and the third node “Kennedy”. What would be output by the following code:

LLStringNode temp = presidents;

while (temp != null)

{

temp = temp.getLink();

}

System.out.println(temp.getInfo());

< Since we are attempting to access an object through a null reference, there will be an error message printed. >

5. [3 points] Suppose a collection object is defined to hold elements of class Object, and you use it to store String objects. Describe what you must do when you retrieve an object from the collection and intend to use it as a String.

< The object must cast into a string. >

6. [8 points] Show what is written by the following segment of code, given that item1, item2, and item3 are int variables, and stack is an object that fits our abstract description of a stack. Assume that you can store and retrieve variables of type int on stack.

item1 = 1;

item2 = 0;

item3 = 4;

stack.push(item2);

stack.push(item1);

stack.push(item1 + item3);

item2 = stack.top();

stack.push (item3*item3);

stack.push(item2);

stack.push(3);

item1 = stack.top();

stack.pop();

System.out.println(item1 + ” ” + item2 + ” ” + item3);

while (!stack.isEmpty())

{

item1 = stack.top();

stack.pop();

System.out.println(item1);

}

<Please enter your response using this font type, size and color>

7. [2 points] Explain the relationship between dynamic storage allocation and recursion.

< Recursion can be supported by systems and languages that support dynamic storage allocation.Dynamically allocated memory exists until it is released either explicitly by the programmer, exiting a block, or by the garbage collector. In recursion we will be using the same piece of function or variables repeatedly. So they are required for a long time which is supported by dynamic memory allocation. Also we cannot estimate the memory required, in prior in recursion so as to allocate a static memory. So we need dynamic memory allocation. Hence they are closely related to each other>

8. [8 points] Analyze the factorial method and answer the following questions:

int factorial (int n)

{

if (n > 0)

return (n * factorial (n – 1));

else

if (n == 0)

return 1;

}

a. What is the base case?

b. What is the general case?

c. What are the constraints on the argument values?

d. What does the method do?

<Please enter your response using this font type, size and color>

9. [2 points] What are the three interfaces we defined related to our Queue ADT?

< QueueInterface , BoundedQueueInterface, UnboundedQueueInterface >

10. [2 points] Describe in general terms the approach we use to implement an unbounded queue based on an array.

<Please enter your response using this font type, size and color>

11. [2 points] What does it mean for a class’s equals and compareTo methods to be “consistent”?

<Please enter your response using this font type, size and color>

12. [10 points] Questions a-e below refer to the following figure:

a. What are the ancestors of node J?

b. What are the descendants of node T?

c. What are the descendants of node B?

d. What is the order in which the nodes are visited by a preorder traversal?

e. What is the order in which the nodes are visited by a postorder traversal?

<Please enter your response using this font type, size and color>

13. [5 points] If a heap is used to implement a priority queue, what is the Big O efficiency of the enqueue operation, assuming the size of the priority queue is N?

< log₂N>

14. [10 points] What would be the order of the following list after two iterations of the “inner” part of the Insertion Sort algorithm?

13 4 16 19 2 15 12 3 23 20

< 4 13 16 19 2 15 12 3 23 20>

15. [10 points] Suppose we are using Merge Sort to sort the following list of numbers. What would be the order of the list immediately before the execution of the merge method in the original (non-recursive) call to mergesort?

13 4 16 19 2 15 12 3 23 20

< 2 3 4 12 13 15 16 19 20 23>

16. [25 points] Programming Sorting Algorithms: For this section, use theSorts.java test harness (provided by instructor).

a. Describe an approach to modifying theSorts.java program so that after calling a sorting method the program prints out the number of swaps needed by the sorting method.

b. Implement your approach.

c. Test your new program by running theselectionSort method. Your program should report 49 swaps.

d. Now, modify your program to also output the number of comparisons (compares) needed. You must include one or more statements to increment your counter within the sorting methods themselves. For each of the listed methods, make and test the changes needed, and list both the number of swaps and the number of compares needed by the Sorts program to sort an array of 50 random integers.

selectionSort swaps:____ compares:____

bubbleSort swaps:____ compares:____

shortBubble swaps:____ compares:____

insertionSort swaps:____ compares:____

<Please enter your response using this font type, size and color>

Our website has a team of professional writers who can help you write any of your homework. They will write your papers from scratch. We also have a team of editors just to make sure all papers are of HIGH QUALITY & PLAGIARISM FREE. To make an Order you only need to click Ask A Question and we will direct you to our Order Page at WriteDemy. Then fill Our Order Form with all your assignment instructions. Select your deadline and pay for your paper. You will get it few hours before your set deadline.