GE8151 Unit I Algorithmic Problem Solving PDF

Preview

Summary

Notes for UNIT I...

Description

Regulation – 2017 GE8151 – Problem Solving and Python Programming Notes - Unit I – Algorithmic Problem Solving Syllabus Algorithms, building blocks of algorithms (statements, state, control flow, functions), notation (pseudo code, flow chart, programming language), algorithmic problem solving, simple strategies for developing algorithms (iteration, recursion). Illustrative problems: find minimum in a list, insert a card in a list of sorted cards, guess an integer number in a range, Towers of Hanoi. -----------------------------------------------***********-----------------------------------------------------

Problem Solving and Programming •

•

•

Computer programming is the craft of writing useful, maintainable, extensible source code which can be interpreted or compiled by a computing system to perform a meaningful task. Programming involves the activities such as analysis, developing, understanding, generating algorithms, verification of requirements of algorithms including their correctness and resource consumption, and implementation of algorithms in a target programming language. The purpose of the programming is to find sequence of instructions that will automate performing a specific task or solving a given problem.

Need for Logical Analysis and Thinking • Program Logic • Program Design • Programming Language Statements • Program documentation and maintenance Program Logic:  It is used to instruct a computer software program on how to perform a specific task properly.  This generally consists of identifying the inputs, activities, and outcomes. Program Design  Designing is a process that an organization uses to develop a program.  It requires three steps. They are algorithm, flowchart and pseudo-code.  Algorithm  step by step description of the solution  Flowchart  diagrammatic representation of the solution

1



Pseudo code  high level description of an algorithm and it uses the structured programming constructs. Program Language Statements  It is an instruction written in a high level language that commands the computer to perform a specified action. Program Documentation and Maintenance  Documentation is the information that describes the product to its users. It consists of the product technical manuals and online information.  Software Maintenance is the modification of a software product after delivery to correct faults, to improve performance or other attributes.  The program may require updating, fixing of errors, etc., during the maintenance phase.

Algorithm   

Algorithm is a step by step description for solving a problem. It is a well defined computational procedure consisting of a set of instructions that takes some value or set of values as input and produces some value or set of values as output. There is a time and space complexity associated with each algorithm. The time complexity specifies the amount of time required to perform a specific task. Space complexity specifies the size of memory required by the algorithm.

Building Blocks of Algorithm  Incoming information: The values or data that are needed to find the solution for a given problem. (input)  Step numbers: Positions in algorithm.  Control Flow: It is an order in which individual statements, instructions are evaluated.  Statements: It tells which data variable to update and in what manner.  Outgoing Information: The values or data that gives solution for the given input. (Output) Qualities of a Good algorithm  Time  Memory  Accuracy  Sequence  Generability Method for Developing an Algorithm  Define the problem: State the problem to be solved in clear and concise manner.  Problem Requirements: List the inputs and the outputs.  Manipulating Requirements: Describe the steps needed to convert from input to output.  Test the Algorithm: Choose the input data and verify how the algorithm works. Characteristics of an Algorithm 2

 In algorithm, each and every instruction should be precise and unambiguous.  The instruction in an algorithm should not be repeated infinitely.  Ensure that the algorithm will ultimately terminate.  The algorithm should be written in sequence.  It looks like normal English.  The desired result should be obtained only after the finite number of steps. Simple Strategies for developing algorithm  There are three control structures or basic building blocks of algorithm  They are Sequence, Selection and Iteration. Building Block Common Name Description Sequence Action Instructions are executed in sequential order Selection Decision or A decision is making a choice Branching among several actions (Condition checking) Iteration Looping or A loop is one or more Repetition instructions that the computer performs repeatedly.  Sequence Structure: o It is the most common form of control structure. o Each statement in the program is executed one after another in the given order.

o An algorithm to add two numbers entered by user: Step 1: Start Step 2: Declare variables a,b and c Step 3: Read values of a and b Step 4: Add a and b and assigns the result to c c=a+b Step 5: Display c Step 6: Stop 3

 Selection Structure: o The selection control structure is the representation of a condition and choice between two actions. o The choice made depends on whether the condition is true or false. It is also called a decision. o This structure is sometimes referred as if-then-else structure because it directs the program to perform in this way: if condition A is true then perform Action X else perform Action Y.

o An algorithm to check whether the given number is odd or even. Step 1: Start Step 2: Declare variable num Step 3: Read the values of num Step 4: IF num % 2 = = 0 THEN Display the given number is even ELSE Display the given number is odd Step 5: Stop  Iteration Structure: o This process is also called as repetition or looping o It carries out a particular action over and over again until some condition is met. o There are two ways of testing to see if the condition is met  Pre-test loops  Post-test loops o In pre-test loops, the condition is tested at the beginning of the loop. If the condition fails, the looping process will never carried out. Here the loop is operated only when the condition is met. Pre-test loops ends when the condition fails. o In post-test loops, the condition is tested at the end of the loop. The looping process is executed first whether the condition is true or false and will keep repeating until the condition is met. This loop ends when the condition is true.

4

o Algorithm to find factorial of a given number Step 1: Start Step 2: Declare variables fact, I and n. Step 3: Initialize the variable fact  1 and i  1 Step 4: Read value of n. Step 5: Repeat the following steps until i=n+1 fact  fact * i ii+1 Step 6: Display fact Step 7: Stop Advantages of algorithm 1. It is a step-wise description of a solution to a given problem, which makes it easy to understand. 2. It uses a definite procedure to solve a problem. 3. It is not dependent on any programming language, so it is easy to understand for anyone even without programming language. Disadvantages of algorithm 1. It is not a computer program; it is rather a concept of how the program should be written. 2. It is time consuming, an algorithm needs to be developed first, which is then converted into flowchart and then into a computer program. 3. It is difficult to show branching and looping statements.

Flowchart 

A flowchart is a graphical or symbolic representation of a process. Each step in the process is represented by a different symbol and contains a short description of the process step. Types of Flowchart  Flowcharts can be used for a variety of purposes in manufacturing, architecture, engineering, business, technology, education, science, medicine, government, administration and other discipline areas.  There are a wide variety of flowchart types: 5

o Swim lane Flowcharts o Data flow Diagrams o Workflow Diagrams o Influence Diagrams Need for Flowchart  The process can be explained clearly through symbols and text in flowcharts.  Every programmer uses the same basic symbols, so that others can easily read and interpret the logic of a program.  It provides effective program documentation and maintenance.  While preparing flowchart the sequence, selection or iterative structure can be used whenever needed.  In flowchart, logic of the program is communicated in a much better way than algorithms  It is easier to understand than narrative description of algorithm. Flowchart symbols  It utilizes specialized symbols. S.No Name of the Symbol Symbol Description 1 Terminator Represents the start and stop of program 2 Input/Output Denotes either input or output operation 3 Process Symbol Denotes the process to be carried out 4 Decision Represents decision making and branching statements 5

Flow lines

6

Connectors

7

Document

Represents the sequence of steps and direction of flow. Used to connect symbols It is off page connector which is used to connect different flow lines Indicates data that can be read by people, such as printed output.

Basic guidelines for preparing flowchart 1. In drawing proper flowchart, all necessary requirements should be listed in logical order. 2. The flowchart should be clear, neat and easy to follow. 3. The direction of flow of a procedure or system should always start from top to bottom or from left to right.

6

4. Only one flow line should come out from a process symbol. 5. Only one flow line should enter a decision symbol. However, two or three flow lines, one for each possible solution, may leave the decision symbol.

6. Only one flow line is used in conjunction with terminal symbol.

7. The description of each process must be written within the standard symbols. If necessary, we can use the annotation symbol to describe the data or computational stepes more clearly. 8. For more complex problems, it is better to use connector symbols to reduce the number of flow lines in flowchart. 9. Intersection of flow lines should be avoided to make it more effective. 10. The flowchart should have a logical start and stop. 11. The validity of the flowchart should be tested by means of giving normal or unusual test data. Advantages of using flowchart 1. Communication: Flowcharts provides a better way for communicating the logic of a system. 2. Standard Symbols: The use of standard symbols improves flowchart readability. 3. Proper Documentation: It serves as a program documentation to know what the program actually does and how to use the program. 4. Efficient Coding: It acts as a guide or blueprint during the system analysis and program development phase. 5. Visual Clarity: It has the ability to visualize the multiple progress and their sequence into a single document.

7

Disadvantages of using flowchart 1. Complex Logic: In case of complex problems, flowcharts tend to continue for many pages, making them hard to follow. 2. Alterations and modifications: If alterations are required, it can be difficult to modify. 3. Reproduction: The symbols in flowchart cannot be typed. 4. Confusion: Excessive use of connectors will confuse the programmers. So the cost of operation becomes high. 5. No updates: Programs are updated regularly. It does not takes place expecially in the case of large programs. Example: Sequence Structure Draw a flowchart to find product of two numbers A and B.

8

Example: Selection Structure Draw a flowchart to find the entered number is odd or even.

Example: Iteration Structure Draw a flowchart to find the factorial of a given number.

9

Pseudo-code       

Pseudo means “false of imitation” and code means “instructions” written in programming language. It is not a real programming code written in English but it models, even look like programming codes. It is an outline of a program written in a form that can be easily converted into real programming statements. The goal of writing pseudo code is to provide high level description of an algorithm. Once the pseudo code is accepted, it is transformed into real programming code. Pseudo code uses some keywords to denote programming process. They are: o Input: READ, OBTAIN, GET, PROMPT o Output: PRINT, DISPLAY, SHOW o Compute: COMPUTE, CALCULATE, DETERMINE o Initiate: SET, INITIALIZE o Add one: INCREMENT

Basic guidelines of Pseudocode 1. Statement should be written in English and programming language independent. 2. It should describe the logical plan to develop a program. 3. Steps must be understandable and it should not be difficult. 4. Each instruction should be written in sequence. 5. Keywords must be capitalized. 6. Each set of instruction must be written from top to bottom. 7. It should be easy for translating the design code into code in any programming language. Advantages of Pseudocode 1. It is language independent; it can be used by most of the programmers. 2. It becomes easy to develop a program based on a pseudocode rather than with a flowchart. 3. It is compact and easy to modify. Disadvantages of Pseudocode 1. It does not provide visual representation of the programs logic. 2. No accepted or standard rules for writing pseudocode. 3. It is not used to understand the flow of the program control. 4. It cannot be compiled nor executed.

10

Example: Sequence Structure Pseudocode to find the product of two number A and B. START Program Use variables A, B, and C DISPLAY “Enter the values of A and B READ A, B CALCULATE C = A * B PRINT “The Result is: “ C END Program Example: Selection Structure Pseudocode to find the entered number is odd or even. START Program Use variable n DISPLAY “Enter the value of n” GET n DETERMINE IF n % 2 = = 0 THEN DISPLAY “The given number is Even” ELSE DISPLAY “The given number is Odd” END Program Example: Iteration Structure Pseudocode to find the factorial of a given number. START Program Use variables fact, i, and n SET fact1 and i 1 DISPLAY “Enter the value of n” COMPUTE the following fact fact * i i  i+1 UNTIL i=n+1 PRINT “The factorial of given number: “, fact END Program ----------------------------------------------------------*********---------------------------------------------

11...