CMPT 120

Topic: Introduction to Computing Science

Last Lecture
• Introduce the course
• What is this course all about?
• What resources do we have to learn the stuff?

2
• Little activity
• How to get ready for next lecture?

• Any questions related to our course web site?

http://www.cs.sfu.ca/CC/120/alavergn/
2
Today’s Menu
• What is Computing Science?
• Algorithm

3
3
Learning Outcomes
At the end of this course, a student is expected to:
• Describe fundamental concepts pertaining to
computing science

4
• Computing science
• Problem solving
• Algorithm
• Decomposition

4
What is this course all about?
• Course Title: “Introduction to Computing Science
and Programming 1”

Learn fundamental
concepts of
computing science

5
This slide is from our Lecture 1.
 What is Computing Science?
• Lot’s of answers out there
• For example:
• On youtube:
http://www.youtube.com/watch?v=U0luqHYa0EI
• On wiki: http://en.wikipedia.org/wiki/Computer_science

Will look at
• In a nutshell: Computer/Computing science is
this step 1. Creating solutions to problems (solution expressed as an
today. algorithm)
2. Analysing these algorithms (does it solve the problem? is
it efficient? etc…)
3. Automating these algorithms, often using computers
Will look at the first question
when we talk about “testing” Will look at this
and the second question 6
step throughout
when we talk about algorithm the rest of software
analysis. the semester.
Areas of Computing Science
• On wiki:
http://en.wikipedia.org/wiki/Computer_science

• Research at the School of Computing Science at SFU:

http://www.cs.sfu.ca/research/groups/

7
Computer versus Computing
• Computer: a tool

• “Despite its name, a significant amount of computer

science does not involve the study of computers
themselves.”
Reference: http://en.wikipedia.org/wiki/Computer_science

• Computing: field of study

• According to
http://wordnetweb.princeton.edu/perl/webwn?s=computation
• The terms “calculation”, ”computation” and
“computing” are synonymous and they signify:
• “The procedure of calculating; determining something by 8
mathematical or logical methods.”
• Definition of Computation: problem solving that involves
numbers or quantities.
What is Computing Science?
• Lot’s of answers out there
• For example:
• On youtube:
http://www.youtube.com/watch?v=U0luqHYa0EI
• On wiki: http://en.wikipedia.org/wiki/Computer_science
• In a nutshell: Computer/Computing science is
1. Creating solutions to problems (solution expressed as an
algorithm)
2. Analysing these algorithms (does it solve the problem? is
it efficient? etc…)
3. Automating these algorithms, often using computers

9
software
Algorithm – Example
• Problem:
• You have no more milk.

• Solution: High level algorithm:

It describes a solution
• Buy some milk. to the problem without
details.

• “Implement” the solution:

• Your new roommate tells
you to go buy some milk.
• Hum…? 10
Decomposition – Example
• We may not have
sufficient details to
implement the algorithm
and solve the problem!
• So we need to
decompose the algorithm
into “finer” steps (more
detailed steps)
Low level algorithm:
• Go to neighbourhood It describes the steps
corner store of a solution
• Buy 2 liters of organic to the problem in
homo milk (cow milk) details.
11
Algorithm – Another example
• Let’s create an algorithm that solves the
following problem (or task):

Get myself to SFU in the morning

12
Example – Get myself to SFU
in the morning
• Here is a high-level (i.e., no details) algorithm that’s
solves this problem, expressed in English
• Wake up
• Wash ourselves
• Eat breakfast
• Take the bus

• Observations:
• The steps may appear ambiguous to the person that is
to perform them, s/he may require more details 13
Example – Get myself to SFU
in the morning
• We disambiguate or “detail” the steps of a high-
level algorithm by decomposing each of its steps
into more detailed steps
• One way to do this is by asking
-> “What do you mean …”
when considering a step

• This is how we go from a high-level to a low-level

algorithm of the solution to our problem

• Let’s try!
14
Example – Get myself to SFU
in the morning
• What do you mean “Wake up”?
• I mean:
• stop clock alarm
• get out of bed
• …

15
Example – Get myself to SFU
in the morning
• What do you mean “Wash ourselves”?
• I mean:
• Turn on water
• Get undressed
• Step into shower
• Wash
• Here, again “What do you mean “Wash”?
• I mean:
• Shampoo my hair
• Rinse my hair
• Apply conditioner
• Rinse my hair some more
• Soap up my body
• Rinse my body
• …
• Step out of shower 16
• Dry myself
• …
Example – Get ready to go to
SFU in the morning
• See if you can continue this process of getting more
details by asking “What do you mean …” with the
rest of the steps of the high-level algorithm
• In other words, see if you can continue creating the
low-level (detailed) algorithm of our solution

17
Example – Get ready to go to
SFU in the morning
• Eat breakfast
•
•
•
•
•
•
•

18
Example – Get ready to go to
SFU in the morning
• Take the bus
•
•
•
•
•
•
•

19
Algorithm – observations?

21
Algorithm - Definition
• A finite sequenced set of unambiguous steps
• This set of steps executes in a finite amount of
time i.e. it should finish at some point, and when
it does, it produces a result
• This result solves the initial problem
• The algorithm also describes
• The input it is expecting, if any
• The output it is producing

22
More about algorithm
• https://www.khanacademy.org/computing/compu
ter-science/algorithms/intro-to-algorithms/v/what-
are-algorithms

23
How do we express an
algorithm?
1. Use a natural language like English
• Example:
• Problem/task: Figure out your course final grade
• Take all the grades you obtained in course activities (e.g.,
assignments, exams, etc…)
• Compute each grade as a % of final grade
• Add them up for a total of 100%

24
How do we express an
algorithm?
2. Use a mix of natural language and computer
language -> pseudocode
• Example:
• Problem/task: Figure out your course final grade
• Read each grade until EOF
• finalGrade = 0
• For each grade
• Set percentOfFinalGrade to this grade’s % of the final grade
• Set gradedOutOf to this grade’s max
• Compute newGrade: (grade * percentOfFinalGrade ) / gradedOutOf
• Keep a running total: finalGrade = finalGrade + newGrade
• Print finalGrade
• Else
• Print “Do not have all grades!”
25
How do we express
an algorithm?
3. Use a
flowchart

26
How do we express
an algorithm?
4.
http://www.ikea.com/ms/en_US/customer_service/as
sembly_instructions.html

27
Why do we need algorithms?

28