Transcript Week3.1

CMP 131
Introduction to Computer
Programming
Violetta Cavalli-Sforza
Week 3, Lecture 1
Quiz: This Wednesday, March 14
•
•
•
•
Covers material from Weeks 1 & 2
Slides
Reading (Ch 1.1-1.3)
Combination of true/false, and shortanswer questions, long-answer question
Quiz – Be Familiar With
• Basic hardware concepts (computer
components)
• Basic hardware/software concepts
– Binary vs. decimal representations and conversion
– Binary addition and outcomes, logical operations
• Different types of software & applications
• Basic types of PLs and their differences
(assembly, machine, high-level)
– NO: details about the different programming language
paradigms (first part of Week 2, Lecture 1)
– YES: structured, imperative, modular, and objectoriented PLs
Quiz – Be Familiar With (2)
• What happens to your program:
– Compiling, linking, executing, interpreting
• Different types of program errors:
syntactic, logical, runtime
• Software development lifecycle
• Software engineering process
• Top-down design, stepwise refinement
Brief Review (Week 1)
• History of Hardware and Software
• Hardware components
• Hardware/Software interface:
– Layers of the Machine
– Kinds of Software
• What happens to your program?
– Compilation, Linking, Execution
– Compilation vs. Interpretation
– Program errors
• Syntax, Semantics, Grammars
Brief Review (Week 2)
• Computer Languages
– History
– Different Types
• Software Development Lifecycle
• Software Engineering Process
1. Problem statement
2. Analysis
3. Design
4. Implementation
5. Testing & verification
6. Maintenance
• Top-down design, step-wise refinement
• Introduction to the TurboPascal IDE
– Editing, compiling, running programs
This Week
• More top-down design and stepwise refinement
examples & practice
• Introduction to basic algorithm concepts:
– sequential, selection and repetition concepts
– stacking vs. nesting
• Some basics of the Pascal language
• Reading: Chs 1.4-1.5, Ch 2.
– Read through once or twice well.
– You are not expected to know everything in there
– We’ll go over the most important concepts in class.
Case Study 3: Program for Grades
Revised Problem Statement
• A program that will let me enter and store the score that I
receive for each assessment in the course, the
maximum score that I could have obtained in that
assessment, and the name of the assessment. When I
run the program, it will:
– Retrieve and display the scores it already knows in a table with
suitable headers
– Give me the option to enter data for one or more additional
assessments or to exit (AssessmentName, MyScore, MaxScore)
– If I choose to enter data for an assessment it will prompt me for
all three values on one line
– After I enter the values it will again give me the option to enter
new data or to exit.
• When I exit the program
– all the data (old and new) will be stored to a new file so that it
can be retrieved next time the program is run.
– all the data it has for me will be shown.
Are you starting to think that you should use a spreadsheet instead?
Case Study 3: I/O Analysis
• Design (Algorithm):
– Input:
• Existing data from file
– Need to specify file name or not?
• New data from keyboard
– Output:
• Existing data from file to the screen
• Existing data plus new data to file
Case Study 3: Processing Analysis
•
Processing:
1. Display existing data
•
•
Print table header
For each item in the file containing old data, print the values
2. Prompt user to exit or enter new data
•
If user chooses to exit, then continue to Step 3, otherwise
– Prompt user to enter data:
Name of assessment, My score, Max score
– Do something with that data…
•
Repeat step 2
3. Display all the information the program has for me
4. Finalize files
5. Exit
Refinement Step 2
•
Prompt user to exit or enter new data
–
–
Alternative 1: A single prompt that can accept either data or
an indication to exit.
Alternative 2: Two different prompts:
•
•
–
Selection:
If user chooses to exit,
then continue to Step 3 (display all data, finalize, exit)
else
•
•
•
Exit/Continue
Prompt for data (if continue)
Prompt user to enter data:
AssessmentName, MyScore, MaxScore
Do something with that data…
(e.g. add it to the end a file)
Repeat step
Case Study 4:
A Simple Statistics Calculator
A program like those in graphic calculators
that allows entering the data and will
automatically display mean/average, the
frequency, the median, the mode …
– We can do a conceptual version of it
Let’s review definitions
• Mean: (n1 + n2 + … + nm) / m
• Median: Given a set of m numbers, the value v
such that 50% of the numbers are smaller than it
and 50% of the numbers are larger than it.
– If m is odd, v will be one of the numbers
– If m is even, v will be an average of two of the
numbers
• Mode: The most frequent value in a set of
numbers
– May need to cluster into intervals / ranges
• Frequency:
– May need to cluster into intervals / ranges
Consider the different requirements
• Mean:
– Don’t need to keep track of the numbers, just
• How many of them
• Their sum
• Median:
– Need to order (sort) them
• Mode, Frequency:
– Possibly if they are integers, certainly if they
are real, need to find:
• minimum and maximum
• create intervals
• count frequency in each interval
Mean of 3 Numbers
• INPUT: 3 numbers
• OUTPUT: Mean of 3 numbers
• PROCESSING:
Get 3 numbers
Sum them
Compute Mean as Sum / 3
Mean of 3 Numbers: Program
PROGRAM ComputeAverage (input,output);
{A simple program that computes an average.}
VAR
Score1, Score2, Score3 : integer;
Average : real;
BEGIN
writeln ('Enter three scores and press <Enter>.');
readln (Score1, Score2, Score3);
Average := (Score1 + Score2 + Score3) / 3;
writeln (Average:20:3)
END.
Mean of 20 Numbers
• INPUT: 20 numbers
• OUTPUT: Mean of 20 numbers
• PROCESSING:
Get 20 numbers one at a time, keeping a
running sum
Compute Mean as Sum / 20
Mean of 20 Numbers: Refinement
PROCESSING:
Do the following 20 times:
Get a Number
Add it to the Sum
Compute Mean as Sum / 20
QUESTION: Is this good enough?
Mean of 20 Numbers: Refinement
PROCESSING:
Initialize Sum to 0
Do the following 20 times:
Get a Number
Add it to Sum
Compute Mean as Sum / 20
This is an example of definite looping: You know how
many times you go around the loop when you start.
Mean of N Numbers
• INPUT: Several numbers
• OUTPUT: Mean of numbers
• PROCESSING:
Get numbers and how many of them (Count)
Add to Sum
Compute Mean as Sum / Count
Mean of N Numbers: Take 1
PROCESSING:
Ask user how many numbers (store in Count)
Ask user for that many numbers and
compute Sum
Compute Mean as Sum / Count
Mean of N Take 1: Refinement
PROCESSING:
Initialize Sum to 0
Prompt for value of Count
Read value of Count
Do the following Count times:
Prompt for Number
Read Number
Add Number to Sum
Compute Mean as Sum / Count
This is ALSO an example of definite looping :
You know how many times you go around the loop when you start.
Mean of N Numbers: Take 2
PROCESSING:
repeat
Prompt for Number
Read Number
Add Number to Sum
Increment Count by 1 (add 1 to Count)
until no more numbers
Compute Mean as Sum / Count
This is an example of indefinite looping :
You DO NOT know how many times you go around the loop until you finish.
Mean of N Numbers (Take 2):
Refinement
PROCESSING:
Initialize Sum to 0
Initialize Count to 0
repeat
Prompt for Number
Read Number
Add Number to Sum
Increment Count by 1
until no more numbers
Compute Mean as Sum / Count
Questions
• How do we know there are no more numbers?
– If you were reading from a file, you would get a signal
that you were at the end of the file
– From the terminal, there must be either:
• 2 different prompts:
– 1) enter more data? yes/no
– 2) (if yes) then ask for data
• a special value that is a signal to end
– Should be value that won’t be confused with the other data, i.e.
is not a legal data value
– e.g. -99999 (if you are computing an average of scores, this is
not a legal score)
Is the logic okay with a sentinel
value? Or is there a problem?
PROCESSING:
Initialize Sum to 0
Initialize Count to 0
repeat
Prompt for Number
Read Number
Add Number to Sum
Increment Count
until Number = -99999
Compute Mean as Sum / Count
Mean of N (Take 2): Refinement
PROCESSING:
Initialize Sum to 0
Initialize Count to 0
repeat
Prompt for Number
Read Number
if Number is not equal to -99999
then
Add number to Sum
Increment Count
until Number = -99999
Compute Mean as Sum / Count
Can we make it better?
Or different?
•
In previous, we test if Number is the
special value of -99999 twice:
1. To decide whether it is a legal number, to
add it to Sum
2. To decide whether to exit the loop.
•
•
This is not very elegant, and it is also
inefficient (though equality tests are
cheap)
Rewrite the loop to test only once
Mean of N (Take 3)
PROCESSING:
Initialize Sum to 0
called a sentinel value
because it guards the loop
Initialize Count to 0
Prompt for Number
Read Number
while Number is not equal to -99999 do:
Add Number to Sum
Increment Count
Prompt for Number
Read Number
Compute Mean as Sum / Count
This is also an example of indefinite looping :
You DO NOT know how many times you go around the loop until you finish.