Lab Record Format

 

Program/output On The Left Page.

Aim, Description ,analysis and results on the Right Page

Linear Search
// Linear Search in C
#include <stdio.h>
int main() {
int arr[100], n, target, i, found = 0;

printf("Enter the number of elements: ");
scanf("%d", &n);
printf("Enter the elements:\n");
for(i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
printf("Enter the element to search: ");
scanf("%d", &target);

for(i = 0; i < n; i++) {
if(arr[i] == target) {
printf("Element found at position %d\n", i);
found = 1;
break;
}
}
if(!found) {
printf("Element not found\n");
}
return 0;
}

🧪 Sample Input and Output

🔹 Sample Input 1 (Element Present at Beginning):Best Case

Enter the number of elements: 5
Enter the elements: 10 20 30 40 50
Enter the element to search: 10

🔹 Output:

Element found at position 0

🔹 Sample Input 2 (Element Present in the Middle):

Enter the number of elements: 6
Enter the elements: 5 15 25 35 45 55
Enter the element to search: 35

🔹 Output:

Element found at position 3

🔹 Sample Input 3 (Element Present at End):

Enter the number of elements: 4
Enter the elements: 2 4 6 8
Enter the element to search: 8

🔹 Output:

Element found at position 3

🔹 Sample Input 4 (Element Not Present):Worst Case

Enter the number of elements: 5
Enter the elements: 11 22 33 44 55
Enter the element to search: 99

🔹 Output:

Element not found

 

Aim: To implement and understand the working of the Linear Search algorithm to search for an element in a list/array.

Description:

Linear Search, also known as sequential search, is a simple searching algorithm that checks each element of the list one by one until the desired element (called the key or target) is found or the list ends.

The algorithm begins at the first element and compares each element with the key:

·         If a match is found, the index of the element is returned.

·         If no match is found by the end of the list, the algorithm returns that the element is not present.

Linear search is straightforward and does not require the list to be sorted. It is most useful for small datasets or when the list is unsorted.

Step-by-Step Algorithm:

  1. Start
  2. Input the list (array) of elements
  3. Input the element to be searched (called target)
  4. Set a variable found to false
  5. Loop through each element in the list from index 0 to n-1:
    a. If     list[i] == target:
        i. Set     found = true
        ii. Print position     i
        iii. Exit the loop
  6. If found == false, print "Element not found"
  7. Stop

 Analysis:

🔁 Time Complexity:

·         Best Case: O(1) → when the element is at the first position.

·         Worst Case: O(n) → when the element is not found or at the last position.

·         Average Case: O(n/2) ≈ O(n)

Space Complexity:

·         O(1) → as it uses a constant amount of extra space.

Limitations:

·         Inefficient for large lists compared to more advanced algorithms like Binary Search (which requires sorted data).

·         Performance degrades linearly as list size increases.

Advantages:

·         Very simple to implement.

·         Works on both sorted and unsorted lists.

Result:

The Linear Search algorithm was successfully implemented.
Given an array of elements and a target value, the algorithm correctly identified the position of the target element when present and displayed an appropriate message when the element was not found.

The working of the algorithm was verified using multiple test cases with:

·         Target at the beginning

·         Target in the middle

·         Target at the end

·         Target not present in the list

The output matched the expected results in all test cases.

 

 

Comments

Post a Comment

Popular posts from this blog

Data Structures Lab PCCSL307 KTU 2024 Scheme - Dr Binu V P

About Me    Learn the theory Data Structures and Algorithms PCCST303 Scheme and Assessments Experiment List and References Lab Assignments Format of the Lab Record Lab Cycle ( Mandatory Programs) 1.Polynomial Addition Using Arrays 2.Sparse Matrix- Transpose and Addition 3.Stack    Implement  stack using array    Infix to Postfix Conversion and Evaluation 4.Queue    Queue using array     Circular Queue using array     Double ended Queue using array 5.Singly Linked List      Singly  Linked list and operations     Stack using linked list     Queue using linked list    Polynomial addition using linked list    Polynomial multiplication using linked list     Priority Queue-Post office customers simulation     Circular Queue using Linked List 6. Doubly Linked List      Doubly Linked List- Operations     Double Ended Queue ...
Read more

Sparse Matrix - Transpose and Addition

Image
  A sparse matrix is a special type of matrix in which most of the elements are zero or have some default value. In contrast, a dense matrix is one in which most of the elements are non-zero. Sparse matrices are used in various fields, including computer science, numerical analysis, and scientific computing, when dealing with large datasets or systems where efficiency and memory usage are crucial.   As a rule of thumb, if 2/3 of the total elements in a matrix are zeros, it can be called a sparse matrix . Using a sparse matrix representation — where only the non-zero values are stored — the space used for representing data and the time for scanning the matrix are reduced significantly. In many real-world problems — like graphs, networks, or scientific simulations — the majority of elements in the matrix are zero . Such a matrix is called a Sparse Matrix . Formally: A matrix in which the number of zero elements is significantly greater than the number of non-zero elements. ...
Read more

Polynomial Addition using Arrays

Polynomial  Addition We can represent a polynomial as a collection of terms and every term is having a coefficient and exponent. So, we can represent this as a list of terms having coefficients and exponents.  Each term of a polynomial (like 3 x 2 3x^2 , 5 x 1 5x^1 , − 7 x 0 -7x^0 ) can be stored in a structure having two parts: coefficient (like 3, 5, -7) exponent (like 2, 1, 0) An array of such structures represents the whole polynomial. Structure Definition (Example in C) struct Term { int coeff; // Coefficient of the term int expo; // Exponent of the term }; And then you can declare: struct Term poly1 [10], poly2 [10], polyResult [20]; to represent polynomials. Algorithm to Add Two Polynomials Assumption : Both polynomials are sorted in decreasing order of exponents . Steps : Initialize three pointers (indexes): i = 0 for first polynomial (poly1), j = 0 for second polynomial (poly2), k = 0 for result polynomial (polyR...
Read more