Question 1
In this question you will design a data structure to support the following ADT.
Data A collection of Piazza posts for a course where each post has at least the following fields 1
• postID: a unique integer identifying a post within the course
• date: the date when the post was initially created 2
• views: an integer giving the total number of times this post has been viewed
Operations Each of these operations must run in worst-case O log(n) time where n is the number of Piazza
posts in the collection.
• Insert(postID, date, views) Add an item with these values to the collection. If an
item with postID already exists in the collection, calling Insert updates the views but
does not change the date.
• Delete(postID) Remove this item from the collection.
• Search(postID) Return the information in the collection about this post.
• MaxViewedAfter(earliest date) Of all posts on or after earliest date, return
the postID of the one that has the most views. If multiple posts meet the date criteria
and are tied for the most views, return any one of them.
(a) Describe the data structure you will use to implement this ADT. If your solution uses an augmentation 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 with the following values already inserted (in any order
you wish).
(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) Describe the algorithm for Search and justify that it runs in O(log(n)) time.
(f) Provide pseudocode for MaxViewedAfter and justify that it runs in O(log(n)) time.