Course Instructor: Anosha Khan Course TA: Talha Azhar

Question 1:
Objective:
Understand and implement the Binary Search Algorithm to find an element in a sorted array.

What is Binary Search?

Binary Search is an efficient searching algorithm that works only on sorted arrays.
It repeatedly divides the search range in half to quickly find the target element.

Algorithm Steps:
• Start with two variables
• low = 0 (first index)
• high = n - 1 (last index)
• Find the middle index:
• mid = (low + high) / 2
• Compare the middle element with the target value:
• If arr[mid] == target, the element is found.
• If arr[mid] < target, search in the right half (low = mid + 1).
• If arr[mid] > target, search in the left half (high = mid - 1).
• Repeat steps 2–3 until low > high.

If this happens, it means the element is not found in the array.

Your Task:
Write a C++ program that:

• Takes the number of elements as input.

• Takes sorted elements (in ascending order).
• Takes the target value to search for.
• Applies binary search to find the target.
• Displays the index if found; otherwise, prints “Element not found.”

Example :
Enter number of elements: 7
Enter elements (sorted): 2 5 8 12 16 23 38
Enter value to search: 16
Element found at index 4

Enter value to search: 7

Element not found
Question 2:
Write a program that simulates a lottery. The program should have an array of five integers named
lottery and should generate a random number in the range of 0 through 9 for each element in the
array. The user should enter five digits, which should be stored in an integer array named user.
The program is to compare the corresponding elements in the two arrays and keep a count of the
digits that match. For example, the following shows the lottery array and the user array with
sample numbers stored in each. There are two matching digits (elements 2 and 4).

Lottery array: user array:

7 4 9 1 3 4 2 9 7 3

The program should display the random numbers stored in the lottery array and the number of
matching digits. If all of the digits match, display a message proclaiming the user as a grand prize
winner.

Question 3:
Write a program that uses the following arrays:
• empId: an array of seven long integers to hold employee identification numbers.
• The array should be initialized with the following numbers:
5658845 4520125 7895122 8777541 8451277 1302850 7580489
• hours: an array of seven integers to hold the number of hours worked by each employee.
payRate: an array of seven doubles to hold each employee's hourly pay rate.
• wages: an array of seven doubles to hold each employee's gross wages.

The program should relate the data in each array through the subscripts. For example, the number
in element 0 of the 'hours' array should be the number of hours worked by the employee whose
identification number is stored in element 0 of the 'empId' array. That same employee's pay rate
should be stored in element 0 of the 'payRate' array.
The program should display each employee number and ask the user to enter that employee's
hours worked and pay rate. It should then calculate the gross wages for that employee (hours
times pay rate) and store them in the wages array. After the data has been entered for all the
employees, the program should display each employee's identification number and gross wages.
Input Validation: Do not accept negative values for hours or numbers less than 6.00 for pay rate.

Question 4:
The local Driver's License Office has asked you to write a program that grades the written portion
of the driver's license exam. The exam has 20 multiple-choice questions.
Here are the correct answers:
1. B 6. A 11. B 16. C
2. D 7. B 12.C 17. C
3. A 8. A 13. D 18. B
4. A 9. C 14. A 19. D
5. C 10. D 15. D 20. A
Your program should store the correct answers shown above in an array. It should ask the user to
enter the student's answers for each of the 20 questions, and the answers should be stored in
another array. After the student's answers have been entered, the program should display a
message indicating whether the student passed or failed the exam. (A student must correctly
answer 15 of the 20 questions to pass the exam.) It should then display the total number of
correctly answered questions, the total number of incorrectly answered questions, and a list
showing the question numbers of the incorrectly answered questions.
Note: Remember, we don't know what char arrays are so don't use them yet.
Remember: you are not yet allowed to use char arrays

Question 5:
Given two arrays of integers A and B of sizes M and N respectively. Write a function named MIX ()
with four arguments, which will produce a third array named C. such that the following sequence
is followed.

• All even numbers of A from left to right are copied into C from left to right.
• All odd numbers of A from left to right are copied into C from right to left.
• All even numbers of B from left to right are copied into C from left to right.
• All old numbers of B from left to right are copied into C from right to left.

A, B and C are passed as arguments to MIX (). e.g., A is {3, 2, 1, 7, 6, 3} and B is {9, 3, 5, 6, 2, 8, 10}
the resultant array C is {2, 6, 6, 2, 8, 10, 5, 3, 9, 3, 7, 1, 3}.

Question 6:
Jack was bored from his usual routine of studies, and he wants to solve a problem to relax his
mind.

The problem is as follows:

Given a number N denoted the elements in an array. He wants to arrange the elements of an array
such that odd positions have sorted elements in ascending order and even positions have sorted
elements in descending order.

For example,

• If we have 1 2 3 4 5 then the result will be 1 5 2 4 3.

• If we have 3 6 9 10 12 5 15 18 then result would be 3 18 5 15 6 12 9 10.

• If we have 1 6 8 9 11 12 then result would be 1 12 6 11 8 9.

Note: You are not allowed to use any extra array. (this thing is known as inplace algorithm)

Question 7:
Write the following functions to support the set operations.

Each set will be represented by three identifiers that is:

▪ int arr[ ]
 o It will point to an array of integers on heap treated as set of integers
▪ int
o it will store size of array created above treated as size of set/array.
▪ int
o it will store number of Elements stored in set.
▪
Functions:
1. bool addElement (int set[ ], int & noe, int capacity, int element);
Details: Initially the set will be empty when created. This function will add one element in
the set.
2. bool removeElement ( int set[ ], int & noe, int capacity, int element)
Details: This function will remove one element from the set if it is present.
3. bool searchElement (int set[ ], int noe, int element);
Details: This function will search the given element in set and return true if it is present.
4. int searchElementPosition (int set[ ], int noe, int element);
Details: This function will search the given element in set and return its position.
5. bool isEmpty(int noe);
Details: This function will return true if the set is empty.
6. bool isFull( int noe, int capacity);
Details: This function will return true if the set is full.
7. void displaySet ( int set[ ], int noe );
Details: This function will display the elements of set.
8. void intersection (int setA[ ], int setB[ ], int setANoe, int setBoe, int newSet [ ], int &
newSetNoe );
Details: This function will compute the intersection of two sets and place it is new set.
9. void union ( int setA[ ] , int setB[ ], int setANoe, int setBNoe, , int newSet [ ], int &
newSetNoe );
Details: This function will compute union of two sets and place it is new set.
10. void difference (int setA[ ], int setB[ ], int setANoe, int setBNoe, , int newSet [ ], int &
newSetNoe );
Details: This function will compute the difference of A and B(A-B) and place it is new set.
11. bool isSubset (int setA[ ], int setB[ ], int setANoe, int setBNoe);
11.1. return 1 if proper subset
11.2. return 2 if improper subset
11.3. return 0 if not a subset
12. void displayCrossProduct (int setA[ ], int setB[ ], int setANoe, int setBNoe);
Details: This function will display the cross product of A and B on screen.
13. void displayPowerSet ( int set[ ] , int noe);
Details: This function will display the power set of the given function.
14. void creatClone (int sourceSet[ ], int sourceNoe, int sourceCapacity, int targetSet[ ], int
targetNoe, int & targetCapacity );
Details: This function will a copy of the set in targetSet variable.

Sample Run:
const int setACapacity = 10;
int setANOE = 0
int setA[setACapacity];
const int setBCapacity = 7;
int setBNOE = 0
int setB[setBCapacity];
addElement ( setA, setANOE, setACapacity, 5 );
addElement ( setA, setANOE, setACapacity, 15 );
addElement ( setA, setANOE, setACapacity, 9 );
addElement ( setA, setANOE, setACapacity, 10 );
cout<<"Set A Elements :”;
displaySet ( setA, setANOE );
addElement ( setB, setBNOE, setACapacity, 9 );
addElement ( setB, setBNOE, setACapacity, 17 );
addElement ( setB, setBNOE, setACapacity, 95 );
cout< < "Set B Elements :";
displaySet ( setB , setBNOE );
const int setCCapacity = 20;
int setCNOE = 0
int setC[setCCapacity];
intersection ( setA, setB, setANOE, setBNOE, setC , setCNOE, setCCapacity);
cout< < "Set C Elements : ";
displaySet ( setC, setCNOE );
cout<<" nPower Set of B: ";
displayPowerSet ( setB, setBNOE );

“Twenty years from now you will be more disappointed by the things that you
didn't do than by the ones you did do. So throw off the bowlines. Sail away
from the safe harbor. Catch the trade winds in your sails.
Explore. Dream. Discover.”
[-Mark Twain-]