CPSC 121 Lecture Notes - Lecture 36: Mathematical Induction, Circular Reasoning, Quicksort

• School: UBC
• Department: Computer Science
• Course: CPSC 121
• Professor: BELLEVILLE, PATRICE

Document Summary

Cpsc 121 lecture #36 induction and randomized quicksort. Topics included: induction examples, find the ith smallest item. Theorem: every positive integer n greater than 1 that is either a prime or can be written as a product of primes. Then once we conclude that the theorem works for 2 and 3, we can prove the theorem for n = 4. Then once we conclude that the theorem works for 2, 3, and 4, we can prove the theorem for n = 5 etc: we need base cases so that our recursion has a start. Problem: find the ith smallest element in an unsorted list. (aka randomized quick sort: approaches, 1) sort the list, the runtime would be nlog(n, 2) use a binary search tree, the runtime would be nlog(n). Binary search trees are useful if the list changes / is edited often: 3) an algorithm with n runtime, first pick a random element x in the list.