Lecture Overview

When designing a program's data, we have three steps:

• Step 1: come up with an Interface or Abstract Data Type (ADT) for the data. An ADT is written in English and perhaps uses mathematical notation to describe the semantics (meaning) of the operations that must be performed on the data. I talked about the Queues, Lists, USets, and Sets from Section 1.2. These kind of ADTs are general ADTs intended for broad use, but during program design we might also come up with domain specific ADTs. For example, if we are writing a music player, we need an ADT for the library of songs. Perhaps the ADT builds on the List ADT, but has operations for finding all songs by a particular author and so on.

• Step 2: once we have decided on an ADT, we next sketch out various potential implementations of the ADT using pseudocode. Most ADTs will have more than one implementation, so in this phase we will describe as many of these implementations as we can. Of course, we don't want to spend the time implementing each of these implementations, so for the most part we describe the implementations using pseudocode.
  • Step 2a: for each implementation, we then estimate its time complexity and space complexity, analyizing the worst case, average case, and amortized cost of each of the operations on the ADT. We are estimating the cost of these things on a simplified model of computation.
  • Step 2b: we compare the estimates of the various implementations to pick a specific implementation of our ADT.

• Step 3: actually implement the ADT in the programming language for our project.

I started talking about Step 2 for the Stack ADT, although we will have to finish it next time.

Exercises

From the list of exercises

• Exercise 1..1 For now, just describe in pseudocode how you would solve each of these problems. We will come back to this exercise in future lectures, where I will ask you to estimate speed and eventually implement using C++. But for now, just figure out if you would use a Stack, Queue, List, USet, SSet, and briefly describe how you would do so.

• Exercise 1..2 on Dyck words. Describe using pseudocode how you can verify if a string is a Dyck word using a stack.