Lab on Data Structure: Practical Unit 4

Table of Contents

1. Task 10: Polynomial Addition using Linked Lists
2. Tasks 11-13: Recursion vs Iteration (Factorial, Fibonacci, GCD)
3. Task 15: Sparse Matrix Conversion
4. Viva and Logic Comparison

1. Task 10: Polynomial Addition using Linked Lists

Assignment: WAP to scan a polynomial using a linked list and add two polynomials.

In this program, each node of the linked list represents a term of the polynomial. Each node contains:

Coefficient: The numerical factor.
Exponent: The power to which the variable is raised.
Next: Pointer to the next term.

Logic for Addition: Traverse both lists. If exponents match, add coefficients. If one exponent is higher, add that term to the result list and move only that list's pointer.

2. Tasks 11-13: Recursion vs Iteration

Assignment: Calculate Factorial, Fibonacci series, and GCD using both (i) recursion and (ii) iteration.

Factorial (Task 11)

Recursive: fact(n) = n * fact(n-1).
Iterative: Use a for loop from 1 to n.

Fibonacci Series (Task 12)

Recursive: fib(n) = fib(n-1) + fib(n-2).
Iterative: Use a loop and three variables (a=0, b=1, c) to update the sequence.

GCD - Greatest Common Divisor (Task 13)

Recursive (Euclidean): gcd(a, b) = gcd(b, a % b).
Iterative: Use a while loop with the modulo operator.

3. Task 15: Sparse Matrix Conversion

Assignment: WAP to convert the Sparse Matrix into non-zero form and vice-versa.

A Sparse Matrix is a matrix where most elements are zero. To save space, we store only the non-zero elements in a 3-column format: Row, Column, Value.

Example Conversion:

Original Matrix (2D)	Non-Zero Form (Triplet)
0 5 0 0 0 8 0 0 0	Row: 0, Col: 1, Val: 5 Row: 1, Col: 2, Val: 8

4. Viva and Logic Comparison

Comparison: Recursion vs. Iteration

While Recursion makes the code cleaner and easier to understand for problems like Fibonacci or Trees, it uses more memory because each call is stored on the Stack. Iteration is generally faster and more memory-efficient.

Frequently Asked Questions

Q: Why use a linked list for polynomials?
Since we don't know the number of terms beforehand, linked lists allow dynamic storage and easy insertion of terms in descending order of exponents.

Q: What is the base case for GCD recursion?
The recursion stops when the second number becomes zero; at that point, the first number is the GCD.