Final Examination

Com 1201 – Fall 2002 – Jeff Raab

Name ________________________________________ ID# _________________________

Introduction

This is a closed book, closed notes examination. Please read all of the instructions for each problem before you provide your solution. If you have any questions regarding a particular problem, please raise your hand and the test proctor will help you understand the requirements for the problem. You have one class period to complete the problems on this examination.

The signatures of the methods specified by each of the ADTs are listed on the last page of this examination, for your reference. You may tear that sheet off of the exam if you like.

Grading

Section	Points	Score
1	10
2	30
3	20
4	20
5	20
Total	100
Letter grade

Section 1 – Java programming

(10) 1. Consider a type of array named a Power-2-Array. An array of int values, a, is defined to be a Power-2-Array if the sum of its contents is equal to 2^a.length.

Write a public method below named power2Array that takes an array of int values named a and has a return type of boolean. Your method must return true if the given array is a Power-2-Array by the above definition, or false in every other case. Your code must be complete, correct, documented, and as efficient as possible.

Analyze your method by listing its actual number of steps in the worst case, and by using Big-Oh notation to generalize the number of steps in the worst case.

The actual number of steps in the worst case is _________________________ .

Using Big-Oh notation, this generalizes to _________________________ .

Section 2 – Implementing an ADT

(30) Write an implementation of the Queue ADT, in Java, that uses an array of Objects to hold the contents of the queue. Your implementation must never fail to enqueue an Object due to insufficient space in the array of contents. Your implementation does not have to reduce the length of the array at any time, though it is acceptable for it to do so if you choose.

Your implementation must be complete, correct, documented, and as efficient as possible given the constraints of the problem. Include in your documentation for each method an analysis of the worst case running time of the method, using Big-Oh notation. The details of the Queue ADT are included on the final page of the examination.

Use the remainder of this page and the next page to provide your answer.

(this page intentionally left mostly blank)

Section 3 – Short answer questions

(10) 1. Is it possible to implement the Stack ADT using one or more implementations of the Queue ADT? In other words, is it possible to implement the Stack ADT by using only one or more queues to hold the contents of the stack? You may use only the Queue ADT methods of the queues to implement the methods specified in the Stack ADT. You may assume that a Queue ADT implementation exists that is complete and correct.

Write your answer below. If yes, describe in reasonable detail how such a Stack ADT implementation would be implemented, including at least a short explanation for each method in the ADT. If no, describe in reasonable detail why one or more Queue ADT implementations are insufficient to implement the Stack ADT.

(10) 2. Describe in reasonable detail a way to implement the Dictionary ADT such that the insertItem, findElement, and removeElement methods would all run in O(1) time, assuming that all of the keys associated with elements in the structure are integers in the range [25, 75]. You do not have to ensure that the remaining Dictionary ADT methods would have any particular running times, and you do not have to describe how those remaining methods would be implemented.

Describe how much memory would be used by such a structure, both specifically and in Big-Oh notation. For example, if you were to describe an unsorted sequence implementation of the Dictionary ADT, you would state that your structure would use 1 sequence of size n, which is O(n).

Section 4 – Diagrammatic questions

(5) 1. List the order in which the contents of the following tree would be visited, for each of the given traversals:

Traversal	Visit order
Preorder
Postorder
Inorder

(5) 2. List the order in which the given keys would be contained in a Priority Queue ADT implemented using a sorted sequence, where keys are ordered in nondecreasing order of their priority value. You should ignore the elements associated with the given keys as they could be any objects, and they do not affect the resulting order.

For this problem the priority value of a key is defined as its minimum absolute value difference from the various powers of 2. For example, the priority value of the key 12 is 4, as it is 4 away from both 8, 2³, and 16, 2⁴. The priority value of the key 66 is 2, as it is 2 away from 64, 2⁶. A table of the powers of 2 is below, for your reference:

k	0	1	2	3	4	5	6	7	8	9	10
2^k	1	2	4	8	16	32	64	128	256	512	1024

Fill in the sequence diagram below with your answer, given the following list of keys in random order:

Keys

94

28

43

256

71

48

462

11

0

84

54

Sorted sequence priority queue
	0	1	2	3	4	5	6	7	8	9	10
size = 11

(5) 3. Draw the heap that results from removing a minimum key from the heap shown below. Circle each node on the given heap diagram that was removed or had its key swapped in this process. You should ignore the elements associated with the given keys as they could be any objects and do not affect the resulting order.

(5) 4. List the contents of the array for an open addressing hashtable using the linear probing style of collision handling, after performing the given Dictionary ADT operations in order. Use the following hash function:

h(k) = | 2k + 5 | mod 11

You should ignore the elements associated with the given keys as they could be any objects and do not affect the resulting order. Place an X in the array to indicate an empty location that used to contain a key. Use the following array diagram for scratch work:

	0	1	2	3	4	5	6	7	8	9	10
length = 11

Fill in the following array diagram with your final answer, for these given operations:

Operations

insertItem(2)

insertItem(14)

insertItem(2)

removeAllElements(2)

removeElement(0)

insertItem(13)

	0	1	2	3	4	5	6	7	8	9	10
length = 11

Section 5 – Data structures

For each situation below, list the ADT you would choose for the specified task, and the implementation of that ADT that would provide the most efficient running time for each of the operations listed in the problem. Please use asymptotic analysis for the running time, and use Big‑Oh and Big‑Theta as appropriate.

(10) 1. You are employed by a software company designing an application for use by produce wholesalers. Your job is to implement the data structure used to store the inventory of the warehouse containing the produce. The data structure must be able to add a product with an associated code indicating its likelihood to spoil, remove a product that is most likely to spoil (to ship it from the warehouse), and return the overall number of products in the inventory. No other functionality is needed.

Your choice of ADT would be: _________________________________

Your choice of implementation would be: _________________________________

Operation	Method in ADT used to implement	Running time
Add a product and its code
Remove a product likely to spoil
Return the number of products

(10) 2. You are employed by a software company designing an application for use by taxicab dispatchers. Your job is to implement the data structure used to associate customers with taxicabs. The data structure must be able to associate a customer’s address with a taxicab’s number, find the address associated with a taxicab’s number, and remove the association between an address and a taxicab number (when the customer has been delivered to its destination. No other functionality is needed.

Your choice of ADT would be: _________________________________

Your choice of implementation would be: _________________________________

Operation	Method in ADT used to implement	Running time
Associate address with taxicab
Find address associated with taxi
Remove address and taxicab association

Stack ADT

void push(Object)

Object pop()

Object top()

int size()

boolean isEmpty()

Queue ADT

void enqueue(Object)

Object dequeue()

Object front()

int size()

boolean isEmpty()

Vector ADT

void insertAtRank(int, Object)

Object removeAtRank(Object)

Object elementAtRank(int)

Object replaceAtRank(int, Object)

int size()

boolean isEmpty()

List ADT

Position insertFirst(Object)

Position insertLast(Object)

Position insertBefore(Position, Object)

Position insertAfter(Position, Object)

Object remove(Position)

Position first()

Position last()

boolean isFirst(Position)

boolean isLast(Position)

Object replaceElement(Position, Object)

void swapElements(Position, Position)

int size()

boolean isEmpty()

Sequence ADT

(Vector ADT + List ADT +)

Position atRank(int)

int rankOf(Position)

Priority Queue ADT

void insertItem(Comparable, Object)

Object removeMin()

Comparable minKey()

Comparable minElement()

int size()

boolean isEmpty()

Dictionary ADT

void insertItem(Object, Object)

Object removeElement(Object)

Object[] removeAllElements(Object)

Object findElement(Object)

Object[] findAllElements(Object)

Object [] keys()

Object[] elements()

int size()

boolean isEmpty()