Detailed Notes - Unit 1: Introduction

UNIT 1: INTRODUCTION

1.1 Algorithm
Definition: An algorithm is a finite sequence of well-defined steps to solve a problem.
Properties of an algorithm:
- Input: Zero or more inputs.
- Output: At least one output.
- Definiteness: Steps are precise and unambiguous.
- Finiteness: Must terminate after a finite number of steps.
- Effectiveness: Each step must be feasible and executable.
Example: Binary search, sorting algorithms.

1.2 Complexity Analysis

Time Complexity: The amount of time taken by an algorithm as a function of input size
(n).
- Best Case: Minimum time taken for given input.
- Worst Case: Maximum time taken.
- Average Case: Expected time over all possible inputs.
Space Complexity: The amount of memory required by an algorithm.
- Includes fixed part (constants, program size) and variable part (dynamic memory,
recursion stack).
Example:
- Linear Search: O(n).
- Binary Search: O(log n).

1.3 Asymptotic Notations

- Big O (O): Upper bound, worst case. Example: QuickSort O(n^2).
- Omega (Ω): Lower bound, best case. Example: Insertion Sort Ω(n).
- Theta (Θ): Tight bound, average case.
Graphical Representation:
- O(g(n)) grows no faster than g(n).
- Ω(g(n)) grows at least as fast as g(n).
- Θ(g(n)) grows exactly as g(n).

1.4 Elementary Data Structures

Stack:
- Linear structure, Last In First Out (LIFO).
- Operations: push, pop, peek.
- Applications: Expression evaluation, function calls.
Queue:
- Linear structure, First In First Out (FIFO).
- Operations: enqueue, dequeue.
- Applications: Scheduling, BFS.
Binary Tree:
- Hierarchical structure, each node has max 2 children.
Binary Search Tree (BST):
- Ordered binary tree, left child < root < right child.
Heap:
- Complete binary tree, used in priority queues.
- Max-Heap: Parent node ≥ children.
- Min-Heap: Parent node ≤ children.
Graph:
- Collection of vertices and edges.
- Representations: Adjacency matrix, adjacency list.
- Applications: Social networks, computer networks.

1.5 Heap Sort

Heap Sort is a comparison-based sorting algorithm using heap data structure.
Steps:
1. Build a max heap from the input array.
2. Swap the first (largest) element with the last.
3. Reduce heap size and heapify root.
4. Repeat until array is sorted.
Complexity: O(n log n).
Advantages: In-place sorting, no extra memory required.
Summary:
In this unit, we covered the basics of algorithm definition, complexity analysis,
asymptotic notations,
and essential data structures like stack, queue, binary tree, BST, heap, and graph,
along with heap sort.
 Detailed Notes - Unit 2: Traversal and Search Techniques
UNIT 2: TRAVERSAL AND SEARCH TECHNIQUES

2.1 Binary Tree Traversals

Traversal: Visiting all the nodes of a tree in a specific order.
Types of Traversals:
- Preorder (NLR): Visit root, then left, then right.
- Inorder (LNR): Visit left, then root, then right.
- Postorder (LRN): Visit left, then right, then root.
Example: For tree with root A, left B, right C,
Preorder = A B C, Inorder = B A C, Postorder = B C A.
Complexity: O(n) where n is number of nodes.

Pseudocode - Inorder Traversal:

Inorder(node):
if node != NULL:
Inorder([Link])
print([Link])
Inorder([Link])

2.2 Graph Traversals

Graph: A set of vertices connected by edges.
Two main traversal techniques:
1. Breadth-First Search (BFS):
- Uses a queue.
- Explores neighbors level by level.
- Applications: Shortest path in unweighted graph, network broadcasting.
- Complexity: O(V + E).

Pseudocode - BFS:
BFS(G, start):
mark start as visited, enqueue(start)
while queue not empty:
 v = dequeue()
for each neighbor u of v:
if u not visited:
mark u visited, enqueue(u)

2. Depth-First Search (DFS):

- Uses recursion or stack.
- Explores path as deep as possible before backtracking.
- Applications: Cycle detection, topological sorting.
- Complexity: O(V + E).

Pseudocode - DFS:
DFS(v):
mark v as visited
for each neighbor u of v:
if u not visited:
DFS(u)

2.3 Divide and Conquer

General Method:
- Divide: Break problem into smaller subproblems.
- Conquer: Solve subproblems recursively.
- Combine: Merge solutions of subproblems.

Examples:
1. Binary Search:
- Input: Sorted array.
- Compare mid element with target.
- If target < mid, search left half, else right half.
- Complexity: O(log n).

2. Merge Sort:
- Divide array into halves.
- Recursively sort halves.
- Merge sorted halves.
- Complexity: O(n log n).

3. Quick Sort:
- Select pivot element.
- Partition array into left (< pivot) and right (> pivot).
- Recursively sort partitions.
- Average case: O(n log n), Worst case: O(n^2).

Summary:
This unit covered binary tree traversals (inorder, preorder, postorder),
graph traversals (BFS, DFS), and divide-and-conquer techniques (binary search, merge
sort, quick sort).
 Detailed Notes - Unit 3: Greedy Method
UNIT 3: GREEDY METHOD

3.1 Introduction to Greedy Method

Definition: The greedy method builds up a solution step by step, always choosing the
next step that offers the most immediate benefit (locally optimal choice), hoping to find
a global optimum.
Characteristics:
- Greedy-choice property: A global solution can be arrived at by choosing a local
optimum.
- Optimal substructure: An optimal solution to the problem contains optimal solutions
to subproblems.

3.2 General Method

Greedy Algorithm Framework:
1. Determine the optimal substructure property.
2. Develop a recursive definition of the solution.
3. Show that local choice leads to global optimum.
4. Construct an algorithm implementing the greedy strategy.

3.3 Knapsack Problem (Fractional)

Problem: Given n items with weights and values, fill a knapsack of capacity W to
maximize total value.
Greedy Approach:
- Compute value/weight ratio for each item.
- Sort items in descending order of ratio.
- Take items until capacity is full (items can be divided).
Complexity: O(n log n) (due to sorting).
Limitation: Does not work for 0/1 Knapsack.

3.4 Minimum Cost Spanning Tree (MST)

Definition: A spanning tree of a graph with minimum total edge cost.
Algorithms:
1. Prim’s Algorithm:
- Start with any vertex, repeatedly add the smallest edge connecting tree to outside.
- Complexity: O(E log V) with priority queue.

2. Kruskal’s Algorithm:
- Sort edges by weight.
- Add edges one by one if they don’t form a cycle (use union-find).
- Complexity: O(E log E).

3.5 Single Source Shortest Path

Problem: Find shortest paths from a source to all vertices in a weighted graph.
Dijkstra’s Algorithm:
- Initialize distance[source] = 0, others = ∞.
- Use priority queue to extract vertex with minimum distance.
- Relax all edges of that vertex.
- Repeat until all vertices processed.
Complexity: O(V log V + E log V).

Applications of Greedy Algorithms:

- Job sequencing with deadlines.
- Huffman coding (data compression).
- Activity selection problem.

Summary:
The greedy method provides efficient solutions for problems such as Fractional
Knapsack, MST (Prim’s, Kruskal’s), and Single Source Shortest Path (Dijkstra’s).
However, it may fail when the problem does not exhibit greedy-choice property or
optimal substructure.
 Detailed Notes - Unit 4: Dynamic Programming
UNIT 4: DYNAMIC PROGRAMMING

4.1 Introduction to Dynamic Programming (DP)

Definition: DP is an algorithmic technique for solving problems by breaking them down
into simpler subproblems and storing the results to avoid redundant computations.
Key Principles:
- Optimal Substructure: The optimal solution can be constructed from optimal solutions
of subproblems.
- Overlapping Subproblems: Subproblems are solved multiple times in recursion; DP
avoids this by storing results.
Approaches:
- Top-down (Memoization): Solve recursively and store results.
- Bottom-up (Tabulation): Solve iteratively from smaller subproblems.

4.2 Multistage Graphs

Definition: A directed weighted graph divided into stages; DP used to find shortest path
from source to sink.
Algorithm:
- Process vertices from last stage backwards.
- For each vertex, compute cost as min(cost to next + edge weight).
Complexity: O(V + E).

4.3 All-Pair Shortest Path – Floyd-Warshall Algorithm

Definition: Computes shortest paths between all pairs of vertices.
Algorithm:
- Initialize distance matrix with direct edge weights (∞ if no edge).
- For each vertex k, update:
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]).
Complexity: O(n^3).

4.4 Optimal Binary Search Tree (OBST)

Problem: Given keys with search probabilities, construct BST with minimal expected
cost.
Approach:
- Compute cost[i][j] = min over all roots (cost[i][r-1] + cost[r+1][j] + sum of
probabilities).
- Use DP table to find minimum expected cost.
Applications: Database indexing, compiler symbol tables.

4.5 0/1 Knapsack Problem

Problem: Given n items with weights and values, choose subset to maximize value
within capacity W.
Recurrence:
dp[i][w] = max(dp[i-1][w], value[i] + dp[i-1][w-weight[i]]) if weight[i] <= w.
Complexity: O(nW).

4.6 Traveling Salesman Problem (TSP)

Problem: Find shortest tour visiting all cities exactly once and returning to start.
DP Approach (Held-Karp Algorithm):
- Use bitmasking to represent subsets.
- Recurrence: dp[mask][i] = min(dp[mask ^ (1<<i)][j] + dist[j][i]).
- Complexity: O(n^2 * 2^n).

4.7 Flow Shop Scheduling

Problem: Schedule jobs on multiple machines to minimize completion time.
Approach: Use DP to compute optimal job sequences.

Summary:
Dynamic Programming is a powerful technique for solving optimization problems like
Multistage Graphs,
Floyd-Warshall (All Pairs Shortest Path), OBST, 0/1 Knapsack, TSP, and Flow Shop
Scheduling.
 Detailed Notes - Unit 5: Backtracking & Branch and Bound
UNIT 5: BACKTRACKING & BRANCH AND BOUND

5.1 Backtracking - Introduction

Definition: Backtracking is a general algorithmic technique for solving problems
incrementally by building candidates and abandoning a candidate as soon as it is
determined not to be feasible.
Characteristics:
- Uses depth-first search of solution space tree.
- Eliminates infeasible solutions early.
- Explores only promising candidates.
Applications: Combinatorial problems, puzzles, constraint satisfaction problems.

5.2 General Method

Procedure:
1. Define solution space tree (each node represents partial solution).
2. Generate nodes using DFS.
3. If partial solution is infeasible, backtrack to previous step.
4. Continue until solution found or all nodes explored.

5.3 The 8-Queens Problem

Problem: Place 8 queens on a chessboard so that no two attack each other.
Approach:
- Place queens row by row.
- Check if position is safe (no other queen in same column/diagonal).
- If safe, place queen and move to next row.
- If not, backtrack and try another position.
Complexity: O(N!) in worst case but reduced by pruning.

5.4 Sum of Subsets Problem

Problem: Given a set of positive integers and a target sum, find all subsets whose sum
equals the target.
Backtracking Approach:
- Recursively generate subsets.
- At each step, include or exclude an element.
- If current sum exceeds target, backtrack.

5.5 Graph Coloring Problem

Problem: Assign colors to vertices of a graph so that no two adjacent vertices have the
same color.
Approach:
- Assign colors one by one.
- If current assignment valid, move to next vertex.
- If not valid, backtrack.
Applications: Scheduling, register allocation in compilers.

5.6 Hamiltonian Cycle Problem

Problem: Find a cycle in a graph that visits every vertex exactly once and returns to the
start.
Backtracking Approach:
- Build path vertex by vertex.
- If next vertex is not visited and edge exists, add to path.
- If no feasible extension, backtrack.
Complexity: Exponential in general.

5.7 Branch and Bound - Introduction

Definition: Branch and Bound is a systematic method for solving optimization problems.
It divides the problem into subproblems (branching) and uses bounds to prune
unpromising subproblems.
Steps:
- Branch: Divide problem into subproblems.
- Bound: Calculate lower/upper bounds for solutions in subproblem.
- Prune: Ignore subproblems that cannot lead to better solution.

5.8 Traveling Salesperson Problem (TSP) using Branch and Bound

Problem: Find minimum cost Hamiltonian cycle visiting all cities exactly once.
Approach:
- Use reduced cost matrix for bound.
- Expand node with least cost bound (best-first search).
- Continue until optimal tour found.
Complexity: Exponential but prunes many branches compared to brute force.

Summary:
Backtracking is effective for constraint satisfaction problems like 8-Queens, Subset
Sum, Graph Coloring, Hamiltonian Cycles.
Branch and Bound is used for optimization problems like TSP, providing efficiency by
pruning.
 Detailed Notes - Unit 6: Contemporary Issues
UNIT 6: CONTEMPORARY ISSUES

6.1 Introduction
This unit focuses on modern trends and developments in algorithms through expert
lectures, online seminars, and webinars.
It emphasizes the application of algorithms in emerging fields like Artificial Intelligence,
Machine Learning, Cryptography, Cloud Computing, and Big Data.

6.2 Importance of Contemporary Issues

- Keeps learners updated with latest research and industrial practices.
- Bridges the gap between theoretical foundations and real-world applications.
- Prepares students for higher studies, competitive exams, and research opportunities.

6.3 Expert Lectures

- Delivered by industry experts or researchers.
- Topics include advanced algorithms, performance optimization, and real-world
challenges.
- Benefits: Direct exposure to cutting-edge technologies and problem-solving
techniques.

6.4 Online Seminars and Webinars

- Provide flexible, remote access to knowledge from global experts.
- Cover topics like AI algorithms, Machine Learning pipelines, Quantum Computing
algorithms.
- Enhance interaction and encourage collaborative learning.

6.5 Contemporary Topics in Algorithms

1. Artificial Intelligence (AI):
- Algorithms for search (A*, minimax).
- Machine Learning optimization algorithms (gradient descent, backpropagation).

2. Machine Learning (ML):

- Supervised, unsupervised, and reinforcement learning algorithms.
- Applications: Natural language processing, image recognition, recommendation
systems.

3. Cryptography:
- Algorithms for secure communication (RSA, AES, SHA hashing).
- Blockchain algorithms ensuring data integrity and security.

4. Cloud Computing:
- Algorithms for resource allocation, load balancing, data scheduling.
- Ensures efficient utilization of large-scale infrastructure.

5. Big Data:
- Algorithms for distributed data processing (MapReduce, Hadoop).
- Real-time streaming algorithms (Apache Spark).

6.6 Benefits of Exposure to Contemporary Issues

- Enhances problem-solving skills.
- Encourages interdisciplinary research.
- Equips students with skills needed in IT, data science, and research careers.

Summary:
Unit 6 emphasizes learning beyond the classroom by exposing students to current
trends through expert lectures, seminars, and webinars.
It highlights the role of algorithms in AI, ML, Cryptography, Cloud, and Big Data, making
learners industry-ready.