quiz4

An ADT is a description of how data can be accessed and manipulated. In other words, an ADT is an interface allowing the caller to store and retrieve data. A data structure is a concrete realization of an ADT; data structures give specific algorithms to implement the interface that the ADT describes.

Two examples of ADTs are lists and stacks. Lists and stacks are both defined by a collection of routines that allow a user to store and manipulate data (e.g. insertFirst, getLast, etc. for list; pop, push, etc. for stack). Two examples of data structures are linked lists and array lists. Both linked lists and array lists are concrete implementations of the list ADT; each of them give implementations for the interface that the list ADT describes.

An interface is the publicly-accessible methods of a class definition, and it describes what parts of the class users are allowed to access. For example, we have seen many data structures with methods like getSize() and isEmpty() in their interfaces. The interface presents users wiht a clean way to use the class, without worrying about the private details of how the class is implemented.

An implementation is all the private details of how a class methods and data fields are defined.

We have \(P(n) \equiv \sum\limits_{i=1}^{n} i \cdot 2^i = 2^{n+1}(n-1) + 2\).

The base case, \(P(1)\), that is to say \(\sum\limits_{i=1}^{1} i \cdot 2^i = 2^{1+1}(1-1) + 2\). We reduce this as follows:

For the inductive hypothesis, we assume \(P(k)\), that is, we assume that \(\sum\limits_{i=1}^{k} i \cdot 2^i = 2^{k+1}(k-1) + 2\).

For the inductive case, we show that \(P(k)\) implies \(P(k+1)\) for positive \(k\).

As we have shown both the base case and the inductive case, \(P(n)\) must be true for all integers \(n>1\).

We have \(P(n) \equiv \sum\limits_{i=1}^{n} \frac{3}{4^i} = 1 - (\frac{1}{4})^n\).

The base case, \(P(1)\), that is to say \(\sum\limits_{i=1}^{1} \frac{3}{4^i} = 1 - (\frac{1}{4})^1\). We reduce this as follows:

For the inductive hypothesis, we assume \(P(k)\), that is, we assume that \(\sum\limits_{i=1}^{k} \frac{3}{4^i} = 1 - (\frac{1}{4})^k\).

For the inductive case, we show that \(P(k)\) implies \(P(k+1)\) for positive \(k\).

As we have shown both the base case and the inductive case, \(P(n)\) must be true for all integers \(n>1\).

We have \(P(n) \equiv \sum\limits_{i=1}^{n} i \cdot 2^i = 2^{n+1}(n-1) + 2\).

The base case, \(P(1)\), that is to say \(\sum\limits_{i=1}^{1} i \cdot 2^i = 2^{1+1}(1-1) + 2\). We reduce this as follows:

For the inductive hypothesis, we assume \(P(k)\), that is, we assume \(\sum\limits_{i=1}^{k} i \cdot 2^i = 2^{k+1}(k-1) + 2\).

For the inductive case, we show that \(P(k)\) implies \(P(k+1)\) for positive \(k\).

As we have shown both the base case and the inductive case, \(P(n)\) must be true for all integers \(n>1\).

We have \(P(n) \equiv \sum\limits_{i=1}^{n} \frac{3}{4^i} = 1 - (\frac{1}{4})^n\).

The base case, \(P(1)\), that is to say \(\sum\limits_{i=1}^{1} \frac{3}{4^i} = 1 - (\frac{1}{4})^1\). We reduce this as follows:

For the inductive hypothesis, we assume \(P(k)\), that is, we assume \(\sum\limits_{i=1}^{k} \frac{3}{4^i} = 1 - (\frac{1}{4})^k\).

For the inductive case, we show that \(P(k)\) implies \(P(k+1)\) for positive \(k\).

As we have shown both the base case and the inductive case, \(P(n)\) must be true for all integers \(n>1\).