Lab on Data Structure: Practical Unit 1
Table of Contents
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;
}
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.