Lab on Data Structure: Practical Unit 1

Table of Contents

1. Lab Objectives & Learning Outcomes
2. Core Concept: C++ Templates
3. Task 1: Linear and Binary Search
4. Task 2: Insertion, Bubble, and Selection Sort
5. Lab Exam Tips & Troubleshooting

1. Lab Objectives & Learning Outcomes

The primary goal of this lab is to help students apply theoretical concepts in a practical setting through programming assignments.

Skill Enhancement: Focuses on writing, debugging, and testing code for efficiency.
Outcome: Students will demonstrate proficiency in implementing data structures and analyzing their complexities.

2. Core Concept: C++ Templates

The syllabus explicitly requires the use of Template functions for searching and sorting tasks.

Definition: Templates allow a function or class to work with different data types (int, float, char) without rewriting the code for each type.

Example Template Structure:

        template <typename T>

        int linearSearch(T arr[], int n, T key) {

          for(int i = 0; i < n; i++) {

            if(arr[i] == key) return i;

          }

          return -1;

        }

3. Task 1: Linear and Binary Search

Assignment: Write a program to search an element from a list, giving the user the option to perform Linear or Binary search using template functions.

Implementation Details

Linear Search: Scans every element. Ideal for unsorted lists.
Binary Search: Requires a sorted list. Uses the divide-and-conquer approach to locate elements in O(log n) time.

4. Task 2: Insertion, Bubble, and Selection Sort

Assignment: WAP using templates to sort a list. Give users the option to choose between Insertion, Bubble, or Selection sort.

Logic Summaries for Coding

Algorithm	Key Logic	C++ Concept
Bubble Sort	Compare adjacent elements and swap if needed.	Nested loops with swap().
Selection Sort	Find the minimum element and swap it with the first unsorted element.	Tracking min_index.
Insertion Sort	Build the sorted list one element at a time by inserting it into position.	Shifting elements.

5. Lab Exam Tips & Troubleshooting

Exam Focus: In practical exams, ensure your menu-driven interface is clear and handles invalid inputs gracefully.

Common Error: Forgetting to sort the array before calling the Binary Search function.
Debugging Tip: Use print statements inside your sorting loops to see how the array changes in each "pass."
Template Usage: Ensure the `template <typename T>` line is placed immediately above every function definition that uses it.

Frequently Asked Questions

Q: Why use Templates in this lab?
The syllabus mandates it to ensure students can create generic and reusable code.

Q: What is the benefit of a Menu-Driven program?
It allows the user to interactively choose algorithms, fulfilling the "option" requirement in assignments.