CSC 345 Lecture Notes - Lecture 1: Contraposition, Insertion Sort, Quicksort
16 Mar 2016
School
Department
Course
Professor
Document Summary
Definition of algorithm: method for solving problems suitable for computer implementation. Definition of data structure: most algorithms involve methods of organizing the data involved in the computation. Object created this way is called a data structure. As a software engineer: design algorithms that are easy to understand, code and maintain (debug, design algorithms that are efficient. P vs np: operations per second insertion sort quick sort, 1e6 o(infinite) days, 1e9 centuries minutes, 1e12 months near instantly. There should never be a favorite data structure because each situation has different requirements. Proof techniques: 1) proof by examples, there is one element in a set s that has property p, all elements in x in set s has property p, example 1) Proof: 2^4 1 = 15 = 3 * 5. Qed: 2) direct proof if p then q, assume p is true and try to show that q is true, example 2) If x is even, then 3x is even.
