Comprehensive notes, MCQs, and Short Questions for Chapter 3 Algorithms and Problem Solving. Covers computational problems, searching/sorting algorithms, complexity analysis, and problem-solving strategies.
Definition: A problem that can be solved by a computer using a step-by-step method (algorithm). It consists of Input, Process (Algorithm), and Output.
Classification:
- Decision Problems: Answer is Yes/No (e.g., Is number even?).
- Search Problems: Finding a value in a dataset (e.g., Finding a name in a list).
- Optimization Problems: Finding the best solution (e.g., Shortest path).
- Counting Problems: Counting number of solutions (e.g., Number of ways to arrange books).
Definition: A set of well-defined instructions to solve a problem. Like a recipe for a computer.
Properties:
- Input/Output: Defined inputs and outputs.
- Definiteness: Steps must be clear.
- Effectiveness: Steps must be feasible.
- Finiteness: Must stop after a finite number of steps.
Linear Search: Checks each element one by one. Simple but slow for large lists. Complexity: O(n).
Binary Search: Works on sorted lists. Divides the list in half repeatedly. Much faster. Complexity: O(log n).
Mechanism: Repeatedly swaps adjacent elements if they are in the wrong order. The largest element 'bubbles' to the top in each pass.
Complexity: O(n^2). not efficient for large datasets.
Time Complexity: How runtime increases with input size.
- O(1): Constant time.
- O(n): Linear time.
- O(log n): Logarithmic time.
- O(n^2): Quadratic time.
Space Complexity: How much memory is needed.
Class P (Polynomial): Problems solvable efficiently by computer (e.g., Sorting).
Class NP (Nondeterministic Polynomial): Problems where a solution can be verified efficiently, but finding it might be hard (e.g., Sudoku).
NP-Hard & NP-Complete: Extremely hard problems. If one NP-Complete problem is solved efficiently, all NP problems can be.
Divide and Conquer: Break problem into subproblems (e.g., Merge Sort).
Greedy Algorithm: Make the best local choice at each step (e.g., Coin Change).
Dynamic Programming: Store results of subproblems to avoid re-computation (e.g., Fibonacci).
Backtracking: Try possibilities and backtrack if a path fails (e.g., Maze, N-Queens).