CS50x 2026 - Lecture 3 - Algorithms

Introduction

This tutorial covers the fundamental concepts of algorithms as presented in CS50's Lecture 3. It will guide you through searching algorithms, sorting techniques, and the principles of recursion, providing a solid foundation for understanding how algorithms work in computer science.

Step 1: Understanding Searching Algorithms

Searching algorithms help you find specific data within a collection.

Key Searching Techniques

• Linear Search

  • Sequentially checks each element until the desired element is found or the list ends.
  • Best for small or unsorted datasets.

• Binary Search

  • Efficiently finds an element in a sorted array by repeatedly dividing the search interval in half.
  • Requires the dataset to be sorted beforehand.

Practical Advice

• When working with large datasets, opt for binary search to reduce the time complexity from O(n) to O(log n).

Step 2: Analyzing Running Time

Understanding the efficiency of algorithms is crucial.

Measuring Efficiency

• Use Big O notation to describe the running time of an algorithm relative to the input size.
• Common complexities include:
  • O(1): Constant time
  • O(n): Linear time
  • O(log n): Logarithmic time
  • O(n²): Quadratic time

Practical Advice

• Analyze your algorithm's efficiency to determine its scalability.

Step 3: Implementing Searching in Code

You can implement searching algorithms in C.

Example Code for Linear Search

int linear_search(int array[], int size, int target) {
    for (int i = 0; i < size; i++) {
        if (array[i] == target) {
            return i; // Return the index if found
        }
    }
    return -1; // Return -1 if not found
}

Example Code for Binary Search

int binary_search(int array[], int size, int target) {
    int low = 0;
    int high = size - 1;

    while (low <= high) {
        int mid = (low + high) / 2;
        if (array[mid] < target) {
            low = mid + 1;
        } else if (array[mid] > target) {
            high = mid - 1;
        } else {
            return mid; // Return the index if found
        }
    }
    return -1; // Return -1 if not found
}

Step 4: Exploring Sorting Algorithms

Sorting algorithms arrange data in a specific order, which can enhance searching efficiency.

Key Sorting Techniques

• Selection Sort

  • Repeatedly selects the minimum element from the unsorted portion and moves it to the sorted portion.
  • Time complexity: O(n²).

• Bubble Sort

  • Repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order.
  • Time complexity: O(n²).

• Merge Sort

  • Divides the array into halves, sorts them, and merges them back together.
  • Time complexity: O(n log n).

Practical Advice

• For larger datasets, prefer Merge Sort or other more efficient algorithms over Selection or Bubble Sort.

Step 5: Understanding Recursion

Recursion is a method where a function calls itself to solve smaller instances of the same problem.

Example Code for Recursive Function

int factorial(int n) {
    if (n <= 1) {
        return 1; // Base case
    }
    return n * factorial(n - 1); // Recursive case
}

Practical Advice

• Use recursion sparingly, as it can lead to high memory usage due to function call stacks.

Conclusion

In this tutorial, we've covered essential algorithms including searching and sorting techniques, and introduced the concept of recursion. Understanding these principles is vital for efficient programming and problem-solving in computer science. For further learning, consider implementing these algorithms in different programming problems or exploring more complex data structures.