Answers to these please urgent!! I sent $18$ questions i dont even know which is answered please help $--1-4$ Short Answer: Data Abstraction $[6$ points$]$

$1.$ If you are given an interface for an ADT, but not an actual source le$,$ how well can you program

against it$?($Hint: there is a type of methods that cannot be specied in an interface.$)[2$ points$]$

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

implemented? $[2$ points$]$

$3.$ Would it be safer $($more secure$/$reliable$)$ to expose an mutable or immutable type to an unknown $3$rd

party library? Explain. $[2$ points$]$

$5-6$ Short Answer: Bags, Stacks and Queues $[8$ points$]$

$4.$ Trace a stack $($called S$)$ through the following operations:

Stack S $=$ new Stack $()$ ;

S $.$ push $($ new I n t e g e r $(2))$ ;

S $.$ push $($ new I n t e g e r $(7))$ ;

I n t e g e r X $=$ S $.$ pop $()$ ;

S $.$ push $($ new I n t e g e r $(8))$ ;

S $.$ push $($ new I n t e g e r $(5))$ ;

I n t e g e r X $=$ S $.$ pop $()$ ;

I n t e g e r Y $=$ S $.$ peek $()$ ;

S $.$ push $($ new I n t e g e r $(3))$ ;

I n t e g e r Z $=$ S $.$ pop $()$ ;

$($a$)$ Give the contents of the stack after this code has been executed. Indicate the elements in order

and label the top. $[2$ points$]$

$($b$)$ Give the contents of the stack after this code has been executed. Indicate the elements in order

and label the top. $[2$ points$]$

$5.$ Trace a queue $($called Q$)$ through the following operations:

Queue Q $=$ new Queue $()$ ;

Q$.$ enqueue $($ new I n t e g e r $(3))$ ;

I n t e g e r X $=$ Q$.$ dequeue $()$ ;

Q$.$ enqueue $($ new I n t e g e r $(12))$ ;

Q$.$ enqueue $($ new I n t e g e r $(5))$ ;

Q$.$ enqueue $($ new I n t e g e r $(1))$ ;

I n t e g e r Y $=$ Q$.$ f i r s t $()$ ;

Q$.$ enqueue $($ new I n t e g e r $(9))$ ;

I n t e g e r Z $=$ Q$.$ dequeue $()$ ;

$($a$)$ What is the value of Y after it has been assigned? $[2$ points$]$

$($b$)$ Give the contents of the queue after the code has been executed. Indicate the elements in order

and label the front. $[2$ points$]$

$7-10$ Short Answer: Analysis of Algorithms $[10$ points$]$

$6.$ What are the Big$-$Oh orders of the following growth functions? You should provide a relatively tight

upper bound. $[2$ points$]$

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

f$2($n$)=$ nlog$10($n$)+$ nlog$2($n$)$

$7.$ Show that the upper bound you give for f$1$ above does indeed hold. $[2$ points$]$

$8.$ Assume you have two algorithms A and B$.$ A is O$($n$),$ and B is O$($n$2).$ Will the algorithm A always

run faster than algorithm B on real$-$world inputs? Explain. $[2$ points$]$

$9.$ 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. $[2$ points$]$

f o r $($ int i $=1$ ; i Math $.$ pow $(2,$ 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 $!")$ ;

$10.$ Consider the following algorithm that implements selection sort:

public s t a t i c void s e l e c t i o n S o r t $($ Comparable $[]$ a $)\{$

int N $=$ a $.$ l e n g t h ;

f o r $($ int i $=0$ ; i $$ N; i $++)\{$

int min $=$ i ;

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

i f $($ l e s s $($ a $[$ j $],$ a $[$ min $]))$ min $=$ j ;

exch $($ a $,$ i $,$ min $)$ ;

$\}$

$\}$

If you were choosing a cost metric $($i$.$e$.,$ what operation should be counted$),$ in order to determine this

algorithm's Big$-$Oh order, what operation would be the best choice? Explain. $[2$ points$]$

$11-14$ Short Answer: Elementary Sorts, Mergesort $[8$ points$]$

$11.$ Embedded hardware with solid state storage $($e$.$g$.,$ EEPROM, ash$)$ has a limit number of writes during

its life cycle. Hence, one sorting algorithm design goal is to minimize the number of writes that are

made. Of the sorting algorithms discussed, which achieves that goal even in worse case? $[2$ points$]$

$12.$ In terms of sorting quickly, would we ever want to use insertion sort $($O$($n$2))$ instead of mergesort

$($O$($nlogn$))?[2$ points$]$

$13.$ Consider the following array: $1,2,8,3,7,4,6,5.$ Show a trace of execution for top$-$down mergesort.

Illustrate how the array is broken down, and then merged into an ordered state. $[2$ points$]$

$14.$ In the lower bound proof for sorting, why does a sorted input require fewer comparisons than an

unsorted one? $($Hint: think about how much you 'learn' from each comparison in both of those

cases.$)[2$ points$]$