Transcript Document

Designing Algorithms
Csci 107
Lecture 3
Administrativia
• Lab access
– Searles 128: daily until 4pm unless class in progress
– Searles 117: 6-10pm, Sat-Sun 12-10pm
• Office hours:
– Mon, Wed 4-5, Tue after lab
– Quick questions: Anytime I am in the office
– Email to set up appointment
• My office: Searles 219
• Study group: Mondays 8-10 pm in Searles 224
Designing algorithms
• Last time
– Pseudocode
– Algorithm: computing the sum 1+2+…+n
– List variables
• Today
– Adding two m-digit numbers
– Computing MPG
– Search and variations
List variables
• How to represent (in pseudocode) inputs of arbitrary size?
• Suppose that we need to read 100 numbers from the user, or
1000, or..
– we could give each variable a different name…tedious!!
• Use a list variable:
– Variable: list a of size n
– This means that a is a list of n elements: a1, a2, a3,…,an
– To read the list from the user use
• Get n and a1, a2, a3,…,an
– To print the list use
• Print a1, a2, a3,…,an
– We can treat each element in the list as a variable
• Set a3 to 5
• Set a4 to a3 +2
Problem
• Adding two m-digit numbers
7597831 +
1287525
------------------8885356
Write an algorithm to solve this problem. Assume the
basic operation is adding one-digit numbers.
Algorithm for adding two m-digit numbers (Fig 1.2)
Given: m ≥ 1 and two positive numbers a and b, each
containing m digits, compute the sum c = a + b.
Variables: m, list a0 ..am-1, list b0 …. bm-1 , list c0 …cm-1 cm, carry, i
0
Get values for m, am-1 … a0 and bm-1 … b0
1
Set the value of carry to 0.
2
Set the value of i to 0.
3
Repeat steps 4-6 until i > m-1
4
Set the value of ci to ai + bi + carry
5
if ci ≥ 10 then
subtract 10 from ci and set the value of carry to 1
else set the value of carry to 0
6
Add 1 to i
7
Set the value of cm to carry
8
Print value of c = cm cm-1 cm-2 … c0
So, how does this work???
For example, the input is m = 4, a = 3276, and b = 7345.
After step 0, the variables m, a, and b have those values:
m
4
3 2
a3 a2
7 6
a1 a0
7 3
b3 b2
4 5
b1 b0
After steps 1 and 2, the variables i and carry are initialized.
i
0
carry
0
Next, steps 4-6 are repeated until the value of i > 3. Each
repetition computes a single digit of c.
c4 c3 c2
c1 c0
A model for visualizing an algorithm’s behavior
Computer
Algorithm
Input
(keyboard)
Output
(screen)
Variables
E.g., Visualizing Fig 1.2
Computer
Input
(keyboard)
4
3276
7345
0 Get values for …
…
8 Print value of …
m
4
i
0
carry
3 2
a3 a2
7 3
7 6
a1 a 0
4 5
b3 b2
b1 b0
c4 c3 c2
c1 c0
Output
(screen)
0
Algorithm for computing MPG (Fig 2.5)
Write a pseudocode algorithm to compute the distance traveled and
the average miles per gallon on a trip when given as input the number
of gallons used and the starting and ending mileage readings on the
odometer. Repeat this process until user wants to stop.
Variables: response, gallons, start, end, distance, mpg
0
Set response to “Yes”
1
Repeat steps 2-8 until response = “No”
2
Get gallons, start, end
3
Set distance to end - start
4
Set mpg to distance ÷ gallons
5
Print mpg
6
if mpg > 25.0 then
print “You are getting good gas mileage”
else print “You are NOT getting good gas mileage”
7
Print “Do you want to do this again, Yes or No?”
8
Get response
9
Stop
So, how does this work???
For example, suppose we use 25 gallons, beginning at 12000
and ending at 13000 on the odometer. Then, after step 2,
some variables have the following values:
Yes
25
12000
13000
response
gallons
start
end
After step 4, the variables distance and mpg are computed.
distance
1000
mpg
40
Steps 5-9 displays these results on the output screen:
40
You are getting good gas mileage
Do you want to do this again, Yes or No?
Visualizing Fig 2.5
Computer
Input
(keyboard)
25
12000
13000
0 Set response …
…
11 Stop
response Yes gallons
start
distance
end
mpg
Output
(screen)
Designing Algorithms: A Methodology
1. Read the problem, identifying the input and the
output.
2. What variables are needed?
3. What computations are required to achieve the
output?
4. Usually, the first steps in your algorithm bring
input values to the variables.
5. Usually, the last steps display the output
6. So, the middle steps will do the computation.
7. If the process is to be repeated, add loops.
How was the MPG program (Fig 2.5) designed?
Problem statement:
Write a pseudocode algorithm to compute the distance
traveled and the average miles per gallon on a trip when
given as input the number of gallons used and the starting
and ending mileage readings on the odometer.
Input: number of gallons, starting mileage, ending mileage
Output: distance traveled, average miles per gallon
Variables: gallons, start, end, distance, mpg
Calculate: distance = end - start
mpg = distance / gallons
Put the steps in order: input, calculate, output (steps 2-8)
Determine if a loop is needed (steps 0, 1, 9, 10)
A Search Algorithm
Problem statement: Write a pseudocode algorithm to find
the location of a target value in a list of values.
Input: a list of values and the target value
Output: the location of the target value, or else a message that
the value does not appear in the list.
Variables:
The (sequential) search algorithm (Fig 2.9)
Variables: target, n, list list of n values
Get the value of target, n, and the list of n values
Set index to 1
Set found to false
Repeat until found = true or index > n
If the value of listindex = target
then
Output the index
Set found to true
else
Increment the index by 1
If not found then
Output a message that target was not found
Stop
Variations of sequential search..
• Modify the sequential search algorithm in order
– To find all occurrences of target in the list and print the
positions where they occur
– To count the number of occurrences of target in the list
– To count how many elements in the list are larger than
target
More algorithms
• Write algorithms to find
– the largest number in a list of numbers (and the position where it
occurs)
– the smallest number in a list of numbers (and the position where it
occurs)
– the range of a list of numbers
• Range= largest - smallest
– the average of a list of numbers
– the sum of a list of numbers
For next time..
• Read Chapter 2
– Except 2.3.3 (Pattern matching), which we’ll do
next time
• Lab 1 is due tomorrow