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
• 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
• 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
• it sometimes loops forever
• 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)