Top-Down Design and Control Structures in Python

3/10/16 Notes

Chapter 7/8

Top-Down Design

Takes the most basic aspect of a program and breaks it down into subprograms.

Control Structure

An expression that determines the order in which a program executes.

In Python, this is an if statement.

It can also be a looping statement.

Boolean Expression

A "True or False" program statement.

Composite Data Types

Example:

• numbers[0] = 1066
• numbers[1] = 1492
• numbers[2] = 999
• numbers[3] = 553
• numbers[4] = 1892

Example Code:

for i in range(3):
    print(numbers[i])

Arrays

When data is being read into an array, a counter is updated for each operation (e.g., for i in range(5)).

Sequential Search of an Unsorted Array

A sequential search examines each item in turn and compares it to the target item. If it matches, the item is found. If not, the search continues to the next item. The search stops either when the item is found or when all items have been examined without a match. This involves a loop with two ending conditions.

Example:

• 5
• 195
• 260
• 340
• 490

Pseudocode

Set position to 0
Set found to FALSE
WHILE (position < length AND NOT found)
    IF (numbers[position] equals searchItem)
        Set found to TRUE
    ELSE
        Set position to position + 1

Note: In Python, "!" means "not", as in "not found".

Code Example

position = 0
found = False
searchItem = 40
while (position < length and not found):
    ...

Boolean Operators

AND: Returns True if both operands are true; False otherwise.

OR: Returns True if at least one operand is true; False otherwise.

NOT: Returns True if the operand is false; False otherwise.

A boolean variable stores either True or False.

Binary Search

A binary search repeatedly divides the number of items in a sorted list in half. It checks if the middle element is the target item. If not, it eliminates half of the list based on whether the target item is greater or less than the middle element.

Bubble Sort

Example:

• 55, 95, 60, 40
• 55, 60, 95, 40
• 55, 60, 40, 95
• ...

The program repeatedly compares adjacent elements and swaps them if they are in the wrong order, until the list is sorted.

For a list of 5 numbers, a maximum of 4 passes are needed.

For a list of 1000 numbers, a maximum of 999 passes are needed.

The maximum number of passes is always one less than the number of items.

Subprogram Statements (Functions)

A section of code can be given a name (a function) and called by that name elsewhere in the program.

When a function is called, the main program's execution pauses while the function's code is executed.

Parameters and Arguments

Parameters: Identifiers listed in parentheses in the function definition (formal parameters).

Arguments: Identifiers listed in parentheses in the function call (actual parameters).