1.Compare linear search to binary search as algorithms for searching records in
ID: 3671757 • Letter: 1
Question
1.Compare linear search to binary search as algorithms for searching records in a Java program. Describe each one. When would you use each of them? What is the "bigO" complexity of each?(10points)2. Compare the bubble sort and insertion sort algorithms for sorting records in a Java program? What are the disadvantages and advantages of each? When would you use each of them ? What is the "bigO" complexity of each (10points)
3. Compare a Queue to a stack as data structures in Java. When would you use each of them? (10points)
4. What is the Object class in Java? Explain the danger in using it as the type for a linked list (10 points) 1.Compare linear search to binary search as algorithms for searching records in a Java program. Describe each one. When would you use each of them? What is the "bigO" complexity of each?(10points)
2. Compare the bubble sort and insertion sort algorithms for sorting records in a Java program? What are the disadvantages and advantages of each? When would you use each of them ? What is the "bigO" complexity of each (10points)
3. Compare a Queue to a stack as data structures in Java. When would you use each of them? (10points)
4. What is the Object class in Java? Explain the danger in using it as the type for a linked list (10 points)
2. Compare the bubble sort and insertion sort algorithms for sorting records in a Java program? What are the disadvantages and advantages of each? When would you use each of them ? What is the "bigO" complexity of each (10points)
3. Compare a Queue to a stack as data structures in Java. When would you use each of them? (10points) 2. Compare the bubble sort and insertion sort algorithms for sorting records in a Java program? What are the disadvantages and advantages of each? When would you use each of them ? What is the "bigO" complexity of each (10points)
3. Compare a Queue to a stack as data structures in Java. When would you use each of them? (10points)
4. What is the Object class in Java? Explain the danger in using it as the type for a linked list (10 points)
Explanation / Answer
1. Linear search algorithm
To search for a record out n records we compare each record from the first record onwards with the search record.If it is matched.The search process is successfully terminated.otherwise the process terminates at the end of the list.
The best case of this algorithm is when a particular record is found at the beginning of the list.
The worst case is when the record is found at the end of the list or record not found.
Binary search:
This algorithm is used to search for a record in sorted list.In every recursion the searchrecord is compared with the middle record to decide whether the record is in the first half of the list or in the second part.
Binary search ends quickly than linear search because in every iteration we discard half of the list of elements.
Linear search is used for unsorted lists where as binary search is used for sorted lists.
The time complexity of linear search grows as then value of n grows.O(n).
The time complexity of binary search is O(logn)
2.Bubble sort runs n times outerloop,at every iteration the largest element is bubbled to its correct position.
the inner loop runs for n-i-1 times i.e.it is less than previous iteration.If there are zero swaps in a particular iteration we can conclude that the list is sorted. The time complexity is O(n^2).
Insertion sort ,runs by viewing the lilst as sorted list and unsorted list.
In every iteration,the record is taken from unsorted list and inserted at its right position in the sorted list.
The time complexity for this algorithm is also O(n^2).
3.Queue is a FIFO(First in First Out)data structure, where the record inserted into the queue is removed first.
where Stack is LIFO(L:ast In first out)where the top element is popped out of the stack.
Stacks are used in various computer science applications
1.when implementing recursion we use stack to place the recursive call data on top of the stack.
2.Evaluation of postfix expression
3.To convert arithmetic expression in infix form to postfix form.
4.Stacks are used in pushdown automata for parsing expressions or statements.
Queues are used in various operating applications.
1. Memory management techniques to remove a file based on FIFO order
2.In processor scheduling like FIFO technique.
3. In priority queue scheduling also priority queues are used.
4. OBJECT class in java
It is the parent class of all the classes in java. Object class is used to refer objects of a type which is not known.
Every time the object is casted to its origianal type to call the methods of the subclass.
There is a risk of ClassCastException when converting an Object type object to a specific type.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.