RTU Kota B.Tech CSE/IT 5th Semester Analysis of Algorithms Question Paper 2019

RTU Computer Science and IT Analysis of Algorithms 2019 Paper Review

Preparing for the Rajasthan Technical University B.Tech Analysis of Algorithms exam requires a strong command of computational complexity, mathematical proofs, and algorithmic paradigms. For Computer Science and Information Technology students, this subject forms the definitive theoretical core of software engineering. You cannot excel in competitive programming, optimize backend database queries, or pass technical placement interviews without a rigorous understanding of time and space trade-offs.

The 2019 paper tests your capability to solve recursive equations, trace optimal substructures in dynamic programming, and classify theoretical computational bounds. Publishing this specific branch paper review on exam-support.in helps engineering students understand exactly how examiners construct mathematical problems and distribute marks across the algorithm design modules. This systematic preparation helps you approach your fifth-semester exam confidently, Jaiprakash.

Understanding the CSE/IT Branch Exam Pattern

The RTU theory examination is a three-hour paper worth 70 marks. The paper features three distinct sections designed to evaluate both foundational definitions and step-by-step algorithmic tracing.

• Part A: This section contains ten compulsory questions worth two marks each. You must define asymptotic notations (Big-O, Theta, Omega), state the principle of optimality, define a feasible solution in the greedy approach, or explain the properties of a heap data structure under 30 words.
• Part B: You will find seven questions here. You must answer five of them. Each question is worth four marks. Your answers require solving basic recurrence relations using the Master Theorem, tracing a single pass of the Quick Sort algorithm, or evaluating the time complexity of iterative binary search.
• Part C: This section offers five major questions. You need to answer three. Each question carries ten marks. These require you to execute the 0/1 Knapsack problem using dynamic programming, construct a minimal spanning tree using Kruskal's or Prim's algorithm with a given graph matrix, or explain NP-Completeness along with polynomial-time reduction proofs.

Core Topics Evaluated in the CSE/IT Paper

The 2019 question paper covers several critical modules that establish the mathematical rules for algorithmic efficiency. Focus your study time on these specific computation areas to maximize your exam score.

Asymptotic Analysis and Divide-and-Conquer

This module evaluates your mathematical baseline. You must master the precise definitions of upper, lower, and tight bounds. Practice solving recurrence relations using substitution, recursion trees, and the Master Method. The paper frequently tests your ability to determine time bounds for standard divide-and-conquer algorithms like Merge Sort and Strassen's Matrix Multiplication. Expect to solve equations like:

$$T(n) = 2T\left(\frac{n}{2}\right) + c n$$

Greedy Method

The greedy paradigm builds solutions piece by piece, always choosing the next piece that offers the most immediate benefit. Study the optimal selection criteria for the Fractional Knapsack problem. Practice tracing algorithms for generating Minimum Cost Spanning Trees and calculating single-source shortest paths using Dijkstra's algorithm. The paper evaluates your ability to execute these algorithms step-by-step using cost tracking tables.

Dynamic Programming

Dynamic programming solves optimization problems by breaking them down into simpler, overlapping subproblems and storing the results. You must master the two-dimensional matrix structures for the Longest Common Subsequence (LCS), 0/1 Knapsack, and Matrix Chain Multiplication. Expect ten-mark questions providing specific item weights and values, asking you to compute the maximum profit by filling out the entire DP table explicitly.

Backtracking and Branch-and-Bound

When simple optimization fails, systematic state-space tree searches are required. Study the implementation of the N-Queens problem and the Graph Coloring problem using the backtracking method. Compare this with the Branch-and-Bound approach used for the Travelling Salesperson Problem (TSP), focusing heavily on how lower bounds are calculated to prune the state-space tree and eliminate non-optimal paths early.

NP-Hard and NP-Complete Classes

This theoretical module classifies problems based on their computational tractability. You must understand the structural definitions of P, NP, NP-Complete, and NP-Hard complexity classes. Review Cook's Theorem, which proves the NP-Completeness of the Boolean Satisfiability (SAT) problem, and study the logic behind reducing one problem to another in polynomial time (e.g., reducing SAT to the Clique problem).

Answer Writing Strategy for High Marks

RTU evaluators look for clean recurrence trees, explicit state-space graphs, and step-by-step matrix updates. Use a blue pen for your general text explanations and mathematical derivations. Use a black pen and ruler for drawing recursion trees, dynamic programming tables, and final graphical structures.

In Part A, answer directly. If a question asks for the definition of an NP-Complete problem, state clearly that it is a problem in the NP class to which any other problem in NP can be reduced in polynomial time.

In Part B, use clear computation blocks. When applying the Master Theorem, explicitly list the values of the parameters $a$, $b$, and $f(n)$, state the specific case rule that applies, and write the final complexity bound clearly.

In Part C, tabular precision is critical. When solving a ten-mark 0/1 Knapsack DP problem, draw the complete two-dimensional computation grid. Label the rows with the items and the columns with the knapsack capacities. Fill in each cell linearly, showing the formula substitution $\max(V[i-1, w], v_i + V[i-1, w-w_i])$ for at least the first few updates. Box your final maximum profit value.

Time Management During the Exam

Allocate exactly 20 minutes to Part A. Spend 40 minutes addressing the five short-answer questions in Part B. Reserve the remaining 120 minutes for the three long-answer questions in Part C. Computing dynamic programming matrices, drawing complete branch-and-bound state-space trees, and writing out mathematical reduction proofs requires significant writing time. This distribution guarantees you 40 minutes per major question, giving you time to cross-verify your matrix calculations and recursion boundaries. Use the final 10 minutes to verify your question numbering, ensure all tree edges match their cost weights, and check that your algorithm steps follow a logical progression.