Suppose you have a class to represent a list

Given a file of n data items in sorted order, where n = 1030. Suppose you wanted to use Binary
Search to find the value 762 in this file, using Binary Search. Unknown to you, the value is not
even in the file. Precisely, how many comparisons you would need to make in order to find this
out. Explain your answer in terms of the way in which Binary Search works. Be specific about the
asymptotic cost of Binary Search.
Answer: In Binary Search , always the search space will be reduced to half the orginal size. Thus the
maximum number of comparisons will be log2(n).
Here n = 1030.
Thus , max comparisons = ceil(log2(1030)) = ceil(10.0084) = 11
1.

2.

Suppose you have a class to represent a list. See prototype below. When you study the
implementation of the class you remember that you implemented it as a doubly linked list.
Write DeleteAfter. Be sure to handle all error situations.
public class ListClass {
public ListClass(void) { List = 0 }; //constructor – initializes list to be empty
public InsertAfter(itemtype item, int index); //validates index, inserts item at any position in list
public itemtype DeleteAfter(int index); //validates index, deletes item at position index in a list,
returns item – handles any deletion
… //other useful functions of class omitted
private boolean VerifyIndex (int index); //validates that index is position within list
private ListNode PtrTo ( int index );
//returns a
reference to the node at position index
private ListNode List; //nodeptr
private int Length;
}
//elsewhere you define
private class ListNode {
itemtype data;
ListNode Right, Left;
}

3.

There are lots of ways to implement a list. Please make a table that shows the following(The
attachment is a word doc containing this chart in case you find it useful):
Plain Array
Linked (dynamic allocation)
Ave cost to insert
Ave cost to delete
Max cost to insert
Max cost to delete
Ave cost to search
Max cost to search
Major advantage
Major disadvantage

4.

Array (garbage collection style)

Linked (Hybrid in Array)

Write a function to insert A the value S as the right child of value R in a linked implementation of a
right in-threaded binary tree. You may assume you have a reference to R called Here. You may
not treat the existence of a right child of R an an error situation. This should be a complete
standalone routine that does not call anything else.
— Font family –Andale MonoArialArial BlackBook AntiquaComic Sans MSCourier
NewGeorgiaHelveticaImpactSymbolTahomaTerminalTimes New RomanTrebuchet
MSVerdanaWebdingsWingdings
— Font size –1 (8pt)2 (10pt)3 (12pt)4 (14pt)5 (18pt)6 (24pt)7 (36pt)

5.

Given a file of data in random order, where the size of the file is n = 2k. Suppose you want to find
the largest item in the file. How would you go about finding it? What is the cost (think O(f(n))) of
your solution? Justify your answer. Solutions that are more efficient are worth more points.

Bubble sort…
6.

In specifying the ADT, it is important for the name to reflect the implementation

True or false – true
7.

Suppose you have to store employee records for your employer, the largest company in the state
of Maryland. The primary key is the Social Security number. You need to primarily access
individual records, but occasionally expect to need to print out the file for an employee directory.
Your coworker wants to hash the records by using division on the primary key – stripping off the
first five digits as the address, with linear probing to resolve collisions. Tell your coworker three
reasons all in support of his idea OR all against his idea.

8.

Regarding ADT’s…
A. An ADT promotes data encapsulation and an ADT tells the user what methods are available to
manipulate the data and it is important to select your implementation prior to developing the ADT
to make sure don’t overlook details.
B. An ADT tells the user what methods are available to manipulate the data and it is important to
select your implementation prior to developing the ADT to make sure don’t overlook details. .
C. An ADT promotes data encapsulation.
D. An ADT tells the user what methods are available to manipulate the data.
E. An ADT promotes data encapsulation and it is important to select your implementation prior to
developing the ADT to make sure don’t overlook details.
F. An ADT promotes data encapsulation. and an ADT tells the user what methods are available to
manipulate the data.
G. It is important to select your implementation prior to developing the ADT to make sure don’t
overlook details.

9.

Write a function called EvalPrefix that accepts a validated prefix expression, composed only of
operators and single digit integer values, and recursively evaluates the expression, returning an
integer result. Your solution should not use a stack. The class, in which this is to be included, also
contains the following private functions. You may use them if you wish.
private int Oper (char Symb, int Op1, int Op2 ); //Oper returns the result of applying the operator
in Symb to the
//operands in Op1 and Op2
private char GetSymb ( string data); //Extracts an operator symbol from data
private int GetValue ( string data); //Extracts an operand value from data.

10. Write a recursive function called Palindrome that will ascertain if a string P contains a
palindrome, i.e. a string that reads the same forward or backwards. Example: ‘Madam I’m Adam’.
You may assume the contents of the string are characters. Punctuation is typically ignored in a
palindrome. No stacks or queues are allowed. No counting is allowed. Do any necessary error
checking. The original string P should be left unchanged.
public static boolean isPal(String s)
{ // if length is 0 or 1 then String is palindrome
if(s.length() == 0 || s.length() == 1)
return true;
if(s.charAt(0) == s.charAt(s.length()-1))
/* check for first and last char of String:
* if they are same then do the same thing for a substring

* with first and last char removed. and carry on this
* until you string completes or condition fails
* Function calling itself: Recursion
*/
return isPal(s.substring(1, s.length()-1));

}

/* If program control reaches to this statement it means
* the String is not palindrome hence return false.
*/
return false;

11. Suppose you have declared array A to be used for the hybrid implementation of several lists and
stacks. The last item of List 4 is in location 37. You check location 38 and since it turns out to be
in use, what do you do?. Comment on the validity of your strategy for handling insertions.

12. Characterize a situation in which you would choose a bubble sort over a natural merge. Be
specific.
13. Which of the following are true statements about Binary search trees?
A.You can determine if a desired item is present or not in an average of O(log n) time.
B.They are a reasonable choice when you wish to access the data in sorted order, in addition to
having quick access for individual items.
C.A deleted item is, in general, replaced by it’s pre-order successor.
D.A, B, and D.
E.The smallest item in the tree is at the root.
F.A and C.
G.All of the above.
14. Suppose you have a file of data of approximately 10,000 personnel records (FYI, 213 = 8192 and
214 = 16384) using Social Security numbers as primary key. You expect to mostly access
individual records so you want that to be fast, but you expect to also access the entire file in
sorted order reasonably often. You have decided to use an indexed sequential file structure or an
order 5 B-Tree. Give 3 reasons why an Indexed sequential search structure is better. Then give
three reasons that an order 5 B-tree is better. What additional information do you need to choose
between them?

15. Convert the following in order expression to post order, using a stack. You must show your work.
The $ denotes exponentiation. (a+b)*c – (a-b)*c/2 + x$3$2
16. Address Calculation Sort (Bucket Sort) uses a simple numerical calculation on the key of a record
(like hashing) to determine in which bucket the record belongs. This calculation averages O(1). It
then uses a simple insertion sort to order the record correctly within the bucket.
(a) What is the complexity of Address Calculation Sort. Please support your answer – a proof is
not required.
(b) Will Address Calculation Sort exploit ordering in the data (reverse order, in order, or both)?
Why or why not.
(c) Supposing the data is clustered, non-uniform, in its distribution. How does this affect the
complexity of the sort. Support your answer.

17. Perform a Radix Sort on the following list of numbers. Show only the first pass. How many passes
are required? 92817 42386 22204 89551 32867 11726

18. Suppose you wished to use an array to solve a coding problem but the language you are
constrained to use (we will call it C–) does not support arrays. In other respects, C– is very
similar to C++ and Java. Upon learning something about the syntax of the language, you discover
that it does support stacks directly, i.e. you can declare something to be of type stack without
defining a stack. Also, push, pop and empty operations are supported as part of the language.
You decide to write an array class using a stack as a home for the array.
stack S; //Given this declaration
itemtype S.pop(); //These are available operations
void S.push(itemtype X);
void S.empty();
public interface Stack {
public int size(); //Returns number of elements in stack
public boolean isEmpty(); //Returns true if stack empty, else false
public Object peek() //Returns value at top of stack – stack unaltered
throws StackEmptyException;
public void push(Object element); //Inserts new item at top of stack
public Object pop() //Removes and returns item at top of stack
throws StackEmptyException;
}
where
public class StackImp implements Stack {…omitted…}
You may assume that Object and StackEmptyException are properly defined. There are no
intentional syntax errors.
Specify the interface for the Array and write the insertion and deletion methods.
19. What is the standard way to implement a queue in an array? Why do we do it this way? Be
specific. Give the O(g(n)) of the insert and delete methods.
20. In evaluating a postfix expression, if the symbol just read is a $ then the next action is:
A.Pop the stack.
B.Push $ onto the stack.
C.Write $ to output string.
D.Read another symbol from input string.

Our website has a team of professional writers who can help you write any of your homework. They will write your papers from scratch. We also have a team of editors just to make sure all papers are of HIGH QUALITY & PLAGIARISM FREE. To make an Order you only need to click Ask A Question and we will direct you to our Order Page at WriteDemy. Then fill Our Order Form with all your assignment instructions. Select your deadline and pay for your paper. You will get it few hours before your set deadline.