CSC152 2005F, Class 1: About the Course Admin: * No office hours today (unless you really need them) * No homework for Monday Overview: * Subject matter(s) of the course * Some background questions * Administrative issues Subject Matter * Traditional subject matter of CS2: Algorithms and Data Structures * We did algorithms in 151, so why are we doing them again? * Algorithms provide instructions for solving problems * We need to work on your algorithm-writing skills * Different approaches * Patterns of algorithm writing * Divide and conquer * Greed * Dynamic programming * Famous algorithms * Searching * Sorting * And more (I hope) * Means of analyzing algorithms * Efficiency: * Speed of computing result * Of expression (amount of code used) * Resource use (memory) * Correctness * Proof! * Carefully thought out test suites * Data structure: Mechanism for organizing information * List and Vector * Both collect elements in a sequence * Vectors permit you to efficiently reference elements by position * Lists grow efficiently; vectors do not * Nowadays: Algorithms and Abstract Data Types * Start with *what operations we want to do on the data* * Typical approach: List functions wanted and then figure out one or more data structures that support those functions * PAMI for ADTs * Purpose (e.g. Lists group data so that they can be accessed in sequence) * Applications (Lists are good for ...) * Methods, the functions we want the ADT to provide (cons, car, cdr, empty? nil) * Implementation, how we get those functions implemented efficiently USING A DATA STRUCTURE * Subject 2 (3? 4?): Object-Oriented Programming * Not functional programming * Functional programming involves defining and combining functions * Also anonymous functions, higher-order functions, symbols as first-class data, etc. * Anonymous: (map (lambda (x) (* 2 x) (list 1 2 3))) * Higher-order: Create/return procedures as values ; Take procedures as params * Object-oriented programming involves defining and combining objects * Object: Collection of data and functions on those data * Encapsulation, Polymorphism, Inheritance * Subject 3 (or whatever): Java Programming * Good langauge for doing this stuff * Useful for upper level classes * Students seem to want to learn the language