Discussion
Algorithm \(B_{k}, k \in \{1,2\}\) is said to be correct if and only if it calculates the correct values of T[i][j], for all \(0 \le i,j \le n\), (as per the recursive formulation) at the end of the execution of the algorithm \(B_{k}\).
Which one of the following statements is true?
Answer: A
Both algorithms B1 and B2 are correct.
Each entry T[i][j] depends on two others: the one above, T[i-1][j], and the one to its left, T[i][j-1]. An algorithm is correct if both of these already hold their final values when T[i][j] is computed. Row 0 and column 0 are base cases, already equal to 1.
- B1 fills the table row by row, left to right. When it reaches T[i][j], row i - 1 is complete, and T[i][j-1] was computed just before in the same row. Both dependencies are ready.
- B2 fills the table by anti-diagonals, s = i + j from 2 to 2n, computing only the cells with i + j = s in each pass. Both dependencies of T[i][j] have index sum s - 1, so they were computed in the previous pass (or are base cases). Both are ready.
Since both orders respect the dependencies, both give the correct table, ruling out the three options that call either algorithm incorrect. The wasted iterations of B2 make it slower (Θ(n3) work) but not wrong.
Post your comment
Please log in or register to post a comment.
Examination Categories
- SSC Exams
- Banking Exams
- Teaching Exams
- Civil Services Exams
- Railways Exams
- Engineering Recruitment Exams
- Defence Exams
- State Government Exams
- Police Exams
- Insurance Exams
- Nursing Exams
- Other Government Exams
- NRA CET
- PG Entrance Exams
- Campus Placement
- MBA Entrance Exams
- CUET and UG Entrance
- Judiciary Exams
- Regulatory Body Exams
- Software Development