Introduction

Algorithms

Chapter 1
Algorithms

Philip W. L. Fong

Department of Computer Science

University of Calgary
Calgary, Alberta, Canada

CPSC 331 (Spring 2021)

Philip W. L. Fong Chapter 1: Algorithms

 Introduction
Algorithms

Readings

Chapter 1: The Role of Algorithms in Computing

Philip W. L. Fong Chapter 1: Algorithms

 Introduction
Algorithms

Outline

1 Introduction

2 Algorithms

Philip W. L. Fong Chapter 1: Algorithms

 Introduction
Algorithms

Grading Scheme

Assignments (3 × 18% = 54%)

Tutorial Participation (12 × 0.5% = 6%)
Final Exam (40%)

Philip W. L. Fong Chapter 1: Algorithms

 Introduction
Algorithms

How to be Successful in CPSC 331

Aim for deep understanding (ability to improvise and

create) rather than rote learning

Philip W. L. Fong Chapter 1: Algorithms

 Introduction
Algorithms

How to be Successful in CPSC 331

Aim for deep understanding (ability to improvise and

create) rather than rote learning
Read the textbook, reflectively

Philip W. L. Fong Chapter 1: Algorithms

 Introduction
Algorithms

How to be Successful in CPSC 331

Aim for deep understanding (ability to improvise and

create) rather than rote learning
Read the textbook, reflectively
Attempt lots of exercises

Philip W. L. Fong Chapter 1: Algorithms

 Introduction
Algorithms

How to be Successful in CPSC 331

Aim for deep understanding (ability to improvise and

create) rather than rote learning
Read the textbook, reflectively
Attempt lots of exercises
Catch up with the coursework. Do not fall behind.

Philip W. L. Fong Chapter 1: Algorithms

 Introduction
Algorithms

Outline

1 Introduction

2 Algorithms

Philip W. L. Fong Chapter 1: Algorithms

 Introduction
Algorithms

Computational Problems

Definition (Computational Problem)

Input: a description of input parameters to the problem
Output: a specification of what the desirable results of
computation shall be

Philip W. L. Fong Chapter 1: Algorithms

 Introduction
Algorithms

Computational Problems

Definition (Computational Problem)

Input: a description of input parameters to the problem
Output: a specification of what the desirable results of
computation shall be

Definition (Problem Instance)

An instance of a computational problem is a specific
combination of input parameters for that problem.

Philip W. L. Fong Chapter 1: Algorithms

 Introduction
Algorithms

Example of Problem/Instance
Example (Sorting)
The sorting problem can be stated as follows:
Input: a sequence ha1 , a2 , . . . an i of “keys”
The keys are assumed to be comparable (i.e., supporting
the < operator, which is a binary relation that is irreflexive,
asymmetric, and transitive).
Output: a permutation hb1 , b2 , . . . , bn i of the input
sequence that is in ascending order
Here is an instance of the sorting problem:

h3, 1, 4, 2, 5i

The expected output would be the following:

h1, 2, 3, 4, 5i
Philip W. L. Fong Chapter 1: Algorithms
 Introduction
Algorithms

Preconditions and Postconditions

The input description typically specifies two things:

the type of each parameter
conditions that are assumed of the inputs, also known as
preconditions
the preconditions may also specify assumptions on the state
of the computational environment

Philip W. L. Fong Chapter 1: Algorithms

 Introduction
Algorithms

Preconditions and Postconditions

The input description typically specifies two things:

the type of each parameter
conditions that are assumed of the inputs, also known as
preconditions
the preconditions may also specify assumptions on the state
of the computational environment
The output specification tells us two things:
the type of return values
conditions that must be met by the output, also known as
postconditions, when the inputs satisfy the preconditions
the postconditions may also specify how the state of the
computational environment should be altered (aka side
effects)

Philip W. L. Fong Chapter 1: Algorithms

 Introduction
Algorithms

Algorithms

Definition (Algorithm)
An algorithm is a platform-independent and language-agnostic
presentation of a computational procedure. It is typically
designed to solve a given computational problem.

Two key phrases:

1 platform-independent and language-agnostic
2 solve

Philip W. L. Fong Chapter 1: Algorithms

 Introduction
Algorithms

Keyword: “solve”

By saying that an algorithm A solves a computational

problem P, it means that, whenever A is given inputs that
match the parameter description of P, it is guaranteed that
A will (a) terminate in finite time and (b) produce results
that satisfy the output specification of P.

Philip W. L. Fong Chapter 1: Algorithms

 Introduction
Algorithms

Keyword: “platform-independent & language-agnostic”

We aspire to present the computational procedure in a

platform-independent and language-agnostic manner.
Not only for Windows, OS X, or Linux.
Not only for Java, C++, or Python.
Only an ideal. Usually assume:
a von Neumann architecture with Random Access Memory
an imperative programming paradigm that is supported by
mainstream programming languages
We don’t present computational procedures in a particular
programming language. We instead employ abstract
presentation.

Philip W. L. Fong Chapter 1: Algorithms

 Introduction
Algorithms

Presentation of Algorithms (1)

One abstract presentation scheme is pseudocode, as

found in the textbook (pages 20–22, under the heading
“Pseudocode conventions”).
Pseudocode is not “code”: it is an abstract presentation of
computational steps.
It can be easily translated to a programming language by a
competent programmer.

Philip W. L. Fong Chapter 1: Algorithms

 Introduction
Algorithms

Presentation of Algorithms (2)

One objection to the textbook is that the pseudocode looks

like actual “code.” It draws the reader away from the big
ideas. The reader ends up focusing too narrowly on the
technical details.
Use elegant and succinct English writing whenever
possible to highlight the essence of a computational step.
In your pseudocode, aspire to use mathematical notations
when possible. Do not use code-like constructs. Math is
the universal language.

Philip W. L. Fong Chapter 1: Algorithms

 Introduction
Algorithms

Presentation of Algorithms (3)

Remark
I will use the criteria of the previous 3 slides to grade your work.

Philip W. L. Fong Chapter 1: Algorithms

 Introduction
Algorithms

Insertion Sort (1)

Algorithm 1: I NSERTION -S ORT(A)
1 for j = 2 to A.length do
2 key = A[j];
3 Insert key into the sorted subarray A[1 .. j − 1];

key
ii
I
j
sorted prefix
wtf
processed
Philip W. L. Fong Chapter 1: Algorithms
 Introduction
Algorithms

Insertion Sort (2)

Algorithm 2: I NSERTION -S ORT(A)

1 for j = 2 to A.length do
2 key = A[j];
// Insert key into the sorted subarray A[1 .. j − 1].
3 i = j − 1;
4 while i > 0 and A[i] > key do
5 A[i + 1] = A[i];
6 i = i − 1;
7 A[i + 1] = key ;

Philip W. L. Fong Chapter 1: Algorithms

 Introduction
Algorithms

Remarks

Compare the English sentence to the elaboration. The

high-level intention is very clear from the English writing,
but it becomes obscure in the details.
It is therefore okay to write in English. In occasions such
as the above, we may need to elaborate the English writing
to detailed computational steps.
When you write your pseudocode, you need to decide
which level of details is the most appropriate. What I find
most useful, sometimes, is to give a multi-round
presentation. Start with laying out the intention, and then
elaborate the details in subsequent rounds of presentation.

Philip W. L. Fong Chapter 1: Algorithms

 Introduction
Algorithms

Insertion Sort in English

To sort a sequence of elements:

Consider each element of the sequence in turn, starting
from the lower indices, and proceeding to the higher
indices.
Remark: By now, the prefix of the sequence that is to the
left of the element under consideration is already sorted.
Take out the current element.
Insert that element into the prefix to its left.

Exercise
What are the strengths and weaknesses of this presentation of
insertion sort?

Philip W. L. Fong Chapter 1: Algorithms