CSE/Math 261 Discussion

A brief report of meeting today with Garth Isaak, Bennett Eisenberg,
Arthur Busch, Donal Hillman, Henry Baird, and Edwin Kay

Agreed:
   - most CSE261 students are CS majors
   - Rosen is a decent text, typical of other decent texts
   - Rosen (& others) cover too much for one semester
   - We should try to agree on a partition of the topics into
         A)  core topics that should be covered in depth (& drilled in)
         B)  topics that can be skimmed or skipped

Below we list the topics that should be covered in CSE/Math 261, along
with their relative importance.  We also indicate the role of these
topics in CSE courses.  The relevant CSE courses are
  CSE 109  Systems Programming  (Programming in C++)
  CSE 262  Programming Languages (Theory of design and implememntation
                                  of programming languages)
  CSE 303  Operating Systems  
  CSE 302  Compiler Design   (Theory and implementation of compilers)
  CSE 313  Graphics
  CSE 318  Automata and Formal Grammars  (Finite state automata,
                        Turing machines, regular expressions, context
			free grammars)
  CSE 327  Artificial Intelligence Applications
  CSE 340  Design and analysis of algorithms
  CSE 343  Network Security

A)  Core topics
   - Logic, Proof, Sets, Functions (Rosen Ch 1)
      (Proofs are pervasive in CSE 318, CSE 340.  They should know 
       how to construct inductive proofs, proofs by contradiction,
       etc.  Further, it is important for students to understand 
       formal definitions of sets, functions, etc.)
   - Algorithms, Integers, Matrices (Ch 2)
       note:  applications of no. theory (e.g. PK cryptography) can be skimmed
       note:   most students claim to have seen matrices earlier from Math 205
      (The central topic of CSE 340 is the study of algorithms.)
   - Mathematical Reasoning, Induction, & Recursion (Ch 3)
         note:  induction & recursion need to be drilled
      (CSE 109, CSE 262, CSE 303, CSE 318, CSE 302)
   - Counting (Pigeonhole, Perms, Combs, Binomial, Enumerability,  etc) (Ch 4)
      (Counting is important in CSE 318 and CSE 340.  The notion of
      countability is essential to some proofs in CSE 318.)
   - Relations (Ch 7)
      (For CSE 318, it is important that students understand relations
       as subsets of products of sets.)
   - Graphs (Ch 8)
        note:  shortest-paths & coloring can be skimmed or skipped
            (Graph algorithms are covered in CSE 340)
   - Trees (Ch 9)
         note:  MST can be skimmed or skipped (covered in CSE340)
    (Trees are an important data structure in CSE 109.  Search trees
    are an important topic in CSE 327. Tree algorithms constitute an
    important topic in CSE 340)

B) Topics that can be Skimmed or Skipped
   - Discrete Probability
        note:  covered in other required courses
        if skimmed, leave just enough for expected case analysis
   - Advanced Counting Techniques
        note:  recurrence relations & their solution should not be 
               skipped or skimmed
               D&C algs can be skipped (covered in CSE340)
   - Boolean Algebra
        note:  introduced & applied in other CS courses
   - Modeling & Computation
        note:  covered in other CSE courses