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