Comprehensive notes, MCQs, and Short Questions for Chapter 3 Algorithms and Problem Solving. Covers Computational Problems, Algorithm Design (Divide & Conquer, Greedy, DP), Sorting, and Complexity.
Definition: A problem that can be solved by a computer using a step-by-step method (algorithm).
Components:
1. Input: Data given to the computer.
2. Process: The algorithm or set of steps.
3. Output: The final result.
Types:
- Decision Problems: Answer is Yes/No (e.g., Is number even?).
- Search Problems: Find a value in a dataset (e.g., specific ID in a list).
- Optimization Problems: Find the best solution (e.g., Shortest path).
- Counting Problems: Count outcomes (e.g., Number of ways to arrange books).
Divide and Conquer: Break a big problem into smaller sub-problems, solve them, and combine results (e.g., Merge Sort).
Greedy Algorithms: Make the best choice at each step, hoping for the global optimum (e.g., Coin Change problem).
Dynamic Programming (DP): Break problem into overlapping sub-problems and store results to avoid redundant work (e.g., Fibonacci sequence).
Backtracking: Try different options step-by-step and backtrack if a path fails (e.g., N-Queens problem, Sudoku).
Bubble Sort: Simple sorting algorithm. Compares adjacent elements and swaps them if they are in the wrong order. Repeats until sorted.
Time Complexity: O(n²) - Slow for large datasets.
Space Complexity: O(1).
Merge Sort: A Divide and Conquer algorithm. Splits list into halves, sorts them, and merges them.
Time Complexity: O(n log n) - Much faster.
Linear Search: Checks each item one by one. Simple but slow. Time: O(n).
Binary Search: Divide and conquer approach. Requires sorted list. Checks middle element, then eliminates half the list. Time: O(log n).
Time Complexity: How runtime increases with input size. Measured in Big O Notation:
- O(1): Constant time (Best).
- O(log n): Logarithmic (Very fast, e.g., Binary Search).
- O(n): Linear (e.g., Linear Search).
- O(n²): Quadratic (Slow, e.g., Bubble Sort).
Space Complexity: How much memory is needed.
Class P: Problems solvable in polynomial time (efficiently solvable).
Class NP: Problems where a solution can be verified quickly, but finding it might be hard.
NP-Complete: The hardest problems in NP (e.g., Knapsack Problem, Traveling Salesman). If one is solved efficiently, all NP problems are solved.