Algorithm_Unit1 of Information Technology and Computer

DAA

1. Unit 1: Introduction to Algorithms Course: Design and Analysis of Algorithms (Anna University) Unit 1: Introduction

2. Notion of an Algorithm - A well-defined computational procedure. - Input → Output via finite steps. Characteristics: • Input • Output • Definiteness • Finiteness • Effectiveness

3. Fundamentals of Algorithmic Problem Solving Steps: 1. Understand the problem 2. Identify input and output 3. Design a strategy 4. Formulate algorithm 5. Verify correctness 6. Analyze efficiency

4. Important Problem Types - Sorting (e.g., Merge Sort, Quick Sort) - Searching (e.g., Binary Search) - Graph Algorithms (e.g., BFS, DFS) - Numerical Problems - Combinatorial Problems - String Matching Problems

5. Analysis of Algorithm Efficiency - Time Complexity: Measures running time - Space Complexity: Measures memory usage - Types: Best, Average, Worst Case - Performance depends on input size (n)

6. Analysis Framework - Define the input size (n) - Identify the basic operation - Count how many times it executes - Determine growth function T(n)

7. Asymptotic Notations Used to describe the running time: - Big O (O): Upper bound (Worst Case) - Omega (Ω): Lower bound (Best Case) - Theta (Θ): Tight bound (Average Case) Properties: Transitive, Symmetric, Reflexive

8. Empirical Analysis - Measure actual running time - Tools: Stopwatch, Timer, Profilers - Run on different inputs and compare

9. Mathematical Analysis Recursive Algorithms: - Use Recurrence Relations - Solved using: Substitution, Recursion Tree, Master Theorem Non-Recursive: - Use loop counting method

10. Visualization Techniques - Flowcharts - Dry Run Tables - Recursion Trees - Animation Tools (e.g., VisuAlgo, Python Tutor)