**Tom Kelliher, CS17**

**Feb. 12, 1996**

Observations from the lab:

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

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:

- Calculating a tip
- Double checking a grocery receipt
- Automating LaTeX to
`HTML`conversion

Also known as the * software life cycle*

Starting from the problem statement:

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

Is the life cycle always linear?

** Divide-And-Conquer**

Details to be determined:

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

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:

- Input --- usually required
- Output
- Unambiguousness --- computers don't accept ambiguity
- Generality --- solves a
*class*of problems - Correctness --- correctly solve the given problem
- Finiteness --- termination
- 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

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

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 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

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

- Design an algorithm that keeps reading positive numbers until the user enters a zero value, and determines and outputs the largest number
- Design an algorithm that reads an arbitrary number of numbers and outputs their arithmetic average
- Design an algorithm that outputs the
**i**th largest number in a group of**n**numbers.

Sat Feb 10 11:09:52 EST 1996