CSE 240 Logic and Discrete Math - bsiever/WUSTL-CSE-Curriculum GitHub Wiki

Outcomes of the subcommittee meeting

Proposed Learning Outcomes

  • Determine the truth of statements using predicate logic and accurately apply formal definitions (esp. vacuous truth cases)
  • Write literate proofs using straightforward application of standard outlines (direct, contrapositive, contradiction, upper/lower bounds).
  • Write inductive proofs, including structural induction (trees, lists,)
  • State and apply basic definitions, facts, and notation for commonly used discrete math constructs
  • Derive big-O running time for simple pseudocode examples, especially recursive examples. Includes finding closed-forms for recursively-defined formulas using unrolling and recursion trees 

  • Classify the complexity of simple algorithms in terms of polynomial versus exponential

Topics Covered in CSE 240

  • logic and proofs
  • number theory
  • sets and collections of sets
  • relations
  • functions
  • graphs
  • Induction and recursive definition
  • big-O, algorithms,
  • state diagrams
  • countability
  • finite state machines, NFAs, DFAs, Turing Machines
  • conditional probabilities and Bayes theorem

Comments on CSE 240

  • The subcommittee felt the content covered is appropriate when compared to our peer institutions. Some questions were raised about incorporating additional active learning exercises (improving upon what currently exists). Also, focusing the proofs discussion on CS-specific topics such as teaching induction using pseudocode with trees or loops as an additional example.
  • The subcommittee also felt that CSE 240 should be a prereq for CSE 247. This will ensure students entering CSE 247 have been exposed to the basics of structuring a proof.

Math Requirements for CSE 347 (Kunal)

The math requirements for 347 are not really covered well in the above listed content. In particular, we generally need students to be comfortable with discrete probability, combinatorics, how to write proofs and some number theory.

Discrete probability topics used: Indicator random variables, linearity of expectation, union bound, markov's inequality, Chebyshev and Chernoff bounds. Combinatorics: Relatively simple counting arguments and upper and lower bounds on binomials. How to write proofs: This is the most important aspect of 347 and the one the students are least prepared in. Mostly they need to know structural induction, contradiction, how to set up arguments, some reductions from one problem to another. Number theory: Relatively simple modular algebra, some idea on how to manipulate mods and also how to do simple number theory proofs. Some of this stuff is meant to be covered by 240, but the students are not really prepared for it when they come to 347. In particular, they find it hard to set up random variables and manipulate probabilities and expectations. Writing and understanding proofs is the biggest challenge.

For each school please fill in the following for their CSE 240 equivalent

  • Content Covered
  • Pedagogy / Delivery
  • Learning Outcomes

Here is a link to my CSE 240 page which lists the topics we discuss.

Assigned: Todd

  • UIUC CS173 Course Profile and Spring 2019 Calendar

    • Content Covered

      • logic and proofs
      • number theory
      • sets and collections of sets
      • relations
      • functions
      • graphs
      • Induction and recursive definition
      • trees
      • big-O, algorithms, NP
      • state diagrams
      • countability

    • Delivery

      • Lecture twice a week (75 minutes) and a discussion session once a week (50 minutes)

    • Learning Outcomes/Goals

      • Predicate logic: determine the truth of statements,
      • perform simple transformations (esp. negation)
      • accurately apply formal definitions (esp. vacuous truth cases, attention to variable types and scope)
      • Write literate proofs using straightforward application of standard outlines (direct, contrapositive, contradiction, upper/lower bounds)
      • Write inductive proofs, including proofs on trees
      • State and apply basic definitions, facts, and notation for commonly used discrete math constructs
      • Derive big-O running time for simple pseudocode examples,recursive examples. Includes finding closed-forms for recursively-defined formulas using unrolling and recursion trees
      • Classify examples the complexity of very simple examples in terms of countable versus uncountable, polynomial versus exponential, decidable versus undecidable

  • Vanderbilt

    • Content Covered
      • An introduction to sets, relations, functions
      • Basic counting techniques
      • Permutations, combinations
      • Graphs
      • Recurrence relations
      • Simple analysis of algorithms, O-notation
      • Boolean algebra, propositional calculus, and numeric representation
    • Delivery
      • Lecture 3 times a week (50 minutes)
    • Learning Outcomes/Goals
      • None specified

  • MIT 6.042

    • Content Covered
      • Fundamental concepts of mathematics: definitions, proofs, sets, functions
      • Discrete structures: elementary number theory, graphs, counting
      • Discrete probability theory
    • Delivery
      • Lecture 3 times a week (50 minutes) students work in teams in a flipped classroom
    • Learning Outcomes and Goals

Assigned: Steve

  • Harvey Mudd: Math 55 Discrete Math Spring 2018 course page

    • Content covered
      • combinatorics (sets, relations, lists, multisets, Pigeonhole, binomial coefficients, induction, Cantor's Thm)
      • number theory (Euclid's GCD, mod arithmetic, factoring, Fermat's Little Thm, RSA)
      • graph theory (graphs, coloring, planar graphs, trees, partial orderings, projects on posets)
    • Pedagogy/delivery
      • unclear, but 3.0 unit course, seems to have a class project
    • Learning outcomes
      • not explicitly stated, but "emphasis on proofs and creative problem-solving"

  • Cal Tech: Ma/CS 6a Discrete Math Fall 2016-17 course page

    • Content covered
      • Crypto (congruences, primality testing, generating fcns, RSA)
      • Combinatorics (counting, permutations/combinations, groups, isomorphisms, partitions)
      • Graph theory (BFS, Eulerian cycles, coloring, trees, matching, bipartiteness, flows)
    • Pedagogy/delivery
      • 3 1-hr lectures per week
    • Learning outcomes
      • None listed

  • Purdue: CS 182 Foundations of Computer Science Spring 2019 website

    • Content covered (from canonical syllabus)
      • Logic, proofs, Boolean logic
      • Sets, fcns, relations
      • Sequences & sums
      • Number representations (floating-pt, precision vs. accuracy)
      • Counting, permutations, combinations, basic probability
      • Algorithm fundamentals (running time)
      • Graphs and trees
      • Proof techniques (induction, construction, contradiction, diagonalization)
      • Crypto (number theory, RSA)
      • Languages, expressions, NFAs, DFAs, Turing machines, halting problem, P vs. NP
    • Pedagogy/delivery
      • 2 1.25-hr lectures, 1 (?) optional problem-solving session per week
    • Learning outcomes
      • None stated in syllabus

Assigned: Marion

CMU: 15-151: Mathematical Foundations for Computer Science

This course is very similar but covers less than CSE240. No graphs, finite automata, regular expressions, Turing machines and NP-Completeness.

Content Covered

  • Proofs
  • Induction
  • Functions and Sets
  • Combinatorics
  • Probability

Pedagogy / Delivery

Lectures, assignments, 3 midterms, 1 final exam

Learning Outcomes

  • Students learn to formalize arguments using mathematical proofs.
  • Ability to reason logically and clearly. Ability to prove using elementary logic.

Stanford: CS103 Mathematical Foundations of Computing

Interesting: This course does not cover probability, but goes into other concepts such as finite automata, regular expressions, Turing machines and NP-Completeness.

Content Covered

  • proof techniques, logic, and induction
  • sets, functions, and relations
  • introduction to formal languages
  • Finite Automata: DFA's, NFA's
  • Regular Expressions
  • Context-Free Grammars, Turing Machines, and NP-Completeness

Pedagogy / Delivery

  • Lectures, 9 assignments, 2 midterms, 1 final

Learning Outcomes

  • students get the mathematical foundations necessary for computer science