What is an Algorithm
- An algorithm is a step-by-step procedure to solve a specific task
- Algorithms address a general, well-defined problem by taking various instances as input and transforming them into the desired output
Problem Vs. Instance
- it is crucial to distinguish between a problem (the general description) and an instance (a specific case)
Algorithm Design Philosophy
- Modeling: Abstract a real-world problem into a clean problem suited for algorithmic solutions
- Reasoning about Correctness: Correct algorithms must align with well-defined problems
Algorithm Representation
- Algorithms can be expressed in:
- English - easy to write, but less precise
- Pseudocode - A blend of plain language and code syntax
- Programming Language - Precise but harder to understand
- Clear representation helps communicate the core idea of an algorithm effectively
Take-Home Lessons
-
The Heart of an Algorithm is its Idea : If the core idea is unclear, the representation is too complex
-
Correctness Requires Careful Demonstration : The correctness of an algorithm must be demonstrated systematically, especially with complex algorithms
-
Simplify Input Instances : Narrowing problem instances ( e.g. limiting to trees or lower dimensions) helps ensure algorithms are both correct and efficient
-
Counterexamples as a Tool : Finding instances where an algorithm fails is a key way to prove it incorrect