Friday June 9, 2000

Quiz 4

1. List the four steps in the problem solving process according to Geoge Polya

2. What are the three major types of executions we mentioned that are used in programming languages.

Recall that yesterday we talked about the steps that George Polya found were taken in the problem solving process.

Understand the problem - This is an essential step because if you don't understand what you are being asked to solve, you are unlikely to be able to solve it.
Design or Devise a plan - A plan is called an algorithm. It is a finite sequence of logical steps that terminate to produce a desired outcome.
Implement the Plan
Evaluate the Outcome

We also discussed the Software Life Cycle

Software Life Cycle

BIRTH

Requirements specification. Here we must understand the problem and decide what the desired outcome should be.
Analysis - consider the requirements specifications and raise and questions about Input/Output issues, etc.
Design - we come up with an algorithm. An algorithm should not contain code that is specific to the language with which we are dealing. It should simply be an abstract solution of the problem. For example, one step in algorithm might state: load an integer from a file, but not discuss any specific Java code used to open a file.
Implementation - after we have come up with a good plan, then we put it into action. We write specific code to implement our plan. Sometimes it is tempting to skip the design phase, but very often this will cause you to be unsuccessful in solving the problem.
Test/Debug - more than likely when we are writing a program that is not trivial, there will be errors. The purpose of testing our program is to try to find errors. However, through testing alone we cannot prove that our program will always work correctly. We simply use testing to try to discover any problems and try to correct them. Removing the problems we find is called debugging. Where did this term originate?
Maintenance - once we have successfully written a program to solve a problem, we must maintain it, that is, while a client is using the program they may discover problems with it or decide that would like something new added to it.
Ugrading - when new errors are discovered or new requirements are requested we must modify our original solution

DEATH

These are two important concepts that we need to keep in mind as we are working.

Yesterday we mentioned three major programming constructs that are common in programming languages.

Sequential Execution

This is a series of steps that are to be executed in sequence.

For example

a = 3

b = 4

c = a+b

Conditional Execution

It is very important in a programming language to be able to execute statements only when a certain condition is true. For example, given a sequence of numbers, we want to find the sum of all the even numbers in the list. So we would only add to our sum if the number we were considering were even.

In almost all programming languages, there is the keyword if. If allows us to perform conditional execution.

The syntax of the if statement is

if (condition)
   statement;

If the condition is true, then the statement will be executed.

Notice that if the condition is false then the programming language is not instructed to do anything.

We can modify this if structure to instruct the programming language what to do if the condition is false. We do this with the else statement.

if (condition)
   statement1;
else
   statement2;

If the condition is true, then statement1 is executed, otherwise statement2 is executed.

These if and else statements can be nested together to form a more complex structure.

if (condition1)
   statement1;
else if (condition2)
   statement2;
else
   statement3;

In this case, if condition1 is true, then statement1 is executed. If condition1 is not true, but condition2 is, then statement2 is executed. If neither condition1 nor condition2 is true, then statement3 is executed.

Another way of performing conditional execution is with a switch structure. In a switch structure we examine a variable and based on the value of that variable we peform a certain action. These actions are called cases.

The syntax of this structure is

switch (variable) {
   case value1 : statement1; break;
   case value2 : statement2; break;
   ...
   case valuen : statementn; break;
   default: defaultstatement;
}

Repeated Execution

Another important construct in programming languages is repeated execution or looping. This allow us to do things like perform an action on all numbers from 1 to 100, etc.

One of the basic ways to implement repeated execution is with the while statement. There are two ways we can use the while statement.

do {
   somestatements
} while (condition);

while (condition) {
   somestatements
}

In the first case, we are guaranteed that the statements will be executed at least one time and will continue to be executed as long as the condition is true. In the second case, the statements will only be executed if the condition is true and will continue to be executed as long as the condition is true.

A specialized case of the while loop is the for loop.

for (statement1;condition;statement2)
   somestatements

The first statement is an initialization. It is executed one time. As long as condition is true, somestatements along with statement2 are executed.

In order to help make the flow of the program easier to understand and plan we can use the concept of a flowchart. A flowchart allows us to describe the flow of the program using various symbols.

Recall that an algorithm is a plan. At the beginning of our plan we use an ellipse.

At the end we will also use an ellipse.

We will discuss more about flowcharts Monday. For now let us consider a couple of problems and see how we can come up with an algorithm to solve the problem.

Given a positive number determine whether or not it is even.
Given a positive number, find all of the positive divisors of the number.
Determine whether or not a given positive number is prime.
Given a positive number, n, find all of the prime numbers less than or equal to n.