Transcript CS107: Introduction to Computer Science

CS107
Introduction to Computer Science
Lecture 2
Administrativia
• Lab access
– Searles 128: daily until 4pm unless class in progress
– Searles 117: 6-10pm, Sat-Sun 12-10pm
• Office hours
– M, W 4-5 pm
– Quick questions: Anytime I am in the office
– Email to set up appointment
• My office: Searles 219
• Study group
– Mondays 8-9pm in Searles 224
Last time
– What is (not) Computer Science
– Algorithms, properties and examples
– Expressing algorithms: Pseudocode
• Who was Alan Turing and what is he famous for?
• Today
– More pseudocode elements
– Algorithm examples
Expressing algorithms
• Is natural language good?
– For daily life, yes…but for CS is lacks structure and
would be hard to follow
– Too rich, ambiguous, depends on context
• How about a programming language?
– Good, but not when we try to solve a problem..we want
to think at an abstract level
– It shifts the emphasis from how to solve the problem to
tedious details of syntax and grammar.
Pseudocode
• Pseudocode = English but looks like programming
• Good compromise
– Simple, readable, no rules, don’t worry about
punctuation. Lets you think at an abstract level about
the problem.
– Contains only instructions that have a well-defined
structure and resemble programming languages
Pseudocode elements
• Basic operations
– Read the input from user
– Print the output to the user
– Cary out basic arithmetical computations
• Conditional operations
– Execute an operation if a condition is true
• Repeat operations
– Execute a block of operation multiple times until a
certain condition is met
Basic operations
– Read the input from user
• Get x
• Get a, b, c
– Print the output to the user
• Print x
• Print “Your mileage is ” x
– Cary out basic arithmetical computations
• Set x to 10
• Set y to x*x/3
Conditional statements
Specify a statement that may or may not be done:
if <condition> then
<statement to be done>
else <statement to be done otherwise>
Example
if the value of carry is 0 then set the value of a to
0
else set the vale of a to a+1
Loop statements
specify a group of statements that may be done
several times (repeated):
repeat until <condition>
< statements to be repeated >
• How does this work?
– Condition is evaluated
– If it is true than the loop terminates and the next instruction to be
executed will be the instruction immediately following the loop
– If it is false, then the algorithm executes the <statements to be
repeated> in order, one by one
Example
Variables: count
Step 1: set count to 1
Step 2: repeat step 3 to step 5 until count is > 10
Step 3: set square to count *count
Step 4: print value of square and value of count
Step 5: add 1 to count
Step 6: end
• What does this algorithm do?
• Note: indentation
– Not necessary, but makes reading/understanding algorithms easier
Pseudocode examples
Equivalent:
– Set the value of a to 1
– Set a to 1
– a=1
Equivalent
–
–
–
–
Add 1 to count
Set count to count + 1
Increment the value of count by 1
count = count + 1
Writing in pseudocode gives you the freedom to choose
any of these!
• Incorrect
– Set 1 to a
– Add a + b (what do you do with the result?)
– Set a+b +3
• Note: not the same
– set a to b
– set b to a
• Example: what is the output of the following algorithms?
set a to 2
set a to 2
set b to 4
set b to 4
set a to b
set b to a
print a, b
print a, b
A model for visualizing an algorithm’s behavior
Computer
Algorithm
Input
(keyboard)
Output
(screen)
Variables
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.
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)
Problem
• Adding two n-digit numbers
7597831 +
1287525
------------------8885356
How would you write an algorithm to solve this problem?
Assume the basic operation is adding one-digit numbers.
Computing the sum 1+2+….+n
Problem: Write an algorithm which reads a
positive integer from the user and computes the
sum of all positive integers smaller than or equal
to te number entered by the user.
– Example: if the user enters 10, the algorithm should
compute 1+2+3+…+10
Gauss formula
• Find a formula for 1 + 2 + ……. + n
Gauss noticed that
• 1 + n = n+1
• 2 + (n-1) = n+1
• ….
==> 1 + 2 + … + (n-1) + n = n(n+1)/2