Transcript CS107: Introduction to Computer Science

CSE 102
Introduction to Computer Engineering
What is an Algorithm?
What is an algorithm?
An algorithm is a well-defined procedure that
allows the computer to solve a problem.
What is an algorithm?
Example algorithms:
• Cooking a dish
• Making a peanut-butter jelly sandwich
• Shampooing hair
• Programming a VCR
• 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:
• be well-ordered and unambiguous,
• each operation must be effectively computable,
• 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
Algorithm (?):
1. Generate a list of all prime numbers n1, n2, n3, …
2. Sort the list in ascending order
3. Print out the 100th element in this list
Is this an algorithm?
Algorithms
An algorithm consists of:
• the actions to be executed, and
• the order in which the actions are to be executed
Example
Problem: Find the sum of the first 5 numbers in a list.
Actions:
• Set the initial value of SUM to 0
• Take the first number from the list
• Add the number to SUM
• Take the next number from the list
Algorithm:
1. Set the initial value of SUM to 0
2. Take the first number from the list
3. Add the number to SUM
4. Take the next number from the list
5. Repeat steps 3-4 five times
Pseudocode
Pseudocode is an informal language that helps
programmers develop algorithms.
Example
Problem: Find the sum of the first 5 numbers in a list.
Pseudocode:
1. SUM ← 0
2. N ← first number in the list
3. SUM ← SUM + N
4. N ← next number in the list
5. Repeat steps 3-4 five times
Flowchart
Flowchart is a graphical representation of an
algorithm.
Example
Problem: Find the sum of the first 5 numbers in a list.
start
SUM ← 0
N ← first number in the list
SUM ← SUM + N
N ← next number in the list
False
five times
exit
True
Flowchart
Flowchart symbols:
• Sequence structure
• Selection structure
• Repetition structure
Flowchart
Sequence structure
SUM ← 0
Flowchart
Selection structure
False
N>50
True
Flowchart
Repetition structure
repeated action
True
condition
False
Example
Problem: Read the grades of 20 students and print “passed” if the grade is
greater than or equal to 50, otherwise print “failed”.
COUNT ← 0
Read grade
Print “failed”
False
grade >= 50
True
COUNT ← COUNT+1
False
COUNT=20
True
exit
Print “passed”
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
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
M
A model for visualizing an algorithm
Algorithm
Variables
Operations
An algorithm consists of operations that involve variables
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
Problem: For any three numbers input by the user, compute
their sum and average, and output them
Example of algorithm in pseudocode:
Variables: a, b, c, sum, avg
1. Get the values of a, b, c from user
2. Set avg to (a+b+c)/3
3. Set sum to (a+b+c)
4. Print sum and avg
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:
variables: r, c
1. Get the value of r from user
2. Set c to 2 * pi * r
3. Print “The circumference of your circle is “ c
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 A is greater than 5
then set the value of B to 1
else set the value of B to 0
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
a←1
Equivalent:
–
–
–
–
–
Add 1 to count
Set count to count + 1
Increment the value of count by 1
count = count + 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
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.
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