Algorithm Development Techniques PDF

BIT 157 INTRODUCTION TO STRUCTURED PROGRAM DESIGN LINDA AMOAKO BANNING, PhD  ALGORITHM DEVELOPMENT INTRODUCTION TECHNIQUES ALGORITHM DEVELOPMENT A step-by-step approach used in creating solutions to a specific problem. STEPS TO ALGOR...

BIT 157 INTRODUCTION TO STRUCTURED PROGRAM DESIGN LINDA AMOAKO BANNING, PhD  ALGORITHM DEVELOPMENT INTRODUCTION TECHNIQUES ALGORITHM DEVELOPMENT A step-by-step approach used in creating solutions to a specific problem. STEPS TO ALGORITHM DEVELOPMENT 1. Understand the problem ○ Clearly define the problem and identify all its components (inputs, outputs, processes, constraints) 2. Plan ○ Determine the most efficient approach STEPS TO ALGORITHM DEVELOPMENT 3. Design the Algorithm ○ Put together the sequence (solution) using pseudocode or flowcharts 4. Implement ○ Convert the algorithm into code 5. Test and Debug ○ Execute the code with test data to check for correctness TECHNIQUES FOR ALGORITHMS DEV’T Top-Down Design Bottom-up Design Structured Pseudocode  TOP-DOWN 1. DESIGN APPROACH 1. TOP-DOWN DESIGN Also known as the stepwise refinement Begins with the overall problem and progressively breaks it down into smaller subproblems (decomposition) until the last subprogram can be simple enough to be solved directly. PROCESS OF TOP-DOWN DESIGN Identify the main problem Divide the problem into general subproblems Refine each subproblem into smaller tasks Continue the refinement process until each task is simple enough to be considered as one step in the solution Implement the lowest level modules first and then integrate them into the higher modules. EXAMPLE OF TOP-DOWN APPROACH SORT AN ARRAY OF NUMBERS (Merge sort) ○ Divide the array into smaller parts ○ Sort each part separately ○ Merge the sorted parts EXXX: Write out the algorithm for sorting an array of numbers. ADVANTAGES OF TOP-DOWN APPROACH Easy to debug Reduces errors in solution Promotes modularity Promotes code reusability DISADVANTAGES OF TOP-DOWN APPROACH Requires extensive planning Might not be applicable for all problem types, e.g., exploratory problems Any small change to the parent problem may require a complete restructuring of the designed sub problems.  BOTTOM-UP 2. DESIGN APPROACH 2. BOTTOM-UP DESIGN Starts with solving the smallest and most basic components of the problem first, then combining them into larger modules until the complete system is built. Used often in object-oriented programming PROCESS OF BOTTOM-UP DESIGN Identify the smallest, most reusable components of the problem Develop and test these low-level modules first Integrate smaller components into larger subsystems Combine the subsystems to form the final solution EXAMPLE OF BOTTOM-UP DESIGN Sorting a list using bottom-up Merge-sort ○ Start by sortin gsmall parts of the array ○ Combine sorted pats interatively until the entire array is sorted ○ EXXX: Write out the algorithm ADVANTAGES OF BOTTOM-UP DESIGN It allows for the independent development of components It is very useful in OOP Promotes incremental development procedures Suitable for problems with unclear and undefined structures. DISADVANTAGES OF BOTTOM-UP DESIGN It is difficult to define how smaller modules will fit into the final system in the early stages of system development There can be inefficiencies if designed modules do not fit well together  DISCUSSION Compare and contrast Top-Down and Bottom-Up design approaches.  STRUCTURED 3. PSEUDOCODE APPROACH 3. STRUCTURED PSEUDOCODE APPROACH It focuses on writing algorithms using a clear, logical and structured format, very similar to actual programming. It ensures that the algorithm is easy to implement in a high-level programming language. KEY FEATURES OF STRUCTURED PSEUDOCODE APPROACH It follows a clearly-defined sequence of procedures It uses programming structures like selection, iteration and control It is very similar to natural language ADVANTAGES OF STRUCTURED PSEUDOCODE APPROACH It improves readability and clarity of the algorithm It makes transitioning to actual code easier It reduces the apparent complexity by structuring logic into modules  DISADVANTAGES OF STRUCTURED PSEUDOCODE APPROACH DISCUSS!  COMPARISON OF THREE APPROACHES FEATURE TOP-DOWN BOTTOM-UP STRUCTURED APPROACH APPROACH PSEUDOCODE Starting Point High-level problem Low-level modules Structured logic Development Style Breaks down into Builds up from Uses structured smaller parts small components control statements Best For Large, complex Modular, reusable Writing clear and problems needing component-based easy-to-follow logic clear hierarchy problems Main Challenge Integration of Designing Ensures logical subproblems components to fir consistency final system CONSTRUCTING A PSEUDOCODE Fundamental blocks include ○ Input/output – accepting and displaying data INPUT firstNumber; OUTPUT result ○ Conditionals – indicating decision points IF (hungry) eat, Else sleep ○ Loops – allowing iterative movements FOR; Do—Until; Do-While ○ Variables – storing and manipulating data CREATE, SET  WRITING EXAMPLES PSEUDOCODE EXAMPLE 1: ADDING TWO NUMBERS START INPUT number1, number 2 CREATE sum ADD number1, number2 STORE value in sum OUPTUT sum END EXPLANATION The “START” and “END” blocks define the area of the pseudocode The numbers to be added are accepted into the pseudocode using the construct “INPUT” “CREATE”, “ADD”, and “STORE” are used to indicate the operations and set the variables needed for the operation “OUTPUT” displays the final result obtained from the intended operation in the variable “sum”. EXAMPLE 2: EVEN OR ODD CHECKER BEGIN PRINT “Enter a number: “ READ number IF number MOD 2 == 0 THEN PRINT “The number is even” ELSE PRINT “The number is odd” ENDIF END SAMPLE EXERCISES 1. Find the largest of three numbers 2. Check if a number is prime 3. Convert temperature from Celsius to Fahrenheit 4. Calculate the sum of N natural numbers 5. Reverse a number 6. Check if a string is a palindrome 7. Find the GCD using the Euclidean Algorithm NEXT TOPICS Understanding Variables and Data Types Flow Charts Understanding Structure Modules END