Unit 2: Algorithms & Control Structures Study Guide

The Basics of Algorithms

• Initial Concept Exploration: Making a Peanut Butter Sandwich     * Writing instructions for a simple task, such as making a peanut butter sandwich, reveals significant variance in interpretation and detail between individuals.     * Potential Variances in Instructions:         * Ingredients: Use of peanut butter, jam, jelly, preserves, butter, or margarine.         * Bread Types: Whole wheat, white bread, French bread, or croissants.         * Assembly Order: The specific sequence in which ingredients are layered.         * Tools: Which utensils are used to spread or cut.         * Serving Instructions: Instructions on how to present or plate the final product.

• Definition of an Algorithm     * Core Definition: An algorithm is a sequence of precise, step-by-step instructions designed to solve a specific problem or perform a computation.     * Properties of Algorithms:         * Algorithms can be written in different ways and still accomplish the same goal. Example: Taking one step forward and then one step to the right results in the same final position as taking one step to the right and then one step forward.         * Algorithms that appear very similar can yield vastly different results; precision is vital.     * Real-Life Examples:         * Giving directions from Location A to Location B.         * Instructions for tying shoelaces.         * Instructions for playing a game.         * A baking recipe.     * Computer Science Context: Algorithms are the fundamental foundation of all computer programs.

• Creating and Modifying Algorithms     * Algorithms can be generated from a fresh idea, by combining existing algorithms, or by modifying existing ones.     * Common Computational Algorithms:         * Finding the minimum (smallest) or maximum (largest) value in a numeric list.         * Computing the sum or average of a set of numbers.         * Determining the path of a robot through a maze.         * Determining if an integer is evenly divisible by another integer.     * Benefits of Using Existing Algorithms as Building Blocks:         * Reduced development time.         * Reduced testing requirements.         * Simplified identification of errors.

• Solving Problems with Algorithms     * Problem: A task that can (or sometimes cannot) be solved algorithmically.     * Instance of a Problem: A specific example of a problem. For example, while "sorting a list" is a general problem, "sorting the list $(5, 2, 1, 7, 8)$ is a specific instance.     * Decision Problem: A problem that requires a binary "yes" or "no" answer.     * Optimization Problem: A problem focused on finding the best possible answer (e.g., finding the shortest path between two geographic locations).

• Algorithmic Efficiency and Unreasonable Time     * Efficiency: An estimation of the computational resources used by an algorithm. This is often informally measured by the number of times a statement or group of statements executes.     * Reasonable Time: Algorithms with polynomial efficiency or slower are considered to run in a reasonable amount of time.     * Unreasonable Time: Algorithms with exponential or factorial efficiencies are considered to run in an unreasonable amount of time.

• Heuristic Solutions     * Approach: When a problem cannot be solved in a reasonable amount of time, programmers use heuristics.     * Definition: Heuristic programming prioritizes finding a solution in the fastest time possible, often trading off accuracy, efficiency, or optimality for speed.     * Logic: The "good enough" philosophy—if it solves the problem, it is acceptable.     * Common Heuristic Methods:         * Trial and error.         * Common sense.         * Guesstimates.         * Following a "rule of thumb."

Control Structures - Sequence

• Foundations of Programming     * Program: An algorithm written in a specific language that a computer can understand and execute. Examples include software, websites, and video games.     * Code Statement: A portion of program code that expresses a specific action to be carried out.     * Control Structure: A mechanism that determines the order of statement execution or the direction of the "flow" of the program. Clarity and readability are essential when expressing these in code.

• The Three Universal Control Structures     * 1. Sequence: A series of precise statements executed in order.     * 2. Selection: The algorithm chooses one of two paths based on a condition.     * 3. Repetition (Iteration): The algorithm repeats a sequence of steps.

• Flowcharts     * Flowcharts are diagrammatic representations of algorithms, processes, or workflows. They help programmers organize the logic of complex algorithms before writing code.     * Standard Flowchart Shapes:         * Oval (Ellipse): Represents the Start or End of an algorithm.         * Rectangle: Represents one or more steps or processes.         * Diamond: Represents a conditional or decision step (e.g., True/False, Yes/No).         * Parallelogram: Represents Input or Output (displaying a message).         * Arrows: Show the direction of movement through the algorithm.

• Sequential Algorithm Example: The Maze     * A robot (represented by a black triangle) faces right on white squares. It must reach a gray square.     * Commands:         * MOVE_FORWARD: Moves 1 square forward in the current direction.         * ROTATE_RIGHT: Turns right $90^{\circ}$ in the same square.         * ROTATE_LEFT: Turns left $90^{\circ}$ in the same square.     * Example Sequential Algorithm to navigate a specific maze:         1. MOVE_FORWARD         2. MOVE_FORWARD         3. ROTATE_RIGHT         4. MOVE_FORWARD         5. MOVE_FORWARD

Control Structures - Iteration

• Definition of Iteration     * Iteration is the process of repeating steps rather than listing them sequentially over and over. It allows programs to be scaled to solve large, complex problems efficiently.

• The Shampoo Problem: A Case for Iteration     * Standard directions: "Wash, Rinse, Repeat."     * Sequential Representation: A flowchart showing Wash -> Rinse -> Wash -> Rinse -> End.     * The Problem with Sequence: If the task requires washing 10,000 times, the program becomes redundant and massive.     * Iterative Solution: Use a Condition to test before each run. The loop only runs if the condition is True (e.g., Is Hair Dirty? Yes).

• Iteration in AP Pseudocode     * REPEAT n TIMES: Repeats a block a fixed number of times.         * Example: x ← 0 REPEAT 3 TIMES { DISPLAY(x) x ← x + 1 } // Output: 0 1 2                  * REPEAT UNTIL (condition): Repeats until a specific condition is met.         * If the condition is true initially, the loop never runs.         * Infinite Loop: If the condition never becomes true, the loop runs forever.         * Example: x ← 0 REPEAT UNTIL (x > 2) { DISPLAY(x) x ← x + 1 } // Output: 0 1 2             

Iterations in Python

• The while Loop     * Runs as long as a condition is True.     * Syntax: python while condition: statement1 statement2              * Indentation: In Python, statements belonging to the loop body MUST be indented. Python uses indentation to distinguish internal loop code from the rest of the program.

• Rules for Terminating a Loop     1. Variables in the condition must be initialized before the loop.     2. The condition is tested before the loop begins.     3. At least one variable in the condition must change value within the loop body to eventually make the condition false.

• The for Loop     * Used to iterate over a sequence (list, set, or range).     * Syntax: python for x in sequence: statement              * Example: Iterating over string "banana" prints each letter (b, a, n, etc.) on a new line.

• The range() Function     * Method 1: range(stop)         * range(10): Starts at 0, goes up to 9 (stops before 10).     * Method 2: range(start, stop)         * range(1, 10): Starts at 1, goes up to 9.     * Method 3: range(start, stop, step)         * range(1, 10, 2): Starts at 1, stops at 9, increments by 2 (1, 3, 5, 7, 9).

Control Structures - Selection

• Binary Engines     * Computers are binary machines; every complex decision ultimately reduces to a choice between two outcomes: True or False, 0 or 1, Yes or No.     * Selection: The process of following one of two paths based on whether a condition is true or false.

• If-Else Statements     * Format: "If [condition] is True, then follow [Procedure A], Else follow [Procedure B]."     * AP Pseudocode Example: IF ( x > 5 ) { DISPLAY("x is greater than 5") } ELSE { DISPLAY("x is NOT greater than 5") }         

• The CAN_MOVE Command     * In the Robot Maze context: CAN_MOVE(direction).     * Parameters for direction: left, right, forward, backward.     * Returns True if there is an open square in that direction.

Selections in Python

• Syntax of the if Statementpython if condition: statement          * If the condition is false, the statement is ignored entirely.     * Comparison uses == (equals), != (not equals), <, >, <=, >=.     * Note: Using a single = inside a condition results in an error because = is for assignment, not comparison.

• The if-else Statementpython if x == y: print("They are equal") else: print("They are NOT equal")          * This is more efficient and elegant than using two separate if statements.

• Input Conversion     * User input is captured as a string. To use it for numeric comparison, it must be converted: x = int(input("Enter number: ")).

Nesting Iteration & Selection

• Nested Logic     * Occurs when conditions must be met sequentially (e.g., verifying if a driver is a senior AND has a parking pass).     * The elif Statement: Short for "Else If." It allows for multiple specific conditions in sequence.     * Logic Flow: The computer checks conditions from top to bottom. As soon as it finds a True condition, it executes those statements and exits the entire if-elif-else structure.

• Compounding Conditions with Logic Operators     * and: Both conditions must be True.     * or: At least one condition must be True.     * Example for Age Groups:         * Minor: age < 18         * Adult: age >= 18 and age < 55         * Senior: age >= 55

• The break Function     * Used to immediately exit a loop even if the loop's condition is still true.

• The continue Function     * Stops the current iteration of a loop and immediately skips to the next iteration (returns to the top of the loop).

• The pass Function     * Acts as a placeholder. Since Python requires loop and selection bodies to contain at least one indented statement, pass allows for empty structures without triggering errors.

• Using else with Loops     * An else block after a while or for loop runs once when the loop's condition becomes False.

Practical Application Case Study: Pencil Calculation Program

• Problem: Calculate the minimum number of 12-pack pencil boxes needed so every student gets an equal amount with zero leftovers.

• Logic Steps:     1. Initialize boxes = 1.     2. Calculate pencils = 12 * boxes.     3. Iteration condition: Run as long as pencils % stu != 0 (where % is the modulus operator, checking for a remainder).     4. Inside loop: Increment boxes += 1, recalculate pencils = 12 * boxes.     5. Exit/Else: Print the value of boxes.

• Python Implementation (Modular):python stu = int(input("How many students? ")) boxes = 1 pencils = 12 * boxes while pencils % stu != 0: boxes += 1 pencils = 12 * boxes else: print("You need " + str(boxes) + " boxes.")