Exercises: ADTs and CollectionsFeb 122018
Before attempting these exercises, you should read the posts about abstract data types, arrays and stacks and queues.
- Find the Python code for each of the operations supported by the list, set and dictionary ADTs.
- Write a description of strings as an ADT; explain what kind of data a string is, and list the important operations on strings.
- Explain, in terms of the primitive memory operations ‘read’ and ‘write’, how the ‘get’ and ‘set’ operations on an array can be implemented.
- The union of two sets is a new set containing every item from the first set together with every item from the second set.
In code, write a function using the operations of the set ADT to compute the union of two input sets.
Write another function to compute the intersection of two sets.
- Explain how two stacks can be used to implement a queue.