CS 61B ADTs and Asymptotic Analysis
Spring 2021
1 ADT Matchmaking
Match each task to the correct Abstract Data Type pairs.
1. You want to keep track of all the unique users who have logged on to your system.
2. You are creating a version control system and want to associate each file name with a Blob.
3. We are running a server and want to service clients in the order they arrive.
4. We have a lot of books at our library and we want our website to display them in some sorted order. We have multiple copies of some books and we want each listing to be separate.
Discussion 7: March 1, 2021
for the job by drawing a line connecting matching
a) List b) Map c) Set
d) Queue
1) c) You should use a set because we only want to keep track of unique users (i.e. if a user logs on twice, they shouldn’t show up in our data structure twice). Additionally, our task doesn’t seem to require that the structure is ordered.
2) b) You should use a map. Maps naturally let you pair a key and value, and here we could have the file name be the key, and the blob be the value.
3) d) We should use a queue. We can push clients to the front of the queue as they arrive, and pop them off the queue as we service them.
4) a) We should use a list because a list is an ordered collection of items. Additionally, we need to allow for duplicate items because we have multiple copies of some books.
2 I Am Speed
Give the worst case and best case running time in Θ(·) notation in terms of M and N. Assume that comeOn() is in Θ(1) and returns a boolean.
if (comeOn()) { j += 1;
} else {
j *= 2;
for(inti=0;i