CC-213L – Data Structures and Algorithms
Fall 2024
LAB-09 Issue Date: November 25, 2024
The objective of this lab is to:
1. Understanding sparse matrices and their implementation.
2. Develop the ability to trace recursive calls and understand the flow of execution in recursive
functions.
3. Learn to visualize the recursive call stack and identify base cases and termination conditions.
4. Writing basic recursive functions.
ALERT!
1. You are encouraged to bring your laptop to attend the lab.
2. This is an individual lab, you are strictly NOT allowed to discuss your solution with fellow colleagues,
even not allowed asking how is he/she is doing, it may result in negative marking. You can ONLY
discuss with your TAs or with me.
3. Anyone caught in act of plagiarism would be awarded an “F” grade in this Lab.
Task 01: [25 Marks]
Develop a class for 2D matrices of any generic type (using templates), This class should store the elements of
the 2-D matrix in a linear array of generic type created dynamically. Thus you will have to use a mapping
formula to store and retrieve items. Assume the matrix you receive is always an upper left triangular matrix.
1 2 3 4 5
6 7 8 9 0
10 11 12 0 0
14 15 0 0 0
16 0 0 0 0
Your class should support the following operations:
1. Constructor, destructor, Copy-constructor.
You should always implement constructor, destructor and copy-constructor in case of dynamic
memory allocation.
2. int mapIndex( int i, int j )
This is a private function that should take a 2D index and return its equivalent linear index.
3. void setElement( int i, int j, T val)
Set the value of element stored at ith row and jth column.
4. bool updateElement( int i, int j, T updatedval)
Set the value of element stored at ith row and jth column.
5. T getElement( int i, int j )
Get the value of element stored at ith row and jth column.
6. void printMatrix( )
This function should print the matrix on console (in 2D matrix form).
7. void transpose ( )
This function should take the transpose of the matrix.
8. void printSubMatrix( int r1, int r2, int c1, int c2)
This function should display the sub matrix specified by given arguments.
Write a main program providing menu to make it easy to use and test matrix class functionalities. No marks
shall be given without this driver program.
Punjab University College Of Information Technology Page 1 of 3
Madiha Khalid
CC-213L – Data Structures and Algorithms
Fall 2024
LAB-09 Issue Date: November 25, 2024
Task 02: [25 Marks]
1. Write a recursive function to check whether a number is prime or not. A prime number is a number
that is divisible only by itself and 1 (e.g. 2, 3, 5, 7, 11).
2. Write a recursive function to print the binary equivalent of a given number. For example, if the given
number is 21 then function should print 10101.
3. Write a number to print first n Fibonacci numbers.
4. Write a recursive function that take two integer numbers as input and return their GCD (Greatest
Common Divisor) using Euclidian method.
5. Write a recursive function to compute and return an.
Task 03: [20 Minutes]
Create a recursive trace for the following algorithms using the provided starting values in the main
functions, also show the return value at each level of recursion. Do the dry run on your notebooks.
int fun1(int a, int b)
{
a > b ? return a : return b;
}
int fun(int a, int b)
{
if(a == 0)
return b;
return fun(a-1,2*b), fun(a-1,2*b-1);
}
int main()
{
fun(8,0);
return 0;
}
int fun1(int a, int b)
{
a > b ? return a : return b;
}
int fun(int a, int b)
{
if(a == 0)
return b;
return fun( fun(a-1,2*b), fun(a-1,2*b-1) );
}
int main()
{
fun(4,5);
return 0;
}
Punjab University College Of Information Technology Page 2 of 3
Madiha Khalid
CC-213L – Data Structures and Algorithms
Fall 2024
LAB-09 Issue Date: November 25, 2024
int triangularNumber(int n)
{
if (n == 1)
return 1;
return n + triangularNumber(n - 1);
}
void printTriangularNumbers(int n, int current = 1)
{
if (current > n)
return;
cout << triangularNumber(current) << " ";
printTriangularNumbers(n, current + 1);
}
int main()
{
int terms = 6;
printTriangularNumbers(terms);
return 0;
}
Punjab University College Of Information Technology Page 3 of 3
Madiha Khalid
