UNIT II

1)Linear and Binary, Search Methods

1. Linear Search (Sequential Search)

Linear Search is the simplest search algorithm. It works by checking each element in a list
or array one by one until the desired element is found or the end of the list is reached.

Algorithm:

1. Start from the first element in the array.

2. Compare the current element with the target element.
3. If they match, return the index of the element.
4. If not, move to the next element and repeat steps 2-3.
5. If the end of the list is reached and the element is not found, return -1 (element not
found).

Time Complexity:

 Best Case: O(1) (The element is at the first position).

 Worst Case: O(n) (The element is at the last position or not found).
 Average Case: O(n).

Space Complexity: O(1) (Constant space required).

#include <stdio.h>

// Function to perform linear search

int linearSearch(int arr[], int n, int target) {
for (int i = 0; i < n; i++) {
if (arr[i] == target) {
return i; // Return index of the target element
}
}
return -1; // Element not found
}

int main() {

Page 1 of 17
 int arr[] = {2, 4, 0, 7, 1, 9, 5};
int target = 7;
int n = sizeof(arr) / sizeof(arr[0]);

int result = linearSearch(arr, n, target);

if (result != -1) {
printf("Element found at index %d\n", result);
} else {
printf("Element not found\n");
}
return 0;
}

2. Binary Search

Binary Search is a much faster search algorithm compared to Linear Search, but it requires
the array to be sorted. It works by repeatedly dividing the search range in half and checking
whether the target element is smaller or greater than the middle element.

Algorithm:

1. Start by finding the middle element of the array.

2. If the middle element is the target, return its index.
3. If the target is smaller than the middle element, search the left half of the array.
4. If the target is greater than the middle element, search the right half of the array.
5. Repeat this process until the element is found or the range is empty (i.e., the start
index is greater than the end index).

Time Complexity:

 Best Case: O(1) (The middle element is the target).

 Worst Case: O(log n) (We halve the search space with each step).
 Average Case: O(log n).

Space Complexity: O(1) for the iterative version (constant space), O(log n) for the
recursive version (due to function call stack).

C Implementation of Binary Search (Iterative and Recursive):

#include <stdio.h>

Page 2 of 17
// Iterative Binary Search function
int binarySearch(int arr[], int low, int high, int target) {
while (low <= high) {
int mid = low + (high - low) / 2;

// Check if target is present at mid

if (arr[mid] == target) {
return mid;
}

// If target is smaller than mid, search the left half

if (arr[mid] > target) {
high = mid - 1;
}
// Otherwise, search the right half
else {
low = mid + 1;
}
}
return -1; // Element not found
}

int main() {
int arr[] = {1, 3, 5, 7, 9, 11, 13};
int target = 7;
int n = sizeof(arr) / sizeof(arr[0]);

int result = binarySearch(arr, 0, n - 1, target);

if (result != -1) {

Page 3 of 17
 printf("Element found at index %d\n", result);
} else {
printf("Element not found\n");
}
return 0;
}
2)Bubble Sort, Selection Sort, Insertion Sort, Quick Sort, Merge Sort.

1. Bubble Sort

Bubble Sort is a simple sorting algorithm that repeatedly steps through the list, compares
adjacent elements, and swaps them if they are in the wrong order. This process is repeated
until the list is sorted.

Algorithm:

1. Traverse the list from the beginning.

2. Compare each pair of adjacent elements.
3. If the current element is greater than the next element, swap them.
4. After each full pass through the list, the largest element is moved to its correct
position.
5. Repeat the process for the remaining unsorted part of the list.
6. If no swaps are made in a pass, the list is sorted.

Time Complexity:

 Best Case: O(n) (when the list is already sorted).

 Worst Case: O(n²) (when the list is sorted in reverse order).
 Average Case: O(n²).

Space Complexity: O(1) (in-place sorting).

#include <stdio.h>

void bubbleSort(int arr[], int n) {

for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
// Swap arr[j] and arr[j + 1]
int temp = arr[j];

Page 4 of 17
 arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}

void printArray(int arr[], int size) {

for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}

int main() {
int arr[] = {64, 25, 12, 22, 11};
int n = sizeof(arr) / sizeof(arr[0]);

printf("Unsorted array: ");

printArray(arr, n);

bubbleSort(arr, n);

printf("Sorted array: ");

printArray(arr, n);

return 0;
}

2. Selection Sort

Page 5 of 17
Selection Sort is an in-place comparison-based sorting algorithm. It repeatedly finds the
minimum element from the unsorted part of the array and swaps it with the first unsorted
element.

Algorithm:

1. Start from the first element of the array.

2. Find the smallest element in the unsorted part of the array.
3. Swap the smallest element found with the first element of the unsorted part.
4. Move the boundary between sorted and unsorted parts one element to the right.
5. Repeat this process for all elements.

Time Complexity:

 Best Case: O(n²).

 Worst Case: O(n²).
 Average Case: O(n²).

Space Complexity: O(1) (in-place sorting).

3. Insertion Sort

Insertion Sort is a simple sorting algorithm that builds the sorted list one element at a time
by inserting each new element into its correct position in the sorted part of the list.

Algorithm:

1. Start from the second element of the list.

2. Compare the current element with the element(s) in the sorted part of the list.
3. Move the current element to its correct position by shifting the larger elements one
position to the right.
4. Repeat the process for all elements.

Time Complexity:

 Best Case: O(n) (when the list is already sorted).

 Worst Case: O(n²) (when the list is sorted in reverse order).
 Average Case: O(n²).

Space Complexity: O(1) (in-place sorting).

#include <stdio.h>

void insertionSort(int arr[], int n) {

for (int i = 1; i < n; i++) {
int key = arr[i];

Page 6 of 17
 int j = i - 1;

// Move elements of arr[0..i-1] that are greater than key

// to one position ahead of their current position
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}

void printArray(int arr[], int size) {

for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}

int main() {
int arr[] = {64, 25, 12, 22, 11};
int n = sizeof(arr) / sizeof(arr[0]);

printf("Unsorted array: ");

printArray(arr, n);

insertionSort(arr, n);

printf("Sorted array: ");

Page 7 of 17
 printArray(arr, n);

return 0;
}

4. Quick Sort

Quick Sort is an efficient divide-and-conquer algorithm. It works by selecting a pivot

element from the array and partitioning the other elements into two sub-arrays, according to
whether they are smaller or larger than the pivot. The sub-arrays are then sorted recursively.

Algorithm:

1. Choose a pivot element from the array.

2. Partition the array into two sub-arrays:
o One with elements smaller than the pivot.
o One with elements larger than the pivot.
3. Recursively apply the same process to the sub-arrays.

Time Complexity:

 Best Case: O(n log n) (balanced partitions).

 Worst Case: O(n²) (when the pivot is always the smallest or largest element).
 Average Case: O(n log n).

Space Complexity: O(log n) (due to recursion stack).

C Implementation of Quick Sort:

#include <stdio.h>

void swap(int* a, int* b) {

int temp = *a;
*a = *b;
*b = temp;
}

int partition(int arr[], int low, int high) {

int pivot = arr[high]; // pivot element
int i = low - 1; // index of smaller elemen

Page 8 of 17
 for (int j = low; j < high; j++) {
if (arr[j] <= pivot) {
i++;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return i + 1; // return pivot index
}
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);

quickSort(arr, low, pi - 1); // Recursively sort the left sub-array

quickSort(arr, pi + 1, high); // Recursively sort the right sub-array
}
}
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}

int main() {
int arr[] = {64, 25, 12, 22, 11};
int n = sizeof(arr) / sizeof(arr[0]);

printf("Unsorted array: ");

Page 9 of 17
 printArray(arr, n);

quickSort(arr, 0, n - 1);

printf("Sorted array: ");

printArray(arr, n);

return 0;
}
2)Binary trees, Properties, Representation and Traversals (DFT, BFT), Expression Trees
(Infix, prefix, postfix). in ADS&A

Binary Trees in Algorithm Design and Analysis (ADS&A)

A binary tree is a tree data structure in which each node has at most two children, commonly
referred to as the left child and right child.

1. Properties of Binary Trees

 Binary Tree Structure: Every node has at most two children.

 Root: The top node of the tree is the root, from where the tree originates.
 Leaf Nodes: Nodes that do not have children are called leaf nodes.
 Depth of a Node: The number of edges from the root to the node.
 Height of the Tree: The height of the tree is the maximum depth of any node in the
tree.
 Full Binary Tree: A binary tree is full if every node has either 0 or 2 children.
 Complete Binary Tree: A binary tree is complete if all levels are fully filled except
possibly for the last level, which is filled from left to right.
 Perfect Binary Tree: A binary tree is perfect if all internal nodes have two children,
and all leaf nodes are at the same level.
 Balanced Binary Tree: A binary tree is balanced if the height of the left and right
subtrees of any node differs by at most 1.

2. Representation of Binary Trees

Binary trees can be represented in multiple ways:

a. Array Representation:

 The binary tree is represented as an array. The root node is stored at index 0.
 For any node at index i, the left child is at index 2i + 1, and the right child is at
index 2i + 2.

Page 10 of 17
b. Linked Representation:

 Node Structure: A binary tree can be represented using a node structure with three
parts:
o Data: The data contained in the node.
o Left Pointer: A pointer/reference to the left child.
o Right Pointer: A pointer/reference to the right child.

struct Node {
int data;
struct Node* left;
struct Node* right;
};

3. Traversals in Binary Trees

There are two primary types of binary tree traversals:

a. Depth-First Traversal (DFT)

In Depth-First Traversal, the tree is traversed deeply before backtracking. There are three
types of depth-first traversals:

 Inorder (LNR): Traverse the left subtree, visit the root node, then traverse the right
subtree.
o Example: For a tree with the root 1, left child 2, and right child 3, the
traversal will be: 2, 1, 3.
 Preorder (NLR): Visit the root node, then traverse the left subtree, then traverse the
right subtree.
o Example: 1, 2, 3.
 Postorder (LRN): Traverse the left subtree, then traverse the right subtree, and
finally visit the root node.
o Example: 2, 3, 1.

Code Example (Inorder Traversal):

void inorder(struct Node* root) {

if (root != NULL) {
inorder(root->left); // Traverse left
printf("%d ", root->data); // Visit root
inorder(root->right); // Traverse right
}

Page 11 of 17
}

b. Breadth-First Traversal (BFT) or Level-Order Traversal

In Breadth-First Traversal, the tree is traversed level by level, starting from the root. A
queue is often used to implement this traversal.

 Level Order Traversal involves visiting all nodes at each level of the tree before
moving to the next level.

Code Example (Level-Order Traversal):

4. Expression Trees

An expression tree is a binary tree used to represent expressions. Each internal node
represents an operator, and the leaf nodes represent operands (constants or variables).
Expression trees are used for parsing and evaluating expressions.

Expression trees can represent expressions in three formats:

 Infix Notation: Operators are placed between operands. Example: A + B

 Prefix Notation (Polish Notation): The operator is placed before the operands.
Example: + A B
 Postfix Notation (Reverse Polish Notation): The operator is placed after the
operands. Example: A B +

a. Infix Expression Tree

An infix expression tree has operators at the internal nodes and operands at the leaves. The
order of operations is preserved in the tree.

Example: Expression: (A + B) * C

 Infix tree:

*
/ \
+ C
/\
A B

b. Prefix Expression Tree

In the prefix expression tree, the operator appears before its operands.

Example: Prefix Expression: * + A B C

Page 12 of 17
  Prefix tree:

*
/ \
+ C
/\
A B

c. Postfix Expression Tree

In the postfix expression tree, the operator appears after its operands.

Example: Postfix Expression: A B + C *

 Postfix tree:

*
/ \
+ C
/\
A B

Converting Between Notations:

 Infix to Prefix/Postfix:
o Infix to Prefix: Reverse the infix expression, convert it to postfix, and then
reverse the result.
o Infix to Postfix: Use the Shunting Yard algorithm or a stack-based approach
to convert infix to postfix.

Algorithm for Infix to Postfix Conversion (using Stack):

1. Initialize an empty stack and an empty result.

2. Scan the infix expression from left to right:
o If the token is an operand, append it to the result.
o If the token is an operator, pop operators from the stack and append them to
the result until you find an operator with lower precedence. Push the current
operator onto the stack.
o If the token is a left parenthesis, push it onto the stack.
o If the token is a right parenthesis, pop and append operators from the stack
until you encounter a left parenthesis.
3. Pop any remaining operators in the stack and append them to the result.

Time Complexity of Binary Tree Operations:

Page 13 of 17
  Search: O(h), where h is the height of the tree (for a balanced binary tree, this is
O(log n)).
 Insert/Delete: O(h) for balanced trees (for an unbalanced tree, it can degrade to
O(n)).
 Traversal (DFT, BFT): O(n), where n is the number of nodes in the tree.

Space Complexity:

 Space for Representation: O(n), where n is the number of nodes (due to pointers in
the linked representation).
 Traversal Space: O(h) for DFS (stack space) and O(n) for BFS (queue space).

4)Graphs-Basic Concepts, Storage structures and Traversals. in ADS&A

Graphs in Algorithm Design and Analysis (ADS&A)

A graph is a non-linear data structure consisting of a set of vertices (or nodes) connected by
edges (or arcs). Graphs are used to represent various real-world problems such as networks,
social media connections, paths in a maze, and more.

1. Basic Concepts of Graphs

 Vertex (Node): A fundamental unit in a graph, representing an entity (e.g., a person,

city, or point).
 Edge (Arc): A connection between two vertices, representing a relationship between
the entities.
 Graph Types:
o Undirected Graph: In an undirected graph, edges have no direction, meaning
if there's an edge between vertex A and vertex B, you can travel in both
directions (A ↔ B).
o Directed Graph (Digraph): In a directed graph, edges have a direction,
meaning the edge from vertex A to vertex B is distinct from the edge from
vertex B to vertex A (A → B).
o Weighted Graph: In a weighted graph, edges have weights or costs
associated with them, representing the distance, time, or cost between nodes.
o Unweighted Graph: An unweighted graph does not have any weights
associated with the edges.
o Cyclic Graph: A graph that contains at least one cycle (a path that starts and
ends at the same vertex).
o Acyclic Graph: A graph that does not contain any cycles. If the graph is
directed, it is known as a Directed Acyclic Graph (DAG).
o Connected Graph: In an undirected graph, if there is a path between every
pair of vertices, the graph is said to be connected.
o Disconnected Graph: A graph that is not connected, meaning some vertices
do not have paths to other vertices.

2. Graph Storage Structures

Graphs can be represented using two primary storage structures:

Page 14 of 17
a. Adjacency Matrix:

 A 2D array adj[][] where adj[i][j] is 1 (or the weight of the edge) if there is
an edge from vertex i to vertex j, and 0 (or infinity for weighted graphs) if there is
no edge.
 Pros:
o Simple to implement.
o Efficient for dense graphs (graphs with many edges).
 Cons:
o Wastes space for sparse graphs (graphs with few edges).
o O(1) time complexity for checking if there is an edge between two vertices,
but O(n²) space complexity.

Example of Adjacency Matrix for a graph with 4 vertices (V = 4):

lua
Copy
0 1 2 3
---------------
0|0 1 0 1
1|0 0 1 0
2|1 0 0 0
3|0 0 0 0

In this matrix, adj[0][1] = 1 means there is an edge from vertex 0 to vertex 1.

b. Adjacency List:

 An array of lists (or vectors). Each list corresponds to a vertex and contains a list of its
adjacent vertices (i.e., the vertices to which it is directly connected by edges).
 Pros:
o More space-efficient for sparse graphs.
o O(1) time complexity for adding an edge, and the space complexity is O(E),
where E is the number of edges.
 Cons:
o Checking if an edge exists between two vertices takes O(n) time.

Example of Adjacency List for the same graph:

0: 1 -> 3
1: 2
2: 0
3: (no adjacent vertices)

Page 15 of 17
In this list:

 Vertex 0 is connected to vertices 1 and 3.

 Vertex 1 is connected to vertex 2.
 Vertex 2 is connected to vertex 0.
 Vertex 3 has no outgoing edges.

3. Graph Traversals

Graph traversal refers to the process of visiting all vertices in a graph. There are two primary
types of graph traversal:

a. Depth-First Search (DFS):

DFS explores as far as possible along each branch before backtracking. It's implemented
using recursion or a stack.

 Steps:
1. Start at a vertex, mark it as visited.
2. Visit all its unvisited adjacent vertices recursively.
3. Backtrack when no more unvisited adjacent vertices are found.
 Applications:

o Used to check for connectivity.

o Used in topological sorting (in DAGs).
o Used in cycle detection (in directed and undirected graphs).
 Time Complexity: O(V + E), where V is the number of vertices and E is the number
of edges.
 Space Complexity: O(V), for storing the visited nodes and recursion stack.

b. Breadth-First Search (BFS):

BFS explores all the neighbors of a vertex before moving to the next level. It uses a queue to
keep track of vertices to be explored.

 Steps:
1. Start at a vertex, mark it as visited, and enqueue it.
2. Dequeue a vertex, visit all its unvisited adjacent vertices, and enqueue them.
3. Repeat the process until the queue is empty.
 Applications:

o Used for finding the shortest path in an unweighted graph.

o Used in level-order traversal of a tree.
 Time Complexity: O(V + E), where V is the number of vertices and E is the number
of edges.
 Space Complexity: O(V), for storing the visited nodes and the queue.

Code Example (BFS) in C:

Page 16 of 17
4. Graph Applications

 Shortest Path: Algorithms like Dijkstra's or Bellman-Ford for finding the shortest
path in weighted graphs.
 Topological Sort: Used in directed acyclic graphs (DAGs) for ordering vertices in a
way that for every directed edge u → v, vertex u comes before vertex v.
 Cycle Detection: DFS and BFS are commonly used for detecting cycles in directed
and undirected graphs.
 Minimum Spanning Tree: Algorithms like Prim's and Kruskal's for finding the
minimum spanning tree in a weighted graph.

5. Summary of Time and Space Complexities:

 DFS Time Complexity: O(V + E) and Space Complexity: O(V) due to recursion
stack or visited array.
 BFS Time Complexity: O(V + E) and Space Complexity: O(V) due to the queue
used to store vertices.

Page 17 of 17