Transcript Algorithms

Algorithms

Readings: [SG] Ch. 2 & 3

Chapter Outline:
1. Chapter Goals
2. What are Algorithms
1. Real Life Examples (origami, recipes)
2. Definition
3. Example: A = B + C
3.
4.
5.
6.
Expressing Algorithms – Pseudo-Code
Simple Algorithms
Recursive Algorithms
Time Complexity of Algorithms
(UIT2201: Algorithms) Page 1
LeongHW, SoC, NUS
Algorithms
 Computing
devices are dumb
 How to explain to a dumb mechanical /
computing device how to solve a problem
 How
to solve a problem using
“a small, basic set of primitive
instructions”.
 Complexity
of Solving Problems.
(UIT2201: Algorithms) Page 2
LeongHW, SoC, NUS
1. Goals of Algorithm Study

To develop framework for instructing
computer to perform tasks

To introduce notion of algorithm as means of
specifying how to solve a problem

To introduce and appreciate approaches for
defining and solving very complex tasks in
terms of simpler tasks;
(UIT2201: Algorithms) Page 3
LeongHW, SoC, NUS

Chapter Outline:
1. Chapter Goals
2. What are Algorithms
1. Real Life Examples (origami, recipes)
2. Definition of Algorithm
3. Example: A = B + C
3.
4.
5.
6.
Expressing Algorithms – Pseudo-Code
Simple Algorithms
Recursive Algorithms
Time Complexity of Algorithms
(UIT2201: Algorithms) Page 4
LeongHW, SoC, NUS
2. Computer Science and Algorithms…
 Computer
Science can be considered…
as study of algorithms including
their formal properties
Their hardware and software realisations
Their applications to diverse areas
(UIT2201: Algorithms) Page 5
LeongHW, SoC, NUS
Algorithms: Real Life Examples
 Many
Real-Life Examples
 Cooking: Recipe for preparing a dish
 Origami: The Art of Paper Folding
 Directions: How to go to Changi Airport
 Remember:
 Framework: How to give instructions;
 Alg: The actual step-by-step instructions;
 Abstraction: Decomposing / Simplifying
(UIT2201: Algorithms) Page 6
LeongHW, SoC, NUS
Real Life Example: Cooking
 Framework:
“Cooking or Recipe language”
 Algorithm:
“Recipe for a Dish”
(step by step instructions on how to cook a dish)
 Problem
Decomposition
 Preparing Ingredients;
 Preparing Sauce;
(UIT2201: Algorithms) Page 7
LeongHW, SoC, NUS
Real Life Example: Origami
 Framework:
“Origami or Paper-Folding language”
 Algorithm:
“Sequence of Paper-Folding Instructions”
(step by step instructions for each fold)
 Problem
Decomposition
 Start with a Bird Base; …
 Finish the Head;
 Finish the Legs; Finish the Tail;
(UIT2201: Algorithms) Page 8
LeongHW, SoC, NUS
Real Life Examples: Issues
 Problems/Difficulties:
 Imprecise Instructions;
 Job can often be done even if instructions are
not followed precisely
 Modifications may be done by the person
following the instructions;
 But,
NOT for a Computer
 Needs to told PRECISELY what to do;
Instructions must be PRECISE;
Cannot be vague or ambiguous
(UIT2201: Algorithms) Page 9
LeongHW, SoC, NUS
Definition of Algorithm:
 An
algorithm for solving a problem
“a finite sequence of unambiguous, executable
steps or instructions, which, if followed would
ultimately terminate and give the solution of
the problem”.

Note the keywords:




Finite set of steps;
Unambiguous;
Executable;
Terminates;
(UIT2201: Algorithms) Page 10
LeongHW, SoC, NUS
Algorithm Examples?

Problem 1: What is the largest integer
INPUT: All the integers { … -2, -1, 0, 1, 2, … }
OUTPUT: The largest integer
Algorithm:
 Arrange all the integers in a list in decreasing order;
 MAX = first number in the list;
 Print out MAX;
 WHY is the above NOT an Algorithm?
 (Hint: How many integers are there?)

Problem 2: Who is the tallest women in the world?
 Algorithm: Tutorial...
(UIT2201: Algorithms) Page 11
LeongHW, SoC, NUS
Example: Adding two (n-digit) numbers
 Input: Two positive m-digit decimal numbers
(a and b)
am, am-1, …., a1
bm, bm-1, …., b1
 Output: The sum c = a + b
cm+1, cm, cm-1, …., c1
(Note: In the textbook, it was am-1,…,a1,a0 …)
(UIT2201: Algorithms) Page 12
LeongHW, SoC, NUS
How to “derive” the algorithm
 Adding
is something we all know
 done it a thousand times, know it “by heart”
 How
do we give the algorithm?
 A step-by-step instruction
 to a dumb machine
 Try
an example:
3492
8157
“Imagine you looking at yourself solving it”
(UIT2201: Algorithms) Page 13
LeongHW, SoC, NUS
Algorithm: Finding sum of A & B
Step 1: Set the value of carry to 0
Step 2: Set the value of i to 1.
Step 3: Repeat steps 4 through 6 until the value of i is > m.
Step 4: Add ai and bi to the current value of carry, to get xi.
Step 5: If xi < 10 then
let ci=xi and reset carry to 0.
Else (* i.e. xi  10 *)
let ci=xi - 10 and reset carry to 1.
Step 6: Increase the value of i by 1.
Step 7: Set cm+1 to the value of carry.
Step 8: Print the final answer cm+1, cm, …., c1
Step 9: Stop.
(UIT2201: Algorithms) Page 14
LeongHW, SoC, NUS

Chapter Outline:
1. Chapter Goals
2. What are Algorithms
3. Expressing Algorithms – Pseudo-Code
1.
2.
3.
4.
5.
Communicating Alg to computer
Pseudo-Code
Primitive Operations and examples
Variables and Arrays
Algorithm C=A+B in pseudo-code
4. Simple Algorithms
5. Recursive Algorithms
6. Time Complexity of Algorithms
(UIT2201: Algorithms) Page 15
LeongHW, SoC, NUS
3. Expressing Algorithms to Computer
 To
communicate algorithm to computer
 Need way to “represent” the algorithm
 Cannot use English
 Can
use computer language
 machine language and
 programming languages (Java, Pascal, C)
 But, these are too tedious (&technical)
 Use
Pseudo-Code instead…
(UIT2201: Algorithms) Page 16
LeongHW, SoC, NUS
Pseudo-Code to express Algorithms
 Pseudo-Code
 Mixture of computer language and English
Somewhere in between
precise enough to describe what is meant without
being too tediuos
 Examples:
 Let c be 0;
 Sort the list of numbers in increasing order;
 Need
to know both
 syntax – representation
 semantics – meaning
(UIT2201: Algorithms) Page 17
LeongHW, SoC, NUS
Primitive Operations
 To
describe an algorithm, we need some
well-defined programming primitives
 Assignment primitive:
 assignment statement, input/output statements
 Conditional primitive:
 if statement
 case statement
 Looping (iterative) primitive:
 for loop,
 while loop,
 Statements
are executed one-by-one
(UIT2201: Algorithms) Page 18
LeongHW, SoC, NUS
Conditional Primitives…
 if
statement
 to take different actions based on condition
 Syntax
if (condition)
then (Step A)
else (Step B)
endif
true
Step A
condition?
false
Step B
if (condition)
then (Step A)
endif
 Semantics
(UIT2201: Algorithms) Page 19
LeongHW, SoC, NUS
Examples -- (if statement)…
Let mark be the total-mark obtained
if (mark < 40)
then (print “Student fail”)
else (print “Student pass”)
endif
…
read in mark (*from the terminal*)
if (mark < 40) then (Grade  “F”)
else if (mark < 50) then (Grade 
else if (mark < 60) then (Grade 
else if (mark < 70) then (Grade 
else if (mark < 80) then (Grade 
endif
print “Student grade is”, Grade
“D”)
“C”)
“B”)
“A”);
…
(UIT2201: Algorithms) Page 20
LeongHW, SoC, NUS
Looping Primitive – while-loop

the while-loop
 loop a “variable”
number of times

Syntax
while (condition) do
(some sequence
of statements)
condition?
false
true
Some sequence
of statements;
endwhile

Semantics…
(UIT2201: Algorithms) Page 21
LeongHW, SoC, NUS
Looping Primitive – for-loop

First, the for-loop
 loop a “fixed” or (predetermined) number of
times

Syntax
for j  a to b do
(some sequence
of statements)
j  a;
(j <= b)?
false
true
Some sequence
of statements;
endfor

Semantics…
j  j+1;
(UIT2201: Algorithms) Page 22
LeongHW, SoC, NUS
“Exercising the alg”: for and while
for j  1 to 4 do
print 2*j;
endfor
print “--- Done ---”
Output:
2
4
6
8
--- Done ---
j  1;
while (j <= 4) do
print 2*j;
j  j + 1;
endwhile
print “--- Done ---”
Output:
2
4
6
8
--- Done --(UIT2201: Algorithms) Page 23
LeongHW, SoC, NUS
Variables and Arrays…
 In
the computer, each variable is assigned
a storage “box”
 can store one number at any time
 eg: sum, j, carry
 Arrays:
 Often deal with many numbers
 Such as A1, A2, A3, … , A100
 Store as an “array” A[1], A[2], … , A[100]
we treat each of them as a variable,
each is assigned a storage “box”
(UIT2201: Algorithms) Page 24
LeongHW, SoC, NUS
Algorithm: A = B + C (in pseudo-code)
We can re-write the C=A+B algorithm as follows:
Alg. to Compute C = A + B:
(*sum two big numbers*)
carry  0;
for i  1 to m do
x[i]  a[i] + b[i] + carry ;
if (x[i] < 10)
then ( c[i]  x[i]; carry  0; )
else ( c[i]  x[i] – 10; carry  1; )
endfor;
c[m+1]  carry;
Print c[m+1], c[m], …., c[1]
(UIT2201: Algorithms) Page 25
LeongHW, SoC, NUS

Chapter Outline:
1.
2.
3.
4.
Chapter Goals
What are Algorithms
Expressing Algorithms – Pseudo-Code
Simple Algorithms
1. Simple iterative algorithms
Computing Sum, Find Max/Min
2. Modular Program Design
3. Divisibility and Prime Numbers
5. Recursive Algorithms
6. Time Complexity of Algorithms
(UIT2201: Algorithms) Page 26
LeongHW, SoC, NUS
Simple iterative algorithm: Sum

Given: List of numbers: A1, A2, A3, …., An

Output: To compute the sum of the numbers
Note: Store numbers in array A[1], A[2], … , A[n]
Sum(A, n);
begin
Sum_sf  0;
k  1;
while (k <= n) do
Sum_sf  Sum_sf + A[k];
k  k + 1;
endwhile
Sum  Sum_sf;
Print “Sum is”, Sum
end;
(UIT2201: Algorithms) Page 27
LeongHW, SoC, NUS
Exercising Algorithm Sum:
Input:
A[1] A[2] A[3] A[4] A[5] A[6]
2
5
10
3
12
24
Processing:
Output:
k
?
1
2
3
4
5
6
6
Sum-sf
0
2
7
17
20
32
56
56
n=6
Sum
?
?
?
?
?
?
?
56
Sum is 56
(UIT2201: Algorithms) Page 28
LeongHW, SoC, NUS
Algorithm for Sum (with for-loop)

We can also use a while-loop instead of a for loop.
Sum(A, n);
(* Find the sum of A1, A2,…, An. *)
begin
Sum_sf  0;
for k  1 to n do
Sum_sf  Sum_sf + A[k];
endfor
Sum  Sum_sf;
Print “Sum is”, Sum
end;

HW: (a) Note the differences…
(b) Modify it to compute the average?
(UIT2201: Algorithms) Page 29
LeongHW, SoC, NUS
Remarks about the iterative algorithm…

Note the three stages:
1. Initialization
 Set some values at the beginning
2. Iteration
 This is the KEY STEP
 Where most of work is done
3. Post-Processing or Cleanup

Can use this setup for other problems
 Calculating average, sum-of-squares
 Finding max, min; Searching for a number,
(UIT2201: Algorithms) Page 30
LeongHW, SoC, NUS
Modular Program Design

Software are complex
 HUGE (millions of lines of code) eg: Linux, Outlook
 COMPLEX; eg: Flight simulator

Idea: Divide-and-Conquer Method
 Complex tasks can be divided and each part solved
separately and combined later.

Modular Program Design
 Divide big programs into smaller modules
 The smaller parts are
called modules, subroutines, or procedures
Design, implement, and test separately
 Modularity, Abstraction, Division of Labour
 Simplifies process of writing alg/programs
(UIT2201: Algorithms) Page 31
LeongHW, SoC, NUS
Simple Algorithms: Prime Numbers

Algorithm to determine if n is prime
Given: A positive integer n
Question: Is n a prime number?

What do we know?
“A number n is prime iff
n has no positive factors except 1 and n”

Idea: Express it “algorithmically”
“n is not divisible by any positive number k
such that 1 < k < n.” or k=2,3,4,…,(n-1)

What we already have:
 A module Divisible(m,n) to check divisibility
 We can use it as a primitive
(UIT2201: Algorithms) Page 32
LeongHW, SoC, NUS
Pseudo-Code for Prime:
Prime(n)
(* To determine if n is prime *)
begin
for k  2 to (n-1) do
if Divisible(k,n)
then (Print “False” & exit)
else (* Do nothing *)
endfor
Print “True” & Stop
end;

Note: Prime uses the module Divisible(k,n)

Exercise it with:
 Prime (5); Prime (4);
 Prime (55); Prime (41);
(UIT2201: Algorithms) Page 33
LeongHW, SoC, NUS
A Simple Module: Divisibility
A
module (procedure) for divisibility
Given: Two positive integers m and n
Question: Is n divisible by m?
or Algorithm to compute Divisible(m,n)
{
True, if n is divisible by m
Divisible (m, n) 
False, if n is not divisible by m
 Algorithm
Idea:
“A positive integer n is divisible by m iff
for some positive integer k  n, m*k = n.”
(UIT2201: Algorithms) Page 34
LeongHW, SoC, NUS
Module for Divisibility:

Algorithm (in pseudo-code)

Exercise it with:
 Divisible (3, 9);
Divisible (3, 5);
Divisible (3,101);
Divisible(m,n)
(* To compute if n is divisible by m *)
begin
D  false; (* assume false, first *)
for k  1 to n do
if (m*k = n) then (Dtrue; exit-loop)
else (* Do nothing *)
endfor
Divisible  D; (* true or false *)
end;
(UIT2201: Algorithms) Page 35
LeongHW, SoC, NUS

Chapter Outline:
1.
2.
3.
4.
5.
6.
Chapter Goals
What are Algorithms
Expressing Algorithms – Pseudo-Code
Simple Algorithms
Recursive Algorithms
Time Complexity of Algorithms
1. Sequential search algorithm
2. Binary search algorithm
3. Analysis of Time Complexity
7. Summary…
(UIT2201: Algorithms) Page 36
LeongHW, SoC, NUS
Search: sequential search algorithm
List of numbers: A1, A2, A3, …., An
and a query number x;

Given:

Question: Search for x in the list;
Sequential-Search(A, n, x);
(* Search for x in A1, A2,…, An. *)
begin
for k  1 to n do
if (x = A[k])
then (Print “Yes”; Stop)
else (* do nothing *)
endfor
Print “No”; Stop
end;
(UIT2201: Algorithms) Page 37
LeongHW, SoC, NUS
Remarks on Sequential Search Alg

Analogy: House-to-house search…

How fast is it to search for x?
 How many comparisons do we need?
 Example: 13, 38, 19, 74, 76, 14, 12, 38, 22, 55
When x=14, need 6 comparisons
When x=13, need only 1 comparison  BEST CASE
When x=55, need 10 comparisons  WORST CASE
When x=5, need 10 comparisons  WORST CASE

In general, given n numbers, A1,…,An
 Best Case: 1 comparison
 Worst Case: n comparisons
 Average Case: (n+1)/2 comparisons
(UIT2201: Algorithms) Page 38
LeongHW, SoC, NUS
Binary Search
 If
the List is sorted, that is
A1 A2  A3  ….  An
 Then,
we can do better,
 actually a lot better….
(UIT2201: Algorithms) Page 39
LeongHW, SoC, NUS
Binary Search
1, 4, 9, 11, 14, 43, 78
(UIT2201: Algorithms) Page 40
LeongHW, SoC, NUS
Binary Search (How fast is it?)
 Imagine







n=100
After 1 step, size is  50
After 2 steps, size is  25
After 3 steps, size is  12
After 4 steps, size is  6
After 5 steps, size is  3
After 6 steps, size is  1
DONE!!
 What
if n=1000? 1,000,000?
(UIT2201: Algorithms) Page 41
LeongHW, SoC, NUS
Binary Search Algorithm
Sorted List A1 A2  A3  ….  An
A number x.
Question: Is x in the list?
Binary-Search(A,n,x);
1. First  1
Last  n
2. While ( First  Last ) do
mid   (first+last) / 2 
If ( x = A[mid] )
then (output Yes and Stop)
else If ( x < A[mid] )
then Last  mid-1
else If ( x > A[mid] ) then First  mid+1
EndWhile
3. Output False and Stop
4. End
Input:
(UIT2201: Algorithms) Page 42
LeongHW, SoC, NUS
Time Complexity Analysis
 Sequential
Search (Alg):
 Worst Case:
n comparisons
 Best Case: 1 comparison
 Avg Case: n/2 comparisons
 Binary
Search (Alg):
 Worst Case: log2 n comparisons
 Best Case: 1 comparison
 Avg Case: about log2 n comparisons
 How
to get the Average Case?
 using mathematical analysis…
(UIT2201: Algorithms) Page 43
LeongHW, SoC, NUS
Complexity of Algorithm…

Logarithmic Time Algorithm
 Binary Search

A Linear Time Algorithm
 Algorithm Sum(A,n) -- O(n) time
 Algorithm Sequential-Search(A,n,x) – O(n) time

A Quadratic Time Algorithm
 Simple Median-Find (T2-Q3)

An Exponential Time Algorithm
 All-Subsets(A,n)
(UIT2201: Algorithms) Page 44
LeongHW, SoC, NUS

Chapter Outline:
1.
2.
3.
4.
5.
Chapter Goals
What are Algorithms
Expressing Algorithms – Pseudo-Code
Simple Algorithms
Recursive Algorithms
1. Recursion – the idea
2. Fibonacci sequence
3. Tower of Hanoi
6. Time Complexity of Algorithms
(UIT2201: Algorithms) Page 45
LeongHW, SoC, NUS
5. Recursion

A problem solving method of
“decomposing bigger problems into
smaller sub-problems that are identical to itself.”

General Idea:
 Solve simplest (smallest) cases DIRECTLY
usually these are very easy to solve
 Solve bigger problems using smaller sub-problems
that are identical to itself (but smaller and simpler)

Abstraction:
 To solve a given problem, we first assume that we
ALREADY know how to solve it for smaller instances!!

Dictionary definition:
recursion
see recursion
(UIT2201: Algorithms) Page 46
LeongHW, SoC, NUS
Example: Fibonacci Numbers…

Definition of Fibonacci numbers
1. F1 = 1,
2. F2 = 1,
3. for n>2, Fn = Fn-1 + Fn-2

Problem: Compute Fn for any n.

The above is a recursive definition.
 Fn is computed in-terms of itself
 actually, smaller copies of itself – Fn-1 and Fn-2

Actually, Not difficult:
F3 = 1 + 1 = 2
F4 = 2 + 1 = 3
F5 = 3 + 2 = 5
F6 = 5 + 3 = 8
F7 = 8 + 5 = 13
F8 = 13 + 8 = 21
F9 = 21 + 13 = 34
F10 = 34 + 21 = 55
F11 = 55 + 34 = 89
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …
(UIT2201: Algorithms) Page 47
LeongHW, SoC, NUS
Fibonacci Numbers: Recursive alg
Fibonacci(n) (* Recursive, SLOW *)
begin
if (n=1) or (n=2)
then Fibonacci(n)  1 (*simple case*)
else Fibonacci(n)  Fibonacci(n-1) +
Fibonacci(n-2)
endif
end;
 The
 It
above is a recursive algorithm
is simple to understand and elegant!
 But,
very SLOW
(UIT2201: Algorithms) Page 48
LeongHW, SoC, NUS
Recursive Fibonacci Alg -- Remarks
 How
slow is it?
 Eg: To compute F(6)…
F(6)
F(5)
F(4)
F(4)
F(3)
F(2)

F(3)
F(2)
F(2)
F(3)
F(1)
F(2)
F(2)
F(1)
F(1)
HW: Can we compute it faster?
(UIT2201: Algorithms) Page 49
LeongHW, SoC, NUS
Example: Tower of Hanoi
A
B
C
A
B
Given: Three Pegs A, B and C
Peg A initially has n disks, different size, stacked up,
larger disks are below smaller disks
Problem: to move the n disks to Peg C, subject to
1. Can move only one disk at a time
2. Smaller disk should be above larger disk
3. Can use other peg as intermediate
(UIT2201: Algorithms) Page 50
LeongHW, SoC, NUS
C
Tower of Hanoi

How to Solve: Strategy…
 Generalize first: Consider n disks for all n  1
 Our example is only the case when n=4

Look at small instances…
 How about n=1
 Of course, just “Move disk 1 from A to C”
 How about n=2?
1. “Move disk 1 from A to B”
2. “Move disk 2 from A to C”
3. “Move disk 1 from B to C”
(UIT2201: Algorithms) Page 51
LeongHW, SoC, NUS
Tower of Hanoi (Solution!)

General Method:
 First, move first (n-1) disks from A to B
 Now, can move largest disk from A to C
 Then, move first (n-1) disks from B to C

Try this method for n=3
1. “Move disk 1 from A to C”
2. “Move disk 2 from A to B”
3. “Move disk 1 from C to B”
4. “Move disk 3 from A to C”
5. “Move disk 1 from B to A”
6. “Move disk 1 from B to C”
7. “Move disk 1 from A to C”
(UIT2201: Algorithms) Page 52
LeongHW, SoC, NUS
Algorithm for Towel of Hanoi (recursive)

Recursive Algorithm
 when (n=1), we have simple case
 Else (decompose problem and make recursive-calls)
Hanoi(n, A, B, C);
(* Move n disks from A to C via B *)
begin
if (n=1) then “Move top disk from A to C”
else (* when n>1 *)
Hanoi (n-1, A, C, B);
“Move top disk from A to C”
Hanoi (n-1, B, C, A);
endif
end;
(UIT2201: Algorithms) Page 53
LeongHW, SoC, NUS
Characteristics of Algorithm

Correctness

Complexity --- time, space (memory), etc

Ease of understanding

Ease of coding

Ease of maintainence
(UIT2201: Algorithms) Page 54
LeongHW, SoC, NUS
 If
you are new to algorithms
 read the textbook
 try out the algorithms
 do the exercises
… The End …
(UIT2201: Algorithms) Page 55
LeongHW, SoC, NUS