Chapter 3
ALGORITHMS. INTEGERS
OUR GOAL
• Algorithms
• Linear search Binary search (Group 1)
• Bubble Sort Insertion sort (Group 2)
• The growth of functions (VinhDP)
• Complexity (VinhDP)
• Integers
• Divisibility: mod, div, congruent (Group 3)
• Applications of mod: (Group 4)
• Integer representations (Group 5)
• Primes and composites, gcd and lcm, The
Euclidean algorithm (Group 6)
Algorithms
• An algorithm is a finite sequence of precise
instructions for performing a computation or
for solving a problem.
• Language: natural language, programming
language, pseudocode
• Example.
Properties
• Input.
• Output.
• Definiteness. // defined precisely
• Correctness. // correct output
• Finiteness. // finite number of steps for any input in
the set.
• Effectiveness. // in a finite amount of time.
• Generality // not just for a particular set of input values.
Algorithms
• Linear search O(n)
• Binary search O(logn)
• Bubble sort O(n2)
• Insertion sort O(n2)
The linear search algorithm
procedure linear search(x: integer, a 1, a2, ..., an:
distinct integers)
i := 1
while (i ≤ n and x axi ) a ?x a ?x a ?
1 2 3
i := i + 1 a1 a2 a3 … an
if i ≤ n then location := i
else location := 0
return location {location is the subscript of the term that
equals x, or is0 if x is not found}
How many comparisons (i ≤ n, x ai ) are required?
(e.g., finding x = 7 from the list 3, 1, 5, 7, 4, 9)
The binary search algorithm
procedure binary search (x: integer, a1, a2, ...,an: increasing
integers)
i := 1
j := n
Finding x = 7
while i < j
i=1 j=8
m := (i + j)/2
2 3 5 6 7 8 10 13
if x > am then i := m + 1
m=4
else j := m x=7
i=5 j=8
if x = ai then location := i
else location := 0 7 8 10 13
m=6
return location x=7
{location = i if ai = x, or 0 j=6
i=
if x is not found} 5 7 8
m=5
Linear and Binary
Search
( Linear search )
Sorting algorithms
• Bubble sort
• Insertion sort
• More (in later chapters or in
exercises)
• Merge sort (chapter 4) // one
of the fastest
• Tournament sort (chapter 10)
Bubble sort
i=1 i=2
3a 2 2 2 2 a <a 2 2
1 >a2 1 2
2 3 3 3 3 3 1
a2<a3 a2>a3
4 4 4 1 1 1 3
a3 >a4 a3<a4
1 1 1 4 4 4 4
a4<a5
5 5 5 5 5 5 5
Bubble sort
i=3 i=4
2 1 1a
a1>a2 1 <a2
1 2 2
a2<a3
3 3 3
4 4 4
5 5 5
sorted
The bubble sort
procedure bubblesort(a1,...,an :
real numbers with n ≥ 2)
for i := 1 to n − 1
for j := 1 to n − i
if aj > aj+1 then swap(aj,
aj+1)
{output: a1,...,an is in
increasing order}
The Insertion sort
procedure insertion sort(a1,a2,...,an: real numbers with n
≥ 2)
for j := 2 to n // begin with the 2nd element
i := 1
while aj > ai // find the first element with incorrect position
i := i + 1 3 2j = 2 4 1 5
m := aj
for k := 0 to j − i − 1
2 3 j4= 3 1 5
aj−k := aj−k−1 2 3 4 1
j=4
5
i=1 m=1
ai := m // insert aj into ai
2
{a1, ... ,an is in increasing order} 2 3 4 5
It is usually not the most efficient. 1 2 3 4 5
1 2 3 4 5
The growth of functions
• Bubble sort: (n – 1).n/2
comparisons for sorting n
elements
• An other sorting algorithm: using
2nlog2n + 3n + 13 comparisons.
• Which one should be used?
The growth of important functions
1 < logn < n < nlogn < n2 < n3 < 2n < n!
How to estimate big-O of other
functions?
• How to estimate big-oh of functions such as
100n2 + 23nlog(n3) + 2017?
Using some rules in practice:
– 1. f(n) is O(g(n)) Cf(n) is O(g(n))
Ignore constants
– 2. If f1(n) = O(g1(n)) and f2(n) = O(g2(n)), then
o (f1 + f2)(n) = O(max(|g1(n)|,Ignore added
|g2(n)|).
smaller order
o (f1.f2)(n) = O(g1.g2(n)) terms
Ex1. 3n is O(n) and 2n2 is O(n2)
3n + 2n2 is O(n2) And 3n.(2n2) is O(n3)
Ex2. 100n2 + 23nlog(n3) + 2017 is O(?)
log(n3) = 3logn = O(logn), nlogn is O(n2)
Answer: O(n2)
Complexity of algorithms
Estimate big-oh
procedure printsth(n: positive integer)
begin
for i:=1 to n do
print “hi” n + n =2n is O(n)
for k:=1 to n do
print “I love you”
end
Estimate big-O of the given algorithm
Estimate big-oh
procedure printsth(n: positive integer)
begin
for i:=1 to n do
for k:=1 to n do
print “I love you”
end
Estimate big-O of the given algorithm
n+n+…+n
= n.n = n2 is O(n2)
O(n2) time complexity
Estimate big-oh
procedure printsth(n: positive integer)
begin
for i:=1 to n do
for k:=1 to n do
for j:=1 to n print do
print “I love you”
end
Estimate big-O of the given algorithm
n2 + n 2 + … + n 2
= n.n2 = n3 is O(n3)
O(n3) time complexity
Estimate big-oh
procedure printsth(n: positive integer)
begin
For i:=1 to n do
print “hi”
For j:=1 to n do
For k:=1 to i do
print “I love you”
end
Estimate big-O of the given algorithm
n + n2 is O(n2)
Divisibility
dividend 37 5 divisor
2 7
Quotient = 37 div 5
Remainder
37 mod 5
37 – 5 = 32 // count =1
32 – 5 = 27 // count =2
27 - 5 = 22
22 – 5 = 17
17 – 5 = 12
12 – 5 = 7
7–5=2 // count = 7
2 < 5 stop
-37 5
-37 = 5(-7) + (-2)
-37 = 5(-7) + 2 ???
-37 = 5(-8) + 3 OK
Remainder = 3, quotient = -8
a m b m
r q1 r q2
a b (mod m)
Read: a is congruent to b modulo m
Applications
Cryptography
Cryptography:
Encryption: LOVE SVCL
Decryption: LOVE SVCL
A B C D E
F G H I J
Bob Alice K L M N O
LOVE SVCL SVCL LOVE P Q R S T
U V W X Y Z
Use f(p) = (p + 7) mod 26 to
encode the message
OK.
OK 14 10 21 170 1 VR
A B
2
C D E
F G H I J
K L M N O
P Q R S T
U V W X Y Z
23 24 25
Applications
• Pseudorandom numbers
What sequence of pseudorandom numbers is
generated using the pure multiplicative
generator
xn + 1 = 3xn mod 11 with seed x0 = 2?
If xn + 1 = 3xn + 5 mod 7 and x3 = 3, what are x2
and x4?
Applications
Hashing function - example.
Suppose that a computer has only the memory
locations 0, 1, 2, …, 19. Use the hashing
function h where
h(x) = (x + 5) mod 20
to determine the memory locations in which 57
is stored.
Integer representations
• 23215 seconds = (? hours ? minutes and ?
seconds)
• Suppose a “day” = 13 hours, an “hour” = 13
minutes, and a “minute” = 13 seconds.
3153 sec = d hr m sec
• (3 5 11)60 = ?
• (5 1 7)13 = ?
• Convert (3215)13 to decimal expansion
• Find the base 5 expansion of the integer 73
• Base b expansion:
n = akbk + ak-1bk-1 + … + a2b2 + a1b1 + a0
n = (akak-1…a1a0)b
• Base 2 = binary: {0, 1}
• Base 3: {0, 1, 2}
…
• Base 8 = octal : {0, 1, 2, 3, 4, 5, 6, 7}
…
• Base 13: {0..9, A, B, C}
…
• Base 16 = hexadecimal: {0..9, A..F}
…
gcd, lcm
• gcd (a, b) : greatest common divisor
– What is the fastest way to find gcd(a, b)?
• lcm(a, b) : least common multiple
• gcd(a,b).lcm(a,b) = a.b for integers a, b > 0
Euclidean algorithm to find gcd(a,
b)
procedure gcd(a, b: integers)
while (b 0) do
r := a mod b # r: remainder
a := b
b := r
return (a)
The Euclidean Algorithm example
Suppose r = a mod b
gcd(a, b) = gcd(a mod b, b) = gcd(r, b)
procedure(a, b: integers) // a =14, b = 6
i : =0
While b < > 0 b = 6 b=2 b=0
a: = b a=6 a=2 gcd(14,
6) =2
b: = a mod b b=2 b=0
i:=i+1 i =1 i=2
{gcd(a, b) = a}
Challenge. $30,000 prize if you can factorize
this number
74037563479561712828046796097429573142
59318888923128084936232638972765034028
26627689199641962511784399584330502127
58537011896809828673317327310893090055
25051687706329907239638078671008609696
2537934650563796359
Review – chapter 3
Encrypt the message NEW using the function f
(p) = (p + 11) mod 26.
