Transcript More Algorithms - Computer Science

CPSC 171 Introduction to
Computer Science
3 Levels of Understanding Algorithms
More Algorithm Discovery and Design
Announcements
Last day to Add/Drop Sept 11
Wipe Down Computer Keyboards and
Mice
Read Chapter 2
Homework 2 due this Friday (Hand in
electronically or paper copy)
Lab 1 due this Thursday (Hand in
electronically)
Recall That…
An Algorithm is …
Three types of pseudocode instructions



Sequential (computation, input, output)
Conditional (if then else)
Iterative (while and do/while)
Creating Algorithms
Given a description of what an
algorithm is supposed to do
“Design an algorithm to beat me in the game
of 21”
Create an Algorithm to do it
How?
Game Time
Who can beat me in the game 21?
Objective:
Get your opponent to say the number 21.
Rules:
One player goes first starting counting from 1.
On each turn a player may say one or two consecutive
numbers.
You must begin where your opponent left off.
The first person to say the number 21 loses.
There is a way to always beat me!
3 Levels of Tasks
Level 1


Given: An algorithm and the input to the algorithm
Do: State the output
Level 2


Given: A description and an algorithm
Do: Decide if the algorithm is correct
Level 3:


Given: A description
Do: Design an algorithm
Level 1
Description: Given a bank account starting balance and
the interest rate print out the interest earned and the
final balance.
Code:
get balance, rate
assign earned to be balance*rate
assign total to be balance+earned
print “amount earned is “
print earned
print “ending balance is “
print total
Input: balance is 100, rate is 0.05
Output: ??
Level 1
Code:
Get num1, num2
Set average to be
If num1 > average
print “You did
Else
print “you did
(num1+num2)/2
then
better than average”
worse than average”
Input: num1 is 10 and num2 is 8
Output: ??
Level 1
Code:
Get num1, num2
Set total to be num1
While num1 < num2
Update total to be total + num2
Update num1 to be num1 + num1
If total > (num1 + num2) then
Print “total is big”
Else
Print “total is small”
Print total
Input: num1 is 10 and num2 is 8
Output: ??
Input: num1 is 5 and num2 is 11
Output: ??
Level 2
Level 2


Given: A description and an algorithm
Do: Decide if the algorithm is correct
Here is what to do:


Make up your own input
Make sure to test boundary conditions
Level 2
Description:Given two numbers, calculate their average and print
“You did better than average” if the first number is larger than
the average or print “You did worse than average” if the first
number is smaller than the average
Code:
Get num1, num2
Set average to be
If num1 > average
print “You did
Else
print “you did
(num1+num2)/2
then
better than average”
worse than average”
Input: ??
Output: ??
Is the Algorithm correct?
Level 2
Description: Calculate the average of a set of numbers provided by
the user. Print out the average.
Code:
Print “how many numbers?”
Get counter
Set total to be 0
While counter > 0
print “enter the next number”
Get number
Set total to be total + number
Set counter to be counter – 1
Set average to be total / counter
Print “The average of the numbers is”
Print average
Input: ??
Output: ??
Is the Algorithm correct?
Level 2
Description: Calculate the average of a set of numbers provided by
the user. Print out the average.
Code:
Print “how many numbers?”
Get number_of_numbers
Set counter to be 1
Set total to be 0
While counter < number_of_numbers
print “enter the next number”
Get number
Set total to be total + number
Set counter to be counter + 1
Set average to be total / number_of_numbers
Print “The average of the numbers is”
Print average
Input: ??
Output: ??
Is the Algorithm correct?
Level 3
Level 3:


Given: A description
Do: Design an algorithm
Start with sequential algorithms
Add in conditionals
Add in loops
Level 3 – Sequential Operations
Design an algorithm to:
1.
2.
3.
Given the base and height of a triangle
and output the triangle’s area.
Output the flying time between two cities
given the mileage M between them and
the average speed of the airplane.
Given an accounts starting balance,
interest rate, and yearly service charge,
output the end of year balance.
Level 3 – Conditional Operations
Design an algorithm to:
1.
2.
Compute and display the value x/y if the
value of y is not 0. If y is 0 then display
“unable to perform the division.”
Compute the area and circumference of a
circle given the radius r if the radius is
greater than or equal to 1.0; otherwise
you should compute only the
circumference.
Level 3 – Conditional Operations
Design an algorithm to:
Given an accounts starting balance,
interest rate, and yearly service charge,
output the end of year balance.
Subtract the service charge only if the
starting balance is below $1,000.
Designing Algorithms
When designing algorithms you first have to
understand the description so well that you can
clearly explain each step
Go Forth and Multiply: Multiply two numbers
using repeated addition
Sequential search: Find a particular value in an
unordered collection
Find maximum: Find the largest value in a
collection of data
Example 1: Go Forth and Multiply
Task
Implement an algorithm to multiply two
numbers, a and b, using repeated addition
Algorithm outline
Create a loop that executes exactly b times,
with each execution of the loop adding the
value of a to a running total
Algorithm: Go Forth and Multiply
Figure 2.10
Algorithm for Multiplication via Repeated Addition
Example 2: Looking, Looking,
Looking
Task

Find a particular person’s name from an
unordered list of telephone subscribers
Algorithm outline

Start with the first entry and check its
name, then repeat the process for all
entries
Example 2: Looking, Looking,
Looking (continued)
Algorithm discovery

Finding a solution to a given problem
Naïve sequential search algorithm


For each entry, write a separate section of the
algorithm that checks for a match
Problems
 Only works for collections of exactly one size
 Duplicates the same operations over and over
Example 2: Looking, Looking,
Looking (continued)
Correct sequential search algorithm




Uses iteration to simplify the task
Refers to a value in the list using an index (or
pointer)
Handles special cases (such as a name not
found in the collection)
Uses the variable Found to exit the iteration
as soon as a match is found
Figure 2.13
The Sequential Search Algorithm
Example 3: Big, Bigger,
Biggest
Task

Find the largest value from a list of values
Algorithm outline


Keep track of the largest value seen so far
(initialized to be the first in the list)
Compare each value to the largest seen so far,
and keep the larger as the new largest
Example 3: Big, Bigger,
Biggest (continued)
Once an algorithm has been developed, it
may itself be used in the construction of
other, more complex algorithms
Library


A collection of useful algorithms
An important tool in algorithm design and
development
Example 3: Big, Bigger,
Biggest (continued)
Find Largest algorithm


Uses iteration and indices as in previous
example
Updates location and largest so far when
needed in the loop
Figure 2.14
Algorithm to Find the Largest Value in a List