CMPT 280– Intermediate Data Structures and Algoirthms Assignment 2

Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

Department of Computer Science

CMPT 280– Intermediate Data Structures and Algoirthms

Assignment 2

Date Due: February 3, 2023, 6:00pm

Total Marks: 41

General Instructions

• Assignments must be submitted using Canvas.

• Responses to written (non-programming) questions must be submitted in a PDF file, plain text file ( .txt), Rich Text file ( .rtf), or MS Word’s .doc or .docx files. Digital images of handwritten pages are also acceptable, provided that they are clearly legible, and they are in either the JPEG or PNG image format.

• Programs must be written in Java.

• VERY IMPORTANT: Canvas is very fragile when it comes to submitting multiple files.  We insist that you package all of the files for all questions for the entire assignment into a ZIP archive file. This can be done with a feature built into the Windows explorer (Windows), or with the zip terminal command (LINUX and Mac).  We cannot accept any other archive formats.  This means no tar, no gzip, no 7zip.  Non-zip archives will not be graded.  We will not grade assignments if these submission instructions are not followed.

Your Tasks

The questions on this assignment are about timing analysis and ADT specification. There is no program- ming on this assignment.

Question 1 ():

For each of the following functions, give the tightest upper bound chosen from among the usual simple functions listed in Section 3.5 of the course readings. Answers should be expressed in big-O notation.

(a) (1 point) f1 (n) = n2 log2 n + n3 log280 n +

(b) (1 point) f2 (n) = 0.4n4 + n2 log n + log2 (2n )

(c) (1 point) f3 (n) = 4n0.7 + 29n log2 n + 280

Question 2 ():

Suppose the exact time required for an algorithm A in both the best and worst cases is given by the function

TA(n) = n2 + 42 log n + 12n3 + 280^n

(a) (2 points) For each of the following statements, indicate whether the statement is true or false.

1. Algorithm A is O(log n)

2. Algoirthm A is O(n2 )

3. Algoirthm A is O(n3 )

4. Algoirthm A is O(2n )

(b) (1 point) Can the time complexity of this algorithm be expressed using big-Θ notation?  If so, what is it?

Question 3 ():

If possible, simplify the following expressions. Hint: See slide 11 of topic 3 of the lecture slides!

(a) (1 point) O(n2 ) + O(log n) + O(n log n)

(b) (1 point) O(2n ) · O(n2 )

(c) (1 point) 42O(n log n) + 18O(n3 )

(d) (1 point) O(n2 log2 n2 ) + O(m)              (yes, that’s an‘m’, not a typo; note that m is independent of n)

Question 4 ():

Consider the following Java code fragment:

✞

//   Print   out   all   ordered   pairs   of   numbers   between   1   and  n

for ( i  =   1;   i   <=  n ;   i ++)   {

for ( j  =   1;   j   <=  n ;  j ++)   {

System . out . println (   i  +   " ,   "  +  j )   ;

}

}

(a) (3 points) Use the statement counting approach to determine the exact number of statements that

are executed when we run this code fragment as a function of n. Show all of your calculations.

(b) (1 point) Express the answer you obtained in part (a) in big-Θ notation (since the best and worst cases are the same – there is only one path of execution through this loop).

Question 5 ():

Consider the following pseudocode:

✞                                                                                               Algorithm   r o u n d R o b i n T o u r n am e n t ( a )

This   algorithm   generates   the   list   of  matches   that  must   be

played   in   a  round - robin   pirate - dueling   tournament   ( a   tournament   where

each   pirate   duels   each   other   pirate   exactly   once ) .

names   of   pirates   in   the   tournament

n  =  a . length

for   i  =  0  to  n - 1

for   j  =   i +1  to  n - 1

print   a [ i ]  +   "   duels   "  +  a [ j ]

Note: the pseudocode for  i  =  a  to  b means that the loop runs for all values of i between a and b, inclusive, that is, including the values a and b.

(a) (6 points) Use the statement counting approach to determine the exact number of statements that are executed by this pseudocode as a function of n. Show all of your calculations.

(b) (1 point) Express the answer you obtained in part a) in big-Θ notation (since, again, the best and worst cases are the same).

Question 6 (3 points):

Using the active operation approach, determine the time complexity of the pseudocode in question 5. Show all your work and express your final answer in big-Θ notation.

Question 7 (6 points):

Consider the following pseudocode.

✞                                                                                               Algorithm   multiSearch (  data ,   target   ):

data :     a   list   of   arrays   of   integers ;   in   each   array   the

integers   are   sorted   in   ascending   order ;  the   list

’ data ’  has   a   cursor .

target :   an   integer

//   Iterate   over   the   arrays   in   the   list   ’ data ’  using

//   its   cursor :

data . goFirst ()

found   =   false

while (   ! data . after ()   and   ! found   )  {

//   search   for   integer   ’ target ’   in  A

found   =  binarySearch ( data . currentItem () ,   target )

data . goForth ()

Using the active operation approach to timing analysis determine the time complexity of this pseu- docode in the worst case.  Assume that the list of arrays contains n arrays and that each array has exactly m items in it.  Be sure to clearly identify the line that is the active operation.  Show all your work and express your final answer in Big-O notation (because we are doing a worst-case analysis).

Question 8 (11 points):

A priority queue is a queue where a numeric priority is associated with each element.  Access to elements that have been inserted into the queue is limited to inspection and removal of the elements with smallest and largest priority only.  A priority queue may have multiple items that are of equal priority.

Give the ADT specification for a bounded priority queue using the specification method described in Topic 7 of the lecture notes.  By “bounded”, it is meant that the priority queue has a maximum capacity specified when it is created, and it can never contain more than that number of items.

Your specification must specify the following operations:

newPriorityQueue: make a new queue

insert: inserts an element with a certain priority

isEmpty: test if the queue is empty

isFull: test if the queue is full

maxItem:  obtain the item in the queue with the highest priority

minItem:  obtain the item in the queue with the lowest priority

deleteMax: remove from the queue the item with the highest priority

deleteAllMax: remove from the queue all items that are tied for the highest priority deleteMin: remove from the queue the item with the lowest priority

frequency:  obtain the number of times a certain item occurs in the queue (with any priority)

Files Provided

None.

What to Hand In

You must submit the following files:

assignment2.doc/docx/rtf/pdf/txt - your answers to questions 1 to 8.  Acceptable file formats are Word ( .doc or  .docx), PDF ( .pdf), rich text ( .rtf), or plain text ( .txt).  Digital images of handwritten pages are also acceptable, provided that they are clearly legible and that they are in JPEG ( .jpg or .jpeg) or PNG ( .png) format, or they are embedded in a Word or PDF file. Other image formats are not accepted and will receive a grade of zero.

If you are submitting a single file, for example, a PDF or DOC containing answers to all questions, you can submit just the document without zipping it.

If you are submitting multiple files (e.g. multiple PNG or JPEG images), submit them in a ZIP file archive.


2023-03-02