Bangladesh Oil Gas and Mineral Corporation (BOGMC)- Petrobangla
Post: Assistant Manager (CSE/IT/ICT)
Exam Date: 31.05.2024, Exam Taker: BUET
a =85
if a>=90 print A;
if a>=80 print B;
if a>=70 print C;
if a>=60 print D;
else print F;
B C D
Evaluation:
a = 85 is not greater than or equal to 90 → A is not printed.
a = 85 is greater than or equal to 80 → B is printed.
a = 85 is greater than or equal to 70 → C is printed.
a = 85 is greater than or equal to 60 → D is printed.
The else part is skipped because the previous condition is true.
- Public (
public) → Accessible everywhere (inside class, package, subclass, and outside package). - Private (
private) → Only accessible within the same class (not within the package, subclass, or outside). - Protected (
protected) → Accessible within the class, package, and subclasses (even outside the package), but not outside the package unless it’s through inheritance.
i
/ \
h g
/ \ / \
f c d e
/ \
a b
[ not possible to find b tree by only given post order]
Array Representation:
Formula for Binary Tree Array Representation:
- Left child of node at index
i→2i + 1 - Right child of node at index
i→2i + 2
Time Complexity of QuickSort with First Element as Pivot on Sorted Array
In QuickSort, when we select the first element as the pivot, the time complexity heavily depends on the partitioning step. In the case of an already sorted array, the first element is always the smallest element, leading to an unbalanced partitioning where one sub-array is always empty.
Steps:
- Pivot Selection: The first element is chosen as the pivot.
- Partitioning: The pivot is placed at its correct position, and the array is partitioned into two sub-arrays:
- Left sub-array: Empty (no elements smaller than the pivot).
- Right sub-array: Contains n-1 elements (larger than the pivot).
- Recursion: This process repeats for the right sub-array, reducing the problem size by 1 each time, leading to a total of n recursive calls.
Recurrence Relation:
T(n) = T(n-1) + O(n)
Where:
- T(n-1) is the time for the next recursive call.
- O(n) is the partitioning step.
This recurrence leads to:
T(n) = O(n) + O(n-1) + O(n-2) + ... + O(1) = O(n²)
Conclusion:
When the array is already sorted, and the first element is chosen as the pivot, the QuickSort algorithm exhibits worst-case time complexity of O(n²) due to highly unbalanced partitioning at each step.
🎥 Video Solution:
Quick Sort Algorithm
🎥 Video Solution:
Quick Sort Performance
3. Employee (empno, PK, empname, monthlysalary, deptno, FK, mqrnd(FK)) Department(deptno, deptname,deptlocation) Course(crscode,pk, crd desc, crs category, crs duration); Offering(off begingate, crscode fk, offeringlocation, empno fk)
Find SELECT d.deptno, d.deptname, AVG(e.monthsalary) AS average_salary
FROM Department d
JOIN Employee e ON d.deptno = e.deptno
GROUP BY d.deptno, d.deptname
HAVING AVG(e.monthsalary) > 1000;SELECT c.crscode, c.crsdesc, c.crscategory, c.crsduration, COUNT(o.crscode) AS offering_count FROM Course c JOIN Offering o ON c.crscode = o.crscode GROUP BY c.crscode, c.crsdesc, c.crscategory, c.crsduration HAVING COUNT(o.crscode) = 2;
Traffic Signal Cycle:
- GREEN: 70 seconds
- YELLOW: 5 seconds
- RED: 75 seconds
- Total cycle time = 70 + 5 + 75 = 150 seconds.
Clock Input:
The FSM is driven by a clock with a 5-second period. This means the FSM transitions every 5 seconds.
Number of States:
- GREEN: 70 seconds → 70 / 5 = 14 clock cycles
- YELLOW: 5 seconds → 5 / 5 = 1 clock cycle
- RED: 75 seconds → 75 / 5 = 15 clock cycles
- Total clock cycles in one full cycle = 14 + 1 + 15 = 30 clock cycles.
State Representation:
The FSM must cycle through 30 states to complete one full traffic signal cycle.
Calculating the Number of Flip-Flops:
The number of flip-flops required is determined by the number of states in the FSM. For N states, the minimum number of flip-flops required is:
Number of flip-flops = ⌈log₂(N)⌉
Calculating:
log₂(30) ≈ 4.906
⌈4.906⌉ = 5
Source: [Byjus.com]
