The Practice of Computing Using

 Date 25.04.2017 Size 10.12 Kb. #17642

The Practice of Computing Using

PYTHON

William Punch

Richard Enbody

Chapter 3

Algorithms & Program Development

What is an Algorithm?

• process or a set of rules to be followed in calculations or other problem-solving operations

• a recipe for solving a problem

Example: Summing Numbers

• Sum the numbers between 1 and 100 (inclusive)

Algorithm vs. Program

• an algorithm is a description of how to solve a problem
• a program is an implementation of an algorithm in a particular language to run on a computer (usually a particular kind of computer)
• difference between what we want to do and what we actually do

What’s the Difference, Really?

• we can analyze the algorithm independent of its implementation.
• we can examine how easily, or with what difficulty, a language allows us to realize an algorithm
• we can examine how different computers impact the realization of an algorithm

Aspects of an Algorithm

• Detailed: Provide enough detail to be implementable. Can be tricky to define completely, relies on “common sense”
• Effective: the algorithm should eventually halt, and halt in a “reasonable” amount of time. “reasonable” might change under different circumstances (faster computer, more computers, etc.)

Aspects of an Algorithm (2)

• Specify Behavior: the algorithm should be specific about the information that goes in (quantity, type, etc.) and the information that comes out.
• General Purpose: algorithms should be idealized and therefore general purpose. A sorting algorithm should be able to sort anything (numbers, letters, patient records, etc.)

• We will emphasize, over and over, that a program is an essay on problem solving intended to be read by other people, even if “other people” is you in the future!
• Write a program so that you can read it, because it is likely that sometime in the future you will have to read it!

• The easiest thing to do that affects readability is good naming
• use names for the items you create that reflect their purpose
• to help keep straight the types used, include that as part of the name. Python does not care about the type stored, but you do!

print "Average:", average

• info at the top, the goal of the code
• purpose of variables (if not obvious by the name)
• purpose of other functions being used
• anything “tricky”. If it took you time to write, it probably is hard to read and needs a comment

• indenting is a visual cue to say what code is “part of” other code.
• This is not always required as it is in Python, but Python forces you to indent.

Aspects of Programming (2)

• Robust: As much as possible, the program should account for inputs that are not what is expected. More on this with error handling in Chapter 14
• Correct: Our programs should produce correct results. Much harder to ensure than it looks!

Example: Summing Numbers

• Sum the numbers between 1 and 100 (inclusive)

Example: Summing Numbers

• Sum the numbers between 1 and 100 (inclusive)
• Can write a loop:

print sum

• Is there a better way?

The Problem is “Problem-Solving”

• Remember, two parts to our goal:
• Understand the problems to be solved
• Encode the solution in a programming language, e.g. Python

Steps to Problem Solving

• Engage/Commit
• Visualize/See
• Try it/Experiment
• Simplify
• Analyze/Think
• Relax

You need to commit yourself to addressing the problem.

• Don’t give up easily
• Try different approaches
• Set the “mood”

Find a way that works for you, some way to make the problem tangible.

• draw pictures
• layout tables
• literally “see” the problem somehow

Think it Over/Analyze

• stop
• evaluate how you are doing
• analyze and keep going, or start over.

Multiplication Algorithm

• How to the find the product of two numbers using only addition (no multiplication)?

Multiplication Algorithm

• Get input integers a and b
• Set sum to 0
• Add a to the sum b times

Prime-Verification Algorithm

• How to determine if a positive integer is prime?

Prime-Verification Algorithm

• Get input integer n
• For each number i from 2 through sqrt(n)
• If n % i == 0, n is not prime, exit loop
• If loop completed normally, n is prime

Square Root Algorithm

• How to find the square root of an integer?
• This is difficult!

Square Root Algorithm

• Get input integer n
• Guess the square root of n
• Divide the n by the guess
• Average the quotient (from 3) and the guess
• Make the new guess the average from step 3
• If the new guess is “sufficiently different” from the old guess, go back to step 3, else halt.