# Problem Solving and Pseudocode

Tom Kelliher, CS17

Feb. 12, 1996

Observations from the lab:

• Editing
• Compiling/Running
• Debugging
• Saving
• ``C++ is like BASIC!!''

# Problem Solving

The process of transforming the description of a problem into the solution of that problem by using our knowledge of the problem domain and by relying on our ability to select and use appropriate problem-solving strategies, techniques, and tools.

A few problems examples:

1. Calculating a tip
2. Double checking a grocery receipt
3. Automating LaTeX to HTML conversion

## The Software Development Method

Also known as the software life cycle

Starting from the problem statement:

1. Requirements specification --- removal of ambiguity from the problem statement (acquiring expertise)
2. Analysis --- a detailed determination of the problem inputs and outputs
3. Design --- the development of a logically-ordered set of steps, whose application to the problem input produces the problem output
4. Implementation --- the creation of a working program from the design
5. Testing and verification --- of the working program
6. Documentation
1. The problem being solved
2. Who is responsible?
3. The design
4. The particulars of the implementation

Is the life cycle always linear?

Divide-And-Conquer

## Analysis

Details to be determined:

• Inputs/Outputs, their form, their media
• Special constraints or conditions
• Computational formulas, equations

# Algorithm Design and Representation

Algorithm:

A sequence of a finite number of steps arranged in a specific logical order which, when executed, produces the solution for a problem.

An algorithm must satisfy the following requirements:

1. Input --- usually required
2. Output
3. Unambiguousness --- computers don't accept ambiguity
4. Generality --- solves a class of problems
5. Correctness --- correctly solve the given problem
6. Finiteness --- termination
7. Efficiency --- recognition of finite computing resources: CPU cycles, memory

Pseudocode:

A semiformal, English-like language with a limited vocabulary that can be used to design and describe algorithms.
• Meta-programming language
• Algorithm representation

## Pseudocode Structural Elements

C. Bohm and G. Jacopini proved in 1966 than pseudocode required only three structural elements

### The Sequence Control Structure

A series of steps or statements that are executed in the order they are written in an algorithm.

Example:

```print "What is your name?"
print "How old are you, ", name, "?"
let birthYear = CURRENT_YEAR - age
```

begin/ end pair grouping:

```begin
let amountDue = overDue + currentBilling + penalty
print "You owe: ", amountDue
end
```

### The Selection Control Structure

The alternatives of two courses of action only one of which is taken depending on the outcome of a condition, which is either true or false.

```if condition
then_part
else
else_part
end_if
```

Structure of `then_part`, `else_part`:

• A single statement
• A set of statements enclosed by begin/ end

```if payment is overdue
begin
let amountDue = pastDue + currentBilling + penalty
print "You owe: ", amountDue
end
else
print You owe: , currentBilling
end_if
```

Alternative nested if-else structure element: `else_if`

```if grade < 60
print "F"
print "D"
print "C"
print "B"
else
print "A"
end_if
```

### The Repetition Control Strucutre

Specifies a block of one or more statements that are repeatedly executed until a condition is satisfied.

```while condition
loop_body
end_while
```

Structure of `loop_body`

```let sum = 0
while there are input numbers to sum
begin
print "Next number: "
let sum = sum + number
end
end_while
print "The sum is: ", sum
```

# Example Problems

1. Design an algorithm that keeps reading positive numbers until the user enters a zero value, and determines and outputs the largest number
2. Design an algorithm that reads an arbitrary number of numbers and outputs their arithmetic average
3. Design an algorithm that outputs the ith largest number in a group of n numbers.

Thomas P. Kelliher
Sat Feb 10 11:09:52 EST 1996
Tom Kelliher