Sequential Search and List Extremes: Principles of Computer Science Algorithm Discovery

Algorithm Discovery and Design Fundamentals\n\n- Algorithm Discovery: Finding a solution to a given problem. This is considered the most challenging and creative part of the problem-solving process.\n- Design Strategy: A common strategy for algorithm discovery is to determine how the same problem would be solved manually by hand. If a manual solution can be understood and explained, it can often be expressed as a formal algorithm.\n- Influence of Data Organization: A critical concept in algorithm design is that the selection of an algorithm to solve a problem is greatly influenced by the way the input data is organized (e.g., whether a list is sorted or unordered).\n- Algorithm Correctness: An algorithm is deemed correct only when it produces the correct result for all possible cases, including edge cases.\n- Efficiency and Elegance: Computer scientists aim for algorithms that are not only correct but also efficient (performing tasks in a reasonable amount of time or steps) and elegant (being well-structured and concise).\n\n# The Sequential Search Algorithm\n\n- Problem Definition (Reverse Telephone Lookup): Given a phone number ($NUMBER$), find the name associated with it in a list of $10,000$ pairs of numbers ($T_1, T_2, ..., T_{10,000}$) and names ($N_1, N_2, ..., N_{10,000}$).\n- The Moving Finger Metaphor: The variable $i$ acts as an index or pointer into the list, resembling a \"moving finger\" scanning the telephone numbers and pointing to the one the algorithm is currently evaluating.\n- Inefficient First Attempt (Figure 2.11): Initial designs without iteration would require writing $10,000$ separate conditional statements. This would take roughly $150$ pages at $66$ lines per page, be highly inefficient (continuing to check after finding the answer), and would be incorrect if the number is missing from the list.\n- Refined Sequential Search (Figure 2.13):\n - Step 1: Get values for $NUMBER$, $T_1, ..., T_{10,000}$, and $N_1, ..., N_{10,000}$.\n - Step 2: Set the value of $i$ to $1$ and set the value of $Found$ to $NO$.\n - Step 3: While both ($Found = NO$) and ($i \\le 10,000$) do Steps 4 through 7.\n - Step 4: If $NUMBER$ is equal to the $i^{th}$ number on the list, $T_i$, then…\n - Step 5: …Print the name of the corresponding person, $N_i$.\n - Step 6: …Set the value of $Found$ to $YES$.\n - Step 7: Else (if $NUMBER$ is not equal to $T_i$), add $1$ to the value of $i$.\n - Step 8: If ($Found = NO$) then…\n - Step 9: …Print the message 'Sorry, this number is not in the directory'.\n - Step 10: Stop.\n- Scalability: If the phone book contained $1,000,000$ or even $1,000,000,000$ numbers, only two lines would require modification: those defining the input size (Line 1) and those defining the loop limit (Line 3).\n\n# Finding the Largest Value in a List\n\n- Problem Definition: Given a value $n \\ge 1$ and a list of unique numbers $A_1, A_2, ..., A_n$, find and print the numerically largest value and its position (location) in the list.\n- Informal Strategy: Initially assume the first item is the largest. Compare this against subsequent items. If a new item is larger, replace the stored maximum with this new value and update its recorded position. Discard values that are smaller.\n- Metaphorical Example: Imagine a pile of papers with numbers ($19, 41, 12, 63, 22$). If the current \"largest so far\" is $19$ and the next is $41$, discard $19$ and keep $41$. If the next is $12$, discard it and keep $41$. This continues until the pile is empty.\n- Detailed Formal Algorithm (Figure 2.14):\n - Input: Get a value for $n$ (size of list) and values for $A_1, A_2, ..., A_n$.\n - Initialization: Set the value of $\text{largest so far}$ to $A_1$. Set the value of $\text{location}$ to $1$. Set the value of $i$ to $2$.\n - Execution Loop: While ($i \\le n$) do:\n - If A_i > \\text{largest so far} then:\n - Set $\text{largest so far}$ to $A_i$.\n - Set $\text{location}$ to $i$.\n - Add $1$ to the value of $i$.\n - Termination: Print out the values of $\text{largest so far}$ and $\text{location}$. Stop.\n- Logic Note: The index $i$ starts at $2$ because the first item ($A_1$) is already used as the initial baseline. The continuation condition ($i \\le n$) ensures the loop finishes after the entire list is searched.\n\n# Building Blocks and Libraries\n\n- Building-Block Concept: Once an algorithm is developed, it can be used as a primitive operation in constructing more complex algorithms. For example, the Find Largest algorithm is a building block for sorting an unordered list into ascending order.\n- Libraries: These are collections of useful, prewritten algorithms. They are essential tools for algorithm design because they allow developers to build on existing results rather than starting from absolute basic primitives (sequential, conditional, iterative) every time.\n\n# Multiplication via Repeated Addition\n\n- Basic Concept: Multiplication of two non-negative integers $a$ and $b$ can be achieved by adding the value of $a$ to a running total $b$ times.\n- Initial Multiplication Algorithm (Figure 2.10):\n - Get values for $a$ and $b$.\n - If (either $a = 0$ or $b = 0$) then set $product$ to $0$.\n - Else, set $count$ to $0$ and $product$ to $0$.\n - While (count < b) do:\n - Set $product$ to ($product + a$).\n - Set $count$ to ($count + 1$).\n - Print the value of $product$ and Stop.\n- Efficiency Fixes: Without the initial check for $a = 0$ or $b = 0$, the algorithm would still find the correct answer of $0$, but it might do so through thousands of unnecessary additions (e.g., adding $0$ to a sum $5,386$ times if $b = 5,386$).\n- Handling Negative Numbers: The standard algorithm fails if b < 0 because the condition (count < b) is immediately false. To fix this:\n - Set a boolean flag $\text{bnegative}$ to $NO$.\n - If b < 0, set $b = -b$ and set $\text{bnegative}$ to $YES$.\n - Calculate the product using the absolute value of $b$.\n - If $\text{bnegative} = YES$, the final result is $-product$.\n- Algorithm Limitation Warning: The text suggests adding a check: if a > 10,000 or b > 10,000, display a message suggesting the use of a more efficient multiplication algorithm (like the traditional grade school method) instead of repeated addition.\n\n# Questions & Discussion\n\n- Q: What parts of the sequential search of Figure 2.13 change if the list is 1 million vs 10,000?\n- A: Only Line 1 (to input 1 million names/numbers) and Line 3 (to change the loop limit to 1 million) would need to be changed.\n\n- Q: How does the choice of data organization influence search?\n- A: Humans don't turn every page for a phone number because they exploit the numerical or alphabetical order. In a sorted reverse directory, one can start in the middle based on the first digit and move quickly, which is much faster than sequential search.\n\n- Q: Is repeated addition efficient for multiplication?\n- A: No, it is highly inefficient compared to grade-school multiplication because of the sheer number of operations required (e.g., adding $234$ to a total $567$ times).", "title": "Sequential Search and List Extremes: Principles of Computer Science Algorithm Discovery"}