SUBJECT : DATA STRUCTURE AND ALGORITHM

Question no 01: [15 Marks]

Suppose an institute hires you to develop a system for an entry test. Undergraduates and graduates can apply for their desired program. They are limited number of seats 50 for graduates and 50 for undergraduates. The students will be enrolled on FCFS basis. You are supposed to enroll only the students who meet the following criteria.

• The students having 60 above percentage in their intermediate exams can apply for bachelors program.
• The students having CGPA 3 above in their graduate can apply for masters program.

Solution Guidelines:

Create a class named Student having the following details.

• name,fatherName,CNIC_no,phoneNumber,intermediatePercentage,appl iedProgram.
• provideSeatNum():allocate seat numbers to the enrolled students for bachelors students use B as initial while M for masters and concatenate with the stored index no to generate seat no for example if a student object is stored at array index 5 its seat no will be [B5 for bachelors while M5 for masters]
• Eligible Criteria (): only those students are eligible to apply who meet the above scenario requirements. If a student is eligible generate its seat no and add it to the entry class array according to their applied programs

Create a class named Entry having the following details.

• Maintain two different arrays for bachelors and masters program.
• Enroll students in first come first serve basis, the size of each array will be 50.
• Invoke student class method named eligible Criteria.
• Display the enrolled students arrays with complete details of the student.

Note: You are not allowed to use any built-in Data Structure classes to implement above scenario.

Question no 02: [05 Marks]

Write a program that inserts the following numbers into an initially empty BST such that the tree produced is equivalent to binary search tree.

50 30 25 75 82 28 63 70 4 43 74

Hint: Calculate the mean value in method and put that value at the root and recursively build the left and right subtree.

A. Implement a function which, given a node in this binary search tree, prints out the maximum depths of its left and right subtrees.

B. Implement a function to find the maximum value of all the nodes in the tree.

C. Implement a function that balance the tree using appropriate rotation type and return the root value.

Note: You are not allowed to use any built-in Data Structure classes to implement above scenario.

Question no 03: [05 Marks]

Consider flight network having places of departure and destination. Flight network represent place name as a node and flight trajectories between place names are the edges. Consider Pakistan cities as a node and show the source and destination paths, show all the paths separately with their labels and include their code as well. Analyze this scenario that tree or graph should implement here, justify and also implement this with appropriate data structure.

Example: Network represents that there are three cities named Karachi, Islamabad and Lahore. Flight schedule from Karachi to Islamabad, Islamabad to Lahore and Lahore to Karachi. Places save as class having departure time and day also.

Note: You are not allowed to use any built-in Data Structure classes to implement above scenario.

NOTE: SOLVE ALL 3 QUESTIONS AS SOON AS POSSIBLE.