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?"
read name
print "How old are you, ", name, "?"
read age
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"
else_if grade < 70
   print "D"
else_if grade < 80
   print "C"
else_if grade < 90
   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: "
      read 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.