Computer ALGORITHM HOMEWORK

As we have seen in module 2, the instructions that make up computer programs are executed sequentially. We have already studied the simplest statements (assignment, input, and output). In this module, we will study more complex statements, often called compound statements. In contrast to simple statements, compound statements can contain other statements as "parts" and can control the sequence in which statements are executed. In several of the examples that appear in the module, we ask you to "trace" through code that has been written. To trace through code means to systematically write down the value of every variable in the program, at every step, and to understand the relationships (if any) between these variables. You must do this task carefully and literally—the brain has a great capacity for seeing what it wants to see, sometimes, things that are not even there! The ability to trace is absolutely essential in analyzing (understanding) and debugging code. We will supply electronic traces for some of the code, but you should always do your own paper-and-pencil traces too. After acquiring a lot of experience, you will find you can do such traces in your head. I. Sequential Statements If our programs consisted only of statements like the ones we saw in module 2 (assignments, input, and output), there would be no need for a special way to code sequential statements. But if we have statements that can change the sequence of execution (also referred to as flow of control), it becomes necessary to have a special way to ensure the correct sequenced execution of certain groups of statements. Grouped statements that are executed sequentially are called blocks. We indicate a block by placing it between braces, { and }. It is customary to indent the statements that form a block, and you will see this in all our code. It is also customary to omit the braces if a block contains just one simple statement. A block can contain any kind of statement, from simple assignment statements to any of the other statements that we will be studying in this module. If you carefully study the templates provided for the programming exercises, you will notice that right after the words int main, a block appears that contains the executable statements of the program. Naturally, the statements inside this block are executed sequentially. To help you avoid a common mistake programmers make when writing sequential statements, look at this programming tip. II. Selection Statements Selection statements allow programs to execute actions that depend on certain conditions. We will examine two different types of selection statements: if-then statements if-then-else statements These statements are appropriate when a Boolean (i.e., two-way) choice is involved. We will illustrate the use of each of the selection statements by writing pseudocode (i.e., synthesizing code) to solve the following two problems. The parity problem: Read in a positive integer and determine if it is even or odd. Hint. The days-in-a-month problem: Given an integer variable (month) that is between 1 and 12, output the number of days in that month. Hint. You should compare the two different solutions that we will produce for these problems to get an idea about the strengths and weaknesses of the two types of selection statements. A. The if-then Statement In pseudocode, the basic structure of an if-then statement is shown in the diagram below. Click on each underlined link to explore the different parts that make up this statement. Then click on the "next" button to understand how an if-then statement works. Here is an example of an if-then statement from everyday life. Consider what might happen if you want some coffee: If (coffee cup is empty) then { go to coffee machine fill cup with coffee add cream add sugar } Drink coffee! If the coffee cup is not empty, none of the tasks listed in the braces need to be done—you just drink the coffee. If the coffee cup is empty, you would have to first do those various tasks. Only after they have been completed can you drink the coffee. The if-then statement provides just one place to insert statements that describe alternate actions for the then part. It is ideal in situations where we might have to deal with one special situation, and then proceed normally. In general, it is impossible to tell which branch in the flow chart will be followed until the Boolean expression is evaluated at run time, which is why we say that the if-then statement can alter the flow of control. An important concept in analyzing code is to be aware of what conditions would hold (i.e., be true) at any given point in the code. Suppose you put your pencil (or mouse) on a line of code that appears in the then part of an if-then statement. You would know definitely that the if condition had to be true—otherwise the flow of control would never have taken you there! The if-then Solution for the Parity Problem Here is a pseudocode solution for the parity problem. The result is contained in a variable called is_even, which will be set to true if the given number was even and set to false if it was odd. As you read the code, notice how the code has been "blocked" into separate groups by using blank lines. The declarations, the input statement, the assignments, the if-then statement, and the output statement are all separated from each other. When comments appear below each other, they are aligned to present a neat appearance. You should learn to write pseudocode (and code!) in this way. /* Pseudocode solution (if-then) for parity problem */ Declare number as int // number being tested Declare is_even as bool // parity of the number Input number Set is_even = true // set as default value Set remainder = (number % 2) // The then part has just 1 statement, so we omit braces If (remainder == 1) then Set is_even = false // number was odd End If Output is_even You should stop now and trace the code using two different inputs to understand how the code works. In C++ or Java, the if-then statement in the pseudocode would be written as follows: if (remainder == 1) is_even = false ; // C++ or Java if-then statement Note the presence of the semicolon ( ; ) to terminate the statement. The words then and end if are also dropped. Do you know why so many keywords are dropped in C++ and Java? Exercise: Think about whether this pseudocode could be used without modification to deal with negative integers. If not, what modification would you suggest? Answer Exercise: Before you go on, do this code analysis exercise involving the if-then statement. The if-then Solution for the Days-in-a-Month Problem We will now turn to the days-in-a-month problem. The solution is straightforward: use a Boolean expression to select each month, and set the number of days accordingly. (We have deliberately not shown blank lines between each if-then statement to save screen space). /* Pseudocode solution (if-then) for days-in-a-month */ Input month If (month == 1) then Set days = 31 End if If (month == 2) then Set days = 28 End if If ((month == 2)&&(leapyear = true)) then Set days = 29 End if If (month == 3) then Set days = 31 End if If (month == 4) then Set days = 30 End if If (month == 5) then Set days = 31 End if If (month == 6) then Set days = 30 End if If (month == 7) then Set days = 31 End if If (month == 8) then Set days = 31 End if If (month == 9) then Set days = 30 End if If (month == 10) then Set days = 31 End if If (month == 11) then Set days = 30 End if If (month == 12) then Set days = 31 End if Output days Points to note: We could have used output statements in place of each Set days = statement, but it is preferable to have just one output statement at the end, as shown above. Remember that days is a variable—it is meant for use in situations like this, where it could have different values depending on the context. Although this code is straightforward and will work, we should look at some of the disadvantages of the if-then solution to the days-in-a-month-problem. We can make this lengthy code much shorter by grouping together the months that have the same number of days using OR expressions. /* Improved pseudocode (if-then) for days-in-a-month */ If ((month==1)||(month==3)||(month==5)||(month==7)|| (month==8)||(month==10)||(month==12)) then Set days = 31 End if If ((month==4)||(month==6)||(month==9)||(month==11)) then Set days = 30 End if If (month==2) then Set days = 28 End if If ((month==2)&&(leapyear==true)) then Set days = 29 End If Note how we have used blank lines to separate different pieces of the code and that all the code for month == 2 has been kept together. Explore this program using the following interactive trace. Click on the step button to step through the execution algorithm, one instruction at a time. The restart button lets you start execution of the algorithm again. ? 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 /* Improved pseudocode (if-then) for days-in-a-month */ Input month Input leapyear If ((month==1) || (month==3) || (month==5) || (month==7) || (month==8) || (month==10) || (month==12)) then Set days = 31 End if If ((month==4) || (month==6) || (month==9) || (month==11)) then Set days = 30 End if If (month == 2) then Set days = 28 End if If ((month == 2) && (leapyear == T)) then Set days = 29 End if month leapyear days As we step through the algorithm, we will explain each step. To explore all possible control flow paths in this algorithm, we recommend you execute it using each of the following input values: month = 10, leapyear = T month = 9, leapyear = F month = 2, leapyear = T month = 2, leapyear = F Then use inputs of your own choosing. < restart step > The first if test will succeed if month takes any of the values 1, 3, 5, 7, 8, 10, or 12. Why? The disadvantage noted earlier still remains. B. The if-then-else Statement Explore the structure of the if-then-else statement by clicking on various links in the following diagram, and then click on the "next" button to understand how the statement is executed. Use the if-then-else statement when you want to have two separate courses of action. The critical property of the if-then-else statement is that only one of the two sets of statements will be executed: if the then part is executed, the else part will be completely bypassed and vice versa. It is guaranteed that exactly one of these two parts will be executed. Note that the then part and the else part might have different numbers of statements, which is why we have used different indices, m and n. Also, just as with the if-then statement, it is generally not possible to tell which branch will be followed until run time, when the Boolean expression is actually evaluated. Thus the if-then-else statement also can alter the flow of execution. You should again be aware of conditions that you know must be true for the flow of control to lead to a certain point. For example, if you are currently executing a line of code in the else part, you know that the if test must have failed. The if-then-else Solution to the Parity Problem Let us again solve the parity problem, this time using an if-then-else statement. /* Pseudocode solution (if-then-else) for parity problem */ Declare number as int // number being tested Declare remainder as int // stores remainder of % by 2 Input number // read in the number remainder = (number % 2) If (remainder == 1) then Output "Number is Odd" Else Output "Number is Even" End If Carefully compare this code with the code that was written for this problem using the if-then statement. Notice that because we now have two places where we can have alternate actions, we do not need the "default" variable (is_even) that we used before—we can just output different messages. This if-then-else statement would be written in C++ as follows: // if-then-else statement in C++ if (remainder == 1) cout << "Number is Odd" ; else cout << "Number is Even" ; Points to note: The words then and End if are not used. There is a semicolon ( ; ) before the word else, and at the end of the entire statement. Why? Exercise: Before you go on, do this code analysis exercise involving the if-then-else statement. The if-then-else Solution for the Days-in-a-Month Problem Now we turn to the days-in-a-month problem. The solution is again fairly straightforward, but because the final program is sophisticated from a "structural" point of view, we present it in stages. Look at this pseudocode solution for the days-in-a-month problem. Points to note: In this problem, we can see clearly how compound statements can contain other statements within them. The else part for the outermost if-then-else statement is itself another if-then-else statement! And this inner if-then-else statement also has "nested" inner parts. Although this nesting might seem a bit confusing at first, the indenting and the explanatory labels and our stepwise development should help you understand how the statements fit together. We have added comments to each End if, marking which if statement it is associated with. It is always a good idea to indicate such pairings, especially when a bunch of them are piled up in the same place, as above. You should follow this tagging convention with closing braces ( } ) also. Explore this program using the following interactive trace. Click on the step button to step through the execution algorithm, one instruction at a time. The restart button lets you start execution of the algorithm again. ? 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 /* Improved pseudocode (if-then) for days-in-a-month */ Input month Input leapyear If ((month==1) || (month==3) || (month==5) || (month==7) || (month==8) || (month==10) || (month==12)) then Set days = 31 Else If ((month==4) || (month==6) || (month==9) || (month==11)) then Set days = 30 Else // month must be 2 If ((leapyear == T)) then Set days = 29 Else Set days = 28 End if // for leap year End if // months within 30 days End if // months within 31 days month leapyear days As we step through the algorithm, we will explain each step. To explore all possible control flow paths in this algorithm, we recommend you execute it using each of the following input values: month = 10, leapyear = T month = 9, leapyear = F month = 2, leapyear = T month = 2, leapyear = F Then use inputs of your own choosing. < restart step > Let us again trace this code for month = 1. The first if statement succeeds, and after days has been set to 31, all the other statements are bypassed. Why? Thus, this solution is markedly more efficient than the if-then solution to this problem. Exercise: What conditions would be true at the line that has set days = 28 in the pseudocode? Answer Nested if-then-else statements like the one shown above are called cascaded if-then-elses, and they occur frequently in programming. To avoid the statements marching off the right margin if we have a highly nested sequence, the following special format is used (only when we have multiple nested if-then-else statements). We show the code as it would be written in Java or C++. // if-then-else statement in Java or C++ if ((month==1)||(month==3)||(month==5)||(month==7)|| (month==8)||(month==10)||(month==12)) days = 31 ; else if((month==4)||(month==6)||(month==9)|| (month==11)) days = 30 ; else if (leapyear == true) days = 29 ; else days = 28 ; Note how the words else and if are placed on the same line and are aligned on the left. Now that you have become familiar with the if-then and if-then-else constructs, you can write pseudocode to solve the following problem, which is an extension of the programming project in module 2. You again have to compute the pay for a person, but this time, you have to decide if the person should get overtime pay. A person will get overtime pay if he or she has worked more than 40 hours per week. There are two pay rates: the standard rate will apply for the first 40 hours, and the overtime rate will apply for any additional hours. Your pseudocode algorithm should compute the total weekly pay for the person. You will develop your algorithm, using pseudocode, in five phases. The tabs on the top of the interactive diagram below will carefully guide you through these five phases, as follows: Description—In this phase, we explain the problem and give you the input variable names you will use in developing your algorithm. Test Plan—In this phase, you will choose values for the variables so that you can test whether your algorithm produces the answer you expect. You must complete this phase before you can advance to the next phase. Code—In the code phase, you will write the algorithm. We provide variable names and hints to help you. You must complete this phase before you can advance to the next phase. Execute—In this phase, you can step through your algorithm using the values you chose in the test-plan phase to see how the final output is calculated. You can choose new input values by clicking on the "restart" button, but your original test values will be used in the answer phase. You must complete this phase before you can advance to the next phase. Answer—In this phase, you can compare your algorithm and data with the correct ones. In doing this exercise, note that the then part has two statements, requiring us to use braces to ensure that they will be executed sequentially, whereas the else part has only one statement (needing no braces). Description Test Plan Code Execute Answer You again have to compute the pay for a person, but this time, you have to decide if the person should get overtime pay. A person will get overtime pay if he or she has worked for more than 40 hours per week. There are two pay rates: the standard rate will apply for the first 40 hours, and the overtime rate will apply for any additional hours. Your pseudocode proram should compute the total weekly pay for the person. We will assume that the number of hours worked is an integer (as we did in the programming exercise in module 2). Be sure that your code computes the correct pay in these three cases: if the number of hours worked per week is less than 40, exactly 40, and greater than 40. In doing this exercise, note that the then part has two statements, requiring us to use braces to ensure that they will be executed sequentially, whereas the else part has only one statement (needing no braces). Your program will use the following input variables. Your program will compute the output using variable wages. hrs_worked total hours worked per week std_rate standard pay rate ovt_rate overtime pay rate