Class Notes (838,006)
Canada (510,619)
CSC104H1 (67)
Lecture

Lecture 21, 22 - Algorithm Complexity

3 Pages
77 Views
Unlock Document

Department
Computer Science
Course
CSC104H1
Professor
Mark Lanctot
Semester
Fall

Description
Algorithm Complexity – Lecture 21/22 Recall linkedlist.c append operation. Because a pointer to end of list is kept as tail, statements -> time is O(1) Induction proofs Induction is used when you have a claim that some property holds for all n >= 0 or 1, where n is an integer. Call this claim P(n) Two steps: 1. Prove base case – claim holds for n = 0 or n = 1 2. Show that P(n) implies P(n+1). Assume that P(n) is true, and prove that P(n+1). a. Establishes an infinite implication… (-> means implies) b. P(n) -> P(1) -> P(2) -> P(3) Example 1: P(n) =∑ Step 1 - Base case: N = 1 ∑ Step 2 – Assume that P(n) is true. Show that P(n+1) is true ∑ = . Example 2: ∑ Step 1 – Base Case: N = 1∑ Step 2 – Assume that P(n) is true. Prove for P(n+1) ∑ ∑ Example 3 3 P(n) is n >= 2, then p – n is divisible by 3 Step 1 – Base Case P(2) and 6 is divisible by 3. Step 2 Assume that P(n) is true -> n – n = 3r. r is some integer. Prove P(n+1) P(n) is true because this is divisible by 3. Induction assumed here. Applications for Algorithms – Breadth First Search on a Grid Start End Two lists: C , null ) Line above is Tuple representing coordinates (row/column) App
More Less

Related notes for CSC104H1

Log In


OR

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Sign up

Join to view


OR

By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.


Submit