Chapter 10

Chapter Overview

The chapter focuses on the fundamental concepts of algorithms, which serve as the ultimate backbone of computer science and software engineering. An algorithm is a precise, well-defined procedure that takes some input, processes it systematically through a sequence of logical operations, and produces a corresponding output to solve a computational problem.

Beyond simple step-by-step procedures, algorithmic problem solving forms the core of modern computational thinking. It enables software engineers to abstract complex real-world challenges into structured, computable models. From ancient mathematical procedures—such as Euclid’s algorithm for finding the Greatest Common Divisor (GCD)—to contemporary deep learning pipelines driving artificial intelligence, algorithms translate human problem-solving logic into execution pathways for hardware.

This chapter introduces students to the core concepts of algorithms, their classification, representations (flowcharts, pseudocode), methods of design, and formal techniques for analyzing algorithm performance using Time and Space Complexity.

---

Learning Objectives

By mastering this chapter, students will be able to:

• Understand the foundational concept of an algorithm and its role in computing and computational problem-solving.
• Identify and evaluate key characteristics of effective algorithms (Finiteness, Definiteness, Inputs, Outputs, Effectiveness, Generality).
• Learn about different types and paradigms of algorithms, including Deterministic vs. Non-Deterministic, Brute Force, Divide and Conquer, Greedy, and Dynamic Programming strategies.
• Master algorithm representation tools, including standard flowchart symbols, decision trees, and clean, language-independent pseudocode notation.
• Understand the structured steps in algorithm design, from initial problem abstraction to verification, testing, and dry runs.
• Analyze and compare algorithm performance using Big O notation for time and space complexities.
• Formulate efficient algorithms for standard searching (Linear, Binary Search) and sorting (Bubble, Selection, Insertion) tasks.

---

Important Concepts

What is an Algorithm?

An algorithm is a set of instructions that is used to solve a problem or perform a specific task. It is a well-defined procedure that takes some input and produces a corresponding output. Algorithms are used in various fields, including computer science, mathematics, operational research, quantitative finance, and engineering.

To be considered a valid, well-formed algorithm in computer science, a procedure must satisfy six essential properties:

+-----------------------------------------------------------------+
|                     ESSENTIAL CHARACTERISTICS                   |
+-----------------------------------------------------------------+
| 1. Input         : Zero or more well-defined inputs.           |
| 2. Output        : At least one clear, deterministic output.    |
| 3. Definiteness  : Every step is unambiguous and clear.         |
| 4. Finiteness    : Guaranteed to terminate after finite steps. |
| 5. Effectiveness : Operations are basic and executable.         |
| 6. Generality    : Solves a broad class of problem instances.   |
+-----------------------------------------------------------------+

1. Input: An algorithm must receive zero or more specified quantities as external inputs.
2. Output: It must produce at least one well-defined output representing the solution.
3. Definiteness: Each instruction must be clear, unambiguous, and precise. There should be no room for multiple interpretations.
4. Finiteness: An algorithm must terminate after a finite number of steps for all valid input cases. An infinite execution loop is an anti-pattern, not an algorithm.
5. Effectiveness / Feasibility: Every operation must be sufficiently basic that it can, in principle, be executed accurately in a finite amount of time using pencil and paper.
6. Generality: The algorithm must apply to any valid instance of the defined problem set, rather than being hardcoded for a single specific set of numbers.

Real-World Case Study: Automated Teller Machine (ATM) Cash Withdrawal

Consider an ATM processing a cash withdrawal request. The underlying algorithm:

• Input: User PIN, account identifier, requested withdrawal amount ($A$).
• Definiteness: Validates PIN via encrypted database query. Checks if $A \le \text{Account Balance}$ and $A \pmod{100} == 0$.
• Finiteness: Executes precisely 5 processing checks; if any fail, it aborts immediately with an error prompt.
• Output: Dispenses physical currency notes and prints a receipt balance statement.

---

Types of Algorithms

Algorithms are broadly classified based on their execution determinism and structural design paradigms.

1. Deterministic vs. Non-Deterministic Algorithms

• Deterministic Algorithms: These algorithms produce the exact same output for a given input every time they are executed under identical conditions. The step-by-step state transition is completely predictable.
  • Example: Binary Search, Euclid's GCD algorithm, Bubble Sort.
• Non-Deterministic Algorithms: These algorithms may produce different outputs or follow different internal state execution paths for the same input across multiple executions. They often rely on randomness, probabilistic heuristics, or parallel execution states.
  • Example: Randomized QuickSort (pivot selection is random), Genetic Algorithms for global optimization, Monte Carlo simulations.

2. Major Algorithmic Design Paradigms

Beyond determinism, practical software engineering categorizes algorithms by their strategy:

                  +-----------------------------------+
                  |   ALGORITHMIC DESIGN PARADIGMS    |
                  +-----------------------------------+
                                    |
     +-----------------+------------+------------+------------------+
     |                 |                         |                  |
[Brute Force]  [Divide & Conquer]             [Greedy]     [Dynamic Programming]
  Exhaustive     Split, Conquer,             Local Best        Store Subproblem
  Search         Combine Results             Choice             Results (Memo)

• Brute Force: Evaluates every possible candidate solution exhaustively until the correct solution is found. Simple to write, but highly inefficient ($O(2^n)$ or $O(n!)$).
• Divide and Conquer: Breaks a problem into smaller subproblems of the same type, solves them recursively, and combines their solutions.
  • Example: Merge Sort, Quick Sort, Binary Search.
• Greedy Strategy: Makes the locally optimal choice at each step with the hope of reaching a globally optimal solution.
  • Example: Dijkstra’s Shortest Path, Huffman Coding, Fractional Knapsack.
• Dynamic Programming (DP): Solves complex problems by breaking them down into overlapping subproblems, solving each subproblem once, and storing its answer in a lookup table (memoization/tabulation).
  • Example: Fibonacci sequence generation via memoization, Longest Common Subsequence (LCS).

---

Algorithmic Toolset: Representation Methods

Before converting logic into source code (like Python or C++), algorithms are designed and documented using high-level visual and textual tools.

A. Flowcharts

A flowchart is a pictorial representation of an algorithm using standard geometric shapes connected by directional arrows (flow lines).

Standard Flowchart Symbols Table

Symbol Shape	Technical Name	Primary Purpose / Function
Oval / Capsule	Start / End (Terminal)	Denotes the absolute beginning or conclusion of the process flow.
Parallelogram	Input / Output	Represents operations where data is read from external sources or printed.
Rectangle	Process	Represents calculations, variable assignments, and data manipulations.
Diamond	Decision / Condition	Represents logical conditional checks (True/False or Yes/No branching).
Circle	Connector	Connects different sections of a large flowchart on the same page.
Arrows	Flow Lines	Indicates the direction of execution logic between process steps.

B. Pseudocode

Pseudocode is an informal, high-level description of an algorithm intended for human reading rather than machine compilation. It uses structured programming constructs (e.g., IF-ELSE, FOR, WHILE) without strict syntax rules.

Example Pseudocode (Finding Maximum of Two Numbers):

BEGIN
    READ num1, num2
    IF num1 > num2 THEN
        SET max = num1
    ELSE
        SET max = num2
    ENDIF
    PRINT "Maximum Value is: ", max
END

---

Algorithm Design

Algorithm design is the systematic process of developing a new algorithm or modifying an existing one to solve a specific problem efficiently. It involves a multi-phase lifecycle:

+-------------------+      +-------------------------+      +-----------------------+
| 1. Problem        | ---> | 2. Input/Output         | ---> | 3. Algorithm          |
|    Definition     |      |    Analysis             |      |    Development        |
+-------------------+      +-------------------------+      +-----------------------+
                                                                        |
+-------------------+      +-------------------------+                  |
| 5. Implementation | <--- | 4. Testing, Dry Run   | <----------------+
|    & Code         |      |    & Evaluation         |
+-------------------+      +-------------------------+

1. Problem Definition: Clearly defining the scope, constraints, and operational goals of the problem to be solved without ambiguity.
2. Input and Output Analysis: Identifying the exact data types, structures, ranges, and formats of inputs provided and expected outputs.
3. Algorithm Development: Formulating step-by-step logic utilizing pseudocode, control structures, and functional decomposition.
4. Testing and Evaluation (Dry Run): Tracing the developed algorithm manually using sample trace tables and boundary test cases to catch logical bugs early.
5. Implementation & Refinement: Converting the pseudocode into optimized, readable target programming code (e.g., Python).

---

Algorithm Analysis

Algorithm analysis is the formal evaluation of the efficiency and computational resource requirements of an algorithm. It allows software architects to select the optimal algorithm for large dataset scales independent of hardware, compiler, or implementation language. Performance is assessed along two primary dimensions: Time Complexity and Space Complexity.

Asymptotic Notations

To describe how an algorithm's execution metrics grow as input size $n$ approaches infinity, we use mathematical asymptotic bounds:

• Big O ($\mathcal{O}$): Represents the Worst-Case time or space complexity (Upper Bound). It guarantees the algorithm will not take longer than this bound.
• Big Omega ($\Omega$): Represents the Best-Case time or space complexity (Lower Bound).
• Big Theta ($\Theta$): Represents the Average-Case / Tight Bound performance.

       Complexity Growth Rate Comparison (Fastest to Slowest)
  -----------------------------------------------------------------
  O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(2^n) < O(n!)
  Constant Logarithmic Linear Linearithmic Quadratic Exponential Factorial
  -----------------------------------------------------------------

---

Time Complexity

Time complexity is a measure of the total amount of computational execution time (measured as the number of primitive machine operations executed) an algorithm takes to complete as a function of the input size $n$.

Comparative Time Complexities of Fundamental Operations

• Constant Time $\mathcal{O}(1)$: Accessing an array element by index arr[i].
• Logarithmic Time $\mathcal{O}(\log n)$: Binary Search algorithm on a sorted array.
• Linear Time $\mathcal{O}(n)$: Linear Search across an unsorted list, finding min/max in an unstructured array.
• Linearithmic Time $\mathcal{O}(n \log n)$: Merge Sort, Heap Sort, Quick Sort (average case).
• Quadratic Time $\mathcal{O}(n^2)$: Bubble Sort, Selection Sort, Insertion Sort (nested iterations).
• Exponential Time $\mathcal{O}(2^n)$: Solving the Tower of Hanoi problem, Recursive calculation of Fibonacci numbers without memoization.

---

Space Complexity

Space complexity is a measure of the total amount of memory space required by an algorithm to run to completion as a function of the input size $n$.

Space complexity consists of two parts: $\text{Total Space Complexity} = \text{Fixed Auxiliary Space} + \text{Dynamic/Input Space}$

1. Fixed / Auxiliary Space: Memory used for constants, simple variables, fixed-size scalar variables, and instruction space that does not scale with input size.
2. Dynamic / Input Space: Memory allocated for input variables, dynamic data structures, and stack frame space generated by recursive calls.

Example: Bubble Sort sorts elements in-place, yielding an auxiliary space complexity of $\mathcal{O}(1)$, whereas Merge Sort requires creating auxiliary temporary arrays yielding $\mathcal{O}(n)$ auxiliary space.

---

Key Definitions

• Algorithm: A clear, well-defined sequence of computational instructions that takes input data and transforms it through structured processing into an accurate output.
• Deterministic Algorithm: An algorithm whose execution path and output are completely determined by its initial state and input parameters, producing identical results every run.
• Non-Deterministic Algorithm: An algorithm that can exhibit different behaviors across runs for identical inputs due to non-deterministic choice points or probabilistic steps.
• Time Complexity: A formal mathematical expression quantifying the growth rate of total operational execution steps as input scale $n$ increases.
• Space Complexity: A formal mathematical expression quantifying the growth rate of total dynamic memory utilized by an algorithm during execution.
• Big O Notation: A standard symbolic notation used to denote the mathematical upper bound (worst-case scenario) of an algorithm's resource consumption growth curve.
• Flowchart: A formal graphical diagram depicting the operational workflow, control logic, and sequence of steps within an algorithm.
• Pseudocode: An informal, machine-independent, human-readable specification of an algorithmic logic written in structured high-level natural language.
• Dry Run (Trace Table): A manual testing technique where a programmer walks through an algorithm line-by-line on paper, recording variable values at every execution state.
• Auxiliary Space: The extra temporary memory space allocated by an algorithm during execution, excluding the memory occupied by the initial input data itself.
• In-Place Sorting: A sorting algorithmic trait where output sorting is achieved by re-arranging the original input array in memory, requiring $\mathcal{O}(1)$ auxiliary space.
• Recursion: A programming technique where a function calls itself directly or indirectly to solve smaller instances of the same problem until reaching a terminal base case.

---

Important Terms

Term	Meaning & Detailed Operational Context
Big O Notation ($\mathcal{O}$)	A asymptotic notation describing the maximum theoretical upper bound of execution time or memory utilization for large $n$.
Algorithm Design	The engineering workflow of creating efficient computational workflows targeting specific functional outputs.
Problem Definition	The baseline phase specifying target requirements, functional parameters, pre-conditions, and post-conditions.
Input & Output Analysis	The explicit mapping of physical data representations, variable ranges, structures, and precise expected results.
Dry Run	A manual code trace executed by a programmer with sample data using a structured trace table to verify algorithm logic.
Infinite Loop	A fatal algorithmic flaw where the termination condition (finiteness) is never met, causing continuous execution.
Control Structure	Logical control blocks (Sequential, Selection/Conditional, Iteration/Loops) governing execution pathways.
Recursion Depth	The maximum dynamic call stack allocation level generated by nested self-referential function executions.

---

Important Formulas & Mathematical Frameworks

1. Mathematical Upper Bound Definition (Big O)

An algorithm $f(n)$ is in $\mathcal{O}(g(n))$ if and only if there exist positive real constants $c$ and $n_0$ such that: $f(n) \le c \cdot g(n) \quad \forall n \ge n_0$

2. Time Complexity Analysis of Nested Loops

For quadratic operations such as Bubble Sort, the total number of element comparisons $T(n)$ for an array of length $n$ is calculated as: $T(n) = (n - 1) + (n - 2) + (n - 3) + \dots + 1 = \sum_{k=1}^{n-1} k$ $T(n) = \frac{(n - 1) \cdot n}{2} = \frac{n^2 - n}{2} \implies \mathcal{O}(n^2)$

3. Binary Search Recurrence Relation

The work done in halved steps yields the recurrence relation: $T(n) = T\left(\frac{n}{2}\right) + \mathcal{O}(1)$ Solving via substitution yields: $n \to \frac{n}{2} \to \frac{n}{4} \dots \to \frac{n}{2^k} = 1 \implies 2^k = n \implies k = \log_2 n \implies T(n) = \mathcal{O}(\log_2 n)$

---

Diagrams (Structural Text Descriptions)

1. Flowchart Geometry & Connections

                     +-------------------+
                     |    [ Start ]      |  <-- Oval Terminal
                     +-------------------+
                               |
                               v
                     +-------------------+
                     | Read Input N, Key |  <-- Parallelogram (I/O)
                     +-------------------+
                               |
                               v
                     +-------------------+
                     | Set Index i = 0   |  <-- Rectangle Processing
                     +-------------------+
                               |
                               v
                     +-------------------+
            +------->|   Is i < N ?      |  <-- Diamond Decision
            |        +-------------------+
            |               /     \
            |         (Yes)/       \(No)
            |             v         v
            |    +----------------+  +-------------------+
            |    | Is Arr[i]==Key?|  | Print "Not Found" |
            |    +----------------+  +-------------------+
            |          /    \                  |
            |    (Yes)/      \(No)             v
            |        v        v          +-------------------+
            |  +----------+ +--------+   |     [ End ]       |
            |  |Print "Found"|| i = i+1|   +-------------------+
            |  +----------+ +--------+             ^
            |        |          |                  |
            |        v          +------------------+
            |    +-------+
            |    |[ End ]|
            |    +-------+
            |        ^
            +--------+

2. Comparative Growth Rates Graph

 Execution Steps
      ^
      |                                              /  O(2^n)
      |                                 .-----------'
      |                             . -'    /  O(n^2)
      |                         . -'    . -'
      |                     . -'    . -'   /  O(n log n)
      |                 . -'    . -'   . -'
      |             . -'    . -'   . -'   /  O(n)
      |         . -'    . -'   . -'   .-'
      |     . -'    . -'   . -'   . -'
      | . -'    . -'   . -'   . -'  /  O(log n)
      |----------------------------/--- O(1)
      +----------------------------------------------------> Array Size (n)

---

Real-Life Applications & Deep-Dive Case Studies

1. Web Search Engines (Google PageRank Algorithm)

Search engines deal with billions of web pages. Standard linear iteration over all pages for a query would be unusable due to slow speed.

• Mechanism: Google uses graph-based link-structure analysis combined with inverted indexing and distributed parallel computing paradigms (MapReduce).
• Impact: Queries yield results across billions of documents in fractions of a second ($< 0.2$ seconds).

2. Streaming Platform Recommendations (Collaborative Filtering)

Platforms like Netflix analyze massive multi-dimensional matrix datasets representing user watch histories, ratings, and skip patterns.

• Mechanism: Recommendation systems run non-deterministic, iterative machine learning algorithms (such as Matrix Factorization and K-Nearest Neighbors) to identify dynamic user-item affinity vectors.
• Impact: Provides personalized movie suggestions in real-time, driving high content engagement.

3. Online Banking & Cryptography (RSA Public Key Algorithm)

Securing online financial transactions relies on modular arithmetic and number theory algorithms.

• Mechanism: The RSA algorithm relies on the computational difficulty of prime factorization for large integers (e.g., 2048-bit numbers).
• Impact: While multiplying two large prime numbers takes fractions of a millisecond ($\mathcal{O}(1)$ practical operations), factoring their product back into primes without key knowledge takes thousands of computing years, protecting data against unauthorized access.

4. Route Navigation Systems (Dijkstra’s Shortest Path Algorithm)

Mapping platforms evaluate real-time traffic and road networks represented as weighted graphs.

• Mechanism: Modified versions of Dijkstra’s Algorithm, utilizing min-priority heaps, process location nodes to compute the minimum-cost route between source and destination.
• Impact: Updates optimal directions instantly when road closures or dynamic traffic delays occur.

---

Step-by-Step Problem Solving Strategies & Detailed Traces

Strategy 1: Tracing an Algorithm Using a Trace Table

A Trace Table is a structured analytical technique used to track variable value updates line-by-line during manual execution.

Problem: Trace the Bubble Sort Algorithm on Array arr = [5, 2, 8, 1]

Algorithm Pseudocode:

For i from 0 to N-2
    For j from 0 to N-i-2
        If arr[j] > arr[j+1] Then
            Swap arr[j] and arr[j+1]

Step-by-Step Execution Trace Table ($N = 4$):

Outer Pass ($i$)	Inner Index ($j$)	Element Comparisons (arr[j] vs arr[j+1])	Action Taken	Array State After Operation
Start	-	-	Initial Array	[5, 2, 8, 1]
i = 0	$j = 0$	$5 > 2$ (True)	Swap $5$ and $2$	[2, 5, 8, 1]
	$j = 1$	$5 > 8$ (False)	No Swap	[2, 5, 8, 1]
	$j = 2$	$8 > 1$ (True)	Swap $8$ and $1$	[2, 5, 1, 8]
i = 1	$j = 0$	$2 > 5$ (False)	No Swap	[2, 5, 1, 8]
	$j = 1$	$5 > 1$ (True)	Swap $5$ and $1$	[2, 1, 5, 8]
i = 2	$j = 0$	$2 > 1$ (True)	Swap $2$ and $1$	[1, 2, 5, 8]
Complete	-	-	Terminate	Sorted Array: [1, 2, 5, 8]

---

Strategy 2: Mathematical Proof of Binary Search Time Complexity

Theorem: Binary Search on a sorted array of length $n$ has a worst-case time complexity of $\mathcal{O}(\log_2 n)$.

Proof:

1. Let $n$ be the initial size of the sorted array search space.
2. In each iteration step $k$, the algorithm compares the target key with the middle element and divides the remaining search space strictly in half:
   • Step 0: $n$
   • Step 1: $\frac{n}{2}$
   • Step 2: $\frac{n}{2^2}$
   • Step $k$: $\frac{n}{2^k}$
3. In the worst-case scenario, searching continues until the remaining sub-array length is reduced to $1$ element: $\frac{n}{2^k} = 1$
4. Multiplying both sides by $2^k$: $n = 2^k$
5. Taking the base-2 logarithm ($\log_2$) on both sides: $\log_2(n) = \log_2(2^k)$ $\log_2(n) = k \cdot \log_2(2)$ $k = \log_2(n)$
6. Since each step involves $\mathcal{O}(1)$ comparison operations, the total execution upper bound is directly proportional to $k$: $\text{Total Operations } T(n) = \mathcal{O}(\log_2 n)$ Q.E.D.

---

Higher-Order Thinking Skills (HOTS) Questions

Question 1

An array contains $N$ sorted distinct elements. An engineer proposes using Linear Search over Binary Search because Linear Search is simpler to code. Evaluate this decision quantitatively for an array containing $1,048,576$ elements.

Solution / Answer:

1. Linear Search Worst-Case Analysis:
   • Linear Search evaluates elements sequentially starting from index $0$.
   • Maximum iterations required $= N = 1,048,576$ operations ($\mathcal{O}(N)$).
2. Binary Search Worst-Case Analysis:
   • Binary Search repeatedly halves the search space.
   • Maximum iterations required $= \lceil \log_2(1,048,576) \rceil = 20$ operations ($\mathcal{O}(\log_2 N)$).
3. Quantitative Comparison:
   • $\frac{\text{Linear Search Operations}}{\text{Binary Search Operations}} = \frac{1,048,576}{20} \approx 52,428$ times faster.
4. Conclusion: The engineer's decision is incorrect for large datasets. While code simplicity is a factor for small $N$, at $N = 10^6$, Binary Search reduces execution comparisons by $99.998\%$, making it necessary for high performance.

---

Question 2

Analyze the time complexity of the following code snippet and express it in Big O notation:

def complex_loop(n):
    count = 0
    i = n
    while i > 1:
        for j in range(0, n):
            count += 1
        i = i // 2
    return count

Solution / Answer:

1. Outer Loop Analysis:
   • Variable i starts at $n$ and is divided by $2$ in each step until i <= 1.
   • The outer while loop executes $\log_2(n)$ times.
2. Inner Loop Analysis:
   • The inner for loop runs from $0$ to $n-1$, executing exactly $n$ times for every single step of the outer loop.
3. Total Step Calculation: $\text{Total Execution Steps} = (\text{Outer Loop Iterations}) \times (\text{Inner Loop Iterations})$ $\text{Total Execution Steps} = \log_2(n) \times n = n \log_2(n)$
4. Final Complexity: $\mathcal{O}(n \log n)$ (Linearithmic Time Complexity).

---

Question 3

Can an algorithm have a best-case time complexity of $\mathcal{O}(1)$ and a worst-case time complexity of $\mathcal{O}(n^2)$? Provide a clear candidate algorithm and defend your answer.

Solution / Answer:

• Yes, standard Bubble Sort and Insertion Sort exhibit this exact performance profile.
• Defense for Insertion Sort:
  • Best-Case $\mathcal{O}(1)$ / $\mathcal{O}(n)$: When the input list is already fully sorted. Insertion sort performs single comparisons per outer loop pass without shifting elements. If framed for a single search insertion step, it terminates in $\mathcal{O}(1)$ at index 0. (For full array verification, best case is $\mathcal{O}(n)$ comparisons).
  • Worst-Case $\mathcal{O}(n^2)$: When the input list is sorted in exact reverse order. Every newly processed element must be shifted past every previously processed element, resulting in $\frac{n(n-1)}{2}$ operations $\implies \mathcal{O}(n^2)$.
• Alternative Example: QuickSort has a best/average case of $\mathcal{O}(n \log n)$, but degrades to $\mathcal{O}(n^2)$ in the worst case if the worst possible pivot (e.g., smallest or largest element) is selected repeatedly.

---

Previous Year Questions (PYQs) with Detailed Solutions

Question 1 (CBSE Class 11 CS)

Differentiate between a flowchart and pseudocode. State one advantage of each.

Answer:

Comparison Parameter	Flowchart	Pseudocode
Representation Type	Graphical/Diagrammatic representation using standardized geometric shapes.	Textual representation using structured English constructs.
Execution Path Visualization	Highly visual; logic flow, conditions, and loops are easy to trace visually.	Linear and narrative; resembles actual code statements.
Space Required	Requires broad canvas space; hard to fit large algorithms on a single page.	Compact and easily formatted within standard text documents.

• Advantage of Flowchart: Excellent for visual learners and non-technical stakeholders to quickly grasp high-level conditional logic pathways.
• Advantage of Pseudocode: Easily converted directly into programming code in Python, C++, or Java without redrawing complex visual shapes.

---

Question 2 (CBSE Class 11 CS)

Write an algorithm and draw a flowchart to find the largest of three numbers $A$, $B$, and $C$.

Answer:

Algorithm (Pseudocode):

STEP 1: Start
STEP 2: Read input values A, B, and C
STEP 3: If A >= B AND A >= C Then
            Set MAX = A
        Else If B >= A AND B >= C Then
            Set MAX = B
        Else
            Set MAX = C
        EndIf
STEP 4: Display "The largest number is:", MAX
STEP 5: Stop

Flowchart Description:

1. Start: Oval terminal symbol containing "Start".
2. Input: Parallelogram containing "Input A, B, C".
3. Decision 1: Diamond containing "Is $A \ge B$ and $A \ge C$?".
   • True Branch: Arrow leading to a Process box "Set $MAX = A$", then branching directly down to Output.
   • False Branch: Arrow leading to Decision 2.
4. Decision 2: Diamond containing "Is $B \ge C$?".
   • True Branch: Arrow leading to a Process box "Set $MAX = B$".
   • False Branch: Arrow leading to a Process box "Set $MAX = C$".
5. Output: Parallelogram receiving connections from all branches containing "Print MAX".
6. End: Oval terminal symbol containing "Stop".

---

Question 3 (CBSE Class 11 CS)

Define Space Complexity. Calculate the space complexity of an algorithm that computes the sum of $N$ array elements using a simple iterative loop.

Answer:

• Definition: Space Complexity is the total amount of memory space required by an algorithm during execution, expressed as a function of the input size $N$.
• Calculation:
  • Input storage required for $N$ array elements $= \mathcal{O}(N)$.
  • Auxiliary scalar variables required for iteration and summation:
    • sum (integer) $= 1$ memory slot.
    • i (loop control index) $= 1$ memory slot.
    • N (array size variable) $= 1$ memory slot.
  • Total auxiliary space allocation $= 3 \text{ scalar slots} = \mathcal{O}(1)$ (Constant Auxiliary Space).
  • Overall Total Space Complexity $= \mathcal{O}(N)$ due to input array storage requirements.

---

Common Mistakes & How to Avoid Them

Common Misconception / Mistake	Reality & Correct Conceptual Approach	How to Avoid
Confusing Algorithms with Source Code or Flowcharts	An algorithm is abstract logical thinking. Flowcharts and Pseudocode are tools to represent it; source code is its implementation.	Keep algorithmic design completely independent of target programming language syntax rules.
Ignoring the Finiteness Property	Creating algorithms with infinite loops or recursive calls that lack base cases.	Ensure every loop has a clear, reachable termination flag and recursive routines contain explicit base cases.
Assuming Big O measures absolute execution time in seconds	Big O measures the growth rate of operational steps relative to input size $n$, not machine clock execution seconds.	Evaluate algorithms by step scaling factor trends rather than benchmark time stopwatch readings.
Forgetting Auxiliary Space in Space Complexity	Counting only the input size and missing temporary arrays or deep recursive stack calls.	Account for call stacks generated by recursion and extra dynamic allocations created during run time.

---

Quick Revision Summary Notes

• An Algorithm is a finite, unambiguous, step-by-step computational procedure that converts inputs into deterministic outputs.
• Key properties: Input, Output, Definiteness, Finiteness, Effectiveness, Generality.
• Deterministic algorithms produce identical pathways every execution; Non-deterministic algorithms incorporate randomness or dynamic state logic.
• Major representation formats are Flowcharts (graphical shapes) and Pseudocode (structured text descriptions).
• Algorithm Design lifecycle follows: Problem Definition $\to$ I/O Analysis $\to$ Development $\to$ Testing/Dry Run $\to$ Code Implementation.
• Time Complexity measures total operational steps; Space Complexity measures total dynamic memory consumed.
• Big O Notation ($\mathcal{O}$) specifies theoretical worst-case performance upper bounds.
• Complexity growth hierarchy: $\mathcal{O}(1) < \mathcal{O}(\log n) < \mathcal{O}(n) < \mathcal{O}(n \log n) < \mathcal{O}(n^2) < \mathcal{O}(2^n) < \mathcal{O}(n!)$
• Linear Search runs in $\mathcal{O}(n)$ time; Binary Search requires a sorted array and runs in $\mathcal{O}(\log n)$ time.
• Bubble, Selection, and Insertion Sort require nested loop iterations yielding $\mathcal{O}(n^2)$ worst-case time complexity.

---

NCERT Textbook Questions & Detailed Answers

Question 1

Define an algorithm. What are the main characteristics of an algorithm?

Answer: An algorithm is a well-defined, step-by-step computational procedure that takes zero or more inputs, processes them systematically through clear instructions, and yields a correct output to solve a specific problem.

The six fundamental characteristics of a valid algorithm are:

1. Input: Accepts zero or more clearly specified inputs.
2. Output: Produces at least one verified result or output.
3. Definiteness: Each step is explicit, clear, and unambiguous.
4. Finiteness: Terminates guaranteed after a finite number of steps for all inputs.
5. Effectiveness: Consists of basic, feasible operations capable of paper-and-pencil execution.
6. Generality: Appliable across an entire operational class of input instances.

---

Question 2

Write an algorithm to calculate the factorial of a given positive integer $N$.

Answer:

Pseudocode Algorithm:

BEGIN FactorialCalculation
    READ N
    IF N < 0 THEN
        PRINT "Error: Factorial is not defined for negative numbers."
        EXIT
    ENDIF
    
    SET fact = 1
    SET i = 1
    
    WHILE i <= N DO
        fact = fact * i
        i = i + 1
    ENDWHILE
    
    PRINT "Factorial of ", N, " is: ", fact
END FactorialCalculation

---

Question 3

Differentiate between Linear Search and Binary Search algorithms. Provide a tabular comparative breakdown.

Answer:

Feature / Metric	Linear Search	Binary Search
Prerequisite Input Condition	Array elements can be in any arbitrary/unsorted order.	Array elements MUST be sorted (ascending/descending).
Search Mechanism	Sequentially scans elements one-by-one from index $0$ to $N-1$.	Divides search space in half repeatedly by comparing with middle element.
Worst-Case Time Complexity	$\mathcal{O}(N)$ (Linear Time).	$\mathcal{O}(\log_2 N)$ (Logarithmic Time).
Best-Case Time Complexity	$\mathcal{O}(1)$ (Found at index 0).	$\mathcal{O}(1)$ (Found directly at middle element).
Algorithmic Paradigm	Brute Force Sequential Iteration.	Divide and Conquer.
Data Structure Suitability	Works well on Arrays and Linked Lists.	Highly effective on Arrays; inefficient on Linked Lists due to direct indexing requirement.

---

Question 4

Draw a flowchart to compute the roots of a quadratic equation $ax^2 + bx + c = 0$.

Answer:

                          +--------------------+
                          |     [ Start ]      |
                          +--------------------+
                                    |
                                    v
                          +--------------------+
                          |  Read coefficients |
                          |      a, b, c       |
                          +--------------------+
                                    |
                                    v
                          +--------------------+
                          |  Calculate Disc D: |
                          |   D = (b*b)-4*a*c  |
                          +--------------------+
                                    |
                                    v
                          +--------------------+
                          |      Is D >= 0 ?   |
                          +--------------------+
                               /          \
                        (Yes) /            \ (No)
                             v              v
            +-------------------+   +-----------------------+
            |  root1=(-b+sqrt(D))/(2*a) | | realPart = -b/(2*a)   |
            |  root2=(-b-sqrt(D))/(2*a) | | imagPart = sqrt(-D)/(2*a) |
            +-------------------+   +-----------------------+
                      |                         |
                      v                         v
            +-------------------+   +-----------------------+
            | Print root1, root2|   | Print roots as:       |
            +-------------------+   | realPart ± i*imagPart |
                      \             +-----------------------+
                       \                        /
                        v                      v
                          +--------------------+
                          |      [ Stop ]      |
                          +--------------------+

---

Question 5

What is the importance of Algorithm Analysis? Briefly discuss Time and Space complexity.

Answer:

• Importance of Algorithm Analysis: Algorithm Analysis provides a rigorous theoretical mechanism to evaluate and compare the efficiency of different problem-solving approaches independently of specific hardware configurations, operating systems, memory sizes, or programming language choices. It prevents software systems from failing when scaled to real-world multi-million entry production datasets.

• Time Complexity: Quantifies how the total runtime (expressed in total basic operational steps) grows relative to input data scaling ($N$). It highlights processing bottlenecks prior to code deployment.

• Space Complexity: Quantifies the total dynamic execution memory required by an algorithm as a function of input size ($N$). It ensures systems operate reliably within available hardware memory allocations without causing buffer overflows or memory allocation failures.