Software Development Unit 1 - Introduction to Algorithm PDF

SOFTWARE UNIT 1 – INTRODUCTION TO ALGORITHM DEVELOPMENT Edition 01, August 2021 This learning material relates to BCS Syllabus July 2021, and covers Level 4 Certificate in IT examinations f...

SOFTWARE UNIT 1 – INTRODUCTION TO ALGORITHM DEVELOPMENT Edition 01, August 2021 This learning material relates to BCS Syllabus July 2021, and covers Level 4 Certificate in IT examinations from October 2021 to October 2022  SOFTWARE DEVELOPMENT UNIT 1 INTRODUCTION TO ALGORITHM What is Algorithm? An algorithm is a set of instructions that tells a computer how to transform a set of facts about the world into useful information. The algorithm needs to be executed in a particular order for producing the proper information. In general, every process follows some algorithm. We can give a lot of common examples of algorithms like, sorting a set of numbers or names, finding routes through maps, displaying information on a screen. Algorithms can simply be defined as a set of instructions that are followed step by step to accomplish a goal or solve a problem. They can be thought as mini-instruction manuals that tell computers how to execute a task or manipulate a given data. Any computing problem can be solved by doing a sequence of actions in a particular order. A procedure for solving a problem in terms of 1. the actions to be carried out, and 2. the order in which these actions are to be executed is considered as an algorithm. You can think about making a dessert as an example of algorithm. If you are explaining this to a new a person who don’t know how to prepare, what will you do? You will be explaining each step in detail, isn’t it? This is an example of algorithm. One important thing in the algorithm is the order of execution of the actions. If the actions are executed in the order which is different from the specified order, then the outcome of the algorithm will be different, or sometimes it may not produce any output. The following example illustrates the importance of order of actions in the algorithm. For instance, consider the routine of a normal person from getting out of bed to reaching office. a. Get out of bed, b. brush, c. remove dress, d. take shower, Published September 2021 ©Bauhaus Educational Services Ltd All rights reserved BCS HEQ – Software Development | 1  e. gets dressed, f. have breakfast. g. gets into car and drives to office This routine makes the person reach well at the office. Suppose the set of actions are done in a slightly different manner. a. Get out of bed, b. brush, c. remove dress, d. gets dressed, e. take shower, f. have breakfast. g. gets into car and drives to office Here the person will be showing up at office with wet dress. In this case, the order of only two actions is disturbed, which made the whole outcome strange. Similar is the case of computer programs. Defining the order of execution of actions or statements in a computer program is called program control. Input: In computer terms, input is the data or information that needed to make a decision. For the above example what are information needed? We need different information in each step. When you take a shower, what are the information you needed? You may be considering the temperature outside to bath with hot or cold water. You can consider the brand of the shower gel you use. The information is different for the other step: like when you get dressed. You should consider what cloths are available in your wardrobe. Then you may check the weather prediction for the day to choose a dress. Also, you might be having some personal preferences. This all information can be represented in data, which can be a collection of words of numbers. Temperature, for example, is a number, while a weather forecast might say "rainy" or "sunny." Transformation Next comes the heart of an algorithm – computation. Computations involve arithmetic, decision-making and repetition. Published September 2021 ©Bauhaus Educational Services Ltd All rights reserved BCS HEQ – Software Development | 2 So how does the computation work in taking the shower. You will decide on hot water or cold water by applying some math on those input quantities. If the temperature is cold, then you might be choosing the hot water. The same logic is applied to a computer. This taking shower algorithm would look like “if the temperature is below 25 degrees, shower with hot water, else shower with cold water.” After choosing the type of water you have to take shower. Pour water, applying gel, massage and then repeat. Repetition is an important part of an algorithm. Output The final step of an algorithm is output. How do you express your outcome or answer? The output is usually a data as input. The output of an algorithm is sometimes the input for another algorithm. Computers make complex algorithms to achieve a complex task just by combining the small ones. However, output can also refer to the act of providing information, such as displaying text on a computer, creating audible cues, or engaging in some other sort of communication. So, after getting dressed, you go out into the world, bracing yourself for the elements and the stares of onlookers. Some Examples of Algorithm First let us consider an algorithm to add two numbers: 1. Take two number inputs 2. Add numbers using the + operator 3. Display the result Although it looks simple and obvious, each step is important in the algorithm. So let’s do another example to Find the largest number among three numbers Step 1: Start Step 2: Declare variables a, b, and c. Step 3: Read variables a, b, and c. Step 4: If a > b If a > c Display a is the largest number. Published September 2021 ©Bauhaus Educational Services Ltd All rights reserved BCS HEQ – Software Development | 3  Else Display c is the largest number. Else If b > c Display b is the largest number. Else Display c is the greatest number. Step 5: Stop The same problem can be done in different ways. So, the algorithm will determine in which way you are going to code your program. Let us look at another algorithm for finding the largest of three numbers. Step 1: Start Step 2: Declare variables a, b, and c. Step 3: Read variables a, b, and c. Step 4: Initialise max with a Step 5: if b > max then assign b to max Step 6: if c > max then assign c to max Step 7: display max as the largest Step 8: Stop. Next let us write an algorithm to find the factorial of a number Step 1: Start Step 2: Declare variables n, factorial and i. Step 3: Initialize variables factorial ← 1 i←1 Step 4: Read value of n Step 5: Repeat the steps until i = n 5.1: factorial ← factorial*i 5.2: i ← i+1 Published September 2021 ©Bauhaus Educational Services Ltd All rights reserved BCS HEQ – Software Development | 4  Step 6: Display factorial Step 7: Stop Preparing a Computer Program The steps in preparing a computer program involve: 1. Study the requirement specification for the application. 2. Problem analysis and decision making: decide on what algorithm should use 3. Producing the source code (source program) from the algorithm used in the previous step by using the proper programming language. 4. Compile the program into machine-language or object code. Compiler is a program which translates the program written in programming language to object code. The compiler will spot out the syntax errors in the code. It should be corrected to proceed further. The correction and compilation is done repeatedly, until the code is free from any syntax error. The compiler will produce an executable program to run the program which is called object code or machine code. A run-time error will cause the program to halt during execution because it cannot carry out an instruction. 5. Run the program: The program will be running with test data which will then detect the logical errors. These errors occur due to the incorrect method of implementation. So, the logically incorrect statements are syntactically correct, but it is doing some incorrect methods to find the solution which is not applicable to the current situation. It is the programmers who identify the logical errors from the sample input and sample output. 6. The program can now be put into general use. DEFINITION OF SOME FUNDAMENTAL CONCEPT OF SOFTWARE DEVELOPMENT Before we go further in the design and analysis of algorithms, there are a number of related concepts that need to be defined. Published September 2021 ©Bauhaus Educational Services Ltd All rights reserved BCS HEQ – Software Development | 5 Program: A program is a collection of instructions that lead a computer to operate in a specific predetermined way. Programs are the key factors that makes the computer distinct, where we can say that without program computers are useless. A program is comparable to a recipe where the list of ingredients are variables, and the directions are statements that instructs the computer how to operate on variables. The variables are not limited to numbers, they can represent text, numeric data, or graphical images. There are mainly two different types of programming languages: high-level languages and low-level languages. High-level languages are more like human languages which are easier to understand. C, C++, Python, and Java are just a few. Low-level languages, also called assembly languages, are closer to computer language which makes it difficult to understand. Every program written in any language must be translated to machine language which is the only language that computer can understand. The translation of programming language is done by compilers, interpreters, and assemblers. You get an executable version of the software when you are buying it. This executable file is a file in machine language where the programs have already been compiled and assembled. Statement: A statement is an instruction written in a high-level language. A statement directs the computer to perform a specified action. A single statement in a high-level language can represent several machine-language instructions. Programs consist of statements and expressions. An expression is a group of symbols that represent a value. Expression: An expression in programming is any legal combination of symbols that represents a value. Here the term legal refers to the rules of the programming language or application. Each programming language has its own rules to define legal and illegal. Every expression consists of two components which are operands and operators. Operands are values, while the operators are the symbols that defines some particular action. Expression should have at least one operand and one operator. For instance, Published September 2021 ©Bauhaus Educational Services Ltd All rights reserved BCS HEQ – Software Development | 6 y+2 is an expression in python. Here y and 2 are operands, and the symbol ‘+’ is an operator which indicates addition. Programming languages, database systems, and spreadsheet programmes all use expressions. In database systems, for example, expressions are used to describe the data you want to retrieve. These expressions are called queries. The type of value that expressions represent is used to classify them. For example: Boolean expressions: Evaluate to either TRUE or FALSE integer expressions: Evaluate to whole numbers, like 3 or 100 Floating-point expressions: Evaluate to real numbers, like 3.141 or -0.005 String expressions: Evaluate to character strings Introduction to programming Now let us start writing codes in python. Printing a line of text print(“Hello, World!”) Printing a variable x = 10 print(x) Here the first statement assigns a value to the variable x and the second line prints the value of the variable. y = “Hello Everyone!” print(y) Comments #This is a comments print(“The comment does not affect your program”) Published September 2021 ©Bauhaus Educational Services Ltd All rights reserved BCS HEQ – Software Development | 7 Saving your program: Go to “File” again and select “Save As.” Name your file “hello_world.py” and save it. Data types As we discussed before, the program consists of some instructions which operates on some data. The data used in the programming is classified by its data type. Data types are the factors that tells the compiler or interpreter how to work on the data. In python, each data value is called an object. For example, 5 or “Good morning” are objects. Here “Good morning” is an object with data type string (or str as short), and its value is “Good morning”. A string is a set of one or more characters which is enclosed by quotes. You can use single quotes or double quotes. For example: “Good morning” ‘Good morning’ For numbers, there are two data types handling whole numbers and decimal numbers. The data type int, which is a short form of integer, is used for whole numbers in python. Decimal or fractional numbers have a data type called float. The numbers 2, 5, and 20 are some examples of objects with data type int. The numbers 1.5, 15.3, 0.99 and 5.1 are some examples of objects with data type float. E.g.: 1.2+2.3 >>3.5 Objects with a bool data type have a value of either True or False and are called Boolean. To represent the absence of a value, the objects with data type NoneType are used, and these objects will always have the value none. Constants and Variables Published September 2021 ©Bauhaus Educational Services Ltd All rights reserved BCS HEQ – Software Development | 8 A constant is a value that never changes. 3+5 >> 8 The numbers 3 and 5 in this example are constants: the number three will always represent the value 3 and the number five will always represent the value 5. However, the variable refers to the value that can change. A variable has a name and a value. The name of the variable consists of one or more characters and numbers. The rule for naming of any variable is dependent on the programming language you use. Then this name is assigned to some value using the assignment operator which is ‘=’ symbol. In some programming language the developers have to declare the variable with data type for making the computer clear about the data type of the variable. In contrast, python doesn’t require the declaration of variable. You can create a variable just by assigning any value to the variable. There is no need for explicitly mentioning the data type. For example: x= 10 The above statement will create a variable with name x and value 10. The data type of above variable will be int as the value is an integer number. On the other hand, in C or C++ you should declare the variable with data type as follows: int a; char character; Here the variable a has data type int and the variable character has data type char. Arithmetic Operators We can use variables for the mathematical operations Published September 2021 ©Bauhaus Educational Services Ltd All rights reserved BCS HEQ – Software Development | 9 Apart from four basic arithmetic operations, there are other three operations which are exponent, modulo, and integer division. When dividing a number with another number, you will get result (which is quotient) and reminder (which is reminder). The modulo operation returns the reminder when two numbers are divided. E.g.: when we do 14/4 the quotient is 3 and remainder is 2. So, 14%4 gives you 2. In python, there is two types of division: integer division and division. The former returns the quotient of division and the later returns the result as decimal point number. The operator / is used for normal division and // is used for integer division. x = 20 y = 10 a = x + y # answer is 30 b = x - y # answer is 10 c = x * y # answer is 200 d = x / y # answer is 2 p=5 q=2 r = p // q # answer is 2 s = p % q # answer is 1 t = p ** q # answer is 25 Published September 2021 ©Bauhaus Educational Services Ltd All rights reserved BCS HEQ – Software Development | 10 The value of a variable can be changed during the execution of the program. The value can be incremented or decremented using the following statements. # incrementing x by 10 x = x + 10 # decrementing x by 5 x=x-5 Shorthand operators There are some shorthand methods to do the arithmetical operations. # incrementing x by 1 x += 1 # incrementing x by y x += y # decrementing x -= 1 x -= y # multiplication x *= 2 # division x /= 5 Comparison Operators Comparison operators are similar to arithmetic operators; they are operators used in expressions with operands on either side. The expressions with arithmetic operators evaluate to some results in numbers. In contrast, expressions with comparison operators evaluate to boolean values True or False. Published September 2021 ©Bauhaus Educational Services Ltd All rights reserved BCS HEQ – Software Development | 11 Logical Operators Logical operators take two expressions and return true/ false. CONTROL STRUCTURES Computer programs consists of program statements which follow some particular logic. Control structures are the commands which can be considered as the building blocks of the program. These commands lead the program to make any decision and forward the execution to some path over the other. They specify the flow of control in the program. Normally, a program can have different types of execution style. Sometimes they follow the linear sequence order, sometimes they bypass the code, sometimes they repeat some sections. Control structures analyse the variables and data, then it decides the direction of the program execution based on the given parameters. Any algorithm or program can be clearer and more understood if they use self-contained modules called as logic or control structures There are three basic types of logic, or flow of control, known as: 1. Sequence logic, or sequential flow Published September 2021 ©Bauhaus Educational Services Ltd All rights reserved BCS HEQ – Software Development | 12  2. Selection logic, or conditional flow 3. Iteration logic, or repetitive flow Sequence This is the basic control structure which follows the linear order. The program statements are executed in the order they are written. This is called sequential execution. Sometimes the next statement to be performed may not be the one after the previous one. It transfers the control to other statements which is called transfer of control. In the sequence logic the statements are executed one after the other in the order in which they are written. In some cases, they transfer the control to some other statements. As the name indicates, the sequential flow executes the statements in sequential or serial manner. The modules are performed in the obvious order unless new instructions are given. Sequences can be specified directly using explicitly numbered steps. The majority of the processing including some complex problems will follow this basic pattern of execution. The following is the basic flow diagram of the sequential logic where each module is executed in the serial order. For example, consider a program for adding two numbers. x=10 y=5 sum = x+y Published September 2021 ©Bauhaus Educational Services Ltd All rights reserved BCS HEQ – Software Development | 13  print(sum) It assigns values to two variables x and y, then calculates the sum of the numbers by adding the variables. Then it prints the sum. Here the statements are executed in the order they are written. These blocks of code follow the sequence structure. The following code works same as the above code. The only difference here is the following code accepts the numbers from the keyboard. In the previous case, the two numbers were hard coded. x=int(input("Enter the first number")) y=int(input("Enter the second number")) sum = x+y print(sum) Here the first two lines are input statements. The function input() accepts the inputs from the input device keyboard. All the inputs are considered to be strings. So we have to explicitly mention those to numbers by using int(), double(), float() functions. When you are mentioning the input as integer by using int(), it will give value error if the user input decimal numbers. Selection Selection logic decides the flow of execution based on the conditions or parameters. It simply selects some module out of other written modules. The control structure which uses the selection logic are called conditional structures. There are three types of conditional structures: 1. Single Alternative 2. Double Alternatives 3. Multiple Alternatives Single Alternative: This structure has the form: If (condition) then: [Module A] [End of If structure] Double Alternative: This structure has the form: If (Condition), then: [Module A] Else: Published September 2021 ©Bauhaus Educational Services Ltd All rights reserved BCS HEQ – Software Development | 14  [Module B] [End if structure] Multiple Alternatives: This structure has the form: If (condition A), then: [Module A] Else if (condition B), then: [Module B].... Else if (condition N), then: [Module N] [End If structure] The single, double, and multiple alternative selection structures are obtained by three programming statements which are if, if…else, and switch statements. The if statement selects an action based on the condition. If the condition is true, it selects Published September 2021 ©Bauhaus Educational Services Ltd All rights reserved BCS HEQ – Software Development | 15 the statement, otherwise it skips that statement. This simple if statement implements the single alternative selection. On the other hand, the if…else statements work as double alternative selection. It executes some action if the condition evaluated to true, otherwise it executes some other action. This is called double alternative because, it selects one action from the two options based on the condition. The final multiple alternatives are implemented using switch statements or if…else if statements. These have multiple conditions, and an action is selected from the different options based on each condition. CONDITIONAL STATEMENTS In python the keywords used for conditional statements are if, elif, and else. The conditional statements are the main reason for the program to behave differently in different scenarios. It analyses the variables and makes the decision from the value of the variable based on some condition. Here is the pseudo code for conditional statement If (expression) then (code a) The following is the pseudo code for the if else conditional statement. If (expression) then (code a) else (code b) The pseudo code explains that if the expression evaluates to true, then the codes in code a will execute. And if the expression evaluates to false the code a will be skipped, and code b will execute. # conditional statements if price>100 : print(“item is expensive”) else : print(“item is economical”) You can even put an if statement inside of another if statement. This is called nesting. Published September 2021 ©Bauhaus Educational Services Ltd All rights reserved BCS HEQ – Software Development | 16  # nested if If number % 2 == 0 : If number % 5 == 0 : print(“number is divisible by 10”) else : print(“number is divisible by 2”) else : print(“number is not a multiple of 2”) if elif if score >= 90 : print(“your score is excellent”) elif score >= 70 : print(“your score is good”) elif score >= 50 : print(“your score is minimum”) else : print(“you failed”) Here if none of the expressions in the if, elif statements evaluate to True, then the code in the else statement will be executed. Let us try to write some examples with conditional statements (which has selection structure) The following code will find given number is odd or even num=int(input("Enter the number")) if (num%2 == 0): print("The number is even") else: print("The number is odd") Here the modulo operator (%) checks the reminder of dividing the num variable by 2. If the reminder is 0, then the number is even else it is odd. The following code snippet checks the marks and respond accordingly. Published September 2021 ©Bauhaus Educational Services Ltd All rights reserved BCS HEQ – Software Development | 17  if (mark>=90): print("Congrats!!! You scored awesome") elif (mark>=70 && mark=50 && mark 1: for i in range(2, num): if (num % i) == 0: isPrime = True break if isPrime: print(num, “is not a prime number”) else: print(num, “is a prime number”) In this example the given number is taking modulus operation with every number below that to find whether it is a factor or not. If any of the number is found to be the factor of the given number, then isPrime variable is set to true and the loop is exited using break statement. Remember % operator calculates the reminder of the integer division. If the reminder is zero, then the divisor is a factor. Example: Write a program to swap two numbers. a = 3 b = 9 Published September 2021 ©Bauhaus Educational Services Ltd All rights reserved BCS HEQ – Software Development | 24 temp = a a = b b = temp print("The value of a after swapping: {}".format(a)) print("The value of b after swapping: {}".format(b)) Here a and b are two variables which have values 3 and 9 respectively. When you swap the numbers, it is exchanging the values. In order to swap the numbers, you need another temporary variable to hold one value while swapping. You can experiment on this example without using temp variable as below. a = b b = a You can see that output of the above two statements are not as expected. The value of a and b is 9 in this case. It is because when you move the value of b to a using the statement a=b, the previous value of a which is 3 is being replaced and lost. In the second statement you are assigning the current value (9) is being assigned to b in b=a. REFERENCES/READING LIST Althoff C., The Self-Taught Programmer, Self Taught Media, 2017 Bhargava A., Grokking Algorithms, Manning Publications, 2015 Gaddis T., Starting out with Java from Control Structures through Objects, Pearson(6th Edition), 2016 Dietel H., Dietel P., C How to program, Pearson Hall, (8th Edition) 2016 Dietel H., Dietel P., Introduction to Python for the Computer and Data Sciences, Pearson, 2019 Goodrich, M., Tamassia, R., Goldwasser M., Data Structures and Algorithms in Python, Wiley India, 2016 Published September 2021 ©Bauhaus Educational Services Ltd All rights reserved BCS HEQ – Software Development | 25  Deitel, H., Deitel, P., Java How to Program, Pearson India(11th Edition), 2018 Savitch, W., Problem solving with C++, Pearson (10th Ed), 2018. Parker J. R., Python An Introduction to Programming, MLI, 2017 Published September 2021 ©Bauhaus Educational Services Ltd All rights reserved BCS HEQ – Software Development | 26