CS141 Theory Assignment 2

Question One

A. Differentiate between linear search and binary search.

B. If the list is already in sorted order, how can you utilize this information in improving the linear search technique? Show your improvement in the algorithm of linear search.

Question Two

A. For the following code of linear search using iteration, convert it into an equivalent code using recursion.

int findLinear(Comparable[] elements, Comparable key)
{
for (int i=0; iif (elements[i].compareTo(key) == 0)
return i;
return -1;
}

B. For the following code of binary search using iteration, convert it into an equivalent code using recursion.

int findBinary(Comparable[] elements, Comparable key, int length)
{
int upper = length-1;
int lower = 0;
while (upper >= lower)
{
int index = (upper+lower)/2;
int compared = elements[index].compareTo(key);
if (compared == 0)
return index;
else if (compared == -1)
lower = index+1;
else
upper = index-1;
}
return -1;
}

Question Three

a) Translate the following UML class diagram into Java. To understand the problem, please refer to the description given after the diagram. see image.

Student Class:

• Attributes:
  • StudentId: unique id of the Student.
  • FirstName: the first name of the Student.
  • LastName: the last name of the Student.
  • Age: The age of the Student.
• Methods:
  • Student( id: int, Fname: String, Lname: String, age: int): constructor
  • displayStudentInfo(): this method displays all the attributes of the Student.

b) Using java.util.LinkedList class, write a java program that will display following Menu to execute different member functions of Students LinkedList.

To add a new student in Linked List, Enter 1.
To get the number of students of a given age, Enter 2.
To get and display all students of a given age, Enter 3.
To remove a student by ID from the Linked List, Enter 4
To Exit, Enter 0.
Enter Your Option: ____

Question Four

A) Define Stake and Queue in Java. What are their main differences?

B) Consider the following code:

import java.util.Stack;
import java.util.Queue;
import java.util.LinkedList;
public class StackBasicExample
{
public static void main(String[] args)
{
Stack stack = new Stack<>();
stack.push("ali");
stack.push("mohammed");
stack.push("alqahtani");
String h = stack.peek();
String t = stack.pop();
System.out.println(stack);
Queue queue = new LinkedList<>();
queue.add("Khalid");
queue.add("Ali");
queue.add("Khalid");
String r = queue.remove();
System.out.println(queue);
}
}

What does each of the following methods do?

1) stack.push("ali");
2) String h = stack.peek();
3) String t = stack.pop();
4) queue.add("Khalid");
5) String r = queue.remove();