Scribd
Upload
18 views4 pages

Complete Algorithm Guide

The document provides a comprehensive guide to algorithms, defining them as finite sets of instructions for specific tasks with properties like input, output, and effectiveness. It categorizes algorithms into types such as brute force, greedy, and dynamic programming, and discusses time and space complexity using Big-O notation. Additionally, it covers sorting and searching algorithms, recursion, backtracking, and graph algorithms, highlighting their applications and characteristics.

Uploaded by

rounaksingh11250
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
18 views4 pages

Complete Algorithm Guide

The document provides a comprehensive guide to algorithms, defining them as finite sets of instructions for specific tasks with properties like input, output, and effectiveness. It categorizes algorithms into types such as brute force, greedy, and dynamic programming, and discusses time and space complexity using Big-O notation. Additionally, it covers sorting and searching algorithms, recursion, backtracking, and graph algorithms, highlighting their applications and characteristics.

Uploaded by

rounaksingh11250
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Complete Guide to Learning Algorithms

1. Introduction to Algorithms

An algorithm is a finite set of well-defined instructions for accomplishing a specific task. It takes an input,

processes it, and produces an output.

Properties of Algorithms:

- Input: Zero or more inputs.

- Output: At least one output.

- Definiteness: Clear and unambiguous steps.

- Finiteness: Must terminate after a finite number of steps.

- Effectiveness: Each operation must be basic enough to be done.

Example: Algorithm to add two numbers:

1. Start

2. Input two numbers A and B

3. Add A and B, store in SUM

4. Output SUM

5. Stop

2. Types of Algorithms

1. Brute Force Algorithm

2. Greedy Algorithm

3. Divide and Conquer Algorithm

4. Dynamic Programming Algorithm


Complete Guide to Learning Algorithms

5. Backtracking Algorithm

6. Randomized Algorithm

7. Recursive Algorithm

Each type is suited to specific kinds of problems.

3. Time and Space Complexity

Time Complexity: How the running time increases with input size.

Space Complexity: How much memory is required as input size increases.

Big-O Notation:

- O(1): Constant time

- O(n): Linear time

- O(log n): Logarithmic time

- O(n^2): Quadratic time

Example: Binary search - O(log n)

4. Sorting Algorithms

- Bubble Sort: O(n^2)

- Selection Sort: O(n^2)

- Insertion Sort: O(n^2)

- Merge Sort: O(n log n)


Complete Guide to Learning Algorithms

- Quick Sort: O(n log n)

- Heap Sort: O(n log n)

Each has its own use-cases, advantages, and drawbacks.

5. Searching Algorithms

- Linear Search: O(n)

- Binary Search: O(log n) [requires sorted array]

Binary Search Pseudocode:

1. Set low = 0, high = n-1

2. While low <= high:

- mid = (low + high) // 2

- if A[mid] == target: return mid

- if A[mid] < target: low = mid + 1

- else: high = mid - 1

3. Return -1

6. Recursion and Backtracking

Recursion: A function calling itself.

Backtracking: Try all possibilities, backtrack if a solution fails.

Used in: N-Queens, Sudoku, Subset Sum, etc.


Complete Guide to Learning Algorithms

Base Case and Recursive Case are essential.

7. Dynamic Programming

Solves problems by breaking them into overlapping subproblems.

Memoization: Top-down approach.

Tabulation: Bottom-up approach.

Used in: Fibonacci, Knapsack, Longest Common Subsequence.

8. Graph Algorithms

- BFS (Breadth-First Search)

- DFS (Depth-First Search)

- Dijkstras Algorithm (Shortest Path)

- Kruskals and Prims (Minimum Spanning Tree)

- Topological Sort

Graphs can be represented as adjacency list or matrix.

You might also like