Designing Algorithms

# Designing Algorithms ## Objectifs et prérequis This chapter introduces students to the fundamental principles of algorithm design, representation, and implementation using structured programming constructs. By the end of this chapter, students will be able to analyze problems, select appropriate design approaches, represent algorithms using pseudocode and flowcharts, apply design strategies such as divide and conquer and greedy methods, and implement algorithms using sequence, selection, and repetition structures, including subroutines and parameter passing mechanisms. **Prerequisites:** - Basic understanding of computer systems and data types - Familiarity with pseudocode syntax from introductory computing - Logical reasoning and problem-solving skills - Ability to follow step-by-step instructions --- ## I. Algorithm Design Approaches 1 ### Definition and Classification Algorithm design approaches refer to systematic methodologies used to construct step-by-step procedures for solving computational problems. These approaches provide frameworks that guide the transformation of a problem statement into an executable algorithm. > **Key Concept:** An algorithm design approach is a general strategy or paradigm that can be applied across multiple problem domains to derive efficient and correct solutions. The two primary approaches covered in this section are: 1. **Top-down design** 2. **Bottom-up design** ### Top-down Design This approach begins with the overall problem and breaks it down into smaller, more manageable subproblems. Each subproblem is further decomposed until the tasks are simple enough to be solved directly. **Properties:** - Hierarchical decomposition - Focus on problem structure before implementation details - Promotes modularity and clarity **Example: Calculating the average of three numbers** 1. Start with the main goal: *Compute average of three numbers* 2. Break into subgoals: - Input three numbers - Compute their sum - Divide sum by 3 - Output the result 3. Each subgoal becomes a step in the algorithm **Step-by-step solution:** - Step 1: Prompt user for first number → store in `a` - Step 2: Prompt user for second number → store in `b` - Step 3: Prompt user for third number → store in `c` - Step 4: Compute `sum = a + b + c` - Step 5: Compute `average = sum / 3` - Step 6: Display `average` **Exercise 1:** Design an algorithm using top-down approach to determine if a year is a leap year. *(Leap year rules: divisible by 4, but not by 100 unless also divisible by 400)* **Corrected Solution:** 1. Main goal: *Determine if year is leap year* 2. Subgoals: - Input year - Check if divisible by 400 → if yes, leap year - Else, check if divisible by 100 → if yes, not leap year - Else, check if divisible by 4 → if yes, leap year - Else, not leap year 3. Algorithm: - Step 1: Input `year` - Step 2: If `year mod 400 = 0` → output "Leap year" - Step 3: Else if `year mod 100 = 0` → output "Not leap year" - Step 4: Else if `year mod 4 = 0` → output "Leap year" - Step 5: Else → output "Not leap year" ### Bottom-up Design This approach starts with solving the smallest, most basic subproblems and gradually combines them to solve larger problems until the original problem is addressed. **Properties:** - Builds complexity from simple components - Often used when sub-solutions are reusable or well-known - Encourages testing and validation at each level **Example: Computing factorial of a number (n!)** Known subproblem: `fact(0) = 1`, `fact(1) = 1` Recursive relation: `fact(n) = n × fact(n-1)` **Step-by-step solution (iterative bottom-up):** - Step 1: Initialize `result = 1` - Step 2: For `i` from 1 to `n`: - `result = result × i` - Step 3: Output `result` **Exercise 2:** Use bottom-up design to compute the sum of the first `n` natural numbers. **Corrected Solution:** - Known: sum of first 0 numbers = 0 - Build up: sum of first 1 = 0 + 1, sum of first 2 = (sum of first 1) + 2, etc. - Algorithm: - Step 1: Input `n` - Step 2: Initialize `total = 0` - Step 3: For `i` from 1 to `n`: - `total = total + i` - Step 4: Output `total` **Comparison Table: Top-down vs Bottom-up** | Feature | Top-down Design | Bottom-up Design | |------------------------|-------------------------------------|--------------------------------------| | Starting point | Original problem | Smallest subproblems | | Direction | Decomposition | Composition | | Focus | Problem structure | Solution building | | Best for | Understanding complex problems | Reusing known solutions | | Example | Leap year checker | Factorial, Fibonacci (iterative) | --- ## II. Algorithm Design Approaches 2 ### Divide and Conquer This strategy involves dividing a problem into two or more subproblems of the same or related type, solving them recursively, and combining their solutions to solve the original problem. > **Key Concept:** Divide and conquer reduces problem size exponentially, often leading to efficient algorithms like merge sort and binary search. **Properties:** - Divide: Split problem into smaller subproblems - Conquer: Solve subproblems recursively - Combine: Merge solutions of subproblems - Recurrence relation often describes time complexity **Example: Binary Search** Search for a target value in a sorted array by repeatedly dividing the search interval in half. **Step-by-step solution:** - Step 1: Set `low = 0`, `high = n-1` - Step 2: While `low ≤ high`: - Compute `mid = floor((low + high)/2)` - If `arr[mid] == target` → return `mid` - Else if `arr[mid] < target` → `low = mid + 1` - Else → `high = mid - 1` - Step 3: If loop ends, return -1 (not found) **Exercise 3:** Apply divide and conquer to find the maximum element in an array. **Corrected Solution:** - Divide: Split array into left and right halves - Conquer: Recursively find max in left and right - Combine: Return the larger of the two maxima - Base case: If array size = 1, return that element - Pseudocode: ``` function findMax(arr, left, right): if left == right: return arr[left] mid = floor((left + right)/2) leftMax = findMax(arr, left, mid) rightMax = findMax(arr, mid+1, right) return max(leftMax, rightMax) ``` ### Greedy Approach This method makes the locally optimal choice at each step with the hope of finding a global optimum. It does not reconsider previous choices. > **Key Concept:** Greedy algorithms are efficient but do not always yield optimal solutions; they work only when the problem exhibits the greedy choice property and optimal substructure. **Properties:** - Makes irrevocable decisions - Prioritizes immediate benefit - Often used in optimization problems - No backtracking **Example: Coin Change (Greedy)** Given coin denominations [1, 5, 10, 25], make change for 63 cents using fewest coins. **Step-by-step solution:** - Step 1: Use as many 25c as possible: 63 ÷ 25 = 2 → remainder 13 - Step 2: Use as many 10c as possible: 13 ÷ 10 = 1 → remainder 3 - Step 3: Use as many 5c as possible: 3 ÷ 5 = 0 → remainder 3 - Step 4: Use 1c coins: 3 → total coins = 2 + 1 + 0 + 3 = 6 **Exercise 4:** Use the greedy approach to schedule maximum number of non-overlapping activities given start and finish times: Activities: (1,4), (3,5), (0,6), (5,7), (3,9), (5,9), (6,10), (8,11), (8,12), (2,14), (12,16) *(Sort by finish time)* **Corrected Solution:** - Sort by finish time: (1,4), (3,5), (0,6), (5,7), (6,10), (8,11), (8,12), (5,9), (3,9), (2,14), (12,16) → actually sort properly: Sorted: (1,4), (3,5), (0,6), (5,7), (6,10), (8,11), (8,12), (5,9), (3,9), (2,14), (12,16) → correct sort by finish: (1,4) f=4, (3,5) f=5, (0,6) f=6, (5,7) f=7, (6,10) f=10, (8,11) f=11, (8,12) f=12, (5,9) f=9, (3,9) f=9, (2,14) f=14, (12,16) f=16 Proper order: (1,4), (3,5), (0,6), (5,7), (6,10), (5,9), (3,9), (8,11), (8,12), (2,14), (12,16) - Select (1,4) → last finish = 4 - Next compatible: (5,7) → last finish = 7 - Next: (8,11) → last finish = 11 - Next: (12,16) → last finish = 16 - Selected: (1,4), (5,7), (8,11), (12,16) → 4 activities **Comparison Table: Divide and Conquer vs Greedy** | Feature | Divide and Conquer | Greedy | |------------------------|-------------------------------------|-------------------------------------| | Approach | Recursive decomposition | Local optimal choice | | Reconsideration | Yes (via recursion) | No | | Optimality | Always optimal if combine step correct | Only if greedy choice property holds | | Examples | Merge sort, binary search | Activity selection, coin change (canonical) | | Complexity | Often O(n log n) | Often O(n) after sorting | --- ## III. Representation of Algorithms – Part 1 ### Pseudocode Pseudocode is an informal, high-level description of an algorithm using structural conventions of programming languages but intended for human reading. It omits language-specific syntax. > **Key Concept:** Pseudocode bridges the gap between natural language and actual code, enabling clear communication of logic without implementation details. **Properties:** - Uses keywords like `INPUT`, `OUTPUT`, `IF`, `THEN`, `ELSE`, `FOR`, `WHILE` - Indentation shows block structure - No strict syntax rules, but must be unambiguous - Variables are declared implicitly by use **Example: Algorithm to find the largest of three numbers** ``` BEGIN INPUT a, b, c IF a > b THEN IF a > c THEN OUTPUT a ELSE OUTPUT c END IF ELSE IF b > c THEN OUTPUT b ELSE OUTPUT c END IF END IF END ``` **Step-by-step trace for a=5, b=3, c=8:** - a > b? 5 > 3 → true - a > c? 5 > 8 → false → output c = 8 **Exercise 5:** Write pseudocode to compute the area of a triangle given base and height. **Corrected Solution:** ``` BEGIN INPUT base, height area = (base * height) / 2 OUTPUT area END ``` ### Flowcharts A flowchart is a diagrammatic representation of an algorithm using standardized symbols to show the flow of control. > **Key Concept:** Flowcharts visualize the sequence of operations, decisions, and data flow in an algorithm, making logic easier to follow and debug. **Standard Symbols:** - Oval: Start/End - Rectangle: Process (assignment, calculation) - Diamond: Decision (yes/no question) - Parallelogram: Input/Output - Arrow: Flow of control **Example: Flowchart for checking if a number is even or odd** 1. Start (Oval) 2. Input number (Parallelogram) 3. Is number mod 2 = 0? (Diamond) - Yes → Output "Even" (Parallelogram) → End - No → Output "Odd" (Parallelogram) → End **Exercise 6:** Draw a flowchart to compute the factorial of a number using iteration. **Corrected Solution (description):** - Start - Input n - Set result = 1 - Set i = 1 - Is i ≤ n? - Yes: result = result × i; i = i + 1 → loop back - No: Output result → End **Comparison Table: Pseudocode vs Flowchart** | Feature | Pseudocode | Flowchart | |------------------------|-------------------------------------|-------------------------------------| | Medium | Textual | Graphical | | Readability | High for sequential logic | High for branching and loops | | Creation speed | Fast | Slower (requires drawing) | | Detail level | Can be concise or detailed | Shows exact flow paths | | Best for | Writing and sharing algorithms | Teaching and debugging logic | --- ## IV. Representation of Algorithms – Part 2 ### Control Structures in Pseudocode Control structures dictate the order in which statements are executed. The three fundamental types are sequence, selection, and repetition. > **Key Concept:** All algorithms can be constructed using only sequence, selection, and repetition structures (structured programming theorem). **Sequence:** Statements executed in order, one after another. **Selection:** Chooses between alternative paths based on a condition. **Repetition:** Repeats a block of statements while a condition holds. **Example: Algorithm with all three structures** *Find the sum of all even numbers from 1 to n* ``` BEGIN INPUT n sum = 0 i = 1 WHILE i <= n DO IF i mod 2 = 0 THEN sum = sum + i END IF i = i + 1 END WHILE OUTPUT sum END ``` **Step-by-step trace for n=6:** - i=1: 1 mod 2 ≠ 0 → skip; i=2 - i=2: 2 mod 2 = 0 → sum=0+2=2; i=3 - i=3: skip; i=4 - i=4: sum=2+4=6; i=5 - i=5: skip; i=6 - i=6: sum=6+6=12; i=7 → loop ends - Output 12 **Exercise 7:** Write pseudocode to print all multiples of 5 between 1 and 100. **Corrected Solution:** ``` BEGIN i = 1 WHILE i <= 100 DO IF i mod 5 = 0 THEN OUTPUT i END IF i = i + 1 END WHILE END ``` ### Nested Control Structures Control structures can be embedded within one another to handle complex logic. **Example: Nested selection in a loop** *Classify numbers from 1 to 10 as negative, zero, or positive (though all positive here, for illustration)* ``` BEGIN i = 1 WHILE i <= 10 DO IF i > 0 THEN OUTPUT i, "is positive" ELSE IF i < 0 THEN OUTPUT i, "is negative" ELSE OUTPUT i, "is zero" END IF i = i + 1 END WHILE END ``` **Exercise 8:** Write pseudocode to input 5 numbers and count how many are even and how many are odd. **Corrected Solution:** ``` BEGIN evenCount = 0 oddCount = 0 i = 1 WHILE i <= 5 DO INPUT num IF num mod 2 = 0 THEN evenCount = evenCount + 1 ELSE oddCount = oddCount + 1 END IF i = i + 1 END WHILE OUTPUT "Even:", evenCount OUTPUT "Odd:", oddCount END ``` --- ## V. Algorithm Design Strategies ### Overview Algorithm design strategies are general paradigms that guide the creation of efficient algorithms. Beyond divide and conquer and greedy, other strategies include dynamic programming, backtracking, and brute force. > **Key Concept:** Choosing the right design strategy depends on the problem’s properties, such as optimal substructure, overlapping subproblems, and constraint satisfaction. ### Dynamic Programming Solves complex problems by breaking them into overlapping subproblems, storing results of subproblems to avoid recomputation (memoization), and building up solutions bottom-up. > **Key Concept:** Dynamic programming is effective when subproblems are reused multiple times. **Properties:** - Overlapping subproblems - Optimal substructure - Uses table or array to store intermediate results - Can be top-down (memoization) or bottom-up **Example: Fibonacci sequence** Compute F(n) where F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2) **Bottom-up DP solution:** ``` BEGIN INPUT n IF n == 0 THEN OUTPUT 0 ELSE IF n == 1 THEN OUTPUT 1 ELSE fib[0] = 0 fib[1] = 1 FOR i FROM 2 TO n DO fib[i] = fib[i-1] + fib[i-2] END FOR OUTPUT fib[n] END IF END ``` **Exercise 9:** Use dynamic programming to compute the 6th Fibonacci number. **Corrected Solution:** - fib[0]=0, fib[1]=1 - i=2: fib[2]=1+0=1 - i=3: fib[3]=1+1=2 - i=4: fib[4]=2+1=3 - i=5: fib[5]=3+2=5 - i=6: fib[6]=5+3=8 - Output 8 ### Brute Force Enumerates all possible candidates for the solution and checks each one for validity. > **Key Concept:** Brute force is simple to implement but often inefficient; used when problem size is small or no better strategy is known. **Example: Finding a password by trying all combinations** If password is 3 digits (000–999), try 000, 001, ..., 999 until match. **Exercise 10:** Use brute force to find if a number between 1 and 10 is equal to 7. **Corrected Solution:** ``` BEGIN FOR guess FROM 1 TO 10 DO IF guess = 7 THEN OUTPUT "Found: 7" EXIT LOOP END IF END FOR END ``` **Comparison Table: Design Strategies** | Strategy | Best When | Time Complexity | Example | |----------------------|------------------------------------------------|----------------------|--------------------------| | Divide and Conquer | Problem splits into independent subproblems | O(n log n) typical | Merge sort, binary search| | Greedy | Local choice leads to global optimum | O(n log n) or O(n) | Activity selection | | Dynamic Programming | Overlapping subproblems, optimal substructure | O(n²) or O(n) | Fibonacci, shortest path | | Brute Force | Small search space, no structure | O(kⁿ) or O(n!) | Password cracking | --- ## VI. Sequence and Selection Structures 1 ### Sequence Structure The simplest control structure where statements are executed in the exact order they appear. > **Key Concept:** Sequence is the default flow of execution; no branching or looping occurs. **Properties:** - Linear execution - No conditions or loops - Each step depends on the previous **Example: Algorithm to convert Celsius to Fahrenheit** ``` BEGIN INPUT celsius fahrenheit = (celsius * 9/5) + 32 OUTPUT fahrenheit END ``` **Step-by-step for celsius=25:** - fahrenheit = (25 × 9/5) + 32 = 45 + 32 = 77 - Output 77 **Exercise 11:** Write a sequence-only algorithm to compute the perimeter of a rectangle given length and width. **Corrected Solution:** ``` BEGIN INPUT length, width perimeter = 2 * (length + width) OUTPUT perimeter END ``` ### Selection Structure Allows the algorithm to choose between two or more alternative paths based on a condition. > **Key Concept:** Selection introduces decision-making into algorithms, enabling them to respond differently to different inputs. **Types:** - **Single alternative:** IF condition THEN ... END IF - **Double alternative:** IF condition THEN ... ELSE ... END IF - **Multiple alternative:** IF ... ELSE IF ... ELSE ... END IF **Example: Grade assignment based on score** ``` BEGIN INPUT score IF score >= 90 THEN OUTPUT "A" ELSE IF score >= 80 THEN OUTPUT "B" ELSE IF score >= 70 THEN OUTPUT "C" ELSE IF score >= 60 THEN OUTPUT "D" ELSE OUTPUT "F" END IF END ``` **Exercise 12:** Write pseudocode to determine if a number is positive, negative, or zero using selection. **Corrected Solution:** ``` BEGIN INPUT num IF num > 0 THEN OUTPUT "Positive" ELSE IF num < 0 THEN OUTPUT "Negative" ELSE OUTPUT "Zero" END IF END ``` **Comparison Table: Sequence vs Selection** | Feature | Sequence | Selection | |------------------------|---------------------------------------|---------------------------------------| | Flow | Linear | Branching | | Decision making | None | Based on condition | | Flexibility | Low | High | | Use case | Fixed calculations | Conditional logic | | Example | Area of rectangle | Pass/fail check | --- ## VII. Sequence and Selection Structures 2 ### Combining Sequence and Selection Real-world algorithms often use sequence to perform actions and selection to make decisions within that flow. **Example: Algorithm to compute discount based on purchase amount** ``` BEGIN INPUT amount IF amount >= 1000 THEN discount = amount * 0.15 ELSE IF amount >= 500 THEN discount = amount * 0.10 ELSE discount = 0 END IF finalAmount = amount - discount OUTPUT finalAmount END ``` **Step-by-step for amount=750:** - amount >= 1000? No - amount >= 500? Yes → discount = 750 × 0.10 = 75 - finalAmount = 750 - 75 = 675 - Output 675 **Exercise 13:** Write pseudocode to calculate salary after tax: - No tax if salary ≤ 300,000 - 10% tax if 300,000 < salary ≤ 600,000 - 20% tax if salary > 600,000 **Corrected Solution:** ``` BEGIN INPUT salary IF salary <= 300000 THEN tax = 0 ELSE IF salary <= 600000 THEN tax = salary * 0.10 ELSE tax = salary * 0.20 END IF netSalary = salary - tax OUTPUT netSalary END ``` ### Common Pitfalls in Selection - **Overlapping conditions:** Using `IF` without `ELSE IF` can cause multiple blocks to execute. - **Missing ELSE:** May leave some cases unhandled. - **Incorrect boundary conditions:** Using `>` instead of `>=` can cause off-by-one errors. **Example of error:** ``` IF score > 90 THEN OUTPUT "A" IF score > 80 THEN OUTPUT "B" ``` For score=85: first condition false, second true → outputs "B" (correct), but if score=95: both true → outputs "A" and "B" (incorrect). **Corrected:** Use `ELSE IF` to ensure only one block runs. **Exercise 14:** Identify and fix the error in this pseudocode: ``` BEGIN INPUT age IF age >= 18 THEN OUTPUT "Adult" END IF IF age < 18 THEN OUTPUT "Minor" END IF END ``` **Corrected Solution:** The error is that both IF statements can execute if age is exactly 18? No: if age=18, first IF true → "Adult", second IF false (18<18 false) → only "Adult". Actually, it's correct but inefficient. Better to use ELSE. **Improved version:** ``` BEGIN INPUT age IF age >= 18 THEN OUTPUT "Adult" ELSE OUTPUT "Minor" END IF END ``` --- ## VIII. Sequence and Selection Structures ### Integrated Application This section reinforces the use of sequence and selection together in solving realistic problems. **Example: Algorithm to validate a password** *Rules: at least 8 characters, contains at least one digit, and one uppercase letter* ``` BEGIN INPUT password lengthOk = (LENGTH(password) >= 8) hasDigit = FALSE hasUpper = FALSE i = 1 WHILE i <= LENGTH(password) DO char = SUBSTRING(password, i, 1) IF char >= '0' AND char <= '9' THEN hasDigit = TRUE END IF IF char >= 'A' AND char <= 'Z' THEN hasUpper = TRUE END IF i = i + 1 END WHILE IF lengthOk AND hasDigit AND hasUpper THEN OUTPUT "Valid password" ELSE OUTPUT "Invalid password" END IF END ``` **Note:** This example introduces repetition (covered later) but uses selection within the loop. **Exercise 15:** Write pseudocode to input three sides of a triangle and determine if it is equilateral, isosceles, or scalene. **Corrected Solution:** ``` BEGIN INPUT a, b, c IF a = b AND b = c THEN OUTPUT "Equilateral" ELSE IF a = b OR b = c OR a = c THEN OUTPUT "Isosceles" ELSE OUTPUT "Scalene" END IF END ``` **Step-by-step for a=5, b=5, c=3:** - a=b? 5=5 true, b=c? 5=3 false → first condition false - a=b? true → so second condition true → output "Isosceles" --- ## IX. Repetition Structures 1a ### Introduction to Loops Repetition structures (loops) allow a block of statements to be executed multiple times, either a fixed number of times or until a condition is met. > **Key Concept:** Loops eliminate redundancy and enable algorithms to handle variable-sized input efficiently. **Types:** - **Counter-controlled loop:** Executes a known number of times (e.g., FOR loop) - **Condition-controlled loop:** Executes while a condition is true (e.g., WHILE loop) **FOR Loop Syntax (Pseudocode):** ``` FOR variable = start TO end DO statements END FOR ``` **WHILE Loop Syntax:** ``` WHILE condition DO statements END WHILE ``` > **Key Concept:** A loop must have a clear termination condition to avoid infinite loops. **Example: FOR loop to print numbers 1 to 5** ``` BEGIN FOR i = 1 TO 5 DO OUTPUT i END FOR END ``` **Exercise 16:** Write pseudocode using a FOR loop to compute the sum of the first 10 even numbers. **Corrected Solution:** ``` BEGIN sum = 0 FOR i = 1 TO 10 DO evenNum = 2 * i sum = sum + evenNum END FOR OUTPUT sum END ``` **Step-by-step:** - i=1: even=2, sum=2 - i=2: even=4, sum=6 - i=3: even=6, sum=12 - i=4: even=8, sum=20 - i=5: even=10, sum=30 - i=6: even=12, sum=42 - i=7: even=14, sum=56 - i=8: even=16, sum=72 - i=9: even=18, sum=90 - i=10: even=20, sum=110 - Output 110 ### Infinite Loops and Termination An infinite loop occurs when the loop condition never becomes false. **Example of dangerous loop:** ``` WHILE TRUE DO OUTPUT "Hello" END WHILE ``` **How to avoid:** - Ensure loop variables are updated - Ensure condition eventually becomes false - Use sentinel values or counters **Exercise 17:** Why is this loop infinite? ``` BEGIN i = 1 WHILE i <= 5 DO OUTPUT i END WHILE END ``` **Corrected Solution:** The variable `i` is never incremented inside the loop, so `i` remains 1, and the condition `i <= 5` is always true → infinite loop. **Fix:** Add `i = i + 1` inside the loop. --- ## X. Repetition Structures – Part 1 ### WHILE Loop in Detail The WHILE loop evaluates a condition before each iteration. If true, the body executes; if false, the loop terminates. > **Key Concept:** The condition is checked at the start, so the loop body may execute zero times. **Example: Validate user input (positive number)** ``` BEGIN INPUT num WHILE num <= 0 DO OUTPUT "Error: Enter a positive number" INPUT num END WHILE OUTPUT "Thank you" END ``` **Exercise 18:** Write pseudocode to find the first power of 2 greater than 100 using a WHILE loop. **Corrected Solution:** ``` BEGIN power = 1 WHILE power <= 100 DO power = power * 2 END WHILE OUTPUT power END ``` **Step-by-step:** - power=1 → 1≤100 → power=2 - power=2 → 2≤100 → power=4 - power=4 → 4≤100 → power=8 - power=8 → 8≤100 → power=16 - power=16 → 16≤100 → power=32 - power=32 → 32≤100 → power=64 - power=64 → 64≤100 → power=128 - power=128 → 128≤100? false → exit - Output 128 ### Loop Invariants A loop invariant is a condition that is true before and after each iteration of a loop. It helps in proving correctness. > **Key Concept:** Loop invariants are used to reason about loop correctness and are essential in formal verification. **Example: In the power-of-2 loop above** Invariant: `power` is always a power of 2, and `power` is the smallest power of 2 ≥ initial value after k iterations. - Initially: power=1=2⁰ → true - After each iteration: power doubles → still power of 2 - When loop ends: power > 100 and is power of 2 → correct **Exercise 19:** State the loop invariant for a loop that sums the first n natural numbers. ``` BEGIN sum = 0 i = 1 WHILE i <= n DO sum = sum + i i = i + 1 END WHILE END ``` **Corrected Solution:** Loop invariant: At the start of each iteration, `sum = 1 + 2 + ... + (i-1)` - Initially: i=1, sum=0 → sum of first 0 numbers = 0 → true - After iteration: sum includes i, then i increments → invariant holds - When loop ends: i = n+1 → sum = 1+2+...+n → correct --- ## XI. Repetition Structures – Part 2 ### Nested Loops A loop inside another loop. The inner loop completes all its iterations for each single iteration of the outer loop. > **Key Concept:** Nested loops are used to handle multi-dimensional data, such as matrices or grids. **Example: Print a 3x3 grid of coordinates** ``` BEGIN FOR row = 1 TO 3 DO FOR col = 1 TO 3 DO OUTPUT "(", row, ",", col, ") " END FOR OUTPUT NEWLINE END FOR END ``` **Output:** (1,1) (1,2) (1,3) (2,1) (2,2) (2,3) (3,1) (3,2) (3,3) **Exercise 20:** Write pseudocode to print a multiplication table from 1 to 5 using nested FOR loops. **Corrected Solution:** ``` BEGIN FOR i = 1 TO 5 DO FOR j = 1 TO 5 DO product = i * j OUTPUT product, " " END FOR OUTPUT NEWLINE END FOR END ``` **Step-by-step for i=2:** - j=1: 2×1=2 - j=2: 2×2=4 - j=3: 2×3=6 - j=4: 2×4=8 - j=5: 2×5=10 - Output line: 2 4 6 8 10 ### Loop Optimization Techniques to reduce unnecessary computations inside loops. **Example: Loop-invariant code motion** Move calculations that do not change inside the loop outside. **Inefficient:** ``` FOR i = 1 TO n DO result = result + (constant * 2) END FOR ``` **Efficient:** ``` temp = constant * 2 FOR i = 1 TO n DO result = result + temp END FOR ``` **Exercise 21:** Optimize this loop: ``` BEGIN total = 0 FOR i = 1 TO 100 DO total = total + (50 * 3) END FOR END ``` **Corrected Solution:** ``` BEGIN temp = 50 * 3 // = 150 total = 0 FOR i = 1 TO 100 DO total = total + temp END FOR OUTPUT total END ``` ---