SOFTENG 211 - "software engineering theory"

This course is inappropriately named. To my knowledge, it's better that it's called something like "discrete mathematics". This course is the best course in this semester.

  • logic
    • propositional logic, first-order logic, predicate logic, quantifiers
    • the 16 binary boolean operators
  • set theory
    • equality
      • indiscernability of identicals / identity of indiscernables
    • "pairs"
    • "reification"
    • !! "element of" being the only predicate needed
    • Zermelo-Fraenkel Set Theory
      • standard definition of equality
      • axiom of extensionality
      • axiom of pairing
      • set comprehension
        • Russel's Antinomy -> axiom scheme of restricted comprehension
      • axiom of union
      • axiom of power set
      • axiom of infinity
      • axiom of choice
    • "functions" - are relations which is left-total and right-unique
    • Cartesian product
    • equivalence relation
      • equivalence classes
      • partition
    • partial order
      • "strict partial order"?
      • total order
    • transitive closure
      • directed acyclic graph
    • "uniqueness" & "totality" of functions
    • injectivity, surjectivity, bijectivity
  • mathmatical induction
    • pigeonhole principle
  • strings
    • string:= function: N --> alphabet
    • concatenation
    • partial evaluation of functions
    • semigroup, monoid
      • e.g. function compositio
  • computability
    • Gödel's Incompleteness Theorums (IT1 & IT2)
    • strings and "languages"
    • deterministic finite automata
      • pumping lemma
      • concatenation of languages
        • Mealy+ machines
    • Turing machines
      • universal Turing machines
        • how it runs over the same tape (like a caterpillar)
        • algorithm (really just manually simulating a TM)
      • halting problem, entscheidungsproblem, busy beavers
        • time complexity of UTM (uncomputably steep)
    • "primitive recursive functions" & others
    • introducing P & NP problems
    • other universal computing paradigms
      • Conway's game of life
      • UTM running on a bintree instead of a linear tape
  • boolean algebra
    • normal forms (CNF, DNF)
    • satisfiability(of CNF)/non-validity(of DNF) (hard)
    • prefix normal form
  • lambda calculus
    • currying
    • lambda terms
      • infinite supply (x0, x1, x2, ...)
      • application
      • abstraction
    • free variables vs. bound variables
    • shadowing
    • alpha-conversion (renaming a bound variable)
    • beta-reduction (applying an abstraction)
    • pairs, and the "True", "False" abstractions(functions)
    • recursion, and intro to the Y-combinator
    • evaluation order
      • deterministic strategies
        • applicative order (start with rightmost, innermost)
          • it sometimes loops forever
        • normal order (start with leftmost, outermost)
          • it sometimes duplicates work (but can be solved by caching,
            aka "lazy evaluation")
      • non-deterministic strategies
        • inherent parallelism
  • counting
    • set, multiset, list, permutation
      • bitstring/signature
    • some counting principles
      • invariance
      • disjoint sum
      • cartesian product
    • counting "weak compositions" & "compositions"
    • counting functions f: S -> T, given |S|, |T| (power)
      • counting surjective functions f (Stirling number of the second kind)
  • graphs
    • directed graph (aka "digraph")
    • "walk", "path", "cycle"
    • tree
    • example: counting binary trees which have n nodes
    • using transition matrices
      • counting walks
        • using generating functions, on matrices
    • Eulerian cycles
    • Hamiltionian cycle
    • minimum spanning trees
      • Prim's algorithm
      • Kruskal's algorithm
    • shortest path
      • Dijkstra's algorithm
  • using generating functions
    • example: Fibonacci sequence
    • example: Pascal's triangle (two-param GenFunc) (combinations)