Topic 1: Introduction, Basic Concepts
CMPUT204: Introduction to Algorithms
Course Information (given in a separate document)
Algorithms Concepts
Copyright By PowCoder代写 加微信 powcoder
Recursion and Induction
Pseudo-code, RAM model
Getting Started: InsertionSort
Readings: CLRS Chapters 1, 2 (p5-29) (Loop invariant to be discussed
next week)
CLRS does not discuss how to prove correctness of recursive algorithms. Seminars will present some examples.
The Study of Algorithms
This course separates “programmers” from “algorithm designer”:
A programmer knows how to write code
An algorithm designer knows how to reason about code
Argue about correctness and resources mathematically Has wide-range of “tools” for a wide-variety of problems
Leaving this course you should have learned:
Algorithms: sorting, graphs, math-operations, problem solving,
Design Paradigms: greedy, divide-and-conquer, dynamic
programming
Analysis: correctness, worst/average/best case, asymptotic
Week 1: Introduction
What’s an Algorithm?
Problem: Given an input X satisfying …, output Y satisfying …
Instance: A specific input for a problem is an instance
Algorithm: A well-defined step-by-step procedure for X → Y
Examples (that you already know!):
Given a natural number X, output Y which is X!
Given a sequence of numbers (a1, …, an), output a sorted list.
What do we need to argue about an algorithm? Correctness
Amount of resources: time and space Can we do any better?
For any instance? For some particular type of good instances?
Week 1: Introduction
Correctness for Recursive Codes
The factorial function: n! = ni=1 i
Recursive implementation:
procedure factorial(n) if (n = 0) then
return 1 else
Week 1: Introduction
(with 0! = 1)
return n × factorial(n − 1)
How do we prove the correctness of recursive code?
We need a proof that starts at a base case (0 in this case), and progresses from there until it covers all integers …
I.e., we prove correctness of recursions using induction!
∗∗ Base case
∗∗ Recursive call
Claim: For every natural number n, factorial(n) = n!. Proof: By induction.
(Base case) We show the claim holds for some initial value. Forn=0wehavethat0!=1andfactorial(0)=1.
(Induction step) Fix some k. Assuming the claim holds for k, we show the claim also holds for k + 1.
Assuming factorial(k) = k!, we have that
factorial(k + 1) = (k + 1) × factorial(k) ∗ ∗ since k + 1 > 0
= (k + 1) × k! k
= (k + 1) × i i=1
= i=(k+1)!
∗ ∗by induction hypothesis
Week 1: Introduction
Induction proof structure
Base case: We show the claim holds for some initial value.
(Not necessarily 0)
Induction step: Fix some natural number k. Assuming the claim
holds for k, we show that the claim also holds for k + 1.
Alternative: (Full/Complete/Strong induction)
Induction step: Fix some natural number k. Assuming the claim holds for all natural numbers 0 ≤ i ≤ k we show it also holds for k + 1.
Induction is a powerful and a commonly used tool.
Must-haves in induction proofs:
A clearly defined base case
A well-defined assumption for any instance of a fixed size A correct induction step — that indeed works for any k.
Without these (and they are sometimes subtle) inductions can go horribly wrong.
Week 1: Introduction
Motivation: Fibonacci (Efficiency Issues)
Consider the sequence of Fibonacci numbers defined recursively: 0 if n = 0
F(n) = 1 if n = 1 F(n−1)+F(n−2) if n≥2
0 1 2 3 4 5 6 7 8 9 10 …
0 1 1 2 3 5 8 13 21 34 55 … Problem: Given n, output F(n).
Week 1: Introduction
Direct and easy recursive implementation:
procedure fib1(n) if n<2 then
return n else
return fib1(n−1) + fib1(n−2) Trace of recursive calls:
fib1(4) /\ fib1(3) fib1(2) /\/\
fib1(2) fib1(1) fib1(1) fib1(0) /\
fib1(1) fib1(0)
Week 1: Introduction
Some back-of-the-envelop calculations:
Let T1(n) denote the number of recursive calls in fib1(n).
fib1(n − 1) — invoked 1 time
fib1(n − 2) — invoked 2 times
fib1(n − 3) — invoked 3 times
fib1(n − 4) — invoked 5 times
fib1(n − 5) — invoked 8 times
Claim: For all natural numbers n ≥ 2, fib1(n − i) is invoked F (i + 1) times for any 1 ≤ i ≤ n − 1.
Proof: induction!
It follows T1(n) ≥ ni=2 F(i) which is exponential in n (it is known 1+√5 n
that T1(n) is about 2 , see pages 59-60 of Text).
Week 1: Introduction
Non-recursive implementation: procedure fib2(n)
for j=3 to n+1 do
F[j] = F[j − 1] + F[j − 2]
return F[n+1]
Yet another non-recursive implementation: procedure fib3(n)
return 0 x=0
for j = 2 to n do
newy = x + y x=y
Week 1: Introduction
Some calculations about the cost
Let T2(n) and T3(n) denote the number of times we invoke the loop in fib2 and fib3 respectively
T2(n) = T3(n) = n − 1, for all n ≥ 1
Thus, T1(n) - exponential, T2(n),T3(n) - linear
What about space, measured by the number of “integers stored in memory”
fib2 - linear; all Fibonacci numbers are stored in an array fib3 - small constant, x and y, newy, and a loop counter
Conclusion: fib3 is the best.
Week 1: Introduction
Methodologies for Analyzing Algorithms
How do we measure an algorithm’s running time (RT)?
RT depends on hardware, software, implementation language,
How about measuring RT in terms of input size?
We cannot run against all possible inputs
Even inputs of the same size may have different RTs.
We need an analytic way of measuring RT independent of environment factors (CPU speed, compiler, implementation, ...).
Idea/Solution:
Abstract away — select theoretical computer model
Try to identify “key operations”: If each operation costs me $1
dollar — how much will I end up paying
Week 1: Introduction
Model of computation: RAM
RAM: random access machine Components
Input device
Output device
CPU: computation unit (inc. program)
M: memory locations (each can store an integer)
M[0], M[1], M[2], . . .
Program: fixed user-defined instruction sequence
Properties
CPU has access to any mem location directly (by index)
move data between memory
compare data and branch
binary arithmetic operation
read from Input to memory
write from memory to Output
variables are local (unless stated otherwise) parameters passed by value
primitive operations:
assign a value to a variable
calling a method/function/procedure an arithmetic operation
comparing two basic variables
returning a value from a method
Week 1: Introduction
Model of computation: RAM (Cont’d)
We will do our best to abstract away from all of those! Given an algorithm, we can measure:
Time — number of primitive (basic) instructions executed Space — number of memory locations used
In this course we will often look at Time, seldom Space.
Week 1: Introduction
Model of describing an algorithm
Describing algorithms: pseudocode Pseudocode example
input: integers a, b output: a × b
for j = 1 to b do
sum = sum + a return sum
Pseudocode conventions
indentation indicates block structure
while/for/repeat/if/then/else
Procedure/Function: name(pam1,pam2,...) ** or ◃ comment
array indexing: A[i] for ith cell of array A.
Week 1: Introduction
An example: Insertion Sort
Input: n elements (a1, a2, . . . , an) where each pair is comparable (e.g., numbers, cards, chess players, GDPs)
Output: an ordered permutation (a′1, a′2, . . . , a′n) such that a′1 ≤a′2 ≤...≤a′n
Our first solution: Insertion sort
Idea: repeatedly insert A[j] into sorted sublist A[1..j − 1]
How to insert? One by one, move elements in sorted sublist A[1..j − 1] which are bigger than key(= A[j]) to the right
Week 1: Introduction
An example: Insertion Sort
Pseudocode
InsertionSort(A) **sort A[1..n]
for j = 2 to n do
key = A[j] **insert A[j] into sorted sublist A[1..j − 1] i=j−1
while (i>0 and A[i]>key) do
A[i + 1] = A[i]
i=i−1 A[i + 1] = key
Week 1: Introduction
An example: Insertion Sort Trace
Input: : (53,21,47,62,14,38)
Week 1: Introduction
53 21 53 53 21 53 21 53 21 53 21 47 21 47 21 47 21 47 21 47 21 47 21 47 21 21 14 21 14 21 14 21 14 21 14 21 14 21
47 62 47 62 47 62 47 62 53 62 53 62 53 62 53 62 53 62 53 62 53 53 47 53 47 53 47 53 47 53 47 53 47 53 47 47 38 47
14 38 ** j←2, key=21
14 38 ** end of this iteration 14 38 ** j←3, key=47
14 38 ** j←4, key=62
14 38 ** j←5, key=14
62 38 ** j←6, key=38
53 62 ** output permutation
Analysis of running time
Model of computation: RAM
Problem: run time varies with input
Kinds of analysis
Worst case
T (n) — maximum time over all inputs of size n
Average case
Must specify input distribution over which average computed Most common: assume uniform distribution (all inputs of size
n equally likely) Best case
The least running time for any instance; useful only for lower bound.
Week 1: Introduction
Analysis of Insertion Sort
InsertionSort(A)
for j = 2 to n do key = A[j]
n − 1 i=j−1 n−1
while (i > 0 and A[i] > key) do A[i + 1] = A[i]
nj=2 tj nj=2(tj − 1) nj=2(tj −1) n−1
A[i+1] = key
tj — number of times the while loop test is executed for j.
T (n) = n+2(n−1)+3 tj − 2(n − 1)+n−1 = 2n−1+3 tj
Week 1: Introduction
Running time
Best case: list is already sorted (for any 2 ≤ j ≤ n we have tj = 1)
T (n) = 2n − 1 + 3(n − 1) = 5n − 4
Worst case: list is reverse sorted (for any 2 ≤ j ≤ n we have
T(n)=2n−1+3 2 −1 =1.5n +3.5n−4
Average case: Suppoe we randomly choose n numbers and apply insertionSort. On average, half of the elements in A[1..j] are less than A[j] and half are greater. So tj is about j/2 and we end up with a quatratic function, as bad as the worst case.
n(n+1) 2
Week 1: Introduction
Correctness of insertion sort
Theorem: InsertionSort(A) returns A in a sorted order.
To prove the theorem we will prove the following claim.
Claim: Forany2≤j≤n+1,atthestartofj-iterationofthe for-loop, the subarray A[1..j − 1] consists of the elements originally in A[1..j − 1], and in sorted order.
This Claim is an example of a Loop Invariant, which we will study next.
Week 1: Insertion Sort
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com