COEN 179 Lecture Notes - Lecture 25: Selection Sort, Search Algorithm
6 Jun 2020
School
Department
Course
Professor
Document Summary
Coen 179 lecture 24 p, np, np-hardness, np-completeness notes. Selection sort takes about 6 months to sort 10^8 names on a typical laptop. Maybe not for large degree, but it is advantageous to consider all polynomials as fast running time for theoretical purposes. Def: the class p consists of problems whose solutions can be found with an algorithm whose running time is bounded above some polynomial n^k. Max in p since there is an o(n) algorithm to find largest value of n items. Sorting in p because there is an o(n^2) algorithm to sort n items. Primality in p because there is an o(n^6) algorithm to determine whether an integer is prime or not. Some important problems for which no known poly time algorithm has been found. e. g. partition. Output: true if we can partition s[1n] into 2 arrays a[1k] Instance: s = [10, 8, 36, 4, 4, 4, 4, 2, 5, 5, 1, 1, 1, 7]
