1. 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
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 Array (garbage collection style) Linked (Hybrid in 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. 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 MonoArialArialBlackBookAntiquaComic Sans MSCourierNewGeorgiaHelveticaImpactSymbolTahomaTerminalTimes New RomanTrebuchetMSVerdanaWebdingsWingdings
-- 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.
publicstaticbooleanisPal(String s)
{ // if length is 0 or 1 then String is palindrome
if(s.length() == 0 || s.length() == 1)
returntrue;
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
*/
returnisPal(s.substring(1, s.length()-1));
/* If program control reaches to this statement it means
* the String is not palindrome hence return false.
*/
returnfalse;
}
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.