Question

Interfaces

1. What is inside an interface definition? What does a class do to an interface and what keyword is involved? How does a class do this to an interface (what should we find in the class)? Can an interface have a generic parameter? How do you instantiate an interface as an object? What methods can’t you use on an interface type?

Abstract Data Types
2. What does an ADT define? Does an ADT specify programming language and/or data structures to be used? What 2 data structures could did we learn we could use to implement a list ADT?

Searching and Big O
3. Explain in English how one does a binary search? If I was to Binary search an array for a particular number what must be true about the array before I start the binary search? What is the Big O of binary search? How does this differ from the Big O of a linear search? If I have a sorted array, in ascending order, and I want to search for the 5th biggest element in it, what is the Big O of this algorithm? If I have a sorted linked list, in ascending order, and I want to find the 5th biggest element in it, what is the big O of this algorithm? If I have a 2 Dimensional Array of size N by N unsorted, what is the Big O of finding a particular value in this 2 dimensional Array? What about a 3 dimensional Array of size N by N by N unsorted?

Recursion
4. How can we tell if a function is recursive? What must every recursive function have to ensure no infinite recursion? Write the recursive function to do factorial.

Sorting
5. What is the algorithm for bubble sort? What is the algorithm for Bucket Sort with arrays? What is the algorithm for Selection sort? What is the Big O of bubble and selection sort? What is the algorithm for shell sort and what is the optimization for shell sort and what is the Big O of shell sort with this optimization step? What is the recursive algorithm for merge sort? What are the 2 parts to MergeSort and Where does the recursive step occur? In the merging step, are the two arrays being merged already in sorted order (i.e. if we are merging array A and array B, is array A already sorted and is Array B already sorted?). What is the Big O of merge sort

Generics
6. Why are Generics important in Java, specifically, what do they allow us to do? What can you pass in for a Generic? What 2 functions have we learned that are guaranteed to be callable on a Generic type? How do we create an array of a Generic type?

List ADT, Array Implementation, and Linked Lists
7. What functionality is outlined in the List ADT. Implementing a List as a partially filled array in java, what will be your private variables? What two things does a Node have inside of it? What is a private inner class and why is node a private inner class in Linked List? What are the restrictions of creating an object of a private inner class (can a node object be created in main? If not where can it be created?). What is the beginning of the linked list called? What is the end of the linked list called? How can you tell if a node is the last node in a linked list? How can you find the first node in a linked list? What does an empty list look like? How do you traverse a linked list to (for example) print out all the contents of the linked list? What kind of loop do you use? What special cases must you check for when looping through a linked list?

Answer 1

Q1 /Answer

Interface: an interface is a java concept which is used to implement abstraction. in an interface by deafault all methods are abstract. We camn not create an object of an interface. interface are always implemented in a java class.

Yes interface can be of generic type. Example of such interfaces are Comparable, Comparator

static methods are not allowed in interfaces.

an interface can contain public static final variables and abstract methods.

syntex

interface A

{

//abstract methods

}

class B implements A

{

//override unimplemented methods of A

}

Question 2 What does an ADT define? Does an ADT specify programming language and/or data structures to be used? What 2 data structures could did we learn we could use to implement a list ADT?

ADT: long form of ADT is Abstract Data Type . Here ADT means a concept which can be implemented in many ways. a data type which can be applicable on certain situation. the example of ADT are Arrays, Stack, Queue, LinkeList. yes an ADT specify data structure to be used like Stack is an ADT and also is a data structure. To implement a list ADT you can use Array and Link List datastructure.

Answer 3

A binary search or half-interval search algorithm finds the position of a specified value within a sorted array. In each step, the algorithm Compares the input key value with the key value of the middle element of the array. If the keys match, then a matching element has been found so its index, or position, is returned.

Algorithm

Binary Search ( int A[N] ):

Description: Here A is a sorted array having N elements. ITEM is the value to be searched. BEG denotes first element and END denotes last element in the array. MID denotes the middle value.

1.Set BEG = 1 and END = N

2.Set MID = (BEG + END) / 2

3.Repeat While (BEG <= END)and (A[MID]≠ITEM)

4. If (ITEM < A[MID]) Then
5. Set END = MID –1
6. Else
7. Set BEG = MID + 1

[End of If]

8. Set MID = (BEG + END) / 2 [End of While Loop]
9. If (A[MID] == ITEM) Then
10. Print: ITEM exists at location MID
11. Else
12. Print: ITEM doesn‘t exist

[End of If]

13.Exit

The time complexity of binary search is O(log n)

using linked list time to find any element is O(1) in constant time.

4. How can we tell if a function is recursive? What must every recursive function have to ensure no infinite recursion? Write the recursive function to do factorial.

Answer

Recursive Function:

A function is said to be recursive if it calls itself.

every recursive function has some iteration . In each iteration it makes call to itself and there is always a termination condition to prevent infinite recursion.

consider following program of factorial using recursive function:

public class Factorial {

public static void main(String[] args)
{
Scanner sc= new Scanner(System.in);
System.out.print("enter the number);
num=sc.nextInt();
long factorial = fact(num);
System.out.println("Factorial of " + num + " = " + factorial);
}
public static long fact(int num)
{
if (num >= 1)
return num * fact(num - 1);
else
return 1;
}
}
Answer 5

1. Bubble Sort:

Bubble sort is a simple sorting algorithm. It works by repeatedly stepping through the list to be sorted, comparing two items at a time and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted. The algorithm gets its name from the way smaller elements "bubble" to the top of the list. Because it only uses comparisons to operate on elements, it is also known as comparison sort.

Algorithm: Bubble Sort( int A[ ] ):

Description: Here A is a n unsorted array having N elements.

1.Repeat For J = 1 to N

2. Repeat For K = 1 to N-J
3. If (A[K] > A[K+1])Then
4. Interchange A[K] and A[K+1] [End of If]

[End of Step 2 For Loop]

[End of Step 1 For Loop]

5.Exit

Selection sort Algorithm:

Selection Sort ( int A[] ):

Description: Here A is a n unsorted array having N elements. 1.Repeat For J = 1 to N

2. Set MIN = J

3. Repeat For K = J+1 to N
4. If (A[K] < A[MIN]) Then
5. Set MIN = K

[End of If]

[End of Step 3 For Loop]

6.        Interchange A[J] and A[MIN]

[End of Step 1For Loop] 7.Exit

Time complexity of merge sort is O(nlogn ) in all cases