Figure 2.9: The Sequential Search Algorithm Task 1: Sequential Search Algorithm Initialization block Iteration block; the key step where most of the work is done Post-Processing block
Algorithms Problem Solving Readings: [SG] Ch. 2 Chapter Outline: Chapter Goals What are Algorithms Pseudo-Code to Express Algorithms Some Simple Algorithms [SG] Ch. 2.3 Computing Array-Sum Structure of Basic Iterative Algorithm Examples of Algorithmic Problem Solving
Simple iterative algorithm: Array-Sum(A,n)
Input: List of numbers: A1, A2, A3, …., An Output: To compute the sum of the numbers Note: Store numbers in array A[1], A[2], … , A[n] Array-Sum(A, n); (* Find the sum of A1, A2,…,An. *) begin Sum_SF 0; k 1; while (k <= n) do Sum_SF Sum_SF + A[k]; k k + 1; endwhile Sum Sum_SF; Print “Sum is”, Sum; return Sum; end; Sum_SF represents the Sum-So-Far Click to see alg. animation
Structure of “basic iterative algorithm” Array-Sum(A, n); (* Find the sum of A1, A2,…,An. *) begin Sum_SF 0; k 1; while (k <= n) do Sum_SF Sum_SF + A[k]; k k + 1; endwhile Sum Sum_SF; Print “Sum is”, Sum end; Name of Algorithm Parameters: A and n Some comments for human understanding Initialization block Iteration block; the key step where most of the work is done Post-Processing block Structure of Basic iterative algorithm Recall Recurring Principle: The Power of Iterations
Re-use of “basic iterative algorithm”
Once an algorithm is developed, Give it a name (an abstraction): Array-Sum(A,n) It can be re-used in solving more complex problems It can be modified to solve other similar problems Modify algorithm for Array-Sum(A,n) to… Calculate the average and sum-of-squares Search for a number; find the max, min Develop a algorithm library A collection of useful algorithms An important tool-kit for algorithm development
Algorithms (Introduction) Readings: [SG] Ch. 2 Chapter Outline: Chapter Goals What are Algorithms Pseudo-Code to Express Algorithms Some Simple Algorithms Examples of Algorithmic Problem Solving [Ch. 2.3] Searching Example, Finding Maximum/Largest Modular Program Design Pattern Matching
Algorithmic Problem Solving
Examples of algorithmic problem solving Sequential search: find a particular value in an unordered collection Find maximum: find the largest value in a collection of data Pattern matching: determine if and where a particular pattern occurs in a piece of text
Task 1: Looking, Looking, Looking…
Task Find a particular person’s name from an unordered list of telephone subscribers Algorithm outline Start with the first entry and check its name, then repeat the process for all entries
Task 1: Looking, Looking, Looking…
Sequential search algorithm Re-use the basic iterative algorithm of Sum(A,n) Refers to a value in the list using an index i (or pointer/subscript) Uses the variable Found to exit the iteration as soon as a match is found Handles special cases like a name not found in the collection Question: What to change in Initialization, Iteration, Post-Processing?
Figure 2.9: The Sequential Search Algorithm Task 1: Sequential Search Algorithm Initialization block Iteration block; the key step where most of the work is done Post-Processing block
Algorithm Sequential Search (revised)
Seq-Search(N, T, m, NAME); begin i 1; Found No; while (Found = No) and (i <= m) do if (NAME = N[i]) then Print T[i]; Found Yes; else i i + 1; endif endwhile if (Found=No) then Print NAME “is not found” endif end; Preconditions: The variables NAME, m, and the arrays N[1..m] and T[1..m] have been read into memory. Initialization block Iteration block; the key step where most of the work is done Post-Processing block
Note the differences…
Seq-Search () is a high-level primitive It takes in something as input, Computes something, Return some computed values. Seq-Search N, T m NAME Found
Task 2: Big, Bigger, Biggest
Task: Find the largest value from a list of values Algorithm outline Keep track of the largest value seen so far Initialize: Set Largest-So-Far to be the first in the list Iteration: Compare each value to the Largest-So-Far, and keep the larger as the new largest Use location to remember where the largest is. Initialize: … (Do it yourself) Iteration: …. (Do it yourself)
Figure 2.10: Algorithm to Find the Largest Value in a List Task 2: Finding the Largest Initialization block Iteration block; the key step where most of the work is done Post-Processing block
Algorithm Find-Max
Find-Max(A,n); (* find max of A[1..n] *) begin Max-SF A[1]; Location 1; i 2; (* why 2, not 1? *) while (i <= n) do if (A[i] > Max-SF) then Max-SF A[i]; Location i; endif i i + 1 endwhile Max Max-SF; return Max, Location end; Preconditions: The variable n and the arrays A have been read into memory. Initialization block Iteration block; the key step where most of the work is done Post-Processing block
Modular Program Design
Software are complex HUGE (millions of lines of code) eg: Linux, Outlook COMPLEX; eg: Flight simulator Idea: Divide-and-Conquer Method (or decomposition) Complex tasks can be divided and Each part solved separately and combined later. Modular Program Design Divide big programs into smaller modules The smaller parts are called modules, subroutines, or procedures Design, implement, and test separately Modularity, Abstraction, Division of Labour Simplifies process of writing alg/programs
Task 3: Pattern Matching
Algorithm search for a pattern in a source text Given: A source text S[1..n] and a pattern P[1..m] Question: Find all occurrence of pattern P in text S? C A T A T C A T A S 1 2 3 4 5 6 7 8 9 A T A P 1 2 3 Output of Pattern Matching Algorithm: There is a match at position 2 There is a match at position 7
Example of Pattern Matching
A T A P 1 2 3 k Align pattern P with text S starting at pos k = 1; Check for match (between S[1..3] and P[1..3]) Result – no match C A T A T C A T A S 1 2 3 4 5 6 7 8 9
Example of Pattern Matching
A T A P 1 2 3 k Align pattern P with text S starting at pos k = 2; Check for match (between S[2..4] and P[1..3]) Result – match! Output: There is a match at position 2 C A T A T C A T A S 1 2 3 4 5 6 7 8 9
Example of Pattern Matching
A T A P 1 2 3 k Align pattern P with text S starting at pos k = 3; Check for match (between S[3..5] and P[1..3]) Result – No match. C A T A T C A T A S 1 2 3 4 5 6 7 8 9
Comments