Algorithm Fundamentals – Detailed Lecture Notes

An algorithm is a finite, ordered sequence of well-defined instructions that solves a problem or accomplishes a task.
- Metaphor: just like a recipe in cooking—each step is followed in order to obtain the desired dish.
Must terminate after a finite number of steps (guaranteed completion).
Forms the bridge where theory meets practice in computer science.
Core attributes (to be covered later under “Characteristics of an Algorithm”):
- Finiteness
- Definiteness / Unambiguity
- Input (zero or more)
- Output (at least one)
- Effectiveness (each instruction basic enough to be executed exactly & in finite time)

In computing, multiple algorithms often solve the same problem; quality varies.
Analysis lets us compare options and choose the most efficient & effective solution.
Especially vital when dealing with large data volumes—inefficiency scales badly.
Two core evaluation dimensions:
- Time Complexity – how quickly an algorithm runs (growth rate of operations).
- Space Complexity – how much memory it uses.
Goal: deliver a solution that is correct and efficient.

Time Complexity
- Measures algorithmic running time relative to input size $n$ .
- Expressed using asymptotic notation (e.g., $O(n)$ linear, $O(n \log n)$ log-linear).
- Gives an upper bound on growth, independent of machine speed.
Space Complexity
- Measures additional memory consumed by the algorithm versus input size.
- E.g., in-place sort uses $O(1)$ extra space, while mergesort uses $O(n)$ .
Analytical focus ("a-priori analysis"): estimate these metrics before writing or running code.

Divide & Conquer
- "Chop-chop the problem." Break a large problem into smaller, manageable sub-problems → solve each → combine results.
- Classic examples: mergesort, quicksort, binary search.
- Benefits: parallelism potential, clearer reasoning, often yields $O(n \log n)$ time improvements.
Iterative Approach
- Repeat a set of instructions until a condition is satisfied.
- Metaphor: looping through an array to find the maximum value.
- Often uses explicit loops (for/while) and mutable state.
Recursive Approach
- Function calls itself on smaller input until reaching a base case.
- Often mirrors divide-and-conquer conceptually.
Re-using Known Algorithms / Pattern Recognition
- If a new problem resembles a solved one, adapt the proven algorithm instead of reinventing.
- Saves time and leverages vetted efficiency.

Considered the most critical phase in any algorithmic project.
Analogy: drawing a map before the journey—without it, you risk going the wrong way.
Activities:
- Clearly define the goal and desired outputs.
- Gather requirements, constraints, resources, & assumptions.
- Identify edge cases & success criteria.
Outcome: a solid foundation enabling an effective design; you cannot craft a good algorithm for a problem you don’t fully understand.

Real-world workflow often revisits earlier stages (e.g., optimization may reveal need for redesign).

Builds upon foundational knowledge from CC104 (earlier course): theoretical definitions now move to actionable practice.
Relates to software engineering phases (requirements → design → code → test).
Time & space complexity link directly to hardware realities: CPU cycles, cache sizes, RAM limits.

Efficiency as responsibility: wasting compute cycles = wasting energy & money.
Scalability ethics: poorly chosen algorithms may exclude users on lower-resource devices.
Transparency: clear pseudocode & documentation help others audit for fairness & correctness.

Upcoming slides will illustrate the full 9-step process by designing a mini calculator.
Will cover: requirement gathering (supported operations), algorithm choice (e.g., parsing expression), implementation, testing, optimization, and documentation.