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.
2 I Am Speed
Discussion 7: March 1, 2021
for the job by drawing a line connecting matching
a) List b) Map c) Set
d) Queue
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