Introduction to

Algorithm
• COURSE DESCRIPTION
Subject: Introduction to Algorithm • Computational Thinking
Lecturer: Hoang Do Thanh Tung • Why to study algorithms?
• Some simple examples
Credit points 3 ECTS
Level Undergraduate • How to study algorithms?
Teaching time
University of Science and Technology of Hanoi
Location
COURSE DESCRIPTION
Course Goals
 Give introduction to Algorithms
 For the students, who take the first algorithm course, to imagine
what/why/how is to study algorithms
 Learn how to express algorithms with pseudo-code and diagram.
Text Book and Reference Books

 Text Book:
 Jeff Erickson. Algorithms. Independently published. 2019.
 Mark A. Weiss . Data Structures & Algorithm Analysis in C++ 4th
Edition. Pearson, 2014.
 Reference Books:
 Sanjoy Dasgupta. Algorithms. McGraw-Hill, 2006.
 Cormen, Leiserson, Rivest, Introduction to Algorithms, 2nd Ed.,
MIT Press, 2001.
Examination and Grading

 Examination
 A midterm exam with an assignment
 A final exam
 Grading
 Attendance/Attitude 10%
 Class exercise and Lab practices 20%
 A midterm exam 20%
 Final exam 50%
Course Prerequisite

Assumption: students don't know programming but concepts as following

 Fundamental data types: decimal number
 Iterative programming concepts: variables, conditionals, iteration, recursion
 High-school algebra
Course plan

 Class Schedule (1 week of theory, 1 week of practice, alternating)

 Theory: 3 hours per lesson, 2 lessons per week
 Practical: 2 hours per lesson
 Material
 moodle.usth.edu.vn
 Modeling Tool for practice
 https://app.diagrams.net/
 Use Chatting for QA to chat and submit your practices
 Each student uses the paper with their computers or smartphones to do
practice
Why Study this Course?

 The more we reduce ourselves to machines in the lower things, the

more force we shall set free to use in the higher. — Anna C. Brackett,
The Technique of Rest (1892)
 Donald E. Knuth stated “Computer Science is the study of algorithms”
 Cornerstone of computer science. Programs will not exist without algorithms.
 Closely related to our lives
 Help to guide how others analyze and solve problems
 Help to develop the ability of analyzing and solving problems via
computers
 Very interesting if you can concentrate on this course
Start with Computational Thinking

 Computational thinking is an approach to solving problems

 using concepts and ideas from computer science, and
 expressing solutions to those problems so that they can be run on a computer.
 Computational thinking is used everywhere by many different types of people.
 computer scientists and engineers, professionals in business, medicine, education, life sciences, social
sciences..
 Understanding computational thinking will be one of the fundamental core skills in all walks of life in the
21st century.
 Computational thinking can be used to solve problems that have real-world social impact.
 For example, mapping the human genome,
 predicting the spread of infectious disease,
 coordinating disaster relief efforts,
 and understanding the impact of government policies.
Key methods in Computational thinking
Decomposition
 Tt is breaking down large complex problems into smaller problems that are
easy to understand and to manage
Break down
Why to study algorithm?
What do you want in your life, to
be fed or fish?
Rules to study this course

 You are totally able to read my slides, course books, materials in internet so
 We don’t have to be hurry to fulfill all slides
 We try to understand each step we reach
 You don’t ask me for solutions first,
 You give me problems you meet
 You try to find the solutions yourself with your computer first
 We discuss about the result
Algorithm: A brief History

 Muhammad ibn Musa al-Khwarizmi, one of the

most influential mathematicians in 9th century in
Baghdad, wrote a textbook in Arabic about adding,
multiplying, dividing numbers, and extracting square
roots and computing π.
 Many centuries later, decimal system was adopted in
Europe, and the procedures in Al Khwarizmi’s book
were named after him as “Algorithms”.
 Alan Turing formalised Turing Machine in 1936, the
foundation of computer science.
Where is Problem, Algorithm, Mathematics?

You have to pick your sisters up at 5pm everyday with $4 budget

Bus ($2 )
Taxi, Grab bike (> $3)
Speed >= Subway

Subway: 30 minutes, 4.30PM (last)

Price: $2 Time to leave varies: 4.15-4.45pm
What is an Algorithm?
 An algorithm is an sequence of elementary
instructions
 Explicit
 Precise
 Unambiguous
 Mechanically-executable
For example

 An algorithm for singing that annoying song ‘99 Bottles of Beer on the Wall’,
for arbitrary values of 99:
 So What is an algorithm for Computer?
An algorithm is a sequence of unambiguous instructions for
solving a problem

input

problem “computer” algorithm

output
Properties of computer Algorithms

 Finiteness: must eventually terminate

 Definiteness: each step is precisely defined, there
is no ambiguity
 Input: information which is required in order to
start the algorithm
 Output: result of the algorithm, with some relation
to the input
 Effectiveness: should be able to be emulated
manually (paper and pencil)
Important problem types

 sorting

 searching

 string processing

 graph problems

 combinatorial problems

 geometric problems

 numerical problems
Programming vs. Problem Solving

 Two very distinct tasks!

 Problem solving:
 developing a solution to a problem
 result is an algorithm or a plan for the solution
 Programming:
 converting the solution into a computer readable form (C,
assembly, VB, Delphi, etc..)
 Programmers are cheap – problem solvers are not!
 eg, architect, engineer vs. bricklayers, carpenters, etc..
Why study algorithms?

 Theoretical importance

 the core of computer science

 Practical importance

 A practitioner’s toolkit of known algorithms

 Framework for designing and analyzing algorithms for new problems

Example: Google’s PageRank Technology

Some simple examples
Algorithm Examples

 Humans solve problems intuitively without usually formalising the steps

involved
 Consider:
 passing this course
 making a cup of tea
 multiplying two numbers
 determining if a number is prime
 finding the largest number in a list
Do you understand this?

 Is the following a legitimate algorithm?

i 1

While (i <= 10) do

ai+1
Print the value of a
End of loop
Stop
Examples of Algorithms – Computing the
Greatest Common Divisor of Two Integers
The greatest common divisor of two non-negative, not-both-zero integers
m and n, denoted gcd(m, n), is defined as the largest integer that divides
both m and n evenly, until the remainder is zero
 Euclid’s algorithm is based on repeated application of equality until the
second number becomes 0
gcd(m, n) = gcd(n, m mod n)

 For example gcd(60, 24) can be computed as follows:

gcd(60, 24) = gcd(24, 12) = gcd(12, 0) = 12
Computing the Greatest Common Divisor
of Two Integers
Here is more structured description of this algorithm:
Euclid’s Algorithm for computing gcd(m, n)

 Step1: If n = 0, return the value of m as the answer and stop;

otherwise, proceed to Step 2.

 Step2: Divide m by n and assign the value of the remainder to

r.

 Step 3: Assign the value of n to m and the value of r to n. Go

to Step 1.
Two descriptions of Euclid’s algorithm
Statement:
Step 1 If n = 0, return m and stop; otherwise go to Step 2
Step 2 Divide m by n and assign the value of the remainder to r
Step 3 Assign the value of n to m and the value of r to n. Go to
Step 1.

Pseodocode:
Algorithm Euclid(m, n)
while n ≠ 0 do
r  m mod n
mn
nr
return m
Other methods for computing gcd(m,n)
Consecutive integer checking algorithm
Step 1 Assign the value of min{m,n} to t
Step 2 Divide m by t. If the remainder is 0, go to Step 3;
otherwise, go to Step 4
Step 3 Divide n by t. If the remainder is 0, return t and stop;
otherwise, go to Step 4
Step 4 Decrease t by 1 and go to Step 2

For example, for number 60 and 24, the algorithm will

try first 24, then 23, and so on until it reaches 12, where
it stops.

Is this slower than Euclid’s algorithm? How much slower?

O(n), if n <= m , vs O(log n)
1-43
 Other methods for gcd(m,n) [cont.]
Middle-school procedure
Step 1 Find the prime factorization of m
Step 2 Find the prime factorization of n
Step 3 Find all the common prime factors
Step 4 Compute the product of all the common prime factors
and return it as gcd(m,n)

Thus, for the numbers 60 and 24, we get

60 = 2.2.3.5
24 = 2.2.2.3
gcd(60,24) = 2.2.3 = 12
Is this an algorithm?

How efficient is it?

Time complexity: O(sqrt(n))
What can we learn from the previous 3
examples?

 Each step of an algorithm must be unambiguous.

 The same algorithm can be represented in several different ways. (different

pseudo-codes)

 There might exists more than one algorithm for a certain problem.

 Algorithms for the same problem can be based on very different ideas and can
solve the problem with dramatically different speeds.
How do we check attendances in a class?
How to study algorithms?
Basic Issues to study Algorithms

 How to design algorithms

 How to express algorithms
 Proving correctness
 Efficiency (or complexity) analysis
 Theoretical analysis
 Empirical analysis
 Optimality
Algorithm Representation Example

 Simple directions to a destination:

 Plain English:

Go straight on to the traffic lights, turn left and take the third turning on the right. If the
red gate is open then go through it, otherwise go through the green gate.
Algorithm Representation Example

 Flowchart:
Algorithm Design and Analysis Process
Algorithm Design
Techniques/Strategies
 Brute force Greedy approach

 Divide and conquer Dynamic programming

Backtracking
 Decrease and conquer

Branch and bound

 Transform and conquer

 Space and time

tradeoffs
Analysis of Algorithms

 How good is the algorithm?

 Correctness
 Time efficiency
 Space efficiency

 Does there exist a better algorithm?

 Lower bounds
 Optimality