2 - Abstract Data Types, Dynamic Arrays, Amortized Analysis

Question 1

What is abstraction? Give three examples of abstraction from real life.

Answer 1

Abstraction is the process of trying to identify the most important qualities of an object or model. (e.g. table of contents, menu, class schedule)

Question 2

What is information hiding? How is it related to abstraction?

Answer 2

Information hiding is purposely not including some information as a way of controlling complexity.

Question 3

How is encapsulation related to abstraction? Explain how a function can be viewed as a type of encapsulation. What information is being hidden or abstracted away?

Answer 3

Encapsulation is placing items into a unit, or capsule. The outside is the task being performed, and the inside is how that task is performed.

Question 4

What makes an ADT description abstract? How is it different from a function signature or an interface?

Answer 4

The description just provides a metaphor for how it behaves.

An interface, on the other hand, lists out exactly the functions that a file may have.

Question 5

Come up with another example from everyday life that illustrates the behavior of each of the six classic abstractions (bag, stack, queue, deque, priority queue, map).

Answer 5

Bag: Adding a value, asking if a value is there, and removing a value. (like box of candy)

Set: In addition to bag operations, no element may appear more than once. (like a VIP party)

Stack: LIFO, remembers the order (like an ordered bus).

Queue: FIFO, remembers the order (like a line)

Deque: Insert/remove from either end, but not the middle (like a bus with two doors).

Priority queue: maintains value in order of importance. (like triage)

Map: maintains pairs of elements (each unique key is matched to a corresponding value).

Question 6

What collection is important, and why? Is order important? Is time of insertion important?

1. names of students enrollled
2. files being held until can be printed on printer
3. URLs for recently visited web pages in browser
4. names of patients waiting for operating room in ER
5. names and associated employee records in company database

Answer 6

1. Set - don’t care about order, but can only enroll once
2. Queue - first in, first out
3. Stack - want the most recent to be on top
4. Priority queue - make sure the most urgent is taken care of first
5. Map - must have unique key corresponding to that employee

Question 7

In what ways is a set similar to a bag? In what ways are they different?

Answer 7

Both are simply unordered lists that allow you to see whether something is there.

They are different in that a bag can contain the SAME thing, while a set must contain unique things.

Question 8

In what ways is a priority queue similar to a queue? In what ways are they different?

Answer 8

Both place some priority on time as a negative factor.

However, for a queue, relative time is the only factor. For a priority queue, there may be other factors.

Question 9

What is a dynamic array?

Answer 9

A dynamic array is one that automatically resizes as elements are added on to ensure that the array does not overflow.

Question 10

What does the term capacity refer to in a dynamic array? What does the term size refer to?

Answer 10

The capacity is how much memory is currently allocated, but the size is how much of that memory is actually storing information.

Question 11

Can you describe the set of legitimate subscript positions in a dynamic array? Is this different from the set of legal positions in an ordinary array?

Answer 11

In a dynamic array, the legitimate subscript positions are only ones that are within the size or one after the array.

In a normal array, you can’t just add onto the end of the array.

Question 12

How does the add function in a dynamic array respond if the user enters more values than the current capacity of the array?

Answer 12

The add function doubles the size of the array.

Question 13

Suppose the user enters 17 numbers into a dynamic array that was initialized with a capacity of 5? What will be the final length of the data array? How many times will it have been expanded?

Answer 13

Once you add onto a 5-sized array, it’ll double into a 10. Once you add onto a 10-sized array, it’ll double into a 20-sized array.

Question 14

What is the algorithmic execution time for the _dyArrayDoubleCapcity, if n represents the size of the final data array?

Answer 14

First, a new array is created (1). Next, the old values are copied into the new array (n/2). Next, the free statement releases old memory (1). Finally, the pointer is changed to reference the array. (1).

Overall, it’s just n.

Question 15

Based on your answer to the previous question, what is the worst case algorithmic complexity of the function dyArrayAdd?

Answer 15

Since there’s only one for loop, the copying of the array, it would be O(n).

Question 16

What are the defining characteristics of the stack abstraction?

Answer 16

1. Push(new Entry) - places new element on the top
2. Pop () - removes the topmost item
3. Top() - returns, but does not remove, the topmost item
4. isEmpty() - determines whether the stack is empty

Question 17

Explain the meaning of the term LIFO. Explain why FILO might have been equally appropriate.

Answer 17

LIFO means last in, first out. This just refers to the top of stack being the last “in”, but the first to leave.

It’s the same as FILO, or first in, last out, which refers to the bottom of the stack instead.

Question 18

Give some examples of stacks found in real life.

Answer 18

Back and forward buttons in a web browser, buffered character input (backspace).

Question 19

Explain how the use of an activation record stack simplifies the allocation of memory for program variables. Explain how an activation record stack makes it possible to perform memory allocation for recursive problems.

Answer 19

For example, if you have a recursive function, you need an activation record every time the function p is created so you know what is being passed and when finally it pops back, so that you can recover each space.

Question 20

Explain the following postfix polish expression:

a. 2 3 + 5 9 - *
b. 2 3 5 9 + - *

Answer 20

a. (2+3) pushed back onto stack, then (5-9) pushed onto stack, so * pops both off and 5 * -4 = -20.
b. (5+9)=14 pushed back onto stack, then (3-14) = -11 pushed back onto stack, then 2*-11 = -22.

Question 21

How is the memory representation of a linked list different from that of a Dynamic Array?

Answer 21

The dynamic array uses a large block of memory (much less common, but much more work to be performed).

The linked list allocates a new link EVERY time, but it’s only a single element.

Question 22

What information is stored in a link?

Answer 22

Each link points to the next node, which contains a data value and a link to the following node.

Question 23

How do you access the first element in a linked list? How would you get to the second element?

Answer 23

The first element in a linked list is just the head of the list. You would following the link in the head to get to the second element in the list.

Question 24

In the last link, what value is stored in the next field?

Answer 24

Nothing - it’s a null pointer.

Question 25

What is the Big-Oh complexity of pushing a value on the front of a linked list stack? Of popping?

Answer 25

It would just be O(1), since you just need to point the new head's pointer to the old head's address. Popping would also be O(1), since you just need to increment the head pointer to the next and free the previously first node.

Question 26

What would eventually happen if the pop function did not free the first link in the list?

Answer 26

There would be a memory leak.

Question 27

Suppose you wanted to test your linked list class. What would be some boundary value test cases? Develop a test harness program and execute your code with these test cases.

Answer 27

You should add 5 nodes, then try to delete the head node and the back node?

Question 28

What features characterize the Bag data type?

Answer 28

1. Add(newElement) - place value into the bag 2. Remove(element) - remove the value 3. Contains(element) - return true if element is in collection 4. Size() - return number of values in collection 5. Iterator() - returns an iterator used to loop over collection

Question 29

How is a set different from a bag?

Answer 29

Two important differences between set and bag: 1. elements in a set MUST be unique (cannot add if already there). 2. set adds a number of operations that combine two sets (set union, intersection, set difference, subset of the other). Some implementations allow elements to be repeated (called a multiset).

Question 30

When a dynamic array is used as a bag, how is the add operation different from operations you have already implemented in the dynamic array stack?

Answer 30

In a dynamic array, the add operation has the potential to need expansion of the top of the stack.

Question 31

Using a dynamic array as the implementation technique, what is the Big-O algorithmic execution time for each of the bag operations? Is this different if you use a linked list as the implementation technique?

Answer 31

For a dynamic array, the time complexity is O(1) for all operations, although the add operation is O(1) on average (b/c you'll be doubling log n times, copying O(n) overall). If a linked list is used, then the only major difference is returning the size, which would require traversing the entire linked list.