Instructions

· Your problem sets are graded on both correctness and clarity of communication. Solutions that

are technically correct but poorly written will not receive full marks.

·  Each problem set may be completed as an individual or in a group of two students. Partners do

not need to be registered in the same section of the course. If you work with a partner, you should not be dividing the questions between partners in such a way that one partner completes some of the questions without the involvement of the other partner. You are both responsible for the content that your group submits for each question and for learning that course material. If the partnership breaks down at the last minute, both partners are responsible for all the questions.

·  Solutions must be typeset electronically, and submitted to MarkUs as a PDF with the filename

ps2.pdf.  Handwritten submissions will receive a grade of zero.  Neatly handwritten diagrams are fine.

· Your submitted file should not be larger than 9MB. Your file might exceed this limit if you use

a word processor like Microsoft Word to create a PDF; if it does, you should look into PDF compression tools to make your PDF smaller, although please make sure that your PDF is still legible before submitting!

·  The work you submit must be that of your group; you may not use or copy from the work of

other groups, or from external sources like websites or textbooks.  We recognize that although it  should  not  be  necessary to  do  so, students may wish to read a different textbook or reference material about course topics. This is not prohibited, but you must declare it.  (See the next bullet). All the information you need has been covered in lectures and/or in our textbook.

·  On the front page of your submission, you must list every source of information you used to

complete this homework (other than your lecture notes, our textbook, or conversations from office hours, lectures, or our Piazza discussion board). For example, indicate clearly the name of every student from another group with whom you had any discussions, the title and sections of every textbook you consulted (excluding the course textbook), the source of every web document you used or website you visited (other than our own CSC263 site.)

Question 1

You have been hired by the director of the Emergency Department at a busy hospital to design a patient intake system that works in a unique way.  While each patient still gets assigned a specific priority based on the severity of their case as in a normal priority queue, now the hospital plans to use at most p priorities to categorize ER patients.  You don’t know exactly what these priorities will be, just that they will be integers and there will be at most p of them used for all the patients. You have already designed the IntakeQueue ADT which will manage the patient priority data.  It has the following operations:

·  Insert(ID,  priority): Add patient with this ID and this priority to the queue.

· Next():  Remove and return the patient with the highest priority value from the queue.   If

multiple patients in the queue have the highest priority, select the one that has been in the queue the longest.

Each patient ID is unique, but you do not need to check for this.  Staff will never try to add a patient to the IntakeQueue who is already in the queue.

(a)  Describe a data-structure to efficiently implement your ADT so that each operation runs in

O(log p) on average.  For each operation, give an explanation of the algorithm in English sen- tences.

(b)  Draw a diagram of the data structure after the following sequence of operations:

Insert(p1,8), Insert(p12,5), Insert(p3,3), Insert(p15,3),          Insert(p8,7), Insert(p6,8), Insert(p5,5), Insert(p2,3), Next()

(c)  For each operation, justify the correctness and complexity of your algorithm.

Question 2

A factory that makes ASTM-compliant masks has contacted you to design an ADT that helps them monitor their mask sales. Masks are made in equally-sized batches, and each batch has the following data associated with it:

· batchID: a unique integer associated with each batch of masks

·  series:  a 5-digit integer indicating which series the batch belongs to.  The factory has been

experimenting with different mask series based on consumer feedback, and each new series is identified as the previous series + 1

·  sales: an integer indicating the number of masks sold from this batch.  This is the number of

mask, not a percentage.

Here is a small sample of the data.  BatchIDs are unique across all batches not just within a series. Although series numbers always increase with time, batchIDs do not necessarily increase with time. So BatchIDs do not necessarily increase with increasing series numbers.

Your task is to implement the following operations to run in worst-case O log(n) time where n is the number of batches in the collection:

·  Insert(batchID,  series,  sales) Add a batch with the associated data to the collection.

In the case that the factory encounters an error and a batch with batchID already exists in the collection, calling Insert updates the series but does not change the sales.

·  Delete(batchID) Remove all data associated with this batchID from the collection. ·  Search(batchID) Return the information in the collection about this batch.

·  TopSoldAfter(benchmark) Of all the batches made starting from benchmark series, return

the batchID of the one that has sold the most. If multiple batches meet the series criteria and are tied for the most sales, return any one of them.

·  LeastSoldAfter(benchmark)  Of all the batches made starting from benchmark series,

return the batchID of the one that has sold the least.   If multiple batches meet the series criteria and are tied for the least sales, return any one of them.

(a)  Describe the data structure you will use to implement this ADT. If your solution uses an aug-

mentation of one or more standard data structures, be clear about any extra information that will be stored.

(b)  Draw a diagram of your data structure containing all the data from the table above.  You may

assume that the batches were inserted in any order you wish. Be sure to show any other variables that are stored in your data structure.

(c)  Describe the algorithm for Insert and justify that it runs in O(log(n)) time.        (d)  Describe the algorithm for Delete and justify that it runs in O(log(n)) time.        (e)  Provide pseudocode for TopSoldAfter and justify that it runs in O(log(n)) time.

(f)  Describe the algorithm for LeastSoldAfter (no need for pseudocode) and justify that it runs

in O(log(n)) time.

Question 3

After our lecture on hashing, you find yourself really excited about hashing with chaining. Your friend on the other hand thinks that hashing with open addressing is a very neat idea to handle collisions. So you design a hash table TC  (meaning Table with Chains) which uses chaining to resolve collisions. Each chain in TC  is a doubly-linked list where insertions are done at the front of the list. Your friend designs a hash table TP  (meaning Table with Probing) which handles collisions using linear probing. When deleting items from TP , the item deleted is replaced with the special “tombstone” marker. For both tables, you use the same hash function and TC  and TP  have the same number of buckets which is much larger than the number of items you wish to hash.  Then the two of you go to a third friend (who now works at a big tech company) to help you decide which is better. She asks you the following questions which you must answer as your submission for this problem.

(a) If you perform a sequence S of Insert and Delete operations on your tables, which table is

going to require fewer comparisons?  Assume that S is comprised of a sequence of n operations O1 , O2 , O3 , ..., On  where 1 < i < n. n is smaller than the number of buckets. Use KCi  to refer to the number of item comparisons made when performing Oi  on TC .  Similarly, use KPi  to refer to the number of item comparisons made when performing (the same) Oi  on TP . For 1 < i < n, consider the following question:  is KCi   < KPi  or KCi   > KPi ?  Show your work and explain your answer with sufficient details. For this question, assume that the parameter to the Delete operation is a pointer to the item to be deleted.

(b)  Does your answer in part (a) remain true if you include the Search operations in the sequence?

Justify your answer.