CS50 Lecture Notes - Week 3

Introduction

• Focus: Algorithms (inputs transformed into outputs)
• Memory: Examining how algorithms utilize memory for efficient computation
• Running Time: Understanding big O notation for analyzing algorithm efficiency

Memory Recap

• RAM: Random Access Memory, a grid-like structure storing bits and bytes
• Arrays: Contiguous memory storage for variables of the same type
• Zero-Indexed: Arrays start counting from 0

Search Algorithms

Linear Search

• Definition: A search algorithm that checks each element in sequence
• Big O Notation: O(n) - worst case, iterate through all elements
• Omega Notation: Ω(1) - best case, find the element immediately
• Implementation: Simple loop through array elements
• Use Case: When data isn't sorted

Binary Search

• Definition: A search algorithm that divides the data in half each step
• Precondition: Data must be sorted
• Big O Notation: O(log n) - efficient as it halves the dataset each iteration
• Omega Notation: Ω(1) - best case, find the element immediately
• Implementation: Compare middle element, decide to search left or right
• Use Case: Efficient for large, sorted datasets

Efficiency Analysis

• Big O: Describes upper bound of running time
• Big Ω (Omega): Describes lower bound (best case) running time
• Big Θ (Theta): When upper and lower bounds are the same

Sorting Algorithms

Selection Sort

• Definition: Repeatedly finding the smallest element and swapping it into place
• Big O Notation: O(n²) - checks each remaining element for smallest
• Omega Notation: Ω(n²) - no benefit from already sorted data
• Implementation: Find smallest, swap, repeat
• Efficiency: Poor for large datasets due to quadratic time complexity

Bubble Sort (Previewed)

• Definition: Repeatedly step through the list, compare adjacent elements and swap if needed
• Implementation: Will be covered in more detail

Pseudocode and Implementation

• Linear Search Pseudocode: Loop through array, check each element
• Binary Search Pseudocode: Check middle, decide left or right
• Selection Sort Pseudocode: Find minimum, swap, reduce problem size

Practical Applications

• Use Cases: Searching in phonebooks, databases, large datasets
• Design Decisions: Sorting first may not always be efficient, depends on frequency of searches

Conclusion

• Key Takeaways:
  • Sorting is a precondition for efficient searching with binary search
  • Linear search is less efficient but works on unsorted data
  • Efficiency measured in big O notation is crucial for large datasets

These notes summarize key points about algorithms and efficiency, using arrays and memory as fundamental concepts. They bridge theory with practical implementation, preparing for future problem-solving and coding challenges in CS50.