CS211 Fall 2000 - TENTATIVE TOPIC LIST - M. Morgenstern - WORKING DRAFT 

++ signifies Accel/Proj Stream

We likely will not cover all the items listed here, in either Stream.


* Overview & Concepts
  - Agenda/topics, you should know Java
    Recitations, attendance, homeworks, grading
    Newsgroup, Online Hw submission
    Objects, data, methods/operators/procedures

  - Classes:
    arrays
    constructors and instantiation
    static variables and methods
    reference variables, parameter passing, return values

  ++Proj: design environment, CodeWarrior in labs
    programs: arrays, I/O (CS211 I/O package?)
    book exercises


* Inheritance:
    extending classes
    polymorphism
    interfaces
    abstract classes
    the instanceof operator
    casting
    the class called Class
    basic Reflection

  ++Proj: program generation of combinations,
    program with subclassing and inheritance, instances
    fix given program with errors, add doc, then run,
    book exercises


* Access, I/O, Exceptions, Recursion, Induction:
  - access control modifiers
    packages, streams, serialization
    exceptions: throw and throws
    try, catch and finally

  - Recursion and induction
    tail recursion
    how it works: parameters, execution stack
    induction proofs

  ++Proj: Recursion programming,
    book exercises



* Program Design
  - top down, bottom up, middle out design
    UML
    pseudo-code
    program stubs

  - Javadoc and comments
    testing
    conditional compilation and inlining (newer compilers)
    debugging
    program/system lifecycle

  ++Proj: interface and module design,
    UML, pseudo-code
    - Modify previous recursion program given revised spec
    - book exercises


* Building GUIs:
  - JFC (Java Foundation Classes)
    AWT, Swing
    containers
    events and listeners
    inner classes
    command line args
    intro to applets

  ++Proj: Game of Life
    book exercises


* GUI and Algorithms
  - GUIs continued

  - Analyisis of algorthims and Big-O notation
    Abstract data types and operators
    arrays (review), sets, multi-sets, collections
    implicit vs explicit representation (eg priority queue 'tree')
    linked lists, cf LISP

  ++Proj: #2 Game of Life: GUI issues
    book exercises


* ADTs and Trees
  - stacks, and uses: expression evaluation, execution stack
    queues, use in simulation
    ADTs

  - binary and n-ary trees
    tree traversal
    expression representation trees
    decision trees
    game trees

  ++Proj: Code Interpretation: parse fully parenthesized expression
    and execute simple code (pairwise instructions) to compute
    result using stack as needed.   too much?


* Search Trees and Hashing
  - search trees: binary, balanced (AVL)
    B-Trees and indices

  - Hashing
    Hash fcn, overflow methods
    analysis
    extensible hashing

  ++Proj: #2 Modifying Code Interp project: generate log of
    intermediate operations and their results
    (extra: B-Tree and indices)


* Graphs
  - types of graphs,
    graph representation and applications
    graph traversal, breadth, depth, best,
    distance and Dijkstra's shortest path

  ++Proj: Introduce major project:
    (game, interpreter/compiler, database indexing, graph algs)
    book exercises


* More on Graphs, Search
  - Topological sort
    spanning tree and algorithm
    Search: linear, binary if sorted

  - Sorts: Selection, Merge
    Binary heap, priority queue, Heapsort

  ++Proj: topological sort (or heapsort)
    book exercises


* Sorting and Alg Analysis
  - Quicksort, details, analysis
  - Divide and conquer strategy

  - Algorithm analysis, asymptotic complexity
    analysis of Heapsort and MergeSort