CSE 214 Computer Science II (Spring 2015)

RECITATION 7 – Maps and Sets

Objective:

1. To study Map and Set
2. Analyze the complexity of operations

1.  Suppose you want to implement a language dictionary. A language dictionary store words and their corresponding meaning. The operations you can perform are insert words to the dictionary, and retrieve the definition given a word. Which data structure you will prefer. Give reason why and why not?

1. Arrays
2. Map
3. Linklist

2. Show the effect of a series of operations on an given map {(7,B), (5,T),(3,Y),(9,H),(2,L)} storing entries with integer keys and single character values.

1. Put(3,K)
2. Get(9)

4. Remove(2)
5. Size()
6. Put(4,I)

3. Let the items of the map is stored on a doubly-linked list, in arbitrary order

What will the worst case time complexity for put(), get() and remove() operation.

4. If we let n denote the size of set S, and m denote the size of set T, what would

be the running time of the operation S.addAll(T), if both sets were implemented as

1. Singly link list
2. Doubly link list

5. If we let n denote the size of set S, and m denote the size of set T, what would

be the running time of the operation S.removeAll(T) when both sets are implemented as

1. Singly link list
2. Doubly link list