* Why does it matter: a brief look inside a search engine
V Basic Java for the experienced
* values
* variables
* conditionals
* indexed variables: arrays
* loops
* functions/methods
* quiz: are you ready?
V Java machine model
V Data representation
* Memory
V Data abstraction
* Data types
* Object = state + change
V Object-oriented programming
V OO modeling: Abstracting relevant aspects of the world
* State
* State functions
* State change
* Objectopia
V Objects and classes
* Java compromise: primitive types vs object types
* Fields (aka instance variables)
* Object types: classes
* Binding fields to object data
* Objects as data in memory
V References
* Aliasing
V Methods
V Parameters
* Formal vs actual parameters
* Method invocation as program rewriting
V Method invocation with activation records
* The memory layout of activation records
* Binding of formal parameters and local variables to activation data
V Methods as functions in context
* Context-dependent functions: dynamic methods
V Context-independent functions: static methods
V Example; math functions
* Are math functions truly context-independent?
* Java compromise: static
V Specification vs implementation
* Implementation hiding
* Public vs private
V Subtyping
* Interfaces
V Inheritance
* Abstract classes
* Concrete classes
V Overriding
* Protected
V Iterative programming
V Indexed collections: arrays
* Java compromise: arrays are not full citizens of Objectopia
* Computing over collections: iteration
* Nested indexing: multidimensional arrays
* Accumulation
V Searching and sorting (part 1)
* linear search
* binary search
* insertion sort
V Sequences
* as arrays
* as strings
V searching in sequences
* text processing
V Operating limits and failure
* Contracts
* Pre- and post-conditions
* Exceptions
V Programming is writing
* Requirements
* Specifications
* Documentation
V Programming with collections
V What do collections represent?
* membership
* iteration
V Collection types
* Lists
* Sets
* Maps
V Generic collections
V Java compromises
* type casts
* generic collections
V Data modeling: Entities, attributes, and relationships
* Entities as objects
* Attributes as fields
* Dynamic attributes as maps
* Functional relationships as object-valued fields
* Non-functional relationships as collection-valued fields
* Objectified relationships
* Graphs
* Relational inverses and doubly-linked data
V Search and collections
* Keeping track of where you have been
* Indexing of collections
V Reactive programming
V interaction
* message passing
* model-view-controller patterns
* graphical user interfaces
V communication
* input and output
V network I/O
* HTTP
* Web services
* introduction to concurrency
V Functional programming
* Immutable data
V Nested data
* Trees
* HTML and XML
* Structural recursion
V Generative recursion
V Divide-and-conquer
V Searching and sorting (part 2)
* Merge sort
V Algebra for collections
* set operations
V Algebra for sequences
* regular expressions
V Higher-order functional programming
V Function objects
* Java trick: Anonymous classes
* Tree traversals and the visitor pattern
* Searching in trees
V Dynamic programming languages: Python
* Runtime type checking
* Methods are just functions
* Objects are just dictionaries (maps)
V Collection types
* List comprehensions
* Where did these ideas come from? Introduction to research in computer science
V Tentative assignments
* simulation (object-oriented programming)
* sound processing (iterative programming)
* perceptron learning on images (iterative programming)
* image processing (iterative programming)
* regular expressions (functional and iterative programming)
* simple search engine (iterative and collections programming)
* dynamic Web pages (functional and reactive programming)
* simple chat server (putting it all together, Python)