CENTRAL QUESTIONS OF
COMPUTER SCIENCE
Which problems can be solved by algorithmic processes?
How can algorithm discovery be made easier?
How can techniques of representing and communicating
algorithms be improved?
How can characteristics of different algorithms be
analyzed and compared?
0-47
CENTRAL QUESTIONS OF
COMPUTER SCIENCE (CONT’)
How can algorithms be used to manipulate information?
How can algorithms be applied to produce intelligent
behavior?
How does the application of algorithms affect society?
0-48
THE CENTRAL ROLE OF ALGORITHMS
IN COMPUTER SCIENCE
0-49
WHAT IS COMPUTER SCIENCE?
The study of algorithms: TERMINOLOGY
• their formal properties
• correctness, limits • Algorithm: A set of steps
that defines how a task is
• efficiency/cost performed
• their hardware realizations • Program: A representation
of an algorithm
• computer design
• Programming: The process
• their linguistic realizations of developing a program
• programming languages • Software: Programs and
algorithms
• their applications
• Hardware: Equipment
• network design, ocean modeling,
bioinformatics, ...
WHAT IS AN ALGORITHM?
… a well-defined procedure that allows an agent to solve a problem.
Note: often the agent is a computer or a robot…
Example algorithms:
Cooking a dish
Making a peanut-butter jelly sandwich
Shampooing hair
Making a pie
EXAMPLE
Is this an algorithm?
Step 1: Wet hair
Step 2: Lather
Step 3: Rinse
Step 4: Repeat
Would you manage to wash your hair with this
algorithm? How about a robot? Why (not)?
ALGORITHMS
An algorithm must:
1. Be well-ordered and unambiguous
2. Each operation must be effectively computable
3. Terminate
EXAMPLE
Problem: Find and print the 100th prime number
• A prime number is a whole number not evenly divisible by any other number other
than 1 and itself
TYPES OF OPERATIONS
Basic operations
• Wet hair
• Rinse
Conditional operations
• If batter is too dry, add water
Repeat/looping operations
• Repeat step 1 and 2 three times
• Repeat steps 2,3,4,…10 until batter becomes soft.
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.
• Let’s you think at an abstract level about the problem.
• Contains only instructions that have a well-defined structure
and resemble programming languages
PSEUDOCODE
Basic (primitive) 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
A MODEL FOR VISUALIZING AN
ALGORITHM
Algorithm
Variables
Operations
An algorithm consists of operations that involve variables
VARIABLES
Variable
• A named memory location that can store a value
• Think of it as a box into which you can store a value, and from which
you can retrieve a value
Examples:
i M
Example of operations
Set the value of i to 3
Set the value of M to i*3 + 12
Set the value of i to i+10
PRIMITIVE OPERATIONS
Get input from user
• Get the value of x from user
Assign values to variables using basic arithmetic operations
• Set the value of x to 3
• Set the value of y to x/10
• Set the value of z to x +25
Print output to user
• Print the value of y, z to the user
EXAMPLE 1
Problem: For any three numbers input by the user,
compute their sum and average and output them
Example of algorithm in pseudocode:
EXAMPLE 2
Problem: Given any value of radius from the user, compute and
print the circumference of a circle with that radius
Algorithm in pseudocode:
START
Display message “How
WHAT IS A FLOWCHART? many hours did you
work?”
Read Hours
Display message “How
A flowchart is a diagram that
much do you get paid
per hour?”
depicts the “flow” of a program.
Read Pay Rate
Multiply Hours by Pay
The figure shown here is a flowchart Rate. Store result in
Gross Pay.
for the pay-calculating program.
Display Gross Pay
END
Rounded
START Rectangle
Display
BASIC FLOWCHART SYMBOLS message “How
many hours did
you work?”
Read Hours
Display
Notice there are three types of symbols in this message “How
much do you Parallelogram
get paid per
flowchart: hour?”
• rounded rectangles Read Pay Rate
• parallelograms Multiply
Hours by Pay
Rectangle Rate. Store
• a rectangle result in
Gross Pay.
Each symbol represents a different type of Display Gross
operation. Rounded Pay
Rectangle
END
START Terminal
Display
BASIC FLOWCHART SYMBOLS
message “How
many hours did
you work?”
Read Hours
Display message “How
Terminals much do you get paid per
hour?”
• represented by rounded rectangles
• indicate a starting or ending point Read Pay Rate
Multiply Hours
by Pay Rate.
START Store result in
Gross Pay.
Display Gross
Pay
END Terminal
END
START
Display
BASIC FLOWCHART SYMBOLS
message “How
many hours did
you work?”
Read Hours
Display message
Input/Output Operations “How much do you
get paid per
Input/Output
Operation
hour?”
• represented by parallelograms
Read Pay Rate
• indicate an input or output operation
Multiply Hours by
Pay Rate. Store
Display result in Gross
Pay.
message “How
Read Hours
many hours Display Gross
Pay
did you work?”
END
START
Display
BASIC FLOWCHART SYMBOLS
message “How
many hours did
you work?”
Read Hours
Display message
Processes “How much do
you get paid per
hour?”
• represented by rectangles
Read Pay Rate
• indicates a process such as a
mathematical computation or variable Multiply Hours
by Pay Rate.
assignment Process Store result in
Gross Pay.
Multiply Hours
Display Gross
by Pay Rate. Pay
Store result in
END
Gross Pay.
START
Stepping Through Display
message “How
Output
Operation
the Flowchart
many hours did
you work?”
Read Hours
Display message
“How much do
How many you get paid per
hour?”
hours did
you work?
Read Pay Rate
Multiply Hours
by Pay Rate.
Store result in
Gross Pay.
Variable Contents:
Hours: ? Display Gross
Pay
Pay Rate: ?
Gross Pay: ? END
START
Stepping Through Display
message “How
many hours did
the Flowchart you work?”
Input Read Hours
Operation
How many
hours did (User types Display message
you work? 40) “How much do
you get paid per
40 hour?”
Read Pay Rate
Multiply Hours
by Pay Rate.
Store result in
Gross Pay.
Variable Contents: Display Gross
Hours: 40 Pay
Pay Rate: ?
END
Gross Pay: ?
START
Stepping Through Display
message “How
many hours did
the Flowchart you work?”
Read Hours
How much do
you get paid Display message
“How much do
per hour? Output you get paid per
Operation hour?”
Read Pay Rate
Multiply Hours by
Pay Rate. Store
result in Gross
Variable Contents: Pay.
Hours: 40
Display Gross
Pay Rate: ? Pay
Gross Pay: ?
END
START
Stepping Through Display
message “How
many hours did
the Flowchart you work?”
Read Hours
How much do
Display
you get paid message “How
per hour? much do you
get paid per
20 hour?”
Input Read Pay Rate
Operation
(User types Multiply Hours by
20) Pay Rate. Store
result in Gross
Pay.
Variable Contents:
Hours: 40 Display Gross
Pay
Pay Rate: 20
Gross Pay: ?
END
START
Stepping Through Display
message “How
many hours did
the Flowchart you work?”
Read Hours
How much
do you get Display message
“How much do
paid per you get paid per
hour? hour?”
Read Pay Rate
Multiply Hours
Process: The by Pay Rate.
Store result in
product of 40
Gross Pay.
times 20 is
Variable Contents: stored in
Hours: 40 Gross Pay Display Gross
Pay
Pay Rate: 20
Gross Pay: 800 END
START
Stepping Through Display
message “How
many hours did
the Flowchart you work?”
Read Hours
Your gross Display message
pay is 800 “How much do
you get paid per
hour?”
Read Pay Rate
Multiply Hours
by Pay Rate.
Store result in
Gross Pay.
Variable Contents:
Hours: 40 Output Display Gross
Pay Rate: 20 Operation Pay
Gross Pay: 800
END
FOUR FLOWCHART
STRUCTURES
Sequence
Decision
Repetition
Case
SEQUENCE STRUCTURE
a series of actions are performed
in sequence
The pay-calculating example
was a sequence flowchart.
DECISION STRUCTURE
One of two possible actions is taken,
depending on a condition.
DECISION STRUCTURE
A new symbol, the diamond,
indicates a yes/no question. NO YES
If the answer is yes, the flow
follows one path.
If the answer is no, the flow
follows another path.
DECISION STRUCTURE
In the flowchart segment
below, the question is asked:
“is x < y?” NO YES
x < y?
If the answer is no, then
process A is performed. Process Process
A B
If the answer is yes, then
process B is performed.
DECISION STRUCTURE
C++ Code
if (x < y)
The flowchart segment a = x * 2;
below shows how a Flowchart
else
decision structure is
a = x + y;
expressed in C++ as an
NO YES
if/else statement. x < y?
Calculate a Calculate a
as x plus y. as x times 2.
DECISION STRUCTURE
C++ Code
if (x < y)
The flowchart segment Flowchart
a = x * 2;
below shows a decision
structure with only one
NO YES
action to perform. x < y?
It is expressed as an if Calculate a
statement in C++ code. as x times 2.
REPETITION STRUCTURE
A repetition structure represents part of the
program that repeats. This type of structure is
commonly known as a loop.
REPETITION STRUCTURE
Notice the use of the diamond
symbol. A loop tests a condition,
and if the condition exists, it
performs an action. Then it tests
the condition again.
If the condition still exists, the
action is repeated.
This continues until the condition
no longer exists.
REPETITION STRUCTURE
In the flowchart segment, the question
“is x < y?” is asked.
YES
If the answer is yes, then Process A is x < y? Process A
performed.
The question “is x < y?” is asked again.
Process A is repeated as long as x is less
than y.
When x is no longer less than y, the
repetition stops and the structure is
exited.
REPETITION STRUCTURE
In the flowchart segment, the question
“is x < y?” is asked.
YES
If the answer is yes, then Process A is x < y? Process A
performed.
The question “is x < y?” is asked again.
Process A is repeated as long as x is less
than y.
When x is no longer less than y, the
repetition stops and the structure is
exited.
REPETITION STRUCTURE
The flowchart segment below shows a repetition
structure expressed in C++ as a while loop.
Flowchart C++ Code
while (x < y)
YES x++;
x < y? Add 1 to x
CONTROLLING A REPETITION
STRUCTURE
The action performed by a repetition structure
must eventually cause the loop to terminate.
Otherwise, an infinite loop is created.
In this flowchart segment, x is never changed.
Once the loop starts, it will never end. YES
x < y? Display x
QUESTION: How can this flowchart be
modified so it is no longer an infinite loop?
A PRE-TEST REPETITION
STRUCTURE
This type of structure is known as a pre-test
repetition structure. The condition is tested
BEFORE any actions are performed.
YES
x < y? Display x Add 1 to x
A PRE-TEST REPETITION
STRUCTURE
In a pre-test repetition structure, if the condition
does not exist, the loop will never begin.
YES
x < y? Display x Add 1 to x
A POST-TEST REPETITION
STRUCTURE
Display x
This flowchart segment shows a post-test
repetition structure.
The condition is tested AFTER the actions Add 1 to
are performed. x
A post-test repetition structure always YES
performs its actions at least once. x < y?
A POST-TEST REPETITION
STRUCTURE
The
flowchart
segment C++ Code
Display x
below shows do
a post-test {
repetition Flowchart cout << x << endl;
Add 1 to x++;
structure x } while (x < y);
expressed in
C++ as a do- YES
x < y?
while loop.
CASE STRUCTURE
One of several possible
actions is taken,
depending on the
contents of a variable.
CASE STRUCTURE
The structure below
indicates actions to perform
depending on the value in CASE
years_employed
years_employed.
1 2 3 Other
bonus = bonus = bonus = bonus =
100 200 400 800
CASE STRUCTURE
If years_employed = If years_employed =
2, bonus is set to 200 3, bonus is set to 400
If years_employed = If years_employed is
CASE
1, bonus is set to 100 years_employed any other value,
bonus is set to 800
1 2 3 Other
bonus = bonus = bonus = bonus =
100 200 400 800
COMBINING STRUCTURES
Structures are commonly combined to create more
complex algorithms.
The flowchart segment below combines a decision
structure with a sequence structure.
YES
x < y? Display x Add 1 to x
COMBINING STRUCTURES
This flowchart segment
NO YES
shows two decision x > min?
structures combined.
Display “x is NO YES
outside the limits.”
x < max?
Display “x is Display “x is
outside the limits.” within limits.”
SUMMARY
1) Flowchart 2) Pseudocode
Start/End Begin/End (not necessary)
Input/Output Read/Print : read x,y
Process [An equation] : x=y+6
Comput: compute x as y+6
Decision If/ if-else / While
Predefined process [function_name()]: average(x,y)
Line Not Applicable
Connector Not Applicable
HOMEWORK
Problem: Given two positive integers, compute their
greatest common divisor
