Choosing an Algorithm and Thinking About Efficiency

• Mapping a Problem to an Appropriate Algorithm

  • Take your problem and identify the suitable class of algorithms for
    it.

  • Understand the characteristics of each algorithm, including their
    
    efficiency.
    

    Understanding Efficiency

• Space Complexity

  • Computer Memory: How much memory does an operation require as afunction of its size?

  • Variables:

    • How do variables affect memory usage?

    • Are there any optimizations to reduce memory usage?

• Time Complexity

  • Running Time: How long does it take for the algorithm to complete?

  • Finding a Math Expression:

  • Derive an expression that describes the running time based on thenumber of inputs.

  • Identify the type of time complexity (e.g., linear, quadratic, exponential).

    • Number of Basic Steps:

  • Determine the number of basic steps required as a function of input size.

  • Understand how many steps are needed to solve the problem.

• Fundamental Difficulty

  • Assess the fundamental difficulty of the problem:

  • Is it hard? (e.g., NP-complete, easy)

  • How does this affect algorithm design?

• Input Size Considerations

  • Understanding Input Size:

    • Does input size depend on the specific problem?

    • Are inputs represented as integers, strings, or other data types?

    • How long is a list of data?

    • What is the number of bits in an integer representation?

• Basic Steps and Computational Complexity

  • Identifying Basic Steps:

  • Determine whether basic steps involve significant computation.

  • Are there built-in primitives that can simplify computations?

  • Consider arithmetic, comparison, memory operations, and random access model.

    • Counting Basic Steps:

    • What do you want to count? (Best Case, Worst Case, Expected Case)

    • Best Case: fastest, fewest steps

    • Worst Case: maximum number of steps

      • This is often the hardest case to analyze and may require assumptions about input distribution.

    • Expected Case: average running time

• Validation and Debugging

• Introduction

  Validation and debugging are essential components of software development. Validation helps increase confidence in the program's correctness by identifying potential issues, while debugging is the process of determining why the program is not working as expected.

• The Importance of Validation

• Validation is a process to uncover problems: It ensures that the program meets its specifications and works correctly.

• We can't be sure: No matter how thorough the testing process is, there's always a possibility that the program may contain bugs or errors that were not caught.

• Debugging

• Process of determining why the program is not working: It involves identifying the root cause of the problem and fixing it.

• Key aspects of debugging:

  • Identifying events leading to an error

  • Analyzing the code to understand what went wrong

• ### Best Practices for Writing Programs that Facilitate Validation and Debugging

1. Write your programs to facilitate validation and debugging: Make your code as modular, readable, and maintainable as possible.

2. Use assert statements: They provide a way to verify that the program is working correctly by checking assumptions at runtime.

3. Write specifications: Clearly define what you want your program to do and how it should behave under different scenarios.

4. Modularize: Break down your program into smaller, independent modules or functions to make it easier to test and debug each component separately.

• Testing

• Test input/output pairs against a specification: This ensures that the program works correctly for a given set of inputs.

• Units testing:

  • Validate each piece of the program: Functions and classes

  • Test small, independent components to ensure they work correctly before integrating them into the larger program

• Integration testing: Verify that the entire system works as expected by combining multiple units or functions.

• The Challenges of Exhaustive Testing

• With billions of possible combinations, exhaustive testing is often impossible.

• Look at something small: Focus on testing individual components or small parts of the program before moving on to larger sections.

• Creating an Effective Test Suite

• Strive for a test suite that's:

  • Small enough: Manageable and testable within a reasonable amount of time

  • Large enough: Provides some confidence in the program's correctness