Programming for Problem Solving Notes
MODULE 5: BASIC ALGORITHMS
1. SEARCHING
Searching means finding a particular element from a collection of data.
For example:
• Finding roll number in a student list
• Finding a name in a contact list
• Finding a number in an array
There are mainly two types of searching:
1. Linear Search
2. Binary Search
1.1 LINEAR SEARCH
Definition:
Linear Search checks each element one by one until the required element is found.
It is the simplest searching algorithm.
Algorithm Steps
1. Start from the first element.
2. Compare the current element with the target element.
3. If matched, return the position.
4. Otherwise move to the next element.
5. Repeat until the element is found or array ends.
Example
Array:
10 20 30 40 50
Find = 40
Search Process:
• Compare 10 with 40 → Not equal
• Compare 20 with 40 → Not equal
• Compare 30 with 40 → Not equal
• Compare 40 with 40 → Found
Position = 4
C Program: Linear Search
#include <stdio.h>
int main()
{
int arr[5] = {10, 20, 30, 40, 50};
int i, key, found = 0;
printf("Enter element to search: ");
scanf("%d", &key);
for(i = 0; i < 5; i++)
{
if(arr[i] == key)
{
found = 1;
printf("Element found at position %d", i + 1);
break;
}
}
if(found == 0)
{
printf("Element not found");
}
return 0;
}
Explanation of the Program
int arr[5] = {10, 20, 30, 40, 50};
Creates an array of 5 elements.
int i, key, found = 0;
• i → loop variable
• key → value to search
• found → checks whether element is found
scanf("%d", &key);
Takes input from user.
for(i = 0; i < 5; i++)
Loop traverses entire array.
if(arr[i] == key)
Compares array element with target element.
found = 1;
Marks that element has been found.
break;
Stops loop immediately.
Time Complexity
Worst Case:
n comparisons
Complexity = O(n)
Meaning: If array size doubles, searching time may also double.
1.2 BINARY SEARCH
Definition
Binary Search works only on sorted arrays because it compares the middle element and decides
whether to search in the left half or the right half of the array. It repeatedly divides the array into
two halves, reducing the search area each time until the required element is found or the search
range becomes empty.
Example
Array:
10 20 30 40 50 60 70
Find = 50
Process:
Middle = 40
50 > 40
Search right half.
Next middle = 60
50 < 60
Search left half.
Next middle = 50
Found.
Algorithm
1. Find middle element.
2. Compare middle with target.
3. If equal → found.
4. If target smaller → search left half.
5. If target greater → search right half.
6. Repeat until found.
C Program: Binary Search
#include <stdio.h>
int main()
{
int arr[7] = {10, 20, 30, 40, 50, 60, 70};
int low = 0, high = 6, mid;
int key;
printf("Enter element to search: ");
scanf("%d", &key);
while(low <= high)
{
mid = (low + high) / 2;
if(arr[mid] == key)
{
printf("Element found at position %d", mid + 1);
return 0;
}
else if(key < arr[mid])
{
high = mid - 1;
}
else
{
low = mid + 1;
}
}
printf("Element not found");
return 0;
}
Flow of Binary Search Program
Suppose user enters 50.
Initial:
low = 0 high = 6
Step 1:
mid = 3, arr[mid] = 40
50 > 40
Search right side.
low = 4
Step 2:
mid = 5, arr[mid] = 60
50 < 60
Search left side.
high = 4
Step 3:
mid = 4, arr[mid] = 50
Element found.
Complexity
Binary Search complexity:
O(log n)
Much faster than linear search.
2. SORTING
Sorting means arranging data in:
• Ascending order
• Descending order
Example:
Original: 50 20 40 10
Ascending: 10 20 40 50
2.1 BUBBLE SORT
Definition
Bubble Sort repeatedly compares adjacent elements and swaps them if they are in wrong order.
Largest element moves to the end after each pass.
Example
Array:
5314
Pass 1:
5 3 → swap
3514
5 1 → swap
3154
5 4 → swap
3145
Largest element reached end.
C Program
#include <stdio.h>
int main()
{
int arr[5] = {5, 2, 8, 1, 3};
int i, j, temp;
for(i = 0; i < 4; i++)
{
for(j = 0; j < 4 - i; j++)
{
if(arr[j] > arr[j + 1])
{
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
printf("Sorted array:\n");
for(i = 0; i < 5; i++)
{
printf("%d ", arr[i]);
}
return 0;
}
Program Explanation
Outer loop:
for(i = 0; i < 4; i++)
Controls number of passes.
Inner loop:
for(j = 0; j < 4 - i; j++)
Compares adjacent elements.
Condition:
if(arr[j] > arr[j + 1])
Checks wrong order.
Swapping:
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
Exchanges positions.
Flow of Bubble Sort
Pass 1: Largest element goes to last.
Pass 2: Second largest goes to second last.
Pass 3: Third largest reaches correct position.
Array becomes sorted.
Complexity
Worst Case:
O(n²)
2.2 SELECTION SORT
Definition
Selection Sort is a sorting algorithm that repeatedly compares and places smaller elements in their correct
positions in the array.
C Program
#include <stdio.h>
int main()
{
int arr[5] = {64, 25, 12, 22, 11};
int i, j, temp;
for(i = 0; i < 4; i++)
{
for(j = i + 1; j < 5; j++)
{
if(arr[i] > arr[j])
{
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
printf("Sorted array:\n");
for(i = 0; i < 5; i++)
{
printf("%d ", arr[i]);
}
return 0;
}
Flow of Selection Sort
1. Start from the first element of the array.
2. Compare the current element with all remaining elements one by one.
3. If a smaller element is found, immediately swap both elements.
4. Repeat the same process for the next position of the array.
5. Continue until all elements are arranged in ascending order.
Complexity
O(n²)
2.3 INSERTION SORT
Definition
Insertion Sort places elements in proper position one by one.
Works like arranging playing cards.
Example
Array:
5241
Take 2.
Insert before 5.
2541
Take 4.
Insert between 2 and 5.
2451
Continue.
C Program
#include <stdio.h>
int main()
{
int arr[5] = {5, 2, 4, 6, 1};
int i, key, j;
for(i = 1; i < 5; i++)
{
key = arr[i];
j = i - 1;
while(j >= 0 && arr[j] > key)
{
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
printf("Sorted array:\n");
for(i = 0; i < 5; i++)
{
printf("%d ", arr[i]);
}
return 0;
}
Flow of Insertion Sort
1. Consider first element sorted.
2. Take next element.
3. Compare with previous elements.
4. Shift larger elements.
5. Insert element in correct position.
6. Repeat.
Complexity
Worst Case:
O(n²)
3. FINDING ROOTS OF EQUATIONS
A root of an equation means value of x for which:
f(x) = 0
Example:
x² - 4 = 0
Roots are:
x = 2 and x = -2
BISECTION METHOD (Basic Idea)
The Bisection Method repeatedly divides a selected interval into two equal parts to find the root
of an equation. It checks in which half the sign of the function changes, because a root always
exists where the function changes from positive to negative or negative to positive. The process
continues by reducing the interval again and again until the root value becomes very close to the
exact answer.
Example Equation
f(x) = x² - 4
Choose interval:
x = 1 → f(1) = -3
x = 3 → f(3) = 5
Since sign changes, root exists between 1 and 3.
Middle:
(1 + 3)/2 = 2
f(2) = 0
Root found.
C Program
#include <stdio.h>
float f(float x)
{
return x * x - 4;
}
int main()
{
float a = 1, b = 3, c;
if(f(a) * f(b) > 0)
{
printf("Invalid Interval");
return 0;
}
for(int i = 0; i < 10; i++)
{
c = (a + b) / 2;
if(f(c) == 0)
{
break;
}
else if(f(a) * f(c) < 0)
{
b = c;
}
else
{
a = c;
}
}
printf("Root = %f", c);
return 0;
}
Program Flow
1. Define function f(x).
2. Take two points.
3. Find middle value.
4. Check if root exists.
5. Print root.
4. ORDER OF COMPLEXITY
Time complexity is the measurement of how the running time of an algorithm increases as the
size of the input increases. It helps us understand the efficiency and performance of a program
for small and large amounts of data.
Common Complexities
Complexity Meaning
O(1) Constant time
O(log n) Logarithmic
O(n) Linear
O(n²) Quadratic
Example 1: O(1)
x = a + b;
Runs once.
Example 2: O(n)
for(i = 0; i < n; i++)
Runs n times.
Example 3: O(n²)
for(i = 0; i < n; i++)
{
for(j = 0; j < n; j++)
{
}
}
Nested loop.
Total operations = n × n
Comparison Table
Algorithm Complexity
Linear Search O(n)
Binary Search O(log n)
Bubble Sort O(n²)
Selection Sort O(n²)
Insertion Sort O(n²)
MODULE 6: FUNCTIONS
1. FUNCTIONS
Definition
A function is a block of code that performs a specific task.
Functions help:
• Reduce code repetition
• Improve readability
• Divide large program into smaller parts
Types of Functions
1. Library Functions
2. User-defined Functions
1.1 LIBRARY FUNCTIONS
These are predefined functions provided by C library.
Examples:
Function Purpose
printf() Output
scanf() Input
strlen() Length of string
sqrt() Square root
Example
#include <stdio.h>
#include <math.h>
int main()
{
float x = 25;
printf("Square root = %f", sqrt(x));
return 0;
}
Explanation
sqrt(x)
Returns square root.
Need:
#include <math.h>
1.2 USER-DEFINED FUNCTIONS
Functions created by programmer.
Parts of Function
1. Function Declaration
2. Function Call
3. Function Definition
Example Program
#include <stdio.h>
int sum(int, int);
int main()
{
int a = 10, b = 20, result;
result = sum(a, b);
printf("Sum = %d", result);
return 0;
}
int sum(int x, int y)
{
return x + y;
}
Detailed Explanation
Function Declaration
int sum(int, int);
Tells compiler:
• function name = sum
• return type = int
• takes two integer arguments
Function Call
result = sum(a, b);
Transfers control to function.
Function Definition
int sum(int x, int y)
{
return x + y;
}
Actual body of function.
Flow of Program
1. main() starts.
2. sum(a,b) called.
3. Control goes to function.
4. x and y receive values.
5. Addition performed.
6. Result returned.
7. main() prints output.
Advantages of Functions
• Code reusability
• Easier debugging
• Better organization
• Easier maintenance
FUNCTION WITH NO ARGUMENT AND NO RETURN VALUE
#include <stdio.h>
void message()
{
printf("Welcome to C Programming\n");
}
int main()
{
message();
return 0;
}
FUNCTION WITH ARGUMENT BUT NO RETURN VALUE
#include <stdio.h>
void square(int n)
{
printf("Square = %d", n * n);
}
int main()
{
square(5);
return 0;
}
FUNCTION WITH ARGUMENT AND RETURN VALUE
#include <stdio.h>
int cube(int n)
{
return n * n * n;
}
int main()
{
int result;
result = cube(3);
printf("Cube = %d", result);
return 0;
}
2. PARAMETER PASSING
When values are sent to a function, they are called arguments or parameters.
Example:
sum(5, 10);
5 and 10 are arguments.
Formal Parameters vs Actual Parameters
Type Meaning
Actual Parameter Values passed during function call
Formal Parameter Variables receiving values
Example:
sum(a, b);
Actual Parameters:
a, b
Formal Parameters:
int sum(int x, int y)
x and y
3. CALL BY VALUE
Definition
In call by value, copy of variables is passed.
Original variables do not change.
Example Program
#include <stdio.h>
void change(int x)
{
x = 100;
printf("Inside function = %d\n", x);
}
int main()
{
int a = 10;
change(a);
printf("Inside main = %d", a);
return 0;
}
Output
Explanation
Value of a copied into x.
Only x changes.
Original variable remains unchanged.
Program Flow
1. a = 10
2. change(a) called
3. x receives copy of a
4. x becomes 100
5. Function ends
6. a remains 10
Memory Representation
Variable Value
a 10
x 100
Different memory locations.
4. PASSING ARRAY TO FUNCTIONS
Arrays can also be passed to functions.
Example Program
#include <stdio.h>
void display(int arr[], int size)
{
int i;
for(i = 0; i < size; i++)
{
printf("%d ", arr[i]);
}
}
int main()
{
int a[5] = {1, 2, 3, 4, 5};
display(a, 5);
return 0;
}
Explanation
void display(int arr[], int size)
Function receives array.
display(a, 5);
Passes array and size.
Program Flow
1. Array created in main.
2. Array passed to function.
3. Function accesses elements.
4. Elements printed.
Important Point
Array passing behaves similar to call by reference.
Changes inside function can affect original array.
Example
#include <stdio.h>
void change(int arr[])
{
arr[0] = 100;
}
int main()
{
int a[3] = {1, 2, 3};
change(a);
printf("%d", a[0]);
return 0;
}
Output
100
Original array changed.
5. IDEA OF CALL BY REFERENCE
Definition
In call by reference, address of variable is passed.
Function can modify original variable.
C uses pointers for this.
Example Program
#include <stdio.h>
void swap(int *x, int *y)
{
int temp;
temp = *x;
*x = *y;
*y = temp;
}
int main()
{
int a = 10, b = 20;
printf("Before swap: %d %d\n", a, b);
swap(&a, &b);
printf("After swap: %d %d", a, b);
return 0;
}
Output
Before swap: 10 20
After swap: 20 10
Detailed Explanation
Function Definition
void swap(int *x, int *y)
x and y are pointer variables.
They store addresses.
Function Call
swap(&a, &b);
& gives address of variable.
Swapping
*x = *y;
Changes original value.
Program Flow
1. a = 10, b = 20
2. Addresses passed
3. x points to a
4. y points to b
5. Values exchanged
6. Original variables change
Call by Value vs Call by Reference
Feature Call by Value Call by Reference
What is passed Copy Address
Original variable changes No Yes
Memory Different Same