Week 3 Lecture: Efficiency and Data Structures

Efficient Algorithms

• In week zero, we discussed algorithms intuitively, like searching a phone book.
• Today, we formalize ideas with code and evaluate algorithm efficiency.

Linear and Binary Search

• Linear Search: Check each item from left to right.
  • Worst case: If the item is the last one.
• Binary Search: Divide and conquer by checking the middle first.
  • Requires sorted data for efficiency.

Analyzing Efficiency

• Big O Notation: Describes an upper bound on algorithm performance.
  • Linear Search: O(n) in worst case.
  • Binary Search: O(log n) in worst case, O(1) in best case.
• Omega Notation: Describes a lower bound.
  • Best case for both searches could be Omega(1) if found immediately.

Implementing Search in C

• Arrays can represent data like lockers or phone book entries.
• Searching can be done using loops to iterate over elements.
• Code Example: Implementing linear search in C using loops and arrays.
• String Comparison: strcmp in C is used for comparing strings instead of ==.

Data Structures and Memory

• Arrays: Contiguous memory for multiple values of the same type.
• Strings: Arrays of characters ending with a null terminator (\0).
• Encapsulate related data using structures to avoid erroneous coding practices.

Structs in C

• Defining Structs: Create custom data types to bundle related information.
• Example: Define a person struct to hold both a name and a number.
• Usage: Arrays of structs can organize complex data like a phone book.

Debugging and Tools

• Debugging Techniques: Use printf for simple debugging, debug50 for step-by-step execution.
• Segmentation Faults: Often caused by accessing memory out of bounds.

Libraries and Functions

• Standard Libraries: Functions like strlen, toupper, and islower help manipulate strings.
• Command Line Arguments: Pass information to programs using argc and argv.

Problem Solving with Sorting

• Sorting can make search more efficient but requires its own algorithm.
• Sorting Problem: Input is an unordered list, output is a sorted list.
• Consider whether the time to sort is justified by the need for fast searching.

This lecture covers the foundations of algorithm efficiency, data structures in C, and introduces the complexities of sorting data. The key takeaway is the balance between time spent sorting data and the benefits gained in search performance.