CS50 Lecture Notes - Week 3

Recap of Week 0

• Representation of Information: Discussed how information is represented in computers.
• Algorithms: Used examples like tearing a phone book to create algorithms.
• Efficiency: Focused on analyzing the efficiency of these algorithms.

Revisiting the Phone Book Example

• Algorithm Analysis:
  • Algorithm 1: One page at a time => Linear (O(n))
  • Algorithm 2: Two pages at a time => Still O(n)
  • Algorithm 3: Tearing in half => Logarithmic (O(log n))
• Efficiency Metrics: X-axis is problem size, Y-axis is time required.
• Importance of design and efficiency in algorithms.

Computer Memory

• Grid of Bytes: Inside your computer's memory (RAM), everything is stored in a grid of bytes.
• Abstracting Away Hardware: We look at memory as an array of bytes where each byte could store various data types (char, int, string).

Arrays and Indices

• Arrays allow storing sequences of elements (characters, integers).
• Indices: Used to access elements in the array starting from 0.
• Example of finding a value in an array through iterative checking.

Linear Search Algorithm

• Pseudocode: For each door from left to right, check if the value is behind the door.
• Step-by-Step Process: Open door, check value, repeat until found or end of array.
• Problem if using an else statement incorrectly: Could prematurely cancel search.
• Efficiency: O(n) in the worst case.

Binary Search Algorithm

• Example Demonstration: Volunteers dividing and conquering a sorted array to find a number.
• Pseudocode:
  • Search middle, if not middle, check if less or greater and continue.
  • Always dividing array in half until the value is found or array is empty.
• Efficiency: O(log n) in the worst case for sorted arrays.

Formalizing Algorithm Efficiency

• Big O Notation: Used for analyzing the upper bound of an algorithm.
• Examples:
  • Linear Search is O(n)
  • Binary Search is O(log n)
• Graphical Representation: Showed how the shapes of these curves differ fundamentally.
• Lower Bound (Omega): Describes the best-case scenario of an algorithm.
• Theta Notation: When upper and lower bounds are the same.

Arrays of Strings

• Comparison of Strings: Using strcmp function for proper comparison.
• String Arrays as Phonebook: Demonstrated practical use with names and numbers.
• Segmentation Faults: Explained common reasons related to memory and array bounds.

Structs in C

• Data Structures: Introduced typedef struct to define new types in C.
• Example: Creating a person type with name and number fields.
• Usage Example: Building a phone book with an array of person structs.

Sorting Algorithms

Selection Sort

• Concept: Repeatedly finding the smallest element and moving to the sorted portion.
• Efficiency: O(n^2) in all cases (worst, best) since always scanning entire list.

Bubble Sort

• Concept: Repeatedly swapping adjacent elements if they are out of order.
• Efficiency: Also O(n^2) in worst case but can be optimized for best case already sorted (O(n)).

Merge Sort

• Concept: Divide and conquer by recursively splitting list into halves and then merging sorted halves.
• Efficiency: O(n log n) in both worst and best cases because dividing and merging are efficient.
• Implementation: Must use more memory for intermediate arrays.

Recursion

• Definition: Functions calling themselves with a base case to stop.
• Example Review: Recursive draw function for pyramid (base case when pyramid height is zero).
• Google's Recursion Easter Egg: Fun example of recursion in Google search.
• Merge Sort Using Recursion: Efficient sorting by recursively dividing the list and merging.

Efficiency Differences Visualized

• Comparison Video: Demonstrated visual differences in efficiency using actual sorting algorithms.
• Conclusion: Merge sort is more efficient than selection or bubble sorts for large data but requires more memory.

Summary & Final Thoughts

• Sorting and searching algorithms are foundational in computer science.
• Big O notation helps us understand and compare their efficiencies.
• Understanding algorithm efficiency and practical implementation can greatly improve performance in software.