Class Crib Notes for CPSC 110 Brent Dingle

Monday, February 18, 2002

Reminders:

Quiz Next Week à Wed., Feb. 27

No class on Friday, Feb. 22 due to relocation =).

Review:

So far we have seen:

• Chap 1 = DOS and Turbo Environ
• Chap 2 = Input and Output
• Chap 3 = Software Engineering, 3 types of errors, Software lifecycle, Simple branching
• Chap 12 = File Input and Output
• Chapter 6 = Boolean Expressions, Complex IF-ELSE IF-ELSEs, Case Stmt
• Chapter 7 = Loops: While-do, Repeat-Until, For

New Stuff for today

Chapter 4 – Top Down Design

Definition:

Designing an algorithm by breaking a larger task into smaller tasks is called Top Down Design.

Also referred to as Divide and Conquer or Stepwise Refinement.

Examples: Builder starts at blueprint = foundation then walls, Musician starts with melody then trills, writer starts with outline then adds details, start big work small.

Example 1 - going from one room to another starts out as:

I. Get out of first room

II. Go to second room

III. Go into second room

Subtasks:

I. Get out of first room

a. Go to door

b. Open the door

c. Get out of door

d. Close door

and so on…

Sub-Subtasks:

a. Go to door

i. Get out of seat

ii. Turn towards door

iii. Walk until you almost bump into the door

and so on…

Example 2, designing a comparison/contrast paper from an outline:

Outline goes:

I. Paragraph 1 – Introduction and statement of purpose

II. Paragraph 2 – First item’s properties

III. Paragraph 3 – Second item’s properties

IV. Paragraph 4 – Discussion of similarities

V. Paragraph 5 – Discussion of difference

VI. Paragraph 6 – Conclusion

Subtasks:

· Write a title page

· Given a purpose write an introduction

· Given a list of properties and an item name write a description of the item

· Given 2 item names and a list of properties for each describe the similarities

· Given 2 item names and a list of properties for each describe the differences

· Given a conclusion write a concluding paragraph

· Write a bibliography

 
Notice the parameters (the givens) in the above subtasks.
 

Sub-SubTasks

· Write a paragraph

o Write a sentence

§ Opening topic sentence

§ Body sentence

§ Closing statement

Example 3

Task = Build a one story house

Subtasks

• Create a floor plan
• Lay foundation
• Build walls
• Build roof
• Incorporate plumbing and electricity and ducts and other features
• Install fixtures – sinks, water heater, heater, air conditioning, bath tubs, showers, counters, cabinets
• Paint walls, ceiling etc.
• Install floor coverings, carpet tile, etc
• Install appliances
• Install furniture
• Continue decorating
• Do landscaping
• other tasks?

Now a summary of top-down design with a picture:

First, describe a problem in terms of high-level tasks.

For each of the high-level tasks:

Describe it also in terms of slightly simpler subtasks.

Continue this breakdown until the subtasks are sufficiently simple to be implemented directly as statements in a programming language (say perhaps Pascal =).

Each subtask becomes a procedure/function (which we will be getting to shortly).

---

Hierarchy of tasks and subtasks in a basic top-down design

---

This has proven to be a highly successful design methodology. It has allowed the development of large programs (100,000 lines or more of source code).

Note, however, as the program size increases, the performance of this method decreases. Specifically, code development becomes slower and it becomes more difficult to test the software and guarantee its reliability. This methodology does not encourage the reuse of software.

Next time

More top-down design, maybe procedures