Mod 3

Question 1

To implement a dynamic array, we need to keep track of three things:

Answer 1

• data – The underlying data storage array for the dynamic array.
• size – The number of elements currently stored in the array.
• capacity – The total number of elements the underlying data storage array has space for before it must be resized.

Question 2

What is Amortized Analysis?

Answer 2

Amortized analysis is the method for analyzing a given operation’s complexity or how much of a resource, especially time or memory, it takes to execute by computing the average cost over the entire sequence. For this technique to be applied, the cost per operation must be known. There also needs to be variation, in which many of the operations in the sequence contribute little cost and only a few operations contribute a high cost to the overall time.

This is exactly the case with the dynamic array insertion (or remove) method.

Question 3

What is Aggregate Analysis?

Answer 3

A version of Amortized analysis, which involves computing an upper bound T on the total cost of a sequence of n operations, and then calculating the amortized cost over n operations as the average cost T / n.

1. Identify where cost is incurred
2. Determine how much cost will be incurred over n operations
3. Compute the amortized cost as the average of total cost (divide by n operations)
4. classify with Big(O)

Question 4

What is encapsulation?

Answer 4

Encapsulation is a mechanism through which we hide the internal details of a data type from a user of that data type, and instead expose a defined interface through which the user interacts with the data type.

Question 5

Describe what an ADT is.

Answer 5

An ADT is a specification that describes how we can interact (i.e., interface) with a data structure. Note that an ADT does not dictate its implementation. As we’ll come to see, an ADT can have multiple possible implementations. It’s important to keep the specification and the implementation separate. While the specification is important to someone using an instance of the data structure, they may not be (nor need to be) aware of the implementation details.

Question 6

Name 3 different ADTs.

Answer 6

Stack
Bag
Queue
Dictionary/Map
Binary Tree
Vector
Set
List

Question 7

What are the operations of a dynamic array?

Answer 7

A dynamic array acts like a static array with adjustable size. When advantageous, a dynamic array can be resized to be more appropriate for the data it stores.

Question 8

Describe the functions that an iterator provides.

Answer 8

Iterators provide an interface to collections by hiding the inner workings of the collection from the user, while still allowing them to get the next element and see if there are any more elements left. They may also provide additional functionality beyond traversal and retrieval.

Question 9

What advantages does using an iterator provide over directly accessing a data structure?

Answer 9

1. For standard libraries, iterators are already optimized.
2. You do not need to know where to start or end.
3. Iterators abstract the mechanics of iteration from the main program.

Question 10

In what situations will an iterator not be helpful when working with a data structure?

Answer 10

Simultaneously stepping through two separate data structures in some complex way, particularly when the data in one dictates position in the other, can cause issues with iterators.