Final Examination

Com 1201 – Winter 2003 – 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	25
2	20
3	25
4	30
Total	100
Letter grade

Section 1 – Java programming

(5) 1. Write a public method below named search that takes an array of int values named a, an int value named v, and has a return type of boolean. Your method must return true if the given array contains the given value, or false in every other case. Your method must be correct and completely documented to the specification of the model code for a function as posted on the course website. Write your function and its documentation in the space below.

Analyze your method by using Big-Oh notation to generalize the number of steps in the worst case.

Using Big-Oh notation, the number of steps is _________________________ .

Section 1 – Java programming

(10) 2. Write a public method below named searchSorted that takes a sorted array of int values named aSorted, an int value named v, and has a return type of boolean. Your method must return true if the given array contains the given value, or false in every other case. Your method must be correct and completely documented to the specification of the model code for a function as posted on the course website. Write your function and its documentation in the space below.

Analyze your method by using Big-Oh notation to generalize the number of steps in the worst case.

Using Big-Oh notation, the number of steps is _________________________ .

Section 1 – Java programming

(10) 3. Write a public method below named searchSortedList that takes the head Node of a sorted list of int values named n, an int value named v, and has a return type of boolean. Your method must return true if the given list contains the given value, or false in every other case. Your method must be correct and completely documented to the specification of the model code for a function as posted on the course website. Write your function and its documentation in the space below.

You may assume that the Node class has three data members: element of type int, previous of type Node, and next of type Node. The given node n will contain the first int in the list and is not a sentinel node. Assume there is no sentinel node at the end of the list, and that the last node in the list has its next reference set to null.

Analyze your method by using Big-Oh notation to generalize the number of steps in the worst case.

Using Big-Oh notation, the number of steps is _________________________ .

Section 2 – Short answer questions

(10) 1. Is it possible to use an implementation of the Dictionary ADT to implement the Queue ADT? The design for such a class would be as follows:

/** Dictionary implementation of the Queue ADT. */

public class DictionaryQueue implements QueueADT {

/** Dictionary used to hold the elements. */

protected DictionaryADT d;

. . .

}

The . . . shows where the rest of the class definition would go.

If it is possible to implement the Queue ADT using methods of the Dictionary ADT, describe in reasonable detail how the enqueue, dequeue, and front methods would be implemented. You don’t have to write the code, just explain how it would work.

If it is not possible, explain why it is so.

(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 [10, 25). 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, using Big-Oh notation. For example, if you described 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 3 – 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

(10) 2. Show the heap that results from inserting items with the following keys into a heap implementation of the Priority Queue ADT. The keys must be inserted in order from left to right. Assume that priority is defined by standard English dictionary (lexicographical) order where words that begin with the letter A are higher priority than those starting with the letter B, and so on. You do not have to show the elements, just the keys.

Keys

CHILD

APPLE

TROT

APPLY

ZONK

POISED

(5) 3. Draw the heap that results from removing a minimum key from the heap shown below. On the given heap diagram, use arrows to show which nodes had their keys swapped during the process of reestablishing the heap condition. As in the given diagram, you do not have to show the elements associated with the keys.

(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(3)

insertItem(14)

insertItem(3)

removeElement(0)

removeElement(3)

insertItem(6)

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

Section 4 – 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()

Object minElement()

int size()

boolean isEmpty()

Dictionary ADT

constant: NOT_FOUND

void insertItem(Object, Object)

Object removeElement(Object)

Object[] removeAllElements(Object)

Object findElement(Object)

Object[] findAllElements(Object)

Object[] keys()

Object[] elements()

int size()

boolean isEmpty()