Introduction to Algorithms

# CHAPTER 1

Introduction to Algorithms #

1. Introduction #

2. Learning Objectives #

• Define what an algorithm is in the context of computer science.

• Identify the five absolute characteristics of a valid algorithm.

• Trace the standard Algorithm Lifecycle.

• Understand the critical role of algorithms in modern software engineering.

3. What is an Algorithm? #

Algorithms are language-agnostic. You can design an algorithm on a whiteboard using simple English (Pseudo-code), and then translate that exact same mathematical logic into C, Java, Python, or JavaScript. The code changes, but the algorithm remains identical.

4. Characteristics of Algorithms #

1. 1. Input: It must accept zero or more well-defined inputs.

1. 2. Output: It must produce at least one clear, measurable output.

1. 3. Definiteness (Unambiguous): Every single step must be mathematically precise. A computer cannot process "add a little bit of sugar." It requires "add exactly 5 grams."

1. 4. Finiteness: The algorithm MUST eventually terminate. If a while loop runs infinitely forever, it is physically not an algorithm.

1. 5. Effectiveness: The steps must be basic enough that they can, in principle, be carried out by a human with a pencil and paper in a finite amount of time.

5. Why Algorithms Matter #

6. The Algorithm Lifecycle #

1. 1. Problem Definition: Understand the input and the required output.

1. 2. Design Strategy: Choose a mathematical approach (e.g., Divide and Conquer, Greedy).

1. 3. Draft Pseudo-code: Write the logic on a whiteboard.

1. 4. Complexity Analysis: Mathematically prove how fast it will run (Big O Notation).

1. 5. Implementation: Translate the pseudo-code into Python or C++.

1. 6. Testing & Optimization: Run edge cases and fix bugs.

7. Real-World Applications #

• Google Search: Uses the PageRank algorithm to sort billions of web pages in milliseconds based on relevance and authority.

• GPS Navigation (Google Maps): Uses Dijkstra's Shortest Path algorithm to find the absolute fastest physical route between two cities.

• E-Commerce: Amazon uses Collaborative Filtering algorithms to recommend products ("Customers who bought this also bought...").

• Cryptography: WhatsApp encrypts messages using RSA cryptographic algorithms to ensure mathematical security.

8. Mini Project: Daily Task Scheduling Algorithm #

// Pseudo-code Algorithm
1. START
2. ACCEPT an Array of Tasks.
3. IF the Array is empty, PRINT "You are free!" and STOP.
4. SORT the Array so the highest priority task is at Index 0.
5. EXTRACT the task at Index 0.
6. PRINT "Executing: " + task name.
7. REPEAT step 3 until all tasks are finished.
8. END

9. Code Examples: The Simplest Algorithm (Sum of Two Numbers) #

// C Implementation
#include <stdio.h>

int add_numbers(int a, int b) {
    int sum = a + b;
    return sum;
}

int main() {
    printf("Sum: %d\n", add_numbers(5, 10)); // Output: 15
    return 0;
}

// C++ Implementation
#include <iostream>
using namespace std;

int addNumbers(int a, int b) {
    return a + b;
}

int main() {
    cout << "Sum: " << addNumbers(5, 10) << endl; // Output: 15
    return 0;
}

// Java Implementation
public class Main {
    public static int addNumbers(int a, int b) {
        return a + b;
    }

    public static void main(String[] args) {
        System.out.println("Sum: " + addNumbers(5, 10)); // Output: 15
    }
}

# Python Implementation
def add_numbers(a, b):
    return a + b

print(f"Sum: {add_numbers(5, 10)}") # Output: 15

10. Complexity Analysis Basics #

• Time Complexity: O(1) Constant Time. Adding two numbers takes the CPU exactly 1 instruction, regardless of how large the numbers are.

• Space Complexity: O(1) Constant Space. We only store the result in one variable, requiring negligible RAM.

11. Best Practices #

• Plan Before You Type: Never open an IDE and start typing for complex logic. Grab a pen and paper. Draw the algorithm visually. The code is merely a translation of the drawing.

12. Common Mistakes #

• Ignoring Edge Cases: A naive division algorithm return a / b works flawlessly until the user inputs b = 0. The algorithm will crash the system. A robust algorithm always explicitly handles extreme, unexpected, or zero-value inputs.

13. Exercises #

1. 1. Write a pseudo-code algorithm that takes an array of temperatures and outputs the highest temperature found.

1. 2. Does an algorithm require a computer to be executed? Why or why not?

14. MCQs with Answers #

15. Interview Preparation #

• *Conceptual:* "What is the primary difference between a Data Structure and an Algorithm?" *(Answer: A Data Structure is the physical or logical architecture used to organize data in RAM. An Algorithm is the step-by-step mathematical operation applied to that data. They are symbiotic; a great algorithm requires the correct data structure to function).*

16. FAQs #

17. Summary #

18. Next Chapter Recommendation #