Answers for these questions please urgent!!$-$ Short Answer: Data Abstraction

$1.$ When would it make the most sense for the Point$2$D class to use polar coordinates for its internal

representation? $[5$ points$]$

$($a$)$ When fast trigonometry functions are available.

$($b$)$ When the polar coordinates accessor and mutator methods will be used most often.

$($c$)$ When the API provides both Cartesian and polar coordinate methods.

$($d$)$ It never ever matters!

$2.$ When it comes to functionality $($not performance$),$ is it important to know how an ADT is internally

implemented? Explain. $[10$ points$]$

Short Answer: Stacks, Lists, and Generics

$3.$ Consider an implementation of unsorted singly linked list. Suppose it has a representation with a head

and a tail pointer, where head's next eventually leads to tail. Given this representation, which of the

following operation cannot be implemented in O$(1)$ time? $[5$ points$]$

$($a$)$ Insertion before the head node of the linked list.

$($b$)$ Insertion after the tail node of the linked list.

$($c$)$ Deletion of the head node of the linked list.

$($d$)$ Deletion of the tail node of the linked list.

$4.$ Assume that we are storing the ASU IDs of $50$ students in a singly linked list. Due to a security breach,

one entire node has been corrupted in the middle. In this case, will all the $50$ nodes still be accessible

to us$?[5$ points$]$

$($a$)$ Yes $-$ the Java garbage collector will delete the bad node from the list.

$($b$)$ Yes $-$ although we do not have a previous reference, we can use the tail reference.

$($c$)$ No any nodes that follow the corrupted node will be inaccessible.

$($d$)$ No $-$ the entire list will be lost and the data will be inaccessible.

Short Answer: Analysis of Algorithms

$5.$ Consider the following growth function: $[5$ points$]$

f$1($n$)=100+10$log$($n$)$n$2+45$n

What is the Big$-$Oh order of this function? You should provide a relatively tight upper bound $($e$.$g$.,$

not just $2$n$).$

$($a$)$ O$($n$3)$

$($b$)$ O$($n$2$log$($n$))$

$($c$)$ O$($nlog$($n$))$

$($d$)$ O$($n$2)$

$($e$)$ O$($log$($n$))$

$6.$ What is the Big$-$Oh order of the following code fragment? The fragment is parametrized on the variable

n$.$ Assume that you are measuring the number of println calls. You should provide a relatively tight

upper bound $($e$.$g$.,$ not just $2$n$).[5$ points$]$

f o r $($ int i $=1$ ; i n ; i $++)$

f o r $($ int j $=1$ ; j n ; j $*=10)$

System $.$ out $.$ p r i n t l n $("$ Nested l o o p s $!")$ ;

$($a$)$ O$($n$2)$

$($b$)$ O$($n$2$logn$)$

$($c$)$ O$($nlogn$)$

$($d$)$ O$($n$)$

$($e$)$ Does not exist.

Short Answer: Analysis, Design, and Justication I

$7.[$Acu$$a$]$ Consider the following problem, and categorize it according to the dierent axis of problem

complexity: nd the moves to win a game of chess with standard rules. $[5$ points$]$

$($a$)$ Open$-$ended, Well$-$dened

$($b$)$ Open$-$ended, Ill$-$dened

$($c$)$ Close$-$ended, Well$-$dened

$($d$)$ Close$-$ended, Ill$-$dened

$8.[$Vega$]$ Suppose you are given the following problem:

Problem: Consider designing a program that reads a list of IDs from the user and then sorts them and prints them all back to the user. Short Answer: Analysis of Algorithms

Consider the following method, excerpted from a protein structural prediction algorithm. Assume that

any variables not given as parameters are available as globals.

Give a growth function for $m{d}_{?}$fragment that counts the number of assignments in the inner loop

based on $n.[5$ points$]$

Consider the following algorithm that implements linear search:

If you were asked to analyze the performance of this algorithm, would it be useful to write a growth

function that counts the number of times the return false statement will execute? That is$,$ use the

number of returns as the cost metric. Explain. $[10$ points$]$Create an Analysis of this problem by identifying any ill$-$dened parts of the problem, making reason$-$

able assumptions for each $($if possible$),$ and identifying any important metrics. Justify any assumptions you make. $[10$ points$]$ P and C$.$ What would

the result of executing the following code be$?$ Draw the resulting list using box and arrow notation and include any variables. $[10$ points$]$

head.getNext$().$getNext$().$setNext$($head$.$getNext$())$; What would be the difference in memory usage for storing a thousand elements in an array vs a linked

list? Which takes less space? Explain. $[10$ points$]$