Logo CodeWithAnkit

Basic Concepts of Algorithms

1. Definition of Algorithm

An algorithm is a step-by-step procedure used to solve a problem. It takes input, processes it, and produces the desired output.

Algorithms are the foundation of programming and are used in solving real-world computational problems efficiently.

2. Characteristics of Algorithm

  • Input: Accepts zero or more inputs
  • Output: Produces at least one result
  • Definiteness: Each step must be clear and unambiguous
  • Finiteness: Must terminate after a finite number of steps
  • Effectiveness: Steps must be simple and feasible

3. Pseudo Code & Control Structures

Pseudo code is a simple way of writing algorithm logic using plain English-like statements.

Example (If-Else):

IF number > 0
  PRINT "Positive"
ELSE
  PRINT "Negative"
END IF

Example (Loop):

FOR i = 1 TO n
  PRINT i
END FOR

Time Complexity:

  • Sequence → O(1)
  • Loop → O(n)
  • Nested Loop → O(n²)

4. Sorting Algorithms

Sorting algorithms arrange data in a particular order (ascending or descending).

  • Insertion Sort: Inserts elements at correct position
    Best: O(n), Worst: O(n²)
  • Selection Sort: Selects minimum element each time
    Time Complexity: O(n²)
  • Bubble Sort: Swaps adjacent elements
    Best: O(n), Worst: O(n²)
  • Heap Sort: Uses heap data structure
    Time Complexity: O(n log n)

5. Time & Space Complexity

  • Time Complexity: Measures how execution time grows with input size
  • Space Complexity: Measures memory used by the algorithm
  • Helps in choosing the most efficient algorithm

6. Asymptotic Notations

Used to analyze performance of algorithms for large inputs.

  • Big-O (O): Represents worst case
  • Omega (Ω): Represents best case
  • Theta (Θ): Represents average case

UNIT - 2

Unit 2: Divide & Conquer and Greedy Method

Divide and Conquer Technique

Binary Search

Works on sorted array. Divide array into halves.

Steps:

  1. Find middle element
  2. If key == mid → return
  3. If key < mid → search left
  4. If key > mid → search right

Time: O(log n)

Maximum & Minimum

Divide array into parts and compare results.

Steps:

  1. Divide array into two halves
  2. Find max & min of both halves
  3. Compare results

Merge Sort

Steps:

  1. Divide array into halves
  2. Sort each half recursively
  3. Merge sorted halves

Time: O(n log n)

Quick Sort

Steps:

  1. Select pivot
  2. Partition array
  3. Apply recursively

Best: O(n log n), Worst: O(n²)

Strassen’s Matrix Multiplication

Efficient matrix multiplication using divide & conquer.

Steps:

  1. Divide matrices into sub-matrices
  2. Compute 7 multiplications
  3. Combine results

Time: O(n^2.81)

Greedy Method

Greedy algorithm selects the best choice at each step without considering future consequences.

Knapsack Problem

Steps:

  1. Calculate profit/weight ratio
  2. Sort items
  3. Pick highest ratio first

Type: Fractional

Activity Selection

Steps:

  1. Sort by finish time
  2. Select first activity
  3. Pick next non-overlapping

Job Sequencing

Steps:

  1. Sort jobs by profit
  2. Schedule within deadline

Huffman Coding

Steps:

  1. Create nodes of frequency
  2. Combine lowest frequencies
  3. Build tree

Travelling Salesman

Find shortest route visiting all cities once.

Optimal Storage on Tapes

Store programs in increasing order of length.