CS50 Lecture - Week 3: Algorithms and Implementation

Key Themes

• Focus on algorithms and implementation instead of new syntax.
• Understanding how to think algorithmically.
• Importance of dividing and conquering problems.

Review of Algorithms from Previous Weeks

• Phone book algorithms for searching:
  • One page at a time: Linear (1:1 slope).
  • Two pages at a time: Faster but linear (2:1 slope).
  • Binary search: Logarithmic (halving the problem size).

Attendance Exercise

• Demonstrated dividing and conquering by counting attendees using an algorithm that halves each step.
• Attendees stood, paired, summed numbers, and sat down if part of a pair.

Algorithms Explanation

• Algorithms allow mapping problem pieces to code.
• Search for numbers using arrays (similar to gym lockers analogy).

Search Algorithms

1. Linear Search

• Search each element one by one.
• Pseudocode: For each element in array: If element == search_term: Return true Return false
• Efficiency: O(n) in worst case, Omega(1) in best case if lucky.

2. Binary Search

• Requires sorted input.
• Start in the middle, decide to search left or right half.
• Pseudocode: If middle_element == search_term: Return true ElseIf search_term < middle_element: Search left half Else: Search right half
• Efficiency: O(log n) due to halving.

Introduction to Sorting Algorithms

Selection Sort

• Repeatedly find the smallest element and place it in order.
• Efficiency: O(n²), Omega(n²), and Theta(n²).
  • Inefficient because it consistently checks all elements.

Bubble Sort

• Compare adjacent elements and swap if out of order, repeat.
• Efficiency: O(n²), Omega(n) if no swaps needed in a pass.

Merge Sort

• Uses recursion and divide and conquer.
• Steps:
  1. Sort the left half.
  2. Sort the right half.
  3. Merge sorted halves.
• Efficiency: O(n log n) and Omega(n log n), Theta(n log n).

Recursion

• Definition: Function that calls itself.
• Useful for problems like sorting and searching.
• Examples include binary search and merge sort.

Practical Implementations

• Demonstrated search and sorting algorithms using number arrays and volunteers.
• Highlighted importance of efficiency in algorithm design.

Key Takeaways

• Algorithm efficiency is crucial in software design.
• Understanding the order of growth (Big-O notation) helps assess performance.
• Merge sort provides a more efficient sorting method compared to bubble and selection sort due to its divide and conquer approach.